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, 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* (but no need to check duplicate names since we’ll be translating
these via 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 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. (Note that it’ll be
easy to make Bind and 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
complicated.)
When you write tests, make sure that the tests demonstrate and verify that the two forms bind correctly, and different from each other.
Note that you might get a type error about passing a sexpr to a
recursive parse-sexpr call via map. If you get that problem, you
should wrap the match pattern in a sexpr: to ensure that it gets the
right type. (Ideally this wouldn’t be needed, but it’s a problem that
Typed Racket has with type inference around higher-order functions.)
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 three problems:
There is a possible problem with implementing nullary functions as unary functions taking in a dummy-value: what happens if we call a unary function with no arguments?
The converse is also possible: calling a nullary function with one argument.
However, these two are 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
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 three tests that demonstrate these
three 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. (Again, the only thing it should test is
that we don’t get any error.) The test for the third 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
our translation avoid that failure so this test passes.
Finally, make the changes that implements this translation so nullary functions work. Reminder: the first two problems that were demonstrated in the three tests are expected — so you should not 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.
To reiterate:
dummy should also pass. Furthermore, it
shouldn’t pass because you used another name — it should pass no
matter what name is used in the test.