Friday, February 23, 2007

Closure

I've been doing the chapters of Programming in Lua, and I have arrived at chapter 6, "More about functions". Here the concept of closure is introduced and I'm having a hard time grasping the concept.

Here's an example:
-- sortbygrade.lua
names = {"Peter", "Paul", "Mary"}
grades = {Mary = 10, Paul = 7, Peter = 8}

print "-- unordered --"
for i,v in ipairs(names) do print(names[i], grades[v]) end
print "---------------"

table.sort(names, function (n1, n2)
    return grades[n1] > grades[n2]  -- compare the grades
end)

print "--- ordered ---"
for i,v in ipairs(names) do print(names[i], grades[v]) end
print "---------------"


-- function to do the same
function sortbygrade (names, grades)
    table.sort(names, function (n1, n2)
        return grades[n1] > grades[n2]  -- compare the grades
    end)
end

names = {"Peter", "Paul", "Mary"}   -- restore unordered state
sortbygrade(names, grades)          -- order by function

print "--- ordered ---"
print "- w/ function -"
for i,v in ipairs(names) do print(names[i], grades[v]) end
print "---------------"

This was some code I created, based on chapter 6.1. Here is the output, using the standalone version of Lua:

-- unordered --
Peter 8
Paul 7
Mary 10
---------------
--- ordered ---
Mary 10
Peter 8
Paul 7
---------------
--- ordered ---
- w/ function -
Mary 10
Peter 8
Paul 7
---------------

The order function has two parameters, a table and a function.

In Lua a function is an anonymous value, which can be assigned to a variable.

function foo (argument) end

is simply syntactic sugar for

foo = function (argument) end

This means you can use an anonymous function as the second parameter of the order function. This anonymous function should have two arguments, which are both an index for the table, and return a value that indicates which of the two table elements referred to by these indexes should go first.

In the code example, this piece of code is interesting:

function sortbygrade (names, grades)
    table.sort(names, function (n1, n2)
        return grades[n1] > grades[n2] -- compare the grades
    end)
end

The variable grades inside the anonymous function is neither local, nor global. It can be called an "external local variable", or--in Lua jargon--an upvalue.

Now I'm quoting from the text of chapter 6.1 of Programming in Lua:

Consider the following code:

function newCounter ()
    local i = 0
    return function () -- anonymous function
        i = i + 1
        return i
    end
end

c1 = newCounter()
print(c1()) --> 1
print(c1()) --> 2

Now, the anonymous function uses an upvalue, i, to keep its counter. However, by the time we call the anonymous function, i is already out of scope, because the function that created that variable (newCounter) has returned. Nevertheless, Lua handles that situation correctly, using the concept of closure. Simply put, a closure is a function plus all it needs to access its upvalues correctly. If we call newCounter again, it will create a new local variable i, so we will get a new closure, acting over that new variable:

c2 = newCounter()
print(c2()) --> 1
print(c1()) --> 3
print(c2()) --> 2

So, c1 and c2 are different closures over the same function and each acts upon an independent instantiation of the local variable i. Technically speaking, what is a value in Lua is the closure, not the function. The function itself is just a prototype for closures. Nevertheless, we will continue to use the term "function" to refer to a closure whenever there is no possibility of confusion.

So if I understand correctly, we should be talking about closures being assigned to a variable when we run code that defines a function. The code that defines the function is merely a prototype; we never see the actual closure expressed as code text, because it only exists at runtime.

Now that was hard for me to get my head around, and I still have to get used to thinking in closures, and having several instances of the same function, which are all different function values (sorry, closures). My brain hurts.

I guess I have to do some reading on the subject in Wikipedia before I continue in Programming in Lua. The subject is just too important to skip because it is so hard to understand. I was accustomed to and feeling comfortable with procedural programming, so functional programming seems to be a bit weird for me right now.

No comments: