Blog Post

#736 Closure Redesign

brian Mon 7 Sep 2009

I have rewritten how the compiler generates code for closure variables (the ClosureVars step). The new design solves a couple big problems:

  1. should be faster for 90% of cases
  2. allows fine grained control of closure immutability (in preparation for removal of curry operator)
  3. fixes boundary cases I previously disallowed like nested closures in a field initializer
  4. fixes potential memory leaks when multiple closures share the same heap variables

Old Design

Let's start with how things used to work. Anytime you used a local variable in a closure, it was hoisted onto the heap so that it could be shared. All enclosed variables were stored in a single "Cvars" class per method:

x := 2; y := 3
f := |,| { echo($x $y) }

Would compile into something like this:

cvars := Cvars()
cvars.x = 2
cvars.y = 3
f := Closure(cvars)

class Cvars { Int x; Int y }

class Closure : Func
{
  new make(Cvars v) { cvars = v }
  Void doCall() { echo("$cvars.x, $cvars.y") }
  Cvar cvars
}

Because all cvars where shared, this made it difficult to determine immutability when a method had multiple closures. It also introduced a case where closures might be holding onto references they didn't actually need.

New Design

The new design works more like Java inner classes if the compiler detects that a variable is never reassigned. If a variable is never reassigned, then we can consider it "final" according to Java semantics. This means we can compile the code similar to how javac would do it:

x := 2; y := y
f := Closure(x, y)

class Closure : Func
{
  new make(Int x, Int y) { this.x = x; this.y = y }
  Void doCall() { echo("$x, $y") }
  Int x
  Int y
}  

I ran statistics across most of the code base, and it turns out that over 90% of closure variables are final and never reassigned. So this design should provide much better performance in most cases. Understanding how things work under the covers, you should attempt to assign your local variables exactly once to achieve better performance.

Per Variable Wrappers

If a variable is mutable, then it is still required to be hoisted onto the heap so that it may be shared between the method and closure. Instead of hoisting variables into a single Cvars class, we now use a wrapper per variable:

x := 2
f := |,| { x += 1 }

Compiles into:

x := Int$Wrapper(2)
f := Closure(x)

class Closure : Func
{
  new make(Int$Wrapper x) { this.x = x }
  Void doCall() { x.val = x.val + 1 }
  Int$Wrapper x
}

class Wrap$Int 
{ 
  new make(Int v) { val = v }
  Int val
}

This should drastically reduce the number of little classes spit out by the compiler, since we just need a single wrapper class for each type wrapped. It also allows a given closure to avoid referencing any state not directly used by itself.

Immutability

The main reason behind all this work is to allow normal closures to be used in situations where immutable functions are required and only the curry operator works today. Now closures follow more intuitive rules via these three cases:

  1. If the captured variables are final and every one is const, then the function is always immutable and toImmutable will return this
  2. If any of the captured variables are non-final or known to be non-const, then the function is never immutable and toImmutable always throws NotImmutableErr
  3. The last case is when variables are captured with types such as Obj or List where immutability is only known at runtime. In these cases the compiler generates a toImmutable method which attempts to call toImmutable on each variable captured to create a fixed immutable binding for each variable

This should allow much finer grained control of closure immutability over today's design. Remember that if you use a non-final variable in a closure, then the closure can never be considered immutable (we can revisit this issue after we get a little experience under our belt).

This change shouldn't effect any of your existing code. However it was a massive change under the covers to the most complicated step in the compiler. So if you notice any problems, please let me know.

KevinKelley Tue 8 Sep 2009

Great! this is good news. Fan's use of the Actor model for concurrency seems pretty powerful, but we needed a good handle on immutability to allow passing actions to actors.

I've been experimenting around with various concurrency frameworks -- in particular jCSP (CAR Hoare's CSP in java), and Triveni and Trull. Triveni/Trull seems especially interesting for my kind of uses, abstracting over composable networks of processes, and it looks like a good fit with Fan concepts. I'm thinking that with what Fan has now, the need for a library mostly goes away and it comes down instead to patterns of use -- meaning, it's time to put together some good examples showing how to solve a problem with this tools.

Anyway, very nice.

GwendolynBarry Sun 15 Aug 2010

removed

Login or Signup to reply.