Administrative

This homework is for pair submissions, which is going to be the default until the end of the semester. If you want to change pairs for some reason, email us.

This homework will require substantial work: 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…

Please remember the Academic Integrity page — specifically, you should not share code in any public way when you work with your partner. (Please also avoid code snip sites, since often even unlisted snips can end up public.)

The language for this homework is:

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

Introduction

In this homework you will extend the WAE language, turning it from an academic 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 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.

The second part of this homework is going to be a continuation of this work — a solution file will be provided as a basis for doing it. This means that the solution will be given shortly after the deadline, and no late submissions will be accepted from that point on.

Preliminaries

We begin by extending the language in a few relatively simple ways. Some of this work has been done for you — begin by downloading the Algae skeleton 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 / (note that we use ... in a BNF to mean “the previous thing, repeated 0 or more times”);

• 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 Racket 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 to have 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 otherwise (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.)

Part 0: Complete Coverage

As is, the Algae skeleton file that you begin with is not fully covered by tests. Fix this by adding sufficient tests, including testing error messages. (Reminder: 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, ignore them for now.

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.

Part 1: Fixing Arithmetics

Note that arithmetic operators are parsed in a way that allow a variable number of arguments, similar to Racket, and substitution (implementation and specs) are specified accordingly. Also, the formal eval specs specify Racket-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 Racket. 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. Hint: map and foldl are your friends. Another hint: don’t try to solve subtraction/division with a single foldl, instead, consider the needed computations for them: a subtraction expression is implemented via a subtraction and a sum-of-list, and similarly for divisions.

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 Racket errors, and it is enough to have some part of the error rather than all of it.)

Part 2: Adding Booleans and Conditionals

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 relational 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 relational operators: Less, Equal, LessEq, respectively. Unlike Racket, each of these should have exactly two sub-expressions.

• 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 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 Racket boolean value (using the Boolean type). Note that at this stage, this is a hack: we’re extending the AST only because we want to use it to carry another type of runtime value.

• Extend the BNF again with two new keywords that can be used as expressions: True and False (note the capitalization). Then, extend your parse-sexpr accordingly — when it is getting an input that is the symbol True or False, it should produce the corresponding Bool instance. This is a nice way to hide the hack: make it into a feature… Note that we do not use something like <boolean> (or anything else) for a syntax for literal boolean values — only new expressions that evaluate to them. This aspect of our language makes it more like conventional ones where some true/false keyword evaluates to boolean values, rather than the literal non-identifier syntax you find in Racket and in other lisp dialects.

• 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 True/False before the formal specs (again, don’t use <boolean> since we’re not using the Racket syntax for booleans).

• 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 Racket — 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 for the result expression.)

When you’re done, add enough tests to get complete coverage. You should do that by testing only uses of run, not any helpers (it is possible to do that). You should now have a working milestone — to be safe, you can submit your code. (You’d need to add bogus function bindings for some names that the server will require: Not, And, and Or.)

Part 3: Further Extensions

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. (Note that this isn’t really the actual line that you’ll add: something is missing there, the types will make you see what’s missing.)

• To make things work, you need the fake bindings for Not, And, Or, which translate to actual syntax. The idea is simple: just create the code that implements the required operator by generating code. For example, Not is implemented as follows:

  (define (Not expr)
    (If expr (Bool #f) (Bool #t)))

  (You need to fill in the contract and purpose statement.)

• Do the same for And and Or. 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 Racket, Algae has strict booleans (that is, it does not treat any non-false value as true, like Racket). This will make it easy to implement these translation. In other words, the syntax translation code is unrelated to types (since it’s only syntax at that point), but you write the code assuming that its arguments are going to evaluate to boolean values. See below for further clarification on the resulting functionality.

• 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, Racket is actually doing something very similar.)

Clarification on the behavior of and and or

It’s obvious that And is unrelated to types of values because it deals with syntax rather than values — and as such, it cannot tell what kind of values will be used during evaluation. But in this homework context, “assuming that its arguments are going to evaluate to boolean values” means that your And and Or should not generate code that ensures that all of the inputs are proper boolean values. Some values will be tested simply because the resulting code uses if (which will check its condition), so {and 123 True} will fail. On the other hand, {and True 123} should not fail, and simply result in 123.

However, when used in an if condition, {if {and True 123} ...} would fail in the same way that {if 123 ...} will — but here it’s the if evaluation that results in an error.

The bottom line is that your code should be simple, and if an expression like {and True 123} throws an error (by itself, not in an if), then the code could be simpler. Some examples to summarize all of this:

• {and 1 True} would lead to a runtime error when evaluated,
• {and True 1} wouldn’t,
• {if {and True 1} 2 3} would.

Finally

Define minutes-spent as the number of minutes you spent on your homework. (General note: this is needed for all homework, so in the future just remember to add it without being explicitly told to do so…)