# FP (programming language)

**FP** (short for *functional programming*)^{[1]} is a programming language created by John Backus to support the function-level programming^{[1]} paradigm. This allows eliminating named variables. The language was introduced in Backus's 1977 Turing Award paper, "Can Programming Be Liberated from the von Neumann Style?", subtitled "a functional style and its algebra of programs." The paper sparked interest in functional programming research,^{[2]} eventually leading to modern functional languages, and not the function-level paradigm Backus had hoped.

In his Turing award paper, Backus described how the FP style is different from languages based on the lamba calculus:

An FP system is based on the use of a fixed set of combining forms called functional forms. These, plus simple simple definitions, are the only means of building new functions from existing ones; they use no variables or substitutions rules, and they become the operations of an associated algebra of programs. All the functions of an FP system are of one type: they map objects onto objects and always take a single argument.

^{[1]}

FP itself never found much use outside of academia.^{[3]} In the 1980s Backus created a successor language, FL, which remained a research project.

## Contents

## Overview

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

ifx_{1},...,x_{n}arevalues, then thesequence〈x_{1},...,x_{n}〉 is also avalue

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_{1},...,⊥,...,x_{n}〉 =⊥

FP programs are *functions* **f** that each map a single *value* **x** into another:

f:xrepresents thevaluethat results from applying thefunctionfto thevaluex

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:

:〈ix_{1},...,x_{n}〉 =x_{i}if 1 ≤≤ n = ⊥ otherwisei

## 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 += 0unit ×= 1unit foo= ⊥

These are the core functionals of FP:

compositionf∘gwheref∘g:x=f:(g:x)

construction[f_{1},...,f_{n}] where [f_{1},...,f_{n}]:x= 〈f_{1}:x,...,f_{n}:x〉

condition(h⇒f;g) where (h⇒f;g):x=f:xifh:x=T=g:xifh:x=F=⊥otherwise

apply-to-allαfwhereαf:〈x_{1},...,x_{n}〉 = 〈f:x_{1},...,f:x_{n}〉

insert-right/fwhere /f:〈x〉 =xand /f:〈x_{1},x_{2},...,x_{n}〉 =f:〈x_{1},/f:〈x_{2},...,x_{n}〉〉 and /f:〈 〉 =unit f

insert-left\fwhere \f:〈x〉 =xand \f:〈x_{1},x_{2},...,x_{n}〉 =f:〈\f:〈x_{1},...,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.

## 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.

## See also

## References

- ↑
^{1.0}^{1.1}^{1.2}Backus, J. (1978). "Can programming be liberated from the von Neumann style?: A functional style and its algebra of programs".*Communications of the ACM***21**(8): 613. doi:10.1145/359576.359579. - ↑ Yang, Jean (2017). "Interview with Simon Peyton-Jones". https://www.cs.cmu.edu/~popl-interviews/peytonjones.html.
- ↑ Hague, James (December 28, 2007). "Functional Programming Archaeology". http://prog21.dadgum.com/14.html.

*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

- FP Implementations

- Interactive FP (requires Java)
- Furry Paws, FP compiler written in FP
- FP interpreter in Lisp
- Fita Project (German)

*https://en.wikipedia.org/wiki/FP (programming language) was the original source. Read more*.