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 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 one such operation is constant, which transforms a value x into the constant-valued function x̄. Functions are strict:

f:⊥ = ⊥

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 =  ⊥

Functionals

These are the core functionals of FP:

constant     x̄         where   x̄:y = x

composition  f&#x°g        where    f&#x°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.

An 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

See also

• FL programming language (Backus' successor to FP)
• Function-level programming
• Programs as mathematical objects
• J and NGL programming languages
• John Backus