9 Closures

As we just saw, functions in Lua are first-class values. The following example illustrates what that means:

      a = {p = print}      -- 'a.p' refers to the 'print' function
      a.p("Hello World")   --> Hello World
      print = math.sin     -- 'print' now refers to the sine function
      a.p(print(1))        --> 0.8414709848079
      math.sin = a.p       -- 'sin' now refers to the print function
      math.sin(10, 20)     --> 10      20

If functions are values, are there expressions that create functions? Sure. In fact, the usual way to write a function in Lua, such as

      function foo (x)  return 2*x  end

is an instance of what we call syntactic sugar; it is simply a pretty way to write the following code:

      foo = function (x)  return 2*x  end

The expression in the right-hand side of the assignment (function (x) body end) is a function constructor, in the same way that {} is a table constructor. Therefore, a function definition is in fact a statement that creates a value of type "function" and assigns it to a variable.

Note that, in Lua, all functions are anonymous. Like any other value, they do not have names. When we talk about a function name, such as print, we are actually talking about a variable that holds that function. Although we often assign functions to global variables, giving them something like a name, there are several occasions when functions remain anonymous. Let us see some examples.

The table library provides the function table.sort, which receives a table and sorts its elements. Such a function must allow unlimited variations in the sort order: ascending or descending, numeric or alphabetical, tables sorted by a key, and so on. Instead of trying to provide all kinds of options, sort provides a single optional parameter, which is the order function: a function that takes two elements and returns whether the first must come before the second in the sorted list. For instance, suppose we have a table of records like this:

       network = {
         {name = "grauna",  IP = "210.26.30.34"},
         {name = "arraial", IP = "210.26.30.23"},
         {name = "lua",     IP = "210.26.23.12"},
         {name = "derain",  IP = "210.26.23.20"},
       }

If we want to sort the table by the field name, in reverse alphabetical order, we just write this:

      table.sort(network, function (a,b) return (a.name > b.name) end)

See how handy the anonymous function is in this statement.

A function that takes another function as an argument, such as sort, is what we call a higher-order function. Higher-order functions are a powerful programming mechanism, and the use of anonymous functions to create their function arguments is a great source of flexibility. Nevertheless, remember that higher-order functions have no special rights; they are a direct consequence of the fact that Lua handles functions as first-class values.

To further illustrate the use of higher-order functions, we will write a naive implementation of a common higher-order function, the derivative. In an informal definition, the derivative of a function f is the function f’(x) = (f(x + d) - f(x)) / d when d becomes infinitesimally small. According to this definition, we can compute an approximation of the derivative as follows:

      function derivative (f, delta)
        delta = delta or 1e-4
        return function (x)
                 return (f(x + delta) - f(x))/delta
               end
      end

Given a function f, the call derivative(f) returns (an approximation of) its derivative, which is another function:

      c = derivative(math.sin)
      > print(math.cos(5.2), c(5.2))
        -->    0.46851667130038    0.46856084325086
      print(math.cos(10), c(10))
        -->   -0.83907152907645   -0.83904432662041

An obvious consequence of first-class functions is that we can store functions not only in global variables, but also in table fields and in local variables.

We have already seen several examples of functions in table fields: most Lua libraries use this mechanism (e.g., io.read, math.sin). To create such functions in Lua, we only have to put together what we have learned so far:

      Lib = {}
      Lib.foo = function (x,y) return x + y end
      Lib.goo = function (x,y) return x - y end
      
      print(Lib.foo(2, 3), Lib.goo(2, 3))    --> 5    -1

Of course, we can also use constructors:

      Lib = {
        foo = function (x,y) return x + y end,
        goo = function (x,y) return x - y end
      }

Moreover, Lua offers a specific syntax to define such functions:

      Lib = {}
      function Lib.foo (x,y) return x + y end
      function Lib.goo (x,y) return x - y end

As we will see in Chapter 21, Object-Oriented Programming, the use of functions in table fields is a key ingredient for object-oriented programming in Lua.

When we store a function into a local variable, we get a local function, that is, a function that is restricted to a given scope. Such definitions are particularly useful for packages: because Lua handles each chunk as a function, a chunk can declare local functions, which are visible only inside the chunk. Lexical scoping ensures that other functions in the chunk can use these local functions.

Lua supports such uses of local functions with a syntactic sugar for them:

      local function f (params)
        body
      end

A subtle point arises in the definition of recursive local functions, because the naive approach does not work here. Consider the next definition:

      local fact = function (n)
        if n == 0 then return 1
        else return n*fact(n-1)   -- buggy
        end
      end

When Lua compiles the call fact(n - 1) in the function body, the local fact is not yet defined. Therefore, this expression will try to call a global fact, not the local one. We can solve this problem by first defining the local variable and then the function:

      local fact
      fact = function (n)
        if n == 0 then return 1
        else return n*fact(n-1)
        end
      end

Now the fact inside the function refers to the local variable. Its value when the function is defined does not matter; by the time the function executes, fact already has the right value.

When Lua expands its syntactic sugar for local functions, it does not use the naive definition. Instead, a definition like

      local function foo (params)  body  end

expands to

      local foo; foo = function (params)  body  end

Therefore, we can use this syntax for recursive functions without worrying.

Of course, this trick does not work if we have indirect recursive functions. In such cases, we must use the equivalent of an explicit forward declaration:

      local f      -- "forward" declaration
      
      local function g ()
        some code  f()  some code
      end
      
      function f ()
        some code  g()  some code
      end

Beware not to write local in the last definition. Otherwise, Lua would create a fresh local variable f, leaving the original f (the one that g is bound to) undefined.

When we write a function enclosed in another function, it has full access to local variables from the enclosing function; we call this feature lexical scoping. Although this visibility rule may sound obvious, it is not. Lexical scoping plus nested first-class functions give great power to a programming language, but many do not support the combination.

Let us start with a simple example. Suppose we have a list of student names and a table that maps names to grades; we want to sort the list of names according to their grades, with higher grades first. We can do this task as follows:

      names = {"Peter", "Paul", "Mary"}
      grades = {Mary = 10, Paul = 7, Peter = 8}
      table.sort(names, function (n1, n2)
        return grades[n1] > grades[n2]        -- compare the grades
      end)

Now, suppose we want to create a function to do this task:

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

The interesting point in this last example is that the anonymous function given to sort accesses grades, which is a parameter to the enclosing function sortbygrade. Inside this anonymous function, grades is neither a global variable nor a local variable, but what we call a non-local variable. (For historical reasons, non-local variables are also called upvalues in Lua.)

Why is this point so interesting? Because functions, being first-class values, can escape the original scope of their variables. Consider the following code:

      function newCounter ()
        local count = 0
        return function ()      -- anonymous function
                 count = count + 1
                 return count
               end
      end
      
      c1 = newCounter()
      print(c1())  --> 1
      print(c1())  --> 2

In this code, the anonymous function refers to a non-local variable (count) to keep its counter. However, by the time we call the anonymous function, the variable count seems to be out of scope, because the function that created this variable (newCounter) has already returned. Nevertheless, Lua handles this situation correctly, using the concept of closure. Simply put, a closure is a function plus all it needs to access non-local variables correctly. If we call newCounter again, it will create a new local variable count and a new closure, acting over this new variable:

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

So, c1 and c2 are different closures. Both are built over the same function, but each acts upon an independent instantiation of the local variable count.

Technically speaking, what is a value in Lua is the closure, not the function. The function itself is a kind of a prototype for closures. Nevertheless, we will continue to use the term “function” to refer to a closure whenever there is no possibility for confusion.

Closures provide a valuable tool in many contexts. As we have seen, they are useful as arguments to higher-order functions such as sort. Closures are valuable for functions that build other functions too, like our newCounter example or the derivative example; this mechanism allows Lua programs to incorporate sophisticated programming techniques from the functional world. Closures are useful for callback functions, too. A typical example here occurs when we create buttons in a conventional GUI toolkit. Each button has a callback function to be called when the user presses the button; we want different buttons to do slightly different things when pressed.

For instance, a digital calculator needs ten similar buttons, one for each digit. We can create each of them with a function like this:

      function digitButton (digit)
        return Button{ label = tostring(digit),
                       action = function ()
                                  add_to_display(digit)
                                end
                     }
      end

In this example, we pretend that Button is a toolkit function that creates new buttons; label is the button label; and action is the callback function to be called when the button is pressed. The callback can be called a long time after digitButton did its task, but it can still access the digit variable.

Closures are valuable also in a quite different context. Because functions are stored in regular variables, we can easily redefine functions in Lua, even predefined functions. This facility is one of the reasons why Lua is so flexible. Frequently, when we redefine a function, we need the original function in the new implementation. As an example, suppose we want to redefine the function sin to operate in degrees instead of radians. This new function converts its argument and then calls the original function sin to do the real work. Our code could look like this:

      local oldSin = math.sin
      math.sin = function (x)
        return oldSin(x * (math.pi / 180))
      end

A slightly cleaner way to do this redefinition is as follows:

      do
        local oldSin = math.sin
        local k = math.pi / 180
        math.sin = function (x)
          return oldSin(x * k)
        end
      end

This code uses a do block to limit the scope of the local variable oldSin; following conventional visibility rules, the variable is only visible inside the block. So, the only way to access it is through the new function.

We can use this same technique to create secure environments, also called sandboxes. Secure environments are essential when running untrusted code, such as code received through the Internet by a server. For instance, to restrict the files that a program can access, we can redefine io.open using closures:

      do
        local oldOpen = io.open
        local access_OK = function (filename, mode)
          check access
        end
        io.open = function (filename, mode)
          if access_OK(filename, mode) then
            return oldOpen(filename, mode)
          else
            return nil, "access denied"
          end
        end
      end

What makes this example nice is that, after this redefinition, there is no way for the program to call the unrestricted version of function io.open except through the new, restricted version. It keeps the insecure version as a private variable in a closure, inaccessible from the outside. With this technique, we can build Lua sandboxes in Lua itself, with the usual benefits: simplicity and flexibility. Instead of a one-size-fits-all solution, Lua offers us a meta-mechanism, so that we can tailor our environment for our specific security needs. (Real sandboxes do more than protecting external files. We will return to this subject in the section called “Sandboxing”.)

To give a more concrete example of functional programming, in this section we will develop a simple system for geometric regions.^[11] The goal is to develop a system to represent geometric regions, where a region is a set of points. We want to be able to represent all kinds of shapes and to combine and modify shapes in several ways (rotation, translation, union, etc.).

To implement this system, we could start looking for good data structures to represent shapes; we could try an object-oriented approach and develop some hierarchy of shapes. Or we can work on a higher level of abstraction and represent our sets directly by their characteristic (or indicator) function. (The characteristic function of a set A is a function f_A such that f_A(x) is true if and only if x belongs to A.) Given that a geometric region is a set of points, we can represent a region by its characteristic function; that is, we represent a region by a function that, given a point, returns true if and only if the point belongs to the region.

As an example, the next function represents a disk (a circular region) with center (1.0, 3.0) and radius 4.5:

      function disk1 (x, y)
        return (x - 1.0)^2 + (y - 3.0)^2 <= 4.5^2
      end

With higher-order functions and lexical scoping, it is easy to define a disk factory, which creates disks with given centers and radius:

      function disk (cx, cy, r)
        return function (x, y)
                 return (x - cx)^2 + (y - cy)^2 <= r^2
               end
      end

A call like disk(1.0, 3.0, 4.5) will create a disk equal to disk1.

The next function creates axis-aligned rectangles, given the bounds:

      function rect (left, right, bottom, up)
        return function (x, y)
                 return left <= x and x <= right and
                        bottom <= x and x <= up
               end
      end

In a similar fashion, we can define functions to create other basic shapes, such as triangles and non–axis-aligned rectangles. Each shape has a completely independent implementation, needing only a correct characteristic function.

Now let us see how to modify and combine regions. To create the complement of any region is trivial:

      function complement (r)
        return function (x, y)
                 return not r(x, y)
               end
      end

Union, intersection, and difference are equally simple, as we show in Figure 9.1, “Union, intersection, and difference of regions”.

      function union (r1, r2)
        return function (x, y)
                 return r1(x, y) or r2(x, y)
               end
      end
      
      function intersection (r1, r2)
        return function (x, y)
                 return r1(x, y) and r2(x, y)
               end
      end
      
      function difference (r1, r2)
        return function (x, y)
                 return r1(x, y) and not r2(x, y)
               end
      end

The following function translates a region by a given delta:

      function translate (r, dx, dy)
        return function (x, y)
                 return r(x - dx, y - dy)
               end
      end

To visualize a region, we can traverse the viewport testing each pixel; pixels in the region are painted black, pixels outside it are painted white. To illustrate this process in a simple way, we will write a function to generate a PBM (portable bitmap) file with the drawing of a given region.

PBM files have a quite simple structure. (This structure is also highly inefficient, but our emphasis here is simplicity.) In its text-mode variant, it starts with a one-line header with the string "P1"; then there is one line with the width and height of the drawing, in pixels. Finally, there is a sequence of digits, one for each image pixel (1 for black, 0 for white), separated by optional spaces and end of lines. The function plot in Figure 9.2, “Drawing a region in a PBM file” creates a PBM file for a given region, mapping a virtual drawing area (-1,1], [-1,1) to the viewport area [1,M], [1,N].

      function plot (r, M, N)
        io.write("P1\n", M, " ", N, "\n")     -- header
        for i = 1, N do                -- for each line
          local y = (N - i*2)/N
          for j = 1, M do            -- for each column
            local x = (j*2 - M)/M
            io.write(r(x, y) and "1" or "0")
          end
          io.write("\n")
        end
      end

To complete our example, the following command draws a waxing crescent moon (as seen from the Southern Hemisphere):

      c1 = disk(0, 0, 1)
      plot(difference(c1, translate(c1, 0.3, 0)), 500, 500)