View source for Super combinator

A supercombinator is either a constant, or a [[combinator]] which contains only supercombinators as [[subexpression]]s.

To get a fuller idea of what a supercombinator is, it may help to use the following equivalent definition:

Any lambda expression is of the form <code>\x1 x2 .. xn -> E</code>, where E is not a lambda abstraction and n&ge;0.  (Note that if the expression is ''not'' a lambda abstraction, n=0.)  This is a supercombinator if and only if:

* the only [[free variable]]s in E are x1..xn, and
* every lambda abstraction in E is a supercombinator.

So these are supercombinators:

* <code>0</code>
* <code>\x y -> x + y</code>
* <code>\f -> f (\x -> x + x)</code>

These are not combinators, let alone supercombinators, because in each case, the variable y occurs free:

* <code>\x -> y</code>
* <code>\x -> y + x</code>

This is a combinator, but not a supercombinator, because the inner lambda abstraction is not a combinator:

* <code>\f g -> f (\x -> g x 2)</code>

Any lambda calculus expression (or, indeed, Haskell program) with no free variables can be converted into supercombinators using [[lambda lifting]].  For example, the last example can be expressed as:

* <code>\f g -> f ((\h x -> h x 2) g)</code>

Because supercombinators have no free variables, they can always be given their own names and [[lifting pattern|let floated]] to the top level.  The last example, for example, can be rewritten as:

* <code>let { scF h x = h x 2; scE f g = f (scF g) } in scE</code>

Some older compilers for Haskell-like languages, such as [[Gofer]], used this as part of the compilation process.  Converting a whole program into supercombinators leaves no internal lambda abstractions left, and each supercombinator can then be compiled more or less directly into a lower-level language, such as the [[G machine]].

A supercombinator which is not a lambda abstraction (i.e. for which n=0) is called a [[constant applicative form]].

[[Category:Glossary]]
[[Category:Combinators]]