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

In C a function pointer is a pointer that will invoke a function when you dereference it, a closure is a value that contains a function's logic and the environment (variables and the values they are bound to) and a lambda usually refers to a value that is actually an unnamed function. In C a function is not a first class value so it cannot be passed around so you have to pass a pointer to it instead, however in functional languages (like Scheme) you can pass functions in the same way you pass any other value

Answer 2

In GCC it is possible to simulate lambda functions using the following macro:

#define lambda(l_ret_type, l_arguments, l_body)       \
({                                                    \
    l_ret_type l_anonymous_functions_name l_arguments \
    l_body                                            \
    &l_anonymous_functions_name;                      \
})

Example from source:

qsort (array, sizeof (array) / sizeof (array[0]), sizeof (array[0]),
     lambda (int, (const void *a, const void *b),
             {
               dump ();
               printf ("Comparison %d: %d and %d\n",
                       ++ comparison, *(const int *) a, *(const int *) b);
               return *(const int *) a - *(const int *) b;
             }));

Using this technique of course removes the possibility of your application working with other compilers and is apparently "undefined" behavior so YMMV.

Answer 3

The closure captures the free variables in an environment. The environment will still exist, even though the surrounding code may no longer be active.

An example in Common Lisp, where MAKE-ADDER returns a new closure.

CL-USER 53 > (defun make-adder (start delta) (lambda () (incf start delta)))
MAKE-ADDER

CL-USER 54 > (compile *)
MAKE-ADDER
NIL
NIL

Using the above function:

CL-USER 55 > (let ((adder1 (make-adder 0 10))
                   (adder2 (make-adder 17 20)))
               (print (funcall adder1))
               (print (funcall adder1))
               (print (funcall adder1))
               (print (funcall adder1))
               (print (funcall adder2))
               (print (funcall adder2))
               (print (funcall adder2))
               (print (funcall adder1))
               (print (funcall adder1))
               (describe adder1)
               (describe adder2)
               (values))

10 
20 
30 
40 
37 
57 
77 
50 
60 
#<Closure 1 subfunction of MAKE-ADDER 4060001ED4> is a CLOSURE
Function         #<Function 1 subfunction of MAKE-ADDER 4060001CAC>
Environment      #(60 10)
#<Closure 1 subfunction of MAKE-ADDER 4060001EFC> is a CLOSURE
Function         #<Function 1 subfunction of MAKE-ADDER 4060001CAC>
Environment      #(77 20)

Note that the DESCRIBE function shows that the function objects for both closures are the same, but the environment is different.

Common Lisp makes both closures and pure function objects (those without an environment) both to be functions and one can call both in the same way, here using FUNCALL.

Answer 4

Closures imply some variable from the point of function definition is bound together with the function logic, like being able to declare a mini-object on the fly.

One important problem with C and closures is variables allocated on the stack will be destroyed on leaving the current scope, regardless of if a closure was pointing to them. This would lead to the kind of bugs people get when they carelessly return pointers to local variables. Closures basically imply all relevant variables are either ref-counted or garbage-collected items on a heap.

I'm not comfortable equating lambda with closure because I'm not sure that lambdas in all languages are closures, at times I think lambdas have just been locally defined anonymous functions without the binding of variables (Python pre 2.1?).

Answer 5

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.

Answer 6

Closure = logic + environment.

For instance, consider this C# 3 method:

public Person FindPerson(IEnumerable<Person> people, string name)
{
    return people.Where(person => person.Name == name);
}

The lambda expression not only encapsulates the logic ("compare the name") but also the environment, including the parameter (i.e. local variable) "name".

For more on this, have a look at my article on closures which takes you through C# 1, 2 and 3, showing how closures make things easier.