Implementing Closures

Please consider the following pseudocode...


typedef (int (*)(int)) int2int; // int2int: type of function taking an
int and returning an int


int2int f()
{
        int x = 3;


        int g(int y) // local function
        {
                x = x + y; // modifies local variable from enclosing scope.
                return x * y;
        }


        return g;
}


int2int h = f();
print(h(2)); // prints 10
print(h(2)); // prints 14
h = f();
print(h(2)); // prints 10


Here f is a function that takes no parameters and returns a function
of type (int -> int).


g is a local function that makes use of a local variable from a
containing scope.


A compiler (such as a C/C++ compiler) would normally implement x by
allocating space in f's stack frame.


The problem is that when f returns the closure g still needs access to
that instance of x for its lifetime, but the stack frame is deleted.


Also it is not sufficient to implement the function pointer of g as
simply pointing to static code. Each instance of int2int, must also
have some kind of reference to the x instance it modifies.


What are some of the approaches a compiler author could use to
implement such a language feature?


Thanks,
Andrew.
[This issue is well understood in the Lisp community. You basically need
to implement the activation records in a heap and garbage collect them,
keeping them live as long as there are any references to the closure. If
the closure can refer to variables in enclosing scopes, you need to keep
those scopes active as well, in what's known as a spaghetti or cactus
stack. -John]

Return to the comp.compilers page.
Search the comp.compilers archives again.