views updated

combinator A lambda expression containing no free variables. While this is the most general definition, the word is usually understood more specifically to refer to certain combinators of special importance, in particular the following four:

I = λx . x

K = λx . λy . x

S = λx . λy . λz . x(z)(y(z))

Y = λf . (λu . f(u(u))) (λu . f(u(u)))

The combinators I, K, and S were introduced by Schönfinkel and Curry, who showed that any λ-expression can essentially be formed by combining them. More recently combinators have been applied to the design of implementations for functional languages. In particular Y (also called the paradoxical combinator) can be seen as producing fixed points, since Y(f) reduces to f(Y(f)).