Functional programming |
Functional programming is a programming paradigm that treats Computation as the evaluation of mathematical functions. It is more heavily used in academia than in industry. The strength of a functional paradigm is the removal of side-effects during computation. This has uses in both program verification, for checking the correctness of programs, and in program optimisation. One particular use in program optimisation is to transform programs for parallel programming.
Functional programming emphasizes the definition of functions, rather than the implementation of Finite state machine. This is in contrast to procedural_programming or imperative programming where programming emphasizes the sequencing of commands in execution. The values in these languages are formed by using assignments to transform the state of the program. A functional Computer program is immutable: rather than modify state to produce values, it constructs state from older pieces of state in the program.
= Introduction =
function (mathematics) have great strengths in terms of flexibility and analysis. For example, if a function is known to be Idempotent (software), then a call to a function which has its own output as its argument, and which is known to have no Side-effect (computer science), may be efficiently computed without multiple calls.
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) = x2 + 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 object, 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 programming language and map in Haskell_programming_language 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 Currying. Currying is a technique of rewriting a function with multiple parameters as a function with one parameter that maps to another function of one parameter and so on, until all parameters are exhausted. The curried function can be applied to just a subset of its parameters. The result is a function where the parameters in this subset 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.
=History=
Lambda calculus could be considered the first functional programming language, though it was not designed to 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 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 programming language, developed by John McCarthy while at the Massachusetts Institute of Technology for the IBM 700/7000 series#Scientific Architecture scientific computers 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 programming language was a later attempt to simplify and improve LISP. In the 1970s the language ML programming language was created at the University of Edinburgh, and David Turner (computer scientist) developed the language Miranda programming language at the University of Kent. The language Haskell_programming_language was released in the late 1980s in an attempt to gather together many ideas in functional programming research.
=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 programming language or Pascal programming language. 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, before 2002, as notable exceptions).
= Functional programming languages =
Purely_functional programs require no variables and have no side-effects, and are therefore automatically Thread-safe. They are also automatically verifiable provided that any recursive cycle eventually stops. Nested functions just pass their results back to the main function. Functional languages commonly make quite sophisticated use of the Stack (computing).
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.
Furthermore, functional programming languages are likely to enforce referential transparency, which is the familiar notion that equals can be substituted for equals : if two expressions are defined to have equal values, then one can be substituted for the other in any larger expression without affecting the result of the computation. For example, in
z = f(sqrt(2), sqrt(2));
we can factor out Square root(2) and write
s = sqrt(2); z = f(s, s);
thus eliminating the extra evaluation of the square-root function.
As intuitive as it sounds, this is not always the case with imperative languages. A case in point is the C programming language s getchar() function , which gets a Character (computing) from the standard input; it is strictly a function not of its arguments but of the contents of the input stream stdin and how much has already been read. Following the example above:
z = f(getchar(), getchar());
we cannot eliminate getchar() as we did for sqrt(2), because in C, getchar() might return two different values the two times it is called.
Hidden side-effects are in general the rule, rather than the exception, of traditional imperative programming languages. Whenever a procedure reads a value from or writes a value to a global or shared variable, the potential exists for hidden side-effects. This leakage of information across procedure boundaries, in ways that are not explicitly represented by function calls and definitions, greatly increases the hidden complexity of programs written in conventional non-functional languages.
By removing these hidden information leaks, functional programming languages offer the possibility of much cleaner programs which are easier to design and debug. However, they also offer other benefits.
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_programming_language and Common Lisp programming language. 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.
= Higher-order functions =
A powerful mechanism sometimes used in functional programming is the notion of higher-order function. 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 were studied in the lambda calculus theory well before the notion of functional programming existed and are present in the design of a number of functional programming languages, such as Scheme programming language and Haskell programming language.
More generally, higher order functions could be said to be a part of natural language. For example, adverbs can modify verbs (actions) giving rise to derived verbs. As a pattern of thought, imperative verbs are similar to ordinary functions in programming languages.
Higher-order functions are crucial in the function-level programming paradigm, which includes languages such as John Backus s FP (programming language) and Kenneth E. Iverson s J programming language.
= Speed and space considerations =
Functional languages have long been criticised as resource-hungry, both in terms of central processing unit resources and memory. This was mainly due to two things:
As modern imperative languages and their implementations have started to include greater emphasis on correctness, rather than raw speed, and the implementations of functional languages have begun to emphasize speed as well as correctness, the performance of functional languages and imperative languages has begun to converge. For programs which spend most of their time doing numerical computations, some functional languages (such as OCaml programming language and Clean (programming language)) can approach C (programming language) speed, while for programs that handle large matrices and multidimensional databases, Array programming functional languages (such as J programming language and K programming language) are usually faster than most non-optimized C programs. 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 functional programming 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.
There are two methods of evaluating functional languages, strict (or eager evaluation) and lazy evaluation . Strict languages evaluate all function arguments before evaluating the function itself, while lazy languages only evaluate them when they are required. Haskell (programming language) is the most common example of a lazy language, while ML is strict. Lazy evaluation can add significant performance overhead keeping track of unevaluated functions; however, it makes programming easier in many ways.
The competitive performance of modern (impure) functional programming languages such as OCaml and MLton-compiled 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, modern languages are now used in a wide range of scientific applications, from numerical analysis to visualisation.
=Functional languages=
The oldest example of a functional language is Lisp programming language, though neither the original LISP nor modern Lisps such as Common Lisp are pure-functional. Lisp variants include Logo programming language, Scheme programming language, Dylan programming language. The modern canonical examples are Haskell programming language and members of the ML programming language family including SML programming language and Ocaml. Others include Erlang programming language, Clean programming language, and Miranda programming language. A third type of a commonly used functional language is Xslt.
Other computer languages, for example Tcl, Perl, Python (programming language) & Ruby_programming_language, 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 [www.tcs.informatik.uni-muenchen.de/lehre/SS03/Quanten/papers/sel02.pdf.gz+" title="http://scholar.google.com/scholarhl=en&lr=&q=cache:0bfAXyE4QawJ:www.tcs.informatik.uni-muenchen.de/lehre/SS03/Quanten/papers/sel02.pdf.gz+" target="_blank">http://scholar.google.com/scholarhl=en&lr=&q=cache:0bfAXyE4QawJ:www.tcs.informatik.uni-muenchen.de/lehre/SS03/Quanten/papers/sel02.pdf.gz+ Towards a quantum programming language] , and the Haskell-like language [http://www.cs.nott.ac.uk/~jjg/qml.html QML].
provides an exhaustive list.
=See also=
=References=
*Cousineau, Guy and Michel Mauny. The Functional Approach to Programming . Cambridge, UK: Cambridge University Press, 1998. *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. *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. *Harrop, Jon. Objective CAML for Scientists . Cambridge, England: [http://www.ffconsultancy.com/products/ocaml_for_scientists/ Flying Frog Consultancy], 2005.
=External links=
This article includes parts of an [http://www.nupedia.com/article/short/Functional+Programming/ earlier version] ([http://www.nupedia.com/article/677/ stable link]) posted on 19 June 2001 on Nupedia; reviewed and approved by the Computers group; editor, Michael Witbrock ; lead reviewer, Nancy Tinkham; lead copyeditors, Ruth Ifcher. and Larry Sanger.
|
|