lexical analysis – What makes a nested function in C so complicated?


Disclaimer: I’m not a compiler expert, but some of my best friends are! 🙂

I do a lot of embedded systems programming where stack (and other memory) is limited. Most of my code is written in gcc, so I thought nested functions could be useful for reducing stack usage. Here’s an example of what I had in mind:

(Though the algorithm isn’t important for this question, assume that list_traverse takes a pointer to a list head and a function. The function gets called with each element in turn, returning false when it wants the traversal to stop.)

bool list_contains(list_t *head, list_t *item) {
  bool found = false;
  bool contains_aux(list_t *list) {
    if (list == item) {
      found = true;
      return false;
    }
    return true;
  }
  list_traverse(head, contains_aux);
  return found;
}

I assumed that the nested contains_aux() function would simply be compiled “inside” the list_contains() and be able to reference the lexically closed variables (found and item). But I was wrong.

Instead, looking at the generated code, I see that it installs some sort of trampoline function on the stack and calls that before getting to the contains_aux() function.

I guess that makes sense: contains_aux() can’t share the same stack frame as list_contains() because we’re another function deeper in the stack when its called (via list_traverse()).

So is there some way to accomplish this sort of lexical closure efficiently? Or should I just resign myself using un-nested functions and passing a “context” object to contains_aux()?