Assignment #4: Algae, part 2

This assignment is only required for Master students. Undergrads can do it too, and you will be graded as usual — but you will not be able to withdraw a graded homework grade, so submit only if you think that your work is good enough to improve your grade. (Note: the homework grades are all weighted to compute your overall grade, so adding another grade means that you get smaller portions for more grades, which can server as protection against local disasters.)
Note that while undergrads are not required to submit a solution, it will be a very good idea to read the homework and go through the solution when it is later posted.

The assignment is for pair submissions, which is going to be the default until the end of the semester (unless explicitly said otherwise). By default, you should work with the same pairs — email me if you want to change.

The language for this homework is:

Specifically, both the syntax and the semantics are different. Do not try to ‘borrow’ class code!

In this homework, you will finish the Algae implementation. You will add function definitions, which will make Algae a more usable language. Begin your work with the solution for the previous homework, do not use your own solution file (if you really want to, please ask).

Your boss has officially declared binary-only and and or forms as ‘un-fun’. Bring happiness back to the office by extending them to handle any number of sub-expressions. The semantics should still be short circuiting, and they should behave like they do in Scheme.

• Revise the BNF to reflect this,
• Change the parser to allow any number of sub-expressions
• Change the And and Or translators to consume a list of expressions as input.

New Syntax

We will begin by modifying the syntax of the language. It's easiest to go through an example first — here is a complete valid Algae program (look for ‘Collatz’ if you want to know about this program):

To reflect this new syntax, you will first modify the type definitions accordingly. We now have three non-terminals, so we define three types, one for each:

Finally, change parse to parse a whole program using parse-program. Make sure you declare the correct type for it.

Note: the formal specs for subst and eval will get more complicated if they will reflect the new evaluator, so you can get rid of them at this point. Unless, of course, you do want to update them (subst is easy to specify, but eval will be harder.).

Syntax for calling functions

We're not done with syntax additions: the function call syntax is still missing. A function call is specified as {call id expr} — add this new derivation to the ALGAE BNF, type definition (use Call) and to parse-expr. You will also need to add a case to the definition of subst that deals with function call expressions. (Note that subst is still dealing with ALGAE syntax only.)

Note that the function to call is just an identifier — not an arbitrary expression. This means that parsing a call form is not like parsing other operators. (We will have another construct to do that below.)

Function lookup

Clearly, your code will need to lookup function values (Fun instances) from a PROGRAM. Fill in the following code for this:

Evaluating programs

You now need to handle the meaning of programs — first, it needs to be specified. The meaning of a program is now not a numeric (or boolean) value, but rather a function. Actually, the meaning of a program can be taken as a collection of functions, and ‘running’ the program with an argument invokes the function called main as an entry point.

So first of all, to make things easy, we will change run to deal with running a program, and later deal with eval. run needs to take an extra argument (a number or a boolean) which is used with the program's main function definition. Change it so that it looks like the following, taking an extra argument:

Now, as we said, eval needs to take an extra argument that is the whole program. This affects not only the way that run uses eval, but also the many places in which it calls itself (or the eval-number and eval-boolean functions) recursively, as well as adding the argument to the eval-? functions. First of all, this is how the changed eval should look like:

Once you're done with all of this, you will be ready to add a case for dealing with function calls. This is the core part of this extension, but it is not too difficult: a function call is quite similar to what you do when you evaluate a with expression, except that the body and the binding name are part of the function definition which you can get by using lookup-fun. Note that lookup-fun should already take care of signaling an error if the function is not found.

Testing

Now that all the pieces are in place, you can go ahead and add sufficient tests. The problem is that your old tests are all broken now, because run is used differently now. An easy way to avoid rewriting all of your existing tests is to write the following definition:

Now would be another good time to submit a checkpoint version of your code.

Note that the ALGAE language, as currently defined, is a first-class language: you cannot pass around function values around, you cannot get a function value as an argument, and you cannot create new functions at run-time. As an indication of this, the following function definition:

In this part, we will enhance ALGAE one last time — we will turn it into a higher-order language. We will not, however, make it have first class functions. The resulting ALGAE language will be quite similar to C in the way functions are treated. This change will be easier than the previous one.

We will need to add two features to the language: first, a way to specify function names — this will be a new form and a new type that for this form to evaluate to (symbols will be convenient for this too). Note that we need a new form for this — because otherwise, occurrences of identifiers in ALGAE programs have the semantics of referencing some bound name. We also need a way to use these values for calling functions: vcall a form that is similar to call, but it has a function sub-expression rather than a function identifier, and the sub-expression is expected to evaluate to a function name (a symbol).

Here is an example of using this new feature for the same ‘Collatz’ program above:

Again, work in small steps:

• Add the new forms to the BNF: {quote id} to create function name values and {vcall expr expr} that will call the value of the first expr.
• Add the corresponding entries to the ALGAE type definition, use Quote and VCall as the new variant names. (Remember: VCall is similar to Call, but the fundamental difference is that it has expression in both places.)
• Extend parse-expr to parse the new forms. (Again, parsing a vcall form is different from parsing a call form.)
• Extend subst. (This is very easy.)
• Add symbol to the possible result of eval — this means updating contract lines in a few places, as well as adding eval-symbol and a new case in value->algae.
• Add two new code fragments to deal with Quote and VCall syntax values.