nested functions
   HOME

TheInfoList



OR:

In computer programming, a nested function (or nested procedure or subroutine) is a function which is defined within another function, the ''enclosing function''. Due to simple recursive
scope Scope or scopes may refer to: People with the surname * Jamie Scope (born 1986), English footballer * John T. Scopes (1900–1970), central figure in the Scopes Trial regarding the teaching of evolution Arts, media, and entertainment * Cinem ...
rules, a nested function is itself invisible outside of its immediately enclosing function, but can see (access) all local
objects Object may refer to: General meanings * Object (philosophy), a thing, being, or concept ** Object (abstract), an object which does not exist at any particular time or place ** Physical object, an identifiable collection of matter * Goal, an ...
(data, functions, types, etc.) of its immediately enclosing function as well as of any function(s) which, in turn, encloses that function. The nesting is theoretically possible to unlimited depth, although only a few levels are normally used in practical programs. Nested functions are used in many approaches to
structured programming Structured programming is a programming paradigm aimed at improving the clarity, quality, and development time of a computer program by making extensive use of the structured control flow constructs of selection ( if/then/else) and repetition ( ...
, including early ones, such as ALGOL,
Simula 67 Simula is the name of two simulation programming languages, Simula I and Simula 67, developed in the 1960s at the Norwegian Computing Center in Oslo, by Ole-Johan Dahl and Kristen Nygaard. Syntactically, it is an approximate superset of ALGOL ...
and
Pascal Pascal, Pascal's or PASCAL may refer to: People and fictional characters * Pascal (given name), including a list of people with the name * Pascal (surname), including a list of people and fictional characters with the name ** Blaise Pascal, Fren ...
, and also in many modern
dynamic language In computer science, a dynamic programming language is a class of high-level programming languages, which at runtime execute many common programming behaviours that static programming languages perform during compilation. These behaviors cou ...
s and functional languages. However, they are traditionally not supported in the (originally simple)
C-family Due to the success of the C programming language ''The C Programming Language'' (sometimes termed ''K&R'', after its authors' initials) is a computer programming book written by Brian Kernighan and Dennis Ritchie, the latter of whom original ...
of languages.


Effects

Nested functions assumes function scope or block scope. The scope of a nested function is inside the enclosing function, i.e. inside one of the constituent blocks of that function, which means that it is invisible outside that block and also outside the enclosing function. A nested function can access other local functions, variables, constants, types, classes, etc. that are in the same scope, or in any enclosing scope, without explicit parameter passing, which greatly simplifies passing data into and out of the nested function. This is typically allowed for both reading and writing. Nested functions may in certain situations (and languages) lead to the creation of a closure. If it is possible for the nested function to
escape Escape or Escaping may refer to: Computing * Escape character, in computing and telecommunication, a character which signifies that what follows takes an alternative interpretation ** Escape sequence, a series of characters used to trigger some so ...
the enclosing function, for example if functions are first 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 and non-local
automatic variable __NOTOC__ In computer programming, an automatic variable is a local variable which is allocated and deallocated automatically when program flow enters and leaves the variable's scope. The scope is the lexical context, particularly the function or b ...
s referenced in closures can therefore not be stack allocated. This is known as the funarg 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.


Examples

An example using Pascal syntax (with ALGOL,
Modula 2 Modula-2 is a structured, procedural programming language developed between 1977 and 1985/8 by Niklaus Wirth at ETH Zurich. It was created as the language for the operating system and application software of the Lilith personal workstation ...
, Oberon,
Ada Ada may refer to: Places Africa * Ada Foah, a town in Ghana * Ada (Ghana parliament constituency) * Ada, Osun, a town in Nigeria Asia * Ada, Urmia, a village in West Azerbaijan Province, Iran * Ada, Karaman, a village in Karaman Province, Tur ...
, etc. similar): 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 visible also 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; 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 same example in
GNU C The GNU Compiler Collection (GCC) is an optimizing compiler produced by the GNU Project supporting various programming languages, hardware architectures and operating systems. The Free Software Foundation (FSF) distributes GCC as free software ...
syntax (C extended with nested functions): float E(float x)


Quicksort

A more realistic example is this implementation of quicksort: void sort(int *items, int size) Another example is the following implementation of the Hoare partition based quicksort using C++11 lambda expression syntax: template auto Sort(RandomAccessIterator Begin, RandomAccessIterator End)->void


Purpose

Lexically nested function definitions are a form of information hiding and are useful for dividing procedural tasks into subtasks which are only meaningful locally. This avoids cluttering other parts of the program with functions and variables that are unrelated to those parts. They are typically used as helper functions or as recursive functions inside another function (as in the quicksort example above). This has the structural benefit of organizing the code, avoids polluting the scope, and also allows functions to share state easily. As nested function can access local variables of the enclosing function, sharing of state is possible without passing parameters to the nested function or use a global variable, simplifying code. In languages with nested functions, functions may normally also contain local
constants Constant or The Constant may refer to: Mathematics * Constant (mathematics), a non-varying value * Mathematical constant, a special number that arises naturally in mathematics, such as or Other concepts * Control variable or scientific const ...
, and types (in addition to local variables, parameters, and functions), encapsulated and hidden in the same nested manner, at any level of depth. This may further enhance the code structuring possibilities.


Other uses


Control flow

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.


Higher-order functions

As in most languages functions are valid return types, it is possible to create a nested function that accesses a set of parameters from the outer function 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.Higher-Order Functions and Lambdas - Kotlin Programming Language
/ref>


Alternatives

The main alternative to nested functions in languages that lack support for them is to place all relevant functions and variables in a separate module (file) and expose only the top-level wrapper function publicly. In C this will generally be done by using static functions for encapsulation and static variables for communication.Question 20.24: Why doesn't C have nested functions?
comp.lang.c FAQ
This achieves 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 file. It is also not possible in more than a single level. 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. In PHP and other languages the
anonymous function In computer programming, an anonymous function (function literal, lambda abstraction, lambda function, lambda expression or block) is a function definition that is not bound to an identifier. Anonymous functions are often arguments being passed to ...
is the only alternative: the nested function is declared not as usual function, but by reference, as a local variable. To use local variables in the anonymous function, use closure.


Languages

Well known languages supporting lexically nested functions include: * ALGOL-based languages such as ALGOL 68,
Simula Simula is the name of two simulation programming languages, Simula I and Simula 67, developed in the 1960s at the Norwegian Computing Center in Oslo, by Ole-Johan Dahl and Kristen Nygaard. Syntactically, it is an approximate superset of ALGOL 6 ...
,
Pascal Pascal, Pascal's or PASCAL may refer to: People and fictional characters * Pascal (given name), including a list of people with the name * Pascal (surname), including a list of people and fictional characters with the name ** Blaise Pascal, Fren ...
,
Modula-2 Modula-2 is a structured, procedural programming language developed between 1977 and 1985/8 by Niklaus Wirth at ETH Zurich. It was created as the language for the operating system and application software of the Lilith personal workstation. It w ...
, Modula-3, Oberon,
Seed7 Seed7 is an extensible general-purpose programming language designed by Thomas Mertes. It is syntactically similar to Pascal and Ada. Along with many other features, it provides an extension mechanism. Daniel Zingaro"Modern Extensible Languages" ...
and
Ada Ada may refer to: Places Africa * Ada Foah, a town in Ghana * Ada (Ghana parliament constituency) * Ada, Osun, a town in Nigeria Asia * Ada, Urmia, a village in West Azerbaijan Province, Iran * Ada, Karaman, a village in Karaman Province, Tur ...
*Modern versions of
Lisp A lisp is a speech impairment in which a person misarticulates sibilants (, , , , , , , ). These misarticulations often result in unclear speech. Types * A frontal lisp occurs when the tongue is placed anterior to the target. Interdental lisping ...
(with lexical scope) such as
Scheme A scheme is a systematic plan for the implementation of a certain idea. Scheme or schemer may refer to: Arts and entertainment * ''The Scheme'' (TV series), a BBC Scotland documentary series * The Scheme (band), an English pop band * ''The Schem ...
, and
Common Lisp Common Lisp (CL) is a dialect of the Lisp programming language, published in ANSI standard document ''ANSI INCITS 226-1994 (S20018)'' (formerly ''X3.226-1994 (R1999)''). The Common Lisp HyperSpec, a hyperlinked HTML version, has been derived fro ...
* ECMAScript ( JavaScript and ActionScript) *
Dart Dart or DART may refer to: * Dart, the equipment in the game of darts Arts, entertainment and media * Dart (comics), an Image Comics superhero * Dart, a character from ''G.I. Joe'' * Dart, a ''Thomas & Friends'' railway engine character * Dar ...
* Kotlin (local functions) * Scala (nested functions) *Various degrees of support in scripting languages such as Ruby, Python,
Lua Lua or LUA may refer to: Science and technology * Lua (programming language) * Latvia University of Agriculture * Last universal ancestor, in evolution Ethnicity and language * Lua people, of Laos * Lawa people, of Thailand sometimes referred t ...
, PHP and Perl * GCC supports nested functions in C, as a language extension. * C#, starting with C# 7.0 *The D language, a C-related language with nested functions. * Fortran, starting with Fortran-90, supports ''a single level'' of nested (''CONTAINed'') subroutines and functions. * MATLAB (full support) * Wolfram Language


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++ **before C++11: 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++). **since C++11: by using lambda expressions as the quicksort example above. *
Eiffel Eiffel may refer to: Places * Eiffel Peak, a summit in Alberta, Canada * Champ de Mars – Tour Eiffel station, Paris, France; a transit station Structures * Eiffel Tower, in Paris, France, designed by Gustave Eiffel * Eiffel Bridge, Ungheni, M ...
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, by using anonymous methods or lambda expressions. * Java, by using lambda expressions (see Anonymous functions in Java) (since Java 8) or 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

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, C++ or Java as this makes compilers more difficult to implement. However, some compilers do support them, as a compiler specific extension. A well known example of this is the
GNU C The GNU Compiler Collection (GCC) is an optimizing compiler produced by the GNU Project supporting various programming languages, hardware architectures and operating systems. The Free Software Foundation (FSF) distributes GCC as free software ...
implementation of C which shares code with compilers for languages such as Pascal, Ada and Modula.


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 In programming language theory, a non-local variable is a variable that is not defined in the local scope. While the term can refer to global variables, it is primarily used in the context of nested and anonymous functions where some variables can ...
, 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 Lambda lifting is a meta-process that restructures a computer program so that functions are defined independently of each other in a global scope. An individual "lift" transforms a local function into a global function. It is a two step process, ...
during an intermediate stage in the compilation.


Functions as values

In order for local functions with
lexically scoped In computer programming, the scope of a name binding (an association of a name to an entity, such as a variable) is the part of a program where the name binding is valid; that is, where the name can be used to refer to the entity. In other parts o ...
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. 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

At least one implementation of nested functions cause a loss of No-execute stacks (NX stack). GCC's nested function implementation calls nested functions through a jump instruction put in the machine stack at runtime. This requires the stack to be executable. No execute stacks and nested functions are mutually exclusive under GCC. If a nested function is used in the development of a program, then the NX Stack is silently lost. GCC offers the -Wtrampoline warning to alert of the condition. Software engineered using Secure Development Lifecycle often do not allow the use of nested functions in this particular compiler (GCC) due to the loss of NX Stacks.


See also

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


Notes


References

* {{refend


External links


comp.lang.c FAQ: Nested Functions


FreePascal documentation. Source code Subroutines