Development/Common

First-class citizen, First-class function

linuxism 2015. 6. 29. 16:13

First-class citizen

From Wikipedia, the free encyclopedia

For the usage in society, see Second-class citizen.

In programming language design, a first-class citizen (also object, entity, or value) in a given programming language is an entity which supports all the operations generally available to other entities. These operations typically include being passed as a parameter, returned from a function, and assigned to a variable.^[1]

[hide]

History[edit]

The concept of first- and second- class objects was introduced by Christopher Strachey in the 1960s.^[2]^[3] He did not actually define the term strictly, but contrasted real numbers and procedures in Algol:

First and second class objects. In Algol, a real number may appear in an expression or be assigned to a variable, and either may appear as an actual parameter in a procedure call. A procedure, on the other hand, may only appear in another procedure call either as the operator (the most common case) or as one of the actual parameters. There are no other expressions involving procedures or whose results are procedures. Thus in a sense procedures in Algol are second class citizens—they always have to appear in person and can never be represented by a variable or expression (except in the case of a formal parameter)... ^[4]

During the 1990s, Raphael Finkel^[5] proposed definitions of second and third class values, but these definitions have not been widely adopted.^[6]

Examples[edit]

The simplest scalar data types, such as integer and floating-point numbers, are nearly always first-class.

In many older languages, arrays and strings are not first-class: they cannot be assigned as objects or passed as parameters to a subroutine. For example, neither Fortran IV nor C supports array assignment, and when they are passed as parameters, only the position of their first element is actually passed -- their size is lost. C appears to support assignment of array pointers, but in fact these are simply pointers to the array's first element, and again do not carry the array's size.

In most languages, data types are not first-class objects, though in some object-oriented languages classes are first-class objects, and used for metaclasses.

Few languages support continuations and GOTO-labels as objects at all, let alone as first-class objects.

Concept	Description	Languages
first-class function	closures	Scheme, ML, Haskell, F#, Scala, Swift
first-class control	continuations	Scheme, ML, F#
first-class type		Coq
first-class data type		Generic Haskell
first-class polymorphism	impredicative polymorphism
first-class message	dynamic messages (method calls)	Smalltalk,^[7] Objective-C^[7]
first-class class	metaclass	Smalltalk, Objective-C, Ruby, Python
	proof object^[8]	Coq, Agda

Functions[edit]

Main article: First-class functions

Many programming languages support passing and returning function values, which can be applied to arguments. Whether this suffices to call function values first-class is disputed.

Some authors require it be possible to create new functions at runtime to call them 'first-class'. As a result, functions in C are not first-class objects; instead, they are sometimes called second-class objects, because they can still be manipulated in most of the above fashions (via function pointers).

In Smalltalk, functions (methods) are first-class objects, just like Smalltalk classes. Since Smalltalk operators (+, -, etc.) are methods, they are also first-class objects.

Reflection[edit]

Main article: Reflection (computer programming)

Some languages, such as Java, have an explicit reflection subsystems which allow access to internal implementation structures even though they are not accessible or manipulable in the same way as ordinary objects.

References[edit]

Jump up^ Scott, Michael (2006). Programming Language Pragmatics. San Francisco, CA: Morgan Kaufmann Publishers. p. 140.
Jump up^ Rod Burstall, "Christopher Strachey—Understanding Programming Languages", Higher-Order and Symbolic Computation 13:52 (2000)
Jump up^ Harold Abelson and Gerald Jay Sussman, Structure and Interpretation of Computer Programs, 2nd edition, section 1.3.4 footnote 64
Jump up^ Christopher Strachey, "Fundamental Concepts in Programming Languages" in Higher-Order and Symbolic Computation 13:11 (2000); though published in 2000, these are notes from lectures Strachey delivered in August, 1967
Jump up^ Finkel, R. Advanced Programming language Design, p 73
Jump up^ Norman Ramsey. "About first-,second- and third-class value". http://stackoverflow.com. Retrieved 14 September 2013.
^ Jump up to:^a ^b Paritosh Shroff, Scott F. Smith. Type Inference for First-Class Messages with Match-Functions
Jump up^ Bove, Ana; Dybjer, Peter (2009). "Dependent Types at Work" (PDF). Language Engineering and Rigorous Software Development 5520: 57–99. doi:10.1007/978-3-642-03153-3_2. Retrieved 8 June 2015. (also [archived])

First-class function

In computer science, a programming language is said to have first-class functions if it treats functions as first-class citizens. Specifically, this means the language supports passing functions as arguments to other functions, returning them as the values from other functions, and assigning them to variables or storing them in data structures.^[1] Some programming language theorists require support for anonymous functions(function literals) as well.^[2] In languages with first-class functions, the names of functions do not have any special status; they are treated like ordinary variables with a function type.^[3] The term was coined byChristopher Strachey in the context of “functions as first-class citizens” in the mid-1960s.^[4]

First-class functions are a necessity for the functional programming style, in which the use of higher-order functions is a standard practice. A simple example of a higher-ordered function is the map function, which takes, as its arguments, a function and a list, and returns the list formed by applying the function to each member of the list. For a language to support map, it must support passing a function as an argument.

There are certain implementation difficulties in passing functions as arguments and returning them as results, especially in the presence of non-local variables introduced in nested and anonymous functions. Historically, these were termed the funarg problems, the name coming from "function argument".^[5] In early imperative languages these problems were avoided by either not supporting functions as result types (e.g. ALGOL 60, Pascal) or omitting nested functions and thus non-local variables (e.g. C). The early functional language Lisp took the approach of dynamic scoping, where non-local variables refer to the closest definition of that variable at the point where the function is executed, instead of where it was defined. Proper support for lexically scoped first-class functions was introduced in Scheme and requires handling references to functions as closures instead of bare function pointers,^[4] which in turn makes garbage collection a necessity.

[hide]

Concepts[edit]

In this section we compare how particular programming idioms are handled in a functional language with first-class functions (Haskell) compared to an imperative language where functions are second-class citizens (C).

Higher-order functions: passing functions as arguments[edit]

Further information: Higher-order function

In languages where functions are first-class citizens, functions can be passed as arguments to other functions in the same way as other values (a function taking another function as argument is called a higher-order function). In the language Haskell:

map :: (a -> b) -> [a] -> [b]
map f []     = []
map f (x:xs) = f x : map f xs

Languages where functions are not first-class often still allow one to write higher-order functions through the use of features such as function pointers or delegates. In the language C:

void map(int (*f)(int), int x[], size_t n) {
    for (int i = 0; i < n; i++)
        x[i] = f(x[i]);
}

When comparing the two samples, one should note that there are a number of differences between the two approaches that are not directly related to the support of first-class functions. The Haskell sample operates on lists, while the C sample operates on arrays. Both are the most natural compound data structures in the respective languages and making the C sample operate on linked lists would have made it unnecessarily complex. This also accounts for the fact that the C function needs an additional parameter (giving the size of the array.) The C function updates the array in-place, returning no value, whereas in Haskell data structures are persistent (a new list is returned while the old is left intact.) The Haskell sample uses recursion to traverse the list, while the C sample uses iteration. Again, this is the most natural way to express this function in both languages, but the Haskell sample could easily have been expressed in terms of a fold and the C sample in terms of recursion. Finally, the Haskell function has a polymorphic type, as this is not supported by C we have fixed all type variables to the type constant int.

Anonymous and nested functions[edit]

Further information: Anonymous function and Nested function

In languages supporting anonymous functions, we can pass such a function as an argument to a higher-order function:

main = map (\x -> 3 * x + 1) [1, 2, 3, 4, 5]

In a language which does not support anonymous functions, we have to bind it to a name instead:

int f(int x) {
    return 3 * x + 1;
}

int main() {
    int list[] = {1, 2, 3, 4, 5};
    map(f, list, 5);
}

Non-local variables and closures[edit]

Further information: Non-local variable and Closure (computer science)

Once we have anonymous or nested functions, it becomes natural for them to refer to variables outside of their body (called non-local variables):

main = let a = 3
           b = 1
        in map (\x -> a * x + b) [1, 2, 3, 4, 5]

If functions are represented with bare function pointers, it is no longer obvious how we should pass the value outside of the function body to it. We instead have to manually build a closure and one can at this point no longer speak of "first-class" functions.

typedef struct {
    int (*f)(int, int, int);
    int *a;
    int *b;
} closure_t;

void map(closure_t *closure, int x[], size_t n) {
    for (int i = 0; i < n; ++i)
        x[i] = (*closure->f)(*closure->a, *closure->b, x[i]);
}

int f(int a, int b, int x) {
    return a * x + b;
}

void main() {
    int l[] = {1, 2, 3, 4, 5};
    int a = 3;
    int b = 1;
    closure_t closure = {f, &a, &b};
    map(&closure, l, 5);
}

Also note that the map is now specialized to functions referring to two ints outside of their environment. This can be set up more generally, but requires more boilerplate code. If f would have been a nested function we would still have run into the same problem and this is the reason they are not supported in C.^[6]

Higher-order functions: returning functions as results[edit]

When returning a function, we are in fact returning its closure. In the C example any local variables captured by the closure will go out of scope once we return from the function that builds the closure. Forcing the closure at a later point will result in undefined behaviour, possibly corrupting the stack. This is known as the upwards funarg problem.

Assigning functions to variables[edit]

Assigning functions to variables and storing them inside (global) datastructures potentially suffers from the same difficulties as returning functions.

f :: [[Integer] -> [Integer]]
f = let a = 3
        b = 1
     in [map (\x -> a * x + b), map (\x -> b * x + a)]

Equality of functions[edit]

Further information: Function equality

As one can test most literals and values for equality, it is natural to ask whether a programming language can support testing functions for equality. On further inspection, this question appears more difficult and one has to distinguish between several types of function equality:^[7]

Extensional equality: Two functions f and g are considered extensionally equal if they agree on their outputs for all inputs (∀x. f(x) = g(x)). Under this definition of equality, for example, any two implementations of a stable sorting algorithm, such as insertion sort and merge sort, would be considered equal. Deciding on extensional equality is undecidable in general and even for functions with finite domains often intractable. For this reason no programming language implements function equality as extensional equality.

Intensional equality: Under intensional equality, two functions f and g are considered equal if they have the same "internal structure". This kind of equality could be implemented in interpreted languages by comparing the source code of the function bodies (such as in Interpreted Lisp 1.5) or the object code in compiled languages. Intensional equality implies extensional equality (under the assumption that the functions do not depend on the value of the program counter.)

Reference equality: Given the impracticality of implementing extensional and intensional equality, most languages supporting testing functions for equality use reference equality. All functions or closures are assigned a unique identifier (usually the address of the function body or the closure) and equality is decided based on equality of the identifier. Two separately defined, but otherwise identical function definitions will be considered unequal. Referential equality implies intensional and extensional equality. Referential equality breaks referential transparency and is therefore not supported in pure languages, such as Haskell.

Type theory[edit]

Main article: Function type

In type theory, the type of functions accepting values of type A and returning values of type B may be written as A → B or B^A. In the Curry-Howard correspondence, function types are related to logical implication; lambda abstraction corresponds to discharging hypothetical assumptions and function application corresponds to the modus ponens inference rule. Besides the usual case of programming functions, type theory also uses first-class functions to model associative arrays and similar data structures.

In category-theoretical accounts of programming, the availability of first-class functions corresponds to the closed category assumption. For instance, the simply typed lambda calculus corresponds to the internal language of cartesian closed categories.

Language support[edit]

Functional programming languages, such as Scheme, ML, Haskell, F#, and Scala, all have first-class functions. When Lisp, one of the earliest functional languages, was designed, not all aspects of first-class functions were then properly understood, resulting in functions being dynamically scoped. The later Common Lisp dialect does have lexically scoped first-class functions.

Many scripting languages, including Perl, Python, PHP, Lua, Tcl/Tk, JavaScript and Io, have first-class functions.

For imperative languages, a distinction has to be made between Algol and its descendants such as Pascal, the traditional C family, and the modern garbage-collected variants. The Algol family has allowed nested functions and higher-order taking function as arguments, but not higher-order functions that return functions as results (except Algol 68, which allows this). The reason for this was that it was not known how to deal with non-local variables if a nested-function was returned as a result (and Algol 68 produces runtime errors in such cases).

The C family allowed both passing functions as arguments and returning them as results, but avoided any problems by not supporting nested functions. (The gcc compiler allows them as an extension.) As the usefulness of returning functions primarily lies in the ability to return nested functions that have captured non-local variables, instead of top-level functions, these languages are generally not considered to have first-class functions.

Modern imperative languages often support garbage-collection making the implementation of first-class functions feasible. First-class function have often only been supported in later revisions of the language, including C# 2.0 and Apple's Blocks extension to C, C++ and Objective-C. C++11 has added support for anonymous functions and closures to the language, but because of the non-garbage collected nature of the language, special care has to be taken for non-local variables in functions to be returned as results (see below).

Language		Higher-order functions		Non-local variables			Partial application	Notes
Language		Arguments	Results	Nested functions	Anonymous functions	Closures	Partial application	Notes
Algol family	ALGOL 60	Yes	No	Yes	No	No	No	Have function types.
	ALGOL 68	Yes	Yes^[8]	Yes	Yes	No	No
	Pascal	Yes	No	Yes	No	No	No
	Oberon	Yes	Non-nested only	Yes	No	No	No
	Delphi	Yes	Yes	Yes	2009	2009	No
C family	C	Yes	Yes	No	No	No	No	Has function pointers.
	C++	Yes	Yes	C++11 closures^[9]	C++11^[10]	C++11^[10]	C++11	Has function pointers, function objects. (Also, see below.) Explicit partial application possible with `std::bind`.
	C#	Yes	Yes	Partial	2.0 / 3.0	2.0	3.0	Has delegates (2.0) and lambda expressions (3.0).
	Go	Yes	Yes	Yes	Yes	Yes	No
	Objective-C	Yes	Yes	No	2.0 + Blocks^[11]	2.0 + Blocks	No	Has function pointers.
	Java	Partial	Partial	No	Java 8	Java 8	No	Has anonymous inner classes.
	Limbo	Yes	Yes	Yes	Yes	Yes	No
	Newsqueak	Yes	Yes	Yes	Yes	Yes	No
	Rust	Yes	Yes	Yes	Yes	Yes	No
Functional languages	Lisp	Syntax	Syntax	Yes	Yes	Common Lisp	No	(see below)
	Scheme	Yes	Yes	Yes	Yes	Yes	SRFI 26^[12]
	Clojure	Yes	Yes	Yes	Yes	Yes	Yes
	ML	Yes	Yes	Yes	Yes	Yes	Yes
	Haskell	Yes	Yes	Yes	Yes	Yes	Yes
	Scala	Yes	Yes	Yes	Yes	Yes	Yes
Scripting languages	JavaScript	Yes	Yes	Yes	Yes	Yes	ECMAScript 5	Partial application possible with user-land code on ES3 ^[13]
	PHP	Yes	Yes	5.3 closures	5.3 closures	5.3 closures	No	Partial application possible with user-land code.
	Perl	Yes	Yes	anonymous, 6	Yes	Yes	6^[14]	(see below)
	Python	Yes	Yes	Yes	Partial	Yes	2.5^[15]	(see below)
	Ruby	Syntax	Syntax	Unscoped	Yes	Yes	1.9	(see below)
Other languages	Io	Yes	Yes	Yes	Yes	Yes	No
	Maple	Yes	Yes	Yes	Yes	Yes	No
	Mathematica	Yes	Yes	Yes	Yes	Yes	No
	MATLAB	Yes	Yes	Yes	Yes^[16]	Yes	Yes	Partial application possible by automatic generation of new functions.^[17]
	Smalltalk	Yes	Yes	Yes	Yes	Yes	Partial	Partial application possible through library.
	Fortran	Yes	Yes	Yes	No	No	No
	Swift	Yes	Yes	Yes	Yes	Yes	Yes
	Ada	Yes	Yes	Yes	No	Downward Closure	No

C++: C++11 closures can capture non-local variables by reference (without extending their lifetime), by copy construction or by move construction (the variable lives as long as the closure does). The former potentially avoids an expensive copy and allows to modify the original variable but is unsafe in case the closure is returned (see dangling references). The second is safe if the closure is returned but requires a copy and cannot be used to modify the original variable (which might not exist any more at the time the closure is called). The later is safe if the closure is returned and does not require a copy but cannot be used to modify the original variable either.
Java: Java 8 closures can only capture immutable ("effectively final") non-local variables. There are no function types in Java; in Java 8, anonymous functions take the type inferred from the context, which must be a "functional interface" (an interface with one method).
Lisp: Lexically scoped Lisp variants support closures. Dynamically scoped variants do not support closures or need a special construct to create closures.^[18]; In Common Lisp, the identifier of a function in the function namespace cannot be used as a reference to a first-class value. The special operator function must be used to retrieve the function as a value:(function foo) evaluates to a function object. #'foo exists as a shorthand notation. To apply such a function object, one must use the funcall function: (funcall #'foo bar baz).
Perl: Perl 5 only allows anonymous functions to be nested.
Python: Python's anonymous functions can only have an expression as the body.; Explicit partial application with functools.partial since version 2.5, and operator.methodcaller since version 2.6.
Ruby: The identifier of a regular "function" in Ruby (which is really a method) cannot be used as a value or passed. It must first be retrieved into a Method or Proc object to be used as first-class data. The syntax for calling such a function object differs from calling regular methods.; Nested method definitions do not actually nest the scope.; Explicit currying with [1].

Notes[edit]

Jump up^ Abelson, Harold; Sussman, Gerald Jay (1984). Structure and Interpretation of Computer Programs. MIT Press. Section 1.3 Formulating Abstractions with Higher-Order Procedures. ISBN 0-262-01077-1.
Jump up^ Programming language pragmatics, by Michael Lee Scott, section 11.2 "Functional Programming".
Jump up^ Roberto Ierusalimschy; Luiz Henrique de Figueiredo; Waldemar Celes. "The Implementation of Lua 5.0" (PDF).
^ Jump up to:^a ^b Burstall, Rod; Strachey, Christopher (2000). "Understanding Programming Languages" (PDF).Higher-Order and Symbolic Computation 13 (52): 11–49. doi:10.1023/A:1010052305354. (also [archived] on 2010-02-16
Jump up^ Joel Moses. "The Function of FUNCTION in LISP, or Why the FUNARG Problem Should be Called the Environment Problem". MIT AI Memo 199, 1970.
Jump up^ "If you try to call the nested function through its address after the containing function has exited, all hell will break loose." (GNU Compiler Collection: Nested Functions)
Jump up^ Andrew W. Appel (1995). "Intensional Equality ;=) for Continuations".
Jump up^ Tanenbaum, A.S. (1977). "A comparison of PASCAL and Algol 68" (PDF). The Computer Journal21 (4): 319. doi:10.1093/comjnl/21.4.316.
Jump up^ Nested functions using lambdas/closures
^ Jump up to:^a ^b Doc No. 1968: V Samko; J Willcock, J Järvi, D Gregor, A Lumsdaine (February 26, 2006)Lambda expressions and closures for C++
Jump up^http://developer.apple.com/mac/library/documentation/Cocoa/Conceptual/Blocks/Articles/00_Introduction.html
Jump up^ http://srfi.schemers.org/srfi-26/srfi-26.html
Jump up^ http://ejohn.org/blog/partial-functions-in-javascript/
Jump up^ http://perlgeek.de/blog-en/perl-5-to-6/28-currying.html
Jump up^ https://docs.python.org/whatsnew/2.5.html#pep-309-partial-function-application
Jump up^ http://www.mathworks.co.uk/help/matlab/matlab_prog/anonymous-functions.html
Jump up^ http://stackoverflow.com/questions/9154271/partial-function-evaluation-in-matlab
Jump up^ Closures in ZetaLisp

References[edit]

Leonidas Fegaras. "Functional Languages and Higher-Order Functions". CSE5317/CSE4305: Design and Construction of Compilers. University of Texas at Arlington.

External links[edit]

source - https://en.wikipedia.org/wiki/First-class_citizen

https://en.wikipedia.org/wiki/First-class_function

저작자표시

티스토리