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

A year after your WAE implementation was successfully deployed your manager comes up with a request for extending it. Apparently, he’s been taking some advanced algebra course, and in a moment of enlightenment decided that you should have a “proper” implementation of sqrt: one that returns two results. This will have a great impact on the language, since it will now need to deal with any number of values instead of just simple ones. To give some examples:

• evaluating {sqrt 9} would return two results, 3 and -3
• {+ 3 {sqrt 9}} returns 6 and 0
• {+ {sqrt 1} {sqrt 9}} returns four results: 4, 2, -2, and -4

Since the revised language deals with multiple values, it will be called “Muwae”. Marketing is already working on finding a way to use “Ha” as a version indicator, so version 2.0 can come out as “Muwae Ha.Ha”.

The WAE language is itself quite simple, so this work is not going to take long. You will do this in two steps: add a plain sqrt expression to the language, and then extend it so it can deal with multiple values so the sqrt can be made into the proper one.

Begin by downloading the WAE implementation to serve as the basis of your work. As a first step, replace all of the WAEs in the file with MUWAE.

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.

Adding sqrt to the Language

The first step is to add a simple sqrt to the language. This is a quick job of adding a few one-liners in the right places:

1. a new rule for a unary sqrt in the BNF definition.
2. a new variant to the AST type definition: Sqrt.
3. a line to parse these expressions.
4. a line to the formal definition of subst for these expressions.
5. the corresponding case in the subst implementation.
6. a line in the formal definition of eval. (Note that you should use sqrt on the right-hand side as our own simple square-root function.)
7. the corresponding case in the eval definition.
8. Finally, some tests for the new functionality.

Now, if you follow these and do all of these simple changes, you’ll have code that should work, but you might see a type error like:

The thing is that Racket has complex numbers as part of its numeric type hierarchy, which means that it can handle square roots of negative numbers just fine. But the Number in our language is actually the type that is known in proper Typed Racket as Real. This difference makes #lang pl simpler in many places (for example, you can compare two values of type Number with <, whereas in Typed Racket you can’t because it includes complex numbers too).

In addition to that, sqrt in our language is identical to the one in Racket (and in Typed Racket), but its type is restricted so it only takes in non-negative numbers, and returns such numbers (and therefore there are never complex numbers that you can get from it). Because of this, you will need to make the type checker happy by checking that the value that you pass into sqrt is indeed non-negative, and throwing an error if it is negative. The type checker is smart enough to know that since you checked that the input is not negative, then the result must be a plain real number (note: do not use eval twice). To make things nice and tidy, make sure that you update the formal definition of eval with a similar condition.

To help with all of this, here are some tests that you can use:

(Note that the last test specifies the error messages that you should use in case of a negative input to sqrt.)

Multiple Values

Now comes the interesting part of the homework: we’re going to extend the language so that instead of plain numeric values we actually deal with multiple values. As a representation for this, we replace the Number in the output of eval (and run) with (Listof Number). The easy way to do this is to change the types, then run the code to see which type errors you get: each one is an indication of code that should change to either wrap a result number in a list or pull out a number from a list. In the latter case, just use first for now, to get the code into working shape as soon as possible. When you have no more type errors, you will still have the tests to modify: they should also expect to get a list of numbers instead of just the numbers.

Now that the code works again and passes all tests, you have a version of the interpreter that has the semantic change, but not much has changed since it always assumes a single number in those lists. “Fixing” this will get us the actual language that we want to have. If you followed the instructions above, then you now have first conveniently appearing in all places that need to change.

Fixing sqrt

We will begin with sqrt. First of all, this is the only case where instead of returning a list with a single number, you need to return a list of the two results. Once you do that, some of the tests will fail, and you’ll need to fix them too as your evaluator gets closer to what it should do. For example, here’s the first test from the above, revised for this stage:

An issue that you’ll run into here is what to do with (sqrt 0) — should it return a single 0 or two of them (the other being the result of (- 0))? For this homework, we’ll go with the simple and uniform treatment, and end up with two of them:

We now have sqrt produce two outputs as it should, but it still grabs only the first number in its input. To fix this, we need to loop over all of the numbers in the input, and return a result list holding the two roots of each of these inputs. Do this by moving the code into a utility function which you should call sqrt+. The code in eval should now look like:

To help you, here is a skeleton of sqrt+:

The first two “holes” are simple, the last one involves sqrt, two conss, and a recursive call. (We won’t worry about tail-recursive calls here.)

Fixing the Arithmetic Operators

Next, we need to fix the arithmetic operators. This is a bit tricky, since each of them receives two inputs that are both lists, and they should apply the operator on each pair from these two inputs, and collect a list of all of the results. So to make it easy, here is again a skeleton of a utility function that will do this work. This time it is near-complete, and you have a tiny hole to fill:

Here are some tests that should work once you’re done with this part:

Note that these tests are not too great: they test that the result is a list of values in a specific order, and the order can change if we modify our implementation. It would therefore be better to consider these lists as unordered sets, and test that the result is set-equal to some list. But we will just ignore this detail for now, to keep things simple.

Fixing With

The last first that requires fixing is the one used in the evaluation of With. The problem there is that we’re still using the hack of wrapping the numeric result of eval in a Num so we can use it with subst, and Num expects a single number.

One way to resolve this would be to add a new variant called Nums to our AST definition. But this would require reworking new cases for it in a few places… So instead, we will choose an easier solution: just change the existing Num so instead of holding a single Number it will hold a (Listof Number). Once you do that, you will have three easy fixes to do. First, the code that parses numbers should put a list with the number in the Num. Next, there are two small fixes left in the eval function, and everything will work fine with it.

(Note that the BNF should not change, which is evidence that this is still a hack: the multiple-values feature which is a semantic change, has leaked into the AST definition which is supposed to represent the syntax.)

Don’t forget to add tests that demonstrate that this works: that using with to bind a name to a multi-valued expression works as expected. (You need to do this test even though you should already have complete coverage at this point.)

Finally

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