CS 5510 Homework 4

Due: Tuesday, September 27th, 2011 10:45am

Start with the FAE+inf0 interpreter, which includes support for an if0 form:

  <FAE> = ...
        | {if0 <FAE> <FAE> <FAE>}

  (test (interp (parse '{if0 0 1 2}) (mtSub)) (numV 1))
  (test (interp (parse '{if0 7 1 2}) (mtSub)) (numV 2))
  (test (interp (parse '{with {x 0} {if0 x 1 2}}) (mtSub)) (numV 1))

Part 1 – Syntactic Sugar for Local Bindings

Extend the parse function so that it supports a with form for local binding.

  <FAE> = ...
        | {with {<id> <FAE>} <FAE>}

The result of parsing a with function should be an equivalent application of a function. For example, (parse '{with {x 1} {+ x x}}) should produce the same value as (parse '{{fun {x} {+ x x}} 1}).

You should not change the interp function at all.

Part 2 – Syntactic Sugar for Recursive Bindings

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

  <FAE> = ...
        | {rec {<id> <FAE>} <FAE>}

You should not change the interp function at all.

The September 15 lecture slides spell out in detail how to extend the parser to make rec work. You may find the following Racket definition useful:

  (define mk-rec-fun
    '{fun {body-proc}
          {with {fX {fun {fX}
                         {with {f {fun {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 Racket 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 Racket value that is an interpretable representation of a book-language expression.

Example:

  (test (interp (parse '{rec {f {fun {n}
                                     {if0 n
                                          0
                                          {- {f {- n 1}} 1}}}}
                          {f 10}})
                 (mtSub))
          (numV -10))

Part 3 – Implementing a Two-Argument Function in the Book Language

Define the Racket constant plus as a representation of the concrete syntax of a book-language expression such that

   (interp (parse (list (list plus n) m)) (mtSub))

produces the same value as

   (interp (parse (list '+ n m)) (mtSub))

for any Racket number n and m.

In other words, you add a Racket definition

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

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

Part 4 – Implementing a Recursive Function in the Book Language

Define the Racket constant times such that

   (interp (parse (list (list times n) m)) (mtSub))

produces the same value as (numV (* n m)) for any non-negative Racket integers n and m.