Functional programming
Functional programming is a programming paradigm that consist exclusively of functions in the programs. This known from imperative programming side effects are avoided.
The functional programming stems from the academic research. In the 1930s, various people on lambda calculus worked. This is about functions and their evaluation. Functional languages are implementations of this research.
A functional programming language is a programming language that offers language elements for combination and transformation of functions. A purely functional programming language is a programming language that precludes the use of elements that are contrary to the functional programming paradigm. Some authors use the term " functional programming language " is synonymous with " purely functional programming language ".
- 9.1 F # and OCaml
- 9.2 Haskell
- 9.3 Joy
- 9.4 Makefile
- Scala 9.5
- 9.6 Scheme
- 9.7 SML
- XSLT 9.8
Functions in mathematics and programming
The concept of function is in programming and mathematics with different meanings used (compare function (programming ) and function (mathematics) ). In mathematics, a function is considered to be an illustration of the function arguments to the respective operation result so that a function in the mathematical sense, with the same function for each use arguments provides the same result. In contrast function is often used as synonymous with subroutine in computer science. Unlike in mathematics in the computer science need functions in common parlance neither been faithful still free of an effect (also referred to as a side effect or side effect ) to be: First, the result of a call next to the passed when calling function parameters or of the history of function calls general on the instantaneous state of the surrounding computer program depend, and secondly, the function call may have even affect the future behavior of other functions.
The features of functional programming languages , however, behave like mathematical functions. This is achieved among other things by an assignment of the form
Is excluded.
Read Mathematically this line gives little sense, because that would be an equation and it would
Out what is untrue. What is meant is this assignment as
Which is another on the left, than the one on the right. While this is useful for programming, but does not match the behavior of variables in mathematics, where a variable if it has got a value assigned to exactly this value always reserves and not even the one and sometimes the other value in the course of an invoice assumes ( referential transparency).
An approach of functional programming is that their functions behave more like mathematical functions, so that the arithmetic and proof methods of mathematics can be better applied to programs ( to prove especially their correctness ).
It represents further the view that functions are a suitable means for modularizing programs by the main features of a variety of other functions put together (composed ) are. For this purpose, functional programming languages offer increased support, for example, the way functions work much like other types of data, can be used as arguments and return values ( higher order functions ).
The programmer specifies how the functions are composed, but there is still freedom in the analysis that can be used by translators for optimization purposes.
Delineation of imperative programming
Unlike imperative programs, which consist of arithmetic instructions, functional programs are a set of (function ) definitions, which can be mathematically interpreted as partial representations of input data to output data.
A typical example is the factorial of n! a number n ( n! = 1 · 2 · 3 · ... · n ), where an imperative solution:
Characteristic of the imperative programming here are the assignments ( change of values by the symbol ": =" in the pseudo- code represents ). Although the algorithm calculates the factorial of the number n, but the correctness of this computation path is not obvious.
Now, however, you can also use the faculty of defining recursive functions, which leads to functional solution.
Thus, the functional programming does not require grinding and assignments but requires connection to recursion.
Cardinality of functional languages
The cardinality of a programming language is defined by the amount of problems that are decidable in this language. The theoretical computer science has shown that a pure functional programming language with recursion is equally powerful as an imperative programming language loops and assignments allowed ( see Turing - completeness ). This shows that the compliance of the functional paradigm places no limitations, even though it may at first glance seem so.
From the other programming paradigm results in comparison to the more widely used imperative languages a different approach in the design of programs. The main differences are manifested in software engineering and in the performance. In general, there are advantages in the design and maintainability of programs, while the high abstraction of the machine implementation in performance-critical applications is a disadvantage.
Lambda calculus
As a historical theoretical basis of the λ - calculus ( lambda calculus ) by Alonzo Church serves. Each expression and each value is regarded as evaluable function, so that the whole programming on the transfer of functions based as parameters to functions.
The lambda calculus allows to evaluate complete subexpressions separately. This is the main advantage compared to imperative programming. This concept simplifies the program verification, and program optimization, for example, the transfer of the programs in a parallel form of analyzable.
Type System
Historically LISP is to be regarded as the first functional programming language; Languages LISP family (as well as Scheme) are dynamically typed. Since the development of Standard ML ( SML) research in the field of functional programming languages also focused on statically typed languages , in particular those that use the type system by Hindley and Milner. The advantage of this type of system is the availability of parametric polymorphism with type inference: programmers need not specify the types of its functions and other values, but get them free by the translator of all, at the same time still can complain at compile time type errors. This is generally considered significant advantage over dynamically typed languages ( LISP, Python ) interpreted that likewise do not require Typannotationen (as opposed to eg Java or C), but can send a reminder type error at runtime. However, the latter in turn has the advantage of a wider applicability of previously defined functions, if necessary, the time of development not previously seen new areas.
However, the Hindley - Milner system only allows polymorphism of the first rank; Extensions for second polymorphism and general k-th rank are now in the Haskell GHC translator available as extensions, but again require explicit annotations ( type inference from the second rank polymorphism is undecidable ).
Pure functional programming languages
Rein ( engl. pure ) functional programming languages take programs as mathematical function: An expression has there during program execution always the same value. There is no state variables that are changed during a computation. In order to describe desired effects ( user interaction, input / output operations ), special precautions are usually necessary. Most functional programming languages ( Standard ML, Caml, Scheme and others), however, allow such effects and are therefore not purely functional programming languages .
To allow programming with effects, without an impure (English impure ) language to be, in the development of language Haskell originating from the category theory concept of monads has been developed ( in particular by Eugenio Moggi and Philip Wadler ), which Wirkbehaftung expressed by parametric types, and thus forcing the type system, and with expressions between expressions without effects to be distinguished. Also in the Clean and Mercury the type system is used to identify such effects. There, however, one uses the concept of " Uniqueness " types.
Higher-order functions
We distinguish first-order functions and higher-order functions. In higher-order functions functions are self- values . This makes it possible in particular to use a function as arguments or results of other functions. A typical example is the derivative operator: is a differentiable function of the input, output is the derivative of this function. Another standard example is the map function, which takes as input a function f and a list l and returns the modified list, which arises because the function f is applied to each element of the list l. Definition of map in Haskell:
Map f [ ] = [] map f (x: xs ) = f x: map f xs In the first line the result for an empty list [ ] is returned; the second line applies the function f to the first list element x and then performs a recursion for the remainder of the list xs. Requirements analysis and rigorous evaluation
Functional languages can also differ according to their evaluation strategy: the case of strict evaluation ( engl. eager or strict evaluation) the arguments of functions are evaluated first. In contrast, the expressions are passed as a whole and then evaluated in the non- strict evaluation first.
Could for example calculate two ways, wherein the expression is strictly evaluated in the first case since only the arguments of the power function is calculated. In the second case, these arguments are evaluated only when needed, so after the power function was resolved:
A variant of the non- strict evaluation is the need for evaluation (English lazy evaluation ), are evaluated in expressions only when its value is needed in a calculation. This allows, for example, infinite data structures ( the list of all natural numbers, the list of all prime numbers, etc.) define specific algorithms and simplified.
Some calculations can be done with strict evaluation, others run more efficiently with demand evaluation. Schedules the strict evaluation of an expression, so also schedules the non- strict evaluation. Background to this is the confluence property of any functional language underlying λ - calculus, which states that the result of the calculation is independent of the order of evaluation.
Functional Algorithms and Data Structures
Algorithms give advantageous method for the solution of important problems of well- analyzes (eg, Sort ) and are usually, so that a developer can rely on proven, predictable solutions. The same data structures provide for the organization of data. Collections of good algorithms and data structures thus have a great practical importance.
The elimination of destructive assignments leads to a number of classical algorithms and data structures that make good use of this opportunity, so can not be used for functional languages and need to look for new solutions.
Chris Okasaki writes: " Even though most of these books say [ about data structures ], that they are independent of a specific programming language, so they are unfortunately only language independent in the sense of Henry Ford: programmers can use any programming language, as long as it is imperative. "
Just purely functional data structures are by their nature different from the usual data structures that usually only one version of their data manage ( ephemeral data structures), whereas functional data structures to manage multiple versions (persistent data structures).
Examples
The following programs define a function ring area, calculates the area which is situated between the two concentric circles with the radii R and r, or R1 and R2 with the common center. For this, the constant pi and the auxiliary function defined sq. These are then used by the ring area in the calculation.
F # and OCaml
Let Ring area (r1, r2) = let pi = 3.14 let sq x = x * x in pi * (sq r1 - r2 sq. ) Haskell
Sq. :: (Floating a) = > a -> a - optional explicit type specification sq x = x ** 2 ring area :: (Floating a) = > a -> a -> a - optional explicit type specification ring area r1 r2 = pi * ( r1 sq -sq r2) The type of functions sq. ring area is polymorphic and is bordered by specifying the type class floating. The explicit specification of the type is optional and can be used as well by the Haskell inferenziert compiler. Pi is predefined in Haskell.
Here is a more complex implementation, only with the help of higher-order functions:
Ring area ':: (Floating a) = > a -> a -> a - optional explicit type specification ring area ' r1 r2 = foldr (-) $ 0 map [ r1, r2 ] ( ( pi * ) (** 2). ) Joy
Joy uses the Reverse Polish Notation. Note that here all variables denote functions (also pi is a function ).
Makefile
Each Makefile represents a functional program
Scala
Def pi: Double = 3:14 def sq ( x: Double ) = x * x def ring area ( R: Double, r: Double ) = pi * ( sq ( R) - sq ( r)) Scheme
( define ( ring area r1 r2) (define pi 3.14) (define (sq x ) ( x * x)) ( * Pi ( - ( r1 sq ) (sq r2 ))) ) Alternatively, with higher-order functions:
( define ( ring area r1 r2) (* 3:14 ( foldr - 0 ( map ( lambda ( x ) (* xx) ) (list r1 r2) )))) SML
The type of x must be explicitly specified here as a SML97 translator would otherwise infer the type int. The underlying problem is the overloading of operators; This problem was only solved with the introduction of type classes, but in Haskell and related languages .
XSLT
XSLT is used to transform XML (especially XHTML) and has won along with XML much more important. It is functional as Dimitre Novatchev has shown. The defined in the following example function reverses the order of the words of a string. Typical of functional programming languages is the recursive call. The second paragraph shows how the function is used.
- International Conference on Functional Programming Contest ( ICFP Contest)
- Algebraic programming language