Function pointers, Closures, and Lambda

I am just now learning about function pointers and, as I was reading the K&R chapter on the subject, the first thing that hit me was, "Hey, this is kinda like a closure." I knew this assumption is fundamentally wrong somehow and after a search online I didn't find really any analysis of this comparison.

So why are C-style function pointers fundamentally different from closures or lambdas? As far as I can tell it has to do with the fact that the function pointer still points to a defined (named) function as opposed to the practice of anonymously defining the function.

Why is passing a function to a function seen as more powerful in the second case, where it is unnamed, than the first where it is just a normal, everyday function that is being passed?

Please tell me how and why I am wrong to compare the two so closely.

Thanks.

A lambda (or closure) encapsulates both the function pointer and variables. This is why, in C#, you can do:

int lessThan = 100;
Func<int, bool> lessThanTest = delegate(int i) {
   return i < lessThan;
};

I used an anonymous delegate there as a closure (it's syntax is a little clearer and closer to C than the lambda equivalent), which captured lessThan (a stack variable) into the closure. When the closure is evaluated, lessThan (whose stack frame may have been destroyed) will continue to be referenced. If I change lessThan, then I change the comparison:

int lessThan = 100;
Func<int, bool> lessThanTest = delegate(int i) {
   return i < lessThan;
};

lessThanTest(99); // returns true
lessThan = 10;
lessThanTest(99); // returns false

In C, this would be illegal:

BOOL (*lessThanTest)(int);
int lessThan = 100;

lessThanTest = &LessThan;

BOOL LessThan(int i) {
   return i < lessThan; // compile error - lessThan is not in scope
}

though I could define a function pointer that takes 2 arguments:

int lessThan = 100;
BOOL (*lessThanTest)(int, int);

lessThanTest = &LessThan;
lessThanTest(99, lessThan); // returns true
lessThan = 10;
lessThanTest(100, lessThan); // returns false

BOOL LessThan(int i, int lessThan) {
   return i < lessThan;
}

But, now I have to pass the 2 arguments when I evaluate it. If I wished to pass this function pointer to another function where lessThan was not in scope, I would either have to manually keep it alive by passing it to each function in the chain, or by promoting it to a global.

Though most mainstream languages that support closures use anonymous functions, there is no requirement for that. You can have closures without anonymous functions, and anonymous functions without closures.

Summary: a closure is a combination of function pointer + captured variables.

As someone who has written compilers for languages both with and without 'real' closures, I respectfully disagree with some of the answers above. A Lisp, Scheme, ML, or Haskell closure does not create a new function dynamically. Instead it reuses an existing function but does so with new free variables. The collection of free variables is often called the environment, at least by programming-language theorists.

A closure is just an aggregate containing a function and an environment. In the Standard ML of New Jersey compiler, we represented one as a record; one field contained a pointer to the code, and the other fields contained the values of the free variables. The compiler created a new closure (not function) dynamically by allocating a new record containing a pointer to the same code, but with different values for the free variables.

You can simulate all this in C, but it is a pain in the ass. Two techniques are popular:

1. Pass a pointer to the function (the code) and a separate pointer to the free variables, so that the closure is split across two C variables.

2. Pass a pointer to a struct, where the struct contains the values of the free variables and also a pointer to the code.

Technique #1 is ideal when you are trying to simulate some kind of polymorphism in C and you don't want to reveal the type of the environment---you use a void* pointer to represent the environment. For examples, look at Dave Hanson's C Interfaces and Implementations. Technique #2, which more closely resembles what happens in native-code compilers for functional languages, also resembles another familiar technique... C++ objects with virtual member functions. The implementations are almost identical.

This observation led to a wisecrack from Henry Baker:

People in the Algol/Fortran world complained for years that they didn't understand what possible use function closures would have in efficient programming of the future. Then the `object oriented programming' revolution happened, and now everyone programs using function closures, except that they still refuse to to call them that.

In C you can't define the function inline, so you can't really create a closure. All you're doing is passing around a reference to some pre-defined method. In languages that support anonymous methods/closures, the definition of the methods are a lot more flexible.

In the simplest terms, function pointers have no scope associated with them (unless you count the global scope), whereas closures include the scope of the method that's defining them. With lambdas, you can write a method that writes a method. Closures allow you to bind "some arguments to a function and getting a lower-arity function as a result." (taken from Thomas's comment). You can't do that in C.

EDIT: Adding an example (I'm going to use Actionscript-ish syntax cause that's what's on my mind right now):

Say you have some method that takes another method as its argument, but doesn't provide a way to pass any parameters to that method when it's called? Like, say, some method that causes a delay before running the method you passed it (stupid example, but I want to keep it simple).

function runLater(f:Function):Void {
  sleep(100);
  f();
}

Now say you want to user runLater() to delay some processing of an object:

function objectProcessor(o:Object):Void {
  /* Do something cool with the object! */
}

function process(o:Object):Void {
  runLater(function() { objectProcessor(o); });
}

The function you're passing to process() isn't some staticly defined function anymore. It's dynamically generated, and is able to include references to variables that were in scope when the method was defined. So, it can access 'o' and 'objectProcessor', even though those aren't in the global scope.

I hope that made sense.