Supercombinator

This article's factual accuracy is disputed. Relevant discussion may be found on the talk page. Please help to ensure that disputed statements are reliably sourced. (November 2015) (Learn how and when to remove this message)

This article may need to be rewritten to comply with Wikipedia's quality standards. You can help. The talk page may contain suggestions. (November 2015)

A supercombinator is a mathematical expression which is fully bound and self-contained. It may be either a constant or a combinator where all the subexpressions are supercombinators. Supercombinators are used in the implementation of functional languages.

In mathematical terms, a lambda expression S is a supercombinator of arity n if it has no free variables and is of the form λx₁.λx₂...λx_n.E (with n ≥ 0, so that lambdas are not required) such that E itself is not a lambda abstraction and any lambda abstraction in E is again a supercombinator.

See also

• Lambda lifting

References

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