Jim Newton Blog

SKILL for the Skilled: Many Ways to Sum a List (Part 8): Closures -- Functions with State

Team SKILL — Tue, 23 Apr 2013 13:21:00 GMT

In the past several postings to this blog, we've looked at various ways to sum a given list of numbers. In this posting I'll present yet another way to do this. This time the technique will be markedly different than the previous ways, and will take advantage of a powerful feature of SKILL++, namely lexical closures. These closures will be used to implement data encapsulation, and we'll also use lexical closures to capture computation state and continue the computation later.

Put the CIWindow into SKILL++ mode

Before proceeding, we need to change the listening mode of the CIWindow. We would like the CIWindow to interpret input expressions as SKILL++ rather than traditional SKILL.

Normally, when you type SKILL expressions into the CIWindow that defines functions or defines variables, the semantics of your code is taken as traditional SKILL. If, however, you would like to have SKILL++ (Scheme) semantics, you can put the CIWindow into SKILL++ Mode by calling the function (toplevel 'ils). This function does not return immediately, but rather puts the CIWindow into a different listening mode until you call the function resume, causing the (toplevel 'ils) to return.

You can find out which listening mode the CIWindow is in either by looking at the indicate in the button left-hand corner of the CIW. If in SKILL listening mode > will be inconspicuously displayed. The > is a little difficult to notice because it is so inconspicuous.

However, if in SKILL++ listening mode ILS-> will be displayed.

You may also determine the listening mode by calling the function theEnvironment which will return either nil if in SKILL mode, or non-nil, if in SKILL++ mode.

(theEnvironment)
  ==> nil
(toplevel 'ils)
(theEnvironment)
  ==> envobj@0x18fa2020
(resume)
  ==> nil
(theEnvironment)
  ==> nil

Defining an adder

With the CIWindow in SKILL++ mode we can proceed to define a SKILL++ function.

(unless (theEnvironment)
   (toplevel 'ils))

(defun make_adder_8a ()   ; 1.1
  (let ((sum 0))          ; 1.2
    (lambda (n)           ; 1.3
      sum = sum + n)))    ; 1.4

This definition of make_adder_8a is a 4 line function, yet does a lot in its 4 lines. It is a higher-order function, as seen in SKILL for the Skilled: What is SKILL++? it is a function which returns another function. It is a function which creates and returns a special kind of function called a lexical closure. In particular the lambda on line 1.3 creates a unary function which when called will evaluate the expression on line 1.4. However, the expression on line 1.4, references a variable, sum defined on line 1.2 and which is external to the lambda. In this case sum is called a free variable.

The important feature of SKILL++ which makes this magic work is that when make_adder_8a gets called, the let on line 1.2 creates a new binding for the variable named sum. A binding is a newly allocated memory location which is associated with a named variable. The initial value stored in this memory location is 0 as indicated on line 1.2. SKILL++ then proceeds to line 1.3 where it creates an anonymous function, attaching it to this binding. The two occurrences of the name, sum, on line 1.4 (within this anonymous function) are compiled as references to the binding.

The make_adder_8a function returns the anonymous function object created on line 1.3, without evaluating the code on line 1.4. Critically this function object maintains a link to the sum binding. Thereafter when the anonymous is called, the expression on line 1.4 is evaluated and its value returned. In evaluating this expression, the value of sum (in this allocated binding) is referenced and updated by the expression sum = sum + n, n being the value passed to the anonymous function when it is called.

Testing make_adder_8a

Let's experiment with make_adder_8a. Keep in mind that make_adder_8a does not actually add anything, rather it creates a function which is capabile of adding.

A = (make_adder_8a)       ; 2.1
  ==> funobj:A
(A 1)                     ; 2.2
  ==> 1
(A 2)                     ; 2.3
  ==> 3
(A 3)                     ; 2.4
  ==> 6
(A 4)                     ; 2.5
  ==> 10
(A 5)                     ; 2.6
  ==> 15

Arduous line-by-line explanation

On line 2.1, make_adder_8a is called, and as described above a SKILL++ anonymous function object (a closure) is created and returned. This closure is stored in the global variable A.

The CIWindow prints this value as funobj:A. As mentioned before the initial value of sum is 0. Note that sum is not a global variable. Rather it is a variable which is visible only to the code on lines 1.3 and 1.4. Furthermore, notice that we have no immediate access to the variable sum. We cannot query the value of code and we cannot modify its value, except by calling the function we have just stored in the global variable A.

When line 2.2, (A 1) is evaluated, the expression on line 1.4 is evaluated: sum = sum + n with n=1; sum is updated from 0 to 1, and 1 is returned and printed into the CIWindow.

When line 2.3, (A 2) is evaluated, again the expression on line 1.4 is evaluated: sum = sum + n with n=2. This time, sum is updated from 1 to 3 and 3 is returned.

When lines 2.4, 2.5, and 2.6 are evaluated, sum = sum + n is evaluated three times with n=3, n=4, and n=5 respectively; thus sum is updated to 6, 10, and finally to 15.

Summing a list with an adder

You can use an adder as created by make_adder_8a to add the elements of a list incrementally.

A = (make_adder_8a)          ; 3.1
  ==> funobj:A
(mapcar A '(1 2 3 4 5))      ; 3.2
  ==> (1 3 6 10 15)

This call to mapcar iterates across the given list (1 2 3 4 5) and calls the function A on each iteration, each time with the successive element of the list. Since each call to A returns the current value of the partial sum, mapcar returns not he final sum, but rather the list of partial sums computed at each step of the iteration.

Multiple SKILL++ adders in parallel

You can create several adders which work independent of each other. In the following example, we create two adders, A and B. Each one internally maintains its own partial sum of the arguments given to successive calls.

B1 = (make_adder_8a)       ; 4.1
  ==> funobj:B1
B2 = (make_adder_8a)       ; 4.2
  ==> funobj:B2
B3 = (make_adder_8a)       ; 4.3
  ==> funobj:B3
(B1 1)                     ; 4.4
  ==> 1
(B2 10)                    ; 4.5
  ==> 10
(B3 100)                   ; 4.6
  ==> 100
(B1 2)                     ; 4.7
  ==> 3
(B2 20)                    ; 4.8
  ==> 30
(B3 200)                   ; 4.9
  ==> 300
(B1 3)                     ; 4.10
  ==> 6
(B2 3)                     ; 4.11
  ==> 60
(B3 30)                    ; 4.12
  ==> 600

This works because each call to make_adder_8a on lines 4.1, 4.2, and 4.3, each allocate a new closure (three in all), assign each of them respectively turn to the global variables B1, B2, andB3. Each of these three function has its own independent binding of sum, each of which is initialized to code. When lines 4.4, 4.7, and 4.10 are evaluated, the sum binding of B1 is updated, but the sum bindings of B2 and B3 are not effected. Similarly when 4.5, 4.8, and 4.11 are evaluated, the sum binding of B2 is effected. And similarly for lines 4.6, 4.9, and 4.12.

Using flet as an alternative to lambda

If you find the use of (lambda ...) to be confusing in the definition of make_adder_8a, you can, as an alternative, define the same functionality using flet.

(defun make_adder_8b ()       ; 5.1
  (let ((sum 0))              ; 5.2
    (flet ((add (n)           ; 4.3
             sum = sum + n))  ; 5.4
      add)))                  ; 5.5

This implementation of make_adder_8b uses flet to define a local function named add. The normal pattern of using flet which you've seen in previous posts of SKILL for the Skilled such as Continued Introduction to SKILL++, is to define a local function and call it. The pattern used by make_adder_8b is to define a local function and return it, allowing the function which called make_adder_8b to call it, or likewise return it to its caller.

Data Encapsulation and Object Orientation

Some programming languages present the ability to encapsulate data as part of the object model. In these languages private variables are member variables within classes, and methods in/on those classes awkwardly manipulate and access these private variables.

This unholy marriage of private data to object model is limiting in practice because it is not only object oriented programs which need to hide data. In fact, a program written in any style may need to take advantage of encapsulate. In SKILL++ (and other dialects of Scheme), data encapsulation is independent from the object system, as it should be.

In SKILL++ the let and lambda primitives behave differently than in traditional SKILL. They behave in a way which allows a function to create lexical closures. These lexical closures are then able to manipulate the state of private variables which they encapsulate.

Summary

In this article, we looked at how to use lexical closures which maintain their internal state to implement counters. We looked very lightly and abstractly into how this is implemented within the SKILL++. And we traced step by step though a couple of examples of how this works in practice.

In this way SKILL++ provides data encapsulation completely independent from the object system. While SKILL++ does indeed have an extensive, full-featured, and powerful object system, in SKILL++ you are not forced to write a program in an object oriented way just to encapsulate/hide data. Encapsulation is a feature of SKILL++ which is available to you whether you are using OO, imperative, declarative, functional, or any other style you choose.

More to come

In the next post we'll look more at the differences you'll see when defining these types of functions in SKILL++ vs in SKILL.

SKILL for the Skilled: Many Ways to Sum a List (Part 7)

Team SKILL — Mon, 25 Mar 2013 13:05:00 GMT

In this episode of SKILL for the Skilled I'll introduce a feature of the let primitive that Scheme programmers will find familiar, but other readers may have never seen before. The feature is called named let, and I'll show you how to use it to sum the numbers in a given list.

Named LET

There is a feature of let available in SKILL++ which is not available in traditional SKILL, called named let. Here is an example of how it can be used to sum a given list of numbers.

(defun sumlist_7a (numbers)
  (let REPEAT
    ((sum_so_far 0)
     (rest       numbers))
    (if rest
        (REPEAT (plus sum_so_far (car rest))
                (cdr rest))
        sum_so_far)))

In this example, the named let defines a local function named, REPEAT and calls it once with the two arguments, 0 and numbers. Of course, REPEAT is by no means a reserved word; you can name the local function any valid variable name. Within the body of the named let you may call the local function with two arguments. You may recursively call the function zero, one, or more times as your algorithm requires.

Testing the function

If we enable tracing of sumlist_7a and REPEAT, we can see what happens when calling sumlist_7a. We can see that the local function, REPEAT is called recursively several times, and that the implementation does in fact return the correct sum of the given list of numbers.

(trace sumlist_7a)
(trace REPEAT)
(sumlist_7a '(1 2 3 4 5))
|sumlist_7a((1 2 3 4 5))
||(REPEAT 0 (1 2 3 4 5))
|||(REPEAT 1 (2 3 4 5))
||||(REPEAT 3 (3 4 5))
|||||(REPEAT 6 (4 5))
||||||(REPEAT 10 (5))
|||||||(REPEAT 15 nil)
|||||||REPEAT --> 15
||||||REPEAT --> 15
|||||REPEAT --> 15
||||REPEAT --> 15
|||REPEAT --> 15
||REPEAT --> 15
|sumlist_7a --> 15
15

Equivalent to labels

The named let is more or less equivalent to a declaration and call of a local function as if by using labels. If you recall, this is exactly what was shown in sumlist_3b in SKILL for the Skilled: Many Ways to Sum a List (Part 3).

(defun sumlist_3b (numbers)
(labels ((sum (sum_so_far rest)
             (if rest
                 (sum (plus (car rest) sum_so_far)
                      (cdr rest))
                 sum_so_far)))
    (sum 0 numbers)))

If you trace sumlist_3b and sum you'll see that it executes pretty much the same thing as sumlist_7a.

(trace sumlist_3b)
(trace sum)
(sumlist_3b '(1 2 3 4 5))
|sumlist_3b((1 2 3 4 5))
||(sum 0 (1 2 3 4 5))
|||(sum 1 (2 3 4 5))
||||(sum 3 (3 4 5))
|||||(sum 6 (4 5))
||||||(sum 10 (5))
|||||||(sum 15 nil)
|||||||sum --> 15
||||||sum --> 15
|||||sum --> 15
||||sum --> 15
|||sum --> 15
||sum --> 15
|sumlist_3b --> 15
15

Illusion of jumping to the top

The illusion (or abstraction) presented by the named let is that of being able to jump back to the top of the let form, and evaluate it again with different initialization values.

Consider this simple let example.

(let loop
   ((a 10)
    (b 0))
 (println (list a b))
 (when (plusp a)
   (loop (sub1 a) 
         (add1 b))))

Which prints the following output.

(10 0)
(9 1)
(8 2)
(7 3)
(6 4)
(5 5)
(4 6)
(3 7)
(2 8)
(1 9)
(0 10)

Doesn't work in traditional SKILL

If you try to evaluate a named let in traditional SKILL (e.g., with a .il file extension), you'll get an error something like the following, which basically means that SKILL let expects a list as its first operand and you have given the symbol loop instead.

*Error* let: local bindings must be a proper list - loop

let is syntactic sugar for lambda

In SKILL++ the normal let has the same semantics as calling an unnamed function with particular parameter values. For example:

(let ((a X)
      (b Y)
      (c Z))
  (expr1 a b)
  (expr2 b c))

Is semantically the same as the following arguably less readable expression. The expression uses funcall to call a nameless function, defined by the (lambda (a b c) ...); in particular to call it with the three values X, Y, and Z. In fact the two code snippets are simply syntactical transforms of each other.

(funcall (lambda (a b c)
           (expr1 a b)
           (expr2 b c))
         X
         Y
         Z)

When you look at the equivalent lambda form of let it is immediately clear that the expressions within the lambda are not able to make recursive calls to this unnamed function. This limitation is solved by the named let.

Named let and tail-call optimization

The illusion of jumping back to the top in sort of a goto fashion is indeed what happens if tail-call-elimination is enabled via the optimizeTailCall status flag explained in SKILL for the Skilled: Many Ways to Sum a List (Part 4).

Summary

In this post I've shown some examples of how to used the named let construct of SKILL++. This construct converts the conventional let into a loop --- a loop which can be repeated by calling the label as a function, providing the next iteration's variable values.

More to come

In upcoming posts we'll continue to survey the SKILL++ language using the example of summing a list.

SKILL for the Skilled: Many Ways to Sum a List (Part 6)

Team SKILL — Thu, 10 Jan 2013 17:04:00 GMT

In a previous post I presented sumlist_2b as a function that would sum lists of length 0, 1, or more.

(defun sumlist_2b (numbers)
  (apply plus 0 0 numbers))

Unfortunately sumlist_2b cannot handle extremely long lists. In this posting, I will introduce sumlist_6 which does not suffer from this limitation.

This posting will not introduce any new SKILL++ primitives. Instead, it will use several primitives which have been introduced in the previous several postings to implement an algorithm which you may not have seen before. If any of these are unknown or mysterious to you, please consult previous postings of SKILL for the Skilled or the Virtuoso on-line documentation.

apply used to call a function indirectly given the function object and a list of arguments. sstatus modify a status variable of the SKILL virtual machine. optimizeTailCall makes function calls in tail position be stack-space neutral. labels defines local function functions which may be mutually recursive unwindProtectdefines a clean-up procedure which is executed even if an error is triggered.

Very long lists

If you attempt to use sumlist_2b on extremely long lists it will fail. You can generate a very long list as follows:

data = (list 1.1 -2.1 2.3 -.04)
(for i 1 15
  data = (append data data))

This produces a list of length 131072. If you attempt to sum this list with sumlist_2b you get the following error.

*Error* plus: too many arguments (at most 65535 expected, 131074 given) - (0 0 1.1 -2.1 2.3 ... )
<<< Stack Trace >>>
apply(plus 0 0 numbers)
sumlist_2b(data)

The error message complains about a list of length 131074. This is because data has length 131072, but sumlist_2b prepends two additional 0's to the argument list. 131072 + 2 = 131074.

An esoteric issue?

You may very well consider this an esoteric issue. And you would be right. If you are in charge of generating the data, and you know the number of elements in your list is less than 16K, then there is no need to worry about this corner case. I suspect very few of the readers of this blog have ever, or will ever encounter such a situation. Even with that being the case, I discuss this here in the hopes that some of the techniques may prove useful, even if the exact problem never occurs.

Another reason to present a solution to this particular problem is that in so doing we can combine several other concepts which have been discussed in the previous SKILL for the Skilled blog postings.

The applyReduce function

The following implementation of applyReduce takes advantage of (sstatus optimizeTailCall t) and unwindProtect as seen in a previous post of SKILL for the Skilled.

(defun applyReduce (fun args @key (maxArgs 8192) identity)
  (labels ((apply_head (fun args tail)
             (let ((save (cdr tail)))
               (setcdr tail nil)
               (unwindProtect
                (apply fun args)
                (setcdr tail save))))
           (apply_reduce (args)
             (let ((tail (nthcdr (sub1 maxArgs) args)))
               (if (cdr tail)
                   (apply_reduce (cons (apply_head fun args tail)
                                       (cdr tail)))
                   (apply fun args)))))
    (cond
      ((cdr args) 
       ;; if args has more the two elements
       (let ((save_optimizeTailCall (status optimizeTailCall)))
         (sstatus optimizeTailCall t)
         (unwindProtect
           (apply_reduce args)
           (sstatus optimizeTailCall save_optimizeTailCall))))
      (args
       ;; if args has exactly one element
       (car args))
      (t
       ;; if args is nil
       identity))))

How does it work?

The applyReduce function above calls the given function multiple times, but each time with a maximum of maxArgs number of arguments. The maxArgs parameter defaults to 8192 but you may override it to something smaller, especially to understand better how the function works.

(trace plus)
(applyReduce plus '(.1 .2 .3 .4 .5 .6 .7 .8 .9
                    .11 .12 .13 .14 .15 .16 .17 .18 .19) ?maxArgs 5)
(untrace plus)

In the trace output you can see that the plus function is called several times, but never with more than 5 arguments. After the initial call, the first argument to plus is the return value of the previous call.

||||||||||||||(0.1 + 0.2 + 0.3 + 0.4 + 0.5)
||||||||||||||plus --> 1.5
||||||||||||||||(1.5 + 0.6 + 0.7 + 0.8 + 0.9)
||||||||||||||||plus --> 4.5
||||||||||||||||||(4.5 + 0.11 + 0.12 + 0.13 + 0.14)
||||||||||||||||||plus --> 5.0
||||||||||||||||||||(5.0 + 0.15 + 0.16 + 0.17 + 0.18)
||||||||||||||||||||plus --> 5.66
||||||||||||||||||(5.66 + 0.19)
||||||||||||||||||plus --> 5.85

Now we can use applyReduce to create an efficient sumlist_6 function which is able to add up the elements of an arbitrarily long list. We can use sumlist_6 to add up the 131072 elements of the list data created above.

(defun sumlist_6 (numbers)
  (applyReduce plus numbers ?identity 0))

Testing it, we can see that it works and returns the correct result. We need to test sumlist_6 for a very long list, as well as for the nil list and a singleton list.

(sumlist_6 data)
--> 41287.68

(sumlist_6 nil)
--> 0

(sumlist_6 '(42))
--> 42

What about the performance?

Recall the algorithm implemented as sumlist_1a.

(defun sumlist_1a (numbers)
  (let ((sum 0))
    (foreach number numbers
      sum = sum + number)
    sum))

On the Linux machine which I normally use, evaluating (sumlist_1a data) takes approximately 0.02 seconds, while evaluating (sumlist_6 data) takes about 0.003. I.e., sumlist_6 is about 6 times faster for large lists.

Summary

The technique shown in sumlist_2b is very simple, and requires very little code. Nevertheless, it has the caveat that it will fail for arbitrarily long lists. This usually does not matter, and because this corner case is relatively unlikely to occur, the technique is tempting to use, and in fact is a good solution if the data is under your control and you know the length of the list in question is not extremely large.

The technique shown in sumlist_6 is more correct, at the sacrifice of being more complicated code. That being said, because the complication of sumlist_6 is factored into the implementation of the function applyReduce, the actual implementation of sumlist_6 is as simple as sumlist_2b. I would suggest putting a copy of applyReduce in your personal SKILL function library, with the appropriate customer prefix of course.

More to come

In upcoming posts we'll continue to survey the SKILL++ language using the example of summing a list.

Jim Newton

Previous blog posts in this series

SKILL for the Skilled: Many Ways to Sum a List (Part 5)

SKILL for the Skilled: Many Ways to Sum a List (Part 4)

SKILL for the Skilled: Many Ways to Sum a List (Part 3)

SKILL for the Skilled: Many Ways to Sum a List (Part 2)

SKILL for the Skilled: Many Ways to Sum a List (Part 1)

SKILL for the Skilled: Many Ways to Sum a List (Part 5)

Team SKILL — Mon, 26 Nov 2012 17:00:00 GMT

In the most recent posts of SKILL for the Skilled (see previous post here) we looked at different ways to sum a given list of numbers. The goal of these articles is not really to help you sum lists better, but rather to use a simple problem to demonstrate and compare features of the SKILL++ language.

In this posting of we show yet another implementation of sumlist using an operator which will be new to many readers. While the do construct is common to many lisp dialects, particularly Scheme implementations, it is somewhat controversial as some people love it, and some people hate it. Some people find it elegant and expressive, and other find it terse and awkward. I'll present it here and let you decide for yourself.

Summing a list with the (do ...) loop

Recall the implementation of sumlist_1a which accepts a list of numbers as its argument and returns the arithmetic of these numbers.

(defun sumlist_1a (numbers)
  (let ((sum 0))
    (foreach number numbers
      sum = sum + number)
    sum))

Here is yet another implementation of the sumlist function which we've seen in the past several postings. This version of the function uses the (do ...) construct.

(defun sumlist_5a (numbers)
  (do ((remaining  numbers (cdr remaining))
       (sum_so_far 0       (plus sum_so_far (car remaining))))
      ((null remaining)
       sum_so_far)))

Evolution of Lisp

There is an interesting paper which is easy to find on the Internet named Evolution of Lisp by Guy Steele and Richard Gabriel. This paper chronicles many of the features of modern Lisp languages. In the paper you can see the origins of many of the features of SKILL, including the rather obscure one we are going to look at today. Although this construct was first introduced into Maclisp in 1972, Evolution of Lisp refers to it as the new-style do.

An excerpt from Evolution of Lisp:

The awful part [of do] is that it uses multiple levels of parentheses as delimiters and you have to get them right or endure strange behavior; only a diehard Lisper could love such a syntax. Arguments over syntax aside, there is something to be said for recognizing that a loop that steps only one variable is pretty useless, in any programming language. It is almost always the case that one variable is used to generate successive values while another is used to accumulate a result. If the loop syntax steps only the generating variable, then the accumulating variable must be stepped "manually" by using assignment statements [...] or some other side effect. The multiple-variable do loop reflects an essential symmetry between generation and accumulation, allowing iteration to be expressed without explicit side effects:

Examining the example

The sumlist_5a uses do to iterate two variables remaining and sum_so_far from their respective initial values to their final values, using respective formulas to update the variables to their next values.

Breaking it down: Step by Step

As was mentioned above, the syntax of do is somewhat off-putting. There are lots of parentheses, and several interdependent components which you have to get right. The following is an itemization of the various parts of the (do ...) loop.

You normally need to declare 0 or more variables: remaining and sum_so_far in this case. Two variables are specified in this case, but you may use as many as you like.

(do ((remaining  numbers (cdr remaining))
     (sum_so_far 0       (plus sum_so_far (car remaining))))
    ((null remaining)
     sum_so_far))

Specify an initial value of each variable:

remaining = numbers
sum_so_far = 0

(do ((remaining  numbers (cdr remaining))
     (sum_so_far 0       (plus sum_so_far (car remaining))))
    ((null remaining)
     sum_so_far))

Specify a termination condition. The loop continues until this expression becomes TRUE. In this case:
- (null remaining)
specifying to continue until the list remaining is empty.
```
(do ((remaining  numbers (cdr remaining))
     (sum_so_far 0       (plus sum_so_far (car remaining))))
    ((null remaining)
     sum_so_far))
```
If the condition is not yet TRUE, then each variable is updated as per the corresponding formula. In this case:
- remaining = (cdr remaining)
- sum_so_far = (plus sum_so_far (car remaining))
```
(do ((remaining  numbers (cdr remaining))
     (sum_so_far 0       (plus sum_so_far (car remaining))))
    ((null remaining)
     sum_so_far))
```
When the condition is TRUE, the loop terminates and the specified value is returned. This value is usually depends on some of the iteration variables. In this case:
- sum_so_far
```
(do ((remaining  numbers (cdr remaining))
     (sum_so_far 0       (plus sum_so_far (car remaining))))
    ((null remaining)
     sum_so_far))
```

It is not shown above, but you may optionally include 1 or more expressions in the body of the (do ...).

(do ((remaining  numbers (cdr remaining))
     (sum_so_far 0       (plus sum_so_far (car remaining))))
    ((null remaining)
     sum_so_far)
  (println remaining)
  (printf "partial sum = %L\n" sum_so_far))

Variations

One way to think of the SKILL do is as a mixture or generalization of several iteration constructs.

Do as for

The following is like a (for ...) loop.

(do ((i 0 i+1))
    (i==100 
     t) ; return t because for always returns t
  (println i))

... is equivalent to ...

(for i 0 100
  (println i))

Do as foreach

The following is like a (foreach ...) loop.

(let ((some_list '(a b c d)))
  (do ((sub  some_list        (cdr sub))
       (item (car some_list)  (cadr sub)))
      ((null sub) 
       some_list) ; return some_list because foreach returns the list it iterated over
    (println item)))

... is equivalent to ...

(let ((some_list '(a b c d)))
  (foreach i some_list
    (println i)))

Do as a mixture of for and foreach

The (foreach ...) iterates successively through a given list of items. The (for ...) loop iterates successively through a range of integers, given the lower and upper bounds of the range. If you want to iterate one variable through a given list while simultaneously iterating another variable through a range of integers, you can use the (do ...) loop.

(let ((some_list '(a b c d ...)))
  (do ((index 0               (add1 index))
       (sub   some_list       (cdr sub))
       (item  (car some_list) (cadr sub)))
      ((null sub) 
       t)
    (printf "The %d'th of the list is %L\n" index item)))

Which produces the following output.

The 0'th of the list is a
The 1'th of the list is b
The 2'th of the list is c
The 3'th of the list is d
The 4'th of the list is e
The 5'th of the list is f
The 6'th of the list is g

Summary

The SKILL do can be tricky to use. It allows the programmer control of several parallel iteration variables, all of which are potentially incremented according to different rules. You may also explicitly determine the return value, which is fixed and useless for other iteration constructs such as (for ...). You may also specify a series of expressions to evaluate when the iteration finishes while the iteration variables are still in scope holding their final values.

Hopefully you can use the steps above as sort of a cookbook.

More to come
In upcoming posts we'll continue to survey the SKILL++ language using the example of summing a list. See Also

Jim Newton

SKILL for the Skilled: Many Ways to Sum a List (Part 4)

Team SKILL — Mon, 15 Oct 2012 15:27:00 GMT

In the previous posts SKILL for the Skilled: Many Ways to Sum a List (Parts 1, 2, and 3) we looked at several ways to sum a given list of numbers. We ignored the cases of the given list being very long. In this post, we will examine a way to sum the elements of arbitrarily long lists using recursive functions.

The approach shown in this post (part 4) will only work in Virtuoso IC 6.1; it depends on features which are not available in IC 5.1.41 and earlier. In particular we'll look at the optimizeTailCall status flag and at unwindProtect.

You may read this post in either of two ways. If you would like a way to make arbitrarily deep recursion work in SKILL++, you can look at the usage of the callWithOptimizeTailCall function in sumlist_4a. If you'd like to know how it works, look at the section Some Trickery.

What about large lists?

One disadvantage of the type of recursive function shown in sumlist_3a (seen earlier) is that every pending call to a function in SKILL++ requires stack space, and stack space is limited.

The two functions sumlist_1a and sumlist_3a differ in their ability to handle long lists. To demonstrate this limitation it helps to programmatically generate a very long list. The following expressions will generate a list of length 16,384.

data = (list 1.1 -2.1 2.3 -.04)
(for i 1 12
  data = (append data data))

Now what happens if we try to add up 16,384 numbers?

(sumlist_1a data)
=> 5160.96

(sumlist_3a data)

*Error* sumlist_3a: Runtime Stack Overflow!!!
<<< Stack Trace >>>
sumlist_3a(cdr(numbers))
(car(numbers) + sumlist_3a(cdr(numbers)))
if(numbers (car(numbers) + sumlist_3a(cdr(numbers))) 0)
sumlist_3a(cdr(numbers))
(car(numbers) + sumlist_3a(cdr(numbers)))
if(numbers (car(numbers) + sumlist_3a(cdr(numbers))) 0)
sumlist_3a(cdr(numbers))
(car(numbers) + sumlist_3a(cdr(numbers)))
if(numbers (car(numbers) + sumlist_3a(cdr(numbers))) 0)
sumlist_3a(cdr(numbers))
...

(sumlist_3b data)
*Error* unknown: Runtime Stack Overflow!!!
<<< Stack Trace >>>
sum((sum_so_far + car(rest)) cdr(rest))
if(rest (sum (sum_so_far + car(rest)) cdr(rest)) sum_so_far)
sum((sum_so_far + car(rest)) cdr(rest))
if(rest (sum (sum_so_far + car(rest)) cdr(rest)) sum_so_far)
sum((sum_so_far + car(rest)) cdr(rest))
if(rest (sum (sum_so_far + car(rest)) cdr(rest)) sum_so_far)
sum((sum_so_far + car(rest)) cdr(rest))
if(rest (sum (sum_so_far + car(rest)) cdr(rest)) sum_so_far)
sum((sum_so_far + car(rest)) cdr(rest))
if(rest (sum (sum_so_far + car(rest)) cdr(rest)) sum_so_far)
...

It seems there is not enough stack space to add these numbers using the types of recursive functions we have seen up until now.

Tail call optimization

The subtle difference between sumlist_3a and sumlist_3b is not very important in the simple case, but allows for a very special optimization called tail call optimization. The maximum length of the list you may pass to function sumlist_3a is limited by the stack-space. As seen in the stack-trace above, if the list is too long, we get the error Runtime Stack Overflow!!!.

When tail call optimization is enabled, a function call in tail position does not consume additional stack space, thus allowing such a function call (even a recursive function call) to work like a GOTO.

(defun callWithOptimizeTailCall (thunk)
  (let ((save (status optimizeTailCall)))
    (sstatus optimizeTailCall t)
    (unwindProtect
      (thunk)
      (sstatus optimizeTailCall save))))

In SKILL++, tail call optimization is a run-time switch. This means you need not do anything special when loading your code, but you have to enable the optimization at run-time. The function callWithOptimizeTailCall, defined above, is written to allow the caller to specify which bit of code needs the optimization. It can be used as shown in sumlist_4a defined here.

(defun sumlist_4a (numbers)
  (labels ((sum (sum_so_far rest)
             (if rest
                 (sum (plus sum_so_far (car rest))
                      (cdr rest))
                 sum_so_far)))
    (callWithOptimizeTailCall
       (lambda ()
         (sum 0 numbers)))))

OK, Let's Test It

So does it work?

(sumlist_4a data)
==> 5160.96

Yippie! no stack trace. SKILL++ was able to make the recursive call 16,384 times with no problem.

Okay, let's stress test it.

(progn data = (append data data)
       data = (append data data)
       data = (append data data)
       (length data))
==>131072

Now let's see if SKILL++ can add up a list of 131,072 numbers by a recursive function:

(sumlist_4a data)
==>41287.68

Yes. No problem.

Manipulating optimizeTailCall

You don't really need to understand how callWithOptimizeTailCall works in order to use it. To use it, the one or more expressions you'd like to evaluate with the optimization enabled must be wrapped in (lambda () ...) and that function of no arguments should be passed to the callWithOptimizeTailCall.

(callWithOptimizeTailCall
  (lambda ()
     ... some code ...
     ... maybe some more code ...
  ))

The promise of callWithOptimizeTailCall is that it will call the given function with tail call optimization enabled, but have no lasting effect on the global optimizeTailCall setting. I.e., if optimizeTailCall was enabled, it will remain enabled; and if it was disabled, it will remain disabled.

Some Trickery

The implementation of callWithOptimizeTailCall uses some pretty low level trickery which some of the readers might find interesting. status E.g., (status debugMode)
returns either t or nil depending on the value of the named (unquoted) status flag. There are several other documented status flags in SKILL. Perhaps the most commonly used ones are debugMode and printinfix. See the Cadence on-line documentation for explanation of others. debugMode Instructs the SKILL VM compiler to include additional debug information into the compiled instructions. printinfix Instructs the SKILL pretty-printer whether to use infix operators (such as +, ||, ', and ->) and C-style function call syntax such as (1+2+3), or whether to use function names (such as plus, or, quote, and getq), and use lisp-style function call syntax such as (plus 1 2 3). sstatus E.g., (sstatus debugMode t)
Sets the value of the named global status flag. All the flags which are available to status are available for sstatus. unwindProtect E.g., (unwindProtect (unsafe_function) (deleteFile fileName)).
This is used when calling a function or evaluating an expression which might trigger an error. unwindProtect takes two operands: an expression to evaluate, and a clean-up expression. The clean-up expression will get evaluated regardless of whether the first expression triggered an error or not. However, unlike errset it does not suppress the error. In the example in callWithOptimizeTailCall, the use of unwindProtect assures that (sstatus optimizeTailCall save), i.e., the call to restore the optimizeTailCall status occurs, even if the given function, thunk triggered an error. optimizeTailCall E.g., (sstatus optimizeTailCall t)
Controls whether tail-call optimization is enabled. Remember to always restore optimizeTailCall to its previous value so as never to globally effect this flag.

Quick Review

In this post you saw a cookbook way of modifying a particular type of recursive function so that it does not need significant stack space at run-time. The main trick is to write the recursion using tail-call style, and use the function callWithOptimizeTailCall to let SKILL++ do the work for you.

More to come

In the upcoming postings we'll look at even more variations of list summing.

See Also

Tail Call

Jim Newton

SKILL for the Skilled: Many Ways to Sum a List (Part 3)

Team SKILL — Tue, 18 Sep 2012 21:00:00 GMT

In Part 1 and Part 2 of this series of posts, I showed a couple of ways to sum up a given list of numbers. In this post, I want to show a couple of ways to use recursive functions to do this.

Recall the sumlist_1a function

In a previous posting the function sumlist_1a was defined.

(defun sumlist_1a (numbers)
  (let ((sum 0))
    (foreach number numbers
      sum = sum + number)
    sum))

Describing this algorithm in words, we see that it does not express the mathematical relationship very well, but it does describe how a Von Neumann machine would perform the calculation.

Initialize an accumulator to 0
Keep incrementing the accumulator by the successive element of the list
When the list is exhausted, return the accumulator

Implementation with simple recursion

The following implementation of sumlist_3a is an example of simple recursion.

(defun sumlist_3a (numbers)
  (if numbers
      (plus (car numbers)
            (sumlist_3a (cdr numbers)))
      0))

Expressing this algorithm in words, you can see that it is more elegant than sumlist_1a as the code actually expresses a mathematical relationship.

The sum of the empty list is 0
The sum of a N element list is the first element plus the sum of the remaining elements

An advantage of recursive functions such as sumlist_3a is that they are elegant. They often require less code because there is no need to maintain state; e.g., there is no accumulator variable, and no variables are modified during the evaluation of the function.

Implementation with tail recursion

The sumlist_3b function is a tail recursive version of sumlist_3a.

(defun sumlist_3b (numbers)
  (labels ((sum (sum_so_far rest)
             (if rest
                 (sum (plus (car rest) sum_so_far)
                      (cdr rest))
                 sum_so_far)))
    (sum 0 numbers)))

An obvious drawback of this type of recursive function is that it is more difficult for the human to read than simple recursion.

Tail recursion is a technique which can be used to enable recursive function to require no more stack space than iterative functions. There is a pretty clear explanation on Wikipedia.

The main difference, computation-wise, between sumlist_3a and sumlist_3b is the following. In sumlist_3a the final computation the function does is to call the plus function. For example the top level call to sumlist_3a with (1 2 3 4 5 6 7) must completely finish processing (2 3 4 5 6 7) before it can add the 1--the call to (plus 1 ...) cannot occur before the recursive call to sumlist_3a returns.

In sumlist_3b, on the other hand, the computation order is reversed. In the local function, sum, the (plus 1 ...) happens first. That partial sum is passed as the sum_so_far parameter. The final thing the local function does is call itself recursively. There is no pending operating waiting for the recursive call to return.

We'll talk more about why this is important in an upcoming posting of SKILL for the Skilled -- Many Ways to Sum a List.

Testing the functions

If we call sumlist_1a, sumlist_3a, and sumlist_3b on some examples we see that they return the same thing.

(sumlist_1a nil)
=> 0

(sumlist_3a nil)
=> 0

(sumlist_3b nil)
=> 0

(sumlist_1a '(3.4))
=> 3.4

(sumlist_3a '(3.4))
=> 3.4

(sumlist_3b '(3.4))
=> 3.4

(sumlist_1a '(1 2 3 4 5 6 7))
=> 28

(sumlist_3a '(1 2 3 4 5 6 7))
=> 28

(sumlist_3b '(1 2 3 4 5 6 7))
=> 28

Computation order

That the computation order of sumlist_3a and sumlist_3b are opposite can be seen by tracing the plus function.

(trace plus)
==>(plus)
(sumlist_3a '(1 2 3 4 5))
||||||(5 + 0)
||||||plus --> 5
|||||(4 + 5)
|||||plus --> 9
||||(3 + 9)
||||plus --> 12
|||(2 + 12)
|||plus --> 14
||(1 + 14)
||plus --> 15
==>15
(sumlist_3b '(1 2 3 4 5))
||||(1 + 0)
||||plus --> 1
|||||(2 + 1)
|||||plus --> 3
||||||(3 + 3)
||||||plus --> 6
|||||||(4 + 6)
|||||||plus --> 10
||||||||(5 + 10)
||||||||plus --> 15
==>15

Looking at the trace output, we see that sumlist_3a calls plus with first argument being first 5, then 4, 3, 2, and finally 1. However, sumlist_3b, plus is called first with first argument being 1, then with 2, 3, 4, and finally with 5. Since integer addition is commutative, associative, and side effect free, both algorithms give the same result.

This difference in the two computation models might be important in some situations if some function other than plus is used. For example, if a function with side effects is used, you might find that the side-effects happen in a different order.

For example, replacing the 0 with nil, replacing the plus function with cons, and renaming the local function from sum to rev we have two different and useful functions: a list-copy function and a list-reverse function.

(defun copy_3e (numbers)
  (if numbers
      (cons (car numbers)
            (copy_3e (cdr numbers)))
      nil))

(defun reverse_3f (numbers)
  (labels ((rev (list_so_far rest)
             (if rest
                 (rev (cons (car rest) list_so_far)
                      (cdr rest))
                 list_so_far)))
    (rev nil numbers)))

Testing these functions we see the following results:

(copy_3e '(1 2 3 4 5))
==>(1 2 3 4 5)
(reverse_3f '(1 2 3 4 5))
==>(5 4 3 2 1)

Review

In the paragraphs above we looked at two different types of recursive functions. The two techniques usually give compatible results. However, depending on the application one technique may be preferable because of computation order or order of side effects.

More to come

I've alluded several times to the issue that these recursive functions fail for very long lists. In the next post we'll look at some ways of dealing with this issue.

See Also

Tail Recursion

Jim Newton

SKILL for the Skilled: Many Ways to Sum a List (Part 2)

Team SKILL — Mon, 10 Sep 2012 15:53:00 GMT

In the previous posting, SKILL for the Skilled: Many Ways to Sum a List (Part 1), I showed a couple of ways to arithmetically sum up a given list of numbers. In particular, I presenting the following function definition.

(defun sumlist_1b (numbers)
  (apply plus numbers))

In this posting, (Part 2), we'll look at improving this implementation by using the apply function with more than two arguments to enable handling of short lists.

Limitations of the sublist_1b

This function, sumlist_1b, is usually able to add up the numbers in a given list. It is the fastest way I know of from SKILL++ to sum a list, and because of that it is tempting to ignore several cases where it fails.

the nil list
a singleton list
a list whose length is longer than 65535 in length.

An attempt to sum the elements of the empty list results in the following:

(sumlist_1b nil)
*Error* plus: too few arguments (at least 2 expected, 0 given) - nil
<<< Stack Trace >>>
apply(plus numbers)
sumlist_1b(nil)

An attempt to sum the elements of a singleton list results in the following:

(sumlist_1b '(3.4))
*Error* plus: too few arguments (at least 2 expected, 1 given) - (3.4)
<<< Stack Trace >>>
apply(plus numbers)
sumlist_1b('(3.4))

It is somewhat curious but notable that the SKILL plus function is unable to be called with zero or a single argument.

Sometimes you may be able to ignore this limitation

If you are in charge of the data, for example if your program is generating the lists of numbers which you'd like to sum up, you may already know that that in your application sumlist_1b will never be called with nil, singleton lists, or extremely long lists. If that is the case there is no need to worry; sumlist_1b works just fine despite its limitation. However, you need a more robust version of this function, read on.

Try #1 to fix sumlist_1b

The first two of the above limitations can be solved in a straightforward way as special cases in the function implementation.

(defun sumlist_2a (numbers)
  (cond
    ((cdr numbers)          ; if there is more than one element
     (apply plus numbers))
    ((null numbers)         ; if zero elements
     0)
    (t                      ; a singleton list
     (car numbers))))

The sumlist_2a function contains special cases for the nil list and for a singleton list. The tests in the (cond ...) are ordered such that the most common case comes first: (cdr numbers). If the given list has more than one element, then the cdr function will return non-nil. I am assuming that this is the most common situation.

Using apply with 3 or more arguments

Rather than adding additional complexity as in sumlist_2a, there is a simpler way to extend sumlist_1b to work on nil and singleton lists.

With two arguments, the apply function, calls the designated function with the given argument list. A standard (and handy) feature of apply is that if it is given more than two arguments, the second to penultimate ones have the special meaning that they are implicitly prepended to the final one. For example:

(apply plus 1 2 3 '(4 5 6 7 8))

is equivalent to

(apply plus '(1 2 3 4 5 6 7 8))

This feature of apply is pretty common for Lisp dialects such as Common Lisp, elisp (emacs lisp), and MIT/GNU Scheme. One would naturally expect the apply function in SKILL to work the same way, and fortunately it does.

This feature of apply is of course not very interesting for lists whose contents are explicitly given, because if you can type (apply plus 1 2 3 '(4 5 6 7 8)) you can as easily type (apply plus '(1 2 3 4 5 6 7 8)). But it does allow us to rewrite the sumlist_1b function as follows.

(defun sumlist_2b (numbers)
  (apply plus 0 0 numbers))

Why does this work?

This works because prepending 0 twice to the argument list of plus assures that plus has at least two arguments. Also, zero is the arithmetic identity for addition. Arithmetically adding two zeros does not effect the sum -- neither in value nor in type.

Similar problems

Is there a way to construct a function such as sumlist_1b, sumlist_2a, or sumlist_2b which will work for other types of operations like maximization and minimization?

Using the model shown in sumlist_1b, we can implement a function that will return the maximum element of a given list, provided the list has more than one element.

(defun maxlist_2c (numbers)
  (apply max numbers))

However, maxlist_2c fails if the list has one or zero elements. If you want to be able to maximize a list even it it is nil or a singleton list, you can do something similar to sumlist_2a. The maximum element of a singleton list is the first (only) element. However, you'd have to define what you mean by the maximum element of an empty list. It does not really make sense in general because the max operation does not have an identity element. While x+0=0+x=x, there is no number, I, such that max{x,I}=max{I,x}=x. For this reason the function maxlist_2d triggers an error for the empty list.

Even though it does not make sense in general, for your particular application it very well might have a meaning; so you can change the call to error by some other code as you like.

(defun maxlist_2d (numbers)
  (cond
    ((cdr numbers)
     (apply max numbers))
    ((null numbers)
     (error "cannot find maximum of the empty list"))
    (t
     (car numbers))))

More to come

SKILL for the Skilled: Many Ways to Sum a List (Part 1)

Team SKILL — Wed, 05 Sep 2012 15:38:00 GMT

A while back I presented a one day SKILL++ seminar to a group of beginner and advanced SKILL programmers. One example I showed was Variations on how to sum a list of numbers. This is a good example because the problem itself is easy to understand, so the audience can concentrate on the solution techniques rather than on the problem itself.

I want to show a few of these examples in this blog post (and a few upcoming posts) in hopes you may find some of the techniques useful.

Summing Straightforward

One straightforward way to sum a given list of numbers is to use simple iteration and mimic a primitive microprocessor. That is, establish an accumulator initialized to zero, and continue to increment the accumulator by successive numbers from the list until the list is exhausted, and finally return the accumulated value.

(defun sumlist_1a (numbers)
  (let ((sum 0))
    (foreach number numbers
      sum = sum + number)
    sum))

I imagine the code in this function would look very similar in many different languages such as C or Java -- of course with syntax variations.

Summing with apply

In SKILL++ (as well as in traditional SKILL) this is not a particularly efficient implementation because the SKILL virtual machine compiler, unlike a native compiler, is not able to make particularly good use of the processor registers. The way to force SKILL to use the processor registers is to organize your code, when possible, to call built-in compiled functions.

(defun sumlist_1b (numbers)
  (apply plus numbers))

Remember -- to force this function to be defined as SKILL++ rather than traditional SKILL, you'll either need to load it from a file with a .ils extension, or you'll need two wrap the definition in (inScheme ...) when you copy and paste it into the CIWindow.

A quick test with measureTime shows that sumlist_1b is roughly 10 times faster than sumlist_1a on a 10,000 element list of numbers.

How does it work?

The plus function returns the sum in its argument list. For example: (plus 1 2 3 4 5) evaluates to 15.

The apply function, when called with two arguments, calls the function designated by its first argument. In particular apply calls that function argument list given as its second argument. For example:

(apply plus '(1 2 3 4 5))

is a call to plus with two arguments. The first argument plus is the function which apply should call. The second argument, '(1 2 3 4 5) is the list of arguments to call plus with. Thus this use of apply is equivalent to the following.

(plus 1 2 3 4 5)

Note that plus is used without a leading quote because in SKILL++ all global functions are available in a SKILL++ global variable of the same name. The variable plus evaluates to the plus function.

Since sumlist_1b is so much faster (execution-wise) and simpler (line-of-code-wise), it is very tempting to use, but be careful! It suffers from some limitations that do not exist with sumlist_1a. For example, sumlist_1b cannot sum the elements of the nil list. The sumlist_1a, however, claims the sum of the list nil is 0, which indeed sounds like a reasonable answer. Furthermore, sumlist_1a, claims that the sum of a singleton list such as (3.4) is the first (and only) element of the list, which again seems like a reasonable result.

Apply in other languages

Actually the apply function is not an invention of the SKILL (or SKILL++) language. It is in fact central to programming languages derived from lambda calculus. A quick search on Wikipedia finds an article explaining its use in several languages.

More to come

In the next posting, I'll show some ways to get the speed and conciseness of sumlist_1b without the caveats.

SKILL for the Skilled: Introduction to Classes -- Part 5

Team SKILL — Fri, 10 Feb 2012 14:00:00 GMT

In the previous SKILL for the Skilled postings, we looked at a pretty good algorithm for solving the Sudoku puzzle. This algorithm is able to find at least one solution of the puzzle if one exists, and is able to detect that no solution exists if that is in fact the case. In this article we look at a particularly difficult case which the algorithm we have chosen performs poorly.

What about a difficult puzzle?

In his article Solving Every Sudoku Puzzle, Peter Norvig suggests a puzzle which is pretty difficult. In fact it is the worse case for the algorithm he proposes in the article.

Sudoku puzzle 5-1
(SkuSolve '((? ? ? ? ? 6 ? ? ?) (? 5 9 ? ? ? ? ? 8) (2 ? ? ? ? 8 ? ? ?) (? 4 5 ? ? ? ? ? ?) (? ? 3 ? ? ? ? ? ?) (? ? 6 ? ? 3 ? 5 4) (? ? ? 3 2 5 ? ? 6) (? ? ? ? ? ? ? ? ?) (? ? ? ? ? ? ? ? ?)))

The algorithm implemented in SkuFindSolution does in fact solve this puzzle but considerably slower than the other examples shown above. On the particular machine I'm using, all the puzzles described in the previous posting are solved in less than 1/10 of a second. This problematic puzzle takes more than 25 seconds to solve.

starting with: 
+-----+-----+-----+
| | | | | |6| | | |
| |5|9| | | | | |8|
|2| | | | |8| | | |
| |4|5| | | | | | |
| | |3| | | | | | |
| | |6| | |3| |5|4|
| | | |3|2|5| | |6|
| | | | | | | | | |
| | | | | | | | | |
+-----+-----+-----+


found solution:
+-----+-----+-----+
|8|3|4|9|7|6|5|1|2|
|6|5|9|2|3|1|7|4|8|
|2|7|1|4|5|8|6|9|3|
|1|4|5|8|6|2|3|7|9|
|7|2|3|5|4|9|8|6|1|
|9|8|6|7|1|3|2|5|4|
|4|1|7|3|2|5|9|8|6|
|5|9|2|6|8|4|1|3|7|
|3|6|8|1|9|7|4|2|5|
+-----+-----+-----+

A different algorithm

The version of SkuFindSolution shown in SKILL for the Skilled: Part 4 iterates over the cells in the board simply in the order they appear in the list. The following improved version of SkuFindSolution first sorts the cells into order of increasing possibility. Cells which have few possibilities are moved to the beginning of the list, and cells with more possibilities are moved to the end of the list.

The changes in the function are to introduce the local function count_possibilities into the (labels ...),

(count_possibilities (cell)
  (let ((c 0))
    (for i 1 9
      (unless (conflict? i cell)
        c++))
     c))

and to insert a call to (sort ... (genCmpFunction...))

sudoku->cells = (sort sudoku->cells
                      (genCmpFunction ?key count_possibilities))

before calling solve_cell.

Recall the functions genCmpFunction and identity from a previous blog posting.

(defun genCmpFunction (@key (test lessp)
                            (key  identity))
  (lambda (A B)
    (test (key A)
          (key B))))

(defun identity (x)
  x)

The genCmpFunction generates a function which can be used as the second argument of sort. In this case genCmpFunction returns a function which will cause sort to order the cells in increasing order according to the return value of count_possibilities.

The local function count_possibilities returns the integer corresponding to how many of the number in the set {1 2 3 4 5 6 7 8 9} are conflict-free when placed in the given cell.

New version of SkuFindSolution

(defun SkuFindSolution (sudoku)
  (prog ()       
    (labels ((count_possibilities (cell)
               (let ((c 0))
                 (for i 1 9
                   (unless (conflict? i cell)
                     c++))
                 c))
             (conflict? (solution cell)
               (exists group '(column row b3x3)
                 (exists c (slotValue cell group)->cells
                   (and (neq c cell)
                        (eqv solution c->value)))))
             (solve_cells (cells)
               (cond
                 ((null cells)
                  (return sudoku))
                 (((car cells)->value)
                  (and (not (conflict? (car cells)->value
                                       (car cells)))
                       (solve_cells (cdr cells))))
                 (t
                  (let ((cell (car cells)))
                    (for solution 1 9
                      (unless (conflict? solution cell)
                        cell->value = solution
                        (solve_cells (cdr cells))))
                    cell->value = nil)))))
      
      sudoku->cells = (sort sudoku->cells
                            (genCmpFunction ?key count_possibilities))
      
      (solve_cells sudoku->cells))))

What about the performance?

I ran the new algorithm and the old algorithm on four examples, three from the previous posting 4-1, 4-2, and 4-3, and also on 5-1 above. It turns out that the old algorithm performs 2x to 8x faster than the new for the cases it handles well. In particular, for cases for which the old algorithm solves the puzzle in less than 1/10 of a second, the new algorithm works slower but still solves in less than 1/10 of a second. On the other hand, on the extreme case where old algorithm handles poorly, where the old algorithm requires half a minute to solve the puzzle, the new algorithm is 12x faster.

Performance Measurements
Puzzle	Algorithm 1 (seconds)	Algorithm 2 (seconds)	Comparison < 1.0 is bad (More is Better)
4-1	0.0420	0.0669	1 / 1.59 degradation
4-2	0.0230	0.0830	1 / 3.61 degradation
4-3	0.0030	0.0220	1 / 7.35 degradation
5-1	25.22	2.075	12.154 improvement

Summary

In this series of 5 postings (first four listed below) we've used the SKILL++ Object System to implement a sudoku puzzle solver.

I hope you will find the examples in these posting useful.

Jim Newton

SKILL for the Skilled: Introduction to Classes - Part 1
SKILL for the Skilled: Introduction to Classes - Part 2
SKILL for the Skilled: Introduction to Classes - Part 3
SKILL for the Skilled: Introduction to Classes - Part 4

SKILL for the Skilled: Introduction to Classes -- Part 4

Team SKILL — Mon, 14 Nov 2011 15:00:00 GMT

In several previous postings we introduced the problem of solving the sudoku puzzle.

In Part 1, we saw the rules of sudoku and a brief introduction to the SKILL++ Object System.
In Part 2, we started solving the problem top-down by implementing the top level function SkuSolve and agreeing to fill in all the missing pieces incrementally until the program was complete. We also saw how to use hierarchical class definitions to represent the components representing rows, columns and 3x3 blocks.
In Part 3, we saw how to create and initialize non-trivial instances of SKILL++ classes, and used these techniques to initialize the sudoku board with a given partial solution, ready for solving.
In this posting, Part 4, we'll finally show one possible definition of function SkuFindSolution.

Just for a reminder, here is the definition of the top level function, SkuSolve.

(defun SkuSolve (partial_solution)
  (let ((sudoku (SkuInitialize (SkuNew) partial_solution)))
    (printf "starting with: \n%s\n"
            (SkuPrint sudoku))
    (printf "\nfound solution:\n%s\n"
            (SkuPrint (SkuFindSolution sudoku)))))

We have already seen the definitions of SkuNew, SkuInitialize, and SkuPrint. Now we can take a look at the implementation of SkuFindSolution, the function which actually searches for the sudoku solution.

Solving the sudoku puzzle

The function SkuFindSolution takes an instance of class SkuSudoku (created by SkuNew, and populated by SkuInitialize) and modifies it to find a solution of the sudoku puzzle, assuming one exists.

How does it work?

It basically brute forces its way through the cells in the board, trying every possibility for each cell, from 1 to 9, which does not present an immediate conflict. If no solution exists for a particular cell (i.e., if each choice from 1 to 9 inflicts a conflict), the algorithm backtracks and tries a different guess, until it guesses correctly.

The local function conflict? asks "Does the given digit already exist in the row, column, or 3x3 block which contains the cell?" If not, it is a potentially valid guess. The local function solve_cells takes a list of all the remaining cells which have not yet been visited. Each digit that does not create a conflict is tried. There are three cases in the (cond ...):

If there are no more cells to consider, then we're done; we've found a solution! In this case we don't return from solve_cells, but rather return from (SkuFindSolution ...) thanks to prog/return.
If the cell already has a value in it, skip it because it was given in the puzzle partial solution. Note that this second case refuses to recure if a conflict is found. This means the puzzle has no solution, and recursion terminates, causing SkuFindSolution to return nil.
Otherwise, try all possibilities 1 through 9, skipping conflicts. If the (for ...) loop completes, that means we didn't find a solution for this cell. This happens if we've made an invalid guess in a previous iteration. So we set the cell back to the unsolved state (nil), and backtrack.

(defun SkuFindSolution (partial)
  (prog ()
    (labels ((conflict? (digit cell)
               (exists group '(column row b3x3)
                 (exists c (slotValue cell group)->cells
                   (and (neq c cell)
                        (eqv digit c->value)))))
             (solve_cells (cells)
               (cond
                 ((null cells)
                  (return sudoku))
                 (((car cells)->value)
                   (and (not (conflict? (car cells)->value
                                        (car cells)))
                        (solve_cells (cdr cells))))
                 (t
                  (let ((cell (car cells)))
                    (for solution 1 9
                      (unless (conflict? solution cell)
                        cell->value = solution
                        (solve_cells (cdr cells))))
                    cell->value = nil)))))
      (solve_cells sudoku->cells))))

Testing the program

Now you can test the program by copying the following into the CIWindow which comes from the Sudoku Wikipedia entry.

Sudoku puzzle 4-1
(SkuSolve '((5 3 ? ? 7 ? ? ? ?) (6 ? ? 1 9 5 ? ? ?) (? 9 8 ? ? ? ? 6 ?) (8 ? ? ? 6 ? ? ? 3) (4 ? ? 8 ? 3 ? ? 1) (7 ? ? ? 2 ? ? ? 6) (? 6 ? ? ? ? 2 8 ?) (? ? ? 4 1 9 ? ? 5) (? ? ? ? 8 ? ? 7 9)))

You should get the following result if you entered the code correctly.

starting with: 
+-----------------+
|5|3| | |7| | | | |
|6| | |1|9|5| | | |
| |9|8| | | | |6| |
|8| | | |6| | | |3|
|4| | |8| |3| | |1|
|7| | | |2| | | |6|
| |6| | | | |2|8| |
| | | |4|1|9| | |5|
| | | | |8| | |7|9|
+-----------------+

found solution:
+-----------------+
|5|3|4|6|7|8|9|1|2|
|6|7|2|1|9|5|3|4|8|
|1|9|8|3|4|2|5|6|7|
|8|5|9|7|6|1|4|2|3|
|4|2|6|8|5|3|7|9|1|
|7|1|3|9|2|4|8|5|6|
|9|6|1|5|3|7|2|8|4|
|2|8|7|4|1|9|6|3|5|
|3|4|5|2|8|6|1|7|9|
+-----------------+

If you notice, this algorithm only finds one solution of the sudoku puzzle. In some cases there are multiple solutions, but this algorithm won't find them. For example, the empty puzzle has lots of solutions.

Sudoku puzzle 4-2
(SkuSolve '((? ? ? ? ? ? ? ? ?) (? ? ? ? ? ? ? ? ?) (? ? ? ? ? ? ? ? ?) (? ? ? ? ? ? ? ? ?) (? ? ? ? ? ? ? ? ?) (? ? ? ? ? ? ? ? ?) (? ? ? ? ? ? ? ? ?) (? ? ? ? ? ? ? ? ?) (? ? ? ? ? ? ? ? ?)))

starting with: 
+-----------------+
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
| | | | | | | | | |
+-----------------+

found solution:
+-----------------+
|9|7|8|5|3|1|6|4|2|
|6|4|2|9|7|8|5|3|1|
|5|3|1|6|4|2|9|7|8|
|8|9|7|2|1|4|3|6|5|
|3|6|5|8|9|7|2|1|4|
|2|1|4|3|6|5|8|9|7|
|7|8|9|1|2|3|4|5|6|
|4|5|6|7|8|9|1|2|3|
|1|2|3|4|5|6|7|8|9|
+-----------------+

What if there is no solution?

The SkuSolve function is good at detecting that no solution exists for a particular puzzle.

Sudoku puzzle 4-3
(SkuSolve '((5 3 4 6 7 8 9 1 2) (6 7 2 1 9 5 3 4 8) (1 9 8 3 4 2 5 6 7) (8 5 9 7 6 1 4 2 3) (4 2 6 8 5 3 7 9 1) (7 1 3 9 2 4 8 5 6) (9 6 ? 5 3 7 2 8 4) (1 8 7 4 1 9 6 3 5) (? ? 5 2 8 6 1 7 9)))

starting with: 
+-----+-----+-----+
|5|3|4|6|7|8|9|1|2|
|6|7|2|1|9|5|3|4|8|
|1|9|8|3|4|2|5|6|7|
|8|5|9|7|6|1|4|2|3|
|4|2|6|8|5|3|7|9|1|
|7|1|3|9|2|4|8|5|6|
|9|6| |5|3|7|2|8|4|
|1|8|7|4|1|9|6|3|5|
| | |5|2|8|6|1|7|9|
+-----+-----+-----+


no solution

Summary

In this posting, we have seen a fairly straightforward approach to solving the sudoku puzzle. The solution algorithm is pretty easy because the data structures representing the structure of the board make it easy to ask the questions we need to ask, such as:

Is there a conflict putting a digit into a cell?
Which row, column, and 3x3 block is a given cell in?
Is a given cell pending resolution?

The particular implementation of SkuFindSolution also shows an example of how to use SKILL++ local functions. This usage avoids polluting the global function space.

Preview

In the next posting of SKILL for the Skilled we'll take a look at some shortcomings of this algorithm, particularly in regard to performance.

Jim Newton