Administrative

This homework 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 serve 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 — since you are expected to know the material.

The homework is for the same pairs by default. Email me if you have any problems or issues.

The language for this homework is:

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

Introduction

Apparently, Algae has succeeded. It gained some considerable momentum and is going commercial. In this homework, you will help by finishing the implementation. You will add function definitions, which will turn Algae to a usable language. Begin your work with the solution for the previous homework, do not use your own solution (if you really want to, and you have good reasons to do so, ask).

Part 3b: Further Extensions

Your users are unhappy about your binary-only and and or forms: they say that they want the same convenience they get with the variable-arity arithmetic operators. Make them happy by extending and and or to handle any number of sub-expressions. The semantics of this extension should still be short circuiting, and in general they should be extended exactly as they are in Racket, including the case of zero and one subexpressions!

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

The new translators are easy — you will need to have two special cases, one for no expressions and one for a single expression, and a third general case that does the recursive call. (Note: you do need three cases here.)

If you do this right, the two forms will still require booleans for all subforms except the last one (since they’re still implemented via a translation to If), and the last one can evaluate to any value. The code should be simple.

Part 4: Moving to Programs

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 that shows how it is going to be extended (look for “Collatz” if you want to know what this code does):

So the syntax of programs is now:

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:

And the same holds for the parser: instead of a single parse-sexpr function, you should now have the following definitions:

Filling in the code is simple: parse-program should use parse-fun (hint: use map); parse-fun checks for a proper fun syntax to construct a FUN instance using Fun; and finally, parse-expr is just like the previous parse-sexpr (make sure you modify the name in the recursive calls).

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 really want to update them (subst is easy to specify, but eval will be harder).

Syntax for calling functions

We’re not done with the syntax extensions: 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 for the variant name) 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, not with PROGRAM.)

Be careful: 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 later.)

Function lookup

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

You will need either a helper function that will search the function list, or you can use a lambda with the built-in ormap function (which is better). If the needed function name is not found, your code should raise an error. (For simplicity, you can assume that there are no duplicate function names.)

Evaluating programs

Now you need to handle the meaning of programs — the first step is to specify it. The meaning of a program is now not a numeric (or boolean) value, but rather a function. More specifically, 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.

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:

Note that there’s a change to eval: prog is passed to it as a new argument. This is needed because when eval encounters a function call, it will need the whole program to search for a function to use. Besides adding the prog argument, we don’t change eval: it still takes in a single ALGAE expression as its first argument — so how do we start evaluating the body of main with the given argument? Simple: we construct a Call expression that would have been the result of parsing the {call main arg} expression. This is the part that you need to fill in.

Now you need to change eval as discussed: it needs to take the whole program as an extra argument program. This affects not only the way that run uses eval, but also the many places in which eval 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:

Now, all recursive calls to eval and eval-? need to carry over the program argument. When you do that, you will notice that some of these calls are performed indirectly via map. This cannot be easily changed, since map will call its argument with a single element from the list. There are several ways to fix this. An obvious solution that we used in the past is to write a helper function like eval-list. But now that we have lambda we can solve things in a much better way. (Note that you will need to use lambda with argument types.) Change eval by wrapping its whole body with a let that rebinds eval and eval-? to single-argument functions:

With this, fixing the code will be extremely easy.

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 should be easy now: 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. In other words, this part should be similar to what we do in FLANG, except that we look-up a function instead of evaluating an expression. 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:

and then change your existing tests to use run*. You still need to add run tests, of course. (The program at the beginning of part 3 is a good test, but you should add more tests, of course.)

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

Part 5: Making the Language Higher Order

Note that the ALGAE language, as currently defined, is a first-order 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:

will always call the function called foo — the foo argument to main is a binding instance that binds the last foo occurrence, but it does not bind the first expression in the call form.

In this part, we will enhance ALGAE yet again — 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. We’ll use symbols for this too, but note that these are new kinds of ALGAE runtime values — not to be confused with symbols that are used to represent identifiers in our syntax. 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 name, and the sub-expression is expected to evaluate to a function name (a runtime symbol value).

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

• Since we’re going to extend the union type that is used for runtime values, it makes sense to abstract over it so there’s a single type definition that needs to be updated. Add a VAL type definition that simply defines it as the union: (define-type VAL = (U ...)) and then use VAL instead of all places that use that union.

• Add Symbol to the possible result of eval — this is now a simple update of the VAL type. Also, you’ll need to add an eval-symbol and a new case in value->algae.

• Add two new code fragments in eval to deal with Quote and VCall syntax values.

• If you did this right, you will also be able to use a function name as an argument to run.

And this is everything you need for this extension, and this homework. (Don’t forget to test the new extension, of course.)