Super combinator
From HaskellWiki
BrettGiles (Talk  contribs) (HaWiki conversion) 
(Using supercombinators for compilation) 

(5 intermediate revisions by 3 users not shown)  
Line 1:  Line 1:  
−  A  +  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 Haskell program can be converted into  +  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: 
+  
+  * 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 patternlet 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 Haskelllike 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 lowerlevel 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:Glossary]]  
+  [[Category:Combinators]] 
Latest revision as of 06:11, 20 July 2010
A supercombinator is either a constant, or a combinator which contains only supercombinators 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)
Because supercombinators have no free variables, they can always be given their own names and let floated to the top level. The last example, for example, can be rewritten as:

let { scF h x = h x 2; scE f g = f (scF g) } in scE
Some older compilers for Haskelllike 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 lowerlevel 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.