Personal tools

Super combinator

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(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 non-Combinator 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&ge;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.