Super Combinators

A combinator is a LambdaCalculus expression that satisfies the following two conditions:

No variable name occurs free in it.
No Lambda abstraction may occur inside a function application, i.e. something like (\x.x) f is not allowed.

The functions S, K and I as mentioned in EssAndKayCombinators, are combinators.

Combinators can always be written in a form that looks like this:

  Y f x = x (f x)

i.e. the right-hand side contains only function application and arguments that have been bound in the left-hand side.

It is possible to transform every LambdaCalculus expression (that contains no free variables) into a set of combinator definitions C_1 ... C_n and a single expression containing only applications of C_1 ... C_n. The SKI calculus, as described in EssAndKayCombinators, is an existential proof: just take C_1 = S, C_2 = I and C_3 = K. But for practical implementation of a FunctionalProgramming language, a better idea is not to try to get around with a minimal set of combinators, but to find a (possibly large) set of combinators that naturally matches the lambda expression you are trying to evaluate.

Such combinators can become a lot bigger than the small S, K and I combinators, therefore they are called SuperCombinators.

SuperCombinators can rather easily be translated into C or assembly language. In this way, a FunctionalProgramming language can be implemented efficiently.

Introduced by Turner (1979) and generalized by Hughes (1982):

D. A. Turner. A new implementation technique for applicative languages. Software - Practice and Experience, 9:31--49, 1979.

Hughes, J. M. (1982), Super-combinators: A new implementation method for applicative languages, in `1982 ACM Symposium on LISP and Functional Programming', Pittsburgh, Pensylvania, pp. 1--10.

CategoryFunctionalProgramming