Homework #4: Algae
Out: ? Tuesday, October 10th, Due: ? Monday, October 16th, 11:00pm

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…

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.

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.

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.

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

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

Finally

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