COSC 152 Programming Languages

Fall 2006

Homework Assignment #5

A Simple Interpreter
Due: Wednesday, Oct 11, 2:00PM CDT
Submit: E-mail electronic copy to professor, with a subject header "COSC 152 HW#5".
Work may be completed in groups of up to three students. Each group should submit only once. Be certain to put all team member names on work submitted. It would be courteous to carbon-copy your team mates when e-mailing the final submission.
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