Assignment #8: (Not for submission) Turbo Toy

Work and submission is with the same pairs. (As usual, let me know if you want to switch partners.)

You will need to have an updated course plugin which has a specific level for this assignment. Also, read carefully the recent lecture notes before you begin your work.

This assignment is not difficult — you will basically apply the changes that were discussed in class to the Toy language implementation, and then extend it with two new features. To begin your work, get the toy.scm file which should be used as the basis for your work. You will implement a recursive binder called bindrec, a special form for variable assignment, multiple body expressions, and functions that receive their arguments by reference. The next assignment will follow-up on this one.

The grade value of each part is indicated in the following sections. If you did not manage to do some parts, indicate so clearly at the top of your submission file.

As discussed in class, the first step toward implementing recursive environments is changing the implementation of environments so they hold boxes of values instead of plain values. Begin by changing the type — you need to change the frame? definition so instead of VAL? it uses (box-of VAL?), do this and fix the rest of the code so it works with the new implementation (including changing the global environment).

As we have seen, this is a pretty easy task, but to make it even easier, here's a summary of things you should do after the above change:

• Change extend: it still receives VALs, so it should wrap them in boxes when it creates the new frame.
• lookup's definition does not change, so it returns a different type now: fix its contract line to indicate this (it returns a box).
• The global-environment should also be fixed so it is initialized with boxes of values. (It will be cleaner to make scheme-func->prim-val create a box, instead of doing it yourself for each use.)
• Finally, the type of lookup changed, so you should change the single place that uses it accordingly (look in the box).

Completing this part is needed for the rest of the assignment, which will build up on it.

Now that we have an environment where names are associated with mutable boxes, we can use that to implement variable mutation. To implement this, you will extend the language with a new special form: set!. The syntax of this form is: {set! <id> <TOY>}. Add this to the BNF, to the TOY type definition — use Set for the name of the new variant, and to the parse code. To implement the semantics of the new form, add a Set case to the eval function which will use lookup to retrieve the box that holds the value of the named identifier, then evaluate the expression and use set-box! to store that in the box.

As discussed in class, when you implement the semantics of set!, you will have to decide what value to return as a result of evaluating these forms. The three choices that we have seen in class are:

• Return the new value, making it possible to ‘chain’ mutations, and use assignment expressions for their values, for example

  {set! x {set! y 0}}

  will set both x and y to zero, and

  {if {> {set! x {- x 1}} 0} ... ...}

  decrements x and then checks if it's bigger than zero.
• Return the old value, which makes it possible to do something with the value that is now overwritten, for example

  {set! x {set! y x}}

  will swap x and y, and

  {display {car {set! l {cdr l}}}}

  “pops” a value from l and prints it.
• Return some bogus value that cannot really be used for anything, which will make sure that expressions that have a mutation side-effect are not confused with other expressions.

In class, we have used a random number value for that, but that was a kludge. To do this properly, you need a new kind of value that is absolutely useless: add a new BogusV variant to the VAL type definition (it should not consume any inputs), and use that as the return value for evaluating Set syntaxes. As a minor optimization, define bogus as a BogusV value and use that instead of creating new bogosities every time one is needed.

Be sure to add some test cases to check that your modification works. This will be tricky at this point, since bind and fun bodies have just one expression. Hint: you can bind a name to an expression, and never use it. For example, in Scheme:

The next extension is bindrec: a recursive binder form, which will be implemented as shown in class. First, add it to the BNF, it looks just like bind:

The next step is to extend the parser: do not follow the bad cut-and-paste habits that were used in class, instead use the fact that parsing a bindrec is exactly the same as parsing a bind. The new code in parse-sexpr should look like this:

Now to the important part: the change to eval which should implement the semantics of the new form. To make sure that your implementation is correct, add this test case:

In general, there are various approaches that you can use to correctly implement extend-rec — the actual implementation is up to you. A few Scheme features that we have seen in class and can be useful for your code are:

• let* is a form that has the same syntax as let, but each new binding is in the scope of the previous one. For example:

  (let* ([a 2] [b (+ a 3)] [c (* a b)]) (+ b c))

  is valid, since it is just a short-hand form of

  (let ([a 2]) (let ([b (+ a 3)]) (let ([c (* a b)]) (+ b c))))

• for-each is a function that is similar to map, except that it does not construct a list of results. You should use it to iterate some side-effect over some list(s).

Given that our language has side-effects, it now makes sense to have multiple expressions in places where a ‘body’ expression is expected. There are three such places now: bind, bindrec, fun.

To implement this:

• Extend the BNF and the TOY type definition, then adjust the parse-sexpr function accordingly. Remember that a body of expressions requires at least one expression. (It is fine to use a single list-of in the type and make the parser reject a bad expression.)
• You will also need to extend the FunV value type since a closure should now hold a list of expressions.
• Write a helper function called eval-body that simply uses eval to evaluate a list of expressions. Its declaration should look like this:

  ;; eval-body : (Listof TOY) ENV -> VAL ;; evaluates a list of expressions, return the last value. (define (eval-body exprs env) ...)

• Finally, use eval-body in the right places (again, you'll have three of these).

Finally, you will extend the language so that it is possible to pass variables by reference, instead of the usual “by value”. In some languages, it is possible to mark some variables as “by reference” with some keyword (‘&’ in C++, var in Pascal, and ByRef in Visual Basic). C++ programmers that know C too can usually tell you that if you look under the hood, a by-reference argument is really just a pointer, and we can do the same with boxes now. (Note for C programmers: you can view a box as a pointer to its value.)

To make this a little easier we will not use a special mark for arguments. Instead, we will add a new kind of “by reference” functions: rfun — begin by adding this to the BNF (same as fun), and to the TOY type definition (as an RFun variant). Then modify the parser so it generates this new syntax type when seeing an rfun input: do not copy the code, modify the existing code for fun in a similar way that the bind code was generalized above. You will also need to deal with evaluating RFun syntaxes — make them evaluate just like Funs, but the resulting closure should be distinguishable from plain closures: so add a new kind of closure values (RFunV) to the VAL type definition, and use this new constructor when evaluating an RFun syntax.

The last step is the fun part (“fun”, not “fun”): applying RFun values. The first step is to separate the extend functionality into two parts: factor out the code that generates a new frame into its own function — extend-boxes:

Using this new functionality, you can play with some examples and make them into tests. Here's one example that defines swap: