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:
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.
The tests that you’re looking for should be tests that are unfortunately successful: they should pass, and in doing so, they demonstrate a bad feature of the language. For example, it might be that in our language adding 2 and 3 results in 7 — clearly something that is undesirable. You’d demonstrate this with a test like
Note that the tests should pass, and therefore you should not try to fix the brokenness that it demonstrates. (Doing this for the problems that we’re talking about would be too much anyway, since we’re talking about a problem with the fundamental approach to how we implement multiple arguments.)
We’re still limited to our single-identifier binding construct,
Extend the language with two new forms:
bind*. The new
forms’ syntax and semantics should be similar to Racket’s
let* (but no need to check duplicate names since we’ll be translating
preprocess). Sample code that uses them:
To make things a little simpler, make the grammar require at least one
binding 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
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. (Note that it’ll be
easy to make
Bind* hold a list of names and a list of named
expressions — don’t try to make a list of lists, since that will be more
When you write tests, make sure that the tests demonstrate and verify that the two forms bind correctly, and different from each other.
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:
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.
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
dummy? We may encounter an actual binding for
that same name, so we should avoid shadowing user names at all
Begin your work on this part by writing two tests that demonstrate these
two problems. (Add them after the tests from the first part.) 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
dummy for the dummy identifier name. The goal is to make
our translation avoid that failure so this test passes.
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.