Homework #7: Brang Strikes Back
Out: Friday, February 15th, Due: Sunday, March 3rd, 11:00pm


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 homework is a continuation of the BRANG homework. Begin with the posted solution as the initial point for your work. The homework is intended to be relatively quick — but it is more open-ended than usual.

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

The language for this homework is: 

#lang pl 07


Discussing the Previous Extension

In the last homework, we made it possible to define functions with more than one argument, and call functions with more than one argument. This is done by a preprocessor that essentially translates the code to the corresponding curried version. However, the resulting language is not completely identical to a language with properly implemented multi-argument functions. Demonstrate this using tests that expose the differences. There are at least three distinct differences: show at least two of them. (Note: the two should be distinct — not just the same kind of difference applied to different functions and numbers.)

Add the new tests at the end of the code.


Extending Binders

We’re still limited to our single-identifier binding construct, with. Extend the language with two new forms: bind and bind*. The new forms’ syntax and semantics should be similar to Racket’s let and let*. Sample code that uses them: 

{bind {{x 1} {y 2}} {+ x y}}
{bind* {{x 1} {x {+ x 1}} {x {* x 2}}} x}
To make things a little simpler, make the grammar require at least one binder in each of these. Also, since the two forms have exactly the same syntax, you can use a single new parsing bit for both, use an or pattern for this.

This task is up to you now. It should be similar in nature to work that you did in the previous homework. The changes should all happen at the input syntax and translated to the same CORE language. That is, there should not be any changes to the core evaluator.

When you write tests, make sure that the tests demonstrate and verify that the two forms bind correctly, and different from each other.


Extending Function Arguments II

Even with the multiple-arguments extension, we still cannot have functions with no arguments at all. It is easy to get these with a manual translation: all you need to do is ‘invent’ an identifier and use it for a one-dummy-argument function. For applications, you need to just plug in some dummy value. But this leads to two problems:

  1. There is a possible problem with plugging in some random value for no-argument function applications: what happens if we call a unary function with no arguments? However, things would be fine if we only write no-argument function calls to no-argument functions, so the only danger that is left is in masking out what should have been an error.
  2. There is yet another problem, which is possibly more severe. What if, for example, we decide to name the dummy argument that we add to nullary functions dummy? We may encounter an actual binding for that same name, so we should avoid shadowing user names at all costs.

Begin your work on this part by writing two tests that demonstrate these two problems. Be very careful when you write the test for the first problem: it should demonstrate getting such a dummy value without testing the actual value — in other words, the test should be successful regardless of the dummy value that you choose. The test for the second problem is easier, just show an expression that would fail to evaluate properly if we always use dummy for the dummy identifier name. The goal is to make out translation avoid that failure so this test passe.

Finally, make the changes to make it work. Reminder: the first problem that was demonstrated in the two tests is expected — so you shouldn’t try to find a way to make the evaluator throw an error when a unary function is applied on no arguments. The goal is to avoid changing the core interpreter. As for the problem of choosing a dummy name: we can easily solve that and choose a “name” that can never be confused with user code. The thing is that we use de-extend to keep track of names as we translate them to de-Bruijn index numbers — so all we need is to use this with a name that can never occur in user input. That’s easy to achieve if we extend our DE-ENV mapping functions so in addition to symbols, they can map one more value, like #f — then, this value can be used to extend the mapping that represents the shape of the current lexical environment, without using an actual name to do so — meaning that we get out desired effect with no possible name capture.