How to migrate a single variable

If a local variable x is migrated to the heap, every mention needs to be changed:

• The binding instance must be changed to use the ref primitive:

  • (let ([x e]) …) becomes (let ([x (ref e)]) …).
  • (lambda (… x …) …) becomes (lambda (… x …) (let ([x (ref x)]) …)).

• Every write (set x e) becomes a call to primitive :=, as in (:= x e).

• Every read x becomes a call to primitive !, as in (! x).

I recommend defining a helper function for each of these cases.

Primitives ref, !, and := are equivalent to the primitives of the same names that are built into Standard ML; you will need to add them to the UFT and the SVM. Their implementations in the SVM will be almost identical to mkclosure, getclslot, and setclslot, except they will operate on a struct VMBlock, not a closure.

• ref takes one argument, allocates a block on the heap, and stores the value of its argument in that block.

• ! fetches the value stored in a block.

• := updates a block.

How to identify and migrate all necessary variables

A local variable x must be migrated if it meets both of the following criteria:

• Variable x is mutated (written) somewhere in the code.

• Variable x is read or written in a lambda expression that appears in the body of the construct that binds x. (That construct is always a let, a letrec, or a lambda.)

Mutated, captured variables can be migrated to the heap in a two-pass algorithm. I recommend that you define a monad ’a decorated, which should extend any value of type ’a with an environment that remembers a property of mutated variables:

• For every variable that is set, the environment remembers the largest number of lambdas that appear between the syntax being translated and any point where the variable is read or written.

The translation can be written using the Applicative operators <*>, <$>, and pure, which you will have to define.¹

• The first pass walks the syntax from the bottom up, accumulating the environment that remembers the property of mutated variables. It has type exp -> exp decorated.

• Every time this pass encounters a LAMBDA, it checks the bound variables to see if any of them is referred to in a nested lambda. If so, it lifts those variables in the LAMBDA and in the body of the LAMBDA.

• Every time this pass encounters a LET, it checks the bound variables to see if any of them is referred to in a nested lambda. If so, it lifts those variables in the LET and in the body of the LET.

A definition is rewritten by translating its expressions, then discarding the decorations.

Testing

The ultimate test will be the examples from section 2.7.1 of my book. But for starters, here is a file you can test. First use run-hox-with-predef, then use uft hox-cl to confirm that y is not migrated.

(define must-migrate (x)
  (let* ([f (lambda () x)]
         [_ (set x 99)])
    (f)))

(check-expect (must-migrate 3) 99)


(define should-not-migrate (y)
  (let* ([f (lambda () y)])
    (f)))

(check-expect (should-not-migrate 3) 3)