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 interpretable 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.