Functional programming is a style of programming which models computationsas the evaluation of expressions. This article is meant to describe itbriefly; however, the best way to understand functional programming is tolearn the basics of one of the functional programming languages(such asHaskell).
In functional programming, programs are executed by evaluatingexpressions, in contrast with imperative programming where programsare composed ofstatements which change globalstate when executed.Functional programming typically avoids using mutable state.
Functional programming requires that functions arefirst-class, whichmeans that they are treated like any other values and can be passed asarguments to other functions or be returned as a result of a function.Being first-class also means that it is possible to define and manipulatefunctions from within other functions. Special attention needs to be givento functions that reference local variables from their scope. If such afunction escapes their block after being returned from it, the localvariables must be retained in memory, as they might be needed later whenthe function is called. Often it is difficult to determine statically whenthose resources can be released, so it is necessary to use automaticmemory management.
Many programming languages support programming in both functional andimperative style but the syntax and facilities of a language are typicallyoptimised for only one of these styles, and social factors like codingconventions and libraries often force the programmer towards one of thestyles. Therefore, programming languages may be categorized into functionaland imperative ones.
The following table shows which languages support functional programming (bysupporting first-class functions) and for which the functional style is thedominant 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 |
Higher-order functions (HOFs) are functions thattake other functions as their arguments. A basic example of a HOF ismap which takes a function and a list as its arguments, appliesthe 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 alist without using loops or recursion:
subtractTwoFromList l = map (\x -> x - 2) l
We can generalize this function to subtract any given number:
subtractFromList l y = map (\x -> x - y) l
The function given tomap then becomes aclosure because\x -> x - y references a local variabley fromoutside its body.
Higher-order functions are very useful for refactoring code and reduce theamount of repetition. For example, typically mostfor loops can beexpressed using maps orfolds. Custom iteration schemes, such as parallelloops, can be easily expressed using HOFs.
Higher-order functions are often used to implementdomain-specific languages embedded inHaskell as combinator libraries.
Higher-order functions can be usually simulated in object-oriented languagesby functions that takefunction-objects, also calledfunctors (notethatfunctor in Haskell is an entirely different concept). Variables fromthe scope of the call can be bound inside the function-object which acts as ifit were a closure. This way of simulating HOFs is, however, very verbose andrequires declaring a new class each time we want to use a HOF.
Nearly all functional languages contain apure subset that is alsouseful as a programming language. But the semantics of some functionallanguages makes it all too easy to turn a pureexpression into somethingthat can cause other visible changes when computed. Such changes are calledside effects to emphasize that a definition's value, once computed, is itsmost important attribute.
In contrast, Haskell's non-strict semantics promotes the use of its puresubset - even allowing, for example, infinite data structures to be definedand used. Being non-strict means side effects have no pre-determined order.This confines their use toactions, whose ordering is commonlyspecified by using themonadic inteface (but there areother options, including thecomonadic andarrow-basedinterfaces).
In Haskell, it is usually beneficial to write a significant part of a programor library in a purely functional fashion and keep the code involving stateand I/O to the minimum as impure code is more prone to errors. Of course, inpure languages that prohibit side effects completely, there is no impure code.
Purely functional programs typically operate onimmutable data. Insteadof altering existing values, altered copies are created and the original ispreserved. Since the unchanged parts of the structure cannot be modified,they can often be shared between the old and new copies, which saves memory.
Pure computations yield the same value each time they are invoked. Thisproperty is calledreferential transparency and makes possible to conductequational reasoning on the code. For instance ify = f x andg = h y y then we should be able to replace the definition ofg withg = h (f x) (f x) and get the same result;only the efficiency might change.
If a pure computation is referentially transparent then so are itssub-computations. This makes it much easier to run those puresub-computationsin parallel to obtain the result of theentire computation.
Recursion is heavily used in functional programming as it is the canonicaland often the only way toiterate. Functional language implementationswill often includetail call optimisation to ensure thatheavy recursion does not consume excessive memory.
Functional programming is known to provide better support forstructuredprogramming than imperative programming. To make a program structured it isnecessary to developabstractions and split it intocomponents whichinterface each other with those abstractions. Functional languages aid thisby making it easy to create clean and simple abstractions. It is easy,for instance, to abstract out a recurring piece of code by creating ahigher-order function, which will make the resulting code more declarativeand comprehensible.
Functional programs are often shorter and easier to understand than theirimperative counterparts. Since various studies have shown that the averageprogrammer's productivity in terms of lines of code is more or less the samefor any programming language, this translates also to higher productivity.