Trash/DDC/ClosureTyping

Region sharing

Closure typing is used to track the sharing of regions between function calls.

Consider the following function:

f ()
 = do   x = 5
        g () = x
        g

Without closure information this function would have the following type:

f :: forall %r. () -> () -> Int %r

Remember that forall %r out the front is supposed to indicate that the return value is freshly allocated. This is certainly true if we apply both arguments:

twoSeparateInts :: Tuple2 %r1 (Int %r2, Int %r3)
twoSeparateInts = (f () (), f () ())

In twoSeparateInts there is a different region annotation on each of the Int constructors, which means they do not alias, and its safe to treat one as Const and the other as Mutable.

But what happens if we partially apply f? The standard type system will re-generalize the type for this new binding and we're left with:

f_unit :: forall %r1. () -> %r1
f_unit = f ()

We've now got a function which returns the same Int every time we call it, but the type says it's supposed to be fresh! The problem here is that x was free in our original definition of g so is shared between calls to it.

Closure typing