FP (programming language)
FP is a programming language created by John Backus to support the function-level programming paradigm. It allows building programs from a set of generally useful language primitives and avoiding named variables. It was heavily influenced by APL developed by Kenneth E. Iverson in the early 1960s.
The FP language was introduced in Backus's 1977 Turing Award paper, "Can programming be liberated from the von Neumann style?: a functional style and its algebra of programs". The paper sparked interest in functional programming research, eventually leading to modern functional languages, which are largely founded on the lambda calculus paradigm, and not the function-level paradigm Backus had hoped. In his Turing award paper, Backus described how the FP style is different:
FP was used little beyond academia. In the 1980s, Backus created a successor language, FL, as an internal project at IBM Research.
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 :
integer :
character :
symbol :
⊥ 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 or are built from the primitives by program-forming operations.
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:
i:〈x'1,...,xn〉 = xi if 1 ≤ 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:
construction where :x = 〈f1:x,...,fn:x〉
condition where :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 Ef is an expression built from primitives, other defined functions, and the function symbol f alone, using functionals.
FP84
FP84 is an extension of FP to include infinite sequences, programmer-defined combining forms, and lazy evaluation. Unlike FFP, another one of Backus' own variations on FP, FP84 makes a clear distinction between objects and functions: i.e., the latter are no longer represented by sequences of the former. FP84's extensions are enabled by removing the FP restriction that sequence construction be applied to only non-⊥ objects: in FP84 the entire universe of expressions is closed under sequence construction.FP84's semantics are embodied in an underlying algebra of programs, a set of function-level equalities that may be used to manipulate and reason about programs.