Super combinator
From HaskellWiki
(Rewrite to explain what's really going on.) 

Line 1:  Line 1:  
A super combinator is either a constant, or a [[Combinator]] which contains only super combinators as subexpressions. 
A super combinator is either a constant, or a [[Combinator]] which contains only super combinators as subexpressions. 

−  ''This definition is bewildering until you realize that a [[Combinator]] can have nonCombinator internal subexpressions. A super combinator is "internally pure" (every internal lambda is a combinator) as well as externally.'' 
+  To get a fuller idea of what a supercombinator is, it may help to use the following equivalent definition: 
−  Any Haskell program can be converted into super combinators using [[Lambda lifting]]. 
+  Any lambda expression is of the form <code>\x1 x2 .. xn > E</code>, 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: 
−  '''Question:''' Is \x y > x+y a supercombinator? You could get this by lambda lifting \x > x+y in some context, but as in Haskell all functions are of single argument only it's really \x > \y > x+y, where x is free in the inner lambda. In addition to lambda lifting, do you have to uncurry it to \(x, y) > x+y? 
+  * 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> 

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

+  
+  Any Haskell program can be converted into supercombinators using [[Lambda lifting]]. 

−  See also [[Constant applicative form]] 

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

[[Category:Combinators]] 
[[Category:Combinators]] 
Revision as of 03:51, 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<code>
<code>\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)
A supercombinator which is not a lambda abstraction (i.e. n=0) is called a Constant applicative form.
Any Haskell program can be converted into supercombinators using Lambda lifting.