The Department of Practical Computation

Languages: Lua
Level: Advanced

Some of you are groaning at the title. My hope is that, by the end of this essay, I will have you all groaning. }:->

A closure is a tricky idea, and I often find myself looking it up to get a grasp on exactly what it is. Wikipedia says that a closure is "...a function that is evaluated in an environment containing one or more bound variables." That's a good, simple definition, but it doesn't explain very well what's going on. To show you closures, I'm going to use Lua again. Lua's simple syntax and first-class anonymous functions make it an ideal language for describing closures. If you don't know Lua or don't have it handy, you will probably still be able to follow along.

Let's start with a simple example of a closure that returns a series of ever-increasing integers:

function f()
    local x = 0
    return function()
               x = x + 1
               return x
           end
end

g = f()

The function f returns a function that we call multiple times to get our series of integers. Now it would seem to the naïve programmer that x will have gone out of scope after f returns, which will cause a runtime error. But lo, and behold:

> =g()
1
> =g()
2
> =g()
3

(=g() is Lua for "print the value of g().")

Our phantom variable x is alive and well! What happened here? Well, to start off with, we must understand scope.

Each block in Lua has a symbol table that holds local variables. A block is something that begins with function, if, while and friends, and ends with end. When a variable is referenced in a block, Lua first looks for the variable in the current block. If it can't find it there, it looks in the block enclosing the current block. It keeps going in this way all the way up to global scope. The scope of a variable, then, is the extent to which it can be "seen."

Next, we must understand the idea of bound variables. When a variable is referenced, the current scope is searched for a variable with that name. If it is found, the variable is bound in that expression. A variable that is not bound is called a free variable. For example:

a = 3
function f(b)
    return a + b + c
end

In this function f, variables a and b are bound to a in global scope and the argument b to the function. Variable c, however, is free because no variable with that name exists when the function is defined. When f is run, it will look for c in the global scope and bind that value to the variable, or else fail. You can think of a free variable as a variable that is "to be announced."

(Aside: In Lua, variables that are not defined have the special value nil. The above code will error when c is not defined because it will attempt addition with a nil value, but if we were simply doing return c, it would not. Keep in mind that Lua is special in this way, and other languages like Javascript or Python will produce an error whenever free variables cannot be bound.)

In our closure, then, the secret is that the x defined in f() is bound to x inside the anonymous function, and thus continues to exist after f() returns. This anonymous function carries around its bound variable x, and voila! A closure.

So what are closures good for? Well, one of the fun things about Lua is that you can give for a function that returns an anonymous function, typically a closure, and for will call that anonymous function once per loop until it returns nil. This kind of function is called an iterator in Lua (though it is more correctly called a generator — the anonymous function that for calls is the proper iterator). Suppose we want to iterate over a sin wave from one point to another. We could write this:

for i = 0, math.pi*2, 0.1 do
    x = math.sin(i)
    -- Do something with x
done

But it's not exactly clear from the loop definition what's going on. With an iterator, we can make this loop look a bit more self explanatory.

function sin_seq(from, to, step)
    local x = from - step
    return function()
        x = x + step
        if x < to then
            return math.sin(x)
        else
            return nil
        end
    end
end

for x in sin_seq(0, math.pi*2, 0.1) do
    -- Do something with x
end

Yes, the definition of sin_seq is a bit long and complicated, but it's much clearer what's going on in your loop, which is important when you look over your code six months down the road.

And that is what closures are all about. Commence groaning. :)

Languages: Lisp, Lua
Level: Moderate

Lua is a language that at first looks like a wimpy version of Python mixed with shell script. It doesn't come with a large library of helper modules, and it doesn't even have ++ or += operators. It's used most often as an embedded scripting language in places like the ION window manager and World of Warcraft. Most people might pass it over as insignificant, but little Lua is a lot more powerful than it looks.

For starters, Lua has first-class functions. This is a fun CS way of saying that functions exist as values that can be passed around in variables. Going a step further, it has anonymous functions, which means you don't even have to give the functions names before you start throwing them around. Well, technically, they may have names at some point, but they are not like C functions, which are very static and can only exist in one place (unless you want to count function pointers, and I honestly don't). In CS, we call those functions-without-a-name "lambda functions," and in fact they are called just that in Lisp and Python.

To illustrate, here is a function foo which takes a value x and returns an anonymous function that prints a value three more than x.

function foo(x)
  return function() print(x + 3) end
end

f = foo(5)
f()     -- prints "8"
g = foo(10)
g()     -- prints "13"

This code also illustrates the idea of a closure, which is another fun CS idea that I will surely talk about at length in another post.

The second major feature of Lua is the table. A table is a term for a data structure that acts like an array, an associative array (or hashtable), or an object depending on how you look at it. Just like in Lisp, everything in Lua is a list, except that it is even more useful. Tables are the only data structure in Lua — Everything else, from trees to libraries, are all made of tables. An item in a table can be accessed in one of two ways:

t = {}                           -- create a new table
t["a"] = 3                       -- Fill it with a few values
t["b"] = 4
t["c"] = 7
print(t["a"], t["b"], t["c"])    -- array/hashtable style
print(t.a, t.b, t.c)             -- object style
-- output is "3       4       7" for both styles

This dual-syntax gives us a powerful indirection facility. As a trivial example, suppose I have an object representing a series of values for each day of the week, and I want to look up the value for a particular day input by the user.

values = {}
values.Monday = 72
values.Tuesday = 17
values.Wednesday = 90
values.Thursday = 24
values.Friday = 55
values.Saturday = 12
values.Sunday = 42

day = io.read()
print(values[day])

Since I don't know ahead of time what the day is, I can't simply write values.Friday. What I have to do is look up a value by the string given to me, and that's exactly what the [] syntax does.

Now there's another fun feature of Lua that allows some shifty shenanigans to go on. If a function is given only a single literal string or table, parentheses around the arguments may be omitted. To illustrate:

print "Hello, World"       -- equivalent to print("Hello, World")
munge {1,2,3}              -- equivalent to munge({1,2,3})

And as a shortcut for initializing tables, we can put the keys in as well as the values:

t = {a=3, b=4, c=7}  -- equivalent to our first table example

Which, when put together, allows us to make visually nice function calls that can be arbitrarily complex:

post = create_new_post {title="foo", user="chip",
    text=blogtext, refs={341, 207, 199}
}

But the real fun comes in when we combine all of this with our lambda functions. See if you can follow what's happening with this next bit.

function is_a(thing)
  return function(obj)
    return obj.type == thing
  end
end

-- create a few "objects"
foo = {type="point", x=30, y=40}
bar = {type="definition", word="battery", definition="..."}
baz = {type="url", protocol="http", domain="google.com", path="/"}

is_a_url = is_a("url")  -- create a specialized checking function for URLs

print(is_a_url(foo))    --> false
print(is_a_url(bar))    --> false
print(is_a_url(baz))    --> true

The function is_a is a factory which creates specialized functions to determine whether something is of a certain type. So if we're only interested in URLs, we can quickly determine which of our objects are URLs by creating is_a_url from is_a("url"). We could have just made is_a take two arguments, one for the object and one for the type, but our generated function is slightly faster because it removes the need to pass in the type every time. Of course, this is still a level away from Lisp, which can do these kinds of function generating shenanigans at compile time.

I leave you with this gratuitous abuse of lambdas and tables I like to call "How To Fake a Case Statement... Poorly."

function foo(x)
  ({
    a = function()
          print "A IS SUPERIOR"
        end,
    b = function()
          print "B IS BETTER"
        end
  })[x]()
end