Thinking about Sudoku and Scheme, Part 2

Here is how I implemented some of my array primitives. I'll start in the middle:

(define map-board-row-elts
  (array2D-make-row-elt-mapper board-x-dim))

When treating a vector like a two-dimensional array, assuming that you store them row-first, the key piece of information you need is the size of the row. (More generally, for an n-dimensional array, to access an element you need to know the size of dimensions 1 to n - 1). On the top side of my program, the dimensions of my Sudoku board are known. The array primitives don't know. Rather than pass this information to every array access call, I create a function. The function array2D-make-row-elt-mapper captures this information using closure and returns another function:

(define array2D-make-row-elt-mapper
  (lambda (x-dim)
    (lambda (array2D y-idx elt-handler)
      (array2D-map-row-elts
       array2D y-idx x-dim elt-handler))))

Note the nested lambda expressions. The top one receives the x-dim parameter, and the body of this function is another lambda expression. This second lambda expression is the return value of this function: it returns a function. This returned function invokes another function which requires an x-dim parameter.

In this case, the purpose of returning this function is to provide the functionality of another function, array2D-map-row-elts, but without the need to provide an x-dim parameter. The new function is a curried function.

What is a curried function? Currying means taking a function with n parameters and creating a new function with n - 1 parameters. The new function provides a default value for the missing parameter, giving you a simplified API to the original function.

Common Lisp and other languages provide curry and rcurry functions which peel off parameters from the left or right of the paramter list, respectively. So our currying may not meet a strict definition, although we are doing the same thing: providing an interface function that will supply a value for one of the original parameters. Currying often uses a constant for these default parameters; in our case, we're using a variable, but the idea is similar. Scheme does not have a standard curry function, but it is easy enough to express currying by using nested lambda expressions.

In my case, x-dim is the curried parameter. Inside this lambda expression is a reference to x-dim. Scheme supports lexical closure; at the time this lambda expression is evaluated, the result is a function object that "closes over" or "captures" -- that is, retains a reference to -- the variable binding in effect when the lambda expression is evaluated.

This is the variable binding owned by the caller, the variable bound to the name board-x-dim. It is not a copy: if some other piece of code updates the value in that variable, this function would see a different value for x-dim when it executes. This creates complex state with multiple possible "listeners" for the state change: this is one of the reasons that Scheme programmers tend to prefer a functional style where variables are not altered after initial binding.

If you are a C programmer, you may find this very confusing. You can think of it as if the returned function retains a pointer to the board-x-dim sent by the caller. The C runtime model is quite different, though: it has distinct lifetimes for variables; local non-static ("automatic") variables that exist on the stack may be recycled when a given function returns, so it is unsafe to retain pointers to them (in fact, retaining a pointer to an automatic variable is a common beginner's bug in C).

In Scheme, bindings exist as long as there are references to them; when there are no more references to them, they may be garbage-collected (or not).

Let's look at the definition of the next function we call, array2D-map-row-elts:

((define array2D-map-row-elts
  (lambda (array2D y-idx x-dim elt-handler)
    (array2D-map-subrow-elts
     array2D
     0 (- x-dim 1)
     y-idx
     x-dim
     elt-handler)))

OK, we call yet another function: array2D-map-subrow-elts, which is more general (it will map any contiguous subset of the array elements). It is the general case, and array2D-map-row-elts is the more specific case (it maps the whole row), which means we can quite naturally define this specific case by parameterizing the general case. It isn't quite the same as currying, but it is a similar idea; we provide some fixed parameters representing the start of the row (index 0) and end (index x-dim - 1). Here is the general function:

(define array2D-map-subrow-elts
  (lambda (array2D
           x-first-idx x-last-idx
           y-idx
           x-dim
           elt-handler)
    (letrec ((iter-x
              (lambda (x-idx y-idx)
                (elt-handler
                 (array2D-get array2D x-idx y-idx x-dim))
                (if (< x-idx x-last-idx)
                    (iter-x (+ x-idx 1) y-idx)))))
      (iter-x x-first-idx y-idx))))

Are we there yet?

This function receives all the parameters and walks through the array, starting with an arbitrary x-idx (in this case, zero), and proceeding until we have processed the last legal x index (in this case, x-idx - 1).

Note that instead of iteration to walk the array, I use recursion. I won't go into a full explanation of recursion here; suffice it to say that although many people feel that recursion is unnatural and does not reflect how they think about iteration in the "real world," after expressing algorithms recursively for a while, it starts to seem much more natural, and the proposition that recursion and iteration can be transformed into each other does not seem so strange.

This function is formulated using tail recursion, where the bindings are not referenced after the recursive function call. In C or Pascal, the compilers are generally not smart about this sort of thing, and recursing on a large array could result in a very deep set of stack frames. A language like Scheme is able to recognize that since the values that exist in previous function calls are not used, it is free to lose track of the previous values, so no deep stack is actually required. Since this is the case, the decision to use recursion was largely arbitrary. I chose it because I wanted to practice writing recursive functions.

The letrec may be unfamiliar. If the innermost function was not recursive, we could just call it like this, without ever binding the function to a name at all:

((lambda (x-idx y-idx)
   ... )
0 y-idx)

In this case the innermost function is never bound to a name, because nothing has to refer to it by name. The expression around it would simply call it. This is also known as applying parameters to the anonymous function object.

You might think that we could just do this with let. The semantics of let allow the call from outside the function, but the binding to the name iter-x would exist only within the body of the let expression. This body consists of the expression or expressions that occur after the binding list in the let expression. Since the definition of the function occurs as part of the binding list, not part of the body of the let expression, let will not work; letrec is designed specifically to allow definition of recursive or mutually recursive functions within the binding list.

So now are we there yet?

Almost. My final comment on this function concerns the use of the elt-handler parameter. The generated function allows the caller to pass in a handler function. Applying functions to functions is known as higher-order programming; support for higher-order programming is one of the essential features of Lisp and Scheme.

It might seem like this is much too complicated. Functions generating functions calling functions calling functions? Well, yes, this is a bit of overkill to access an array; normally we would use some standard functions for handling data structures. But the general style: creating a lot of small functions -- appears very commonly in Scheme programs, and now you have had a taste of how a typical data structure library might be implemented.

I don't claim to be very experienced with Scheme yet, but I am happy to have gotten to the point where writing functions like array2D-make-row-elt-mapper and its supporting functions comes rapidly and naturally. Reading examples helps, but the lessons don't really click until you tackle a programming problem, and feel your mind begin to undergo rewiring. The level of abstraction, and thus the leverage you can gain from Scheme, become much higher than this, so stay tuned.