FP (programming language)

Infobox programming language
name = FP
logo =
paradigm = function-level
year = 1977
designer = John Backus
developer =
latest release version =
latest release date =
typing =
implementations =
dialects =
influenced_by = APL
influenced = FL, J

FP (short for Function Programming) is a programming language created by John Backus to support the function-level programming paradigm. This allows for the elimination of named variables.

Overview

The values that FP programs map into one another comprise a set which is closed under sequence formation:

if x₁,...,x_n are values, then the sequence 〈x₁,...,x_n〉 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":

〈x₁,...,⊥,...,x_n〉 = ⊥

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:〈x₁,...,x_n〉 = x₁ "i":〈x₁,...,x_n〉 = x_i 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 &times; = 1 unit foo = ⊥

These are the core functionals of FP:

composition f°g where f°g:x = f:(g:x)

construction [f₁,...f_n] where [f₁,...f_n] :x = 〈f₁:x,...,f_n: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:〈x₁,...,x_n〉 = 〈f:x₁,...,f:x_n〉

insert-right /f where /f:〈x〉 = x and /f:〈x₁,x₂,...,x_n〉 = f:〈x₁,/f:〈x₂,...,x_n〉〉 and /f:〈 〉 = unit f

insert-left f where f:〈x〉 = x and f:〈x₁,x₂,...,x_n〉 = f:〈f:〈x₁,...,x_n-1〉,x_n〉 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 ≡ "E"fwhere "Ef is an expression built from primitives, other defined functions, and the function symbol f"' itself, using functionals.

ee also

* FL programming language (Backus' successor to FP)
* Function-level programming
* Programs as mathematical objects
* J programming language
* John Backus

References

* [http://www.stanford.edu/class/cs242/readings/backus.pdf Can Programming Be Liberated from the von Neumann Style?] Backus' Turing award lecture.