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 lambdacalculus. However, combinatorial expressions are much larger than their lambdacalculus 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 specialpurpose computers have been built to perform combinator calculations by graph reduction[?]. Examples include the SKIM[?] ("SKI 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.
Search Encyclopedia
