Nested function

Helper

A nested function typically acts as a helper function or a recursive function.

Control flow

Nested functions can 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.

Higher-order functions

In some languages, it is possible to create a nested function that accesses a set of parameters from the outer function, that is a closure, and have that function be the outer function's return value. Thus it is possible to return a function that is set to fulfill a certain task with little or no further parameters given to it, which can increase performance quite significantly.^[2]

Simple example

A simple example in Pascal:

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

The function F is nested within E. Note that E's parameter x is also visible in F (as F is a part of E) while both x and y are invisible outside E and F respectively.

Similarly, in Standard ML:

fun e (x : real) =
  let
    fun f y = x+y
  in
    f 3 + f 4
  end;

In Haskell:

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

In PL/I:

e: procedure(x) returns(float);
  declare x float;
  f: procedure(y) returns(float);
    declare y float;
    return x + y
    end;
  return f(3.0) + f(4.0);
  end;

In Python:

def e(x: float) -> float:
    def f(y: float) -> float:
        return x + y
    return f(3.0) + f(4.0)

In GNU C^[3] – which extends standard C with nested functions:

float e(float x) {
    float f(float y) {
        return x + y;
    }
    return f(3.0f) + f(4.0f);
}

Quicksort

The following is an implementation of quicksort:^[4]

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];
            int 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);
}

The following is an implementation of the Hoare partition based quicksort using C++11 lambda expression syntax which is an alternative technology that also allows hiding a function inside a function:

// Iter represents a random access iterator
template <typename Iter>
void sort(Iter begin, Iter end) {
	auto partition = [&]() -> Iter {
		// Hoare partition scheme
		Iter& pivot = *begin;
		Iter forwardCursor = begin;
		Iter backwardCursor = end - 1;
		Iter partitionPositionFound = false;

		auto locatePartitionPosition = [&]() -> void {
			while (*forwardCursor < pivot) {
				++forwardCursor;
            }
			while (pivot < *backwardCursor) {
				--backwardCursor;
            }
			if (forwardCursor >= backwardCursor) {
				partitionPositionFound = true;
			} else
				swap(*forwardCursor, *backwardCursor);
            }
		};

		// Trivial helper function
		auto moveOnAndTryAgain = [&]() -> void {
			++forwardCursor;
			--backwardCursor;
		};

		// Brief outline of the actual partition process
		while (true) {
			locatePartitionPosition();
			if (partitionPositionFound)
				return backwardCursor + 1;
			else {
				moveOnAndTryAgain();
            }
		}
	};

	// Brief outline of the quicksort algorithm
	if (begin < end - 1) {
		Iter partitionPosition = partition();
		sort(begin, partitionPosition);
		sort(partitionPosition, end);
	}
}

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.

Modularity

A common alternative is to leverage a language's modularity technology. Some functions are exposed for use outside of the module and some are only visible within the module.

In C, this can be implemented by declaring functions and variables as static to hide them from code outside the file.^[10] This allows for data hiding, encapsulation and decomposition, but at a different level of granularity than with nested functions. This modularity does not support more than one level of nesting.

In object-oriented languages, a class typically provides a scope in which functions and state can be hidden from consumers of the class but accessible within the class. Some languages allow classes to be nested.

Parameters

To implement data hiding, functions can pass around shared data as parameters, but this increases the complexity of function calls.^[1]

In C, this is generally implemented by passing a pointer to a structure containing the shared data.^[10]

Lambda

In PHP and other languages, the lambda is an alternative. A function is defined in a code statement rather than declared with the usual function syntax. It has no name but is callable via a function reference. Such functions can be defined inside of a function as well as in other scopes. To use local variables in the anonymous function, use closure.

Alternatives by language

The following languages provide features that are similar to nested functions:

• C++ – classes allow for similar data hiding and encapsulation; defining a class within a class provides similar structure (see Function object in C++)

• C++11 and later – via lambda expressions (see quicksort example above)^[11]

• Eiffel – explicitly disallows nesting of routines to keep the language simple; does allow the convention of using a special variable, Result, to denote the result of a (value-returning) function

• C# and Visual Basic – via lambda expressions

• Java – since Java 8, via lambda expressions^[12], and in older versions, via an anonymous class containing a single method

Access of non-local objects

There are several ways to implement nested procedures in a lexically scoped language, 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 modern 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, hidden, parameters replace the access links) using a process known as lambda lifting during an intermediate stage in the compilation.

Functions as values

In order for local functions with lexically scoped nonlocals to be passed as results, the language runtime code must also implicitly pass the environment (data) that the function sees inside its encapsulating function, so that it is reachable also when the current activation of the enclosing function no longer exists.^[14] This means that the environment must be stored in another memory area than (the subsequently reclaimed parts of) a chronologically based execution stack, which, in turn, implies some sort of freely dynamic memory allocation. Many older Algol based languages (or dialects thereof) does therefore not allow local functions that access nonlocals to be passed as return values, or do they not allow functions as return values at all, although passing of such functions as arguments may still be possible.

No-execute stacks

GCC's implementation of nested functions in C causes a loss of no-execute stacks (NX stacks). Therefore, software engineered using Secure Development Lifecycle often do not allow the use of GCC's nested functions.^[15] By default, GCC will issue a brief notification when a generated object file requires an executable stack. For a clear warning when compiling C code, use the ‑Wtrampolines option.

The problem occurs because GCC uses "trampolines" (executable code on the stack) to jump to nested functions .^[16] The GCC project has an alternative method that could provide nested functions via non-executable descriptors, however it is currently only used in GCC's Ada compiler.