COSC 3410 Programming Languages
Fall 2011
Homework Assignment #5
A Simple Interpreter
Due: Wednesday, Oct 12, 11:00am CDT
Submit: Turn in
Scheme source files called "hw5.scm" (your interpreter) and "hw5-test.scm" (a SchemeUnit testsuite for your interpreter)
using the
turnin command on
the
Systems Lab
machines. Include the names of all authors at the top of the files
in a comment block.
Work may be completed in pairs. Each team should have only one member turnin.
The Grammar
For this assignment, we will be using the language specified by the following
grammar:
<expr> |
::= |
<number> |
| | |
<symbol> |
| | |
( lambda ( {<symbol>}* )
<expr> ) |
| | |
( if <expr> <expr>
<expr> ) |
| | |
( <prim-op> <expr>
<expr> ) |
| | |
( <expr> {<expr>}*
) |
<prim-op> |
::= |
add |
| | |
sub |
| | |
mul |
| | |
div |
| | |
mod |
where the primitive operators for addition, subtraction, multiplication,
division, and modulus always take two arguments.
Abstract Syntax
Implement the necessary abstract syntax trees (variant records) to represent
the grammar above, in the style shown in EoPL and in lecture.
Parser
Implement parse and unparse for translating between the
concrete and abstract syntaxes.
Simple Interpreter
Implement evaluate which takes an abstract syntax tree and returns
the result of evaluating the expression represented.
For example:
> (evaluate (parse '(add 4 5)))
> 9
> (evaluate (parse '(sub (mul 4 5) (mod 10 3))))
> 19
Notes:
Although our input grammar includes lambda terms and applications,
for now your evaluate function may throw an error if you encounter
a lambda term or an application of anything other than a primitive
operator. Note that this implies there will be no variable
definitions.
Since our language does not include booleans, assume that the
if expression evaluates the true branch if the
condition evaluates to any non-zero value. Conversely, the
expression evaluates the false branch if the condition expression
evaluates to zero.
Check rigorously for errors in the input, or for invalid expressions.
Appropriate errors should be thrown if your interpreter
encounters any trouble. See the eopl:error construct
used in the text. Think carefully about what kinds of errors the
interpreter can encounter.
Back
[Revised 2011 Oct 05 12:24 DWB]