Function pointers, Closures, and Lambda

Question

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.

Answer 1

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.

Answer 2

In C, function pointers can be passed as arguments to functions and returned as values from functions, but functions exist only at top level: you cannot nest function definitions within each other. Think about what it would take for C to support nested functions that can access the variables of the outer function, while still being able to send function pointers up and down the call stack. (To follow this explanation, you should know the basics of how function calls are implemented in C and most similar languages: browse through the call stack entry on Wikipedia.)

What kind of object is a pointer to a nested function? It cannot just be the address of the code, because if you call it, how does it access the variables of the outer function? (Remember that because of recursion, there may be several different calls of the outer function active at one time.) This is called the funarg problem, and there are two subproblems: the downward funargs problem and the upwards funargs problem.

The downwards funargs problem, i.e., sending a function pointer "down the stack" as an argument to a function you call, is actually not incompatible with C, and GCC supports nested functions as downward funargs. In GCC, when you create a pointer to a nested function, you really get a pointer to a trampoline, a dynamically constructed piece of code that sets up the static link pointer and then calls the real function, which uses the static link pointer to access the variables of the outer function.

The upwards funargs problem is more difficult. GCC does not prevent you from letting a trampoline pointer exist after the outer function is no longer active (has no record on the call stack), and then the static link pointer could point to garbage. Activation records can no longer be allocated on a stack. The usual solution is to allocate them on the heap, and let a function object representing a nested function just point to the activation record of the outer function. Such an object is called a closure. Then the language will typically have to support garbage collection so that the records can be freed once there are no more pointers pointing to them.

Lambdas (anonymous functions) are really a separate issue, but usually a language that lets you define anonymous functions on the fly will also let you return them as function values, so they end up being closures.

Answer 3

The main difference arises from the lack of lexical scoping in C.

A function pointer is just that, a pointer to a block of code. Any non-stack variable that it references is global, static or similar.

A closure, OTOH, has its own state in the form of 'outer variables', or 'upvalues'. they can be as private or shared as you want, using lexical scoping. You can create lots of closures with the same function code, but different variables instances.

A few closures can share some variables, and so can be the interface of an object (in the OOP sense). to make that in C you have to associate a structure with a table of function pointers (that's what C++ does, with a class vtable).

in short, a closure is a function pointer PLUS some state. it's a higher-level construct

Answer 4

A lambda is an anonymous, dynamically defined function. You just cannot do that in C... as for closures (or the convination of the two), the typical lisp example would look something along the lines of:

(defun get-counter (n-start +-number)
     "Returns a function that returns a number incremented
      by +-number every time it is called"
    (lambda () (setf n-start (+ +-number n-start))))

In C terms, you could say that the lexical environment (the stack) of get-counter is being captured by the anonymous function, and modified internally as the following example shows:

[1]> (defun get-counter (n-start +-number)
         "Returns a function that returns a number incremented
          by +-number every time it is called"
        (lambda () (setf n-start (+ +-number n-start))))
GET-COUNTER
[2]> (defvar x (get-counter 2 3))
X
[3]> (funcall x)
5
[4]> (funcall x)
8
[5]> (funcall x)
11
[6]> (funcall x)
14
[7]> (funcall x)
17
[8]> (funcall x)
20
[9]> 

Answer 5

Most of the responses indicate that closures require function pointers, possibly to anonymous functions, but as Mark wrote closures can exist with named functions. Here's an example in Perl:

{
    my $count;
    sub increment { return $count++ }
}

The closure is the environment that defines the $count variable. It is only available to the increment subroutine and persists between calls.

Answer 6

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.