Functional programming: Difference between revisions

Content added Content deleted

Inline

Revision as of 11:59, 22 July 2008

Functional programming treats functions as the fundamental first-class objects of the programming language. That has several consequences:

It's not possible to update variables (or other state) in a step-by-step fashion as in imperative programming.
Hence, all dependencies must be made explicit.
That leads to referential transparency -- given the same arguments, a piece of code will always behave identically.
Coding is compositional -- any two pieces of code with a matching 'interface', as specified by the type, can be combined, because no hidden side-effects can intervene. (See Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs by John Backus, 1977 Turing Award Lecture).
It's easy to refactor similar pieces of code, because any subexpression can be replaced by a variable bound at the outside.

This leads to a coding style which is very different from more traditional languages. Iteration is typically replaced by tail-recursion. Lists become a very important datatype. Code often consists of a composition of simpler blocks, which makes it look similar to declarative programming.

Most functional programming languages (FPLs) are related to the lambda calculus, which makes the specification of their formal semantics simpler.

One important characteristic of FPLs is their default evaluation order. Strict or eager FPLs will evaluate an argument as soon as possible, while lazy evaluation will do that as late as possible.

Strict FPLs often have an impure aspect that does allow functions with implicit side-effects, in order to interact with the (stateful) outside world. In non-strict FPLs, one uses monads or other means like uniqueness types to guarantee correct sequencing of side-effects.

With monads, one can also do imperative programming even in a purely functional languages, which is especially helpful if the notion of state is natural to the problem space.

@@ Line 1: / Line 1: @@
+[[Category:Programming Paradigms]]'''Functional programming''' treats functions as the fundamental first-class objects of the programming language. That has several consequences:
-[[Category:Programming Paradigms]]'''Functional programming''' is a programming paradigm that abstracts away the computation state. The program is designed in a stateless, and thus immutable, manner. In this sense functional programming opposes [[imperative programming]], which focuses on state transitions. Functional programming uses procedural decomposition (see [[procedural programming]]) and [[closure]]s. Subprograms there are pure functions, with the only side effect allowed on the function result. [[Iteration]] is typically replaced by [[recursion]], as the former exposes the state either in the form of the loop variable or as the exit condition.
+* It's not possible to update variables (or other ''state'') in a step-by-step fashion as in [[imperative programming]].
-Stateless abstraction ease program semantics definition. In particular it removes the problems with:
+* Hence, all dependencies must be made explicit.
+* That leads to [http://www.haskell.org/haskellwiki/Referential_transparency referential transparency] -- given the same arguments, a piece of code will always behave identically.
+* Coding is '''compositional''' -- any two pieces of code with a matching 'interface', as specified by the type, can be combined, because no hidden side-effects can intervene. (See [http://www.stanford.edu/class/cs242/readings/backus.pdf ''Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs''] by John Backus, 1977 Turing Award Lecture).
+* It's easy to '''refactor''' similar pieces of code, because any subexpression can be replaced by a variable bound at the outside.
+This leads to a coding style which is very different from more traditional languages. [[Iteration]] is typically replaced by tail-[[recursion]]. Lists become a very important datatype. Code often consists of a composition of simpler blocks, which makes it look similar to [[declarative programming]].
-* the order of subexpression evaluation,
-* aliasing,
-* the evaluation time (see [[lazy evaluation]]).
+Most functional programming languages (FPLs) are related to the [[wp:Lambda_Calculus|lambda calculus]], which makes the specification of their formal semantics simpler.
-At the same time it makes programming considerably more difficult, especially when the notion of state is natural to the domain space. Functional languages like [[Haskell]] provide some support for stateful programming, see [http://en.wikipedia.org/wiki/Monads_in_functional_programming monads].
+One important characteristic of FPLs is their default evaluation order. ''Strict'' or ''eager'' FPLs will evaluate an argument as soon as possible, while [[lazy evaluation]] will do that as late as possible.
+Strict FPLs often have an ''impure'' aspect that does allow functions with implicit side-effects, in order to interact with the (stateful) outside world. In non-strict FPLs, one uses [[wp:Monads_in_functional_programming|monads]] or other means like uniqueness types to guarantee correct sequencing of side-effects.
+With monads, one can also do [[imperative programming]] even in a purely functional languages, which is especially helpful if the notion of state is natural to the problem space.