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.

Last updated: 2002-11-03

Nearby terms:

combination ♦ combinator ♦ combinatory logic ♦ Combined object-oriented Language

Try this search on Wikipedia, Wiktionary, Google, OneLook.

Loading