CS 5510 Homework 5

Due: Wednesday, September 28th, 2016 11:59pm

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 22 lecture slides spell out in detail (at the beginning of part 3) how to extend the parser to make letrec work. 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.

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.


Last update: Tuesday, November 15th, 2016
mflatt@cs.utah.edu