Channels ▼

Walter Bright

Dr. Dobb's Bloggers

How Nested Functions Work, part 1

August 28, 2009

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.

Related Reading


More Insights






Currently we allow the following HTML tags in comments:

Single tags

These tags can be used alone and don't need an ending tag.

<br> Defines a single line break

<hr> Defines a horizontal line

Matching tags

These require an ending tag - e.g. <i>italic text</i>

<a> Defines an anchor

<b> Defines bold text

<big> Defines big text

<blockquote> Defines a long quotation

<caption> Defines a table caption

<cite> Defines a citation

<code> Defines computer code text

<em> Defines emphasized text

<fieldset> Defines a border around elements in a form

<h1> This is heading 1

<h2> This is heading 2

<h3> This is heading 3

<h4> This is heading 4

<h5> This is heading 5

<h6> This is heading 6

<i> Defines italic text

<p> Defines a paragraph

<pre> Defines preformatted text

<q> Defines a short quotation

<samp> Defines sample computer code text

<small> Defines small text

<span> Defines a section in a document

<s> Defines strikethrough text

<strike> Defines strikethrough text

<strong> Defines strong text

<sub> Defines subscripted text

<sup> Defines superscripted text

<u> Defines underlined text

Dr. Dobb's encourages readers to engage in spirited, healthy debate, including taking us to task. However, Dr. Dobb's moderates all comments posted to our site, and reserves the right to modify or remove any content that it determines to be derogatory, offensive, inflammatory, vulgar, irrelevant/off-topic, racist or obvious marketing or spam. Dr. Dobb's further reserves the right to disable the profile of any commenter participating in said activities.

 
Disqus Tips To upload an avatar photo, first complete your Disqus profile. | View the list of supported HTML tags you can use to style comments. | Please read our commenting policy.
 


Video