Difference between revisions of "Super combinator"
(Rewrite to explain what's really going on.) |
m (Formatting fix) |
||
Line 10: | Line 10: | ||
So these are supercombinators: |
So these are supercombinators: |
||
− | * <code>0<code> |
+ | * <code>0</code> |
* <code>\x y -> x + y</code> |
* <code>\x y -> x + y</code> |
||
* <code>\f -> f (\x -> x + x)</code> |
* <code>\f -> f (\x -> x + x)</code> |
||
Line 25: | Line 25: | ||
A supercombinator which is not a lambda abstraction (i.e. n=0) is called a [[Constant applicative form]]. |
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]]. |
+ | Any lambda calculus expression (or, indeed, Haskell program) can be converted into supercombinators using [[Lambda lifting]]. |
[[Category:Glossary]] |
[[Category:Glossary]] |
Revision as of 03:52, 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)
A supercombinator which is not a lambda abstraction (i.e. n=0) is called a Constant applicative form.
Any lambda calculus expression (or, indeed, Haskell program) can be converted into supercombinators using Lambda lifting.