FP (programming language)
Encyclopedia
FP is a programming language
created by John Backus
to support the function-level programming
paradigm. This allows eliminating named variables.
which is closed
under sequence formation:
if x1,...,xn are values, then the sequence 〈x1,...,xn〉 is also a value
These values can be built from any set of atoms: booleans, integers, reals, characters, etc.:
boolean : {T, F}
integer : {0,1,2,...,∞}
character : {'a','b','c',...}
symbol : {x,y,...}
⊥ is the undefined value, or bottom. Sequences are bottom-preserving:
〈x1,...,⊥,...,xn〉 = ⊥
FP programs are functions f that each map a single value x into another:
f:x represents the value that results from applying the function f
to the value x
Functions are either primitive (i.e., provided with the FP environment) or are built from the primitives by program-forming operations (also called functionals).
An example of primitive function is constant, which transforms a value x into the constant-valued function x̄. Functions are strict
:
f:⊥ = ⊥
Another example of a primitive function is the selector function family, denoted by 1,2,... where:
1:〈x1,...,xn〉 = x1
i:〈x1,...,xn〉 = xi if 0 < i ≤ n
= ⊥ otherwise
unit + = 0
unit × = 1
unit foo = ⊥
These are the core functionals of FP:
composition f°g where f°g:x = f:(g:x)
construction [f1,...fn] where [f1,...fn]:x = 〈f1:x,...,fn:x〉
condition (h ⇒ f;g) where (h ⇒ f;g):x = f:x if h:x = T
= g:x if h:x = F
= ⊥ otherwise
apply-to-all αf where αf:〈x1,...,xn〉 = 〈f:x1,...,f:xn〉
insert-right /f where /f:〈x〉 = x
and /f:〈x1,x2,...,xn〉 = f:〈x1,/f:〈x2,...,xn〉〉
and /f:〈 〉 = unit f
insert-left \f where \f:〈x〉 = x
and \f:〈x1,x2,...,xn〉 = f:〈\f:〈x1,...,xn-1〉,xn〉
and \f:〈 〉 = unit f
f ≡ Ef
where E'f is an expression
built from primitives, other defined functions, and the function symbol f itself, using functionals.
Programming language
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
created by John Backus
John Backus
John Warner Backus was an American computer scientist. He directed the team that invented the first widely used high-level programming language and was the inventor of the Backus-Naur form , the almost universally used notation to define formal language syntax.He also did research in...
to support the function-level programming
Function-level programming
In computer science, function-level programming refers to one of the two contrasting programming paradigms identified by John Backus in his work on programs as mathematical objects, the other being value-level programming....
paradigm. This allows eliminating named variables.
Overview
The values that FP programs map into one another comprise a setSet (computer science)
In computer science, a set is an abstract data structure that can store certain values, without any particular order, and no repeated values. It is a computer implementation of the mathematical concept of a finite set...
which is closed
Closure (mathematics)
In mathematics, a set is said to be closed under some operation if performance of that operation on members of the set always produces a unique member of the same set. For example, the real numbers are closed under subtraction, but the natural numbers are not: 3 and 8 are both natural numbers, but...
under sequence formation:
if x1,...,xn are values, then the sequence 〈x1,...,xn〉 is also a value
These values can be built from any set of atoms: booleans, integers, reals, characters, etc.:
boolean : {T, F}
integer : {0,1,2,...,∞}
character : {'a','b','c',...}
symbol : {x,y,...}
⊥ is the undefined value, or bottom. Sequences are bottom-preserving:
〈x1,...,⊥,...,xn〉 = ⊥
FP programs are functions f that each map a single value x into another:
f:x represents the value that results from applying the function f
to the value x
Functions are either primitive (i.e., provided with the FP environment) or are built from the primitives by program-forming operations (also called functionals).
An example of primitive function is constant, which transforms a value x into the constant-valued function x̄. Functions are strict
Strict function
A strict function in the denotational semantics of programming languages is a function f where f\left = \perp. The entity \perp, called bottom, denotes an expression which does not return a normal value, either because it loops endlessly or because it aborts due to an error such as division by...
:
f:⊥ = ⊥
Another example of a primitive function is the selector function family, denoted by 1,2,... where:
1:〈x1,...,xn〉 = x1
i:〈x1,...,xn〉 = xi if 0 < i ≤ n
= ⊥ otherwise
Functionals
In contrast to primitive functions, functionals operate on other functions. For example, some functions have a unit value, such as 0 for addition and 1 for multiplication. The functional unit produces such a value when applied to a function f that has one:unit + = 0
unit × = 1
unit foo = ⊥
These are the core functionals of FP:
composition f°g where f°g:x = f:(g:x)
construction [f1,...fn] where [f1,...fn]:x = 〈f1:x,...,fn:x〉
condition (h ⇒ f;g) where (h ⇒ f;g):x = f:x if h:x = T
= g:x if h:x = F
= ⊥ otherwise
apply-to-all αf where αf:〈x1,...,xn〉 = 〈f:x1,...,f:xn〉
insert-right /f where /f:〈x〉 = x
and /f:〈x1,x2,...,xn〉 = f:〈x1,/f:〈x2,...,xn〉〉
and /f:〈 〉 = unit f
insert-left \f where \f:〈x〉 = x
and \f:〈x1,x2,...,xn〉 = f:〈\f:〈x1,...,xn-1〉,xn〉
and \f:〈 〉 = unit f
Equational functions
In addition to being constructed from primitives by functionals, a function may be defined recursively by an equation, the simplest kind being:f ≡ Ef
where E'f is an expression
Expression (programming)
An expression in a programming language is a combination of explicit values, constants, variables, operators, and functions that are interpreted according to the particular rules of precedence and of association for a particular programming language, which computes and then produces another value...
built from primitives, other defined functions, and the function symbol f itself, using functionals.
See also
- FL, Backus' FP successor
- Function-level programmingFunction-level programmingIn computer science, function-level programming refers to one of the two contrasting programming paradigms identified by John Backus in his work on programs as mathematical objects, the other being value-level programming....
- JJ (programming language)The J programming language, developed in the early 1990s by Kenneth E. Iverson and Roger Hui, is a synthesis of APL and the FP and FL function-level languages created by John Backus....
- John BackusJohn BackusJohn Warner Backus was an American computer scientist. He directed the team that invented the first widely used high-level programming language and was the inventor of the Backus-Naur form , the almost universally used notation to define formal language syntax.He also did research in...
- FP84FP84FP84 is an extension of John Backus' FP programming language to include infinite sequences, programmer-defined combining forms , and lazy evaluation....
- FFP, Formal Functional Programming
- FPrFPr (programming language)FPr is a programming language that is an implementation of an FP-System. FP was invented by John Backus and described in his Turing Award lecture...
, Function-level Programming right-associative