A supercombinator is a
mathematical expression
In mathematics, an expression or mathematical expression is a finite combination of symbols that is well-formed according to rules that depend on the context. Mathematical symbols can designate numbers ( constants), variables, operations, fun ...
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 compu ...
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
1.λx
2...λ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.
Functional programming
Implementation of functional programming languages
Lambda calculus
{{comp-sci-theory-stub