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.

The lambda calculus provides the model for functional programming. Modern functional languages can be viewed as embellishments to the lambda calculus.

While not fully functional, both the original Lisp and APL were important in the development of functional programming. Later versions of Lisp such as Scheme and variants of APL did provide full functional support. Other important functional languages include Erlang, Haskell, and ML.

Functional programming languages, especially purely functional ones, have largely been emphasized in academia rather than in commercial software development. However, notable functional programming languages used in industry and commercial applications include Erlang, OCaml, Haskell, Scheme (since 1986) and domain-specific programming languages like R (statistics), Mathematica (symbolic math), J and K (financial analysis), and XSLT (XML).

Many non-functional programming languages such as C, C++ and C# can be made to exhibit functional behaviors using function pointers, the <functional> library and lambda functions respectively.

History

Lambda calculus provides a theoretical framework for describing functions and their evaluation. Although it is a mathematical abstraction rather than a programming language, it forms the basis of almost all functional programming languages today.

Combinatory logic is an equivalent theoretical foundation, developed by Moses Schönfinkel and Haskell Curry. It was originally developed to achieve a clearer approach to the foundations of mathematics. Combinatory logic is commonly perceived as more abstract than lambda calculus and preceded it in invention.

An early functional-flavored 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 features now found in functional languages, though LISP is technically a multi-paradigm language. Scheme and Dylan were later attempts to simplify and improve LISP.

Information Processing Language (IPL) is sometimes cited as the first computer-based functional programming language. It is an assembly-style language for manipulating lists of symbols. It does have a notion of "generator", which amounts to a function accepting a function as an argument, and, since it is an assembly-level language, code can be used as data, so IPL can be regarded as having higher-order functions. However, it relies heavily on mutating list structure and similar imperative features.

Kenneth E. Iverson developed the APL programming language in the early 1960s, described in his 1962 book A Programming Language (ISBN 9780471430148). APL was the primary influence on John Backus's FP programming language. In the early 1990s, Iverson and Roger Hui created a successor to APL, the J programming language. In the mid 1990s, Arthur Whitney, who had previously worked with Iverson, created the K programming language, which is used commercially in financial industries.

John Backus presented the FP programming language in his 1977 Turing Award lecture Can Programming Be Liberated From the von Neumann Style? A Functional Style and its Algebra of Programs. He defines functional programs as being built up in a hierarchical way by means of "combining forms" that allow an "algebra of programs"; in modern language, this means that functional programs follow the principle of compositionality. Backus's paper popularized research into functional programming, though it emphasized function-level programming rather than the lambda-calculus style which has come to be associated with functional programming.

In the 1970s the ML programming language was created by Robin Milner at the University of Edinburgh, and David Turner developed initially the language SASL at the University of St. Andrews and later 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.

In 2008, Microsoft Research is adding F#, a functional language, to their .NET platform.

Concepts

A number of concepts and paradigms are specific to functional programming, and generally foreign to imperative programming (including object oriented programming). However, programming languages are often hybrids of several programming paradigms so programmers using "mostly imperative" languages may have utilized some of these concepts.

Higher-order functions

Functions are higher-order when they can take other functions as arguments, and return them as results. (The derivative and antiderivative in calculus are examples of this.)

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 a mathematical concept of functions that operate on other functions, while "first-class" is a computer science term that describes programming language entities that have no restriction on their use (thus first-class functions can appear anywhere in the program that other first-class entities like numbers can, including as arguments to other functions and as their return values).

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 function that accepts the next argument.

Pure functions

Purely functional functions (or expressions) have no memory or I/O side effects, unless the computation of the result in itself is counted as a side-effect. This means that pure functions have several useful properties, many of which can be used to optimize the code:

• If the result of a pure expression is not used, it can be removed without affecting other expressions.
• If a pure function is called with parameters that cause no side-effects, the result is constant with respect to that parameter list (sometimes called referential transparency), i.e. if the pure function is again called with the same parameters, the same result will be returned (this can enable caching optimisations).
• If there is no data dependency between two pure expressions, then their order can be reversed, or they can be performed in parallel and they cannot interfere with one another (in other terms, the evaluation of any pure expression is thread-safe).
• If the entire language does not allow side-effects, then any evaluation strategy can be used; this gives the compiler freedom to reorder or combine the evaluation of expressions in a program (for example, using lazy evaluation).

While most compilers for imperative programming languages detect pure functions, and perform common-subexpression elimination for pure function calls, they cannot always do this for pre-compiled libraries, which generally do not expose this information, thus preventing optimisations that involve those external functions. Some compilers, such as gcc, add extra keywords for a programmer to explicitly mark external functions as pure, to enable such optimisations. Fortran 95 allows functions to be designated "pure".

Recursion

Main article: Recursion (computer science)

Iteration (looping) in functional languages is usually accomplished via recursion. Recursive functions invoke themselves, allowing an operation to be performed over and over. Recursion may require maintaining a stack, but tail recursion can be recognized and optimized by a compiler into the same code used to implement iteration in imperative languages. The Scheme programming language standard requires implementations to recognize and optimize tail recursion.

Common patterns of recursion can be factored out using higher order functions, catamorphisms and anamorphisms (or "folds" and "unfolds") being the most obvious examples. Such higher order functions play a role analogous to built-in control structures such as loops in imperative languages.

Strict versus non-strict evaluation

Functional languages can be categorized by whether they use strict or non-strict evaluation, concepts that refer to how function arguments are processed when an expression is being evaluated.

In brief, strict evaluation always fully evaluates function arguments before invoking the function. Non-strict evaluation is free to do otherwise.

To illustrate, consider the following two functions f and g:

f(x) := x^2 + x + 1
g(x, y) := x + y

Under strict evaluation, we would have to evaluate function arguments first, for example:

  f(g(1, 4))
= f(1 + 4)
= f(5)
= 5^2 + 5 + 1
= 31

By contrast, non-strict evaluation need not fully evaluate the arguments; in particular it may send the arguments unevaluated to the function, perhaps evaluating them later. For example, one non-strict strategy (call-by-name) might work as follows:

  f(g(1, 4))
= g(1, 4)^2 + g(1, 4) + 1
= (1 + 4)^2 + (1 + 4) + 1
= 5^2 + 5 + 1
= 31

A key property of strict evaluation is that when an argument expression fails to terminate, the whole expression fails to terminate. With non-strict evaluation, this need not be the case, since argument expressions need not be evaluated at all.

Advantages of strict-evaluation

• Parameters are usually passed around as (simple) atomic units, rather than as (rich) expressions. (For example, the integer 5 can be passed on a register, whereas the expression 1+4 will require several memory locations). This has a direct implementation on standard hardware.

• The order of evaluation is quite clear to the programmer: every argument must be evaluated before the function body is invoked.

Advantages of non-strict-evaluation

• Lambda calculus provides a stronger theoretic foundation for languages that employ non-strict evaluation.

• A non-strict evaluator may recognize that a sub-expression does not need to be evaluated. For example, given the definitions

multiply(0, x) = 0;
multiply(n, x) = x + multiply(n-1, x);
f(0) = 1;
f(n) = n * f(n-1);

and expression

multiply(0, f(1000000))

a strict evaluator would (strictly speaking) need to take (on the order of) 1,000,000 steps to find the value of f(1000000). A non-strict evaluator may use the definition of multiply first, reducing the whole expression to 0 before even trying to compute f(1000000).

• Non-strict evaluation can use the above to allow "infinite" data structures. For example, using Haskell, given the definitions

evens n = n : [evens (n+2)] -- an "infinite list" of even numbers starting with n
 
-- The function "take n" returns the first n elements of its argument
take 0 (list)   = []                  -- when n is 0, return an empty list
take n (x:list) = x : (take (n-1) list) -- otherwise, return the first element and n-1 of the next elements

the expression

take 4 (evens 0)

quickly returns [0,2,4,6]. Under strict evaluation, evens would need to be fully evaluated before take could be called, but since evens is recursive it would never (strictly speaking) terminate. With non-strict evaluation, the take 4 function only forces the evaluation of four elements of evens 0 and the other elements are never inspected or evaluated.

Lazy evaluation

The need for a more efficient form of non-strict evaluation led to the development of lazy evaluation, a type of non-strict evaluation, where the initial evaluation of an argument is shared throughout the evaluation sequence. Consequently an argument (such as g(1, 4) in the above example) is never evaluated more than once. Under lazy evaluation, expressions are sent to subordinate functions as references to expression trees whose value has not yet been computed. When any such expression tree must be expanded, the expression tree "remembers" its result, and thus avoids recomputing the same expression a second time. In the initial example, this would pose as follows:

= f(g(1, 4))
= g(1, 4)^2 + g(1, 4) + 1

It is then necessary to evaluate g(1, 4). This can be computed once, yielding:

  g(1, 4)
  = 1 + 4
  = 5

Then, since both references to g(1, 4) are references to the same (pure) expression, both "know" that their value is 5. This means that their value is computed only once, even though they are passed symbolically to the function f.

= 5^2 + 5 + 1
= 25 + 5 + 1
= 31

Lazy evaluation tends to be used by default in pure functional languages such as Miranda, Clean and Haskell.

Functional programming in non-functional languages

It is possible to employ a functional style of programming in languages that are not traditionally considered functional languages. Some non-functional languages have borrowed features such as higher-order functions, and list comprehensions from functional programming languages. This makes it easier to adopt a functional style when using these languages. Functional constructs such as higher-order functions and lazy lists can be obtained in C++ via libraries. In C, function pointers can be used to get some of the effects of higher-order functions. For example the common function map can be implemented using function pointers. In C# version 3.0 and higher, lambda functions can be employed to write programs in a functional style. Widespread declarative domain specific languages like SQL and Lex/Yacc, although not always Turing-complete, use some elements of functional programming, especially in eschewing mutable values.

Comparison of functional and imperative programming

Functional programming is very different from imperative programming. The most significant differences stem from the fact that functional programming avoids side effects, which are used in imperative programming to implement state and I/O. Pure functional programming disallows side effects completely. Disallowing side effects provides for referential transparency, which makes it easier to verify, optimize, and parallelize programs, and easier to write automated tools to perform those tasks.

Higher order functions are rarely used in older imperative programming. Where a traditional imperative program might use a loop to traverse a list, a functional style would often use a higher-order function, map, that takes as arguments a function and a list, applies the function to each element of the list, and returns a list of the results.

Simulating state

There are tasks—for example, maintaining a bank account balance—that often seem most naturally implemented with state. Pure functional programming performs these tasks, and I/O tasks such as accepting user input and printing to the screen, in a different way.

The pure functional programming language Haskell implements them using monads, derived from category theory. Monads are powerful and offer an intuitive way to model state (and other side effects such as I/O) in an imperative manner without losing purity. While existing monads are easy to use, many find it difficult to understand how to define new monads (which is sometimes needed for certain types of libraries).

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

Efficiency issues

Functional programming languages have been perceived as less efficient in their use of CPU and memory than imperative languages such as C and Pascal. However, for programs that perform intensive numerical computations, functional languages such as OCaml and Clean are similar in speed to C. For programs that handle large matrices and multidimensional databases, array functional languages (such as J and K) were designed with speed optimization in mind.

Purely functional languages have a reputation for being slower than imperative languages. However, immutability of data can, in many cases, lead to execution efficiency in allowing the compiler to make assumptions that are unsafe in an imperative language.

For purely functional languages, the worst-case slowdown is exponential. However, such slowdowns occur very rarely in practice.

Coding styles

Imperative programs tend to emphasize the series of steps taken by a program in carrying out an action, while functional programs tend to emphasize the composition and arrangement of functions, often without specifying explicit steps. A simple example of two solutions to the same programming goal (using the same multi-paradigm language Python) illustrates this.

# imperative style
target = [] # create empty list
for item in source_list: # iterate over each thing in source
    trans1 = G(item) # transform the item with the G() function
    trans2 = F(trans1) # second transform with the F() function
    target.append(trans2) # add transformed item to target

A functional version has a different feel to it:

# functional style
# FP-oriented languages often have standard compose()
compose2 = lambda F, G: lambda x: F(G(x))
target = map(compose2(F, G), source_list)

In contrast to the imperative style that describes the steps involved in building target, the functional style describes the mathematical relationship between source_list and target.

In practice in Python that code is often written with a list comprehension, a form of syntactic sugar for the for loop with implicit append:

target = [F(G(item)) for item in source_list]

See also

• Eager evaluation
• Function-level programming (compare and contrast)
• Imperative programming (contrast)
• Lambda calculus
• List of functional programming topics
• Logic programming (contrast)
• Nested function
• Procedural programming (contrast)
• Purely functional
• Structure and Interpretation of Computer Programs, a textbook and a set of lecture videorecordings from MIT

Further reading

• Cousineau, Guy and Michel Mauny. The Functional Approach to Programming. Cambridge, UK: Cambridge University Press, 1998.
• Curry, Haskell Brooks and Feys, Robert and Craig, William. Combinatory Logic. Volume I. North-Holland Publishing Company, Amsterdam, 1958.
• Curry, Haskell Brooks and Hindley, J. Roger and Seldin, Jonathan P. Combinatory Logic. Volume II. North-Holland Publishing Company, Amsterdam * London, 1972.
• Dominus, Mark Jason. Higher-Order Perl. Morgan Kaufman. 2005.
• Felleisen, Matthias, Robert Findler, Matthew Flatt, and Shriram Krishnamurthi. How to Design Programs HTDP. MIT Press. 2001. on-line
• Graham, Paul. ANSI Common LISP. Englewood Cliffs, New Jersey: Prentice Hall, 1996.
• MacLennan, Bruce J. Functional Programming: Practice and Theory. Addison-Wesley, 1990.
• 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.

External links

• Why Functional Programming Matters by John Hughes
• Functional Programming for the Rest of Us An introduction
• "Functional Programming" — Chapter 4 of Advanced Programming Language Design by Raphael Finkel, an introductory explanation of functional programming
• Functional programming in Python (by David Mertz): part 1, part 2, part 3
• The Implementation of Functional Programming Languages Simon Peyton Jones, published by Prentice Hall, 1987.