A method of writing computer programs in which the relationships between variables are stated, rather than instructions to perform operations on the variables. The outcome of running the program is achieved by evaluating the functional relationships. A functional language is an example of a declarative language.
Functional programming is a programming paradigm that conceives computation as the evaluation of mathematical functions and avoids state and mutable data. Functional programming emphasizes the application of functions, in contrast with imperative programming, which emphasizes changes in state and the execution of sequential commands.
A broader conception of functional programming simply defines a set of common concerns and themes rather than a list of distinctions from other paradigms. Other common features of functional programming languages are continuations, Hindley-Milner type inference systems, non-strict evaluation (including, but not limited to, "laziness"), and monads.
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 (concurrent applications), R (statistics), Mathematica (symbolic math), J and K (financial analysis), and domain-specific programming languages like XSLT. Important influences on functional programming have been the lambda calculus, the APL programming language, the Lisp programming language, and more recently the Haskell programming language. 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. An early functional-flavored programming language was LISP (now mixed-case "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, though LISP is technically a multi-paradigm language. Iverson developed the APL programming language in the early 1960s, described in his 1962 book "A Programming Language." 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? in modern language, this means that functional program 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 the language Miranda at the University of Kent. The Haskell programming language was released in the late 1980s in an attempt to gather together many ideas in functional programming research.
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
Functional programming uses the notion of higher-order functions. (The derivative and antiderivative in calculus are mathematical examples of functions that map a function to another 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 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). Not all functional programs or functional programming languages are purely functional.
"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.
Most compilers for imperative programming languages do not perform common subexpression elimination for function calls, because they do not track whether a function is pure.
Recursion
Iteration (looping) in functional languages is usually accomplished via recursion. The Scheme programming language standard requires implementations to recognize and optimize tail recursion.
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 lambda functions, higher-order functions, and list comprehensions from functional programming languages. This makes it easier to adopt a functional style when using these languages. Widespread declarative domain specific languages like SQL and Lex/Yacc, while not 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.
Higher order functions are rarely used in older imperative programming.
The pure functional programming language Haskell implements them using monads, derived from category theory in mathematics.
Efficiency issues
Functional programming languages have automatic memory management with garbage collection, in contrast to older imperative languages like C and Pascal which use explicit memory management. Functional programming languages have been perceived as less efficient in their use of CPU and memory than those languages.
Functional programming languages have become more efficient over the years. For programs which 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. Despite purely functional languages having a reputation for being slower, any imperative algorithm is expressible in these languages with a logarithmic slowdown in the worst case.
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 targetA functional version has a different feel to it:
# functional style def compose2(F, G): # FP-oriented languages often have standard compose() def C(item): # here we create utility-function for composition return F(G(item)) return C target = map(compose2(F,G), source_list) # More compact examples of the functional paradigm in Python: target = map(lambda x: F(G(x)), source_list) # uses a lambda form with map # or: target = [F(G(item)) for item in source_list] # a list comprehensionIn 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.
User Comments Add a comment…