Functional programming

Functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions. Functional programming emphasizes the definition of functions rather than the implementation of state machines, in contrast to procedural programming, which emphasizes the execution of sequential commands. A purely functional program does not use mutation: rather than modifying state to produce values (as is done in imperative programming), it constructs new values from (but does not overwrite) existing values.

There is no uniform agreement on what constitutes functional programming or a functional programming language. Often considered important are first-class functions (including anonymous functions), closures, and recursion. Other common features of functional programming languages are continuations, Hindley-Milner type systems, non-strict evaluation (i.e. "laziness") or explicit suspensions, and monads.

History

Lambda calculus, invented by Alonzo Church in the 1930s, provides a theoretical framework for describing functions and their evaluation. Though it is a mathematical abstraction rather than a programming language, lambda calculus forms the basis of almost all functional programming languages today.

The first computer-based functional programming language was Information Processing Language (IPL), developed by Newell, Shaw, and Simon at RAND Corporation for the JOHNNIAC computer in the mid- 1950s. A much-improved functional programming language was LISP, developed by John McCarthy while at MIT for the IBM 700/7000 series scientific computers in the late 1950s. LISP introduced many of the features now found in modern functional programming languages; Scheme was a later attempt to simplify and improve LISP.

In the 1970s the ML programming language was created by Robin Milner at the University of Edinburgh, and David Turner developed the language Miranda at the University of Kent. ML eventually developed into several dialects, the most common of which are now Objective Caml and Standard ML. The Haskell programming language was released in the late 1980s in an attempt to gather together many ideas in functional programming research.

Higher-order functions

A powerful mechanism used in functional programming is the notion of higher-order functions. Functions are higher-order when they can take other functions as arguments, and/or return functions as results. (The differential operator in calculus is a common example of a function that maps a function to a function.)

Higher-order functions are closely related to first-class functions, in that higher-order functions and first-class functions both allow functions as arguments and results of other functions. The distinction between the two is subtle: "higher-order" describes mathematical concept of functions that operate on other functions, while "first-class" refers to the incorporation of functions as expressions in a programming language.

Higher-order functions enable currying, a technique in which a function is applied to its arguments one at a time, with each application returning a new (higher-order) function that accepts the next argument.

Comparison with imperative programming

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 create 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.

Iteration (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 iteration 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 iteration. For this reason, almost all imperative languages also support it (with FORTRAN 77 and COBOL, before 2002, as notable exceptions).

Functional programming often depends heavily on recursion. The Scheme programming language even requires certain types of recursion ( tail recursion) to be recognized and automatically optimized by a compiler.

Pure functions

Purely functional programs have no side-effects. Since functions do not modify state, no data may be changed by parallel function calls. For this reason, pure functions are always thread-safe, a fact which is exploited by languages that use call-by-future evaluation. Because ordering of side-effects does not have to be preserved in their absence, some languages (such as Haskell) use call-by-need evaluation for pure functions.

"Pure" functional programming languages typically enforce referential transparency, which is the notion that 'equals can be substituted for equals': if two expressions have "equal" values (for some notion of equality), then one can be substituted for the other in any larger expression without affecting the result of the computation. For example, in

    y = f(x) * 

f(x);

a compiler can factor out f(x) if it is pure, transforming the program to

    z = f(x);
    y = z * 

z;

and eliminating the second evaluation of the (possibly costly) call to f(x).

This optimization is called common subexpression elimination.

However, if a function has effects, the function call cannot be eliminated. Consider the following program fragment:

    y = random() * 

random();

The second call to random cannot be eliminated, because its return value may be different from that of the first call (the random function is not idempotent).

Similarly,

    y = printf("x") * 

printf("x");

cannot be optimized away; even if printf returns the same value both times, failing to make the second call would result in different program output.

Many modern compilers for imperative programming languages do not perform common subexpression elimination for function calls, because they do not track whether a function is pure. It is possible for an advanced compiler to infer whether a local function has effects and optimize accordingly; however, most pre-compiled libraries do not expose this information, preventing calls to external functions from being optimized away. Some compilers, such as gcc, add extra keywords for a programmer to explicitly mark pure functions so that this optimization can be performed.

Monads

Some functional languages remove or sandbox side-effects during evaluation using monads. In such languages, all functions become "pure"; the program's evaluation can then be reasoned about using traditional mathematical techniques, and common-subexpression elimination can be performed on all function calls. Because monadic functions depend on the monad values produced by previous function calls, multiple calls still cannot be eliminated; however, their sequencing is made explicit in the program.

Alternative methods (such as Hoare logic) have been developed to track effects in programs. Some modern research languages use effect systems to make explicit the presence of effects.

Expansion of functional programming

Many programmers accustomed to the imperative paradigm find it difficult to learn functional programming, which encompasses a whole different way of composing programs. This difficulty, along with the fact that functional programming environments do not have the extensive tools and libraries available for traditional programming languages, are among the main reasons that functional programming has received little use in the software industry. Functional languages have remained largely the domain of academics and hobbyists, and what little inroads have been made are due to impure functional languages such as Erlang and Common Lisp. It could be argued that the largest influence of functional programming on the software industry has been by those academically trained programmers who have gone on to apply the impure functional programming style to their work in traditional imperative languages.

Speed and space considerations

Functional languages have long been criticised as resource-hungry, both in terms of CPU resources and memory. This was mainly due to two factors:

• some early functional languages were implemented with little concern for efficiency
• non-functional languages achieved speed in part by leaving out features such as bounds checking and garbage collection which are considered by many to be important parts of modern computing frameworks; these features are included in most functional languages

As modern imperative languages and their implementations have started to emphasize correctness rather than raw speed, the implementations of functional languages have begun to emphasize speed as well as correctness; as a result, the performance of functional languages and imperative languages has begun to converge. For programs which perform intensive numerical computations, some functional languages (such as OCaml and Clean) can approach the speed of C, while for programs that handle large matrices and multidimensional databases, array functional languages (such as J and K) are usually faster than most non-optimized C programs^{[ citation needed]}. However, purely functional languages can be considerably slower when manipulating large data structures, due to less efficient memory usage.

Memory usage can be improved in some functional programs by using persistent data structures; these data structures allow part or all of their data to be shared with other values, making copying and modifying relatively inexpensive. This can be done safely because these data structures are immutable, so the usual problems with pointer aliasing in imperative data structures do not arise. Among the commonly used persistent data structures are linked lists and binary trees.

The use of persistent data structures for data that is discarded increases the amount of garbage collection that must occur and decreases the available memory between collection cycles; for this reason, some programs achieve faster performance using mutable data structures. Because modifying memory addresses may be more efficient than allocating new data structures, implementations of "pure" languages often also contain monads for mutable data structures.

The competitive performance of modern (impure) functional programming languages such as OCaml and SML has resulted in their adoption in conventionally Fortran-dominated areas of scientific computation. Thanks to the brevity, expressiveness and availability of sophisticated data structures and algorithms, functional languages are now used in a wide range of scientific applications, from numerical analysis to visualisation^{[ citation needed]}.

Functional languages

The first computer-based functional programming language was Information Processing Language (IPL) from the RAND corporation. Another very old functional language is Lisp, though neither the original LISP nor modern Lisps such as Common Lisp are pure-functional. Some Lisp variants include Scheme, Dylan, and Logo (though Logo is an imperative language). The modern canonical examples are Haskell and members of the ML family including SML and OCaml. Others include Erlang, Clean, and Miranda. A third type of a commonly used functional language is XSLT. Another subset is the mathematics languages Maple and Mathematica.

Some computer languages, for example Tcl, Perl, Python & Ruby, can also be used in a functional style, since they have higher-order functions, abstractions and such.

Efforts are underway to develop quantum functional programming languages, to express quantum algorithms, and further the development of this field. Examples of these are Peter Selinger's influential QPL, described in his paper Towards a quantum programming language, and the Haskell-like language QML.

Category:Functional languages provides an exhaustive list.