lambdaway :: supercombinator

2 | list | login |load

| |

{require lib_uncover}
{uncover https://miro.medium.com/max/2000/0*53T_bcXxZ5pd6Fm2 100 500 A supercombinator}

{center {i ( Here is a {i verbatim} transcript from a paper written by [[Harry R.Schwartz|https://harryrschwartz.com/assets/documents/articles/lifting-lambdas-into-supercompilers.pdf]].{div} I just added [[lambdatalk|?view=start]] code to be compared with Python examples. )}}
{center See this page displayed without [[uncovering effects|?view=supercombinator2]].}

_h1 Lifting Lambdas into Supercombinators

{{title}
_h2 Harry R. Schwartz July 26, 2017
}{{content}
_p I was recently reading about Edwin Brady’s supercombinator compiler, Epic. Epic is the backend powering [[Idris|https://link.springer.com/chapter/10.1007/978-3-319-15940-9_4]] and Epigram (and, optionally, Agda), so I figured it might be worth a look. A “supercombinator compiler” sure sounded impressive, but I didn’t know what it was. Let’s figure that out.
}

{{title}
_h2 First, What’s a Combinator?
}{{content}
_p A combinator is a piece of code (a term) in which all variables are bound. A variable is bound in a given term if it’s defined in that term. For example, in the λ-calculus, the term

{center λx.λy.(x y)}

_p is a combinator, since all of the variables in the body of the expression (that is, x and y) are bound as arguments. Conversely,

{center λx.(z x)}

_p isn’t a combinator, since z appears as a free variable.

_p Using λ-calculus is traditional, but we can talk about this in terms of a more conventional language, too, like Python. This function is a combinator, since both x and y are bound:

{pre
PYTHON                        LAMBDATALK
def combinator(x, y):     |   '{def combinator {lambda {x y}
    return x + y          |        {+ x y}}}
                          |     
combinator(3,4) -> 7      |   '{combinator 3 4} -> 7
}

_p Notes:
_ul 1) {i equivalent '{lambda talk} is added at the right of Python's code for comparison.}

_ul 2) strictly speaking this function is not a combinator, because {b +} is not in the argument's list and can be seen as a free variable. We will admit that when they are global constants, like {b +}, these variables are not to be considered as free variables. Functions have acces to global constants. It's the way followed by Simon Peyton Jones in [[The Implementation of Functional Programming Languages|https://www.microsoft.com/en-us/research/uploads/prod/1987/01/slpj-book-1987.pdf]], 1987. Specifically, see “§13: Supercombinators and Lambda- Lifting”.

_p This function isn’t, since y is free:

{pre
PYTHON                       LAMBDATALK
def not_a_combinator(x):  |  '{def not_a_combinator {lambda {x}
    return x + y          |       {+ x y}}}
                          |
not_combinator(3) -> ???  | '{not_a_combinator 3} -> NaN
}

_p Combinators are interesting because they’re self-contained, or “closed.” They don’t rely on any information unless it’s passed in as an argument, so they compose well, (note 1) which makes them easy to reason about.
}

{{title}
_h2 So, What’s a Supercombinator?
}{{content}
_p A supercombinator is recursively defined as “a combinator whose every sub-term is also a supercombinator.” In other words, a supercombinator is a combinator whose every term, sub-term, sub-sub-term, etc., is also a combinator. Some lambda expressions are combinators, and some combinators are supercombina- tors.

_p For example, here’s a supercombinator:

{center λx.(λy.y y)(x x)}

_p Note that the inner term λy.y y is also a supercombinator.

_p On the other hand, here’s a combinator that isn’t a supercombinator:

{center λx.(λy.x y)}

_p The inner term λy.x y isn’t a combinator because x is free within it, which means that the whole expression isn’t a supercombinator.
}

{{title}
_h2 Generating Supercombinators
}{{content}
_p Every combinator can be transformed into an equivalent (note 2) supercombinator. For example, in Python, we might have a function like:

{pre
PYTHON                       LAMBDATALK
def outside(x):           |  '{def outside
    def inside(y):        |    {def inside {lambda {y} 
        return x + y      |        {+ x y}}}
    return inside(5)      |    {lambda {x} 
                          |        {inside x 5}}}
outside(3) -> 8           |  '{outside 3} -> NaN  // no closures in lambdatalk!!
}

_p This is a combinator, but not a supercombinator. x is a free variable within the definition of inside. However, we could transform this expression by passing in x as an additional argument to inside, like so:

{pre
PYTHON                       LAMBDATALK
def outside(x):           |  '{def outside
    def inside(x, y):     |       {def inside
        return x + y      |            {lambda {x y} 
    return inside(x, 5)   |                {+ x y}}}
                          |       {lambda {x}
                          |            {inside x 5}}}
outside(3) -> 8           |  '{outside 3} -> 8

;; {def outside {lambda {x} {inside x 5}}}
;; {def inside {lambda {x y} {+ x y}}}
;; {outside 3}
}

_p Now that inside doesn’t reference a free variable, we can lift it into the global context, like so:

{pre
PYTHON                       LAMBDATALK
def inside(x, y):         |  '{def inside {lambda {x y}
    return x + y          |       {+ x y}}}
def outside(x):           |  '{def outside {lambda {x}
    return inside(x, 5)   |       {inside x 5}}}
                          |
outside(3) -> 8           |  '{outside 3} -> 8
}

_p We’ve eliminated the closure and the function nesting, and the original and transformed expressions still do the same thing. Our code now consists of a pair of supercombinators! Neat.

_p This act of (1) replacing free variables with arguments and (2) extracting the new combinator into the global context is called lambda lifting. To phrase it another way, lambda lifting is an algorithm for turning closures (that is, functions with free variables) into pure global functions.
}

{{title}
_h2 Compiling with Supercombinators
}{{content}
_p Since every term in a supercombinator is independent of its context—that is, it contains no free variables—compiling a program structured as a collection of supercombinators is much simpler than it would be otherwise. Every λ term can be compiled to a global function, with no nesting or closures.

_p We could imagine designing a compiler for a purely functional language which:
_ul 1. Receives some input code which has been structured as a collection of combinators,
_ul 2. Applies lambda lifting to transform the input into an equivalent collection of supercombinators, and
_ul 3. Compiles them into a target language, with each term corresponding to a top-level function.

_p I’m sure I’m eliding a lot of complexity here, especially in that last step, but this seems to be the general idea.

_p So, if we wanted to build a language on top of Epic, we’d first write a compiler from our language to Epic’s input language (an extended form of the λ-calculus). Epic would take our jumble of expressions, lambda-lift it into a collection of supercombinators, and generate C code based on those pure, global functions.
}

{{title}
_h2 Notes
}{{content}
_ul 1) They compose so well, in fact, that you can build logical systems on top of them with expressiveness equal to the λ-calculus. The SKI and BCKW calculi are prominent examples. 
_ul 2) By equivalent, I specifically mean that two combinators of the same arity will β-reduce to the same expression when given the same arguments. If that doesn’t mean anything to you, that’s OK; your intuitive definition of “equivalent” is probably correct. :-)
}

{{title}
_h2 References
}{{content}
_p There don’t seem to be too many references to compiling with supercombinators floating around. The few that I’ve seen are pretty good, though:
_ul Simon Peyton Jones, [[The Implementation of Functional Programming Languages|https://www.microsoft.com/en-us/research/uploads/prod/1987/01/slpj-book-1987.pdf]], 1987. Specifically, see “§13: Supercombinators and Lambda- Lifting” for a thoroughly relevant elaboration.
_ul John Hughes, Super-Combinators: A New Implementation Method for Applicative Languages, 1982.
_ul [[Edwin Brady|https://www.type-driven.org.uk/edwinb/]], ecb10@st-andrews.ac.uk, Epic—A Library for Generating Compilers, 2011.
}
{hr}
{{title}
_h2 about '{lambda talk}
}{{content}
_p In '{lambda talk} all functions (lambdas) are supercombinators, functions can't have free variables and are independant of any lexical context. The natural way to play with an outside and an inside functions would be to write an IIFE:

{pre
'{def outside_2 {lambda {x} 
      // x is passed to the inside function via an IIFE
    {{lambda {y} {+ 5 y}} x} 
}}
-> {def outside_2 {lambda {x}
   {{lambda {y} {+ 5 y}} x}}}

'{outside_2 3}
-> {outside_2 3}
}

_p  See more about [[lambda]]s in lambdatalk.
}

{{hide}

{def title div
 {@ class="scala" onclick="
 this.nextSibling.style.transform=
(this.nextSibling.style.transform==='scale(0)')? 'scale(1)' : 'scale(0)';
 this.nextSibling.style.height=
(this.nextSibling.style.height==='0px')? 'auto' : '0px';"}}

{def content div
{@ style="transform:scale(0); height:0px; transition:all 1.0s;"}
;; {@ style="transform:scale(1); height:auto; transition:all 1.0s;"}
}
}

{style 
h1,h2,h3 { text-align:center; }
pre { box-shadow:0 0 8px #000; padding:5px;  }
.scala { cursor:pointer; color:#800; }
.scala:hover { color:#f00; font-size:1.01em; }
img:hover { transform:scale(1.01); }
}