Combinator

In mathematics, a combinator is a function with no free variables.

In computer science, combinators have been used as a basis for the semantics of functional programming languages.

A term of a combinator is either a constant, a variable, or an application of the form (A B), denoting the application of term A (a function of one argument) to term B. Application associates to the left in the absence of parentheses. All combinators can be defined as a composition of two basic combinators - S and K. These two and a third, I, are defined thus:

(S f g x)	= (f x (g x))

(K x y)	= x

(I x)	= x	= (S K K x)

There is a simple translation between combinatory logic and the lambda-calculus. However, combinatorial expressions are much larger than their lambda-calculus equivalents.

A combinator of particular interest is the Y combinator, which is a fixed point combinator and can be used to implement recursion.

Other combinators were added by David Turner in 1979 when he used combinators to implement SASL:

(B f g x) = (f (g x))

(C f g x) = (f x g)

(S' c f g x) = (c (f x) (g x))

(B* c f g x) = (c (f (g x)))

(C' c f g x) = (c (f x) g)

Some special-purpose computers have been built to perform combinator calculations by graph reduction. Examples include the SKIM ("S-K-I machine") computer, built at Cambridge University, and the multiprocessor GRIP ("Graph Reduction In Parallel") computer, built at UCL.