Encyclopedia > Combinator

  Article Content


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.

See also:

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

All Wikipedia text is available under the terms of the GNU Free Documentation License

  Search Encyclopedia

Search over one million articles, find something about almost anything!
  Featured Article
Surreal number

... taking Sω and continuing to apply the construction rule to it and thus constructing Sω+1, Sω+2 et cetera. Note that the left sets and right sets may now ...