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

• Conditionals
  
  

  To save the trouble of having to add boolean values and operators over them, simply create if using the syntax described by the EBNF below. Note 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.

• Multi-armed rec
  
  

  Using the datatype definition of environments, implement a multi-armed rec construct that cyclically binds zero or more identifiers. If there are multiple bindings of the same identifier in a single rec expression's list of bindings, your interpreter should halt with an error message. Each named expression can access all the identifiers bound by the rec. All the named expressions must syntactically be functions.

• Multi-argument fun
  
  

  Extend the fun language feature described in lecture so that functions can accept a list of zero or more arguments instead of just one. All arguments to the function must evaluate in the same environment. To simplify your program, you may assume that the number of arguments in a function invocation always matches the number in the procedure definition.

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

{rec {{odd? {fun {n}
              {if n
                {even? {- n 1}}
                0}}}
      {even? {fun {n}
              {if n
                {odd? {- n 1}}
                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>*}

FAQ

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.