Languages that support function calls and let statements choose between eager and lazy evaluation. In eager evaluation, a language evaluates the arguments before calling the function. In lazy evaluation, the language only evaluates the arguments when the variables they refer to are used. Here's an example of the steps that would occur when evaluating the same program under both eager and lazy evaluation:
(define (f x y)
(+ x y))
(f (* 3 4) (* 5 9))
------------------------------------------------------------
EAGER LAZY
(f (* 3 4) (* 5 9)) (f (* 3 4) (* 5 9))
(f 12 45) (+ (* 3 4) (* 5 9))
(+ 12 45) (+ 12 45)
57 57
To avoid scoping problems, assume we are working with programs with no free variables.
In class, we have implemented eager evaluation with both static and dynamic scoping. This assignment explores lazy languages.
Provide a single Scheme program that will produce different answers under lazy and eager evaluation with static scoping. Your program may not use any form of assignment operator. Show the computation steps and the result in each case.
Think simple. You can do this in only a couple of lines of code.
Implement a environment-passing interpreter with lazy evaluation and static scoping for the AFunExp language from the notes (ie, the language with numE, varE, addE, multE, funE and appE).
As a test case, the expression
(let ([y 5])
(let ([x (+ y 1)])
(let ([y 4])
x)))
should return 6 under lazy evaluation with static scoping. You should also
develop your own test cases.
In class, you implemented mutation (setE expressions) using Scheme boxes. Scheme boxes provide a form of assignment operator. Thus, we used assignment in the implementation language to add assignment to our new language. What if you had to implement setE expressions in a language that doesn't have assignment operators? (such languages do exist!)
Implement an interpreter for AFun!Exp from the notes (ie, the language with numE, varE, addE, multE, setE, funE and appE) with eager evaluation and static scoping. Use environments. Your implementation may not use any Scheme assignment operator (such as boxes, set!, any operator with ! in its name, etc). You will be penalized for any violations of the spirit of this assignment, so don't expend energy trying to find what you think are loopholes (such as hash-tables, or using external procedures so you can exploit some other language's implementation of state).
Think hard about this for a while. If you're still stuck after a couple of days (not hours!), here's a small hint or two.
For reference, here are some examples of set! expressions that you can run (in Scheme) to see how assignment should operate:
(let ([x 4])
(let ([y x])
(set! x 5)
y))
(define y 4)
(define (f x)
(set! x 6)
x)
(f y)
y
In general, if you want to know what answer your mutating interpreter should yield for this assignment, run the corresponding Scheme program.