• Homework
• Resources

Homework #6: Mutant FLANG

Out: Friday, February 17th, Due: Friday, February 24th, 7:30pm

Administrative

The language for this homework is:

#lang plait

In this homework you will start with FLANG Language with (box-based) recursion (FLANG+recursion via mutation) and add several features related to mutation.

For full marks, you should try minimize the amount of cut-and-pasting involved in adding new features to the language. See the existing parser for let1 and rec for the kind of thing that you should try to emulate.

For this assignment you are allowed to use boxes, but not plait’s set!

Variable Assignment

Since we have an environment where names are associated with mutable boxes, we can use that to implement variable mutation. To do this, you need to extend the language with a new special form: set!. The syntax of this form is: {set! <id> <RFLANG>}. Add this to the RFLANG type definition (use Set for the name of the new variant), and to the parser code. To implement the semantics of the new form, add a Set case to the interp 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.

When you implement the semantics of set!, return some bogus value that cannot really be used for anything, which will make sure that expressions that are used for side-effect (only assignments for now) are not confused with other expressions.

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

Be sure to add some test cases to check that your modification works. This will be tricky at this point, since let1 and lam bodies have just one expression. Hint: We can use nesting to fake sequencing, as we often do. In particular you can bind a name to an expression, and never use it. For example, in Racket:

(let ([x (display "foo")]) 2)

(begin (display "foo") 2)

Multiple Body Expressions

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

In order to avoid modfying all 3 of these, we will add a single begin form modelled on the same form in Racket.

To implement this:

• Extend the RFLANG type definition, then adjust the parse-sexpr function accordingly. Remember that a body of expressions requires at least one expression (it doesn’t make much sense to have no body). It easiest to use a single Listof in the type and make the parser reject a bad expression as a syntax error, so in the rest of the code you can rely on the list being non-empty.
• Write a helper function called interp-body that simply uses interp to evaluate a list of expressions. There is a decision to make here: what should the value of evaluating a body of multiple expressions return. Like in Racket, we will choose to return the last value.
  The declaration of interp-body should look like this:

  ;; evaluates a list of expressions, returns the last value. (define (interp-body [expr-list : (Listof RFLANG)] [env : ENV]) —«fill-in»—)

  To test your code for both begin and set!, you can use tests like the following.

  (test (run `{let1 {x 1} {begin {set! x 2} x}}) 2) (test (run `{let1 {x 1} {begin {set! x {+ x 1}} x}}) 2) (test (run `{let1 {make-counter {lam initial {let1 {c initial} {lam dummy {begin {set! c {+ 1 c}} c}}}}} {let1 {c1 {make-counter 0}} {let1 {c2 {make-counter 0}} {* {* {c1 0} {c1 0}} {* {c2 0} {c1 0}}}}}}) 6)