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
lambdacalculus. 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.
(20021103)
Nearby terms:
com « COMAL « combination « combinator »
combinatory logic » Comdex » COME FROM
