Personal tools

Functional programming

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
m (some typos)
(C++ supports closures since August 2011.)
 
(7 intermediate revisions by 5 users not shown)
Line 1: Line 1:
'''Functional programming''' is a style of programming which unlike '''imperative programming''' 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 ([[Haskell in 5 steps|learn Haskell]]).
+
[[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 ([[Haskell in 5 steps|learn Haskell]]).
 
You can find an old version of this page [[Functional programming/Old version|here]].
 
   
 
==What is functional programming?==
 
==What is functional programming?==
'''Functional programming''' means that programs are executed by evaluating '''expressions'''. This contrasts with '''imperative programming''' where programs are composed of '''statements''' which change global '''state''' when executed. Functional programming, on the other hand, avoids using state and mutable data.
+
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 '''nested''' in code blocks. Special attention needs to be given to nested functions, called '''[[closure]]s''', 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. Usually it is not possible to determine the moment of release statically which means that an automatic [[memory management]] technique has to be used.
+
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==
 
==Functional vs imperative languages==
   
Many programming languages support programming in both functional and imperative styles, however each language has '''syntax''' and facilities that are optimised only for one of these styles. Often, code written in one particular style and not the other is executed efficiently by the implementations. In addition to that, coding conventions and libraries often force the programmer to use one of the styles. Therefore, programming languages are categorized into functional and imperative ones.
+
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.
   
Following table shows which languages support functional programming (by supporting closures) and for which the functional style is the dominant one.
+
The following table shows which languages support functional programming (by supporting first-class functions) and for which the functional style is the dominant one.
 
{| class="wikitable"
 
{| class="wikitable"
 
|-
 
|-
Line 17: Line 17:
 
! Functional
 
! Functional
 
|-
 
|-
! C/C++
+
! C
 
| No || No
 
| No || No
 
|-
 
|-
 
! Pascal
 
! Pascal
 
| No || No
 
| No || No
  +
|-
  +
! C++
  +
| Yes || No
 
|-
 
|-
 
! Java
 
! Java
Line 39: Line 42:
 
|-
 
|-
 
! Ocaml
 
! Ocaml
  +
| Yes || Yes
  +
|-
  +
! Erlang
 
| Yes || Yes
 
| Yes || Yes
 
|-
 
|-
Line 47: Line 53:
 
==Features of functional languages==
 
==Features of functional languages==
 
===Higher-order functions===
 
===Higher-order functions===
[[Higher order function|Higher-order function]]s ('''HOFs''') are functions that take other functions as their arguments. Basic example of a HOF is <hask>map</hask> which takes a function and a list as its arguments, applies the function to all elements of the list and returns a 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:
+
[[Higher order function|Higher-order function]]s (HOFs) are functions that take other functions as their arguments. A basic example of a HOF is <hask>map</hask> 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:
 
<haskell>
 
<haskell>
 
subtractTwoFromList l = map (\x -> x - 2) l
 
subtractTwoFromList l = map (\x -> x - 2) l
Line 55: Line 61:
 
subtractFromList l y = map (\x -> x - y) l
 
subtractFromList l y = map (\x -> x - y) l
 
</haskell>
 
</haskell>
The function given to <hask>map</hask> then becomes a [[closure]] because <hask>\x -> x - y</hask> references a local variable <hask>y</hask> from the outside of its body.
+
The function given to <hask>map</hask> then becomes a [[closure]] because <hask>\x -> x - y</hask> references a local variable <hask>y</hask> from outside its body.
   
Higher-order functions are very useful for refactoring the code and reduce the amount of repetition. For example, typically most of the ''for'' loops can be expressed using maps or [[fold]]s. Custom iteration schemes, such as parallel loops, can be easily expressed using HOFs.
+
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 [[fold]]s. Custom iteration schemes, such as parallel loops, can be easily expressed using HOFs.
   
Higher-order functions are often used to implement '''[[Embedded domain specific language|domain-specific languages]]''' embedded in Haskell as '''combinator libraries'''.
+
Higher-order functions are often used to implement [[Embedded domain specific language|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.
 
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.
   
 
===Purity===
 
===Purity===
Some functional languages allow expressions to yield actions in addition to return values. These actions are called '''side effects''' to stress out that the return value is the most important outcome of a function (as opposed to imperative programming). Languages that prohibit side effects are called '''pure'''. Even though some functional languages are impure they often contain a '''pure subset''' that is a also useful as a programming language. It is usually beneficial to write a significant part of a functional program in a purely functional fashion and keep the code involving state and I/O to the minimum as it is more prone to errors.
+
Some functional languages allow expressions to yield actions in addition to return values. These actions are called ''side effects'' to emphasize that the return value is the most important outcome of a function (as opposed to the case in imperative programming). Languages that prohibit side effects are called ''pure''. Even though some functional languages are impure they often contain a pure subset that is also useful as a programming language. It is usually beneficial to write a significant part of a functional program 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.
   
 
====Immutable data====
 
====Immutable data====
Purely functional programms operate only on '''immutable''' data. This is possible because on each modification a new version of a data structure is created and the old one is preserved. Therefore, data structures are '''persistent''' as it is possible to refer also to old versions of them. If there are no more references to the old version the unreferred data can be collected by automatic [[memory management]], such as a garbage collector. Often, bigger data structures '''share''' their parts between versions and do not consume as much memory as all versions separately.
+
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====
 
====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 <hask>y = f x</hask> and <hask>g = h y y</hask> then we should be able to replace the definition of <hask>g</hask> with <hask>g = h (f x) (f x)</hask> and get the same result, only the efficiency might change.
+
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 <hask>y = f x</hask> and <hask>g = h y y</hask> then we should be able to replace the definition of <hask>g</hask> with <hask>g = h (f x) (f x)</hask> and get the same result; only the efficiency might change.
   
 
====Lazy evaluation====
 
====Lazy evaluation====
Since pure computations are referentially transparent they can be performed at any time and still yield the same result. This makes it possible to defer the computation of values until they are needed, that is to compute them ''lazily''. '''[[Lazy evaluation]]''' avoids unnecessary computations and allows, for instance, to create '''lazy data structures''' that are built on the fly.
+
Since pure computations are referentially transparent they can be performed at any time and still yield the same result. This makes it possible to defer the computation of values until they are needed, that is, to compute them ''lazily''. ''[[Lazy evaluation]]'' avoids unnecessary computations and allows, for example, infinite data structures to be defined and used.
   
 
====Purity and effects====
 
====Purity and effects====
 
Even though purely functional programming is very beneficial, the programmer might want to use features that are not available in pure programs, like efficient mutable arrays or convenient I/O. There are two approaches to this problem.
 
Even though purely functional programming is very beneficial, the programmer might want to use features that are not available in pure programs, like efficient mutable arrays or convenient I/O. There are two approaches to this problem.
  +
 
=====Side effects in the language=====
 
=====Side effects in the language=====
Some functional languages extend their purely functional core with side effects. The programmer must make sure himself that he doesn't use impure functions in places where only pure functions are expected.
+
Some functional languages extend their purely functional core with side effects. The programmer must be careful not to use impure functions in places where only pure functions are expected.
   
 
=====Side effects through monads=====
 
=====Side effects through monads=====
 
Another way of introducing side effects to a pure language is to simulate them using [[monad]]s. While the language remains pure and referentially transparent, monads can provide implicit state by threading it inside them. The compiler does not even have to 'know' about the imperative features because the language itself remains pure, however usually the implementations do 'know' about them due to the efficiency reasons, for instance to provide <math>O(1)</math> mutable arrays.
 
Another way of introducing side effects to a pure language is to simulate them using [[monad]]s. While the language remains pure and referentially transparent, monads can provide implicit state by threading it inside them. The compiler does not even have to 'know' about the imperative features because the language itself remains pure, however usually the implementations do 'know' about them due to the efficiency reasons, for instance to provide <math>O(1)</math> mutable arrays.
   
Allowing side effects only through monads and keeping the language pure makes it possible to have lazy evaluation that does not conflict with the effects of impure code. Even though the expressions are evaluated lazily, some parts of them are '''forced''' by monads to be evaluated in a specific order and the effects are properly '''sequenced'''.
+
Allowing side effects only through monads and keeping the language pure makes it possible to have lazy evaluation that does not conflict with the effects of impure code. Even though lazy expressions can be evaluated in any order, the monad structure forces the effects to be executed in the correct order.
   
 
===Recursion===
 
===Recursion===
'''Recursion''' is heavily used in functional programming as it is the canonical and often the only way to '''iterate'''. Loops are naturally expressed using '''tail 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 recursion|tail call optimisation]] to ensure that heavy recursion does not consume excessive memory.
   
 
==Benefits of functional programming==
 
==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 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.
 
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.

Latest revision as of 17:23, 31 January 2013

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 (learn Haskell).

Contents

[edit] 1 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.

[edit] 2 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

[edit] 3 Features of functional languages

[edit] 3.1 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) l

We can generalize this function to subtract any given number:

subtractFromList l y = map (\x -> x - y) l
The 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.

[edit] 3.2 Purity

Some functional languages allow expressions to yield actions in addition to return values. These actions are called side effects to emphasize that the return value is the most important outcome of a function (as opposed to the case in imperative programming). Languages that prohibit side effects are called pure. Even though some functional languages are impure they often contain a pure subset that is also useful as a programming language. It is usually beneficial to write a significant part of a functional program 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.

[edit] 3.2.1 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.

[edit] 3.2.2 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.

[edit] 3.2.3 Lazy evaluation

Since pure computations are referentially transparent they can be performed at any time and still yield the same result. This makes it possible to defer the computation of values until they are needed, that is, to compute them lazily. Lazy evaluation avoids unnecessary computations and allows, for example, infinite data structures to be defined and used.

[edit] 3.2.4 Purity and effects

Even though purely functional programming is very beneficial, the programmer might want to use features that are not available in pure programs, like efficient mutable arrays or convenient I/O. There are two approaches to this problem.

[edit] 3.2.4.1 Side effects in the language

Some functional languages extend their purely functional core with side effects. The programmer must be careful not to use impure functions in places where only pure functions are expected.

[edit] 3.2.4.2 Side effects through monads

Another way of introducing side effects to a pure language is to simulate them using monads. While the language remains pure and referentially transparent, monads can provide implicit state by threading it inside them. The compiler does not even have to 'know' about the imperative features because the language itself remains pure, however usually the implementations do 'know' about them due to the efficiency reasons, for instance to provide O(1) mutable arrays.

Allowing side effects only through monads and keeping the language pure makes it possible to have lazy evaluation that does not conflict with the effects of impure code. Even though lazy expressions can be evaluated in any order, the monad structure forces the effects to be executed in the correct order.

[edit] 3.3 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.

[edit] 4 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.