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)