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