Supercombinator

From Wikipedia, the free encyclopedia

A supercombinator is a mathematical expression which is fully-bound and self-contained. It may either be a constant or a combinator where all the subexpressions are supercombinators.

It may be defined, in mathematical terms, as the following:

A supercombinator, $S of arity n is a lambda expression of the form

λx₁.λx₂...λx_n.E

where E is not a lambda abstraction, such that:

i) $S has no free variables.

ii) any lambda abstraction in E is a supercombinator.

iii) n >= 0, so that lambdas are not required.

[edit] References

• S. L. Peyton Jones, The Implementation of Functional Programming Languages. Prentice Hall, 1987.