Nested function

Nested function definitions can be compared to how a Matryoshka doll nests within larger versions of itself, in several levels.

In computer programming, a nested function (or nested procedure/subroutine) is a function which is lexically (textually) encapsulated within another function. It can only be called by the enclosing function or by functions directly or indirectly nested within the same enclosing function. In other words, the scope of the nested function is limited by the enclosing function. The nesting is theoretically possible to any level of depth, although only a few levels are normally used in practice.

An example

An example using Pascal syntax:

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

and the same example in GNU C syntax:

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

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

Purpose

Nested functions are a form of information hiding and are useful for dividing procedural tasks into sub tasks which are only meaningful locally; it avoids cluttering other parts of the program with functions, variables, etc. unrelated to those parts. Nested functions therefore complement other structuring possibilities such as records and objects.

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.

Languages

Well known languages supporting lexically nested functions include:

• ALGOL-based languages such as ALGOL 68, Simula, Pascal, Modula-2, Modula-3, Oberon and Ada.
• Modern versions of Lisp (with lexical scope) such as Scheme, and Common Lisp.
• ECMA Script (JavaScript, and ActionScript).
• Full support in Scala
• Various degrees of support in scripting languages such as Ruby, Python, and Perl (starting with version 6).
• There is also a C-related language with nested functions, the D language.
• GCC also supports nested functions in C, as a language extension.^[1]
• 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++).

• 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

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

1. ^ "Nested Functions - Using the GNU Compiler Collection (GCC)". GNU Project. http://gcc.gnu.org/onlinedocs/gcc/Nested-Functions.html. Retrieved 2007-01-06. 

External links

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