Combinator
<theory> A function with no free variables.
A term is either a constant, a variable or of the form A B denoting the
application of term A (a function of one argument) to term B.
Juxtaposition associates to the left in the absence of parentheses.
All combinators can be defined from 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
lambda-calculus.
The size of equivalent expressions in the two languages are of the same order.
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
See
fixed point combinator,
curried function, supercombinators.
