Homework #6 Solution

Implement an interpreter with lazy evaluation and the following grammar:

<Exp = <Number
| <Symbol
| {+ <Exp <Exp}
| {* <Exp <Exp}
| {lambda {<Symbol} <Exp}
| {<Exp <Exp}
| {let {[<Symbol <Exp]} <Exp}
| {if0 <Exp <Exp <Exp}
| {pair <Exp <Exp}
| {fst <Exp}
| {snd <Exp}
That is, a language with single-argument functions and application, an if-zero conditional, and pair, fst, and snd operations. (The language does not include recursive bindings or records.) Unlike cons, the pair operation does not require its second argument to be a list (and we do not have an empty-list value, anyway).

Implement your interpreter with the eager Plait language, not a lazy language.

Evaluation of the interpreted langauge must be lazy. In particular, if a function never uses the value of an argument, then the argument expression should not be evaluated. Similarly, if the first or second part of a pair is never needed, then the first or second expression should not be evaluated.

Start with more-lazy.rkt. Expand the parse function to support the new forms: if0, pair, fst, and snd. Also, as in HW 4, provide an interp-expr function; the interp-expr wrapper for interpshould take an expression and return either a number S-expression, `function for a function result, or `pair for a pair result. (Meanwhile, the interp function should never return the symbol `pair, just like the starting interp function never returns the symbol `function.) Note that pair results must distinct from function results, so you will need to modify interp and not just use encodings via parse.

(test (interp-expr (parse `10))
`10)
(test (interp-expr (parse `{+ 10 17}))
`27)
(test (interp-expr (parse `{* 10 7}))
`70)
(test (interp-expr (parse `{{lambda {x} {+ x 12}}
{+ 1 17}}))
`30)

(test (interp-expr (parse `{let {[x 0]}
{let {[f {lambda {y} {+ x y}}]}
{+ {f 1}
{let {[x 3]}
{f 2}}}}}))
`3)

(test (interp-expr (parse `{if0 0 1 2}))
`1)
(test (interp-expr (parse `{if0 1 1 2}))
`2)

(test (interp-expr (parse `{pair 1 2}))
`pair)
(test (interp-expr (parse `{fst {pair 1 2}}))
`1)
(test (interp-expr (parse `{snd {pair 1 2}}))
`2)
(test (interp-expr (parse `{let {[p {pair 1 2}]}
{+ {fst p} {snd p}}}))
`3)

;; Lazy evaluation:
(test (interp-expr (parse `{{lambda {x} 0}
{+ 1 {lambda {y} y}}}))
`0)
(test (interp-expr (parse `{let {[x {+ 1 {lambda {y} y}}]}
0}))
`0)
(test (interp-expr (parse `{fst {pair 3
{+ 1 {lambda {y} y}}}}))
`3)
(test (interp-expr (parse `{snd {pair {+ 1 {lambda {y} y}}
4}}))
`4)
(test (interp-expr (parse `{fst {pair 5
;; Infinite loop:
{{lambda {x} {x x}}
{lambda {x} {x x}}}}}))
`5)

(test (interp-expr
(parse
`{let {[mkrec
;; This is call-by-name mkrec
;; (simpler than call-by-value):
{lambda {body-proc}
{let {[fX {lambda {fX}
{body-proc {fX fX}}}]}
{fX fX}}}]}
{let {[fib
{mkrec
{lambda {fib}
;; Fib:
{lambda {n}
{if0 n
1
{if0 {+ n -1}
1
{+ {fib {+ n -1}}
{fib {+ n -2}}}}}}}}]}
;; Call fib on 4:
{fib 4}}}))
`5)

(test (interp-expr
(parse
`{let {[mkrec
;; This is call-by-name mkrec
;; (simpler than call-by-value):
{lambda {body-proc}
{let {[fX {lambda {fX}
{body-proc {fX fX}}}]}
{fX fX}}}]}
{let {[nats-from
{mkrec
{lambda {nats-from}
;; nats-from:
{lambda {n}
{pair n {nats-from {+ n 1}}}}}}]}
{let {[list-ref
{mkrec
{lambda {list-ref}
;; list-ref:
{lambda {n}
{lambda {l}
{if0 n
{fst l}
{{list-ref {+ n -1}} {snd l}}}}}}}]}
;; Call list-ref on infinite list:
{{list-ref 4} {nats-from 2}}}}}))
`6)