closure-vs-combinator


Both closures and combinators can be defined as "functions which have no free variables." So what's the difference?

Michael-Micek

This page is linked from the glossary and is intended for curious beginners who are trying to get up to speed on the terms "closure", "combinator", and "free variable", not as if someone more advanced could actually be confused about the difference.


Pretty sure I read somewhere a closure could be defined as a function whose free variables had all been bound, thus, they weren't free. That's what I was going to put in that page.
<zarchne> And other stuff, more exploring the concepts than, as I say, really expecting them to be comparable.
<foof> From a scheme implementation perspective, there's a huge difference. A combinator is essentially a constant. It's trivial to make them eq? or provide serialization of them.
<zarchne> Jibes.
<forcer> It's a bit difficult
<foof> kawa, mzscheme and stalin provide eq? combinators
<forcer> "free variables" is something you can say about the lexical structure of a function, not about the function value
<Fare> rabbit, gambit, hobbit, twobit, etc, is there already a scheme compiler named weebit?
<Riastradh> Not that I know of.
<Fare> and what did "BIT" stand for, already?
<Riastradh> Nothing. It's just a naming convention for Scheme compilers.
<zarchne> Because It's Time?
<forcer> ((lambda (x) (lambda (y) (+ x y))) 1) - this does not have any free variables, but when evaluated, the value will be a closure which references a variable "outside" of itself.
<zarchne> (Sorry, that's BITNET, which should not be referred to.)
<forcer> In a purely functional world, that would be equivalent, but we do have mutation :-)
<Riastradh> forcer, no, it does have a free variable: +
<forcer> Riastradh: Indeed
<forcer> Make that (x y)
<forcer> ;-)
<forcer> or (y x)
<forcer> since x is 1
<forcer> Anyways, I guess my point is clear
<Riastradh> Then (LAMBDA (X) (LAMBDA (Y) (X Y))) evaluates to a combinator.
<Fare> nobody really knows what is a combinator... anything you want can be a combinator.
<Riastradh> The result of that combinator is not itself a combinator, but that expression itself does evaluate to a combinator.
<Fare> just define it as a combinator, and there you go.
<Riastradh> Fare, no, 'combinator' has a very precise definition: a function with no free variables.
<Fare> Riastradh: wrong. See Curry's Illative Combinatory Logic.
<Fare> Is the Pi combinator a function with no variable?
<Fare> (it basically means "for all")
<Riastradh> In today's world of computer science, that is the definition of combinator.
<forcer> Riastradh: The result of ((lambda (x) (lambda (y) (y x))) 1) will be a closure which references a value "outside of itself", and in a slightly more complicated example, that value could be shared between closures
<Fare> Riastradh: speak for yourself
<Fare> in unlambda, there is a combinator for echoing a character to terminal, and another one for call/cc
<zarchne> One more question. Riastradh, is the term "combinator" really that useful apart from results that came from combinatory logic?
<foof> zarchne: implementations can perform special optimizations on combinators.
<zarchne> okay, gotcha.
<Riastradh> It is useful to have a term to describe procedures that require no reference to the closing lexical environment.
<Riastradh> They can be moved about arbitrarily, since they are not restricted by scope accessibility.


category-learning-scheme