Functional programming

Encyclopedia

In computer science

,

that treats computation

as the evaluation of mathematical function

s and avoids state

and mutable

data. It emphasizes the application of functions, in contrast to the imperative programming

style, which emphasizes changes in state. Functional programming has its roots in lambda calculus

, a formal system

developed in the 1930s to investigate function definition, function application, and recursion

. Many functional programming language

s can be viewed as elaborations on the lambda calculus

.

In practice, the difference between a mathematical function and the notion of a "function" used in imperative programming is that imperative functions can have side effects

, changing the value of program state

. Because of this they lack referential transparency, i.e. the same language expression can result in different values at different times depending on the state of the executing program. Conversely, in functional code, the output value of a function depends only on the arguments that are input to the function, so calling a function

Functional programming languages, especially purely functional

ones, have largely been emphasized in academia rather than in commercial software development. However, prominent functional programming languages such as Common

Lisp, Scheme, Clojure

, Racket, Erlang, Objective Caml

, Haskell

and F# have been used in industrial and commercial applications by a wide variety of organizations. Functional programming is also supported in some domain-specific programming language

s like R

(statistics), Mathematica

(symbolic math), J

and K

(financial analysis) and XQuery

/XSLT

(XML

). Widespread domain-specific declarative languages like SQL

and Lex

/Yacc

use some elements of functional programming, especially in eschewing mutable values. Spreadsheet

s can also be viewed as functional programming languages.

Programming in a functional style can also be accomplished in languages that aren't specifically designed for functional programming. For example, the imperative Perl programming language has been the subject of a book describing how to apply functional programming concepts.

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. An equivalent theoretical formulation, combinatory logic

, is commonly perceived as more abstract than lambda calculus and preceded it in invention. It is used in some esoteric languages including Unlambda

. Combinatory logic and lambda calculus were both originally developed to achieve a clearer approach to the foundations of mathematics

.

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 APL in the early 1960s, described in his 1962 book

's FP

. In the early 1990s, Iverson and Roger Hui

created J

. In the mid 1990s, Arthur Whitney, who had previously worked with Iverson, created K

, which is used commercially in financial industries.

John Backus

presented FP

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 ML 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

. Also in the 1970s, the development of Scheme (a partly functional dialect of Lisp), as described in the influential Lambda Papers and the 1985 textbook

In the 1980s, Per Martin-Löf

developed intuitionistic type theory

(also called

s of arbitrarily complex mathematical propositions expressed as dependent type

s. This led to powerful new approaches to interactive theorem proving

and has influenced the development of many subsequent functional programming languages.

The Haskell language

began with a consensus in 1987 to form an open standard

for functional programming research; implementation releases have been ongoing since 1990.

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

s are functions that can either take other functions as arguments or return them as results (the differential operator

that produces the derivative

of a function is an example of this in calculus).

Higher-order functions are closely related to first-class function

s, 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 partial application

or 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. This allows one to succinctly express, for example, the successor function as the addition operator partially applied to the natural number one.

functions (or expressions) have no memory or I/O side effects

. This means that pure functions have several useful properties, many of which can be used to optimize the code:

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 optimizations 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 optimizations. Fortran 95 allows functions to be designated "pure".

(looping) in functional languages is usually accomplished via recursion

. Recursive function

s 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 language standard requires implementations to recognize and optimize tail recursion. Tail recursion optimization can be implemented by transforming the program into continuation passing style during compiling, among other approaches.

Common patterns of recursion can be factored out using higher order functions, with catamorphism

s and anamorphism

s (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.

Most general purpose functional programming languages allow unrestricted recursion and are Turing complete, which makes the halting problem

undecidable

, can cause unsoundness of equational reasoning, and generally requires the introduction of inconsistency into the logic expressed by the language's type system

. Some special purpose languages such as Coq

allow only well-founded recursion and are strongly normalizing (nonterminating computations can be expressed only with infinite streams of values called codata). As a consequence, these languages fail to be Turing complete and expressing certain functions in them is impossible, but they can still express a wide class of interesting computations while avoiding the problems introduced by unrestricted recursion. Functional programming limited to well-founded recursion with a few other constraints is called total functional programming

. See Turner 2004 for more discussion.

of expressions containing failing or divergent computations. Under strict evaluation, the evaluation of any term containing a failing subterm will itself fail. For example, the expression:

print length([2+1, 3*2, 1/0, 5-4])

will fail under strict evaluation because of the division by zero in the third element of the list. Under nonstrict evaluation, the length function will return the value 4, since evaluating it will not attempt to evaluate the terms making up the list. In brief, strict evaluation always fully evaluates function arguments before invoking the function. Non-strict evaluation does not evaluate function arguments unless their values are required to evaluate the function call itself.

The usual implementation strategy for non-strict evaluation in functional languages is graph reduction

. Non-strict evaluation is used by default in several pure functional languages, including Miranda, Clean and Haskell

.

Hughes 1984 argues for non-strict evaluation as a mechanism for improving program modularity through separation of concerns

, by easing independent implementation of producers and consumers of data streams. Launchbury 1993 describes some difficulties that lazy evaluation introduces, particularly in analyzing a program's storage requirements, and proposes an operational semantics

to aid in such analysis. Harper 2009 proposes including both strict and nonstrict evaluation in the same language, using the language's type system to distinguish them.

, as opposed to the untyped lambda calculus used in Lisp and its variants (such as Scheme). The use of algebraic datatypes and pattern matching

makes manipulation of complex data structures convenient and expressive; the presence of strong compile-time type checking makes programs more reliable, while type inference

frees the programmer from the need to manually declare types to the compiler.

Some research-oriented functional languages such as Coq

, Agda, Cayenne, and Epigram are based on intuitionistic type theory

, which allows types to depend on terms. Such types are called dependent type

s. These type systems do not have decidable type inference and are difficult to understand and program with. But dependent types can express arbitrary propositions in predicate logic

. Through the Curry–Howard isomorphism, then, well-typed programs in these languages become a means of writing formal mathematical proof

s from which a compiler can generate certified code

. While these languages are mainly of interest in academic research (including in formalized mathematics), they have begun to be used in engineering as well. Compcert

is a compiler

for a subset of the C programming language

that is written in Coq and formally verified.

A limited form of dependent types called generalized algebraic data type

s (GADT's) can be implemented in a way that provides some of the benefits of dependently-typed programming while avoiding most of its inconvenience. GADT's are available in the Glasgow Haskell Compiler

and in Scala (as "case classes"), and have been proposed as additions to other languages including Java and C#.

programming language's solid support for functional programming stands out. For example, D has a pure modifier to enforce functional purity. Only Fortran 95 has something similar.

First class functions have slowly been added to mainstream languages. For example, in early 1994, support for lambda, filter, map, and reduce was added to Python

. Then during the development of Python 3000, Guido van Rossum

called for the removal of these features. So far, only the

5.3, Visual Basic

9, C# 3.0, and C++11.

The Language Integrated Query

(LINQ) feature, with its many incarnations, is an obvious and powerful use of functional programming in .NET

.

In Java

, anonymous classes can sometimes be used to simulate closure

s; however, anonymous classes are not always proper replacements to closure

s because they have more limited capabilities.

Many object-oriented design pattern

s are expressible in functional programming terms: for example, the strategy pattern

simply dictates use of a higher-order function, and the visitor pattern roughly corresponds to a catamorphism

, or fold

.

The benefits of immutable data can be seen even in imperative programs, so programmers often strive to make some data immutable even in imperative programs.

. 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 program would use a different technique. It would use a higher-order function that takes as arguments a function and a list. The higher-order function would then apply the given function to each element of the given list and then return a new list with the results.

The pure functional programming language HaskellHaskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...

implements them using monads, derived from category theory

. Monads offer a way to abstract certain types of computational patterns, including (but not limited to) modeling of computations with mutable state (and other side effects such as I/O) in an imperative manner without losing purity. While existing monads may be easy to apply in a program, given appropriate templates and examples, many students find them difficult to understand conceptually, e.g., when asked to define new monads (which is sometimes needed for certain types of libraries).

Impure functional languages usually include a more direct method of managing mutable state. Clojure, for example, uses managed references that can be updated by applying pure functions to the current state. This kind of approach enables mutability while still promoting the use of pure functions as the preferred way to express computations.

Alternative methods such as Hoare logic

and uniqueness

have been developed to track side effects in programs. Some modern research languages use effect system

s to make explicit the presence of side effects.

and memory than imperative languages such as C and Pascal

. For purely functional languages, the worst-case slowdown is logarithmic in the number of memory cells used, because mutable memory can be represented by a purely functional data structure with logarithmic access time (such as a balanced tree). However, such slowdowns are not universal. For programs that perform intensive numerical computations, functional languages such as Objective Caml

and Clean are only slightly slower than C

. For programs that handle large matrices

and multidimensional database

s, array

functional languages (such as J

and K

) were designed with speed optimization.

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, thus increasing opportunities for inline expansion

.

Lazy evaluation

may also speed up the program, even asymptotically, whereas it may slow it down at most by a constant factor (however, it may introduce memory leaks when used improperly). Launchbury 1993 discusses theoretical issues related to memory leaks from lazy evaluation, and O'Sullivan

s). The imperative example is in C++

.

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

,

**functional programming**is a programming paradigmProgramming paradigm

A programming paradigm is a fundamental style of computer programming. Paradigms differ in the concepts and abstractions used to represent the elements of a program and the steps that compose a computation A programming paradigm is a fundamental style of computer programming. (Compare with a...

that treats computation

Computation

Computation is defined as any type of calculation. Also defined as use of computer technology in Information processing.Computation is a process following a well-defined model understood and expressed in an algorithm, protocol, network topology, etc...

as the evaluation of mathematical function

Function (mathematics)

In mathematics, a function associates one quantity, the argument of the function, also known as the input, with another quantity, the value of the function, also known as the output. A function assigns exactly one output to each input. The argument and the value may be real numbers, but they can...

s and avoids state

Program state

One of the key concepts in computer programming is the idea of state, essentially a snapshot of the measure of various conditions in the system. Most programming languages require a considerable amount of state information in order to operate properly - information which is generally hidden from...

and mutable

Immutable object

In object-oriented and functional programming, an immutable object is an object whose state cannot be modified after it is created. This is in contrast to a mutable object, which can be modified after it is created...

data. It emphasizes the application of functions, in contrast to the imperative programming

Imperative programming

In computer science, imperative programming is a programming paradigm that describes computation in terms of statements that change a program state...

style, which emphasizes changes in state. Functional programming has its roots in lambda calculus

Lambda calculus

In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...

, a formal system

Formal system

In formal logic, a formal system consists of a formal language and a set of inference rules, used to derive an expression from one or more other premises that are antecedently supposed or derived . The axioms and rules may be called a deductive apparatus...

developed in the 1930s to investigate function definition, function application, and recursion

Recursion

Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...

. Many functional programming language

Programming language

A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....

s can be viewed as elaborations on the lambda calculus

Lambda calculus

In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...

.

In practice, the difference between a mathematical function and the notion of a "function" used in imperative programming is that imperative functions can have side effects

Side effect (computer science)

In computer science, a function or expression is said to have a side effect if, in addition to returning a value, it also modifies some state or has an observable interaction with calling functions or the outside world...

, changing the value of program state

Program state

One of the key concepts in computer programming is the idea of state, essentially a snapshot of the measure of various conditions in the system. Most programming languages require a considerable amount of state information in order to operate properly - information which is generally hidden from...

. Because of this they lack referential transparency, i.e. the same language expression can result in different values at different times depending on the state of the executing program. Conversely, in functional code, the output value of a function depends only on the arguments that are input to the function, so calling a function

*f*twice with the same value for an argument*x*will produce the same result*f(x)*both times. Eliminating side effects can make it much easier to understand and predict the behavior of a program, which is one of the key motivations for the development of functional programming.Functional programming languages, especially purely functional

Purely functional

Purely functional is a term in computing used to describe algorithms, data structures or programming languages that exclude destructive modifications...

ones, have largely been emphasized in academia rather than in commercial software development. However, prominent functional programming languages such as Common

Common Lisp

Common Lisp, commonly abbreviated CL, is a dialect of the Lisp programming language, published in ANSI standard document ANSI INCITS 226-1994 , . From the ANSI Common Lisp standard the Common Lisp HyperSpec has been derived for use with web browsers...

Lisp, Scheme, Clojure

Clojure

Clojure |closure]]") is a recent dialect of the Lisp programming language created by Rich Hickey. It is a general-purpose language supporting interactive development that encourages a functional programming style, and simplifies multithreaded programming....

, Racket, Erlang, Objective Caml

Objective Caml

OCaml , originally known as Objective Caml, is the main implementation of the Caml programming language, created by Xavier Leroy, Jérôme Vouillon, Damien Doligez, Didier Rémy and others in 1996...

, Haskell

Haskell (programming language)

Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...

and F# have been used in industrial and commercial applications by a wide variety of organizations. Functional programming is also supported in some domain-specific programming language

Domain-specific programming language

In software development and domain engineering, a domain-specific language is a programming language or specification language dedicated to a particular problem domain, a particular problem representation technique, and/or a particular solution technique...

s like R

R (programming language)

R is a programming language and software environment for statistical computing and graphics. The R language is widely used among statisticians for developing statistical software, and R is widely used for statistical software development and data analysis....

(statistics), Mathematica

Mathematica

Mathematica is a computational software program used in scientific, engineering, and mathematical fields and other areas of technical computing...

(symbolic math), J

J (programming language)

The J programming language, developed in the early 1990s by Kenneth E. Iverson and Roger Hui, is a synthesis of APL and the FP and FL function-level languages created by John Backus....

and K

K (programming language)

K is a proprietary array processing language developed by Arthur Whitney and commercialized by Kx Systems. The language serves as the foundation for kdb, an in-memory, column-based database, and other related financial products. The language, originally developed in 1993, is a variant of APL and...

(financial analysis) and XQuery

XQuery

- Features :XQuery provides the means to extract and manipulate data from XML documents or any data source that can be viewed as XML, such as relational databases or office documents....

/XSLT

XSLT

XSLT is a declarative, XML-based language used for the transformation of XML documents. The original document is not changed; rather, a new document is created based on the content of an existing one. The new document may be serialized by the processor in standard XML syntax or in another format,...

(XML

XML

Extensible Markup Language is a set of rules for encoding documents in machine-readable form. It is defined in the XML 1.0 Specification produced by the W3C, and several other related specifications, all gratis open standards....

). Widespread domain-specific declarative languages like SQL

SQL

SQL is a programming language designed for managing data in relational database management systems ....

and Lex

Lex programming tool

Lex is a computer program that generates lexical analyzers . Lex is commonly used with the yacc parser generator. Lex, originally written by Mike Lesk and Eric Schmidt, is the standard lexical analyzer generator on many Unix systems, and a tool exhibiting its behavior is specified as part of the...

/Yacc

Yacc

The computer program yacc is a parser generator developed by Stephen C. Johnson at AT&T for the Unix operating system. The name is an acronym for "Yet Another Compiler Compiler." It generates a parser based on an analytic grammar written in a notation similar to BNF.Yacc used to be available as...

use some elements of functional programming, especially in eschewing mutable values. Spreadsheet

Spreadsheet

A spreadsheet is a computer application that simulates a paper accounting worksheet. It displays multiple cells usually in a two-dimensional matrix or grid consisting of rows and columns. Each cell contains alphanumeric text, numeric values or formulas...

s can also be viewed as functional programming languages.

Programming in a functional style can also be accomplished in languages that aren't specifically designed for functional programming. For example, the imperative Perl programming language has been the subject of a book describing how to apply functional programming concepts.

## History

Lambda calculusLambda calculus

In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped 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. An equivalent theoretical formulation, combinatory logic

Combinatory logic

Combinatory logic is a notation introduced by Moses Schönfinkel and Haskell Curry to eliminate the need for variables in mathematical logic. It has more recently been used in computer science as a theoretical model of computation and also as a basis for the design of functional programming...

, is commonly perceived as more abstract than lambda calculus and preceded it in invention. It is used in some esoteric languages including Unlambda

Unlambda

Unlambda is a minimal, "nearly pure" functional programming language invented by David Madore. It is based on combinatory logic, a version of the lambda calculus that omits the lambda operator. It relies mainly on two built-in functions and an "apply" operator...

. Combinatory logic and lambda calculus were both originally developed to achieve a clearer approach to the foundations of mathematics

Foundations of mathematics

Foundations of mathematics is a term sometimes used for certain fields of mathematics, such as mathematical logic, axiomatic set theory, proof theory, model theory, type theory and recursion theory...

.

An early functional flavored language was Lisp, developed by John McCarthy

John McCarthy (computer scientist)

John McCarthy was an American computer scientist and cognitive scientist. He coined the term "artificial intelligence" , invented the Lisp programming language and was highly influential in the early development of AI.McCarthy also influenced other areas of computing such as time sharing systems...

while at MIT

Massachusetts Institute of Technology

The Massachusetts Institute of Technology is a private research university located in Cambridge, Massachusetts. MIT has five schools and one college, containing a total of 32 academic departments, with a strong emphasis on scientific and technological education and research.Founded in 1861 in...

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

Dylan programming language

Dylan is a multi-paradigm programming language that includes support for functional and object-oriented programming, and is dynamic and reflective while providing a programming model designed to support efficient machine code generation, including fine-grained control over dynamic and static...

were later attempts to simplify and improve Lisp.

Information Processing Language

Information Processing Language

Information Processing Language is a programming language developed by Allen Newell, Cliff Shaw, and Herbert Simon at RAND Corporation and the Carnegie Institute of Technology from about 1956...

(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

Kenneth E. Iverson

Kenneth Eugene Iverson was a Canadian computer scientist noted for the development of the APL programming language in 1962. He was honored with the Turing Award in 1979 for his contributions to mathematical notation and programming language theory...

developed APL in the early 1960s, described in his 1962 book

*A Programming Language*(ISBN 9780471430148). APL was the primary influence on John BackusJohn Backus

John Warner Backus was an American computer scientist. He directed the team that invented the first widely used high-level programming language and was the inventor of the Backus-Naur form , the almost universally used notation to define formal language syntax.He also did research in...

's FP

FP (programming language)

FP is a programming language created by John Backus to support the function-level programming paradigm...

. In the early 1990s, Iverson and Roger Hui

Roger Hui

Roger Hui is a computer scientist and co-developer of the J Programming Language.He was born in Hong Kong and he immigrated to Canada with his entire family in 1966.-Education and career:In 1973, Hui entered the University of Alberta...

created J

J (programming language)

The J programming language, developed in the early 1990s by Kenneth E. Iverson and Roger Hui, is a synthesis of APL and the FP and FL function-level languages created by John Backus....

. In the mid 1990s, Arthur Whitney, who had previously worked with Iverson, created K

K (programming language)

K is a proprietary array processing language developed by Arthur Whitney and commercialized by Kx Systems. The language serves as the foundation for kdb, an in-memory, column-based database, and other related financial products. The language, originally developed in 1993, is a variant of APL and...

, which is used commercially in financial industries.

John Backus

John Backus

John Warner Backus was an American computer scientist. He directed the team that invented the first widely used high-level programming language and was the inventor of the Backus-Naur form , the almost universally used notation to define formal language syntax.He also did research in...

presented FP

FP (programming language)

FP is a programming language created by John Backus to support the function-level programming paradigm...

in his 1977 Turing Award

Turing Award

The Turing Award, in full The ACM A.M. Turing Award, is an annual award given by the Association for Computing Machinery to "an individual selected for contributions of a technical nature made to the computing community. The contributions should be of lasting and major technical importance to the...

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

Principle of compositionality

In mathematics, semantics, and philosophy of language, the Principle of Compositionality is the principle that the meaning of a complex expression is determined by the meanings of its constituent expressions and the rules used to combine them. This principle is also called Frege's Principle,...

. Backus's paper popularized research into functional programming, though it emphasized function-level programming

Function-level programming

In computer science, function-level programming refers to one of the two contrasting programming paradigms identified by John Backus in his work on programs as mathematical objects, the other being value-level programming....

rather than the lambda-calculus style which has come to be associated with functional programming.

In the 1970s ML was created by Robin Milner

Robin Milner

Arthur John Robin Gorell Milner FRS FRSE was a prominent British computer scientist.-Life, education and career:...

at the University of Edinburgh

University of Edinburgh

The University of Edinburgh, founded in 1583, is a public research university located in Edinburgh, the capital of Scotland, and a UNESCO World Heritage Site. The university is deeply embedded in the fabric of the city, with many of the buildings in the historic Old Town belonging to the university...

, and David Turner

David Turner (computer scientist)

Professor David Turner is a British computer scientist.He has a D.Phil. from the University of Oxford. He has held professorships at Queen Mary College, London, University of Texas at Austin and the University of Kent at Canterbury, where he now retains the post of Emeritus Professor.He is...

developed initially the language SASL at the University of St. Andrews and later the language Miranda at the University of Kent

University of Kent

The University of Kent, previously the University of Kent at Canterbury, is a public research university based in Kent, United Kingdom...

. ML eventually developed into several dialects, the most common of which are now Objective Caml

Objective Caml

OCaml , originally known as Objective Caml, is the main implementation of the Caml programming language, created by Xavier Leroy, Jérôme Vouillon, Damien Doligez, Didier Rémy and others in 1996...

and Standard ML

Standard ML

Standard ML is a general-purpose, modular, functional programming language with compile-time type checking and type inference. It is popular among compiler writers and programming language researchers, as well as in the development of theorem provers.SML is a modern descendant of the ML...

. Also in the 1970s, the development of Scheme (a partly functional dialect of Lisp), as described in the influential Lambda Papers and the 1985 textbook

*Structure and Interpretation of Computer Programs*

, brought awareness of the power of functional programming to the wider programming-languages community.Structure and Interpretation of Computer Programs

Structure and Interpretation of Computer Programs is a textbook published in 1984 about general computer programming concepts from MIT Press written by Massachusetts Institute of Technology professors Harold Abelson and Gerald Jay Sussman, with Julie Sussman...

In the 1980s, Per Martin-Löf

Per Martin-Löf

Per Erik Rutger Martin-Löf is a Swedish logician, philosopher, and mathematical statistician. He is internationally renowned for his work on the foundations of probability, statistics, mathematical logic, and computer science. Since the late 1970s, Martin-Löf's publications have been mainly in...

developed intuitionistic type theory

Intuitionistic type theory

Intuitionistic type theory, or constructive type theory, or Martin-Löf type theory or just Type Theory is a logical system and a set theory based on the principles of mathematical constructivism. Intuitionistic type theory was introduced by Per Martin-Löf, a Swedish mathematician and philosopher,...

(also called

*Constructive*type theory), which associated functional programs with constructive proofConstructive proof

In mathematics, a constructive proof is a method of proof that demonstrates the existence of a mathematical object with certain properties by creating or providing a method for creating such an object...

s of arbitrarily complex mathematical propositions expressed as dependent type

Dependent type

In computer science and logic, a dependent type is a type that depends on a value. Dependent types play a central role in intuitionistic type theory and in the design of functional programming languages like ATS, Agda and Epigram....

s. This led to powerful new approaches to interactive theorem proving

Interactive theorem proving

In computer science and mathematical logic, a proof assistant or interactive theorem prover is a software tool to assist with the development of formal proofs by man-machine collaboration...

and has influenced the development of many subsequent functional programming languages.

The Haskell language

Haskell (programming language)

Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...

began with a consensus in 1987 to form an open standard

Open standard

An open standard is a standard that is publicly available and has various rights to use associated with it, and may also have various properties of how it was designed . There is no single definition and interpretations vary with usage....

for functional programming research; implementation releases have been ongoing since 1990.

## Concepts

A number of concepts and paradigms are specific to functional programming, and generally foreign to imperative programmingImperative programming

In computer science, imperative programming is a programming paradigm that describes computation in terms of statements that change a program state...

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

### First-class and higher-order functions

Higher-order functionHigher-order function

In mathematics and computer science, higher-order functions, functional forms, or functionals are functions which do at least one of the following:*take one or more functions as an input*output a function...

s are functions that can either take other functions as arguments or return them as results (the differential operator

Differential operator

In mathematics, a differential operator is an operator defined as a function of the differentiation operator. It is helpful, as a matter of notation first, to consider differentiation as an abstract operation, accepting a function and returning another .This article considers only linear operators,...

that produces the derivative

Derivative

In calculus, a branch of mathematics, the derivative is a measure of how a function changes as its input changes. Loosely speaking, a derivative can be thought of as how much one quantity is changing in response to changes in some other quantity; for example, the derivative of the position of a...

of a function is an example of this in calculus).

Higher-order functions are closely related to first-class function

First-class function

In computer science, a programming language is said to have first-class functions if it treats functions as first-class objects. Specifically, this means that the language supports passing functions as arguments to other functions, returning them as the values from other functions, and assigning...

s, 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 partial application

Partial application

In computer science, partial application refers to the process of fixing a number of arguments to a function, producing another function of smaller arity...

or currying

Currying

In mathematics and computer science, currying is the technique of transforming a function that takes multiple arguments in such a way that it can be called as a chain of functions each with a single argument...

, 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. This allows one to succinctly express, for example, the successor function as the addition operator partially applied to the natural number one.

### Pure functions

Purely functionalPurely functional

Purely functional is a term in computing used to describe algorithms, data structures or programming languages that exclude destructive modifications...

functions (or expressions) have no memory or I/O side effects

Side effect (computer science)

In computer science, a function or expression is said to have a side effect if, in addition to returning a value, it also modifies some state or has an observable interaction with calling functions or the outside world...

. 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 optimizations such as memoizationMemoizationIn computing, memoization is an optimization technique used primarily to speed up computer programs by having function calls avoid repeating the calculation of results for previously processed inputs...

). - 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-safeThread-safeThread safety is a computer programming concept applicable in the context of multi-threaded programs. A piece of code is thread-safe if it only manipulates shared data structures in a thread-safe manner, which enables safe execution by multiple threads at the same time...

). - 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 deforestationDeforestation (computer science)In the theory of programming languages in computer science, deforestation is a program transformation to eliminate tree structures....

).

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 optimizations that involve those external functions. Some compilers, such as gcc

GNU Compiler Collection

The GNU Compiler Collection is a compiler system produced by the GNU Project supporting various programming languages. GCC is a key component of the GNU toolchain...

, add extra keywords for a programmer to explicitly mark external functions as pure, to enable such optimizations. Fortran 95 allows functions to be designated "pure".

### Recursion

IterationIteration

Iteration means the act of repeating a process usually with the aim of approaching a desired goal or target or result. Each repetition of the process is also called an "iteration," and the results of one iteration are used as the starting point for the next iteration.-Mathematics:Iteration in...

(looping) in functional languages is usually accomplished via recursion

Recursion

Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...

. Recursive function

Recursion (computer science)

Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem. The approach can be applied to many types of problems, and is one of the central ideas of computer science....

s 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 language standard requires implementations to recognize and optimize tail recursion. Tail recursion optimization can be implemented by transforming the program into continuation passing style during compiling, among other approaches.

Common patterns of recursion can be factored out using higher order functions, with catamorphism

Catamorphism

In category theory, the concept of catamorphism denotes the unique homomorphism from an initial algebra into some other algebra. The concept has been applied to functional programming as folds.The dual concept is that of anamorphism...

s and anamorphism

Anamorphism

Anamorphosis is a distorted projection or perspective requiring the viewer to use special devices or occupy a specific vantage point to reconstitute the image...

s (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.

Most general purpose functional programming languages allow unrestricted recursion and are Turing complete, which makes the halting problem

Halting problem

In computability theory, the halting problem can be stated as follows: Given a description of a computer program, decide whether the program finishes running or continues to run forever...

undecidable

Undecidable problem

In computability theory and computational complexity theory, an undecidable problem is a decision problem for which it is impossible to construct a single algorithm that always leads to a correct yes-or-no answer....

, can cause unsoundness of equational reasoning, and generally requires the introduction of inconsistency into the logic expressed by the language's type system

Type system

A type system associates a type with each computed value. By examining the flow of these values, a type system attempts to ensure or prove that no type errors can occur...

. Some special purpose languages such as Coq

Coq

In computer science, Coq is an interactive theorem prover. It allows the expression of mathematical assertions, mechanically checks proofs of these assertions, helps to find formal proofs, and extracts a certified program from the constructive proof of its formal specification...

allow only well-founded recursion and are strongly normalizing (nonterminating computations can be expressed only with infinite streams of values called codata). As a consequence, these languages fail to be Turing complete and expressing certain functions in them is impossible, but they can still express a wide class of interesting computations while avoiding the problems introduced by unrestricted recursion. Functional programming limited to well-founded recursion with a few other constraints is called total functional programming

Total functional programming

Total functional programming is a programming paradigm that restricts the range of programs to those that are provably terminating....

. See Turner 2004 for more discussion.

### Strict versus non-strict evaluation

Functional languages can be categorized by whether they use*strict (eager)*or*non-strict (lazy)*evaluation, concepts that refer to how function arguments are processed when an expression is being evaluated. The technical difference is in the denotational semanticsDenotational semantics

In computer science, denotational semantics is an approach to formalizing the meanings of programming languages by constructing mathematical objects which describe the meanings of expressions from the languages...

of expressions containing failing or divergent computations. Under strict evaluation, the evaluation of any term containing a failing subterm will itself fail. For example, the expression:

print length([2+1, 3*2, 1/0, 5-4])

will fail under strict evaluation because of the division by zero in the third element of the list. Under nonstrict evaluation, the length function will return the value 4, since evaluating it will not attempt to evaluate the terms making up the list. In brief, strict evaluation always fully evaluates function arguments before invoking the function. Non-strict evaluation does not evaluate function arguments unless their values are required to evaluate the function call itself.

The usual implementation strategy for non-strict evaluation in functional languages is graph reduction

Graph reduction

In computer science, graph reduction implements an efficient version of non-strict evaluation, an evaluation strategy where the arguments to a function are not immediately evaluated. This form of non-strict evaluation is also known as lazy evaluation and used in functional programming languages...

. Non-strict evaluation is used by default in several pure functional languages, including Miranda, Clean and Haskell

Haskell (programming language)

Haskell is a standardized, general-purpose purely functional programming language, with non-strict semantics and strong static typing. It is named after logician Haskell Curry. In Haskell, "a function is a first-class citizen" of the programming language. As a functional programming language, the...

.

Hughes 1984 argues for non-strict evaluation as a mechanism for improving program modularity through separation of concerns

Separation of concerns

In computer science, separation of concerns is the process of separating a computer program into distinct features that overlap in functionality as little as possible. A concern is any piece of interest or focus in a program. Typically, concerns are synonymous with features or behaviors...

, by easing independent implementation of producers and consumers of data streams. Launchbury 1993 describes some difficulties that lazy evaluation introduces, particularly in analyzing a program's storage requirements, and proposes an operational semantics

Operational semantics

In computer science, operational semantics is a way to give meaning to computer programs in a mathematically rigorous way. Operational semantics are classified into two categories: structural operational semantics formally describe how the individual steps of a computation take place in a...

to aid in such analysis. Harper 2009 proposes including both strict and nonstrict evaluation in the same language, using the language's type system to distinguish them.

### Type systems

Especially since the development of Hindley–Milner type inference in the 1970s, functional programming languages have tended to use typed lambda calculusTyped lambda calculus

A typed lambda calculus is a typed formalism that uses the lambda-symbol to denote anonymous function abstraction. In this context, types are usually objects of a syntactic nature that are assigned to lambda terms; the exact nature of a type depends on the calculus considered...

, as opposed to the untyped lambda calculus used in Lisp and its variants (such as Scheme). The use of algebraic datatypes and pattern matching

Pattern matching

In computer science, pattern matching is the act of checking some sequence of tokens for the presence of the constituents of some pattern. In contrast to pattern recognition, the match usually has to be exact. The patterns generally have the form of either sequences or tree structures...

makes manipulation of complex data structures convenient and expressive; the presence of strong compile-time type checking makes programs more reliable, while type inference

Type inference

Type inference refers to the automatic deduction of the type of an expression in a programming language. If some, but not all, type annotations are already present it is referred to as type reconstruction....

frees the programmer from the need to manually declare types to the compiler.

Some research-oriented functional languages such as Coq

Coq

In computer science, Coq is an interactive theorem prover. It allows the expression of mathematical assertions, mechanically checks proofs of these assertions, helps to find formal proofs, and extracts a certified program from the constructive proof of its formal specification...

, Agda, Cayenne, and Epigram are based on intuitionistic type theory

Intuitionistic type theory

Intuitionistic type theory, or constructive type theory, or Martin-Löf type theory or just Type Theory is a logical system and a set theory based on the principles of mathematical constructivism. Intuitionistic type theory was introduced by Per Martin-Löf, a Swedish mathematician and philosopher,...

, which allows types to depend on terms. Such types are called dependent type

Dependent type

In computer science and logic, a dependent type is a type that depends on a value. Dependent types play a central role in intuitionistic type theory and in the design of functional programming languages like ATS, Agda and Epigram....

s. These type systems do not have decidable type inference and are difficult to understand and program with. But dependent types can express arbitrary propositions in predicate logic

Predicate logic

In mathematical logic, predicate logic is the generic term for symbolic formal systems like first-order logic, second-order logic, many-sorted logic or infinitary logic. This formal system is distinguished from other systems in that its formulae contain variables which can be quantified...

. Through the Curry–Howard isomorphism, then, well-typed programs in these languages become a means of writing formal mathematical proof

Mathematical proof

In mathematics, a proof is a convincing demonstration that some mathematical statement is necessarily true. Proofs are obtained from deductive reasoning, rather than from inductive or empirical arguments. That is, a proof must demonstrate that a statement is true in all cases, without a single...

s from which a compiler can generate certified code

Formal verification

In the context of hardware and software systems, formal verification is the act of proving or disproving the correctness of intended algorithms underlying a system with respect to a certain formal specification or property, using formal methods of mathematics .- Usage :Formal verification can be...

. While these languages are mainly of interest in academic research (including in formalized mathematics), they have begun to be used in engineering as well. Compcert

Compcert

CompCert is a formally verified optimizing compiler for a subset of the C programming language which currently targets PowerPC, ARM and 32-bit x86 architectures. This project, led by Xavier Leroy, started officially in 2005, funded by the French institutes ANR and INRIA. The compiler is...

is a compiler

Compiler

A compiler is a computer program that transforms source code written in a programming language into another computer language...

for a subset of the C programming language

C (programming language)

C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....

that is written in Coq and formally verified.

A limited form of dependent types called generalized algebraic data type

Generalized Algebraic Data Type

In functional programming, a generalized algebraic data type is a generalization of the algebraic data types of Haskell and ML, applying to parametric types.With this extension, the parameters of the return type of a data constructor can be freely chosen when declaring...

s (GADT's) can be implemented in a way that provides some of the benefits of dependently-typed programming while avoiding most of its inconvenience. GADT's are available in the Glasgow Haskell Compiler

Glasgow Haskell Compiler

The Glorious Glasgow Haskell Compilation System, more commonly known as the Glasgow Haskell Compiler or GHC, is an open source native code compiler for the functional programming language Haskell. The lead developers are Simon Peyton Jones and Simon Marlow...

and in Scala (as "case classes"), and have been proposed as additions to other languages including Java and C#.

### Functional programming in non-functional languages

It is possible to use a functional style of programming in languages that are not traditionally considered functional languages. Among imperative programming languages, the DD (programming language)

The D programming language is an object-oriented, imperative, multi-paradigm, system programming language created by Walter Bright of Digital Mars. It originated as a re-engineering of C++, but even though it is mainly influenced by that language, it is not a variant of C++...

programming language's solid support for functional programming stands out. For example, D has a pure modifier to enforce functional purity. Only Fortran 95 has something similar.

First class functions have slowly been added to mainstream languages. For example, in early 1994, support for lambda, filter, map, and reduce was added to Python

Python (programming language)

Python is a general-purpose, high-level programming language whose design philosophy emphasizes code readability. Python claims to "[combine] remarkable power with very clear syntax", and its standard library is large and comprehensive...

. Then during the development of Python 3000, Guido van Rossum

Guido van Rossum

Guido van Rossum is a Dutch computer programmer who is best known as the author of the Python programming language. In the Python community, Van Rossum is known as a "Benevolent Dictator For Life" , meaning that he continues to oversee the Python development process, making decisions where necessary...

called for the removal of these features. So far, only the

`reduce`

function has been removed, and it remains accessible via the `functools`

standard library module. First class functions were also introduced in PHPPHP

PHP is a general-purpose server-side scripting language originally designed for web development to produce dynamic web pages. For this purpose, PHP code is embedded into the HTML source document and interpreted by a web server with a PHP processor module, which generates the web page document...

5.3, Visual Basic

Visual Basic

Visual Basic is the third-generation event-driven programming language and integrated development environment from Microsoft for its COM programming model...

9, C# 3.0, and C++11.

The Language Integrated Query

Language Integrated Query

Language Integrated Query is a Microsoft .NET Framework component that adds native data querying capabilities to .NET languages, although ports exist for Java, PHP and JavaScript....

(LINQ) feature, with its many incarnations, is an obvious and powerful use of functional programming in .NET

.NET Framework

The .NET Framework is a software framework that runs primarily on Microsoft Windows. It includes a large library and supports several programming languages which allows language interoperability...

.

In Java

Java (programming language)

Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...

, anonymous classes can sometimes be used to simulate closure

Closure (computer science)

In computer science, a closure is a function together with a referencing environment for the non-local variables of that function. A closure allows a function to access variables outside its typical scope. Such a function is said to be "closed over" its free variables...

s; however, anonymous classes are not always proper replacements to closure

Closure (computer science)

In computer science, a closure is a function together with a referencing environment for the non-local variables of that function. A closure allows a function to access variables outside its typical scope. Such a function is said to be "closed over" its free variables...

s because they have more limited capabilities.

Many object-oriented design pattern

Design pattern (computer science)

In software engineering, a design pattern is a general reusable solution to a commonly occurring problem within a given context in software design. A design pattern is not a finished design that can be transformed directly into code. It is a description or template for how to solve a problem that...

s are expressible in functional programming terms: for example, the strategy pattern

Strategy pattern

In computer programming, the strategy pattern is a particular software design pattern, whereby algorithms can be selected at runtime. Formally speaking, the strategy pattern defines a family of algorithms, encapsulates each one, and makes them interchangeable...

simply dictates use of a higher-order function, and the visitor pattern roughly corresponds to a catamorphism

Catamorphism

In category theory, the concept of catamorphism denotes the unique homomorphism from an initial algebra into some other algebra. The concept has been applied to functional programming as folds.The dual concept is that of anamorphism...

, or fold

Fold (higher-order function)

In functional programming, fold – also known variously as reduce, accumulate, compress, or inject – are a family of higher-order functions that analyze a recursive data structure and recombine through use of a given combining operation the results of recursively processing its...

.

The benefits of immutable data can be seen even in imperative programs, so programmers often strive to make some data immutable even in imperative programs.

## Comparison to imperative programming

Functional programming is very different from imperative programmingImperative programming

In computer science, imperative programming is a programming paradigm that describes computation in terms of statements that change a program state...

. The most significant differences stem from the fact that functional programming avoids side effects

Side effect (computer science)

In computer science, a function or expression is said to have a side effect if, in addition to returning a value, it also modifies some state or has an observable interaction with calling functions or the outside world...

, 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 program would use a different technique. It would use a higher-order function that takes as arguments a function and a list. The higher-order function would then apply the given function to each element of the given list and then return a new list with 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

Haskell (programming language)

implements them using monads, derived from category theory

Category theory

Category theory is an area of study in mathematics that examines in an abstract way the properties of particular mathematical concepts, by formalising them as collections of objects and arrows , where these collections satisfy certain basic conditions...

. Monads offer a way to abstract certain types of computational patterns, including (but not limited to) modeling of computations with mutable state (and other side effects such as I/O) in an imperative manner without losing purity. While existing monads may be easy to apply in a program, given appropriate templates and examples, many students find them difficult to understand conceptually, e.g., when asked to define new monads (which is sometimes needed for certain types of libraries).

Impure functional languages usually include a more direct method of managing mutable state. Clojure, for example, uses managed references that can be updated by applying pure functions to the current state. This kind of approach enables mutability while still promoting the use of pure functions as the preferred way to express computations.

Alternative methods such as Hoare logic

Hoare logic

Hoare logic is a formal system with a set of logical rules for reasoning rigorously about the correctness of computer programs. It was proposed in 1969 by the British computer scientist and logician C. A. R. Hoare, and subsequently refined by Hoare and other researchers...

and uniqueness

Uniqueness type

In computing, a unique type guarantees that an object is used in a single-threaded way, with at most a single reference to it. If a value has a unique type, a function applied to it can be optimized to update the value in-place in the object code. In-place updates improve the efficiency of...

have been developed to track side effects in programs. Some modern research languages use effect system

Effect system

An effect system is a formal system which describes the computational effects of computer programs, such as side effects. An effect system can be used to provide a compile-time checking of the possible effects of the program....

s to make explicit the presence of side effects.

### Efficiency issues

Functional programming languages are typically less efficient in their use of CPUCentral processing unit

The central processing unit is the portion of a computer system that carries out the instructions of a computer program, to perform the basic arithmetical, logical, and input/output operations of the system. The CPU plays a role somewhat analogous to the brain in the computer. The term has been in...

and memory than imperative languages such as C and Pascal

Pascal (programming language)

Pascal is an influential imperative and procedural programming language, designed in 1968/9 and published in 1970 by Niklaus Wirth as a small and efficient language intended to encourage good programming practices using structured programming and data structuring.A derivative known as Object Pascal...

. For purely functional languages, the worst-case slowdown is logarithmic in the number of memory cells used, because mutable memory can be represented by a purely functional data structure with logarithmic access time (such as a balanced tree). However, such slowdowns are not universal. For programs that perform intensive numerical computations, functional languages such as Objective Caml

Objective Caml

OCaml , originally known as Objective Caml, is the main implementation of the Caml programming language, created by Xavier Leroy, Jérôme Vouillon, Damien Doligez, Didier Rémy and others in 1996...

and Clean are only slightly slower than C

C (programming language)

C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....

. For programs that handle large matrices

Matrix (mathematics)

In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions. The individual items in a matrix are called its elements or entries. An example of a matrix with six elements isMatrices of the same size can be added or subtracted element by element...

and multidimensional database

Database

A database is an organized collection of data for one or more purposes, usually in digital form. The data are typically organized to model relevant aspects of reality , in a way that supports processes requiring this information...

s, array

Array programming

In computer science, array programming languages generalize operations on scalars to apply transparently to vectors, matrices, and higher dimensional arrays....

functional languages (such as J

J (programming language)

The J programming language, developed in the early 1990s by Kenneth E. Iverson and Roger Hui, is a synthesis of APL and the FP and FL function-level languages created by John Backus....

and K

K (programming language)

K is a proprietary array processing language developed by Arthur Whitney and commercialized by Kx Systems. The language serves as the foundation for kdb, an in-memory, column-based database, and other related financial products. The language, originally developed in 1993, is a variant of APL and...

) were designed with speed optimization.

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, thus increasing opportunities for inline expansion

Inline expansion

In computing, inline expansion, or inlining, is a manual or compiler optimization that replaces a function call site with the body of the callee. This optimization may improve time and space usage at runtime, at the possible cost of increasing the final size of the program In computing, inline...

.

Lazy evaluation

Lazy evaluation

In programming language theory, lazy evaluation or call-by-need is an evaluation strategy which delays the evaluation of an expression until the value of this is actually required and which also avoids repeated evaluations...

may also speed up the program, even asymptotically, whereas it may slow it down at most by a constant factor (however, it may introduce memory leaks when used improperly). Launchbury 1993 discusses theoretical issues related to memory leaks from lazy evaluation, and O'Sullivan

*et al.*2008 give some practical advice for analyzing and fixing them.### 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 illustrates this with two solutions to the same programming goal (calculating Fibonacci numberFibonacci number

In mathematics, the Fibonacci numbers are the numbers in the following integer sequence:0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots\; ....

s). The imperative example is in C++

C++

C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...

.