Administrative

This homework is for working and submitting in pairs, but you need to start working on it by yourself even if you don’t have a partner. You need to email us to let us know your status: whether you do have a partner or you need one assigned to you. In the former case, to register as a pair, only one of the two should send the email, but make sure you CC the other student as well so I know that you’re both aware of it. If you don’t have a partner that you want to work with, then please send an email too, and you will be assigned one in a few days (since the assignment is based on the grading of the first two homework). Please do not try to find someone random: having an assigned partner based on your grades should overall work better in the long run.

Note that individual submissions are strongly discouraged. Also, master students have additional homework submissions, so if you are one, please find a master student for a partner (and again, email me if you want one assigned to you). For more questions, see the this FAQ section.

Reminder: submission as a pair is done using user1+user2 as the login and either one of the two passwords. (In other words, you should not share your password with your partner.)

The homework does not require a lot of work, doing it by yourself is not too hard. When you do get assigned, you will combine your work with your new partner’s work, and submit that.

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 described below complete it. In this sense, it is yet another kind of an introduction homework, although not as basic as the previous two.

Important: the handin server requires certain bound names to be present. These names need to be global definitions. The handin server cannot see names of locally defined functions.

Introduction

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 implementing that.

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 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 going to be called “PUWAE” (pronounced “POOOh-wah”, of course). As a first step, replace all of the WAEs in the file with PUWAE.

Complete Coverage

In its original form, the WAE 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. Note that your tests should all be expressed via uses of run — this is the public interface for your language, and therefore it is the only thing that you should test. It should still be possible to get complete coverage, since you should not have any code that is not reachable through it.

Extending the Syntax

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

In the post form there are any number of PUWAE expressions, and arithmetic operator names. Note that operator names in WAE and in PUWAE are not expressions — so using them inside a post form should not be taken as expressions either.

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:

and you need to add a rule for <POST>. Note that <POST> can derive a <PUWAE> too, so mixing postfix forms with the usual prefix syntax is possible, for example:

are all valid syntaxes, and they will evaluate to the same result as above.

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 Racket’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 Racket 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:

Use this type in your definition of the Post variant.

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:

(Note that this code could be made simpler with an or pattern or with the memq function, but for technical reasons this wouldn’t work.) Remember that the parser should be simple — you should not try to make it reject inputs that will not have sufficient numbers etc. For example, expressions like {post 1 2 3}, {post * *} and {post} should parse fine — only later you will get a run-time error trying to evaluate the expression (see post-eval below).

Finally, use this function in your parse-sexpr definition appropriately (use map).

Substitution

Dealing with substitution is going be easier than the above. You 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:

The reason that this function should be local is that it will use subst’s arguments too (for recursive calls). (Note: you don’t need a purpose statement since the new function is part of subst, but Typed Racket will still require a proper type declaration.)

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.

Evaluation

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 perform the post-fix evaluation, where each of the four symbols represents the corresponding binary arithmetic 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:

are valid syntactically (i.e., they will parse just fine), but will lead to a run-time error.

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. Pay attention to the type that you declare for the stack argument: it should hold a list of a specific type of values.

• 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 helper function that will pull out two values from the stack and apply a Racket function on them.

Here is a skeleton post-eval definition that you can use:

Finally

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