Functional programming
Functional programming is a style of programming which models computations as the evaluation of expressions. This article is meant to describe it briefly; however, the best way to understand functional programming is to learn the basics of one of the functional programming languages (such as Haskell).
What is functional programming?
In functional programming, programs are executed by evaluating expressions, in contrast with imperative programming where programs are composed of statements which change global state when executed. Functional programming typically avoids using mutable state.
Functional programming requires that functions are first-class, which means that they are treated like any other values and can be passed as arguments to other functions or be returned as a result of a function. Being first-class also means that it is possible to define and manipulate functions from within other functions. Special attention needs to be given to functions that reference local variables from their scope. If such a function escapes their block after being returned from it, the local variables must be retained in memory, as they might be needed later when the function is called. Often it is difficult to determine statically when those resources can be released, so it is necessary to use automatic memory management.
Functional vs imperative languages
Many programming languages support programming in both functional and imperative style but the syntax and facilities of a language are typically optimised for only one of these styles, and social factors like coding conventions and libraries often force the programmer towards one of the styles. Therefore, programming languages may be categorized into functional and imperative ones.
The following table shows which languages support functional programming (by supporting first-class functions) and for which the functional style is the dominant one.
| Language | Closures | Functional |
|---|---|---|
| C | No | No |
| Pascal | No | No |
| C++ | Yes | No |
| Java | Yes | No |
| Modula-3 | Yes | No |
| Python | Yes | No |
| Ruby | Yes | No |
| D (2.0) | Yes | No |
| Ocaml | Yes | Yes |
| Erlang | Yes | Yes |
| Haskell | Yes | Yes |
Features of functional languages
Higher-order functions
Higher-order functions (HOFs) are functions that
take other functions as their arguments. A basic example of a HOF is
map which takes a function and a list as its arguments, applies
the function to all elements of the list, and returns the list of its results.
For instance, we can write a function that subtracts 2 from all elements of a
list without using loops or recursion:
subtractTwoFromList l = map (\x -> x - 2) lWe can generalize this function to subtract any given number:
subtractFromList l y = map (\x -> x - y) lThe function given to map then becomes a closure because
\x -> x - y references a local variable y from
outside its body.
Higher-order functions are very useful for refactoring code and reduce the amount of repetition. For example, typically most for loops can be expressed using maps or folds. Custom iteration schemes, such as parallel loops, can be easily expressed using HOFs.
Higher-order functions are often used to implement domain-specific languages embedded in Haskell as combinator libraries.
Higher-order functions can be usually simulated in object-oriented languages by functions that take function-objects, also called functors (note that functor in Haskell is an entirely different concept). Variables from the scope of the call can be bound inside the function-object which acts as if it were a closure. This way of simulating HOFs is, however, very verbose and requires declaring a new class each time we want to use a HOF.
Non-strict semantics
Nearly all functional languages contain a pure subset that is also useful as a programming language. But the semantics of some functional languages makes it all too easy to turn a pure expression into something that can cause other visible changes when computed. Such changes are called side effects to emphasize that a definition's value, once computed, is its most important attribute.
In contrast, Haskell's non-strict semantics promotes the use of its pure subset - even allowing, for example, infinite data structures to be defined and used. Being non-strict means side effects have no pre-determined order. This confines their use to actions, whose ordering is commonly specified by using the monadic inteface (but there are other options, including the comonadic and arrow-based interfaces).
In Haskell, it is usually beneficial to write a significant part of a program or library in a purely functional fashion and keep the code involving state and I/O to the minimum as impure code is more prone to errors. Of course, in pure languages that prohibit side effects completely, there is no impure code.
Immutable data
Purely functional programs typically operate on immutable data. Instead of altering existing values, altered copies are created and the original is preserved. Since the unchanged parts of the structure cannot be modified, they can often be shared between the old and new copies, which saves memory.
Referential transparency
Pure computations yield the same value each time they are invoked. This
property is called referential transparency and makes possible to conduct
equational reasoning on the code. For instance if y = f x and
g = h y y then we should be able to replace the definition of
g with g = h (f x) (f x) and get the same result;
only the efficiency might change.
Parallelism
If a pure computation is referentially transparent then so are its sub-computations. This makes it much easier to run those pure sub-computations in parallel to obtain the result of the entire computation.
Recursion
Recursion is heavily used in functional programming as it is the canonical and often the only way to iterate. Functional language implementations will often include tail call optimisation to ensure that heavy recursion does not consume excessive memory.
Benefits of functional programming
Functional programming is known to provide better support for structured programming than imperative programming. To make a program structured it is necessary to develop abstractions and split it into components which interface each other with those abstractions. Functional languages aid this by making it easy to create clean and simple abstractions. It is easy, for instance, to abstract out a recurring piece of code by creating a higher-order function, which will make the resulting code more declarative and comprehensible.
Functional programs are often shorter and easier to understand than their imperative counterparts. Since various studies have shown that the average programmer's productivity in terms of lines of code is more or less the same for any programming language, this translates also to higher productivity.
Books
- Khan, Aslam. Grokking Functional Programming. Manning Publications (2015). p. 475. ISBN 9781617291838