Formal Fp Information
FP (short for Function Programming) is a programming language created by John Backus to support the function-level programming paradigm. This allows eliminating named variables.
Contents |
Overview
The values that FP programs map into one another comprise a set 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
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 built from primitives, other defined functions, and the function symbol f itself, using functionals.
See also
- FL, Backus' FP successor
- Function-level programming
- J
- John Backus
- FP84
- FFP, Formal Functional Programming
- FPr, Function-level Programming right-associative
References
- Can Programming Be Liberated from the von Neumann Style? Backus' Turing award lecture.
Categories: Academic programming languages | Function-level languages
|