Incomputer programming, anested function (ornested procedure orsubroutine) is anamedfunction that is defined within another, enclosing, block and islexically scoped within the enclosing block – meaning it is only callable by name within the body of the enclosing block and can useidentifiers declared in outerblocks, including outer functions. The enclosing block is typically, but not always, another function.
Programming language support for nested functions varies. With respect tostructured programming languages, it is supported in some outdated languages such asALGOL,Simula 67 andPascal and in the commonly usedJavaScript. It is commonly supported indynamic andfunctional languages.However, it is not supported in some commonly used languages including standardC andC++.
Other programming technologies provide similar benefit. For example, alambda function also allows for a function to be defined inside of a function (as well as elsewhere) and allows for similar data hiding and encapsulation. Notably, a lambda function has no name (is anonymous) and therefore cannot be called by name and has no visibility aspect.
Thescope of a nested function is the block that contains it – be it a function block or block within a function body. It is not visible (cannot be called by name) outside its containing block.
A nested function can useidentifiers (i.e. the name of functions, variables, types, classes) declared in any enclosing block, except when they are masked by inner declarations with the same names.
A nested function can be declared within a nested function, recursively, to form a deeply nested structure. A deeply nested function can access identifiers declared in all of its enclosing blocks, including enclosing functions.
Nested functions may in certain situations lead to the creation of aclosure. If it is possible for the nested function toescape the enclosing function, for example if functions arefirst class objects and a nested function is passed to another function or returned from the enclosing function, then a closure is created and calls to this function can access the environment of the original function. The frame of the immediately enclosing function must continue to be alive until the last referencing closure dies andnon-localautomatic variables referenced in closures can therefore not bestack allocated in languages that allow the closure to persist beyond the lifetime of the enclosing block. This is known as thefunarg problem and is a key reason why nested functions was not implemented in some simpler languages as it significantly complicates code generation and analysis, especially when functions are nested to various levels, sharing different parts of their environment.
The nested function technology allows aprogrammer to writesource code that includes beneficial attributes such asinformation hiding,encapsulation anddecomposition. The programmer can divide a task into subtasks which are only meaningful within the context of the task such that the subtask functions are hidden from callers that are not designed to use them.
Block scoping allows functions to share the state of enclosing blocks (including enclosing functions) without passingparameters or usingglobal variables.[1]
A nested function typically acts as ahelper function or arecursive function.
Nested functions can be used for unstructuredcontrol 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 ifbreak is not available, or early termination of a nestedfor loop if a multi-levelbreak or exceptions are not available.
In some languages, it is possible to create a nested function that accesses a set of parameters from the outer function, that is aclosure, 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]
A simple example in Pascal:
functionE(x:real):real;functionF(y:real):real;beginF:=x+yend;beginE:=F(3)+F(4)end;
The functionF is nested withinE. Note thatE's parameterx is also visible inF (asF is a part ofE) while bothx andy are invisible outsideE andF respectively.
Similarly, inStandard ML:
fune(x:real)=letfunfy=x+yinf3+f4end;
InHaskell:
e::Float->Floatex=f3+f4wherefy=x+y
InPL/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;
InPython:
defe(x:float)->float:deff(y:float)->float:returnx+yreturnf(3.0)+f(4.0)
InGNU C[3] – which extends standard C with nested functions:
floatE(floatx){floatF(floaty){returnx+y;}returnF(3)+F(4);}
The following is an implementation ofquicksort:[4]
voidsort(int*items,intsize){voidquickSort(intfirst,intlast){voidswap(intp,intq){inttmp=items[p];items[p]=items[q];items[q]=tmp;}intpartition(){intpivot=items[first],index=first;swap(index,last);for(inti=first;i<last;i++)if(items[i]<pivot)swap(index++,i);swap(index,last);returnindex;}if(first<last){intpivotIndex=partition();quickSort(first,pivotIndex-1);quickSort(pivotIndex+1,last);}}quickSort(0,size-1);}
The following is an implementation of theHoare partition based quicksort usingC++11lambda expression syntax which is an alternative technology that also allows hiding a function inside a function:
template<typenameRandomAccessIterator>autoSort(RandomAccessIteratorBegin,RandomAccessIteratorEnd)->void{autoPartition=[&](){//Hoare partition schemeauto&Pivot=*Begin;autoForwardCursor=Begin;autoBackwardCursor=End-1;autoPartitionPositionFound=false;autoLocatePartitionPosition=[&](){while(*ForwardCursor<Pivot)++ForwardCursor;while(Pivot<*BackwardCursor)--BackwardCursor;if(ForwardCursor>=BackwardCursor)PartitionPositionFound=true;elseSwap(*ForwardCursor,*BackwardCursor);};//Trivial helper functionautoMoveOnAndTryAgain=[&](){++ForwardCursor;--BackwardCursor;};//Brief outline of the actual partition processwhile(true){LocatePartitionPosition();if(PartitionPositionFound)returnBackwardCursor+1;elseMoveOnAndTryAgain();}};//Brief outline of the quicksort algorithmif(Begin<End-1){autoPartitionPosition=Partition();Sort(Begin,PartitionPosition);Sort(PartitionPosition,End);}}
Notable languages supporting nested functions include:
In mostfunctional programming languages, such as Scheme, nested functions are acommon way of implementingalgorithms 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.
Various alternative techniques can be used to achieve similar programming results as via nested functions.
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 asstatic to hide them from code outside the file.[10] This allows for data hiding, encapsulation and decomposition, but at a different level ofgranularity than with nested functions. This modularity does not support more than one level of nesting.
Inobject-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.
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]
InPHP and other languages, thelambda 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 afunction reference. Such functions can be defined inside of a function as well as in other scopes. To use local variables in the anonymous function, useclosure.
The following languages provide features that are similar to nested functions:
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 aclosure. For this reason nested functions are not supported in some languages such as C, C++ or Java as this makes compilers more difficult to implement.[10][13] However, some compilers do support them, as a compiler specific extension. A well known example of this is theGNU C implementation of C which shares code with compilers for languages such as Pascal, Ada and Modula.
There are several ways to implement nested procedures in a lexically scoped language, but the classic way is as follows:
This original method is faster than it may seem, but it is nevertheless often optimized in practical modern compilers (usingdisplays 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 aslambda lifting during an intermediate stage in the compilation.
In order for local functions withlexically scopednonlocals 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 freelydynamic 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.
GCC's implementation of nested functions causes a loss ofno-executestacks (NX stacks). This implementation calls nested functions through ajump instruction placed on the machine stack at runtime. This requires the stack to be executable. No-execute stacks and nested functions are therefore mutually exclusive in GCC. If a nested function is used in the development of a program, then the NX stack is silently lost, unless GCC is called with the‑Wtrampoline option to alert of the condition. Software engineered usingSecure Development Lifecycle often do not allow the use of nested functions in this particular compiler due to the loss of NX stacks.[15]