Supercombinator

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:

1. S has no free variables.
2. any lambda abstraction in E is a supercombinator.
3. n ≥ 0, so that lambdas are not required.

References

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