User:Ruud Koot/Nupedia/Functional Programming (brief version)

Also called Applicative Programming.

Functional programming is a programming methodology that treats computation as the evaluation of mathematical functions. A function in this sense has zero or more parameters and a single return value. The parameters--or arguments, as they are sometimes called--are the inputs to the function, and the return value is the function's output. The definition of a function describes how the function is to be evaluated in terms of other functions. For example, the function f(x) = x² + 2 is defined in terms of the power and addition functions. At some point, the language has to provide basic functions that require no further definition.

Functions can be manipulated in a variety of ways in a functional programming language. Functions are treated as first-class values, which is to say that functions can be parameters or inputs to other functions and can be the return values or outputs of a function. This allows functions like mapcar in LISP and map in Haskell that take both a function and a list as input and apply the input function to every element of the list. Functions can be named, as in other languages, or defined anonymously (sometimes during program execution) using a lambda abstraction and used as values in other functions. Functional languages also allow functions to be curried. Currying is a technique for rewriting a function with multiple parameters as the composition of functions of one parameter. The curried function can be applied to just a subset of its parameters. The result is a function where the parameters in this subset of are now fixed as constants, and the values of the rest of the parameters are still unspecified. This new function can be applied to the remaining parameters to get the final function value. For example, a function add(x,y) = x + y can be curried so that the return value of add(2)--notice that there is no y parameter--will be an anonymous function that is equivalent to a function add2(y) = 2 + y. This new function has only one parameter and corresponds to adding 2 to a number. Again, this is possible only because functions are treated as first class values.

Lambda calculus could be considered the first functional programming language, though it was never designed to actually be executed on a computer. Lambda calculus is a model of computation designed by Alonzo Church in the 1930s that provides a very formal way to describe function evaluation. The first computer-based functional programming language was LISP, developed by John McCarthy while at the Massachusetts Institute of Technology in the late 1950s. While not a purely functional programming language, LISP did introduce most of the features now found in modern functional programming languages. Scheme was a later attempt to simplify and improve LISP. In the 1970s the language ML was created at the University of Edinburgh, and David Turner developed the language Miranda at the University of Kent. The language Haskell was released in the late 1980s in an attempt to gather together many ideas in functional programming research.

Functional programming can be contrasted with imperative programming. Functional programming appears to be missing several constructs often (though incorrectly) considered essential to an imperative language, such as C or Pascal. For example, in strict functional programming, there is no explicit memory allocation and no explicit variable assignment. However, these operations occur automatically when a function is invoked; memory allocation occurs to make space for the parameters and the return value, and assignment occurs to copy the parameters into this newly allocated space and to copy the return value back into the calling function. Both operations can only occur on function entry and exit, so side effects of function evaluation are eliminated. By disallowing side effects in functions, the language provides referential transparency. This ensures that the result of a function will be the same for a given set of parameters no matter where, or when, it is evaluated. Referential transparency greatly eases both the task of proving program correctness and the task of automatically identifying independent computations for parallel execution.

Looping, another imperative programming construct, is accomplished through the more general functional construct of recursion. Recursive functions invoke themselves, allowing an operation to be performed over and over. In fact, it can be proven that looping is equivalent to a special type of recursion called tail recursion. Recursion in functional programming can take many forms and is in general a more powerful technique than looping. For this reason, almost all imperative languages also support it (with FORTRAN 77 and COBOL as notable exceptions).

For Further Reading

Cousineau, Guy and Michel Mauny. The Functional Approach to Programming. Cambridge, UK: Cambridge University Press, 1998.
Graham, Paul. ANSI Common LISP. Englewood Cliffs, New Jersey: Prentice Hall, 1996.
Hudak, Paul. "Conception, Evolution, and Application of Functional Programming Languages." ACM Computing Surveys 21, no. 3 (1989): 359-411.
Pratt, Terrence, W. and Marvin V. Zelkowitz. Programming Languages: Design and Implementation. 3rd ed. Englewood Cliffs, New Jersey: Prentice Hall, 1996.
Salus, Peter H. Functional and Logic Programming Languages. Vol. 4 of Handbook of Programming Languages. Indianapolis, Indiana: Macmillan Technical Publishing, 1998.
Thompson, Simon. Haskell: The Craft of Functional Programming. Harlow, England: Addison-Wesley Longman Limited, 1996.