Functional programming system

This article was due to content flaws on the quality assurance side of the computer science editorial added. This is done in order to bring the quality of the articles from the subject area of ​​computer science to an acceptable level. Help to eliminate the shortcomings in this article and take part in the discussion !  ( + ) Reason: Article consists mainly of unexplained examples and web links. The few paragraphs of text show no concept. - Raphael Kirchner 3:31 p.m., November 20, 2010 (CET)

The term Functional Programming System (abbreviated FP system ) describes a concept of functional programming languages developed by John W. Backus . Backus started from the observation that common programming languages ​​represent computer programs as a small-scale serialized data manipulation, as they are based on the von Neumann machine model. According to Backus, this results in two problems. On the one hand, that von Neumann programs are difficult to parallelize. On the other hand, that it is difficult to argue formally about the properties of Von Neumann programs or to transform them. The Functional Programming System addresses these problems by constructing a program from a composition . Larger amounts of structured data are passed on from one function to the next, which technically enables parallel processing. Backus also considered making this way of working the basis of a new computer architecture that takes advantage of this possibility. ${\displaystyle P}$ ${\displaystyle P=F_{n}\circ F_{n-1}\circ F_{n-2}\circ ..\circ F_{1}}$

In a speech on the occasion of the presentation of the Turing Awards to Backus in 1977, the latter presented the idea of ​​FP systems. The title of the lecture was: Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs . In another essay, Backus decided to use the term function-level programming .

Functional program for calculating the scalar product

With the calculation of the scalar product, Backus gives an instructive example for the application of the functional programming system .

The function ("Inner Product"), which determines the scalar product of two vectors, is composed of the concatenated calculation of the three functions and (in this order), which is expressed as a function composition as follows : ${\displaystyle IP}$ ${\displaystyle Trans,(\alpha \times )}$ ${\displaystyle (/+)}$

${\displaystyle {\begin{aligned}IP&=(/+)\circ (\alpha \times )\circ Trans\end{aligned}}}$

Here is a function that transposes a matrix . In FP, for example, this relationship is noted as follows for a matrix : ${\displaystyle Trans}$ ${\displaystyle {\bigl (}{\begin{smallmatrix}3&4\\7&1\\-1&0\end{smallmatrix}}{\bigr )}}$

${\displaystyle {\begin{aligned}Trans(<<3,4>,<7,1>,<-1,0>>)&=<<3,7,-1>,<4,1,0>>\end{aligned}}}$

The symbols and denote functionals . These take on other functions to create new functions. In der Form takes over the two-digit multiplication function and provides a function that applies to all elements of a passed list of pairs. The result of the calculation is then the list of the individual products. In modern programming languages ​​this is mostly called functional . Backus names them too . ${\displaystyle \alpha }$ ${\displaystyle /}$ ${\displaystyle (\alpha \times )}$ ${\displaystyle \alpha }$ ${\displaystyle \times }$ ${\displaystyle \times }$ ${\displaystyle \alpha }$mapApplyToAll

The function finally roughly corresponds to the function or in the usual functional programming. Backus names it , meaning that the expression represents a function that inserts the operation between two elements in a given list . So it applies . ${\displaystyle /}$reducefoldInsert ${\displaystyle (/+)}$ ${\displaystyle +}$ ${\displaystyle (/+)(<2,3,4>)=2+3+4=9}$

The calculation of the scalar product function is applied to the two vectors and can then be understood as follows: ${\displaystyle IP}$ ${\displaystyle <1,2,3>}$ ${\displaystyle <6,5,4>}$

${\displaystyle {\begin{aligned}&IP:<<1,2,3>,<6,5,4>>\\&=(/+)\circ (\alpha \times )\circ trans:<<1,2,3>,<6,5,4>>\\&=(/+)\circ (\alpha \times ):(trans:<<1,2,3>,<6,5,4>>)\\&=(/+):((\alpha \times ):<<1,6>,<2,5>,<3,4>>)\\&=(/+):<\times :<1,6>,\times :<2,5>,\times :<3,4>>\\&=(/+):<6,10,12>\\&=+:<6,+:<10,12>>\\&=28\end{aligned}}}$

The arithmetic process therefore represents a processing pipeline without an internal state, which converts the input into the output in three separate work steps. The work steps themselves can be parallelized to varying degrees. It would also be possible to create a hardware pipeline for the program . ${\displaystyle IP}$

Notations in the FP system

Backus uses a notation that is loosely based on mathematical conventions and supplements it with McCarthy's conditional expressions and a recursive representation for WHILE loops. It is crucial that each entity represents a function and is therefore compatible with the composition operator. ${\displaystyle \circ }$

Numbers as selectors

The vector programming language APL had a decisive influence on the Combinator based functional programming system by John Backus, which works without a lambda variable list; instead selectors (numbers) are used to pick values ​​from a sequence.

1:<x1,...,xn> → x1
i:<x1,...,xi,...,xn> → xi

Fixed number of combiners / functional forms

Applikation f : x                  = f(x)
Komposition (f o g):x              = f(g(x))
Konstruktion [f1,f2, ... ,fn]:x     = <f1:x,f2:x, ... ,fn:x>
Kondition (p → f ; g):x            = Wenn p:x = T dann f:x sonst wenn p:x = F dann g:x sonst ⊥
Konstante ~x : y                   = Wenn y = ⊥ dann ⊥ sonst x
Insert (/ f):<x1,x2, ... ,xn>       = f:<x1,f:<x2, ... f:<xn-1,xn>>>
Apply to All (α f):<x1,x2, ... ,xn> = <f:x1,f:x2, ... ,f:xn>
Binary to Unary bu f x
While-Schleife (while p f):x        = Wenn p:x = T dann (while p f):(f:x)
         sonst wenn p:x = F dann x sonst ⊥

and the definition of monadic functions:

Def Name ≡ Term

With ⊥ Backus meant the value “bottom”, a value like “undefined” or “exception”. T and F are the values ​​for "true" and "false".

Further development of FP systems

A team of John Backus, John Williams and Edward Wimmers developed the successor FL (Function-Level Programming) in 1989 at the IBM Almaden Research Center . With this concept one should be able to rearrange programs as comfortably as one can rearrange equations in mathematics, for this a referential transparency had to be guaranteed. This should serve a new dimension of program optimization (EFL). With FL, Backus wanted to turn the "then computer science" into an engineering discipline. Again some further developments of FL are J (application like APL) and PLaSM, a programming language for geometry.

FP implementations

• INTERACTIVE FP, help page
• FP compiler that compiles itself to C, repo to
• Fp interpreter in Lisp
• FP trivia, FP repo to
• Plasm ( P rogramming La nguage for S olid M odeling), a functional programming language for use in CAD , which at the Roma Tre University is developed.

See also

• Algebraic programming language

literature

• Wolfram-Manfred Lippe : Functional and applicative programming: basics, languages, implementation techniques . 1st edition. Springer , Berlin 2009, ISBN 978-3-540-89091-1 ( limited preview in Google book search).
• Alberto Paoluzzi ea: Geometric Programming for Computer-Aided Design . 1st edition. Wiley , Chichester 2003, ISBN 978-0-471-89942-6 ( limited preview in Google Book Search).

Individual evidence

1. ↑ Lippe 2009, p. 73
2. ↑ Can Programming Be Liberated from the von Neumann Style? A Functional Style and Its Algebra of Programs Stanford University, 1978 (PDF; 2.87 MB)
3. ↑ Function Level Programs as Mathematical Objects (PDF)
4. ↑ INTERACTIVE FP
5. ↑ INTERACTVE FP - Help
6. ↑ Furry Paws , an FP compiler (English)
7. ↑ fp-interpreter-in-lisp
8. ^ FP interpreter, created in Delphi
9. ↑ PLaSM functional language for computing with geometry. Alberto Paoluzzi ( University of Rome III ), accessed November 27, 2010 . 

Web links

• Criticism of the Backus essay by Edsger W. Dijkstra (PDF; 143 kB)
• John Backus: Function Level Programming and the FL Language , 1987 (video)
• The FL Project: Design of a Functional Language (PDF; 315 kB)
• FL Language Manual, Parts 1 and 2 (PDF; 20 MB)
• Introduction to FL and PLaSM (PDF)
• FP (English)
• Scripts to FP Systems