A number of concepts and paradigms are specific to functional programming, and generally foreign to
imperative programming (including
object-oriented programming). However, programming languages often cater to several programming paradigms, so programmers using "mostly imperative" languages may have utilized some of these concepts.
First-class and higher-order functions Higher-order functions are functions that can either take other functions as arguments or return them as results. In calculus, an example of a higher-order function is the
differential operator d/dx, which returns the
derivative of a function f. 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 for 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 that applies a function to its arguments one at a time, with each application returning a new function that accepts the next argument. This lets a programmer succinctly express, for example, the
successor function as the addition operator partially applied to the
natural number one.
Pure functions Pure functions (or expressions) have no
side effects (memory or I/O). 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 arguments that cause no side-effects, the result is constant with respect to that argument list (sometimes called
referential transparency or
idempotence), i.e., calling the pure function again with the same arguments returns the same result. (This can enable caching optimizations such as
memoization.) • If there is no data dependency between two pure expressions, their order can be reversed, or they can be performed in
parallel and they cannot interfere with one another (in other terms, the evaluation of any pure expression is
thread-safe). • If the entire language does not allow side-effects, then any evaluation strategy can be used; this gives the compiler freedom to reorder or combine the evaluation of expressions in a program (for example, using
deforestation). 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 also lets functions be designated
pure. C++11 added constexpr keyword with similar semantics.
Recursion Iteration (looping) in functional languages is usually accomplished via
recursion.
Recursive functions invoke themselves, letting an operation be repeated until it reaches the
base case. In general, recursion requires maintaining a
stack, which consumes space in a linear amount to the depth of recursion. This could make recursion prohibitively expensive to use instead of imperative loops. However, a special form of recursion known as
tail recursion can be recognized and optimized by a compiler into the same code used to implement iteration in imperative languages. Tail recursion optimization can be implemented by transforming the program into
continuation passing style during compiling, among other approaches. The
Scheme language standard requires implementations to support proper tail recursion, meaning they must allow an unbounded number of active tail calls. Proper tail recursion is not simply an optimization; it is a language feature that assures users that they can use recursion to express a loop and doing so would be safe-for-space. Moreover, contrary to its name, it accounts for all tail calls, not just tail recursion. While proper tail recursion is usually implemented by turning code into imperative loops, implementations might implement it in other ways. For example,
Chicken intentionally maintains a stack and lets the
stack overflow. However, when this happens, its
garbage collector will claim space back, allowing an unbounded number of active tail calls even though it does not turn tail recursion into a loop. Common patterns of recursion can be abstracted away using higher-order functions, with
catamorphisms and
anamorphisms (or "folds" and "unfolds") being the most obvious examples. Such recursion schemes 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
Rocq 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.
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 semantics of expressions containing failing or divergent computations. Under strict evaluation, the evaluation of any term containing a failing subterm fails. For example, the
Python statement: print(len([2 + 1, 3 * 2, 1 / 0, 5 - 4])) fails under strict evaluation because of the division by zero in the third element of the list. Under lazy evaluation, the length function returns the value 4 (i.e., the number of items in the list), since evaluating it does not attempt to evaluate the terms making up the list. In brief, strict evaluation always fully evaluates function arguments before invoking the function. Lazy evaluation does not evaluate function arguments unless their values are required to evaluate the function call itself. The usual implementation strategy for lazy evaluation in functional languages is
graph reduction. Lazy evaluation is used by default in several pure functional languages, including
Miranda,
Clean, and
Haskell. argues for lazy 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 lazy 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 calculus, rejecting all invalid programs at compilation time and risking
false positive errors, as opposed to the
untyped lambda calculus, that accepts all valid programs at compilation time and risks
false negative errors, used in Lisp and its variants (such as
Scheme), as they reject all invalid programs at runtime when the information is enough to not reject valid programs. The use of
algebraic data types makes manipulation of complex data structures convenient; the presence of strong compile-time type checking makes programs more reliable in absence of other reliability techniques like
test-driven development, while
type inference frees the programmer from the need to manually declare types to the compiler in most cases. Some research-oriented functional languages such as
Rocq,
Agda,
Cayenne, and
Epigram are based on
intuitionistic type theory, which lets types depend on terms. Such types are called
dependent types. 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
higher-order logic. Through the
Curry–Howard isomorphism, then, well-typed programs in these languages become a means of writing formal
mathematical proofs 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 language
C that is written in
Rocq and formally verified. A limited form of dependent types called
generalized algebraic data types (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, in
OCaml and in
Scala, and have been proposed as additions to other languages including Java and C#.
Referential transparency Functional programs do not have assignment statements, that is, the value of a variable in a functional program never changes once defined. This eliminates any chances of side effects because any variable can be replaced with its actual value at any point of execution. So, functional programs are referentially transparent. Consider
C assignment statement x = x * 10, this changes the value assigned to the variable x. Let us say that the initial value of x was 1, then two consecutive evaluations of the variable x yields 10 and 100 respectively. Clearly, replacing x = x * 10 with either 10 or 100 gives a program a different meaning, and so the expression
is not referentially transparent. In fact, assignment statements are never referentially transparent. Now, consider another function such as int plusOne(int x) { return x + 1; }
is transparent, as it does not implicitly change the input x and thus has no such
side effects. Functional programs exclusively use this type of function and are therefore referentially transparent.
Data structures Purely functional
data structures are often represented in a different way to their
imperative counterparts. For example, the
array with constant access and update times is a basic component of most imperative languages, and many imperative data-structures, such as the
hash table and
binary heap, are based on arrays. Arrays can be replaced by
maps or random access lists, which admit purely functional implementation, but have
logarithmic access and update times. Purely functional data structures have
persistence, a property of keeping previous versions of the data structure unmodified. In Clojure, persistent data structures are used as functional alternatives to their imperative counterparts. Persistent vectors, for example, use trees for partial updating. Calling the insert method will result in some but not all nodes being created. == Comparison to imperative programming ==