Assignment #5: Algae, part 2

Out: Tuesday, February 9th, Due: Thursday, February 18th, 9:00pm

Administrative

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 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 assignment 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 me.

The language for this homework is:

#lang pl 05

Warning: The language that you will be implementing in this homework is very different in nature than the FLANG language that we are discussing in class.

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

Introduction

In this homework, you will finish the Algae 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 should still be short circuiting, and in general they should behave exactly as they do in Scheme, 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 for no expressions and for a single expression, and the general case will use them recursively. (Note: you do need three cases here.)

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 extentded (look for ‘Collatz’ if you want to know what this code does):

{program {fun even? {n} {if {= 0 n} True {call odd? {- n 1}}}} {fun odd? {n} {if {= 0 n} False {call even? {- n 1}}}} {fun main {n} {if {= n 1} 1 {+ 1 {call main {if {call even? n} {/ n 2} {+ 1 {* n 3}}}}}}}}

So the syntax of programs is now:

<PROGRAM> ::= { program <FUN> ... } <FUN> ::= { fun <id> { <id> } <ALGAE> } <ALGAE> ::= Same as before

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:

(define-type PROGRAM [Funs (funs —«fill-in»—)]) (define-type FUN [Fun (name —«fill-in»—) (arg —«fill-in»—) (body —«fill-in»—)]) (define-type ALGAE Same as before)

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

(: parse-program : Sexpr -> PROGRAM) ;; parses a whole program s-expression into a PROGRAM (define (parse-program sexpr) —«fill-in»—) (: parse-fun : Sexpr -> FUN) ;; parses a function s-expression syntax to an instance of FUN (define (parse-fun sexpr) —«fill-in»—) (: parse-expr : Sexpr -> ALGAE) ;; parses an s-expression into an ALGAE abstract syntax tree (define (parse-expr sexpr) —«fill-in»—)

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:

(: lookup-fun : Symbol PROGRAM -> FUN) ;; looks up a FUN instance in a PROGRAM given its name (define (lookup-fun name prog) —«fill-in»—)

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:

(: run : —«fill-in»—) ;; evaluate a complete ALGAE program contained in a string, ;; given a value to pass on to the `main' function (define (run str arg) (let ([prog (parse str)]) (eval —«fill-in»— prog)))

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 actually need to use lambda:.) Change eval by wrapping its whole body with a let that rebinds eval and eval-? to single-argument functions:

(: eval : ALGAE PROGRAM -> (U Number Boolean)) ;; evaluates ALGAE expressions by reducing them to numbers or booleans ;; `prog' is provided for function lookup (define (eval expr prog) (let ([eval (lambda: ([e : ALGAE]) —«fill-in»—)] [eval-number —«fill-in»—] [eval-boolean —«fill-in»—]) —«fill-in»—))

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:

(: run* : String -> (U Number Boolean)) ;; a version for testing simple ALGAE expressions without function calls (define (run* str) (eval (parse-expr (string->sexpr str)) (Funs null)))

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:

{fun main {foo} {call foo foo}}

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:

{program {fun even? {n} {if {= 0 n} True {call odd? {- n 1}}}} {fun odd? {n} {if {= 0 n} False {call even? {- n 1}}}} {fun do_even {n} {/ n 2}} {fun do_odd {n} {+ 1 {* n 3}}} {fun main {n} {if {= n 1} 1 {+ 1 {call main {vcall {if {call even? n} {quote do_even} {quote do_odd}} n}}}}}}

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

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