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 can work with, then please
send an email too, and you will assign you semi-randomly in a few days
(since the assignment is based on the grading of the first two
homework).

Note that 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).

We have a strong preference to pair people up, but if you have a good reason to work alone (or a strong preference for doing so), please specify that in the email.

Reminder: submission as a pair is done using `user1+user2`

as the login
and either one of the two passwords. (In other words, you don’t need to
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:

#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 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.

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 language implementation to serve
as the basis of your work. As a first step, replace all of the `WAE`

s
in the file with `MUWAE`

.

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.

`sqrt`

to the LanguageThe 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:

- a new rule for a unary
`sqrt`

in the BNF definition. - a new variant to the AST type definition:
`Sqrt`

. - a line to parse these expressions.
- a line to the formal definition of
`subst`

for these expressions. - the corresponding case in the
`subst`

implementation. - 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.) - the corresponding case in the
`eval`

definition. - 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:

Type Checker: type mismatch

expected: Nonnegative-Real

given: Number

expected: Nonnegative-Real

given: Number

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:

(test (run "{sqrt 9}") => 3)

(test (run "{sqrt 1}") => 1)

(test (run "{sqrt 0}") => 0)

(test (run "{sqrt -1}")

=error> "requires a non-negative input")

(test (run "{sqrt 1}") => 1)

(test (run "{sqrt 0}") => 0)

(test (run "{sqrt -1}")

=error> "requires a non-negative input")

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

.)

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.

`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))]

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

:

(: 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]))

;; 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
`cons`

s, and a recursive call. (We won’t worry about tail-recursive
calls here.)

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))))

(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))

=> '(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.

`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.)

Define `minutes-spent`

as the number of minutes you spent on your
homework.