Assignment #3: Algae

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

This homework will require substantial work: make sure you start early.
This is not an introductory homework — leaving things for the last evening is not going to be a good idea. Consider yourself warned. Even if you don't have a partner, you should start working on your own, and later combine forces with your assigned partner.

Use

This homework will guide your work in a few stages — do them in the order that they're mentioned, and make sure that after each step you have working code. If you can't make it through the whole assignment, submit whatever you did cover, and mention this in clear comments. It is a good idea to submit working code after you finish each part if possible (with a comment specifying what parts you have finished).

To make things easier, the homework is split into two parts, the next homework will continue this one.
The second part is going to be for the master students only.

In this homework you will extend the WAE language, turning it from a course toy to an industrial strength programming language. Well ... maybe not, but you'll create a more useful language. The extensions will be substantial: you will add new operators and forms to the language, add new types, and make it possible to define and call functions. You'll even make it into a higher-order language eventually.

Since the extended language will be quite far from WAE, we need a new name. At its core, it will still be similar to WAE, but it will be powerful enough to write general algorithms, so we will call it “Algorithmic AE”, or Algae. (Yes, it's an extension of WAE, but “Algwae” sounds like you have some kind of a speech impediment.) Additional marketing issues like Professional Edition shrink-wrapped boxes, the right paper type for printing the manuals on, a good number of buzzwords (“The Leading Industry-Standard Framework for Rapid Application Development in Semantic and Independent Agent-Based Software”) and a good looking graphic design for the Quick Installation Guide will not be covered in this homework. Feel free to do that if you really want to.

We begin by extending the language in a few relatively simple ways. Some of this work has been done for you — begin by downloading algae.scm and use it as a starting point for your work. This interpreter is the same as the WAE implementation, with the following modifications. (Make sure you go over and understand the code, since you will need to fix and extend it.)

• “WAE” has been changed to “ALGAE”;
• The BNF has been changed to allow any number of arguments for + and *, and one or more arguments for - and /;
• The type definition has been updated to correspond to the new BNF;
• parse-sexpr has been updated to correspond to the new type;
• The substitution specs and the subst function have been updated too (make sure you understand how the helpers are used);
• The formal specs for eval have been updated to specify the same semantics as the Scheme operations, as well as using an evalN function that enforces evaluation of a number (this will become relevant later on);
• eval has been fixed to work as usual for cases of two arguments;
• The output type of eval (and run) is (U Number), which is really the same as Number, but you will be extending it and adding more output types;
• eval-number is added, which is just like eval except that it verifies that the result is a number and throws an error if not (for now, it is impossible for it to throw an error since eval always returns a number) — again, this is done to make it easy to add more types to the language later;
• Finally, and for the same reason as the above two items, the with case is not using Num to wrap the evaluation result — it uses value->algae instead, which converts any possible output of eval back into an ALGAE value. (And this is also a trivial function for now.)

As is, the algae.scm file that you begin with is not fully covered by tests. Fix this by adding sufficient tests, including testing error messages. (Reminder: you need to use the (test ... =error> "some-error-text") form for these tests.) You will see some errors that cannot be covered until you add more types to the evaluator.

Throughout the rest of this work, it will be a good idea to keep your tests updated — change them when the program's behavior changes, and add new tests when you add new parts. This will make your work much easier.

Note that arithmetic operators are parsed in a way that allow a variable number of arguments, similar to Scheme, and substitution (implementation and specs) are specified accordingly. Also, the formal eval specs specify Scheme-like behavior. The only piece that is missing, is the evaluation implementation for them.

Fix eval so that the arithmetic operators behave just like they do in Scheme. (Hint: map and foldl are your friends.) Make sure that you cover all corner cases (no arguments for addition/multiplication, one argument for subtraction/division, etc). Cover such corner cases in your tests too.

You also need to make sure that your evaluator is robust: it must not crash with an unexpected error. As things currently stand, it does not behave as it should when user code attempts a division by zero. You need to check such a case explicitly and throw an error yourself. (Note that the (test ... =error> "...") can only test your own errors, not Scheme errors.)

The next feature that you will add to Algae is a conditional form. Again, the first step is to find a good name for the form. Superfluous buzzwords are always a great idea — combining random ones that don't really mean anything but sound smart is a sure way to impress friends and relatives. So, how about “Interactive Falsification”? It doesn't mean anything, but it sounds very sophisticated. (Imagine the satisfaction you will feel on your next lunch with The Boss when you say “yeah, implementing an interactive falsification primitive form was tricky, but the expressiveness of the language went up an order of magnitude”.)
As a bonus, has a good acronym: if.

But first, you need to add boolean operators to the language — which, as you will see, also requires adding booleans as a possible evaluation result. Again, work in stages:

• Extend the Algae BNF to have <, =, and <= forms.
• Add new variants to the ALGAE type definition for these boolean operators: Less, Equal, LessEq, respectively. Each of these should have exactly two sub-expressions (unlike Scheme).
• Extend parse-sexpr to produce these for forms that begin with <, =, <= respectively.
• This will force you to update other parts of code (subst and eval) — do so and don't forget to take update the formal specs for both functions.
• That last change means that eval can now return a boolean value too — change its type to reflect this (add boolean to the union type).
• The next thing you'll note is that value->algae needs to be able to handle all values that eval can spit out, so it needs to be updated too — as noted above, this requires adding a new variant of ALGAE: make it Bool which has a single Scheme boolean value (using the boolean? predicate).
• Again, extend parse-sexpr — when it is getting an input that is the symbol True or False (note the capitalization), it should produce the corresponding Bool instance.
• You shouldn't be surprised now to see that you need to change subst and eval to account for the new variant. Extend the formal specs too — add a `B' is a boolean before the formal specs (note: this is not <boolean> since we have no concrete syntax as in Scheme).
• Add an eval-boolean too, which is similar to eval-number but verifies a boolean result.
• Now you have enough functionality in place: add an if form to the syntax and parser (it should always have three sub-expressions), and an If variant to the ALGAE type, and everything that is needed to make it work (including the formal rules). The behavior of ALGAE's if should not be as in Scheme — it should require a boolean result for the condition (use eval-boolean). (But note that evaluation of the branches can return any value, so you should use eval directly.)

We want to further extend Algae's use of booleans, by providing a not operator, and two special forms for and and or. But our language is powerful enough, so we can do so without modifying the core evaluator. Instead, we can change the parser (parse-sexpr) so that whenever it encounters one of these it will parse it into core Algae syntax that does the job of the boolean operator.

• First of all, begin by extending the BNF with unary not operator syntax, and binary versions of and and or. (You do not need to deal with any number of arguments for now.)
• Note that you should not extend the type definition — the actual syntax that is used by the core is not modified (since the core evaluator is not modified). But you should modify the parser, however, pretending that you have the required syntax constructors. For example, for not, you will need to add a line like:

  [(list 'not arg) (Not arg)]

  to the operator-parsing code, and two more lines for and and or.
• To make things work, you need the fake bindings for Not, And, Or, which translate to actual syntax. The idea is simple: simply create the code that implements the required operator. For example, Not is implemented as follows:

  (: Not : (ALGAE -> ALGAE)) (define (Not expr) (If expr (Bool #f) (Bool #t)))

  (You need to fill in the contract and purpose statement.)
  Do the same for the other two. Make sure that the semantics is short-circuiting unnecessary computations, that is, if the first expression in an And evaluates to false, then the second one should not be computed.
  Note that unlike Scheme, Algae has strict booleans (that is, it does not treat any non-false value as true, like Scheme). This will make it easy to implement these translation.
• Remember that you should not change the evaluator for this part.
• You should, however, update the formal spec for evaluation in a way that reflects your translation. For example, the evaluation rule for not is:

  eval({not E}) = eval({if E False True})

  (Note: As we will see, Scheme is actually doing something very similar.)

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