Homework #8: Recurse of the Brang
Out: ? Tuesday, October 24th, Due: ? Monday, October 30th, 11:00pm

Administrative

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 previous homework.

The language for this homework is:

#lang pl 08

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:

{ rec { <id> <BRANG> } <BRANG> }

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:

(test (run "{rec {x x} x}") =error> "non-fun form in `rec'")

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

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:

{rec {id E1}
  E2}
-->
{with {id {call Y {fun {id} E1}}}
  E2}

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:

(define Y-combinator (parse "..."))

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:

(test (run "{rec {fact {fun {n}
                        {if0 n 1 {* n {call fact {- n 1}}}}}}
              {call fact 5}}")
      => 120)

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:

(test (run "{rec {Y {fun {n}
                      {if0 n 1 {* n {call Y {- n 1}}}}}}
              {call Y 5}}")
      => 120)
(test (run "{rec {fact {fun {Y}
                        {if0 Y 1 {* Y {call fact {- Y 1}}}}}}
              {call fact 5}}")
      => 120)