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:

(There is a simple translation between combinatory logic and the lambda-calculus. However, combinatorial expressions are much larger than their lambda-calculus equivalents.Sfgx) = (fx(gx)) (Kxy) =x(Ix) =x= (SKKx)

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:

(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.Bfgx) = (f(gx)) (Cfgx) = (fxg) (S'cfgx) = (c(fx) (gx)) (B*cfgx) = (c(f(gx))) (C'cfgx) = (c(fx)g)

See also:

- curried function
- supercombinators
- combinatory logic

*The original version of article was based on material from FOLDOC, used with permission.*