We're all familiar with C functions and how they can call each other recursively:

int foo(int i)
{
    int a;
    a = bar(i);
    return a + 1;
}

int bar(int i)
{
    if (i & 1) return foo(i);
    return i;
}

When a function is entered, a stack frame is created that holds all the local function variables and parameters, and a back pointer to the caller's stack frame. In x86 assembler, the stack frame setup looks like this:

    push EBP           ; caller's EBP is dynamic link
    mov  EBP,ESP ; EBP is frame pointer
    sub  ESP,n*4    ; make room for n locals
    ...
    mov  ESP,EBP ; remove locals from stack
    pop  EBP            ; restore caller's EBP
    ret

But what about nested functions? (C doesn't have nested functions, but the D programming language does.)

int abc(int i)
{
    int a = 7;
    int def(int x) { return a ? def(a) : x; }
    return def(i) + 3;
}

How does the arbitrarily nested calls to def successfully find abc's a? It does not know how many frames back it may be.

Let's look again at the stack frames with back pointers. They look awfully familiar - they're just a backwardly linked list of structs. The fields of the structs are the parameters and local variables. For non-nested functions foo and bar, they look like:

   struct FooFrame
   { int i;
      void* dynamicLink;
      int a;
   }

   struct BarFrame
   {    int i;
        void* dynamicLink;
   }

The dynamicLink member points to the calling function's stack frame. (Stack walkers like debuggers and exception handlers simply walk that list.) To make this work for nested functions, we need to add another threaded list, which links together the lexically enclosing frames, called a static link:

   struct AbcFrame
   { int i;
      void* dynamicLink;
      int a;
   }

   struct DefFrame
   {
        int x;
        void *dynamicLink;
        void *staticLink;
   }

Now, when abc calls nested function def, it passes to def a pointer to its own stack frame AbcFrame, which is used to initialize the staticLink member of  DefFrame. When def recursively calls itself, it passes the value of its staticLink,
not a pointer to its own stack frame DefFrame. Hence, no matter how many invocations of def are on the stack, the staticLink pointer points to the enclosing
stack frame AbcFrame of abc.

Let's rewrite abc and def in C to illustrate the semantics - doing nested functions is just syntactic sugar for this:

    struct AbcFrame
    { int i;
       int a;
    };

    int def(struct AbcFrame *f, int x)
    {
        return f->a ? def(f, f->a) : x;
    }

    int abc(int i)
    {
        struct AbcFrame f;
        f.i = i;
        f.a = 7;
        return def(&f, f.i) + 3;
    }

One more thing: if there are nested functions within nested functions:

   void A()
   {
       void B()
       {
           void C()
           {
                void D()
               {
                    B();
               }
           }
       }
   }

The interesting case is D calling B. Somehow, it needs to get the static link to A's frame and pass it to B. This is because B expects a link to A's stack frame. All that's necessary is to follow the staticLink members back up three levels. Because of visibility rules, this all works - B cannot 'skip' C and call D directly, as it cannot even see D. So, it is only possible to either increase the static nesting level by one, or subtract multiple nesting levels.

 

In part 2, we'll show some more interesting consequences and opportunities presented by nested functions. For instance, what's a locally instantiated template?

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

Thanks to David Held, Bartosz Milewski, Jason House and Andrei Alexandrescu for reviewing this.