Nested function

In computer programming, a nested function (or nested procedure/subroutine) is a function which is lexically (textually) encapsulated within another function, with lexical scope. Nested functions are used in some approaches to structured programming, such as in Pascal, but are not supported in other widely-used structured languages, such as C.

Due to nesting, the scope of the nested function is inside the enclosing function – the nested function is not available outside the function, at the global or module scope – and the nested function can access local variables in the enclosing function, which are known as non-local variables in the nested function. The nesting is theoretically possible to any level of depth, although only a few levels are normally used in practice.

Examples

An example using Pascal syntax:

function E(x: real): real;
    function F(y: real): real;
    begin
        F := x + y
    end;
begin
    E := F(3) + F(4)
end;

The same example in GNU C syntax:

float E(float x)
{
    float F(float y)
    {
        return x + y;
    }
    return F(3) + F(4);
}

One way to write the same example in Haskell syntax:

e :: Float -> Float
e x = f 3 + f 4 where f y = x + y

The function F is nested within E (note that x is visible in F and y is invisible outside F).

Quicksort

A more realistic example is this implementation of quicksort:

void sort(int *a, int size) {
    void quickSort(int first, int last) {
        void swap(int p1, int p2) {
            const int temp = a[p1];
            a[p1] = a[p2];
            a[p2] = temp;
        }
 
        int partition() {
            const int piv = a[first];
            int index = first;
            swap(index, last);
            for (int i = first; i < last; i++)
                if (a[i] < piv)
                    swap(index++, i);
            swap(index, last);
            return index;
        }
 
        if (first < last) {
            const int pivIndex = partition();
            quickSort(first, (pivIndex - 1));
            quickSort((pivIndex + 1), last);
        }
    }
    quickSort(0, size - 1);
}

Purpose

Nested functions are primarily used as helper functions or recursive functions inside a wrapper function, as in the quicksort example above; this can be direct recursion or, in more complex cases, mutual recursion. The nesting has the minor structural benefit of organizing the code and avoiding polluting the shared scope, and the significant benefit of allowing the functions to share state easily. In more detail, nested functions provide the following benefits:

• The nested function is lexically contained within the enclosing function, and thus visibly subsidiary to the enclosing function.
• The nested function is inaccessible outside the enclosing function, and thus does not pollute the shared scope (global or module).
• The nested function can access the local variables of the enclosing function, which are called "non-local variables" of the nested function. This allows sharing state without needing to pass parameters to the nested function or use a global variable.

Of these, the last is usually most significant, as it significantly simplifies code and speeds up execution compared to passing parameters.

As an organization matter, nested functions are a form of information hiding and are useful for dividing procedural tasks into subtasks which are only meaningful locally. This avoids avoids cluttering other parts of the program with functions and variables that are unrelated to those parts.

Other uses

Nested functions can also be used for unstructured control flow, by using the return statement for general unstructured control flow. This can be used for finer-grained control than is possible with other built-in features of the language – for example, it can allow early termination of a for loop if break is not available, or early termination of a nested for loop if a multi-level break or exceptions are not available.

In languages with nested functions, functions may normally also contain local constants, and types (in addition to local variables, parameters, and functions), encapsulated and hidden in the same nested manner. This may further enhance the code structuring possibilities.

Alternatives

The main alternative to nested functions is to use a separate module – place all the relevant functions and variables in a separate module, then only expose the top-level wrapper function publicly. This achieves the same encapsulation and sharing of state, though not the logical organization given by lexical nesting of functions, and comes at the cost of having a separate module, rather than including it in one file. In C this will generally be done by using static functions for encapsulation and static variables for communication.

Another alternative is to share state between the functions through function parameters, most often passing references as arguments to avoid the cost of copying. In C this is generally implemented by a pointer to a structure containing the context. This significantly increases the complexity of the function calls.

Languages

Well known languages supporting lexically nested functions include:

• ALGOL-based languages such as ALGOL 68, Simula, Pascal, Modula-2, Modula-3, Oberon, Seed7 and Ada.
• Modern versions of Lisp (with lexical scope) such as Scheme, and Common Lisp.
• ECMAScript (JavaScript, and ActionScript).
• Scala (full support)
• Various degrees of support in scripting languages such as Ruby, Python, and Perl (starting with version 6).
• Standard C and C++ do not support nested functions, but:
  • GCC supports nested functions in C, as a language extension.
  • The D language, which is C-related, has nested functions.
• Fortran, starting with Fortran-90, supports one level of nested (CONTAINed) subroutines and functions.

Functional languages

In most functional programming languages, such as Scheme, nested functions are a common way of implementing algorithms with loops in them. A simple (tail) recursive inner function is created, which behaves as the algorithm's main loop, while the outer function performs startup actions that only need to be done once. In more complex cases, a number of mutually recursive functions may be created as inner functions.

Some languages without direct support

Certain languages do not have straightforward syntactic and semantic support to implement nested functions. Nevertheless, for some of them the idea of nested functions can be simulated with some degree of difficulty through the use of other language constructs. The following languages can approximate nested functions through the respective strategies:

• C++ allows definition of classes within classes, providing the ability to use class methods in a way similar to nested functions in one level (see Function object in C++). C++11 additionally supports nested lambda functions.

• Eiffel explicitly disallows nesting of routines. This is to keep the language simple, and also allows the convention of using a special variable, Result, to denote the result of a (value-returning) function.

• Visual Basic and C#, by using anonymous methods or lambda expressions.

• Java, through a workaround that consists in an anonymous class containing a single method. A named class declared local to a method may also be used.

Implementation

See also: Man or boy test

Implementation of nested functions can be more involved than it may appear, as a reference to a nested function that references non-local variables creates a closure. For this reason nested functions are not supported in some languages such as C, as this makes compilers more difficult to implement.

There are several ways to implement nested procedures, but the classic way is as follows:

Any non-local object, X, is reached via access-links in the activation frames on the machine stack. The caller, C, assists the called procedure, P, by pushing a direct link to the latest activation of P's immediate lexical encapsulation, (P), prior to the call itself. P may then quickly find the right activation for a certain X by following a fixed number (P.depth - X.depth) of links (normally a small number).

The caller creates this direct link by (itself) following C.depth - P.depth + 1 older links, leading up to the latest activation of (P), and then temporarily bridging over these with a direct link to that activation; the link later disappears together with P, whereby the older links beneath it may come into use again.

Note that P is visible for, and may therefore be called by, C if (P) = C / (C) / ((C)) / etc.

This original method is faster than it may seem, but it is nevertheless often optimized in practical compilers (using displays or similar techniques).

Another way to implement nested functions that is used by some compilers is to convert ("lift") nested functions into non-nested functions (where extra parameters replace the access links) using a process known as lambda lifting during an intermediate stage in the compilation.

See also

• Call stack
• Closure (computer science)
• Inner class
• Nesting (computing)

References

• Bright, Walter (1 May 2004). "Nested Functions". Dr. Dobb's. 

External links

• comp.lang.c FAQ: Nested Functions
• "6.4 Nested procedure and functions". FreePascal documentation.