Difference between revisions of "Functional programming/Alternative 1"
m (→Lazy evaluation)
|Line 62:||Line 62:|
Since pure compuations
Since pure compuations are referentially transparent they can be performed in any order any 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.
Revision as of 10:36, 22 December 2007
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.
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 closures, 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 lated when the function is called. Language implementations must contain special functionality to support this.
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.
Following table shows which languages support functional programming (by supporting closures) and for which the functional style is the dominant one.
Features of functional languages
Higher-order functions are functions that take other functions as their arguments. 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 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:
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 the outside of its body.
Higher-order functions are very useful for refactoring the code and reduce the amount of repetitition. example needed
Add reference to functional objects?
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.
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.
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 = h (f x) (f x) and get the same result, only the efficiency might change.
Since pure compuations are referentially transparent they can be performed in any order any 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.
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.