# Homework #3: Basic Interpreter ExtensionOut: Sunday, January 27th, Due: Friday, February 1st, 11:00pm

This homework is for working and submitting in pairs. 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 student as well. If you don’t know a student that you can work with, then please mail me too, and I will assign you semi-randomly. (But note that this will take a few days.) Note that master students will do additional homeworks, so if you are one, please find a master student for a partner (and again, email me if you want one assigned to you).
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 two works with your new partner.

The language for this homework is:

 `#lang pl 03`

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 also a kind of an introduction, although not as basic as the previous homeworks.

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 the version 2.0 will 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 language 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 written using run — this is the public interface for your language, and therefore it is the only thing that you should test.

## 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 instead you’ll probably see a type error like:

 `Type Checker: Expected Real, but got Complex`
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 in our language Number is actually the type that is known in proper Typed Racket as Real — this usually simplifies things, for example, you can always compare two values of type Number, whereas in Typed Racket you can’t because it includes complex numbers too.

To make a long story short, you can resolve that by checking the result of evaluating sqrt’s argument, throw an error if it is negative, and otherwise proceed as usual. 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. 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:

 ```(test (run "{sqrt 9}") => 3) (test (run "{sqrt 1}") => 1) (test (run "{sqrt 0}") => 0) (test (run "{sqrt -1}") =error> "`sqrt' requires a non-negative input")```
(Note that the last test specifies the error messags 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:

 `(test (run "{sqrt 9}") => '(3 -3))`
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:
 `(test (run "{sqrt 0}") => '(0 0))`

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:

 `[(Sqrt e) (sqrt+ (eval e))]`
 ```(: sqrt+ : (Listof Number) -> (Listof Number)) ;; a version of `sqrt' that takes a list of numbers, and return a list ;; with twice the elements, holding the two roots of each of the inputs; ;; throws an error if any input is negative. (define (sqrt+ ns) (cond [(null? ns) —«fill-in»—] [(< (first ns) 0) —«fill-in»—] [else —«fill-in»—]))```
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:

 ```(: bin-op : (Number Number -> Number) (Listof Number) (Listof Number) -> (Listof Number)) ;; applies a binary numeric function on all combinations of numbers from ;; the two input lists, and return the list of all of the results (define (bin-op op ls rs) (: helper : Number (Listof Number) -> (Listof Number)) (define (helper l rs) (: f : Number -> Number) —«fill-in»— (map f rs)) (if (null? ls) null (append (helper (first ls) rs) (bin-op op (rest ls) rs))))```

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

 ```(test (run "{+ {sqrt 1} 3}") => '(4 2)) (test (run "{+ {/ {+ {sqrt 1} 3} 2} {sqrt 100}}") => '(12 -8 11 -9)) (test (run "{sqrt {+ 16 {* {+ 1 {sqrt 1}} {/ 9 2}}}}") => '(5 -5 4 -4))```
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 the 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, the are two small fixes left in the eval function, and everything will work fine with it.

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.