Nested function - AbsoluteAstronomy.com

Computer programming

Computer programming is the process of designing, writing, testing, debugging, and maintaining the source code of computer programs. This source code is written in one or more programming languages. The purpose of programming is to create a program that performs specific operations or exhibits a...

, a nested function (or nested procedure/subroutine) is a function

Subroutine

In computer science, a subroutine is a portion of code within a larger program that performs a specific task and is relatively independent of the remaining code....

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

Scope (programming)

In computer programming, scope is an enclosing context where values and expressions are associated. Various programming languages have various types of scopes. The type of scope determines what kind of entities it can contain and how it affects them—or semantics...

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
GNU Compiler Collection
The GNU Compiler Collection is a compiler system produced by the GNU Project supporting various programming languages. GCC is a key component of the GNU toolchain...

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

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 decision is changed...

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

Constant (programming)

In computer programming, a constant is an identifier whose associated value cannot typically be altered by the program during its execution...

, and types

Data type

In computer programming, a data type is a classification identifying one of various types of data, such as floating-point, integer, or Boolean, that determines the possible values for that type; the operations that can be done on values of that type; the meaning of the data; and the way values of...

(in addition to local variables

Variable (programming)

In computer programming, a variable is a symbolic name given to some known or unknown quantity or information, for the purpose of allowing the name to be used independently of the information it represents...

, parameter

Parameter

Parameter from Ancient Greek παρά also “para” meaning “beside, subsidiary” and μέτρον also “metron” meaning “measure”, can be interpreted in mathematics, logic, linguistics, environmental science and other disciplines....

s, 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
ALGOL
ALGOL is a family of imperative computer programming languages originally developed in the mid 1950s which greatly influenced many other languages and became the de facto way algorithms were described in textbooks and academic works for almost the next 30 years...

-based languages such as ALGOL 68
ALGOL 68
ALGOL 68 isan imperative computerprogramming language that was conceived as a successor to theALGOL 60 programming language, designed with the goal of a...

, Simula
Simula
Simula is a name for two 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...

, Pascal
Pascal (programming language)
Pascal is an influential imperative and procedural programming language, designed in 1968/9 and published in 1970 by Niklaus Wirth as a small and efficient language intended to encourage good programming practices using structured programming and data structuring.A derivative known as Object Pascal...

, Modula-2
Modula-2
Modula-2 is a computer programming language designed and developed between 1977 and 1980 by Niklaus Wirth at ETH Zurich as a revision of Pascal to serve as the sole programming language for the operating system and application software for the personal workstation Lilith...

, Modula-3
Modula-3
In computer science, Modula-3 is a programming language conceived as a successor to an upgraded version of Modula-2 known as Modula-2+. While it has been influential in research circles it has not been adopted widely in industry...

, Oberon
Oberon (programming language)
Oberon is a programming language created in 1986 by Professor Niklaus Wirth and his associates at ETH Zurich in Switzerland. It was developed as part of the implementation of the Oberon operating system...

and Ada
Ada (programming language)
Ada is a structured, statically typed, imperative, wide-spectrum, and object-oriented high-level computer programming language, extended from Pascal and other languages...

.
Modern versions of Lisp (with lexical scope) such as Scheme, and Common Lisp
Common Lisp
Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived for use with web browsers...

.
ECMA Script (JavaScript
JavaScript
JavaScript is a prototype-based scripting language that is dynamic, weakly typed and has first-class functions. It is a multi-paradigm language, supporting object-oriented, imperative, and functional programming styles....

, and ActionScript
ActionScript
ActionScript is an object-oriented language originally developed by Macromedia Inc. . It is a dialect of ECMAScript , and is used primarily for the development of websites and software targeting the Adobe Flash Player platform, used on Web pages in the form of...

).
Full support in Scala
Various degrees of support in scripting languages such as Ruby
Ruby (programming language)
Ruby is a dynamic, reflective, general-purpose object-oriented programming language that combines syntax inspired by Perl with Smalltalk-like features. Ruby originated in Japan during the mid-1990s and was first developed and designed by Yukihiro "Matz" Matsumoto...

, Python
Python (programming language)
Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...

, and Perl
Perl 6
Perl 6 is a major revision to the Perl programming language. It is still in development, as a specification from which several interpreter and compiler implementations are being written. It is introducing elements of many modern and historical languages. Perl 6 is intended to have many...

(starting with version 6).
There is also a C
C (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....

-related language with nested functions, the D
D (programming language)
The D programming language is an object-oriented, imperative, multi-paradigm, system programming language created by Walter Bright of Digital Mars. It originated as a re-engineering of C++, but even though it is mainly influenced by that language, it is not a variant of C++...

language.
GCC
GNU Compiler Collection
The GNU Compiler Collection is a compiler system produced by the GNU Project supporting various programming languages. GCC is a key component of the GNU toolchain...

also supports nested functions in C, as a language extension.
Fortran
Fortran
Fortran is a general-purpose, procedural, imperative programming language that is especially suited to numeric computation and scientific computing...

, starting with Fortran-90, supports one level of nested (CONTAINed) subroutines and functions.

Functional languages

In most functional programming

Functional programming

In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...

languages, such as Scheme, nested functions are a common way

Programming idiom

A programming idiom is a means of expressing a recurring construct in one or more programming languages. Generally speaking, a programming idiom is an expression of a simple task or algorithm that is not a built-in feature in the programming language being used, or, conversely, the use of an...

of implementing algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

s with loops in them. A simple (tail) recursive

Recursion

Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...

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++
C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...

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
Visual Basic .NET
Visual Basic .NET , is an object-oriented computer programming language that can be viewed as an evolution of the classic Visual Basic , which is implemented on the .NET Framework...

and C#, by using anonymous methods or lambda expressions.

Java
Java (programming language)
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...

, 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

Call stack

In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, control stack, run-time stack, or machine stack, and is often shortened to just "the stack"...

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

Call stack

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

Lambda lifting

Lambda lifting or closure conversion is the process of eliminating free variables from local function definitions from a computer program. The elimination of free variables allows the compiler to hoist local definitions out of their surrounding contexts into a fixed set of top-level functions with...

during an intermediate stage in the compilation.

External links

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

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.