In
computer programming
Computer programming or coding is the composition of sequences of instructions, called computer program, programs, that computers can follow to perform tasks. It involves designing and implementing algorithms, step-by-step specifications of proc ...
, a nested function (or nested procedure or subroutine) is a
named function that is defined within another, enclosing, block and is
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 ...
within the enclosing block meaning it is only callable by name within the body of the enclosing block and can use
identifiers
An identifier is a name that identifies (that is, labels the identity of) either a unique object or a unique ''class'' of objects, where the "object" or class may be an idea, person, physical countable object (or class thereof), or physical mass ...
declared in outer
blocks, including outer functions. The enclosing block is typically, but not always, another function.
Programming language
A programming language is a system of notation for writing computer programs.
Programming languages are described in terms of their Syntax (programming languages), syntax (form) and semantics (computer science), semantics (meaning), usually def ...
support for nested functions varies. With respect to
structured programming Structured programming is a programming paradigm aimed at improving the clarity, quality, and development time of a computer program by making specific disciplined use of the structured control flow constructs of selection ( if/then/else) and repet ...
languages, it is supported in some outdated languages such as
ALGOL
ALGOL (; short for "Algorithmic Language") is a family of imperative computer programming languages originally developed in 1958. ALGOL heavily influenced many other languages and was the standard method for algorithm description used by the ...
,
Simula 67 and
Pascal and in the commonly used
JavaScript
JavaScript (), often abbreviated as JS, is a programming language and core technology of the World Wide Web, alongside HTML and CSS. Ninety-nine percent of websites use JavaScript on the client side for webpage behavior.
Web browsers have ...
. It is commonly supported in
dynamic and
functional languages.
However, it is not supported in some commonly used languages including standard
C and
C++.
Other programming technologies provide similar benefit. For example, a
lambda 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.
Attributes
The
scope 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 use
identifiers
An identifier is a name that identifies (that is, labels the identity of) either a unique object or a unique ''class'' of objects, where the "object" or class may be an idea, person, physical countable object (or class thereof), or physical mass ...
(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 a
closure. If it is possible for the nested function to
escape 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
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 block in ...
s referenced in closures can therefore not be
stack allocated in languages that allow the closure to persist beyond the lifetime of the enclosing block. 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.
Value
The nested function technology allows a
programmer
A programmer, computer programmer or coder is an author of computer source code someone with skill in computer programming.
The professional titles Software development, ''software developer'' and Software engineering, ''software engineer' ...
to write
source code
In computing, source code, or simply code or source, is a plain text computer program written in a programming language. A programmer writes the human readable source code to control the behavior of a computer.
Since a computer, at base, only ...
that includes beneficial attributes such as
information hiding
In computer science, information hiding is the principle of segregation of the ''design decisions'' in a computer program that are most likely to change, thus protecting other parts of the program from extensive modification if the design decisio ...
,
encapsulation and
decomposition
Decomposition is the process by which dead organic substances are broken down into simpler organic or inorganic matter such as carbon dioxide, water, simple sugars and mineral salts. The process is a part of the nutrient cycle and is ess ...
. 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 passing
parameters or using
global variable
In computer programming, a global variable is a variable with global scope, meaning that it is visible (hence accessible) throughout the program, unless shadowed. The set of all global variables is known as the ''global environment'' or ''global ...
s.
Uses
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
In computer science, control flow (or flow of control) is the order in which individual statements, instructions or function calls of an imperative program are executed or evaluated. The emphasis on explicit control flow distinguishes an '' ...
, 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
In computer science, a for-loop or for loop is a control flow Statement (computer science), statement for specifying iteration. Specifically, a for-loop functions by running a section of code repeatedly until a certain condition has been satisfi ...
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.
[Higher-Order Functions and Lambdas - Kotlin Programming Language](_blank)
/ref>
Examples
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
Standard ML (SML) is a General-purpose programming language, general-purpose, High-level programming language, high-level, Modular programming, modular, Functional programming, functional programming language with compile-time type checking and t ...
:
fun e (x : real) =
let
fun f y = x+y
in
f 3 + f 4
end;
In Haskell
Haskell () is a general-purpose, statically typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research, and industrial applications, Haskell pioneered several programming language ...
:
e :: Float -> Float
e x = f 3 + f 4 where f y = x + y
In PL/I
PL/I (Programming Language One, pronounced and sometimes written PL/1) is a procedural, imperative computer programming language initially developed by IBM. It is designed for scientific, engineering, business and system programming. It has b ...
:
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 which extends standard C with nested functions:
float E(float x)
Quicksort
The following is an implementation of quicksort
Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 and published in 1961. It is still a commonly used algorithm for sorting. Overall, it is slightly faster than ...
:
void sort(int *items, int size)
The following is an implementation of the Hoare partition based quicksort using C++11
C++11 is a version of a joint technical standard, ISO/IEC 14882, by the International Organization for Standardization (ISO) and International Electrotechnical Commission (IEC), for the C++ programming language. C++11 replaced the prior vers ...
lambda expression syntax which is an alternative technology that also allows hiding a function inside a function:
template
auto Sort(RandomAccessIterator Begin, RandomAccessIterator End)->void
Languages
Notable languages supporting nested functions include:
*ALGOL
ALGOL (; short for "Algorithmic Language") is a family of imperative computer programming languages originally developed in 1958. ALGOL heavily influenced many other languages and was the standard method for algorithm description used by the ...
-based languages such as ALGOL 68
ALGOL 68 (short for ''Algorithmic Language 1968'') is an imperative programming language member of the ALGOL family that was conceived as a successor to the ALGOL 60 language, designed with the goal of a much wider scope of application and ...
, 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 AL ...
, Pascal, 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
Modula-3 is a programming language conceived as a successor to an upgraded version of Modula-2 known as Modula-2+. It has been influential in research circles (influencing the designs of languages such as Java, C#, Python and Nim), but it ha ...
, Oberon
Oberon () is a king of the fairy, fairies in Middle Ages, medieval and Renaissance literature. He is best known as a character in William Shakespeare's play ''A Midsummer Night's Dream'', in which he is King of the Fairies and spouse of Titania ...
, PL/I
PL/I (Programming Language One, pronounced and sometimes written PL/1) is a procedural, imperative computer programming language initially developed by IBM. It is designed for scientific, engineering, business and system programming. It has b ...
, 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 Languag ...
and Ada
*Modern versions of Lisp
Lisp (historically LISP, an abbreviation of "list processing") is a family of programming languages with a long history and a distinctive, fully parenthesized Polish notation#Explanation, prefix notation.
Originally specified in the late 1950s, ...
(with lexical scope) such as Scheme, and Common Lisp
Common Lisp (CL) is a dialect of the Lisp programming language, published in American National Standards Institute (ANSI) standard document ''ANSI INCITS 226-1994 (S2018)'' (formerly ''X3.226-1994 (R1999)''). The Common Lisp HyperSpec, a hyperli ...
*ECMAScript
ECMAScript (; ES) is a standard for scripting languages, including JavaScript, JScript, and ActionScript. It is best known as a JavaScript standard intended to ensure the interoperability of web pages across different web browsers. It is stan ...
(JavaScript
JavaScript (), often abbreviated as JS, is a programming language and core technology of the World Wide Web, alongside HTML and CSS. Ninety-nine percent of websites use JavaScript on the client side for webpage behavior.
Web browsers have ...
and ActionScript
ActionScript is an object-oriented programming language originally developed by Macromedia Inc. (later acquired by Adobe). It is influenced by HyperTalk, the scripting language for HyperCard. It is now an implementation of ECMAScript (mean ...
)
* Dart
* Kotlin (local functions)
*Rust
Rust is an iron oxide, a usually reddish-brown oxide formed by the reaction of iron and oxygen in the catalytic presence of water or air moisture. Rust consists of hydrous iron(III) oxides (Fe2O3·nH2O) and iron(III) oxide-hydroxide (FeO(OH) ...
* Scala (nested functions)
*Various degrees of support in scripting languages such as Ruby
Ruby is a pinkish-red-to-blood-red-colored gemstone, a variety of the mineral corundum ( aluminium oxide). Ruby is one of the most popular traditional jewelry gems and is very durable. Other varieties of gem-quality corundum are called sapph ...
, Python, Lua, PHP
PHP is a general-purpose scripting language geared towards web development. It was originally created by Danish-Canadian programmer Rasmus Lerdorf in 1993 and released in 1995. The PHP reference implementation is now produced by the PHP Group. ...
and Perl
Perl is a high-level, general-purpose, interpreted, dynamic programming language. Though Perl is not officially an acronym, there are various backronyms in use, including "Practical Extraction and Reporting Language".
Perl was developed ...
* 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
MATLAB (an abbreviation of "MATrix LABoratory") is a proprietary multi-paradigm programming language and numeric computing environment developed by MathWorks. MATLAB allows matrix manipulations, plotting of functions and data, implementat ...
(full support)
*Wolfram Language
The Wolfram Language ( ) is a proprietary, very high-level multi-paradigm programming language developed by Wolfram Research. It emphasizes symbolic computation, functional programming, and rule-based programming and can employ arbitrary stru ...
* Golang (Function closures)
Functional languages
In most functional programming
In computer science, functional programming is a programming paradigm where programs are constructed by Function application, applying and Function composition (computer science), composing Function (computer science), functions. It is a declarat ...
languages, such as Scheme, nested functions are a common way of implementing algorithm
In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
s with loops in them. A simple (tail
The tail is the elongated section at the rear end of a bilaterian animal's body; in general, the term refers to a distinct, flexible appendage extending backwards from the midline of the torso. In vertebrate animals that evolution, evolved to los ...
) recursive
Recursion occurs when the definition of a concept or process depends on a simpler or previous version of itself. Recursion is used in a variety of disciplines ranging from linguistics to logic. The most common application of recursion is in m ...
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.
Alternatives
Various alternative techniques can be used to achieve similar programming results as via nested 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.[Question 20.24: Why doesn't C have nested functions?]
comp.lang.c FAQ This allows for data hiding, encapsulation and decomposition, but at a different level of granularity
Granularity (also called graininess) is the degree to which a material or system is composed of distinguishable pieces, "granules" or "grains" (metaphorically).
It can either refer to the extent to which a larger entity is subdivided, or the ...
than with nested functions. This modularity does not support more than one level of nesting.
In object-oriented languages
Object-oriented programming (OOP) is a programming paradigm based on the concept of '' objects''. Objects can contain data (called fields, attributes or properties) and have actions they can perform (called procedures or methods and impleme ...
, 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.
In C, this is generally implemented by passing a pointer to a structure containing the shared data.
Lambda
In PHP
PHP is a general-purpose scripting language geared towards web development. It was originally created by Danish-Canadian programmer Rasmus Lerdorf in 1993 and released in 1995. The PHP reference implementation is now produced by the PHP Group. ...
and other languages, the lambda
Lambda (; uppercase , lowercase ; , ''lám(b)da'') is the eleventh letter of the Greek alphabet, representing the voiced alveolar lateral approximant . In the system of Greek numerals, lambda has a value of 30. Lambda is derived from the Phoen ...
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
C++11 is a version of a joint technical standard, ISO/IEC 14882, by the International Organization for Standardization (ISO) and International Electrotechnical Commission (IEC), for the C++ programming language. C++11 replaced the prior vers ...
and later via lambda expressions (see quicksort example above)
* 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 Visual Basic is a name for a family of programming languages from Microsoft. It may refer to:
* Visual Basic (.NET), the current version of Visual Basic launched in 2002 which runs on .NET
* Visual Basic (classic), the original Visual Basic suppo ...
via lambda expressions
*Java
Java is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea (a part of Pacific Ocean) to the north. With a population of 156.9 million people (including Madura) in mid 2024, proje ...
since Java 8, via lambda expressions, and in older versions, via an anonymous class containing a single method
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 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, 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 (subroutine) into a global function. It is a tw ...
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 ...
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
Memory management (also dynamic memory management, dynamic storage allocation, or dynamic memory allocation) is a form of resource management applied to computer memory. The essential requirement of memory management is to provide ways to dyna ...
. 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 causes a loss of no-execute stacks (NX stacks). This implementation calls nested functions through a jump 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 using Secure Development Lifecycle often do not allow the use of nested functions in this particular compiler due to the loss of NX stacks.
See also
*Call stack
In computer science, a call stack is a Stack (abstract data type), stack data structure that stores information about the active subroutines and block (programming), inline blocks of a computer program. This type of stack is also known as an exe ...
*Closure (computer science)
In programming languages, a closure, also lexical closure or function closure, is a technique for implementing lexically scoped name binding in a language with first-class functions. Operationally, a closure is a record storing a function to ...
*Function composition (computer science)
In computer science, function composition is an act or mechanism to combine simple functions to build more complicated ones. Like the usual composition of functions in mathematics, the result of each function is passed as the argument of the ne ...
*Inner class In object-oriented programming (OOP), an inner class or nested class is a class declared entirely within the body of another class or interface. It is distinguished from a subclass.
Overview
An instance of a normal or top-level class can exist on ...
*Nesting (computing)
In computing science and informatics, nestinghttps://study.com/academy/lesson/nesting-loops-stan C Programming is where information is organized in layers, or where objects contain other similar objects. It almost always refers to self-similar ...
References
*
{{refend
External links
comp.lang.c FAQ: Nested Functions
FreePascal documentation.
Source code
Subroutines