A supercombinator is a

mathematical expression In mathematics, an expression or mathematical expression is a finite combination of Glossary of mathematical symbols, symbols that is well-formed formula, well-formed according to rules that depend on the context. Mathematical symbols can desi ...

which is fully bound and self-contained. It may be either a constant or a

combinator Combinatory logic is a notation to eliminate the need for quantified variables in mathematical logic. It was introduced by Moses Schönfinkel and Haskell Curry, and has more recently been used in computer science as a theoretical model of comput ...

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 Arity () is the number of arguments or operands taken by a function, operation or relation in logic, mathematics, and computer science. In mathematics, arity may also be named ''rank'', but this word can have many other meanings in mathematics. In ...

''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 Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation tha ...

and any lambda abstraction in ''E'' is again a supercombinator.

References

*S. L. Peyton Jones,
The Implementation of Functional Programming Languages
'. Prentice Hall, 1987. Functional programming Implementation of functional programming languages Lambda calculus {{comp-sci-theory-stub

See also

References