fp programming language

FP (short for Function Programming) is a programming language created by John Backus to support the Function-level programming paradigm.

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 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 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 ≡ 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:⟨x₁,...,x_n⟩  =  x₁  i:⟨x₁,...,x_n⟩  =  x_i  if  0 < i ≤ n                =  ⊥   otherwise