Homework #4: AlgaeOut:   Friday, October 9th, Due:   Thursday, October 15th, 11:00pm


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:

#lang pl 04

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.


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.

Warning: The deadline will not be flexible!

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.


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

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

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:

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.

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:


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