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 (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: ''i'':〈x1,...,xn〉 = xi if 1 ≤ ''i'' ≤ n = ⊥ otherwiseFunctionals
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,...,fnwhere ''f1,...,fnx = 〈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 fEquational functions
In addition to being constructed from primitives by functionals, a function may be defined recursively by an equation, the simplest kind being: f ≡ ''E''f where ''E''f is an expression built from primitives, other defined functions, and the function symbol f itself, using functionals.FP84
FP84 is an extension of FP to include infinite sequences, programmer-defined combining forms (analogous to those that Backus himself added to FL, his successor to FP), 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 accomplished by removing the FP restriction that sequence construction be applied only to ''non''-⊥ objects: in FP84 the entire universe of expressions (including those whose meaning is ⊥) 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.References
{{Reflist, refs= {{Cite journal , doi = 10.1145/359576.359579, title = Can programming be liberated from the von Neumann style?: A functional style and its algebra of programs, journal = Communications of the ACM, volume = 21, issue = 8, pages = 613, year = 1978, last1 = Backus , first1 = J. , doi-access = free {{cite web , title=Association for Computing Machinery A. M. Turing Award , url=http://signallake.com/innovation/JBackus032007.pdf {{Dead link, date=March 2024 , bot=InternetArchiveBot , fix-attempted=yes *''Sacrificing simplicity for convenience: Where do you draw the line?'', John H. Williams and Edward L. Wimmers, IBM Almaden Research Center, Proceedings of the Fifteenth Annual ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages, San Diego, CA, January 1988.External links