Lazy evaluation

Lazy evaluation means that the actual parameter of a function is not evaluated until the corresponding formal parameter is used.  Two ways to implement lazy evaluation are pass-by-name and pass-by-need.  With pass-by-name, the actual parameter is re-evaluated each time the formal parameter is used.  With pass-by-need, the actual parameter is evaluated only the first time the formal parameter is used, and then its value is saved in case this formal parameter is used again.

In the provided implementation of mScheme, parameters of programmer-defined functions are passed-by-value, but parameters of primitive functions such as "if" and "while" use lazy evaluation.  The goal here is to permit parameters of programmer-defined functions to also be evaluated lazily.

Extend the definition of mScheme as follows:  Actual parameters placed inside curly braces { } will be passed-by-name, and actual parameters placed inside square brackets [ ] will be passed-by-need.

Example

Consider this mScheme function: (define f (x y z) (+ (* x x) (* y y))).

Note that the function f accesses x two times, accesses y two times, and does not access z.

Call f using pass-by-value: (f (print 3) (print 4) (print 5)) displays 3, 4, 5 and returns 25.

Call f using pass-by-name: (f {(print 3)} {(print 4)} {(print 5)}) displays 3, 3, 4, 4 and returns 25.

Call f using pass-by-need: (f [(print 3)] [(print 4)] [(print 5)]) displays 3, 4 and returns 25.

Implementation

Lazily evaluated parameters are passed as "thunks".  Thunks are similar to closures, in that each consists of an expression and an environment.  However, a thunk may contain any kind of expression, whereas a closure can only hold a lambda expression.  Also, a thunk is evaluated when its value is accessed, whereas a closure corresponds to a function that must be invoked.

To implement a thunk for a pass-by-need parameter, when the thunk is evaluated to obtain its value, replace this thunk by its value so that the same thunk will not be re-evaluated again later.  Of course, do not perform such a replacement when implementing a thunk for a pass-by-name parameter.

Primitive functions should evaluate thunks only when necessary, as with "+" and "*" in the preceding example.  However, note that the "cons" function can create a pair object without evaluating its two parameters.  Thus it is possible to build a list that contains thunks.  Within lists, thunks should be displayed as either {thunk} or [thunk].

Example: lazy lists

We can create a useful infinite list via this recursive mScheme function:

(define infinite-sequence (x) (cons x [(infinite-sequence (+ x 1))])).

(val L (infinite-sequence 1)) displays the value of L as (1 [thunk]).

Next access an element within the list:  (car (cdr (cdr (cdr L)))) displays 4.

L should now display as (1 2 3 4 [thunk]).  Logically, L is an infinite list, but only a finite prefix of L can be visited and displayed.

Note that this example depends upon the use of lazy evaluation.  It would not work properly if using pass-by-value.