In the last installment, we saw how nested functions are implemented. If you're thinking ahead, you'll ask "but what about pointers to nested functions? Does that work?" The problem is that the nested function, in order to work, requires and extra hidden parameter - the static link to its statically enclosing function's stack frame. This extra parameter means an ordinary function pointer won't work.

What's needed is a so-called "fat pointer" - a pointer pair, one of which points to the nested function, the other is the static link. In the D programming language, this "fat pointer" is called a delegate:

int foo(int delegate(int) dg)
{
    return dg(23);
}

int bar(int i)
{
    int abc(int x) { return i + x; }

    return foo(&abc);
}

The function foo takes as its parameter a delegate which can be called. The invocation bar(4) thus returns 27.

But something looks familiar about that fat pointer delegate. Don't struct member functions also have a hidden pointer - the 'this' reference? And doesn't that 'this' reference point to an object with a bunch of fields? Indeed they do. A delegate is indistinguishable from the address of a member function that is bound to a particular 'this' reference. Function foo cannot tell the difference:

struct S {
    int y;
    int mem(int x) { return y + x; }
}

int func()
{
    S s;
    s.y = 3;
    return foo(&s.mem);   // returns 26
}

As we've seen, the stack frame variables are just like a struct with the struct's fields corresponding to the function's local variables. But there's one more little problem. If that delegate (address of abc plus static link to bar's stack frame) is stored somewhere global, then bar returns, isn't the stack frame destroyed? Yes, it is. If the delegate is then called, won't it be referencing garbage on the stack? Yes, it will be.

Something more is needed; we can't tolerate such a gaping hole in our memory model. The answer is to carry the analogy of stack frames being like a struct a bit further. That frame need not actually be allocated on the stack. It can be allocated on the garbage collected heap. Then, it will persist as long as the delegate exists. Voila, no more memory corruption!

Of course, allocating every stack frame for every function on the heap is going to be disastrously slow - we use a stack because it's so fast at allocation and deallocation. What to do, what to do... The solution is to only allocate the frame on the heap if there is a delegate to a nested function and that nested function actually references variables within the frame.

By pulling on the nested functions string, we wound up with delegates and even closures. Adding in a function literal syntax to make passing delegates to other functions even easier, and we've got a truly delightful and powerful tool at our disposal. I learned about nested functions from the original Pascal language, but I hadn't appreciated how neat and elegant they are until rather recently. We keep finding new uses for them!

There is one more thing of note we can do with these:

Locally Instantiated Templates

Let's rewrite our initial example so that foo is a template function instead
of just a function:

int foo(alias dg)()
{
    return dg(23);
}

int bar(int i)
{
    int abc(int x) { return i + x; }

    return foo!(abc)();
}

An alias parameter to a template in D is passed symbolically, i.e. it is passed at compile time and the template foo is instantiated at compile time. The call to dg(23) is rewritten as abc(32). Using templates to pass parameters symbolically is very powerful, as there are no runtime pointers or other indirections involved.

But there's a problem. When foo is instantiated into being a real function, it's at global scope. When it makes the call abc(23), it has no way of getting the static link to bar's frame (so that abc can reference bar's parameter i). This looks like a real stumper. But the solution is an insight - instead of instantiating foo as a global function, instantiate it as a nested function in bar's scope!

But how does the compiler know to do that? When instantiating a template, it examines the arguments to the alias parameters, and if any of them are nested functions, the template is instantiated in the same scope as those nested functions. (Of course, if there are alias arguments that nest in different scopes, a compile time error results as there's no scope to instantiate the template in that would work for all the arguments.)

These are called locally instantiated templates. As far as I know, they are unique to D's template system.

If you want to learn more about how real compilers work, I am hosting a seminar in the fall on compiler construction.