Extended Interpreters FAQ

  1. Write a parser and interpreter for the RCFWAE language we've discussed in class extended with the language features described below. Your interpreter should have eager application semantics and use caching substitution as described in lecture 2003-09-12.

  2. After completing the first part of the assignment, modify the resulting interpreter so that it has lazy application semantics. (We strongly recommend that you not attempt this part of the assignment until you've gotten the first interpreter done and thoroughly debugged!)

Turn in the first and second parts of the assignment in the files part1.scm and part2.scm respectively. (You may also turn in additional files containing common code.) In each part of the assignment, implement the function parse, which consumes an expression in the language's concrete syntax and returns the abstract syntax representation of that expression, as well as the function interp, which consumes both an abstract syntax expression (as returned by the parse function) and an environment and returns a RCFWAE-value. Please include a contract for every function that you write and include test cases that amply exercise all of the code you've written.

Features to Implement

Here are two example programs that illustrate the three language features described above:

{rec {{odd? {fun {n}
              {if n
                {even? {- n 1}}
      {even? {fun {n}
              {if n
                {odd? {- n 1}}
  {odd? 5}}
which evaluates to 1 (representing truth) and
{{fun {x y} {* x y}} 2 3}
which evaluates to 6.

The syntax of the RCFWAE language with these three additional features can be captured with the following EBNF:

<RCFWAE> ::= <num>
    | {+ <RCFWAE> <RCFWAE>}
    | {- <RCFWAE> <RCFWAE>}
    | {* <RCFWAE> <RCFWAE>}
    | <id>
    | {if <RCFWAE> <RCFWAE> <RCFWAE>}
    | {with {<id> <RCFWAE>} <RCFWAE>}
    | {rec {{<id> <proc>}*} <RCFWAE}
    | {fun {<id>*} <RCFWAE>}
    | {<RCFWAE> <RCFWAE>*}


  1. You've specified that if has three branches: a test expression, a "then" expression which evaluates if the test expression evaluates to a value which is greater than or equal to 1, and an "else" expression which evaluates otherwise. What we should have said is that the "else" expression should evaluate if the test expression evaluates to 0. And, if the test expression doesen't evaluate to a number, you should signal an error.