Due: Tuesday, October 13th, 2020 11:59pm
Difficulty: ★★☆☆
Start with lambda+if0.rkt, which doesn’t already include recursive binding and also doesn’t include * for multiplication.
Extend the parse function so that it supports a letrec form for recursive function bindings.
<Exp> = ... | {letrec {[<Symbol> <Exp>]} <Exp>}
You must not change the interp function at all.
The October 7 lecture slides spell out how to extend the parser to make letrec work, especially at the end of part 4. You may find the following definition useful:
(define mk-rec-fun `{lambda {body-proc} {let {[fX {lambda {fX} {let {[f {lambda {x} {{fX fX} x}}]} {body-proc f}}}]} {fX fX}}})
The above definition makes sense only if you can keep track of different languages and how they interact. The mk-rec-fun definition above is a Plait definition. The value of mk-rec-fun is a representation of the concrete syntax of a Curly expression. If you pass mk-rec-fun to parse, you get a Plait value that is an interpretable representation of a Curly expression.
Example:
(test (interp (parse `{letrec {[f {lambda {n} {if0 n 0 {+ {f {+ n -1}} -1}}}]} {f 10}}) mt-env) (numV -10))
Define the Plait constant plus as a representation of the concrete syntax of a Curly expression such that
(interp (parse (list->s-exp (list (list->s-exp (list plus `n)) `m))) mt-env)
produces the same value as
(interp (parse (list->s-exp (list `+ `n `m))) mt-env)
for any Plait number n and m.
In other words, you add a Plait definition
(define plus `{lambda ....})
to the interepreter program, replacing the .... with somethig that creates the desired Curly function.
You should not change the interp or parse function for this part.
Define the Plait constant times such that
(interp (parse (list->s-exp (list (list->s-exp (list times `n)) `m))) mt-env)
produces the same value as (numV (* n m)) for any non-negative Plait integers n and m.
You should not change the interp or parse function for this part.
Last update: Tuesday, October 13th, 2020mflatt@cs.utah.edu |