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.

This work is yet another extension of the basic Brang language (note: an extension of the first Brang language). You will add a recursive binder form. Begin your work with the posted solution to the BRANG homework (the first one).

The language for this homework is:

Recursive Binder

In this short homework you will implement a recursive rec binder using the Y combinator. The way that this will be implemented is similar to the previous part: using a preprocessor. We will change the syntax that Brang programmers see, but the core language will stay the same — specifically, we will extend the preprocessor so rec forms are transformed to CORE for the core to evaluate as usual. The translation will use the Y combinator that we have talked about in class; implementing it through a translation will allow you to implement recursion while keeping your users blissfully ignorant of the whole Y headache.

As usual, make sure you clearly comment places in the original version (the previous solution) that are modified.

Begin by adding a rec form to the concrete syntax, to the corresponding datatype definition (WRec, for “with-rec”, and so it doesn’t clash with the TR Rec type), and extend parse-sexpr to generate this forms. This rec form should be similar to with, binding a single identifier. Its syntax is:

However, as we have discussed in class, we want to deal only with function expressions, so make sure that the named expression in rec forms is always a fun expression and throw an error if it isn’t. For example, a test like this should succeed:

(Hint: use the cases pattern matching on the BRANG type to test whether you have an instance of the Fun variant.)

Note that the the evaluator does not need to be extended: its input is CORE, which is unchanged — the Brang WRec construct gets translated to the CORE, which is not modified. The evaluation rules should, however, be extended to indicate the new rewrite rule as described below, something like eval(SOME-EXPR) = eval(REWRITTEN-EXPR). Yes, earlier evaluation rules were written only for CORE, so this is a bit different. Had we done the same for with, it might have looked like:

Preprocessing WRecs

The next step is to extend the preprocess function to “compile away” instances of WRec. All you need to do for this is to add a WRec case.

The WRec transformation should roughly look like this:

Remember to update the evaluation rules accordingly.

In this template, Y is not an identifier — it’s a meta-variable that should be replaced by the actual definition of the Y combinator, so we don’t interfere with user bindings. See the code in the lecture notes, and remember the required protection from infinite looping. Since this value is a constant BRANG expression, it is better to generate it once, as a global constant. You should make your life even simpler by using parse with a piece of Brang code in a string, instead of using the AST constructors, e.g:

Finally, note that this will get you a BRANG value for Y, so you will need to construct a BRANG expression using it and feed the result back to the preprocessor. You could try to define the global constant as an already preprocessed CORE value, but this will require more effort and will result in more verbose (and therefore error-prone) code.

The translation case in preprocess is quite simple, given the definition described above. Don’t forget that all code must be transformed recursively — including nested occurrences of rec.

Conditionals

Having a recursive binder in the language is fine, but to really use it, you need a way to test things, so you can write loops. To do this the easy way, add an if0 form to the language. This will be a new if-like form with three subexpressions; the intention is to test whether the first sub-expression evaluates to 0, and based on that evaluate either the second (if it did) or third (if it didn’t) subexpressions. This means that if0 treats 0 as a true value, and anything else (including non-numeric (non-NumVs) values) as false.

This new form will have to go all the way into the evaluation function. (Can you see why?) You will need to add it to the BNF, to both the BRANG and CORE type definitions (use If0 and CIf0), to the parser, to the evaluation rules, and to the eval function.

Testing

Finally, test your new interpreter, for example, try this:

and other examples. Following the execution of such expressions will be enlightening.

Note that your preprocessor should not capture Y. For example, the following two tests should succeed: