CS 5510 Homework 4

Due: Friday, October 2nd, 2009 9:40am

Part 1 – Syntactic Sugar for Recursive Bindings

Start with the FAE+inf0 interpreter. The interpreter already 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))

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

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

(Note that this rec should not be confused with the rec of HW 3, which is an unfortunate naming collision. We use rec this time to be consistent with the book.)

You chould not change the interp function at all.

The September 28 lecture slides spell out in detail how to extend the parser to make rec work. You may find the following Scheme 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}}})

Example:

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

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

Define the constant plus such that

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

produces the same value as

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

for any n and m.

In other words, you add a Scheme definition

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

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 constant times such that

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

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