Personal tools

Super combinator

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(Lambda lifting example)
(Using supercombinators for compilation)
 
Line 1: Line 1:
A super combinator is either a constant, or a [[Combinator]] which contains only super combinators as subexpressions.
+
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:
 
To get a fuller idea of what a supercombinator is, it may help to use the following equivalent definition:
Line 23: Line 23:
 
* <code>\f g -> f (\x -> g x 2)</code>
 
* <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:
+
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>
 
* <code>\f g -> f ((\h x -> h x 2) g)</code>
   
A supercombinator which is not a lambda abstraction (i.e. for which n=0) is called a [[Constant applicative form]].
+
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]].
   
 
[[Category:Glossary]]
 
[[Category:Glossary]]

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.