Functional programming

Functional programming is a programming paradigm within which functions can not only be defined and applied, but also how data can be linked to one another, used as parameters and appear as function results. As a result, a functional program can compose and apply new calculation rules at runtime. Programming languages that enable functional programming are called functional.

Functional programming arises from basic mathematical research. In the 1930s, Alonzo Church developed the lambda calculus as an instrument to work on the decision problem and to define the concept of the calculable function. The lambda calculus itself does not deal with specific functions, but is only a set of rules for how functions are applied to their arguments and how free and bound variables are handled.

The special properties of functional programming make it possible to dispense with the internal states of a calculation process required in imperative programming as well as the associated state changes, which are also called side effects . Dispensing with this simplifies the semantic analysis of a computer program considerably on the one hand and opens up extensive possibilities for rule-based, algebraic program transformation and synthesis on the other. This results in the considerable practical importance of functional programming for computer science.

Another consequence is that in functional programming it is particularly easy to describe algorithms without taking into account the nature of the processed data objects and thus to create generic program code. Many functional procedures are so generic that they have not had to be adapted since the 1950s.

The first significant software created in functional programming is the metacircular Lisp interpreter named eval , created by John McCarthy in 1958 , which represents the semantics of LISP composed of five simple functions. It fits on a DIN A4 page and is still the conceptual basis for the implementation of most programming languages.

definition

The functional programming is characterized by the following properties:

Computer programs are understood as functions that provide an output for an input that is only dependent on this.
Functions are not represented as a sequence of instructions, but as function calls nested within one another.
Functions are equal to all other data objects. This means that they can be used as parameters in functions and can also emerge from functions as calculation results. In particular, functions like other data objects can be created at runtime or can be omitted.
A function can refer to variables that belong to the context in which it was created. It can still do this even if it has left the context. The assignment of the variables at the time this context is exited is then frozen within this function. A function created in this way is called closure and the frozen variable assignments are called closure variables.
Function definitions can be used literally in the position of a function symbol without explicit naming. Such functions are called anonymous and are often casually called "lambdas".

Functional programming languages

A functional programming language is a programming language that implements the properties mentioned above. Important representatives of functional programming languages are Lisp and Haskell . Almost all of the programming languages that have emerged recently allow functional programming.

Languages intended for functional programming include LISP, ML, Haskell, OCaml, F #, Erlang, Clojure and Scala, among others. Languages that enable functional programming among other paradigms include Perl, ECMAScript, Dylan, Ruby, and Visual Basic.NET. Python has limitations on the formulation of anonymous functions.

Popular languages that do not offer any possibilities for functional programming are, for example, C and older Delphi versions (from 2010 closures or anonymous functions are supported).

A purely functional programming language would be understood to be a programming language that is isomorphic to the lambda calculus . This applies with minimal restrictions, for example to the esoteric programming language unlambda .

Many actually object-oriented languages have been upgraded in the most recent versions, such as C ++ (from version 11) or Java (from version 8). However, the syntax suffers, so that the compactness of LISP or Haskell is not achieved.

Math concepts

The general concepts of functional programming come from the mathematics of the 1930s and 1940s. The lambda calculus and category theory are of particular importance . The lambda calculus is an operational set of rules that can be used to determine the meaning of symbolic expressions. Category theory deals with the relationship between mathematical structures. They can be used, for example, to map the structure of a computer program onto structures of perception and thus explain why a certain program solves a certain task correctly.

Lists

Data structures commonly used in imperative programming such as arrays are difficult to use in functional programming because they are difficult to represent using recursion, even if there are approaches such as the functional programming system that explicitly work with such structures. Lists and trees, on the other hand, are very compatible with functional programming.

Be any data type. Then the type of the arbitrarily long lists with at least 0 elements of the type is given by the recursion . Here is the empty list and a two-digit operation that constructs a new list from a value and a list by appending it to the beginning. ${\ displaystyle A}$ ${\ displaystyle A ^ {*}}$ ${\ displaystyle A}$ ${\ displaystyle A ^ {*} = Nil | Cons (A, A ^ {*})}$ ${\ displaystyle Nile}$ ${\ displaystyle Cons: A \ times A ^ {*} \ to A ^ {*}}$ ${\ displaystyle a}$ ${\ displaystyle L}$ ${\ displaystyle M}$ ${\ displaystyle a}$ ${\ displaystyle L}$

You can use this recursive structure to write functions that decompose a list and determine a value in the process. Such a function is called catamorphism. ${\ displaystyle h \ colon A ^ {*} \ to B}$ ${\ displaystyle h}$

Catamorphisms

Let be a data type, a value and a mapping. Then it's through ${\ displaystyle B}$ ${\ displaystyle b \ in B}$ ${\ displaystyle \ otimes \ colon A \ times B \ to B}$

{\ displaystyle {\ begin {aligned} h \ colon A ^ {*} & \ to B \\ Nil & \ mapsto b \\ Cons (a, L) & \ mapsto a \ otimes h (L) \ end {aligned} }}

the catamorphism (from Greek κατά = along, down) given with initial value and link . In the usual notation with banana brackets, it is written as. In terms of functional programming, the circumfix operation is a higher order function. In functional programming languages there is the function or for calculating catamorphisms . A catamorphism following the above definition is right-handed. It corresponds to the following program loop that traverses a list from its end: ${\ displaystyle b}$ ${\ displaystyle \ otimes}$ ${\ displaystyle h = (| b, \ otimes |)}$ ${\ displaystyle (| \ cdot, \ cdot |)}$ reducefold

{\ displaystyle {\ begin {aligned} & x: = b \\ & For \; i: = Length (L) {\ text {Downto}} 1 {\ text {Do}} \\ & \; \; x: = L_ {i} \ otimes x \\ & End \\ & Return (x) \\\ end {aligned}}}

A left-handed catamorphism would start at index 1.

Many basic methods of programming are catamorphisms. Calculated the sum of a list of numbers, strings hanging together and having calculated the length of a list. A function that filters a list for elements that meet the property can be calculated with the function from , which is defined as follows: with if and otherwise . ${\ displaystyle (| 0, + |)}$ ${\ displaystyle (| \ epsilon, \ cdot |)}$ ${\ displaystyle (| 0, Inc |)}$ ${\ displaystyle Inc: (n, k) \ mapsto k + 1}$ ${\ displaystyle l}$ ${\ displaystyle p}$ ${\ displaystyle filter}$ ${\ displaystyle p}$ ${\ displaystyle filter: p \ mapsto (| Nil, f |)}$ ${\ displaystyle f: Cons (a, L) \ mapsto Cons (a, L)}$ ${\ displaystyle p (a)}$ ${\ displaystyle f: Cons (a, L) \ mapsto L}$

If the operation is associative with the neutral element , then the catamorphism is the clear extension of the operation to any number of arguments. This is a useful feature that can save a lot of practical programming work. If, for example, a two-digit function composition has already been implemented, the composition of functions can be displayed as ( the identical figure is here). ${\ displaystyle h}$ ${\ displaystyle \ emptyset}$ ${\ displaystyle (| \ emptyset, h |)}$ ${\ displaystyle h}$ ${\ displaystyle f \ circ g}$ ${\ displaystyle \ bigodot _ {i = 1} ^ {n} f_ {i}}$ ${\ displaystyle n}$ ${\ displaystyle (| id, \ circ |)}$ ${\ displaystyle id}$

Anamorphisms

While catamorphisms "evaporate" lists of individual values, anamorphisms build lists from individual values. The terms are dual to each other.

Let it be a predicate and a mapping. An anamorphism is then defined as follows: ${\ displaystyle p \ colon B \ to \ {w, f \}}$ ${\ displaystyle g \ colon B \ to A \ times B}$ ${\ displaystyle h \ colon B \ to A ^ {*}}$

{\ displaystyle {\ begin {aligned} h: b & \ mapsto Nil {\ text {if}} p (b) = w \\ b & \ mapsto Cons (a, h (b ')) {\ text {with}} [a, b '] = g (b) {\ text {if}} p (b) = f \ end {aligned}}}

The anamorphism with generator and predicate is listed with lens brackets . An example of a simple anamorphism is the function . It calculates the (inverted) list of the first natural numbers from a natural number . ${\ displaystyle g}$ ${\ displaystyle p}$ ${\ displaystyle h = [(p, g)]}$ ${\ displaystyle \ iota = [(i \ mapsto (i <1), i \ mapsto [i, i-1])]}$ ${\ displaystyle n}$ ${\ displaystyle n}$ ${\ displaystyle \ iota (n) = [n, n-1, n-2, .., 1]}$

Hylomorphisms

Be a catamorphism and an anamorphism. Then the image is a so-called hylomorphism (Greek υλη = wood, material). Hylomorphisms are able to represent a whole processing process within which a structure is developed through an anamorphism and evaporated again through a catamorphism. This representation makes it possible to algebraically remove the intermediate structure generated by the anamorphism. The resulting, independent representation of the hylomorphism without intermediate structure leads in practice to a considerable reduction in the required storage space. ${\ displaystyle (| z, f |)}$ ${\ displaystyle [(p, g)]}$ ${\ displaystyle (| z, f |) \ circ [(p, g)]}$

It is easily possible to represent a more complex algorithm such as the Minimax algorithm, which finds the best move in a two-person game such as chess, as a hylomorphism. The hylomorphism , which combines the catamorphism to calculate a number product with the anamorphism mentioned above , calculates the factorial of a number. ${\ displaystyle! = (| 1, \ times |) \ circ ([(i \ mapsto (i <1), i \ mapsto [i, i-1])]}$ ${\ displaystyle (| 1, \ times |)}$ ${\ displaystyle \ iota}$

Differentiation from imperative programming

In contrast to imperative programs , which consist of arithmetic instructions , functional programs are a set of (function) definitions that are mathematically a partial mapping of input data to output data and at the same time are themselves composed of function calls.

A typical example is the calculation of the factorial n! a number n (n! = 1 2 3 ... n), here an imperative solution:

Eingabe:
    Zahl n
Ausgabe:
    Zahl b (= 1 · 2 · 3 · … · n)
Algorithmus:
    b := 1 (Zuweisung)

    solange n > 0 führe aus
        b := n · b
        n := n − 1

    Ausgabe: b

The assignments (change of values, represented by the symbol :=in the pseudocode ) are characteristic of imperative programming . The algorithm calculates the factorial of the number n, but the correctness of this calculation method is not obvious.

Now, however, one can also define the factorial with the help of recursive functions , which leads to the functional solution. ${\ displaystyle n! = f (n) = {\ begin {cases} n \ cdot f (n-1) & \ mathrm {f {\ ddot {u}} r} \ \ n> 0 \\ 1 & \ mathrm {f {\ ddot {u}} r} \ \ n = 0 \ end {cases}}}$

Funktion f(n):
    wenn n > 0 dann:
        Ausgabe: n · f(n - 1)
    sonst wenn n = 0 dann:
        Ausgabe: 1

Functional programming does not require loops or assignments, but it requires recursion.

Lambda calculus

The theoretical basis of the functional programming is the λ-calculus (lambda-calculus) by Alonzo Church . Every expression and every value is viewed as an evaluable function, so that the entire programming is based on the transfer of functions as parameters to functions.

The lambda calculus allows complete sub-expressions to be evaluated separately. This is the main advantage over imperative programming. This concept simplifies program verification and program optimization , for example transferring the programs into a form that can be evaluated in parallel .

Type system

Historically, Lisp is to be understood as the first functional programming language. Languages of the LISP family (like Scheme ) are dynamically typed . Since the development of standard ML (SML) , research in the field of functional programming languages has also focused on statically typed languages, especially those that use the Hindley and Milner type system . The advantage of this type system is the availability of parametric polymorphism together with type inference : programmers do not have to specify the types of their functions and other values, but get them calculated free of charge by the translator, who can also complain about type errors during the translation. This is generally seen as a significant advantage over dynamically typed languages (Lisp, Python ), which also do not require type annotations (in contrast to Java or C , for example ), but can only warn of type errors at runtime. The latter, however, in turn has the advantage of broader applicability of already defined functions to new areas of application that may not have been foreseen at the time of development.

The Hindley-Milner system, however, only permits polymorphism of the first order ; Extensions for polymorphism of the second and generally kth rank are now available as extensions in the Haskell translator GHC , but again require explicit annotations (type inference from polymorphism of the second rank is undecidable ).

Purely functional programming languages

Rein (English pure ) functional programming languages put programs on a mathematical function: An expression has there during program execution always the same value. There are no state variables that can be changed during a calculation. In order to be able to describe the 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.

In order to allow programming with effects without becoming a so-called impure (English impure ) language , the concept of monads from category theory is used in the Haskell language (in particular by Eugenio Moggi and Philip Wadler ), which is effective expresses parametric types and thus forces the type system to distinguish between expressions with and expressions without effects. The type system is also used in Clean and Mercury to identify such effects. There, however, the concept of the "uniqueness" types is used.

Higher order functions

A distinction is made between functions of the first order and functions of higher order . For higher-order functions, functions are themselves values. In particular, this allows functions to be used as results or arguments of other functions. A classic example is the derivation operator , whose representability in Lisp was mandatory for the design of this language: input is a differentiable function, output is the derivation of this function.

A simpler, standard example of a higher order function is the function mapwhich takes as input a function fand a list land returns the modified list that results from applying the function fto each element of the list l. Definition of mapin Haskell :

 map f [] = []
 map f (x:xs) = f x : map f xs

The first line returns the result for an empty list []; the second line applies the function fto the first list element x and then performs a recursion step for the rest of the list xs .

Assessment of needs and strict evaluation

Functional languages can also be differentiated according to their evaluation strategy : With strict evaluation (English eager or strict evaluation ), the arguments of functions are evaluated first. On the other hand, with the non-strict evaluation , the expressions are first transferred as a whole and then evaluated.

For example, one can calculate the expression in two ways: ${\ displaystyle (3 + 5) ^ {2}}$

${\ displaystyle (3 + 5) ^ {2} = 8 ^ {2} = 8 \ cdot 8 = 64}$
${\ displaystyle (3 + 5) ^ {2} = (3 + 5) \ cdot (3 + 5) = 8 \ cdot 8 = 64}$

In the first case, the expression is evaluated strictly because the arguments of the power function are calculated first. In the second case, these arguments are only evaluated when necessary, i.e. after the power function has been resolved (non-strict evaluation).

A variant of the non-strict evaluation is the need for evaluation (English lazy evaluation be) evaluated only in terms if its value is required in a calculation. This allows z. B. define infinitely large data structures (the list of all natural numbers, the list of all prime numbers, etc.), and certain algorithms are simplified.

Some calculations can be carried out more efficiently with a strict evaluation, others with a needs evaluation. If the strict evaluation of an expression terminates, the non-strict evaluation also terminates. The background to this is the confluence property of the λ-calculus on which every functional language is based , which states that the result of the calculation does not depend on the order of the evaluation.

Functional algorithms and data structures

Algorithms indicate advantageous procedures for solving important problems (e.g. sorting ) and are usually well analyzed so that a developer can fall back on proven, assessable solutions. Data structures do the same for organizing data. Collections of good algorithms and data structures are therefore of great practical importance.

Dispensing with assignments means that a number of classic algorithms and data structures that make extensive use of this option cannot be used for functional languages and new solutions have to be sought.

Chris Okasaki writes:

"While most of these books [about data structures] claim that they are independent of a particular programming language, unfortunately they are only language-independent in the sense of Henry Ford : Programmers can use any programming language as long as it is imperative."

Purely functional data structures are by their nature different from the usual data structures, which usually only manage one version of their data (ephemeral data structures), whereas functional data structures manage several versions (persistent data structures).

Examples

The following programs define a function ringareathat calculates the area, the concentric between the two circles with the radii R and rrespectively r1and r2located with common center, according to the mathematical expression: . To do this, the constant and the auxiliary function are defined. These are then used for the calculation. ${\ displaystyle A = \ pi \ cdot | r_ {1} ^ {2} -r_ {2} ^ {2} |}$ pisqringarea

Common Lisp

(defun ringarea (r1 r2)
    (flet ((sq (x)
        (* x x)))
    (* pi (- (sq r1)
        (sq r2)))))

F # and OCaml

let ringarea (r1, r2) =
    let pi = 3.14 in
    let sq x = x*x in
    pi * (sq r1 - sq r2)

Haskell

-- optionale explizite Typangabe
sq :: (Floating a) => a -> a
sq x = x * x

-- optionale explizite Typangabe
ringArea :: (Floating a) => a -> a -> a
ringArea r1 r2 = pi * (sq r1 - sq r2)

The type of the functions sq, ringAreais polymorphic and is Floatinglimited by specifying the type class . The explicit specification of the type is optional and can just as well by the Haskell compiler inferenziert be. Pi is predefined in Haskell.

Here is a more complex implementation, using only higher-order functions:

ringArea' :: (Floating a) => a -> a -> a -- optionale explizite Typangabe
ringArea' r1 r2 = foldr (-) 0 $ map ((*pi) . (^2)) [r1, r2]

Joy

DEFINE: pi == 3.14;; sq == dup *;; ringarea == sq swap sq swap - pi *.

Joy uses the reverse Polish notation . Note that all variables here designate functions ( pi is also a function).

Julia

pi = 3.14;
sq(x::Number) = x * x;
ringarea(R::Number, r::Number) = pi * (sq(R) - sq(r));

python

from math import pi
squared = lambda x: x ** 2
ringarea = lambda r1, r2: pi * (squared(r1) - squared(r2))

Scala

val squared: Double => Double = x => x * x
val ringArea: (Double, Double) => Double =
    (outerRadius, innerRadius) =>
        math.Pi * (squared(outerRadius) - squared(innerRadius))

Kotlin

val sq: (Double) -> Double = { x -> x * x }
val ringarea = { R: Double, r: Double -> PI * (sq(R) - sq(r)) }

There is either the option of specifying the function type separately (above) or of defining the parameter types within the lambda (below).

Java

UnaryOperator<Double> sq = d -> d * d;
BinaryOperator<Double> ringArea = (outerRadius, innerRadius) -> Math.PI * (sq.apply(outerRadius) - sq.apply(innerRadius));

Scheme

1 (define (ring-area r1 r2)
2     (define pi 3.14)
3     (define (sq x)
4         (* x x))
5     (* pi (- (sq r1)
6         (sq r2))))

SML

local
    val pi = 3.14
    val sq = fn (x: real) => x * x
in
    fun ringarea(R, r) = pi * (sq R - sq r)
end

The type of xmust be specified here explicitly, since an SML97 translator would otherwise infer the type int . The underlying problem is that of overloading of operators; this problem was only solved with the introduction of type classes, but in Haskell and related languages.

Swift

let pi = 3.14
let square = {(x: Double) -> Double in x * x }
let ringarea = {(r1: Double, r2: Double) -> Double in
    pi * (square(r1) - square(r2))
}

XSLT

XSLT is used to transform XML (especially to XHTML) and has grown in importance together with XML. It is functional, as Dimitre Novatchev has shown. The function defined in the following example reverses the order of the words in a string. The recursive call is typical for functional programming languages. The second paragraph shows how to use the function.

<xsl:function name="str:reverse" as="xs:string">
  <xsl:param name="sentence" as="xs:string"/>
  <xsl:choose>
    <xsl:when test="contains($sentence, ' ')">
      <xsl:sequence select="concat(str:reverse(
        substring-after($sentence, ' ')),
        ' ',
        substring-before($sentence, ' '))"/>
    </xsl:when>
    <xsl:otherwise>
      <xsl:sequence select="$sentence"/>
    </xsl:otherwise>
  </xsl:choose>
</xsl:function>

<xsl:template match="/">
<output>
  <xsl:value-of select="str:reverse('DOG BITES MAN')"/>
</output>
</xsl:template>

literature

Chris Okasaki: Purely Functional Data Structures. Cambridge University Press, 1999, ISBN 0-521-66350-4 .
Patrick M. Krusenotto Functional Programming and Metaprogramming - Interactive in Common Lisp. Springer, 2016, ISBN 978-3-658-13743-4 .
Lothar Piepmeyer: Basic course in functional programming with Scala. Hanser, 2010, ISBN 978-3-446-42092-2 , p. 297.
Fethi Rabhi, Guy Lapalme: Algorithms - A Functional Programming Approach. Addison Wesley, 1999, ISBN 0-201-59604-0 .

Web links

What is functional programming? , Faculty of Computer Science and Mathematics at the University of Passau
Amr Sabry: What is a Purely Functional Language? In: J. Functional Programming. 8 (1), January 1998, pp. 1-22.
Rainer Grimm: Functional programming (1): Out of the academic niche. at Linux-Magazin Online
Andre Schütz: Functional programming with Scala: Introduction to Informatik Aktuell (magazine)

Individual evidence

↑ ^a ^b Patrick M. Krusenotto: Functional programming and metaprogramming. Springer, Wiesbaden 2016, p. 217ff, p. 244 ff.
^ The Functional Programming Language XSLT ( Memento from December 5, 2008 in the Internet Archive )
↑ From the W3C Recommendation XSL Transformations (XSLT) Version 2.0

[Krusenotto-1] Patrick M. Krusenotto: Functional programming and metaprogramming. Springer, Wiesbaden 2016, p. 217ff, p. 244 ff.

[2] The Functional Programming Language XSLT ( Memento from December 5, 2008 in the Internet Archive )

[3] From the W3C Recommendation XSL Transformations (XSLT) Version 2.0