Jump to content

Supercombinator

From Wikipedia, the free encyclopedia
This is an old revision of this page, as edited by Sesquiannual (talk | contribs) at 04:20, 19 November 2006 (reworded point iii). The present address (URL) is a permanent link to this revision, which may differ significantly from the current revision.

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
λx1.λx2...λxn.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.

References

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