Trash/DDC/ClosureTyping

Region sharing

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 the forall %r at the front of the type 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 are different regions 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 the 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

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

The actual type which is inferred for f is:

f   :: forall %r1
    .  () -> () -($c0)> Int %r0
    :- $c0        = x : %r0

In this type, the $c0 annotation tells us that this function has a object free in its closure which contains the region %r0. In (x : %r0) the x is simply a name for the object which contains this region, and has no other special meaning. We'll see what these names are for in a moment.

If we use this new type and apply the first argument we have:

f_unit :: () -($c0)> Int %r0
       :- $c0   = x : %r0

In this type says that f_unit is a function that takes a unit value and returns an Int, but that Int is free in its closure, ie is being shared by all calls to it and is not fresh. The type system does not generalize regions which are free in the closure of a function.