Assignment #3: Basic Interpreter Extension

This assignment is for pair work and submission. You need to register as pairs by mailing me. Only one of the two should send the email, but make sure you CC the other. Also mail me if you don’t know anyone to work with, and I will assign you semi-randomly. (But note that this will take a few days.)
You must register! You will not be able to submit your work if you do not register — so email me whether you have a partner or not.

The homework does not require a lot of work, and even if you don’t have a partner you should start doing it anyway. If you get assigned in time, then you can later combine the work each of you has done.

The language for this homework is:

The homework is basically a simple extension of the WAE language that we have seen in class. The extension itself is relatively straightforward, and it will be easy to follow the simple steps to achieve it. In this sense, it is also a kind of an introduction, although not as basic as the previous homeworks.

After a great success story deploying WAE in your company as a simple language for frotzing, the single most popular feature that people want is being able to use postfix syntax in a similar way to some scientific calculators. You are now assigned the job of doing so.

The WAE language is itself quite simple, so this work is not going to take long. You will do this in three steps that correspond to the three parts of the evaluator: extending the syntax, the substitution function and finally the evaluator.

Begin by downloading the WAE language implementation to serve as the basis of your work. The new language was supposed to have a reasonable name: “PWAE” (Postfixed WAE), but someone in marketing thought that adding a ‘U’ makes it more marketable, so it is to be called “PUWAE” (pronounced “POOOh-wah”, of course). Begin by replacing all of the WAE references in the file to PUWAE.

In its original form, the WAE implementation, or now your PUWAE implementation, does not have complete coverage. Extend the set of tests to get complete coverage. Make sure that when you finish your work you still have complete coverage, as required by the server.

PUWAE extends the WAE syntax in a simple way: a single new post form is added to the language, which can look like this:

Extend the formal grammar for the language first, and the data type definition next. Given the nature of the new syntax (containing either one of a few known names or a PUWAE expression), it is easiest to use a utility rule — the main BNF should be extended with:

The type definition should also be extended accordingly: you need to add another AST constructor for postfix constructs. If we stick with the rule of directly correlating BNF non-terminals with datatypes and rules with variants, then we would need another type definition for the <POST> entry. But in this case we can use Typed Scheme’s ability to express unions instead, which will lead to simpler code. You should therefore extend the PUWAE type definition with a single Post variant, holding a list of unions. The union should be of a PUWAE expression, or one of the four arithmetic operation names as symbols: (U PUWAE '+ '- '* '/). We’re also using here the Typed Scheme feature of specifying a symbol as a type for all values that are just that symbol. This type is going to be used in several places in the code, so it will make things easier to define a name for it. The following form will bind a new PostfixItem type that stands for the union:

The last step in the syntax part of the language is, of course, extending the parser. This should be relatively straightforward: you need to identify forms that begin with post, and scan their contents for arithmetic symbols (which are left as is) or anything else (which will be parsed recursively). To make this simple, add the following helper function:

Dealing with substitution is going be easier than the above. You basically need to add one case for dealing with the new Post AST values. It is best to do this with a local helper function definition:

You don’t need to extend the formal definition of the subst function (this will be tricky because of the union in the syntax). So you can just as well remove the formal definition. The same applies to the formal eval definition, so you can remove that too now.

Finally, you need to extend the evaluation function as well. Again, this involves adding a new case for dealing with Post AST values. And again this is easy to do using a utility function, post-eval. The definition of this function should be simple now that you’ve done all of the above. You basically need to get a list of postfix items, and go over the list evaluating expressions and performing arithmetic operations. As common with most post-fix languages, this is done with a ‘stack’ of values that should be kept throughout the post-eval call. Note that each post-eval call uses its own stack, passed in as an additional argument, and the first call to each (in eval) will pass in an empty list to initialize it. post-eval will call itself recursively (implementing the loop over the postfix items) or call eval (to evaluate expressions.)

The post-eval function will basically perform the post-fix evaluation, where each of the four symbols represents the corresponding binary arithemtic function (that is, exactly two inputs for each function). It should throw a (run-time) error if it runs out of stack values, or if it has leftover values at the end. This means that expressions like:

For operations that are non-commutative (where the order matters), our post expressions should behave like most RPN calculators do. Here is a test that demonstrates the expected result:

Notes:

• It will be convenient to use match to deal with the stack — check that you have two values for an operation, check that you have exactly one value when you’re done, etc. However, note that when you match a list of numbers, use a pattern like (number: xs) ... so that Typed Scheme will know that you have numbers there.
• Since you will have four pieces of code, one for each operator, and they are not as straightforward as in eval, it will make your work much easier to define a local helper function that will pull out two values from the stack and apply a Scheme function on them.

Define minutes-spent as the number of minutes you spent on your homework.