## CS 5510 Homework 5

Due: Friday, September 29th, 2017 11:59pm

*Note: due date is on Friday instead of Wednesday, since there’s a mid-term on Tuesday*

Start with `lambda+if0.rkt`, which doesn’t already include recursive binding and also doesn’t include `*` for multiplication.

### Part 1 — Syntactic Sugar for Recursive Bindings

Extend the `parse` function so that it supports a `letrec` form for recursive function bindings.

<Expr> = ...
| {letrec {[<id> <Expr>]} <Expr>}

You should not change the `interp` function at all.

The September 21 lecture slides spell out (at the beginning of part 3) how to extend the parser to make `letrec` work, based the expansion shown at the end of the September 19 lecture slides. 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 `plai-typed` definition. The value of `mk-rec-fun` is a representation of the concrete syntax of a book-language expression. If you pass `mk-rec-fun` to `parse`, you get a `plai-typed` value that is an `interp`retable representation of a book-language expression.

Example:

(test (interp (parse '{letrec {[f {lambda {n}
{if0 n
0
{+ {f {+ n -1}} -1}}}]}
{f 10}})
mt-env)
(numV -10))

### Part 2 — Implementing a Two-Argument Function in the Book Language

Define the `plai-typed` constant `plus` as a representation of the concrete syntax of a book-language 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 `plai-typed` number *n* and *m*.

In other words, you add a `plai-typed` definition

(define plus '{lambda ....})

to the interepreter program, replacing the `....` with somethig that creates the desired book-language function.

You should not change the `interp` or `parse` function for this part.

### Part 3 — Implementing a Recursive Function in the Book Language

Define the Racket 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 `plai-typed` integers *n* and *m*.

You should not change the `interp` or `parse` function for this part.

Last update: Sunday, September 24th, 2017mflatt@cs.utah.edu |