Reading On Lisp: Then and Now

> Learning Lisp requires real, significant use of the language. Eventually you begin to think in the language and that's when profiency begins.

This applies to any programming language. It's just more pronounced when switching paradigms. When I was learning python I would write python like it was C. The programs work, but it's not a very good way to write python. Even now when I write something quick in any language it ends up being very C-like since that's the language I use the most.

"People find it easier to grasp an instance of a pattern or abstraction they already know, than to grasp a new abstraction altogether."

But the idea is to build the program up until you are working in a set of target abstractions that fit well with the problem domain. If I don't know the problem domain (or have materials to help me understand it), I have no business writing a program for it.

You are always looking for a high level of cohesion and a low level of coupling. If you already have a natural language that experts talk about the problem in, it is likely that the set of terminology derived from it has these properties. (It is well specified, it is precise, work has been done in it). A trivial example might be the difference between doing statistical work in C vs. statistical work in R. R is pretty clearly better for it.

Modifying something that has a lot of dependencies is only hazardous if what that particular something does is underspecified. If it is a bug in one use of that operator, it should be a bug in every use of that operator. If it isn't, perhaps the operator has special cases, or perhaps you really want two different operators (in either case, it needs greater specification).

YMMV, but in my opinion, one should not be modifying a program that one does not understand (at least mostly). It is easier to modify the 'non bottom up' program without understanding the whole, because generally, you do not have a chance at understanding the whole (not really 'whole', more like 'significant chunk'). You have no other option but to try something and see if it works. It also seems that you would frequently 'miss' changes that need to be propagated throughout the code-base (things that are actually bugs in other places, but perhaps are not manifesting).

In Python (yes, the heresy of using Python in a lisp article), you can define a closure this way:

    def foo(x):
        y = x
        def bar():
            print y
        return bar

    >>> z = foo(1)
    >>> z()
    1

The value of y is preserved, even through it is not assigned in the function bar (outside of its lexical scope). You can pass bar around all you want, and it will maintain its value of y. Even if you create another instance of bar, they will retain their individual values of y.

So say I have a first-order language (where functions are not values). You can write:

    def foo(x): return x + 1

But not:

    def bar(baz, x): return baz(x+1)

That is to say, you pass integers around ('x' above) as values, but not functions. In a minimal higher order language, like C, you can pass functions around like values. Ie: baz could be a pointer to a function in the second line above, which is called by bar.

Now, what happens when you have nested functions?

    def foo():
        def bar(y):
            return y + 1
        return bar

You can't do this in C, but conceptually that's not much different than just defining foo and bar as two separate top-level functions.

But what happens when the inner function refers to a local variable of the outer function?

    def foo():
        x = 1
        def bar(y):
            return x + 1
        return bar

How does 'bar' know what 'x' is? You might ask, why would you want to do this? Well, say you have a function map(fun, list). Map takes a function and a list. It returns a list, each element of which is the value yielded by calling fun with an element in list. Eg:

    def foo(x): return x + 1
    map(foo, [1, 2, 3]) # -> [2, 3, 4]

Map can be defined as:

    def map(fun, list):
        result = []
        foreach item in list:
            result.append(fun(item))

So back to the example, you might want to write something like:

    def foo(list):
        x = some_calculation()
        def bar(y): return x + y
        return map(bar, list)

In other words, the function that you pass to map needs to know not just the current element of the list, but some other information that is held in a local variable in the parent function. This case is very common when using map as replacement for "for" loops (note how in a loop you can refer to the local variables of your function inside the body of the loop).

Now technically the name of the language feature that lets you capture the value of local variables in child functions is "lexically scoped lambda" or something along those lines. A closure is just the most common way to implement the language feature, but people often just use "closure" to refer to the language feature itself.

In a compiler that uses closures, the example above would be translated into code something like:

    class _closure_bar: 
        this.x = Nil

       def _closure_bar(x):
           this.x = x           

       def operator() (y):
           return this.x + y

    def foo(list):
        x = some_calculation()
        bar = new _closure_bar(x)
        return map(bar, list)
    

Instead of passing around a function as a function pointer like in C, you pass around a callable object whose members are the local variables of the parent function captured by the inner function, and which when called executes the body of the inner function.

Now, there is some additional complexity which occurs when an inner function modified the value of a local variable of an outer function. Languages like Python just disallow such modification, which is why people complain about Python not having "full lambdas". Languages like Common Lisp and Scheme add another indirection for local variables that are captured + assigned-to in an inner function.

Here's yet another stab at explaining closures using C. Hopefully this is clear.

The confusion about closures happens because it doesn't exist in other languages. (There isn't a way to express it.)

Let's look at a simple C function that uses a global variable:

  int a = 1;

  int a_plus_2() {
    return 2 + a;
  }

This always returns 2 more than "a". Initially it will return 3. If "a" is set to 5 at some point in the future, "a_plus_2" will then return 7. Simple. No closure here.

In Lisp, "a" would be called a "dynamic variable" because it changing its value affects all code that uses "a" over time, including usage within other scopes; "a" has a dynamic binding. But Lisp also has static binding which means the value of the variable is captured each time a scope is created and remains static over time within that scope.

Imagine a variation of C where variable make this distinction explicit by prefixing with with <dynamic> and <static>. <dynamic> would be the default and in fact is how the real C behaves. <static> now means Lisp notion of static binding (forget C's notion of static, which is totally different). Let's use it.

  <static> int b = 1;
  
  int b_plus_2() {
    return 2 + b;
  }

So here "b" is marked as static. When "b_plus_2" is defined at compile time, the current value of "b" is captured - statically bound - to its current value of 1. So "b_plus_2" will always return 3 _even if the global variable "b" is later modified.

  b = 5; /* modifying b */
  
  int new_b_plus_2 {
    return 2 + b;
  }

Calling "new_b_plus_2" return 7. No surprise here. The twist is that the original "b_plus_2" still returns 3. The value of "b" is captured in a closure. Each new scope encloses the current value of "b", binding its current value statically (unchanging) within that scope. Closures become interesting when the block in question is a function body.

So, yeah - it's a simple concept in the end. It's tricky because it doesn't exist many other languages. It provides a way to encapsulate state analogous to an object in OO languages [1].

The concept is more useful in Lisp with its higher order functions - functions that define other functions. This is very fluid in Lisp, while Python uses its lambda form for anonymous functions, Ruby has blocks and lambdas and...[2], and Java gets close with inner classes.

I hope this helps.

[1] "Objects are a poor man's closure" and "Closures are a poor man's object" http://stackoverflow.com/questions/2497801/closures-are-poor...

[2] I'm don't do Ruby - but's here's a ton of stuff on closures in Ruby: http://innig.net/software/ruby/closures-in-ruby.rb

JavaScript is a pretty good language to illustrate closures, if you use functions and declare all of your variables at the beginning of each function. :)

In the demo below, the closure we're interested in is the combination of the code inside "munger scope", and the environment it resides in. To do its job, munger must search its lexical environment to find each variable. The lexical environment is illustrated by the boxes. Searching for "foo", it must first check munger scope (local), beta scope, alpha scope, and then finally succeeds with the global scope.

In the code at the bottom, the demo1 and demo2 invocations don't influence each other. That combination of code+environment providing independent values is a closure.

   |-- Global Scope ----------------------------------------------------------------|
   |                                                                                |
   |  var foo = "QUX";                                                              |
   |  var alpha = function () {                                                     |
   |                                                                                |
   |     |-- alpha scope ----------------------------------------------------|      |
   |     |                                                                   |      |
   |     |   var a = "AA";                                                   |      |
   |     |   var beta = function () {                                        |      |
   |     |                                                                   |      |
   |     |      |-- beta scope ---------------------------------------|      |      |
   |     |      |                                                     |      |      |
   |     |      |   var b = "BB";                                     |      |      |
   |     |      |   var munger = function () {                        |      |      |
   |     |      |                                                     |      |      |
   |     |      |      |-- munger scope -----------------------|      |      |      |
   |     |      |      |                                       |      |      |      |
   |     |      |      |    a = a + a;                         |      |      |      |
   |     |      |      |    b = b + b;                         |      |      |      |
   |     |      |      |    return a + " " + b + " " + foo;    |      |      |      |
   |     |      |      |                                       |      |      |      |
   |     |      |      |---------------------------------------|      |      |      |
   |     |      |                                                     |      |      |
   |     |      |   }                                                 |      |      |
   |     |      |                                                     |      |      |
   |     |      |   return munger;                                    |      |      |
   |     |      |                                                     |      |      |
   |     |      |-----------------------------------------------------|      |      |
   |     |                                                                   |      |
   |     |   }                                                               |      |
   |     |                                                                   |      |
   |     |  return beta();                                                   |      |
   |     |                                                                   |      |
   |     |-------------------------------------------------------------------|      |
   |                                                                                |
   |  }                                                                             |
   |                                                                                |
   |  js> var demo1 = alpha();                                                      |
   |  js> var demo2 = alpha();                                                      |
   |  js> demo1()                                                                   |
   |  "AAAA BBBB QUX"                                                               |
   |  js> demo1()                                                                   |
   |  "AAAAAAAA BBBBBBBB QUX"                                                       |
   |  js> demo2()                                                                   |
   |  "AAAA BBBB QUX"                                                               |
   |  js> demo1()                                                                   |
   |  "AAAAAAAAAAAAAAAA BBBBBBBBBBBBBBBB QUX"                                       |
   |                                                                                |
   ----------------------------------------------------------------------------------