Difference between revisions of "Super combinator"
(Using supercombinators for compilation) |
|||
(3 intermediate revisions by the same user 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: |
||
− | ''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.'' |
||
+ | 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: |
||
− | Any Haskell program can be converted into super combinators using [[Lambda lifting]]. |
||
+ | * the only [[free variable]]s in E are x1..xn, and |
||
− | '''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? |
||
+ | * 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 pattern|let 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 Haskell-like 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 lower-level 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]]. |
||
− | See also [[Constant applicative form]] |
||
[[Category:Glossary]] |
[[Category:Glossary]] |
||
[[Category:Combinators]] |
[[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 Haskell-like 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 lower-level 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.