combinator

You are here: irt.org | FOLDOC | 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

FOLDOC, Topics, A, B, C, D, E, F, G, H, I, J, K, L, M, N, O, P, Q, R, S, T, U, V, W, X, Y, Z, ?, ALL