Super combinator
From HaskellWiki
m (Formatting fix) 
(Lambda lifting example) 

Line 23:  Line 23:  
* <code>\f g > f (\x > g x 2)</code>  * <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>  
+  
+  A supercombinator which is not a lambda abstraction (i.e. for which n=0) is called a [[Constant applicative form]].  
[[Category:Glossary]]  [[Category:Glossary]]  
[[Category:Combinators]]  [[Category:Combinators]] 
Revision as of 05:08, 1 February 2010
A super combinator is either a constant, or a Combinator which contains only super combinators as subexpressions.
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 \x1 x2 .. xn > E
, where E is not a lambda abstraction and n≥0. (Note that if the expression is not a lambda abstraction, n=0.) This is a supercombinator if and only if:
 the only free variables in E are x1..xn, and
 every lambda abstraction in E is a supercombinator.
So these are supercombinators:

0

\x y > x + y

\f > f (\x > x + x)
These are not combinators, let alone supercombinators, because in each case, the variable y occurs free:

\x > y

\x > y + x
This is a combinator, but not a supercombinator, because the inner lambda abstraction is not a combinator:

\f g > f (\x > g x 2)
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:

\f g > f ((\h x > h x 2) g)
A supercombinator which is not a lambda abstraction (i.e. for which n=0) is called a Constant applicative form.