Brief introduction to four programming language concepts

March 27th, 2007

The following is a whirlwind introduction to four widely misunderstood concepts in programming languages: closures, classes, callbacks, and continuations. (It would be more accurate to say “objects” rather than “classes”, but I couldn’t pass up the opportunity to alliterate.) It is written for a technical audience with some software engineering experience.

I wrote this article a couple of years ago and was recently asked to republish it; I thought I would do it here.

About closures

Closures are functions which remember their lexical environment, i.e. have some state of their own. You can think of a closure as a little package of two items: a pointer to a function and a pointer to a set of name/variable bindings. Closures can typically be treated like any other programming language objects, e.g. they can be stored in variables, passed to functions, and so on.

The best way to understand closures is to think about some examples in Scheme. Here is an extremely brief introduction to Scheme syntax:

(lambda (x)
  (+ x 1))

That is how you would write an anonymous (i.e. unnamed) function which adds one to its input. You can read this code as “a function of one argument x, which returns the sum x plus one”.

In Scheme you could assign this function to a variable as follows:

(define f (lambda (x)
              (+ x 1)))

Then you could use f like a built-in function:

(f 8)
-> 9

Now consider this more complicated example:

(define f (lambda (x)
            (lambda (y)
              (+ x y))))

This is the simplest non-trivial example using closures. Think about what f does. It’s a function of one argument (x). When you call it, you pass it a single number as an argument, which gets bound to x. The return value from calling the function is another function which takes one argument (lambda (y) ...) This new function always adds x to its input (whichever x was passed when the function was created). Let’s try a couple of examples:

(define adder-8 (f 8))
(define adder-9 (f 9))

This defines adder-8 and adder-9 as functions that add 8 or 9 to their input, respectively. The two functions adder-8 and adder-9 are closures, because they have state. Almost like magic, they remember the values for “x” at the time of their creation, since the variable “x” was in the lexical environment of the code that created them. The two closures never get confused about which is the correct value for “x”; they both have their own copies. A scheme interpreter might represent them something like this:

adder-8
(lambda (y) (+ x y)) x = 8
adder-9
(lambda (y) (+ x y)) x = 9
(adder-8 10)
-> 18
(adder-9 10)
-> 19

If you try to reproduce this behaviour in a language that does not support closures (such as C), you’ll find it’s quite messy.

Closures can do many of the same things as objects. Both are ways of combining code with local state. Here is another example:

(define make-counter (lambda ()
                       (let ((c 0))
                         (lambda ()
                           (set! c (+ c 1))
                           c))))

;;; example usage

(define counter1 (make-counter))
(define counter2 (make-counter))

(counter1)
-> 1

(counter1)
-> 2

(counter1)
-> 3

(counter2)
-> 1

(counter2)
-> 2

(counter1)
-> 4

Each call to make-counter manufactures a counter, represented as a closure. Every time you invoke the closure you get the next value. You can manufacture as many counters as you like, each keeping independent track of its current value. The counter values can only be accessed by their parent closures, so this example shows data hiding as well.

(By the way, there is another use of the term “closure” in computer science, unrelated to the above. That’s the “Kleene closure”, referring to the “*” operator used in regular expressions, Extended Backus-Naur Form, and similar formalisms to specify a match for zero or more occurrences of the preceding expression. For example, the regular expression “be*t” would match the string “bt”, “bet”, “beet”, “beeeeet”, and so on.)

About classes (really about objects)

Unfortunately it’s hard to say exactly what an object is, since the various object-oriented languages, object-oriented databases, and distributed object systems all implement them differently. Over the years I’ve settled on this definition:

An object is any association of a data structure with one or more functions that operate on that data structure.

An object oriented language is any language that has these three attributes:

  1. Supports the creation of objects (as defined above), and the invocation of their associated functions.
  2. Supports some notion of polymorphic variable that can store more than one type of object.
  3. Has a mechanism for selecting functions at runtime based on the current (runtime) type of a polymorphic variable.

So for example, C++ qualifies as an object-oriented language because you can write this:

    #include 
    using namespace std;

    class person
    {
    public:
       virtual char* name () { return "Generic Person"; }
    };

    class teacher : public person
    {
    public:
       virtual char* name () { return "Richard Feynmann"; }
    };

    class doctor : public person
    {
    public:
       virtual char* name () { return "Norman Bethune"; }
    };

    main ()
    {
       person *p = chooseRandomPersonType ();
       cout << p->name () << endl;
    }

C++ achieves attribute 1 through the use of classes with associated member functions. Attribute 2 is achieved through the use of inheritance. In this example, variable "p" can hold pointers to a generic person, teacher, or doctor. Attribute 3 is achieved through the use of virtual functions. In this example, the code that calls function "name" can end up executing one of three different bits of code. That code is selected at runtime based on the type of whatever "p" is pointing to.

There are many other features which are nice to have (data hiding, garbage collection, multiple inheritance, separation of interface from implementation, etc.) but in my view those are not essential to object orientation. Inheritance is not even essential, since there are alternative ways of achieving attribute 2.

Objects and closures are equivalent in the sense that they are both ways of unifying code and state. So which should you use? Fortunately it's rarely necessary to choose. Most programming languages are biased toward one or the other as their standard way of building abstractions. For example C++ has support for objects, but not for closures. Scheme has support for closures but not for objects. So just use the "when in Rome" principle.

About callbacks

Sometimes it's necessary to call a function which goes into an infinite loop, waits for various events and handles them as they occur. Many user interface libraries are organized this way, for example.

In these cases you often want to customize the handling of certain events, while retaining the default behavior for others. Libraries can support this by allowing you to register a handler function for each customized event. When a customized event occurs, the system will call the handler function instead of doing the standard processing. Here is a pseudocode example:

    void handleButtonPress (...)
    {
        ... customized button press handling ...
    }

    main
    {
       ...
       uiCreateButton (x, y, w, h, NULL);                // Default handler
       uiCreateButton (x, y, w, h, &handleButtonPress);  // Customized handler
       ...
       uiStartEventLoop ();
    }

The "handleButtonPress" function is referred to as a "callback", since you're asking the toolkit library to "call you back" whenever that button is pressed.

Callbacks mesh very nicely with objects and closures. For example a library can be designed to accept a closure or an object as a callback, rather than a pointer to a function. If the callback is an object, the toolkit can invoke some agreed-upon method whenever the event of interest occurs.

About continuations

Continuations are an extremely strange notion, popularized in the Scheme programming language but also available in other languages such as Ruby. A continuation is a snapshot of a program's execution state, packaged into an object that can be stored in data structures, passed to functions, etc. A continuation can be invoked like a function, which immediately causes the current execution state to be replaced with the state stored in the contination.

The simplest use of continuations is for exception handling. Here's a Scheme example:

    (call/cc
      (lambda (k)
        (... do some computation ...)
        (if problem occurs, call (k))
        (... do more computation ...)))

The Scheme command "call/cc" (an abbreviation for "call-with-current-continuation") creates a continuation, then invokes the given function (lambda (k) ...), passing it the continuation as an argument.

So the code (lambda (k) ...) starts executing immediately, with the continuation object stored in the variable "k". If "k" is invoked as a function, the computation in progress is aborted and the entire call/cc clause returns immediately.

Because continuations can be stored in data structures, you can use them to implement interesting control abstractions like cooperative multitasking. Continuations are a little bit like process control blocks in an operating system. They are also like the setjmp/longjmp facility in C/C++, except that they remember the entire execution state of the program at the time of their creation, and can resume it later, even if the stack frames have disappeared. That's the part that seems like magic. Consider this example in the C language, using setjmp/longjmp:

    #include 
    #include 
    #include 

    jmp_buf env;

    void mysterious ()
    {
      int x = 3;
      int y = 4;

      if (setjmp (env) != 0)
        {
          printf ("longjmp landed in the middle of the mysterious function!\\n");
          printf ("x is %d, y is %d - corrupted?\\n", x, y);
          exit (1);
        }
    }

    main ()
    {
      mysterious ();
      longjmp (env, 1);
    }

In this example, the mysterious function does a "setjmp", then returns normally. What happens if you try to "longjmp" there later? In C with setjmp/longjmp, that's illegal. You're jumping to a dead stack frame. If you try running this code, you'll probably find that x and y get corrupted after the longjmp.

Here's the exact same code translated into Scheme, using continuations:

    (define env #f)

    (define mysterious
      (lambda ()
        (let ((x 3)
              (y 4))
          (if (not (= 0 (call-with-current-continuation
                         (lambda (k)
                           (set! env k)
                           0))))
              (begin
                (display "longjmp landed in the middle of mysterious function!")
                (newline)
                (display "x is ")
                (display x)
                (display ", y is ")
                (display y)
                (newline)
                (exit))))))

    (mysterious)
    (env 1)

In the Scheme version, the values 3 and 4 are always printed correctly. After the continuation has been saved in the variable "env", it can be called at any time while the program is executing, even after the mysterious function has returned. Whenever the continuation is invoked, you'll be popped right into the middle of the "mysterious" function, executing normally, with all the variables in place.

Setjmp/longjmp do their job by fiddling with the stack pointer, but they don't actually save the stack. Once a subroutine has returned, its local variables are gone. But a continuation actually saves the entire stack, and restores it if necessary.

6 Responses to “Brief introduction to four programming language concepts”

  1. Kalani Thielen Says:

    Nice article, Joe. Good timing too; hopefully we’ll all be talking more about this sort of thing in the coming months.

    What do you think about using the CPS transform to explain continuations? I like that it can be described as a couple of rules (similar to eval) and that knowledge of closures (as you cover initially) carries over directly, explaining the “mysterious” property of continuations that they close over control and data paths (as the data path is encoded in “what gets passed” and the control path is in “what gets called”).

    It also makes the definition of callcc very concise:

    callcc k f = f k k

    I posted an interpreter a while back that optionally displays the CPS transform of input programs before they’re evaluated — http://blog.lab49.com/?p=724 — maybe this can help explain the mystery too.

    There’s also been some interesting work recently in delimited continuations (continuations that terminate before the total program does) and “zippers” the data analog of delimited continuations (which let you create “mutated copies” of complex data structures, sharing as much as possible from the original structure). Oleg Kiselyov has done a lot of interesting work in this area: http://okmij.org/ftp/Computation/Continuations.html

  2. David Barnhill Says:

    Microsoft is adding a lot of functional programming features to C# in .Net 3.0. Support for lambda’s and closures will be there for example. Closures are supported in a more clumsy way in C# 2.0. The C# 3.0 Linq libraries use these features extensively. I’m giving a talk on this at Lab 49 NY on April 18, 2007.

  3. Colin Prepscius Says:

    What’s the difference between a c++ functor and a closure then? i.e….

    struct counter {
    counter() : c(0) { }
    int operator()() { return c++; }
    private:
    int c;
    };

  4. Joe Morrison Says:

    C++ functors and closures play similar roles – both can be used as functions with local state. But in C++ the functor isn’t really the same thing as a function. It just has some syntactic sugar that allows the client to use it the same way. Whereas a closure really is a function. In Scheme there is no difference internally. If the function happens to access nonlocal state, we call it a closure.

    In terms of how you use them, you could say that objects are single chunks of state that can have multiple member functions, whereas closures are single functions that can access multiple chunks of nonlocal state.

  5. choy Says:

    wow, joe great article. now i understand why you were interested in my lament about a lack of closures. you should consider adding “coroutines” to your list of C’s.

    http://en.wikipedia.org/wiki/Coroutine

    closest thing C++ has to closures is the boost lambda library. pretty close though.

    for_each(a.begin(), a.end(), std::cout

  6. Inter-Sections » Blog Archive » Comparing pieces of string - part 1 Says:

    [...] If you talk to computer scientists (the kind who like to study languages as forms of sophisticated imperative expression), you will get some interesting concepts about the ‘power‘ of the programming language (e.g. does it support continuations? closures? recursion? functions as first-order variables? etc.). These discussions tend to be really interesting (if you get the jargon), because the topic of programming language design is a pretty neat pseudo-philosophical one. However, they don’t much help in the pragmatic decision between building your company’s core product in Java, Ruby, or PHP (as an example). [...]