Homework 5: Lazy Evaluation Solution

Introduction




This homework will highlight lazy evaluation. Note: Part 3 is the most

substantial part of the homework.




To start, create a directory in your personal repository named ``Hwk_05``.

You must place all files for this homework in this directory.




Part 1: Evaluating expressions by hand




As demonstrated in class, and in the document "Expression Evaluation

Examples" (``expr_eval.pdf`` in ``Resources`` on GitHub), we have

evaluated expressions by hand, step by step, to understand the

different ways in which call by value semantics, call by name

semantics, and lazy evaluation work.




Question 1




Consider the following definitions:




```

sum [] = 0

sum x::xs - x + sum xs




take 0 lst = [ ]

take n [ ] = [ ]

take n (x::xs) = x::take (n-1) xs




evens_from 0 v = [ ]

evens_from n v = v+v :: evens_from (n-1) (v+1)

```




Now, create a file in your homework directory called ``question_1.txt`` with

the following:




- Your name

- Your Internet ID




You will now evaluate the following expression by hand:




```

sum (take 3 (evens_from 5 1))

```




Similarly to the examples in ``expr_eval.pdf``, you must evaluate the

expression three times using three different semantics:




1. Call by value

2. Call by name

3. Lazy evaluation (also known as "call by need")




Label each of your evaluations clearly by evaluation strategy employed, perhaps

as in this example:

```

CALL BY VALUE







CALL BY NAME







LAZY EVALUATION

```




Please write plain text. We also will not accept handwritten work.




Question 2




Recall these definitions for ``foldl`` and ``foldr``, and the functions for

folding ``and`` over a boolean list. (Note: We removed the underscores from the

names as they appeared on the S4.1 slides.)




```

foldr f [] v = v

foldr f (x::xs) v = f x (foldr f xs v)




foldl f v [] = v

foldl f v (x::xs) = foldl f (f v x) xs




and b1 b2 = if b1 then b2 else false




andl l = foldl and true l

andr l = foldr and l true

```




Now, create a file in your homework directory called ``question_2.txt`` with

the following:




- Your name

- Your Internet ID




# Let's evaluate by hand




You will now evaluate these two expressions:




```

andl (true::false::true::true::[])

```

and

```

andr (true::false::true::true::[])

```




You must evaluate the expressions using only two different semantics:




1. Call by value

2. Call by name




Label each of your evaluations clearly by evaluation strategy employed, perhaps

as in this example:




```

andr - CALL BY VALUE







andr - CALL BY NAME







andl - CALL BY VALUE







andl - CALL BY NAME

```




A couple of notes 🎵:




+ Write lists in their basic form using the cons (``::``) and nil (``[]``)

operators instead of using semicolons to separate list values between square

brackets.




+ We don't consider lazy evaluation for this question. Why not? (Try it and

compare with your other results.)




# Which is better?




After you have completed all four evaluations (call by value and call by name

for both `andr` and `andl`), state which evaluation is most efficient and

briefly explain why.




# Reminder




As before, please write plain text. We also will not accept handwritten work.







Part 2: Efficiently computing the conjunction of a list of Boolean values




Create an OCaml file in your homework directory named ``lazy_and.ml``.




Write a function named ``ands`` with type ``bool list - bool`` which computes

the same result as the ``andl`` and ``andr`` functions described in the

problem above, except with the following quality:




Your function should avoid examining the entire list unless absolutely

necessary, hence the "lazy." (Hint: We saw this behavior in one of the by-hand

evaluations above.) Stated explicitly: If the function encounters a ``false``

value then it can terminate and return ``false``.







Part 3: Implementing Streams in OCaml




As demonstrated in class (``lazy.ml`` in ``Sample Programs`` on GitHub) we

developed a type constructor ``stream`` which can create "lazy" streams and use

lazy evaluation techniques within OCaml (which itself is a strict/eager

language).




Start this part by creating a file named ``streams.ml`` in your homework

directory and copying the following code (including comments) into it:




```

(* The code below is from Professor Eric Van Wyk. *)




(* Types and functions for lazy values *)

type 'a lazee = 'a hidden ref




and 'a hidden = Value of 'a

| Thunk of (unit - 'a)




let delay (unit_to_x: unit - 'a) : 'a lazee = ref (Thunk unit_to_x)




let force (l: 'a lazee) : unit = match !l with

| Value _ - ()

| Thunk f - l := Value (f ())




let rec demand (l: 'a lazee) : 'a =

force l;

match !l with

| Value v - v

| Thunk f - raise (Failure "this should not happen")




(* Streams, using lazy values *)

type 'a stream = Cons of 'a * 'a stream lazee




(* The code below is from YOUR NAME HERE *)

```




Change ``YOUR NAME HERE`` to your name.




***Proper attribution:** Always clearly mark all parts of your files that you

did not write, as in the code above, and attribute them to their author (your

instructor, for example). Then indicate where your work starts in the file by

adding your name and a comment to this effect, such as in the code above.*




You will now define a collection of stream values, and functions over streams.







3.1 ``cubes_from``




Define a function ``cubes_from`` with type ``int - int stream`` that creates

a stream of the cubes of numbers starting with the cube of the input value.

For example, ``cubes_from 5`` should return a stream that contains the values

125, 216, 343, ...




Demonstrate to yourself that it works by using ``take`` to generate a finite

number of cubes.




3.2 ``cubes_from_zip``




Copy the ``zip`` function from the ``lazy.ml`` file from class to your current

file (with proper attribution), then define a function ``cubes_from_zip`` with

the same type and behavior as ``cubes_from`` above, but which uses the ``zip``

function (maybe more than once) to construct the stream of cubes.




You may copy and use more functions besides ``zip`` from the ``lazy.ml`` file

from class, but you must use proper attribution.







3.3 ``cubes_from_map``




Now copy the ``map`` function from the ``lazy.ml`` file from class to your

current file (with proper attribution), and define a function named

``cubes_from_map`` with the same type and behavior as ``cubes_from`` above, but

which uses ``map``.







3.4 ``drop``




Define a function named ``drop`` with type ``int - 'a stream - 'a stream``.

This function should discard zero or more elements from the stream, and the

first argument indicates how many to discard ("drop").




*(Notice the type difference between ``drop``, and ``take`` (from ``lazy.ml``).

This is because ``take`` removes finite elements from a stream, so it stores

them as a list.)*







3.5 ``drop_until``




Write a function named ``drop_until`` with type

``('a - bool) - 'a stream - 'a stream``. This function should discard as

many consecutive initial elements as possible from the stream, and output the

remaining stream. The first argument (a function) indicates whether to keep an

element (``true`` means keep, ``false`` means drop).




Stated explicitly, this function drops elements from the input stream until it

finds one for which the function returns ``true``. It then outputs the

remaining part of the stream (including the "``true``" element it found).




Example (using ``head`` and ``nats`` from ``lazy.ml``):




```

head (drop_until (fun v - v 35) nats)

```




The above expression should give ``36``.







3.6 ``foldr``, ``and_fold``, and ``sum_positive_prefix``




Recall ``foldr`` from Part 1 above. For this question, you will define a new

``foldr`` function which uses streams instead of lists. Here are some hints:




+ Because streams have no "empty stream" or "nil" constructor, there is no

"base" value passed to your new ``foldr`` -- it takes only two arguments.

+ Your new ``foldr``'s type must include the ``lazee`` type somewhere, so it

can give a value without examining the entire stream.




For full points, you must do the following:




1. Write the ``foldr`` function with type annotations, including both input

types and the output type.

2. Write an OCaml comment above your ``foldr`` function explaining ``foldr``'s

type and briefly how your function works.







# ``and_fold``




Next, define a function named ``and_fold`` with type ``bool stream - bool``.

It attempts to determine if all elements in the stream are ``true``. If it

encounters a ``false`` element, it should return ``false``.




This function should simply pass some kind of "and" function, and the stream,

to your new ``foldr``.







# ``sum_positive_prefix``




Also, define a function named ``sum_positive_prefix``. It should use your

``foldr`` to add up all the positive integers in an ``int stream`` which appear

**before** any non-positive number.







# A concrete example




To help us think about the above functions, consider the following stream

examples:




```

let ns : int stream = zip ( - ) (from 1000) (cubes_from 1)

```




Notice that ``ns`` is an ``int stream`` computed by using subtraction to zip

together two streams; The first stream is all positive numbers starting from

1000, and the second stream is cubes starting from 1. In particular, this

stream has some positive numbers at the beginning, but then the numbers in the

stream become negative because second stream gets larger faster than the first

stream.




For example, evaluating ``take 15 ns`` yields this:




```

[999; 993; 975; 939; 879; 789; 663; 495; 279; 9; -321; -717; -1185; -1731; -2361]

```




With ``ns`` in mind, consider these two streams:




```

let are_positive ns = map (fun n - n 0) ns




let ns_positive : bool stream = are_positive ns

```

Here, ``ns_positive`` is a ``bool stream`` whose initial values are ``true``,

followed by an unbounded number of ``false`` elements.




Thus

```

and_fold ns_positive

```

will evaluate to ``false``, but

```

and_fold (are_positive (from 1))

```

will not terminate normally.




Similarly, ``sum_positive_prefix ns`` will evaluate to ``7020``, but

``sum_positive_prefix (from 1)`` will not terminate normally.




3.7 The Sieve of Eratosthenes, "``sieve``"




For this final question, we ask you to write a function which computes the

[Sieve of Eratosthenes](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes).

Here is some background:




# The Sieve




We can compute prime numbers by starting with the sequence (a stream) of

natural numbers beginning at 2 and using the following process:




1. Consider the first number in the sequence as a prime number.

2. Discard all multiples of the above number in the remaining sequence.

3. For resulting remaining sequence, go to step (1).




To see this process in action, consider this prefix of natural numbers starting

at 2:

```

2 3 4 5 6 7 8 9 10 11 ...

```




Starting at step (1), we consider 2 as prime for step (2) we discard all

multiples of 2 in the remaining sequence. Notice that because 3 is not a

multiple of 2, we won't discard it:




```

3 5 7 9 11 ...

```




We then essentially "cons" 2 onto the resulting sequence beginning at 3, which

gives us this:

```

Cons (2, 3 5 7 9 11 ... )

```




For step (3), we have the resulting sequence beginning at 3 as our new sequence

and go back to step (1) to repeat the process and get this:




```

Cons (2, Cons (3, 5 7 11 ... ))

```




You can see that we will repeat again, with 5 as the new prime and the

remaining sequence beginning at 7. This process repeats for each prime number

"discovered."




# The ``sieve`` function




Implement the above process as a function named ``sieve``, which has type

``int stream - int stream``. Here are some hints:




+ With your ``sieve`` and the ``from`` function from class, you should be able

to define the stream of prime numbers as ``let primes = sieve (from 2)``.

Thus, ``take 10 primes`` should evaluate to

``[2; 3; 5; 7; 11; 13; 17; 19; 23; 29]``.

+ You might consider a helper ``sift`` function which implements the process we

described above. For example, it could have type

``int - int stream - int stream`` and would output a stream which does not

contain any multiples of its input ``int`` argument. For example, using the

``from`` function from ``lazy.ml``, you could have ``sift 2 (from 3)`` output

the stream ``3 5 7 9 11 ...`` as we saw above.







Turning in your work




Push these files to your ``Hwk_05`` GitHub directory by the due date:

- ``question_1.txt``

- ``question_2.txt``

- ``lazy_and.ml``

- ``streams.ml``




Remember: If you use any other functions from ``lazy.ml`` that we developed in

class, then clearly denote them with proper attribution in your solution.




As in Homework 4, part of your score will be based on your code quality. (See

"Writing transparent code" in Homework 4.)




-------------------------------------------------------------------------------