Assignment #5: Brang

This assignment is for the same pairs. Email if you want to change.

This homework is, again, split into two parts — and the next homework will be based on it.

The language for this homework is:

In class (Lecture #7), we saw how de-Bruijn indexes can be used as an alternative for identifier names. In this homework, you will use this representation for a modified Flang interpreter. You will do this by a program transformer: a procedure that will pre-process the input program and generate a version of this input that uses de-Bruijn indexes for all identifier references. There is also a twist: the program processor will use functional environment-like values for its work.

Begin your work with the Flang interpreter that uses environments.

First of all, rename the language to avoid possible confusion. Since this is going to be a Flang variation that uses de-Bruijn indexes, we name this interpreter “Brang”. Edit the file accordingly.

The transformation from source to de-Bruijn indexes that we will implement is a kind of compilation: it is a translation from one language (Brang) to a different language, which in this case is quite similar except for identifier references. So the first thing we need is a new type of syntax for the transformed code: BRANG*. Create this syntax as a copy of BRANG, except that all of its variant names end with a *. Having a second type for preprocessed code means that the parts of the code that deal with the input syntax stay the same. Specifically, you will not need to modify parse-sexpr for this assignment.

To complete the new type definition, you need to modify it to fit its purpose. There are several things to change: first, instead of Id*, it should have a Ref*, and second, since this syntax is used with de-Bruijn indexes, it should have no place for any identifies (for example, Fun* is going to be a one-argument constructor).

The preprocessed programs that we will be running will have no identifiers, as they will all be translated into de-Bruijn references. You can therefore remove the code that deals with run-time environments: the ENV type definition, and the lookup function.

You still need some definition for an ENV type because closures still hold environments, but the only thing we need in an environment is a list of values — when we encounter a reference, it will tell us what position in this list is needed. Define ENV as the appropriate type.

Before we change eval, it is worthwhile to go over our evaluation rules, which can guide us through changing eval. There are two changes that are required:

• First, we do not have identifiers, and we do not use lookup. Instead, when we encounter a Ref syntax, we use it as an index to pull out a value from the environment, which is now a simple list of values. In other words, we now have this rule:

  eval(Ref(0),cons(v,rest)) = v eval(Ref(n),cons(v,rest)) = eval(Ref(N-1),rest) if n>0

  or a more convenient rule:

  eval(Ref(N),env) = list-ref(env,N)

  (Note that Ref is used in these specs instead of some concrete syntax, since we have no concrete syntax for references.)
• The second change is in the way environments are extended. Previously, we used extend in the formal rules, which was a function of three arguments. Replace this with something appropriate.

You can now reflect these changes in the eval code. First, change all BRANG variant names to the BRANG* variants (in types too). Note that there is no Id* — you have to use Ref* instead.

Next, adjust the rest of the eval code as you did with the formal rules: specifically, you will need to replace Extend according to the new ENV type. The new eval code should be a little simpler than the original. There will be a few other parts of the code that will need to be updated.

The basic idea of the preprocessor is that we need to scan the input program, and convert all identifier occurrences into Ref* AST values. This would be a mostly-routine function that translates BRANG values to BRANG* values. But there is one important thing we need for this scan: when we encounter an identifier, we need to know the ‘shape’ of the current scope — a mapping from identifiers to their de-Bruijn indexes. In other words, a kind of a compile-time environment.

You need to implement this new environment type — and the twist is that you should use functional values for this. These environments map identifiers to integers, so we get this type definition (call it DE-ENV):

• de-empty-env is a vacuous mapping — it always throws an error.
• For any symbol x and DE-ENV e, (de-extend e x) should map x to 0.
• For any symbol x and DE-ENV e, if e maps x to n, then (de-extend e y) should map x to n+1.

For example, if we have this definition:

Using the above, implementing the preprocessor should be easy. As said above, it is a simple recursive scan of its input that translates a given BRANG value (and a DE-ENV mapping) to the corresponding BRANG* value. The only interesting cases are ones that deal with scope: the two cases where a new scope is introduced, and dealing with identifiers.

Finally, you need to connect the preprocessor and the evaluator in run: it should now use preprocess over the parsed input (and an empty static environment), and the result is sent to eval with an empty run-time environment (which is now just an empty list).

Again, remember to thoroughly test your code, the server will require complete code coverage.