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 with the imperative programming style that emphasizes changes in state.cite journal|last=Hudak|first=Paul|authorlink=Paul Hudak|title=Conception, evolution, and application of functional programming languages|journal=ACM Computing Surveys|volume=21|issue=3|pages=359–411|month=September|year=1989|url=http://www.cs.berkeley.edu/~jcondit/pl-prelim/hudak89functional.pdf|doi=10.1145/72551.72554]

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, [cite web|title=Who uses Erlang for product development?|work=Frequently asked questions about Er _ur. accessdate=2007-08-05] OCaml, [cite journal
last = Minsky
first = Yaron
last2 = Weeks
first2 = Stephen
title = Caml Trading - experiences with functional programming on Wall Street
journal = Journal of Functional Programming
volume = 18
issue = 4
pages = 553-564
publisher = Cambridge University Press
location =
date = July 2008
url = http://journals.cambridge.org/action/displayAbstract?aid=1899164
doi = 10.1017/S095679680800676X
accessdate = 2008-08-27]
Haskell, [cite web|title="Haskell - Haskell Wiki|url=http://www.haskell.org/|accessdate=2008-08-27]
Scheme (since 1986) [cite magazine
last = Clinger
first = Will
title = MultiTasking and MacScheme
magazine = MacTech
volume = 3
issue = 12
date = 1987
url = http://www.mactech.com/articles/mactech/Vol.03/03.12/Multitasking/index.html
accessdate = 2008-08-28] [cite magazine
last = Hartheimer
first = Anne
title = Programming a Text Editor in MacScheme+Toolsmith
magazine = MacTech
volume = 3
issue = 1
date = 1987
url = http://www.mactech.com/articles/mactech/Vol.03/03.1/SchemeWindows/index.html
accessdate = 2008-08-28] and domain-specific programming languages like
R (statistics), [ [http://www.r-project.org/useR-2006/program.html The useR! 2006 conference schedule includes papers on the commercial use of R] ] Mathematica (symbolic math), [cite web|author=Department of Applied Math, University of Colorado|title=Functional vs. Procedural Programming Language|url=http://amath.colorado.edu/computing/mmm/funcproc.html|accessdate=2006-08-28]
J and K (financial analysis), and XSLT (XML). [cite web | url=http://www.topxml.com/xsl/articles/fp/ | author=Dimitre Novatchev | title=The Functional Programming Language XSLT - A proof through examples | accessmonthday=May 27 | accessyear=2006 | work=TopXML] [cite web| url=http://gnosis.cx/publish/programming/xml_models_fp.html | author=David Mertz | title=XML Programming Paradigms (part four): Functional Programming approached to XML processing | accessmonthday=May 27 | accessyear=2006 | work=IBM developerWorks]

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

History

Lambda calculus provides a theoretical framework for describing functions and their evaluation. Though 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. [cite book|last=Curry |first=Haskell Brooks |coauthors=Robert Feys and Craig, William |title=Combinatory Logic. Volume I |publisher=North-Holland Publishing Company |location=Amsterdam |year=1958] 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. [cite journal|first=John|last=McCarthy|authorlink=John McCarthy|title=History of Lisp|journal=In ACM SIGPLAN History of Programming Languages Conference|pages=173–196|month=June|year=1978|url=http://citeseer.ist.psu.edu/mccarthy78history.html " The implementation of LISP began in Fall 1958."] 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 [http://www.stanford.edu/class/cs242/readings/backus.pdf 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 , 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.Fact|date=October 2008

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. [cite web | url=http://www.byte.com/art/9408/sec11/art1.htm | title=Functional Programming Comes of Age | author=Dick Pountain | work=BYTE.com (August 1994) | accessmonthday=August 31 | accessyear=2006]

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 we count the computation of the result in itself 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

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 elementsthe 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. [cite journal
last=Hartel
first=Pieter
coauthors=Henk Muller and Hugh Glaser
title=The Functional C experience
journal=The Journal of Functional Programming
volume=14 |issue=2|pages=129–135|month=March |year=2004
url=http://www.ub.utwente.nl/webdocs/ctit/1/00000084.pdf
doi=10.1017/S0956796803004817; cite web
title=Functional programming in Python, Part 3
url=http://www-128.ibm.com/developerworks/linux/library/l-prog3.html
author=David Mertz
accessdate=2006-09-17
work=IBM developerWorks( [http://www-128.ibm.com/developerworks/library/l-prog.html Part 1] , [http://www-128.ibm.com/developerworks/library/l-prog2.html Part 2] )] 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. [cite web|last=McNamara|first=B.|title= FC++: Functional Programming in C++ |url=http://www-static.cc.gatech.edu/~yannis/fc++/| accessdate=2006-05-28] In C one can use function pointers to get some of the effects of higher-order functions, for example one can implement the common function map using function pointers. In C# version 3.0 and higher, lambda functions can be employed to write programs in a functional style.Fact|date=September 2008 Widespread declarative domain specific languages like SQL and Lex/Yacc, while not always Turing-complete, use some elements of functional programming, especially in eschewing mutable values. [cite journal | title=SEQUEL: A structured English query language | author=Donald D. Chamberlin and Raymond F. Boyce | journal=Proceedings of the 1974 ACM SIGFIDET | pages=249–264 | year=1974. In this paper, one of the first formal presentations of the concepts of SQL (and before the name was later abbreviated), Chamberlin and Boyce emphasize that SQL was developed "Without resorting to the concepts of bound variables and quantifiers".]

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). [cite web|last=Newbern|first=J.|title=All About Monads: A comprehensive guide to the theory and practice of monadic programming in Haskell|url=http://www.haskell.org/all_about_monads/html/|accessdate=2008-02-14, "The sheer number of different monad tutorials on the internet is a good indication of the difficulty many people have understanding the concept. This is due to the abstract nature of monads and to the fact that they are used in several different capacities, which can confuse the picture of exactly what a monad is and what it is good for."]

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.Fact|date=October 2008 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.Fact|date=October 2008 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. The worst-case slowdown was shown to be exponential. [ R.A. DeMillo, S.C. Eisenstat, R.J. Lipton (1980). "Space-time trade-offs in structured programming", "JACM" 27: 123-127. doi:10.1145/322169.322180] Situations where such slowdowns arise occur very rarely in practice. They do imply, however, that non-functional supersets of applicative languages are sometimes important.

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 styletarget = [] # create empty listfor 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.

ee 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

References

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. [http://www.htdp.org 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

* [http://www.math.chalmers.se/~rjmh/Papers/whyfp.html Why Functional Programming Matters] by John Hughes
* [http://www.defmacro.org/ramblings/fp.html Functional Programming for the Rest of Us] An introduction
* [ftp://ftp.aw.com/cseng/authors/finkel/apld/finkel04.pdf "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): [http://gnosis.cx/publish/programming/charming_python_13.html part 1] , [http://gnosis.cx/publish/programming/charming_python_16.html part 2] , [http://gnosis.cx/publish/programming/charming_python_19.html part 3]
* [http://research.microsoft.com/~simonpj/papers/slpj-book-1987/index.htm The Implementation of Functional Programming Languages] Simon Peyton Jones, published by Prentice Hall, 1987.