Administrative

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:

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.

Clarification:

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

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

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 three problems:

1. 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?

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

3. 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:

• Begin with writing three tests that demonstrate the problem of implementing nullary functions and function calls. These tests cannot run at this point since the functionality is not implemented.
• Continue with the implementation.
• When that’s done, the first two tests that demonstrated no-error should pass (so this problem does exist).
• And the test that shows that your solution does not mess up evaluating code with 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.