Project 1: a Rudimentary Interpreter

Assigned 21 Sept, due 19 Oct

This exercise is based on one from CS 173 at Brown University. Some differences: it was their first assignment of the semester, not the third (they were expected to learn Scheme on their own, with some tutorial exercises), and they were given a week to do it rather than three weeks. Think about that before begging for an extension.

For every function you write, you must include a contract and a well-chosen set of test cases.

For this assignment, switch languages in Racket to "Use Language Declared in Source", and replace the #lang racket with #lang plai.

Warm-up exercise

1. Type in the definitions (from PLAI chapter 1) of the AE data type and the parse function. Make sure the parse function passes all of its tests. Make up some more test cases of your own, and make sure it passes them.
2. Type in the definition (from PLAI chapter 2) of the calc function. Make sure it passes all of its tests. Make up some more test cases of your own, and make sure it passes them.

WAE

3. Type in the definition (from PLAI chapter 3) of the WAE data type. Modify your parse function so it handles the full WAE syntax. Make sure it passes all its test cases.
4. Type in the definitions (from PLAI chapter 3) of the subst and calc functions. Make up a few additional test cases of your own, and make sure it passes all of them. (I'm going to stop saying that now; take it as read.)

Binary arithmetic operators

At present, there are separate rules for + and -, and if we wanted to add * or /, we would need to change the parser, change the subst function, and change the interpreter. This is a pain.

5. Define a data type BWAE, like WAE but with a single case named binop to handle all binary operators. Modify the parser so it produces BWAE parse trees.
6. Define a lookup function that takes in an operator (a symbol, like '+, '-, etc.) and returns the corresponding built-in function. (Yes, a Scheme function can easily return a function as its value.) If the given symbol isn't the name of a built-in function, your function should return false.
7. Modify the subst and calc functions so they work correctly on BWAE parse trees.
8. To demonstrate how much more extensible your language is now, add support for the * and / operators. You shouldn't need to change the definitions of BWAE, subst, or calc at all -- only the lookup function, and perhaps a trivial change to parse.

Multi-armed with

9. At present, each with binds exactly one new variable. Modify the language to allow a with to bind zero or more variables simultaneously (that is, not depending on one another). If the same identifier is bound more than once in the bindings list of the same with, your parser should halt with an error message.

   For example,

   {with {{x 2}
          {y 3}}
     {with {{z {+ x y}}}
       {+ x z}}}
   

   should evaluate to 7, while

   {with {{x 2}
          {x 3}}
   	{+ x 2}}
   

   should halt with an error message. And

   {with {{x 2}}
     {with {{x {+ x 1}}
            {y {+ x 2}}}
        {* x y}}}
   

   should evaluate to 12 (not 15!).

   This may require defining a new abstract syntax (MBWAE?), modifying the parser, modifying the subst function, and/or modifying the interpreter.

Testing and errors

Your parser and interpreter must detect errors and explicitly signal them by calling (error ...). (Look it up in the Help Desk.) I shall consider an error raised internally by Scheme to be a bug in your code.

For example, the parser should detect a with that binds the same identifier more than once, and signal an error before calc ever sees it. If the parser does not signal an error in such cases, it's a bug.

Scheme signals a "divide by zero" error if you attempt to evaluate (/ 1 0). You may be tempted to have your calc function just use Scheme's division operator to detect and signal this error. This will be considered a bug: you need to detect division-by-zero yourself, and signal it yourself, before calling Scheme's division procedure.

To test whether your function has correctly raised an error, look up the test/exn function in the Help Desk. Note that it only catches errors that you signal, not those raised by built-in functions.

What to Turn In

Turn in four Racket source files: ae.rkt, wae.rkt, bwae.rkt, and mbwae.rkt containing the source code for the four stages of the assignment. If you don't get them all working, turn in as much as you've got, with an explanation of where you got stuck and what you've tried.