Previous    Next

CLOSURE CONVERSION

A function passed as an argument is represented as a closure: a combination of a machine-code pointer and a means of accessing the nonlocal variables (also called free variables). An example of a nonlocal variable in an object-oriented language is an instance variable of a class. A method referring to an instance variable accesses it through this, which is an implicit formal parameter of the method. One way to compile free-variable access for nested functions is to represent closures as objects. The closure conversion phase of a functional-language compiler transforms the program so that none of the functions appears to access free (nonlocal) variables. This is done by turning each free-variable access into an instance-variable access. Some local variables declared in a function f are also accessed by functions nested within f; we say these variables escape. For example, in Program 15.5, in the function putInt, the variables dig and c escape (because they are used in the inner-nested function doDigit), but the variable rest does not escape. Given a function f(a1,…, an) B at nesting depth d with escaping local variables (and formal parameters) x1, x2,…, xn and nonescaping variables y1,…, yn, we can rewrite into

f(this, a1,..., an) {
 c272 r = newc272(this, x1, x2,..., xn);
return B′
]


The new parameter this is the closure pointer, now made into an explicit argument. The variable r is an object containing all the escaping variables and the enclosing closure pointer. This r becomes the closure-pointer argument when calling functions of depth d + 1. The class (in this case c272)hasto be made up specially for each function, because the list of escaping variables (and their types) is different for each function. Any use of a nonlocal variable (one that comes from nesting depth < d) within B must be transformed into an access of some offset within the record this (in the rewritten function body B′). Function values We can represent a function value as an object with a single method (which we will call exec) and zero or more instance variables (to hold nonlocal variables). We will represent the type t1 -> t2 as the class

abstract class c_t1_t2 { abstract public t2 exec(t1 x); }


and any actual function value belonging to this type will be an extension of this class, adding instance variables and overriding exec. Program 15.12 is the result of closure-converting Program 15.11. We can see that each function type is an abstract class, and each function is a different subclass of the abstract class. Escaping local variables are put into the closure objects of inner-nested functions. Furthermore, when functions are deeply nested, it's often useful for the closure of the inner-nested function to have a link to the enclosing function's closure for convenient access to variables of functions further out.

printTable after closure conversion (class constructors omitted).
abstract class cont {
 abstract public answer exec(); }
abstract class c_list_cont_answer {
 abstract public answer exec(list l, cont c); }
class printTable extends c_list_cont_answer {
 public answer exec(list l, cont c) {
 doListX r1 = new doListX(this, c);
 return r1.exec(l);
} }
abstract class c_list_answer {
 abstract public answer exec(list l); }
class doListX extends c_list_answer {
 printTable link;
 cont c;
 public answer exec (list l) {
 return if (l==null) c.exec()
 else {doRest r2 = new doRest(this,l);
 int i = l.head;
 again r3 = new again(i,doRest);
 return putInt.exec(i,again);
} }
abstract class c_void_answer { abstract public answer exec(); }
class doRest extends c_void_answer {
 doListX link;
 list l;
 public answer exec() {
 return doListX.exec(l);
} }
class again extends c_void_answer {
 int i;
 doRest d;
 public answer exec() {
 return putInt(i+i, d);
} }



Java End example

JaVaScreenshot Previous    Next
Comments