CSE 130, Summer Session I, 2008

Programming Languages: Principles and Paradigms

Programming Assignment 2

The purpose of this assignment is to learn about interpreting by writing and extending an interpreter for the WAE language in PLAI. It is to be completed individually according to the course collaboration policy.

You can work on this assignment using DrScheme or MzScheme on ACS machines or on your own machine. Wherever you work, you first have to install the PLAI language. Once installed, it will work in both DrScheme and MzScheme, and you will find documentation for the PLAI language by selecting "Help Desk" from the Help menu in DrScheme, and then following the link labeled Programming Languages: Application and Interpretation under the heading "Languages".

Tasks

First, write a parser and interpreter for the WAE language in PLAI. The book will be of great assistance; it provides the beginnings of a parser, an abstract syntax datatype, and an interpreter. Once you've written and tested the parser and interpreter for WAE, extend the language with these features:

Generic Binary Arithmetic Operators

The parse and calc functions in the book use separate rules for addition and subtraction. You will replace these separate rules with a generic implementation for binary arithmetic operators.

• Using an appropriate data structure, associate each operator name (a symbol) with a (Scheme) procedure that performs the operation.
• When parsing a binary operator application (in the concrete syntax), look up the operator name and return a binop datatype variant of WAE containing the procedure for that operator.
• When evaluating a binop variant (in the abstract syntax), use the procedure value you stored while parsing.

Once you have implemented addition and subtraction this way, you can add other binary operators without modifying your functions; you need modify only your data structure. To illustrate this, add associations for the symbols * and / to procedures that implement multiplication and division, and write your own automated tests for this functionality.

Parallel Bindings in with

The WAE language in the book includes a with construct that binds a single identifier to the value of an expression. You will modify the with construct to bind any number of identifiers to values, as with Scheme's let.

• Your with will have a list of bindings together with a single expression as its body.
• Each binding specifies an identifier and an expression whose value will be bound to the identifier only while evaluating the body of the with.
• An expression in the binding list may refer to identifiers bound outside the with, but not to other identifiers bound in the same binding list.
• An identifier may appear at most once in each binding list.
• Reserved symbols (keywords and operator names) may not be re-bound.
• Your abstract syntax will use a Binding type defined in the code given to you.

Resulting Grammar

Here is a BNF grammar for the resulting WAE language:

<WAE> ::= <num>
        | {<binop> <WAE> <WAE>}
        | {with {<binding> ...} <WAE>}
        | <id>

<binop> ::= + | - | * | /

<binding> ::= {<id> <WAE>}

The ellipsis (...) means the previous non-terminal is present zero or more times.

Error Messages

Your parser will need to detect illegal syntax. The tests include an example of each error your parser must detect, and the message it should pass to Scheme's error function.

Testing

As with the previous assignment, you will need to think carefully about where your code might fail and add your own test cases to the test file. Once again your submission will be tested against a more comprehensive suite of tests than we gave you and we may also assess the quality of your tests.

Submitting Your Work

• Copy your files to an ACS GNU/Linux machine (if they're not already there).
• Before submitting your work, it's a good idea to make sure it runs in MzScheme on an ACS GNU/Linux machine and passes all the tests we've given you.
• In the directory where your files are, run bundle-pa2 and follow the directions. (If you haven't run prep cs130u yet, you'll have to do that first.)
• You can overwrite earlier submissions until the deadline, so submit early and often!
• After the deadline the bundle script will no longer work. Late submissions will be accepted only by arrangement with the instructor.