What's a Closure?

Other people have already answered this, but since you come from a C++ background, perhaps this will help.

Lambdas and closures get mentioned together because they don't make sense apart. "Lambda" is just a fancy term for an anonymous function, but it also implies that the function is created (sans optimizations) dynamically (i.e. at runtime). This doesn't ever happen in C++, so hence the confusion.

A closure is the concept that a dynamically created function carries with it the state in which it was created (in C++ terms, the callstack). Imagine for a moment we had a C++ keyword called "lambda" that could create functions at runtime. What would the following code do?

  typedef int (*function_t)(int);
  function_t accum(int x) {
    return lambda (int y) { return x+=y; };
  }

You see the problem? "x" is no longer on the stack once foo() returns, but the function we return from foo accesses it! In fact doing anything meaningful with "x" is bogus. The solution is to have dynamically created functions like this to logically copy the call-stack that they are created in, so that they can access any of these stack variables. This is a closure.

It is clear that you could have lambdas without closures, by either disallowing accessing any non-globals in your lambdas, or just having the behavior be undefined if the function accesses any variables that have left scope. In practice this makes for lots and lots of bugs, so the solution is closures.

The C++ way of combining a function with state, is to use a class (or a struct). Here's the C++ way of doing the above:

  class accum { 
    int x;
    accum(int x) : x(x) {}
    int operator()(int i) {return x+=i}
  }

Notice how you need to be explicit about what state you keep in the class. With closures the state kept around is implicit, but it is kept around too.

Do you know a way to disable strict identity over equality checking (=== vs ==)? It's a Crockford-ism, but I think the jury's still out on the value of strict type checking vs coercion and I'd like the choice.

One of these is easy, and two of these are hard.

A lambda is basically a function literal. Just like you have string literals ("string"), number literals (3), and array literals ({1, 2, 3}), you can have function literals (function(x, y){x+y}). C++ does not have these, so I used JavaScript syntax as it is the most similar.

A closure is a dynamic binding of parameters to a function in the scope of its definition. This is not a valid concept in C, because there is only one scope for function definitions. In C++, there are namespaces and classes, but these are static, so it still isn't quite right.

You'll need to imagine that you can define a function inside another function. Then, suppose you have something like this:

  int f1(int x, int y) {
    int f2(int z) {
      return x+z;
    }
    return f2(y);
  }

What should f1(1, 2) return? If C++ is extended with only the feature to define functions within functions, this will result in a compiler error: x is used undeclared in f2. If it is extended with static or lexical scoping, it will return 3. Lexical scoping is generally what you want; the alternative (dynamic scoping) is useful in a few cases but generally more confusing and less powerful.

Then, suppose you want to return a reference to f2 instead. We need to keep the x value around in order to be able to actually make use of the reference, so we store the reference along with that x value. The data structure containing the function reference and any values needed to use it is called a "closure". You can think of it as a function object containing a function pointer and some extra values, plus some behind-the-scenes magic to initialize it.

A monad is something entirely different. The most analogous thing in C is if you had the ability to define an extra computation that is applied at every semicolon. That computation might be for maintaining state, or for propagating errors, or for deciding which lines are actually run, or really anything.

If you're doing CPS in a language with tail-call optimization then the same stack frame will be used for all your function calls. I don't know if V8 does this. In something like Node you don't do full CPS, you have portions of your code in CPS but usually only a few layers deep as you need to give control back to the event loop at some point.

I see several explanations here already, none of which gets at the essence of the difference between a lambda expression and a closure.

A lambda expression (or juat "lambda" for short) is a syntactic construct: something you write in your program, like "(lambda (x) (+ x 1))" or "function (x) { return x + 1; }".

Lambda expressions, like any other evaluable expressions, have values. Just as the expression "2 + 2" has the value 4 which is represented in the machine as binary 100, so a lambda expression has a value, which is a function, and that value has a representation in the machine.

What is that representation? It turns out that the most general representation of a functional value is a closure, which is simply a code pointer with some associated data (or a pointer thereto). A function pointer in C is just a code pointer; this is an impoverished representation that requires the programmer, in order to write general higher-order functions (functions that take functions as arguments), to explicitly pass around a data pointer along with each function pointer, and pass the data pointer when calling through the function pointer:

  void foo(int (*f)(void* data, int x), void* data) {
    ... (*f)(data, n) ...
  }

You've surely seen this idiom if you've worked with function pointers much. A closure, again, packages up the two pieces together so you don't have to deal with them separately.

You can see the similarity between instances and closures. An instance has a vtable (in C++ parlance), which is an indexed collection of code pointers, along with its data. A closure, instead of having a vtable, has a single code pointer. Instances and closures are duals: an instance provides a collection of operations, while a closure provides only one. Other than that, they're identical.

So, to summarize: a lambda expression, like a `new' expression, is a syntactic construct you find in your code. Lambda expressions evaluate to closures just as `new' expressions evaluate to instances; closures and instances are implementation constructs, like binary integers, inside the machine.

Finally, note that the only difference between a function defined in the traditional way and one defined by a lambda expression is that the latter has no name. It's fine to call these "anonymous function expressions" if your language doesn't use the word "lambda".