combinator
A function with no {free variable}s. 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
{Combinatory logic} is equivalent to the {lambda-calculus} but
a lambda expression of size O(n) is equivalent to a
combinatorial expression of size O(n^2).
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},
{supercombinator}s.
(1994-12-06)