Extended Interpreters

1. Write a parser and interpreter for the FWAE language we’ve discussed in class, extended with the language features described below. Your interpreter should have eager application semantics and use deferred substitution. Call the new language CFWAE (conditionals, functions, with, and arithmetic expressions).


2. [Extra Credit] After completing the first part of the assignment, copy the resulting interpreter and modify it 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 tested and debugged!)

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 CFWAE-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, create the construct if0 using the syntax described by the EBNF below. Note that if0 has three branches:

• A test expression
• A “then” expression, which evaluates if the test expression evaluates to zero
• An “else” expression, which evaluates for any other number.

Evaluation should signal an error for non-numeric test values.

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 with the same deferred substitutions. To simplify your program, you may assume that the number of arguments in a function invocation always matches the number in the procedure definition. For example:

{{fun {x y} {* x y}} 2 3}

evaluates to 6.

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

<CFWAE> ::= <num>
    | {+ <CFWAE> <CFWAE>}
    | {- <CFWAE> <CFWAE>}
    | {* <CFWAE> <CFWAE>}
    | <id>
    | {if0 <CFWAE> <CFWAE> <CFWAE>}
    | {with {{<id> <CFWAE>} ...} <CFWAE>}
    | {fun {<id> ...} <CFWAE>}
    | {<CFWAE> <CFWAE> ...}

In this grammar, the ellipsis (...) means that the previous non-terminal is present zero or more times.

Get Points Back

This assignment builds on the previous. If you know your rudimentary interpreter had problems, and you fix those problems in your extended interpreter, and you provide test cases to prove this, and you tell us what you fixed, we’ll give you back any points that you lost for functionality.

Describe what you fixed in comments at the top of your program.

FAQ

• Nothing yet