CS 5510 Homework 3

Due: Thursday, September 15th, 2011 10:45am

Part 1 – Conditionals

Start with the F1WAE interpreter plus compiler that uses deferred substitution. Add an if0 form to the language:

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

The interpreter should evaluate if0 by evaluating the first sub-expression. If it produces 0, then the interpreter should evaluate the second sub-expression and return its result (and not evaluate the third sub-expression). If the first sub-expression produces any other number, the interpreter should evaluate the third sub-expression and return its result (and not evaluate the second sub-expression).

Also fix compile and cinterp to support if0, and add test cases for interp*.

Some examples:

  (test (interp (parse '{if0 0 1 2})
                (list)
                (mtSub))
        1)
  (test (interp (parse '{if0 1 1 2})
                (list)
                (mtSub))
        2)
  (test (interp (parse '{if0 {f 5} 1 2})
                (list (parse-defn '{deffun {f x} {- x 5}}))
                (mtSub))
        1)
  (test (interp* (parse '{if0 {f 5} 1 2})
                 (list (parse-defn '{deffun {f x} {- x 5}})))
        1)

Part 2 – Compiling Function Names to Offsets

The starting compiler for F1WAE preserves function names in application forms. Since the order of function definitions never changes, however, the compiler could convert a function name into an index into a list of function bodies.

Change the representation of capp and the compile function so that a capp has a function index instead of the name. Of course, compile will need to take a list of defined functions (or at least the names) in addition to an expression.

Also change cinterp to take a Racket list of function-body expressions, instead of a list of CFunDef. You should be able to remove theCFunDef datatype completely.

Finally, be sure to change interp* so that it works with the revised compile and cinterp functions.

All of the old interp* tests should work, and you should add more to include tests with multiple definitions.