Assignment 2

Due: Tu Feb 4

Exercise 3.17

Consider a language extension to support lazy evaluation in Mini-ML. For this we introduce a new type constructor #, where #t   is the type of suspensions of type t. There should be a new constructor delay e and a destructor let delay u = e₁ in e₂. The intent is that we substitute an expression for u which need not be a value.

1. Extend the typing, value, and evaluation judgments.
2. Define a function force which has type (#a) -> a for a type variable a.
3. Prove that force (delay e) evaluates to v if and only if e evaluates to v according to your operational semantics.
4. Represent the new expression constructors in LF.
5. Represent the new value rules in LF.
6. Represent the new evaluation rules in LF.
7. Extend the proof of type preservation (Theorem 2.5).
8. Extend the proof of value soundness (Theorem 2.1).
9. Extend the definition of the value soundness judgment (Section 3.7) and give a representation of the new cases in LF.
10. Another choice of primitives for suspensions are delay e and force e. Compare this to the primitives delay and let delay used above. Do you see any advantages or disadvantages?