23

I'm learning C and was curious as to why the language does not allow nested functions.

From what I've read, the lack of nested functions seems to have been a simplification that was inherited from its parent language, B. And the reason they were left out of B seems to be twofold:

  1. Memory limitations - the language needed to be compact so that its compiler would fit in the PDP-7's 8K memory (Ritchie, 1993).
  2. Speeding up the runtime organisation.

Is this correct or were they excluded from C for some other reason?

Also, I came across the second point in Peter van der Linden's Deep C, but I'm not quite sure what it means. The author says excluding nested functions "simplified the compiler and slightly sped up the runtime organistion of C programs", and later briefly mentions how nested functions are implemented with static links in other programming languages such as Pascal, PL/I and Algol-60. So, by "speed up runtime organisation", does the author mean that B and C's program execution is sped up as a result of not having to maintain these static links at runtime?


EDIT: To clarify, by "nested function", I mean a function whose definition appears within another function's body and which can access the outer function's variables, so something like:

int foo() {
    int x = 1;

    int bar(y) {
        return x + y;
    }

    return bar(9);

}

13
  • 8
    With nested functions, you need to figure out how to access local variables of the parent functions, which needed a special setup on the stack. "Newer" (or older, but more sophisticated) CPUs offered this as a special command, while "older' CPUs need additional commands to do that. So it quickly stopped being a speed improvement, and it was only a modest one in the first place.
    – dirkt
    Nov 28, 2022 at 6:34
  • 6
    Non-nested functions are also a lot easier to understand (personal opinion). If you ever have to work with Javascript, which is a C derivative that allows inline unnamed nested functions, you will see the complexity that function nesting brings.
    – cup
    Nov 28, 2022 at 7:27
  • 4
    (mostly off topic) This is a good question, but it did make me smile. The language I first used professionally was Forth, which might be described as nothing but nested functions. The classic implementation to accomplish this is with two simple stacks. The first is the parameter stack, which is the primary means of passing values and getting values back. The return stack keeps track of where to go back to when the current word ("function") completes. This scheme allows Forth to execute quickly and use little memory. Of course, a Forth programmer has to think backwards, and for me, cool.
    – RichF
    Nov 28, 2022 at 16:25
  • 6
    Given there's either no difference (only access to globals), or the ability to break the function in subtle ways through code outside the function (access to parent variables); and I'm not sure many benefits, it could just have been decided it wasn't a feature worth implementing. C was not supposed to be an all-encompassing language like Algol.
    – davolfman
    Nov 28, 2022 at 18:11
  • 3
    I feel like there's a disagreement in the answers, about what a nested function is. Are they regular functions declared within a function scopes, or are they named closures? Both are "nested functions" in a sense, but the difficulty in implementing them varies quite a lot. Could you please clarify in the question which type of function you meant? Nov 30, 2022 at 10:04

8 Answers 8

31

Keeping all functions as a flat array/list that can simply be iterated over does make life a lot simpler for a compiler writer. No nested functions allows that, and also resolves some forms of the funarg problem. Here is one aspect of it:

C has sort-of first-class functions. You can pass them to functions, and return them from functions. (Standard Pascal doesn't allow you to return a function as a value.) C is also a simple stack-oriented language, where memory is allocated and the local variables are initialized upon function entry, and discarded upon function exit. If we allow functions inside functions, it raises certain questions. For example, if you pass a nested function as a parameter to another function, what is its environment? Does it initialize a new parent function, or use the local environment? If you pass it outside the parent function, what's that environment? The encompassing function's stack frame would not have been initialized, etc. Well, perhaps it could be, or a closure could be used and passed around. A closure would be the "static link" you speak of. A pointer to an environment for the function. Now you have to keep track of that. We're trying to fit into 32 KB aren't we?

1
  • Comments are not for extended discussion; this conversation has been moved to chat.
    – Chenmunka
    Nov 30, 2022 at 20:18
19

Yes, not supporting nested functions simplifies compiler construction.

It's a matter of scope handling. Nested functions do need a compiler that can handle function names according to scope. I.e. a nested function should only be (by default) visible to code within that function, but not outside, thus the compiler has to dynamically 'learn' and 'forget' their names. By not supporting nested functions a compiler can handle all function lookup in a single flat table. It doesn't need to create and destroy sub tables according to scope.

Usually, a simplified compiler will of course be faster written, need less memory and compile faster.

No, I know of no reason to speed up runtime organization by not supporting nested functions.

That is, if that statement is about the runtime organisation of the program compiled. Supporting or not supporting is a sole function of the compiler and should not in any way influence the generated program. Something not in a program can of course not have any influence on runtime.

Of course the above statement could as well be understood as referring to the compiler, which would be just a repetition of the first point.


An interesting side note here might be that C originally did not supported any block scope for variables either, as mentioned in this Softwareengineering.SE answer: The 1975 Manual only allows local variable definition on function level (and global/external), while the 1978 "The C Programming Language" explicitly adds block level. So the addition of that feature must have happened somewhere in between.

Likewise newer C compilers (like GCC) nowadays allow nested functions.

16
  • 11
    Assuming we're talking about Algol-like nested functions, permitting uplevel references and recursive activation, then you need to either maintain a display, or follow the activation chain for uplevel references. Either of these involves runtime overhead.
    – dave
    Nov 28, 2022 at 13:37
  • @another-dave Not exactly sure what additional effort you mean, but as far as basic nested functions goes, all can be handled within the limits of basic calling effort.
    – Raffzahn
    Nov 30, 2022 at 11:17
  • See for example the ENTER and LEAVE instructions of x86 - in particular maintenance of the 'display'. Those are not cheap instructions. I'd bet they only get used for languages with nested functions (with uplevel references). But what do you mean by 'basic' nested functions?
    – dave
    Nov 30, 2022 at 13:44
  • @another-dave ENTER/LEAVE are instructions to manage local storage. Handling local storage is independent of the scope a function is defined. Nested functions are about scope, i.e. where that function is visible. Next, I wrote 'basic calling effort' that is the basic overhead to call a function, lo matter what way local storage is used. Last but not least, ENTER/LEAVE are not expensive. They replace a costly sequence to set up a stack frame (PUSH BP;MOV SP,BP, SUB SP,size). They got a bad rep with 486 as it execute that sequence faster than the single instructions.
    – Raffzahn
    Nov 30, 2022 at 15:03
  • 1
    @another-dave True. Those languages do support this (which BTW is also what ENTER/LEAVE do as option). Based on that assumption I do see your point. You're right if it's about full support. But C did cut several corners of its predecessors to slim down. So I interpreted the question not so much why there is no full figured support for the concept, but why it was left out in total. (In addition and IMHO access to higher level surrounding is a great source for spaghetti code, so I wouldn't mind. I'm already careful when it comes to global data, so some kind of half way global sounds like hell)
    – Raffzahn
    Dec 1, 2022 at 2:16
11

It Would Have Been Possible

The feature was implemented in other languages of the time. I’m not aware of a specific quote by Dennis Ritchie or Ken Thompson explaining their reasons for not including it. However,

There Would Have Been Trade-Offs

Consider the simple example:

int(*)() foo(x)
  int x;
{
  int bar(y, z)
    int y;
    int z;
  {
    /* Do stuff.*/
  }

  int baz(w)
    int w;
  {
    /* Do stuff. */
  }

  /* Do stuff with x, foo() and bar(). */
  return (int(*)())(bar);
}

There are a few different ways the language could have handled this:

Nested Functions That Don’t Capture Their Environment

This is similar to Rust (which has separate closures). If Dennis Ritchie had gone this route, the low-level implementation of nested functions could have been exactly the same as top-level functions. Neither foo::bar() nor foo::baz() would be able to refer to the x parameter of foo() (unless the programmer explicitly copied and passed it to the inner function). Here, foo() could return a pointer to either function, and any other external code could safely call it.

On the other hand, there would be nothing you could do with these nested functions that you could not accomplish with C as it exists, by writing static int foo_bar() as a non-nested function. The behavior is the same, and all you are adding is the ability to place the function definition inside function scope. Nesting the function might make it easier for an optimizer to see that there are only one or two paths of control flow that could possibly reach some code.

C Might Have Had First-Class Closures

C++ ended up adding several different variations on this idea in the twenty-first century: lambdas, std::function objects, member-function pointers, std::bind, and I think even a few more.

This would be more complex than function calls in C, but one fairly-simple way to enable it is to pass the daughter function a pointer to the parent call’s stack frame, and the grandparent’s if the function is doubly-nested. This would allow a nested function to access variables in the scope of the most recent call to the functions it’s nested in, even if there are arbitrary recursive or sibling calls in between.

One complication here is what happens when you take a pointer to a nested function. There are legitimate use cases for this, but can such a function pointer be returned from a function, passed back in as an argument to the same function (perhaps through a pointer-to-function-pointer input-output parameter), and called on a different invocation? Would such a call capture the original environment, or the current one? Can a returned pointer to a nested function even be called from outside the parent function?

Functions in early C are very weakly-typed, and the type of a nested-function pointer would have been a leaky abstraction. For example, if the syntax had the type “doubly-nested function returning int,” and allowed one to be called with no other information about the context, all implementations would have to support that.

It Might Have Been Restricted for Simplicity

The complexity of the previous section goes away if it’s illegal to take the address of a nested function at all, and most of it goes away if the closure is considered a temporary whose address cannot be returned from a function. Classic Pascal, which had a lot of influence on C, did not have function pointers. The designers might also have introduced stronger function typing much earlier than they did.

C++ Ended up Doing it a Different Way

In the example I gave above, though, there’s no compelling reason to use closures. foo(x) has only one int argument, and it would be simpler and faster in this example just to pass that to bar(x,y,z) or baz(x,w) if either actually needs it. This would only be more efficient if there were a large number of parameters to be captured.

It’s very unusual to write functions with many arguments, though—especially in K&R, where the compiler cannot even type-check them. Typically, when it grows big enough to be inconvenient, the parameter list gets refactored into a struct. Once you do that, the local state you’d be encapsulating in a closure would all be in that struct, so you can just use the struct to roll your own closure. Maybe pass it in a pointer, and call it this. Then, to be able to call it from elsewhere in the program, you would need a dynamic function pointer—or even a dynamic table of multiple function internal functions, such as bar() and baz(). Since bar() and baz() are both part of the same scope and can call each other. So maybe you put a virtual function table as part of your this structure. Congratulations, you’ve reinvented the class. C with Classes, which evolved into C++, began just as syntactic sugar for that. And first-class closures would have been different syntactic sugar for something very similar.

This is a very popular paradigm, but the C language committee decided that it would be better to keep the language small and simple. And closures would have mostly just duplicated the same functionality.

9

The parser design of early C compilers could be split into two parts: one for processing stuff outside a function body, and one for processing stuff inside a function body. Although some of the more obviously ambiguous constructs have been deprecated, the language as it existed in 1974 would allow a function f that returned int to be declared by writing f() somewhere outside a function definition. A call to a function f which passed no parameters and ignored the return value could be written as f(), but function calls could only appear only within function bodies.

If the language had allowed function definitions, but not declarations, within function bodies, that might have avoided ambiguity, but only if one were willing to forego the single-pass nature of the language. Although C compilers would generally include some output buffering to allow code to be written in cleaner sequence, a C compiler that got as far as parsing a function call

foo(x,y,

could output code for that much of it and not have to keep any of that in memory anymore. If targeting the 8088 instruction set, if that were the 23rd function call within the 9th function, a compiler targeting the 8086 could generate:

         jmp f9k23l0
f9k23l2: 
         call foo
         jmp f9k23l1
f9k23l3:
         push [BP+offset X]
         jmp f9k23l2
f9k23l4:
         push [BP+offset Y]
         jmp f9k23l3

and forget everything about the function call or the arguments that had been processed thus far, beyond the count of how many functions had been processed, how many calls had been made in the current function, and how many labels had been allocated thus far in association with that function call. While the number of jumps would seem absurd, a compiler which fed code to a buffer rather than writing it to a file could, once the buffer needs to get written to the file, rearrange the code in the buffer to avoid jumps within it. If the entire function call has been processed by that point, great. No unnecessary jumps. If the buffer gets full and needs to be output before that, this would end up leading to inefficient jumps within the generated code, but the program would still compile and run correctly.

If one adds the possibility that the above code might not be a function call but instead be a definition of some new function f(), however, then it would be impossible to generate any code for a function call until the entire thing had been parsed.

4
  • 1
    Inasmuch as I follow this, I think you're arguing that nested functions were not possible because the terse K&R functiondefinition syntax could not support it. But that seems backwards reasoning to me; if nested functions were wanted as a useful programming construct, then the syntax would have been something that allowed it.
    – dave
    Nov 28, 2022 at 21:26
  • @another-dave: The "flat" design makes the language simple to process. If there were a perceived need to support nested functions, the language could have been designed differently in a manner that was less convenient to parse, but would avoid grammatically ambiguous situations. The resulting language, however, wouldn't have been the C language we got, but something else instead.
    – supercat
    Nov 28, 2022 at 21:38
  • 2
    Well, sure - if the language had different features, it would be a different language :-) Which might be the actual answer to the OP.
    – dave
    Nov 29, 2022 at 0:02
  • 1
    @another-dave: Many aspects of the C language could be made more useful with minimal tweaks to compilers. My point was that early compilers were designed in ways that would not have been amenable to supporting nested functions because the parsing code that was used within functions was very different from the code that was used outside.
    – supercat
    Nov 29, 2022 at 0:18
9

Other answers and comments allude to the problem, but I wanted to offer my own perspective.

There is a question about what it means for a function to be "nested".

If it means a function that exists at the same top-level namespace as the enclosing function and has the same accessibility, but whose source code is merely organised within the source code of the enclosing function, then that would be relatively trivial to implement. The only complication would be for the programmer, since the namespace now has a different structuring (flat) than the source code (hierarchical).

If it means the same as above, but that the nested function can only be called from within the enclosing function, then enforcing this restriction is inconsistent (in at least some respects) with the use of function pointers - which is a foundational concept in computer science, and an essential feature of the C language.

Finally, if it means the nested function would have implicit access to the local variables of the enclosing function, then obviously it must be only the enclosing function that can call into this nested function, it must mean inconsistency with the use of function pointers, and it must mean that the mechanics of calling these nested functions are different than for ordinary functions.

If we reviewed why the programmer would want to use these nested functions, the same purposes would probably be served as easily in another way by using the ordinary facilities of block-structured programming in C, at the extreme by using GOTOs, or by just writing a non-nested function with the local variables passed to the function as explicit arguments.

As someone who has used .Net languages (VB.NET and C#) that actually have this facility of nested functions (in the latter sense above), I'm inclined to condemn it as "harmful".

I believe it was added to these languages to support very specific needs (related to the LINQ querying feature, where its use as part of short, anonymous functions within an enclosing scope seems quite obvious and useful), but as a general concept it is complicated to understand and clashes harshly with other language features and programming principles. It's also worth noting that these are amongst some of the most modern compilers running on powerful hardware.

So in terms of why it was left out of C (dating from the 1970s onwards), certainly the complexity of compiler implementation would have featured, but I'd suggest the overwhelming reason was simply avoiding complexity in the C language itself and the absence of compelling uses for nested functions (given that the compelling use I mention for the .Net languages, the LINQ querying feature, is light-years beyond C).

9

This is to some extent repeating ideas made by other people in other answers and comments, but I think it deserves to be promoted to 'answer' status.

C does not have nested functions because it wasn't considered useful or necessary by the language designers -- by which I mean Ritchie et. al. (And it wasn't added by ANSI, since their initial remit was to standardize existing practice, not break new ground).

Recall that C was born as the Unix implementation language. Features were added in response to need. The desire was to have a language in which to write Unix and programs to run on Unix, and a few other systems. There were no features in K&R C that were superfluous to that. The size constraints of the PDP-11 surely helped their focus.

This was YAGNI in practice.

2
  • I would argue that unless the language is built around the idea (e.g., JavaScript) that nested functions and lambda are STILL not useful or necessary. Dec 8, 2022 at 16:31
  • Oddly enough, I wrote a couple today. It was the natural way to do what I needed; in this case the point was to control their scope to the surrounding function (Python, FWIW). Of course, in C I could have made them static and confined their scope to a file, but that would still have been much wider than needed.
    – dave
    Dec 8, 2022 at 23:37
3

My guess is that they either:

  1. Never thought of it
  2. Thought of it, but determined it would make the compiler too complex for the resource footprint they wanted and wasn't worth whatever benefit it would have brought to the language.

Nested functions may seem like a forgotten feature to modern programmers, but you need to put yourself into the mindset of a programmer in the 1970s. The keyboard on your desk likely has as much processing power as the machines K&R had. Memory was measured in kilobytes.

I programmed professionally on K&R (i.e., pre-ANSI) era compilers. The alternative for me was writing in assembly language (hopefully paired with a good macro language). Debugging involved calls to a stripped down printf we wrote (we didn't have enough memory for a full C library implementation, so we wrote our own about 10 function version).

The original C language is best compared to that set of programmer tools. You can create a function. You can declare that it returns a value (or not) and that it has a number of parameters (you declare the types of those parameters separately). If you don't declare a return type, it's assumed to return an integer (if my code didn't actually return something, the compiler I used returned (int) 0). The parameters are pushed onto the stack by the caller before the call and (effectively) popped off after the call returns.

Then you write some logic in the body of the function.

That's pretty much how you write well-structured assembly language. But, the C language was soooo much more expressive than assembly language. The compiler I used was pretty basic but it worked fine. We eventually got an in-circuit emulator for debugging; you could place a hardware breakpoint in your code (looking up symbols in a MAP file) and examine memory. I could decompile what I saw in my head (that's the for loop, that's the if statement, the next breakpoint goes here). That's an advantage of having nearly no optimization in the compiler.

As I've said before on this site, it's not fair to look at stuff that was invented/implemented 30, 40, or 50 years ago and say "why didn't they do it this way - it's so obvious?"

2
  • 5
    I think we can discard the 'never thought of it' part. Ritchie has explicitly mentioned features that were inspired by Algol 68, so he at least (and, I would guess, pretty much any language designer of the time) was familiar with Algol 68, which had nested procedures. Your second option is, IMO, nearer the mark - they saw no need of it for writing Unix.
    – dave
    Dec 1, 2022 at 2:10
  • 2
    That's about the 10th time in my life that someone has countered what I've said with "but that was in Algol". Someday I'm going to learn that language. Thanks
    – Flydog57
    Dec 1, 2022 at 4:47
2

I can't speak of the line of thinking of Brian Kernighan and Dennis Ritchie at the time, but it was the general idea that C be minimalist and utilitarian and nested functions do not add anything to the language. I would argue that almost nothing in later languages improves on C and that's a big reason why C is still very popular today.

Here's a less contrived example of nested functions for qsort:

void sort(int *items, int size) {
    void quickSort(int first, int last) {
        void swap(int p, int q) {
            int tmp = items[p];
            items[p] = items[q];
            items[q] = tmp;
        }
        
        int partition() {
            int pivot = items[first], index = first;
            swap(index, last);
            for (int i = first; i < last; i++)
                if (items[i] < pivot)
                    swap(index++, i);
            swap(index, last);
            return index;
        }

        if (first < last) {
            int pivotIndex = partition();
            quickSort(first, pivotIndex - 1);
            quickSort(pivotIndex + 1, last);
        }
    }
    quickSort(0, size - 1);
}

Why would you not simply:

static void swap(int *items, int p, int q) {
    int tmp = items[p];
    items[p] = items[q];
    items[q] = tmp;
}

static int partition(int *items, int first, int last) {
    int pivot = items[first], index = first;
    swap(index, last);
    for (int i = first; i < last; i++)
        if (items[i] < pivot)
            swap(index++, i);
    swap(index, last);
    return index;
}

static void quickSort(int *items, int first, int last) {
    if (first < last) {
        int pivotIndex = partition(items, int first, int last);
        quickSort(items, first, pivotIndex - 1);
        quickSort(items, pivotIndex + 1, last);
    }
}

void sort(int *items, int size) {
    quickSort(items, 0, size - 1);
}

What are you saving with nested functions?

Namespace pollution? That's solved with statics -- C's "private". These aren't exported and won't contribute to namespace pollution.

Not having to pass so many arguments to each function? A static inline function won't have to.

Saving 20-seconds of typing? Maybe, but the general rule is if you're typing the same thing over and over then it's an opportunity for refactoring.

Personally, I prefer the latter form because we're precisely controlling scope. This alone eliminates a few nasty bugs I've seen creep into Node.js code.

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .