# FP (programming language)

(Redirected from FP programming language)
FP
Designed by John Backus
First appeared 1977

FP (short for Function Programming) is a programming language created by John Backus to support the function-level programming[2] paradigm. This allows eliminating 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 primitive function is constant, which transforms a value x into the constant-valued function . 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
=  ⊥   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:(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.