Scheme For Enlightenment Part Twenty Three History of Lisp

You should really check out this 1979 paper on the History of LISP. This John McCarthy paper is a first hand account of what problems LISP was designed to solve, and how LISP was developed. This is the guy who designed and built the first LISP. By 1979, LISP was hardly news, so this paper wasn't written to extoll LISPs many virtues. It seems to have been written as an objective history, with as little bias as possible. In any case, it's a great read, and reasonably short.

At the end, John McCarthy talks about what it will take for a language to replace LISP.

LISP will become obsolete when someone makes a more comprehensive language that dominates LISP practically and also gives a clear mathematical semantics to a more comprehensive set of features.

The word obsolete is a funny word. Today, people talk about technlogical products with one of two words. Obsolete and Bleeding Edge. The idea is that either something is brand new and buggy, or it's old and useless. A synonym for Obsolete is Legacy. This term suggests that the bulk of the product has been built. In the case of software, you may tweak it a bit here and there, but for the most part, you leave it alone.

Modern thinking for languages suggests that if a language is the most popular, then everything else is obsolete. This is wrong, of course. Many languages enjoy niche markets. And, rightly so, as some languages are better for some tasks than others. Most languages are better at some task than any other language. The stereotypes for languages are often misleading. Here are some examples: Fortran is great at number crunching. C is good at operating systems. Perl is great at text processing and integrating things together. LISP is good for artificial intelligence research.

In many ways, there are no general purpose computer languages. It depends on what you need. You might write a web site in Perl. But there might be a bit of the site that performs a long running computation, for example to look for a bit of DNA in a database that is a close match of your sample. That bit might be written in C. Another bit tries to match what genes look like to what they do. That might be in LISP. And so on.

From this perspective, a language is obsolete when another language fills the same niche, and is better at it. LISP is good for functional programming. But so are Python and Ruby. So is LISP obsolete? No, LISP has this mathematical nature to it, and will itself be analyzable in ways that Python and Ruby will never be. But isn't Forth a language that might be analyzed in much the same way? Is Forth a better tool than LISP?

Corporate management would prefer fewer languages to many, for fear of not being able to find someone who knows some obscure language. So a language like Java, which has infinite libraries available, is attractive. So now we just have to find people who know all these libraries.

LISP has a relatively small niche. A smaller dialect, like Scheme, is unlikely to take over the whole niche. A large dialect, like Common Lisp, is also unlikely to take over the whole niche. So LISP can either be thought of as always having been obsolete, or will never be obsolete.

Fortran is a language that has undergone many changes. There was Fortran-60, then Fortran 66, then ANSI 77, and so on. The old saying is, "I don't know what language people will be using in the year 2000, but it will be called Fortran". This is even more true for LISP. LISP is a language where it is convenient to build new languages. The new languages don't have to look much like LISP. LISP could replace itself.

Of course if a language is Turing Complete, then it is equivalent to every other language.

Scheme For Enlightenment Part Twenty Two Hackable By Extension

And yet, Guile makes sense when used as an extension language to C(++) applications. The user of a program should not have to modify the source code to that program to extend it a bit, if that can be avoided. The Gimp is written in C, but i'm not not that interested in grappling with such a huge chunk of code to add an image filter. The ability to do that in an extension language would be nicer. That language would have access to the Gimp's power, but would be protected from doing any lasting harm. It also is documented with a limited API of functions to use. (The Gimp uses Guile as an extension language.)

For simple tasks, like configuration (turn this feature on, turn that one off), using Guile is the nuclear bomb to swat a fly approach. This is what makes the Emacs startup file (in lisp) such a bear to deal with. Even Google doesn't always know the answer to what i'd thought were easy issues. Even an xml file is usually too much. But it might be good for allowing the user to add real functionality. Guile, an implementation of Scheme, is a somewhat simpler language than Lisp. It might have been a better choice for Emacs.

The Unix shell allows one to chain utilities together and provide new functionality easily. The shell itself doesn't have to be fast to make this work. It's much the same idea. But the Unix shell is a simple scripting language with relatively low barrier to entry. And yet, i've used the shell to create filter chains to do image manipulation (using pbmplus for a pool of the basic image manipulation commands), to resize an image to the current screen dimensions, changing the gamma to correspond to the monitor, and using the file name as a label in the corner. The simplicity of the Unix shell did not limit the task overmuch. These are things one might expect the Gimp to do. And, in fact, the Gimp has a command line batch mode, with commands in Guile.

So, Scheme might enjoy a niche as an extension language. Is it a very good extension language? Would Python, Java, Forth, or even BASIC be better? It seems that a very simple language, with very low barrier to entry, would be a win.

Scheme For Enlightenment Part Twenty One - Hackable Closures

In the case of Scheme, particular features that make programming easier - and more fun! - are its powerful mechanisms for abstracting parts of programs (closures - see About Closure) and for iteration (see while do).

The Guile Reference Manual defines closure as the ability to remember the local environment when creating a function. The manual goes on to list four uses of closure.

The first corresponds to C's static local variables.

The second, called Shared Persistent Variable corresponds roughly to C's file static variables. This is a variable that is not accessible to the caller, except in the way that the provided functions grant. While i grant that it is handy for a library to have state variables that the caller won't accidently change unexpectedly, many languages have extended this to absurdity. For example, in Java, one is supposed to never touch a class variable directly. One should use accessor functions to set and get values. This is true even if the function is supposed to get data from a database. That means that the class must have a zillion accessor functions to set and get values. The class is huge, the caller's syntax is ponderous. The compilers either must optimize the calls away, or leave the extra code in. It buys neither the class nor the caller anything of value. In C, Shared Persistent Variables are supported, and they tend to get used as needed, without being elevated to the level of the Holy Grail.

Third, The Callback Closure Problem. The argument is that with closures in Scheme, a call back function can be registered that has all the environment stuff it needs. The callee doesn't need to know all the arguments and such, it just has a function to call, and calls it.

C supports callback functions. They have more syntax associated with them, but that's mostly because C is a statically typed language. In my opinion, the library is where the complicated stuff should be. The caller shouldn't have to build a call back function factory to simplify the library. The library should do as much heavy lifting as possible. And, i've never found this bit of library creation to be error prone, frequent or difficult.

Function factories need to be addressed in more detail. This is as good a place as any. Let's say that one needs a serial number generator. Each number is unique. A function with internal persistent state can simply have a counter that can be incremented, and the new number can be returned. One nice thing in Scheme is that the number can be said to never overflow. Scheme makes the number bigger if needed. But let's say that you need two serial number sequences, one for each of two products. In Scheme, one makes a serial number function factory. Each returned object can be used to generate a sequence that is independent from every other sequence. Can this be done in C? You bet. The difference is that in C, what you do is return a token that the sequence generator uses to determine which sequence is desired. So, the caller must pass a parameter to the generator, rather than have a function that can be called with no parameter. The caller still must remember the function (pointer), which is it's own parameter. I just don't see this as a big deal.

Fourth, Object Orientation. Object and method encapsulation can be a good thing. C libraries can do this. But there isn't any syntax specifically there to support it. Now, having a language that provides object oriented syntax can be a good thing. Objective C is an example of a language that does this without going over the top, as IMO, was done in C++ and Java. And mixing C style code with object oriented code is very natural. Many libraries make sense if written in an object oriented manner. Objective C allows calls to such libraries at will. Even inheritance can be supported in C. It's just that supporting virtual functions takes more work than most C programmers are willing to do, so very few C applications do it. I've only written code that way perhaps twice in a quarter century of C. So only those functions that really needed it also paid the performance penalty required.

In C, Object Orientation can be achieved by convention, rather than be strictly enforced by syntax. So, the maintainer of a chunk of such C code does not have syntax to quickly prove that, for example, only these functions make any changes to this variable. Such things are good. Because if one can limit the scope of where to look for behavior, there is less to look at. Remember that humans are slow. But C has scope rules. And even if some convention is violated in the code, one should be able to spot C's scope rules. For example, i use the keyword static for file global variables often. That means that the text editor can be used to quickly search for all uses of that variable. In C, one knows that this variable is only accessible from that point to the end of the file. Less, if there are blocks where variables are shadowed by local variables. I essentially never intentionally shadow global variables with locals, as it can cause confusion later.

So, the argument is that you can try little bits of Scheme easily. I recall doing that in C. What i was trying to do is figure out the exact semantics of the C language. The White book, The C Language, talks about what the language does, but isn't very precise. So i'd write something quick, like

    for (i = 0; i < 5; i++) {
        call_something(i);
    }

compile it, and step through it with a debugger. I'd also ask the compiler for the assembly language to see what it really did. I had the good fortune to have written ten or twenty thousand lines of PDP-11 assembly language, and had access to Unix running on a PDP-11 with the language writer's own compiler - the Ritchie C compiler. At the time, this was the gold standard for how C should behave. This gave me insights not only into what the exact semantics were, but also why Dennis Ritchie designed them that way. No tricks like that are available for Scheme. The best you might do is read the Scheme standard - which at least is short. A C standard now exists. However, for real understanding, the translation to assembly can hardly be matched.

Scheme For Enlightenment Part twenty - Scheme Is Hackable

Having written this much English about Scheme, i now feel minimally competent to address one of the things that really bothers me about the Guile Reference Manual. Section 4.6.2 is entitled Why Scheme is more hackable than C. This hasn't been my experience, so i'll take the issues point by point, and be as fair as i can in my infinite bias.

* They [interpreted languages] lend themselves to rapid and experimental development cycles, owing usually to a combination of their interpretability and the integrated development environment in which they are used.

There are C interpreters. They are usually sold as debuggers. C compiles very fast. On a 1987 Macintosh II (about 1 MIPS) the Think C (then Lightspeed C) compiler could scan code at effectively 70,000 lines per minute. And, since it only needed to recompile modules that changed (perhaps due to include files), it typically only needed to recompile a few hundred to a thousand lines, taking less than a second. Further, the integrated debugger remembered break points, variable watches and so on, so a single key stroke compiled your code, ran it, and stopped at an interesting breakpoint in seconds. C interpreters often get to this point later, because the interpreter runs code much slower. Interpretive systems like Scheme, Perl, and so on have little to add to this. Unless, while stepping through your code, you see an error, modify your code and continue stepping. To date, the only language system i've used that supported this was C (using a C interpreter). And Guile performs a compile, though without saving it to disk. It can get away with this because compiles are so fast. The interesting bit is that the user doesn't have to do something special to make it happen. The user is very slow compared to the computer, so compiles are invisible. But even Emacs with gcc and gdb is an environment that is integrated enough to be quick. Emacs has a compile command that puts the errors in another window, and can quickly move the cursor to some line that caused an error or warning. It's very fast.

* They [Scheme and other languages] free developers from some of the low level bookkeeping tasks associated with C programming, notably memory management.

This is true. At least this isn't a totally lame argument. It is unfortunate, but at least at the moment, the human is capable of managing memory such that the overall performance is much higher than machines, despite enormous research into automatic memory management (mostly garbage collection). Explicit memory management is faster but more error prone. But Scheme replaces that task with the bookkeeping of managing parenthesis. So far, this one misfeature seems much worse than the syntax headaches that C presents. There are other handy abstractions, but unfortunately, this very ripe area is left unpursued.

* They provide high level features such as container objects and exception handling that make common programming tasks easier.

It may be that C has simpler (and less flexible) scope rules than Scheme. Learning Scheme's scope rules may simply take longer. The most challenging limitations in C's scope rules show up when writing libraries. If a library is viewed as an object class, then the library will want it's own class variables. The library must choose some names, and some could conflict with the names used in other libraries. But C's names are no longer limited to 7 characters, as they were on the PDP-11 with Ritchie's original C compiler. And name conflicts can be limited by using naming conventions. These conventions can be broken when it makes sense, so C retains flexibility. The Java convention for naming classes tries to make name conflicts impossible world wide. It's a very ugly solution. Container objects and exception handling can certainly be done in C. The resulting syntax looks much as it does in object oriented languages. One can use it if they want to. I personally don't find exception handling, that is try and catch, to be easier in most cases. It can get in the way really good error handling, that matches the problem at hand. My highest praise for try and catch is that novice programmers may be encouraged to think about error handling, at least at some minimal level. But it's both complicated and minimal. In the few cases where it is needed, often a simple setjmp/longjmp setup is often sufficient.

Additionally, library writing is relatively rare. Most code is not easily reused. Most code is designed to solve the problem at hand. Certainly, hacking (playing around with some ideas) is not library writing. So, languages with no scope rules, like BASIC, are significantly more hackable than languages with strict scope rules like Scheme. That should sting, being compared to BASIC and coming up short, even on one point of many. But compared to BASIC, essentially all languages are unhackable.

Scheme For Enlightenment Part Nineteen - Ackermann Cached

So, (a 3 13) fails on some machines. (a 3 14) fails on others. I got to thinking. This function is supposed to eventually return. And it does this by calling itself with smaller numbers. And it seems to go over the same space with high frequency. So, if the function was written to remember answers that it previously computed, it could avoid lots of redundant calls. It might be faster. It's a classic trade of memory for time. How much memory, and how much time?

#include <stdio.h>
#include <stdlib.h>

#define A 5
#define B 10000000 /* m gets really big fast */
int acks[A][B]; /* (A * B * sizeof(int) bytes.), eg 200 MB. */

void init_acks()
{
    register int i;
    register int j;

    for (i = 0; i < A; i++) {
 for (j = 0; j < B; j++) {
     acks[i][j] = -1;
 }
    }
}

void setacks(int n, int m, int v)
{
    if (v < 0) {
 return;  /* Don't store bad data. */
    }
    if (n >= 0 && m >= 0 && n < A && m < B) {
 acks[n][m] = v;
    }
}

int chkacks(int n, int m)
{
    if (n >= 0 && m >= 0 && n < A && m < B) {
 return acks[n][m];
    } else {
 return -1;
    }
}

int ack(int n, int m)
{
    register int x;
    register int y;

    if (n == 0) {
 return m + 1;
    }
    x = chkacks(n, m);
    if (x >= 0) {
 return x;
    }
    if (m == 0) {
 x = ack(n - 1, 1);
 setacks(n - 1, 1, x);
 return x;
    } else {
 x = ack(n, m - 1);
 setacks(n, m - 1, x);
 y = ack(n - 1, x);
 setacks(n - 1, x, y);
 return y;
    }
}

int main(int argc, char *argv[])
{
    register int n;
    register int m;

    init_acks();
    if (argc == 3) {
        n = atoi(argv[1]);
        m = atoi(argv[2]);
    } else {
        printf("Usage: ack n m\nwhere n and m are small integers.\n");
        exit(0);
    }
    printf("Answer = %d\n", ack(n, m));
    return 0;
}

You have to call init_acks() before using it. The Ackermann function is called ack(). And this function is good for (a 3 16), assuming you have 200 MB of RAM for the array. It returns the answer very quickly. However, (a 3 17) doesn't work. It gets a stack crash. That's because the cache isn't large enough, and this code reverts to deep recursion. This one can also compute (a 4 1), but not (a 4 2). Worse, 1.5 GB of RAM (which happens to be handy) doesn't get you to (a 3 17). What on Earth is going on?

The Little Schemer chapter nine is available on line. It's postscript, but i was able to read it online. It's an interesting read. And they mention this function. They don't really explain it. I like things spelled out for me. According to the Wikipedia article, Mathemeticians spent a very long time on this. I'm a limited mortal. I don't have time like that. The joke is that the Ackermann function's compute time goes up as 2 ^ 2 ... ^2, where the number of raisings to powers is related to the input values. The result also goes up pretty fast. So (a 3 17) might not fit in a 32 bit integer. And no 32 bit machine will have stack space or cache space to cope anyway.

Why bring this up? Well, at first glance, it looks alot like the change counting function. It's worthwhile to see how they're different, to get an idea of the run time of functions. This brick wall function is not computable for even moderate input values in practice.

Scheme For Enlightenment Part Eighteen - Ackermann

The Ackermann function is often used as a benchmark. It beats the crap out of your recursion system. But even with that caveat, it isn't a very good benchmark. Mainly, it's tough to scale it for reasonable run time for various systems. You can't just feed it new arguments and extrapolate times, though it could be put into a simple loop. The function is pretty simple. It only uses addition and subtraction. It has surprising runtime. There are tons of implementations out there. Here's one.

(define (a n m)
    (if (eqv? n 0) (+ m 1)
  (if (eqv? m 0)
      (a (- n 1) 1)
      (a (- n 1) (a n (- m 1))))))

The function a takes two arguments, n and m. If n is zero, it returns m + 1. This is the base condition, and eventually calls will be made to this ground state. If n isn't zero, then if m is zero, it calls itself with n - 1 and 1. Finally, if both n and m are not zero, it returns a funny nested call. It calls itself with n - 1, but the second argument is the return value of another call to itself. This last bit is interesting, as the return value of the Ackermann function can be really big. So it isn't clear that this function will ever return. It does. Eventually. If your machine is big enough. And if your Universe has been around long enough.

If you explore this function, you find that it seems to hit a brick wall. The enormous difference in speed between LispMe on the Palm and C on the desktop (146,000x) amounts to essentially nothing. You run into this wall right around (a 3 13).

int ack(int n, int m)
{
    if (n == 0) {
        return ++m;
    }
    if (m == 0) {
        return ack(n - 1, 1);
    } else {
        return ack(n - 1, ack(n, m - 1));
    }
}

So if you feed this C script arguments like (a 1 1), (a 1 13), (a 2 1), (a 2 13), (a 3 1), and even (a 3 11), you get answers quickly (less than 20 seconds). The argument (a 3 12) takes more like a minute, and (a 3 13) takes 3 1/2 minutes. And yet (a 3 14) stubbornly refuses to run. What i get is a stack crash, but only after quite some time goes by.

The Wikipedia article explains what's going on. While you read that, i'll write tomorrow's installment.

Scheme For Enlightenment Part Seventeen - C Change

So the next idea is to see what this looks like in C. I've said before that the Scheme version is fast enough. So this exercise is pointless, meaning that it is an exercise.

It's really handy to pass part of the list and use recursion. Can this be done in C without using a linked list library and making copies of lists? Yes. One might use an array, pass a pointer or an index potentially part way into the array, use a handy delimiter so we know when to stop. No need to make copies. The sub lists end at the same place as the full list. Arrays are dumb lists, but are good enough for this sort of thing.

But the recursive structure is still handy, so we'll continue using it.

#include <stdio.h>
#include <stdlib.h>

/* -1 for end of list of coins */
int coins[] = { 50, 20, 10, 5, 2, 1, -1 };

int cc(int am, int c[]) {
  if (am == 0) {
    return 1;
  } else {
    if (am < 0 || c[0] == -1) {
      return 0;
    } else {
      return cc(am - c[0], &c[0]) + cc(am, &c[1]);
    }
  }
}

int main(int argc, char *argv[]) {
  printf("%d\n", cc(atoi(argv[1]), coins));
  return 0;
}

This version works. But i wondered out loud what it might look like using a more Scheme-like syntax. I'm pretty sure no one (sane) would write it this way. The question mark operator isn't very commonly used. Most C programmers think nested comma operators are hard to read. They are. And yet, formulated this way you can still see what is returned fairly quickly. It's whatever is right after a '?', or the last colon.

/* -1 for end of list of coins */
int coins[] = { 50, 20, 10, 5, 2, 1, -1 };

int cc(int am, int c[]) {
  return (am == 0) ? 1 :
    (am < 0 || c[0] == -1) ? 0 :
      cc(am - c[0], &c[0]) +
      cc(am, &c[1]);
}

Again, the original LispMe version for comparison. I'm still trying to wrap my head around how to spot the Scheme return values. As near as i can tell, there's no way around matching the parenthesis for the if operators. The first one is easy. The second one has triple nested parenthesis. And the else clause of the second if starts with addition. The result of the addition is also possibly returned. I was hoping that the Emacs indention would give visual clues. It does. It says that the second if is nested as a clause of the first. It says that the addition operator is a clause of the second if, and the two cc calls are part of the addition. Look sharp for the two constants that are the first clauses of the if's. They seem to just hang there doing nothing. These can be returned.

; count change
(define coins '(50 20 10 5 2 1))

(define (cc am c)
  (if (eq? am 0) 1
      (if (or (< am 0) (null? c)) 0
   (+ (cc (- am (car c)) c)
      (cc am (cdr c))))))

Scheme For Enlightenment Part Sixteen - Time For Debugging

In Guile, i ran my new example with traces set on addition (+) and on the function, cc. (LispMe supports traces. But Guile's output can be trivially pasted into a text editor for these posts.) For a simple example, i asked for the coins needed for 2 cents.

(trace cc)
(trace +)
(cc 2 coins)

[cc 2 (50 25 10 5 1)]
[cc 2 (25 10 5 1)]
[cc 2 (10 5 1)]
[cc 2 (5 1)]
[cc 2 (1)]
|  [cc 1 (1)]
|  |  [cc 0 (1)]
|  |  [cc 0 ()]
|  |  0
|  [+ 1 0]
|  1
[+ 1 1]
2
2

This says that cc was called with 2 cents, and the list of coins. There were no 50's, so it called itself again without that in the list. And so on until just pennies were represented. It then called itself with one penny subtracted. Then called itself with both pennies subtracted. When nothing is left in the coin list, it returns zero. That caller adds one to that zero and returns it (one). That caller's caller adds one to this one, getting two. Two is returned. Finally, 2 coins is the answer.

Unlike the original script, this one only calls itself once. So, the time is more or less linear with the amount of money one starts with. It will never take much time, even on the Palm, even for largish input. The original script has two calls and exhibits some sort of exponential behavior. Two calls means that it has to branch left and right down some tree at each call level. One call becomes two, which becomes four, which becomes eight, and so on. At twenty calls deep, it's a million branches. Two self referencing calls. That's something to look for.

The trace also shows that the caller has something to do after it calls itself. That means that no tail recursion optimization is available to the language execution system. So, one might expect a stack overflow if one feeds it ten dollars (1000 cents). However, if one adds 100, 500 and 1000 (a dollar, a five dollar, and ten dollar bill) to the list, it turns out that 1000 cents isn't a big deal. The recursion depth has to do with the number of units counted in the answer. As long as that is small, there is no danger. Yet, it might still be worthwhile to write either a tail recursive version, or a straight looping version.

I've no idea how i might write a looping version. It's really handy to do the recursive call with a subset of the coins list. Scheme makes a copy of the list, so the original remains undamaged. I'm sure it can be done, the question is how ugly will it get? This is the kind of enlightenment i'm looking for, by the way.

If we do a trace on the original, we get a longer trace. At first, it subtracts the coins (dollars) until it gets below the amount (2). You can see that cc returns 1 for the first time. That's when it tried the $2 bill. Then it tries a $1 bill, and it needs a second bill to add up to $2. It returns one for the 2 singles, and returns this a bit until it gets to add one for the single $2 bill. It adds zero for other failures, and finally ends up with 2. Traces for larger numbers are much, much longer. But following them shows where it calls itself for the left and right recursive calls. Further, you get a feeling for how the function takes time proportional to maybe n^2, rather than the fully linear function i wrote. More on this idea later.

(trace cc)
(trace +)
(cc 2 coins)

[cc 2 (50 20 10 5 2 1)]
|  [cc -48 (50 20 10 5 2 1)]
|  0
|  [cc 2 (20 10 5 2 1)]
|  |  [cc -18 (20 10 5 2 1)]
|  |  0
|  |  [cc 2 (10 5 2 1)]
|  |  |  [cc -8 (10 5 2 1)]
|  |  |  0
|  |  |  [cc 2 (5 2 1)]
|  |  |  |  [cc -3 (5 2 1)]
|  |  |  |  0
|  |  |  |  [cc 2 (2 1)]
|  |  |  |  |  [cc 0 (2 1)]
|  |  |  |  |  1
|  |  |  |  |  [cc 2 (1)]
|  |  |  |  |  |  [cc 1 (1)]
|  |  |  |  |  |  |  [cc 0 (1)]
|  |  |  |  |  |  |  1
|  |  |  |  |  |  |  [cc 1 ()]
|  |  |  |  |  |  |  0
|  |  |  |  |  |  [+ 1 0]
|  |  |  |  |  |  1
|  |  |  |  |  |  [cc 2 ()]
|  |  |  |  |  |  0
|  |  |  |  |  [+ 1 0]
|  |  |  |  |  1
|  |  |  |  [+ 1 1]
|  |  |  |  2
|  |  |  [+ 0 2]
|  |  |  2
|  |  [+ 0 2]
|  |  2
|  [+ 0 2]
|  2
[+ 0 2]
2
2

Scheme For Enlightenment Part Fifteen - Time Is Change

So this change counting thing turns out to be a benchmark, complete with times run under various hardware on LispMe, MIT Scheme and PocketC (which is not Scheme, or really even C, but runs on a Palm). So i ran it on a 2.8 GHz Pentium 4 under Guile 1.8, and it took 0.156 seconds. Startup for Guile is around 0.028 seconds, so the run time was around 0.128 seconds, which doesn't tell me much. This benchmark is way too short for a modern desktop. I already knew that this P4 was faster than any of the hardware listed. I'd like to know how long other programs might take. The run time on the desktop was so short, one can't really extrapolate to other circumstances with much confidence. And i know nothing about what this program does or how it does it. So i ran it on the Handspring Visor Platinum in LispMe. I needed some way to get the time for the benchmark, so i added this code to the script, set the auto-off on the Palm to thirty minutes (1800 seconds) and ran it saying (doit).

(define (doit)
 (define tk (current-ticks))
 (cc 100 coins)
 (ticks-since tk))

I also ran (ticks-per-sec) to find out that my Palm counts time in hundredths of seconds. All this time stuff is LispMe specific, and i can divide by 100 in my head, so i didn't bother having LispMe do that. I should note that the Palm is otherwise useless when running long programs. I don't care that much that my rechargeable batteries are draining a little quicker than usual. There is no A/C adapter, so there are limits to run time. For example, no overnight runs.

Anyway, it returned 26296, which is 262.96 seconds. That makes my Visor faster than a Palm IIIc, which i already knew. It's not as fast as a Palm Tungsten T3, which might be a newer Arm based Palm. That would make sense too. From the desktop timing above, one might expect scripts to run anywhere from 1600 to 2000 times faster on a desktop than on a Palm. That means that even scripts that seem to take no time at all on the desktop may be impractical on the Palm. One second is half an hour.

My original confusion had to do with my expectations and not (yet) reading the manual. I thought that this script made change. It has many of the elements that i'd expected. The cryptic comment says it counts change. It has a list of dollars or coin values. The function takes an amount. It does some list walking, with car and cdr, checking for the end of the list with null?. It subtracts. But what would a function look like that does what i thought this one does?

; count change. How many coins does it take?
(define coins '(50 25 10 5 1))
(define (cc am c)
  (if (null? c) 0
      (if (< (- am (car c)) 0)
   (cc am (cdr c))
   (+ 1 (cc (- am (car c)) c)))))

For reference, here's the original:

; count change
(define coins '(50 20 10 5 2 1))
;(define coins '(50 25 10 5 1))
(define (cc am c)
  (if (eq? am 0) 1
      (if (or (< am 0) (null? c)) 0
   (+ (cc (- am (car c)) c)
      (cc am (cdr c))))))

They are the same number of lines. Both have two nested if's. They both use car, cdr and null? to walk the list. They both do a bit of the work and call themselves to finish it. They both use addition to count. They both use subtraction to mark that a coin has been used. So how can you tell that it does one thing instead of another? At the moment, it looks like one must step through them to see what each one does.

Scheme For Enlightenment Part Fourteen - Change Is Good

My investigations of Scheme started with LispMe, on the Palm Pilot. One might argue that, without a keyboard, the Palm is an awful environment on which to do programming. And, you'd be right in some ways. Scheme can be a terse language, so my eight words a minute text entry isn't so terrible. LispMe does feature an editor that does parenthesis matching. That helps. Part of the draw of the platform is that it runs on two AAA batteries, and fits in my shirt pocket. So, i can goof around with it whenever i have a few minutes. My Palm is about ten thousand times slower than a desktop. One might expect that this is a limitation. It doesn't seem to be. Lacking a fan or disk drive, the Palm makes no noise unless i ask it to. I'd like a laptop that makes no noise and runs on AA batteries. That's what attracted me to the Nokia.

Once the basic syntax was mastered, i looked around for example code to try. A subdirectory of the LispMe documentation has sample programs. One example that i did not understand in the slightest is called change.lispme.

; count change
(define coins '(50 20 10 5 2 1))
;(define coins '(50 25 10 5 1))
(define (cc am c)
  (if (eq? am 0) 1
      (if (or (< am 0) (null? c)) 0
   (+ (cc (- am (car c)) c)
      (cc am (cdr c))))))

It took some time to figure out how to run it. It takes two arguments. The first argument, am, is compared to zero, and is involved in subtraction. So it's a number. The second argument, c, gets passed to null?, car and cdr. That must be a list. A list, coins, is defined, so try it. I figured it must be a program that counts change, like the comment says.

I'd written something like that in BASIC a million years ago. You feed it 7 cents, and it tells you that you need a nickel and two pennies. But this function returns a single value. So perhaps it counts the coins you need. But when you call this with

(cc 7 coins)

it returns 6, not 3. I figured it was broken, and moved on. But eventually, i finished reading the manual from end to end. (Raise your had if you read manuals from end to end.) In the section entitled Sample programs, this program is introduced as a benchmark. You are supposed to call it with

(cc 100 coins)

The value is described as How many ways are there to change 100$ into 1, 2, 5, 10, 20, 50 dollar bills. Now i'm even more confused. One can use seven singles or one five and two singles. That's 2 ways to change $7, not 6. I have no idea what it's doing.

Scheme For Enlightenment Part Thirteen - Eliminate Redundant Specification

Since the C version did not redundantly list paired states, this is an experiment to do this in scheme. Refer to part eleven for the support code.

#!/usr/bin/guile -s
!#
;;; Color the New England states in 4 colors.
(load "amb.scm")

(define (choose-color)
  (amb 'red 'green 'blue 'white))

(define (color-new-england)  ; Choose colors for each state.
  (let ((me (choose-color))  ; MainE
 (ma (choose-color))  ; MAssachuesetts
 (ct (choose-color))  ; ConnecticuT
 (ri (choose-color))  ; Rhode Island
 (nh (choose-color))  ; New Hampshire
 (vt (choose-color))) ; VermonT

    ;; Construct the adjacency list for each state:
    ;; the states' name, its color, the list of its neighbors' colors.
    (let ((Connecticut (list 'Connecticut ct (list ri)))
   (Maine (list 'Maine me (list nh)))
   (Massachuesetts (list 'Massachuesetts ma (list ct)))
   (NewHampshire (list 'NewHampshire nh (list ma vt)))
   (RhodeIsland (list 'RhodeIsland ri (list ma)))
   (Vermont (list 'Vermont vt (list ma))))

      (let ((states (list Connecticut Maine Massachuesetts
     NewHampshire RhodeIsland Vermont)))

 ;; A state's color can't be the same as any of its neighbors.
 (for-each (lambda (c)
      (assert (not (memq (cadr c)
           (caddr c)))))
    states)

 ;; Output the color assignment.
 (for-each (lambda (c)
      (display (car c))
      (display " ")
      (display (cadr c))
      (newline))
    states)))))

(color-new-england) ; run the function to find an answer.

This generates the same answer, but only marginally quicker, if at all. The startup time for Guile dominates, the any time saved is difficult to measure. So i made this same modification to a version with 15 east coast states. This also produced the same answer. And it produced a slow down of a factor of 1.02. The modification was trivial. It isn't a change to the algorithm, just the data. Removing the over specification of the problem led to getting an answer a little slower. Chances are, the order in which the decision tree was searched was altered. That lead to the same answer, but only after a few more failures were considered.

It's too bad. I was hoping for a small speed up. My idea was that less work would have to be done for each decision. Oh well.

Scheme For Enlightenment Part Twelve - Quicker Colors

We last left our hero coloring states on a map. This time, a new version is written in C, but not a translation of the Scheme code. The Scheme version for the entire lower US is 150 lines of code. Much of this is representations of the states and which is near which. The C version for the same lower states is 187 lines long. A similar amount is the data, with the remaining extra code, some 42 lines, comprising more logic. But this isn't terribly fair to C. In Scheme, the data and the program are much more mixed. The data is executed. States become functions, and so on. In the C version, the data and the data structures are just there. And it's also not fair to Scheme. The C version has sort of two copies of the states, rather than three. But the new C version has the feature that it finishes exucution in a reasonable amount of time. Less than a second. Here it is.

#include 
/* Color the New England states in 4 colors. */

#ifndef TRUE
#define TRUE 1
#endif
#ifndef FALSE
#define FALSE 0
#endif

char *colors[] = { 
#define UNDEF -1
    "red",
#define RED 0
    "green",
#define GREEN 1
    "blue",
#define BLUE 2
    "white",
#define WHITE 3
    NULL
};

#define NEIGHBORS 8  /* Max neighboring states. */
struct state {
    int color;
    int neighbors[NEIGHBORS];
    char *name;
};

#define UD -1   /* UNDEF */

/* Adjacency is only checked once.
 * So MA is next to CT, but CT doesn't also check for MA.
 * Later states refer to earlier states only.
 */
struct state states[] = {
#define AL 0
    { UNDEF, { UD, UD, UD, UD, UD, UD, UD, UD }, "Alabama" },
#define AZ 1
    { UNDEF, { UD, UD, UD, UD, UD, UD, UD, UD }, "Arizona" },
#define AR 2
    { UNDEF, { UD, UD, UD, UD, UD, UD, UD, UD }, "Arkansas" },
#define CA 3
    { UNDEF, { UD, UD, UD, UD, UD, UD, UD, UD }, "California" },
#define CO 4
    { UNDEF, { UD, UD, UD, UD, UD, UD, UD, UD }, "Colorado" },
#define CT 5
    { UNDEF, { UD, UD, UD, UD, UD, UD, UD, UD }, "Connecticut" },
#define DE 6
    { UNDEF, { UD, UD, UD, UD, UD, UD, UD, UD }, "Delaware" },
#define DC 7
    { UNDEF, { UD, UD, UD, UD, UD, UD, UD, UD }, "DistrictOfColumbia" },
#define FL 8
    { UNDEF, { AL, UD, UD, UD, UD, UD, UD, UD }, "Florida" },
#define GA 9
    { UNDEF, { FL, AL, UD, UD, UD, UD, UD, UD }, "Georgia" },
#define ID 10
    { UNDEF, { UD, UD, UD, UD, UD, UD, UD, UD }, "Idaho" },
#define IL 11
    { UNDEF, { UD, UD, UD, UD, UD, UD, UD, UD }, "Illinois" },
#define IN 12
    { UNDEF, { IL, UD, UD, UD, UD, UD, UD, UD }, "Indiana" },
#define IA 13
    { UNDEF, { IL, UD, UD, UD, UD, UD, UD, UD }, "Iowa" },
#define KS 14
    { UNDEF, { CO, UD, UD, UD, UD, UD, UD, UD }, "Kansas" },
#define KY 15
    { UNDEF, { IL, IN, UD, UD, UD, UD, UD, UD }, "Kentucky" },
#define LA 16
    { UNDEF, { AR, UD, UD, UD, UD, UD, UD, UD }, "Louisiana" },
#define ME 17
    { UNDEF, { UD, UD, UD, UD, UD, UD, UD, UD }, "Maine" },
#define MD 18
    { UNDEF, { DC, DE, UD, UD, UD, UD, UD, UD }, "Maryland" },
#define MA 19
    { UNDEF, { CT, UD, UD, UD, UD, UD, UD, UD }, "Massachusetts" },
#define MI 20
    { UNDEF, { IN, IL, UD, UD, UD, UD, UD, UD }, "Michigan" },
#define MN 21
    { UNDEF, { IA, UD, UD, UD, UD, UD, UD, UD }, "Minnesota" },
#define MS 22
    { UNDEF, { LA, AR, AL, FL, UD, UD, UD, UD }, "Mississippi" },
#define MO 23
    { UNDEF, { AR, KS, IA, IL, KY, UD, UD, UD }, "Missouri" },
#define MT 24
    { UNDEF, { ID, UD, UD, UD, UD, UD, UD, UD }, "Montana" },
#define NE 25
    { UNDEF, { KS, CO, IA, MO, UD, UD, UD, UD }, "Nebraska" },
#define NV 26
    { UNDEF, { CA, ID, AZ, UD, UD, UD, UD, UD }, "Nevada" },
#define NH 27
    { UNDEF, { MA, ME, UD, UD, UD, UD, UD, UD }, "NewHampshire" },
#define NJ 28
    { UNDEF, { DE, UD, UD, UD, UD, UD, UD, UD }, "NewJersey" },
#define NM 29
    { UNDEF, { AZ, CO, UD, UD, UD, UD, UD, UD }, "NewMexico" },
#define NY 30
    { UNDEF, { CT, MA, NJ, UD, UD, UD, UD, UD }, "NewYork" },
#define NC 31
    { UNDEF, { GA, UD, UD, UD, UD, UD, UD, UD }, "NorthCarolina" },
#define ND 32
    { UNDEF, { MN, MT, UD, UD, UD, UD, UD, UD }, "NorthDakota" },
#define OH 33
    { UNDEF, { KY, IN, MI, UD, UD, UD, UD, UD }, "Ohio" },
#define OK 34
    { UNDEF, { NM, CO, KS, MO, AR, UD, UD, UD }, "Oklahoma" },
#define ORG 35
    { UNDEF, { CA, ID, NV, UD, UD, UD, UD, UD }, "Oregon" },
#define PA 36
    { UNDEF, { DE, OH, NY, NJ, UD, UD, UD, UD }, "Pennsylvania" },
#define RI 37
    { UNDEF, { CT, MA, UD, UD, UD, UD, UD, UD }, "RhodeIsland" },
#define SC 38
    { UNDEF, { GA, NC, UD, UD, UD, UD, UD, UD }, "SouthCarolina" },
#define SD 39
    { UNDEF, { ND, MN, IA, NE, MT, UD, UD, UD }, "SouthDakota" },
#define TN 40
    { UNDEF, { NC, GA, AL, MS, AR, MO, KY, UD }, "Tennessee" },
#define TX 41
    { UNDEF, { NM, OK, AR, LA, UD, UD, UD, UD }, "Texas" },
#define UT 42
    { UNDEF, { AZ, NV, ID, CO, UD, UD, UD, UD }, "Utah" },
#define VT 43
    { UNDEF, { MA, NH, NY, UD, UD, UD, UD, UD }, "Vermont" },
#define VA 44
    { UNDEF, { NC, TN, KY, DE, DC, MD, UD, UD }, "Virginia" },
#define WA 45
    { UNDEF, { ID, UD, UD, UD, UD, UD, UD, UD }, "Washington" },
#define WV 46
    { UNDEF, { VA, KY, OH, PA, MD, UD, UD, UD }, "WestVirginia" },
#define WI 47
    { UNDEF, { MI, IL, IA, MN, UD, UD, UD, UD }, "Wisconsin" },
#define WY 48
    { UNDEF, { CO, UT, ID, MT, ND, SD, NE, UD }, "Wyoming" },
};

/* Does this state have any adjacent states of the same color? */
int
adjstate(int st)
{
    int adj;

    for (adj = 0; adj < NEIGHBORS; adj++) {
 if (states[st].neighbors[adj] != UNDEF &&
     states[st].color == states[states[st].neighbors[adj]].color) {
     return TRUE;
 }
    }
    return FALSE;
}

/* Return TRUE if found a color that works. */
int check_states(int st)
{
    int color;

    /* Start color where you left off.  UNDEF + 1 => RED. */
    for (color = states[st].color + 1; color <= WHITE; color++) {
 states[st].color = color;
 if (!adjstate(st)) {
     return TRUE;
 }
    }
    return FALSE;
}

int main()
{
    int st;
    long rework = 0;  /* stats: Rework=158727 */

    st = 0;
    while (st <= WY) {
 if (!check_states(st)) { /* If the state doesn't work */
     states[st].color = UNDEF; /* revert */
     st--;  /* Try the next state again. */
     rework++;
 } else {
     st++;
 }
    }
    /* Print the answers. */
    for (st = 0; st <= WY; st++) {
 printf("%s = %s\n", states[st].name, colors[states[st].color]);
    }
    printf("Rework=%ld\n", rework);
    return 0;
}

There are some warts i've left in. It didn't turn out that i needed defines for the color table indexes. All i needed to know was the total number of colors, which i could have gotten from sizeof. This would allow the number of colors to be changed, but also would shorten the program by a few lines. In the structure for the states, i could have used a variable length neighboring state list. This would likely increase the number of lines of code a little, but i wouldn't have to know the length of the largest list before starting. In fact, the longest list has 7, not 8 entries. I didn't bother to trim the list. I might decide to add Canada's provinces, for example. That could possibly increase the longest list. The adjstate function is only used once, and can be inserted where it is called. That would also shorten the program. But breaking it out as a function no longer implies a speed penalty, as the compiler can be asked to do this inlining automatically. And having it be a function essentially documents what that chunk of code does.

One difference in the data between Scheme and C is the list of adjacent states. If New Hampshire is next to Vermont, then Vermont is next to New Hampshire. So this relationship only needs to be spelled out once. If it is spelled out twice, it will be checked twice. If it is checked twice, then perhaps the decision tree is larger. In the C version, the state indexes, ME is Maine, and so on, are not defined until the state is defined. That means that no state can refer to adjacent states that come later in the list. That means that i was able to use the C compiler to reduce the list. The original list was the redundant one that i crafted from a map for Scheme. But since TN for Tennessee wasn't defined, the compiler complained when i attempted to use it as an adjacent state to Alabama. No problem. Just change the entry to UD (Undef), and move on. So, you'll see many more adjacent states at the end of the list. For example, Tennessee includes AL for Alabama when it shows up later.

The check_states function assigns a color to a state, and checks to see if any neighbors have that color. The color assigned is the next color available. If there was no color, it starts at the begining of the color list. But it potentially checks all colors. If it finds a color that none of the neighbors have, it stops and returns TRUE. If no colors work for that state, it returns FALSE.

The real difference in code between the Scheme version and the C version is in main. The while loop really traverses the decision tree. And it does it by pruning the tree as it goes. It considers one state at a time, starting with exactly one state. The while loop in main does this wierd walk up and down the list of states. The list starts with all state colors assigned UNDEF. And the first state that is checked is passed to check_states, which assigns it red, checks to see that this works, and returns TRUE. Even in Alabama had any adjacent states listed, these states would all have their color listed as UNDEF, so TRUE would be returned. Then it checks the next state in the list. If it gets to a state that doesn't work, that is none of the possible colors work, it sets that state's color to UNDEF and backs up to reconsider the previous state. The previous state's color is advanced to the next color, since the color it used really doesn't work when future states are considered. And the checking goes on from there. Now it may be that no other colors work for this state, and it will back up some more. But note that when the program needs to back up, it ends up skipping the consideration of the rest of the tree. All the remaining state's combinations and permutations of colors are skipped. This is a real time savings. Because instead of processing something like 328,256,967,394,537,077,627 nodes of decision tree, only 158,727 states were reconsidered. If these reconsiderations all needed 4 colors considered, then 634,908 state colors would be recomputed. I'm sure it was less than that. But in any case, it is much smaller. Actually, map makers must have other tricks (heuristics), because doing anything like 158,727 decisions to make a map by hand would take a long time.

This algorithm isn't taken from the Wikipedia article. That would be, uhm, math. It's adapted from the eight queens problem. That problem is to place eight queens on a chess board so that non of them are attacking any others. Since queens attack in columns, one can't have two queens in the same column, so a queen's position can be represented as her height in her own column as a number. Since there are eight columns of eight, then there are 8^8 = 16,777,216 positions to consider. One could just count in octal and check each number. On modern machines, this may be practical. But if instead, one advances just each queen to the next good move, most of the 16 meganodes don't have to be checked. This problem required less than a tenth of a second on a 1980 PDP-10. Modern desktops are about 10,000 times faster.

That this C version can be written in Scheme is clear. All magic that is used is available in Scheme. As a novice to Scheme, writing more programs can only be instructive. It wouldn't be much of a benchmark, because no matter how fast or slow the Scheme version is, the C version does not take long enough to get an accurate timing. But perhaps a sufficiently slow machine could be used. I have a 486/33... but even then it would only benchmark languages, not hardware/software systems.

Scheme For Enlightenment Part Eleven - Four Colors

One of the destinations that functional programming seems to lead to is decision tree searching. Scheme allows such trees to be searched in a depth first manner fairly easily.

One technique in scheme is based on the call-with-current-continuation function, often abbreviated call/cc. This function allows one to get back to some state and continue computation there. It can act like C's longjmp, which can unwind the stack to some prior point. But additionally, call/cc can rebuild the stack to some deeper depth(!). Guile keeps copies of the whole stack. Other scheme implementations may have some more efficient (quicker) way to implement this magic. And, it's magic, because it allows one to remember not just the call to a function, but all of the context leading up to that call. And then, one can return from that function multiple times. Or one could say that the function can be called multiple times with remembered call state. Between returns, some state may have changed in the heap, so it won't just do the same thing it did last time. It looks like magic, because it is.

They say that the function amb is as old as Lisp. Yet something like no implementations of Scheme come with an implementation. Guile is not an exception here, so an implementation is included. The idea is that amb takes a function and several arguments, and returns an argument where, when passed to the function, returns true. One might expect that it just walks down the list and tries one at a time. However, amb is nestable. That is, one can have several calls pending, and all calls will return arguments so that their functions are true. I don't pretend to know the details of how it works, except that the trial and error uses call/cc to start again. Also, it's a macro, which means that where it is used is text-substituted. It's not a function of it's own. The syntax is odd, and will not be explained here.

Finally, assert uses amb. This function allows one to harbor the illusion that a mathematical assertion is being made. So, first, amb and assert. Put this into the file amb.scm so that the other program will know where to get it.

(define amb-fail '*)

(define initialize-amb-fail
  (lambda ()
    (set! amb-fail
   (lambda ()
     (error "amb tree exhausted")))))

(initialize-amb-fail)

(define-macro amb
  (lambda alts...
    `(let ((+prev-amb-fail amb-fail))
       (call-with-current-continuation
        (lambda (+sk)
          ,@(map (lambda (alt)
                   `(call-with-current-continuation
                     (lambda (+fk)
                       (set! amb-fail
        (lambda ()
          (set! amb-fail +prev-amb-fail)
          (+fk 'fail)))
                       (+sk ,alt))))
                 alts...)
          (+prev-amb-fail))))))

(define (assert pred)
    (if (not pred) (amb)))

Map makers have known that only four colors are needed for country maps when the rule is that no two neighbors are shown with the same color. So if France is red, Spain can't also be red. This example uses just the states of New England. These states are chosen because there aren't that many of them.

#!/usr/bin/guile -s
!#
;;; Color the New England states in 4 colors.
(load "amb.scm")

(define (choose-color)
  (amb 'red 'green 'blue 'white))

(define (color-new-england)  ; Choose colors for each state.
  (let ((me (choose-color))  ; MainE
 (ma (choose-color))  ; MAssachuesetts
 (ct (choose-color))  ; ConnecticuT
 (ri (choose-color))  ; Rhode Island
 (nh (choose-color))  ; New Hampshire
 (vt (choose-color))) ; VermonT

    ;; Construct the adjacency list for each state:
    ;; the states' name, its color, the list of its neighbors' colors.
    (let ((Connecticut (list 'Connecticut ct (list ri ma)))
   (Maine (list 'Maine me (list nh)))
   (Massachuesetts (list 'Massachuesetts ma (list ct ri vt nh)))
   (NewHampshire (list 'NewHampshire nh (list ma vt me)))
   (RhodeIsland (list 'RhodeIsland ri (list ct ma)))
   (Vermont (list 'Vermont vt (list ma nh))))
      
      (let ((states (list Connecticut Maine Massachuesetts
     NewHampshire RhodeIsland Vermont)))

 ;; A state's color can't be the same as any of its neighbors.
 (for-each (lambda (c)
      (assert (not (memq (cadr c)
           (caddr c)))))
    states)

 ;; Output the color assignment.
 (for-each (lambda (c)
      (display (car c))
      (display " ")
      (display (cadr c))
      (newline))
    states)))))

(color-new-england) ; run the function to find an answer.

At the top, one notes that guile is invoked and runs the file. The last line calls the function just defined, and so produces the answer. Defining the function is not enough. This example also shows a Scheme convention used by Guile and the emacs editor scheme support module. Left aligned comments use three semi-colons. Comments that are indented with the code use two, and end-of-line comments use just one.

The load syntax is common to Scheme.

The definition of choose-color is very odd. It says that it is just amb with some colors. Remember that amb is a macro and expands, and move on for now. choose-color is then used in the assignment for abbreviations of the states. This is how the work gets done. Yet, we haven't told it what the rules are yet.

The adjacency list has longer names that eventually are printed, the abbreviation and a list of neighboring states. I may not have mentioned it. Lisp stands for LISt Processing. Scheme, a dialect of Lisp also does lists. A zillion operations are available for goofing around with lists. Scheme is good at lists.

Next comes a list of states, for convenience.

Then, a for-each asserts that the color of one state is not the color of a neighboring state in it's list. The cadr of a list is the second element, which is the state abbreviation. The caddr of the list is the third element, which in this case is a list - the list of neighboring states. The memq function returns true if the given element can be found in the given list. We never want to find our color in the list, so not is used.

Finally, the answers are printed in another loop. It takes a bit of work to see that both the state name and the state's assigned color are printed. You may be hard pressed to find an assignment to a list with the state and the color. My best guess is that the state is a function that returns said list. I'm pretty sure i haven't gotten to the bottom of this mystery.

This example does not take much time to run. But i goofed around with it to try to discover if it, for example, can easily be extended to all 48 contiguous states and the District of Columbia. It can't. At least, not without computers many orders of magnitude faster than the ones we have today, or lifetimes much longer than we enjoy, or both. To date, i've been able to color 17 states with this code. And that's pushing it. This decision tree has states with 1, 2, 2, 3, 3, and 4 neighbors. So the tree has 1 * 2 * 2 * 3 * 3 * 4 = 144 branches. If the average neighbors is 3, with 6 states, the compute time is roughly proportional to about 3^6 or 729. But with 15 states, the time is proportional to 3^15 = 14,348,907. So if this example takes a second, 15 states might take five hours. (Or it might find a solution on the first attempt.) But all 48 lower states plus the District of Columbia could take 10,401,835,608,364 years. That's approximately 759 times the current age of the Universe.

Yet map makers have been coloring non-trivial maps for a long time. I have a colored globe of the Earth, including the lower contiguous 48 states with the District of Columbia. How could they possibly do so by hand if the computer, executing billions of instructions per second, can't have yet finished? The answer is that this algorithm performs a depth first search of the solution space. The only optimization is that if it finds an answer, it stops and returns that answer. This is an optimization when one considers that this means that the entire decision tree may not be traversed. Some parts of it are skipped. There may be many answers. If so, it may find one sooner, on average, than searching half of the tree. But it isn't clear that if it assigns red to Maine and notices once that assigning red to New Hampshire that it won't try assigning these colors to this pair later. There are still larger parts of the tree that don't need to be searched. This program doesn't appear to know how to skip them.

One optimization that i've tried is changing the order in which states are assigned. For example, sorting New England states alphabetically is some seven times faster than the order i'd started with. See, i grew up in Massachuesetts, so i started there and branched out. But this algorithm works better if the states with few connections are listed first, and Massachuesetts is adjacent to the most states in New England. The reason the alphabetical order is faster is that it doesn't happen to need to try as many guesses before it stumbles on a correct solution.

If i were to do this by hand, I'd assign red to Massachuesetts. Connecticut could be green. Rhode Island could be blue. That takes care of the southern chunk of states. Vermont could be green, and New Hampshire could be blue. Maine could then be red. By taking this order, i didn't have to backtrack any guesses. That is, after accounting for the states that had colors chosen, and picking a color that wasn't already used, i was done with that state, and didn't need to go back. That's because i picked a color for the most constrained state, Massachuesetts, first. I didn't even need white. Indeed, at least under Guile, this script doesn't use white either.

I have to imagine that all states start out as red, and then get changed when it turns out that it doesn't work. I've no idea which states get changed when. If i come up with a rule which might reduce the size of the search tree, i've no idea how to tell this program this rule. The scheme tutorials suggest that it may be more difficult to write such a program in C. I've written this in C and was able to put in hints. And the result is a program that is a little longer, but generates colors for all 48 states and the District of Columbia in under a second. That's not because C is so fast, because even at a thousand times times faster, this should take the age of the Universe to finish. It's because my C version does less work.

When there are four choices, it can save alot of time if the most promising branch can be taken first. Just sorting the options can be a win. These experiments were done by trial and error, and statically, in the Scheme version, using small numbers of states, tuned so that it would take some time, but not too much.

Another issue is equivalent results. Starting with a red Massachuesetts means that i should never have to change it. Starting with a green Massachuesetts would be equivalent. The other colors would have to change, but it would be a simple substitution, red is green and green is red, will be fine. It would be nice to be able to avoid running down these redundant branches of the tree.

So, at the moment, i'm forced to the conclusion, that while this is an interesting technique, it's only viable for essentially trivial problems. This is a technique that only a mathemetician could love. Mathemeticians are notorious for wanting to be able to state that a solution exists, without having any care to actually obtain some solution. A non-trivial practical problem is coming up with an optimal schedule for 35,000 students, each taking 12 of 200 different courses on a campus with 300 rooms of various sizes and 250 professors. Brute force isn't going to work here.

Perhaps by learning the details of call/cc, expanding the amb macro to see the resulting code and examining how it really works, something might appear that will suggest optimization options. That would be magic beyond the Ordinary Wizarding Level.

Scheme For Enlightenment Part Ten - A Benchmark

This benchmark has been kicking around since around 1982. It was originally written in C for microprocessors that had, by today's standards, very little memory. On modern processors (as new as a 486) the entire program and data fits into the on-chip processor cache. It's too small to induce TLB thrashing. In short, this tiny benchmark screams on modern CPUs. While there is plenty that can be learned from it, it is not representative of the big long running applications that can chew up a modern machine.

#!/usr/bin/guile \
-e main -s
!#
;;; Eratosthenes prime number sieve, Answer is 1899
;;; $ sieve.g loops
;;; Based on benchmark from Byte, Sept 82.
(define (sieve x)
  (define flags (make-vector 8191 #t)) ; one-bit flags
  (define count 0)
  (define prime 0)
  (define k 0)
  (display "Iterations: ")
  (display x)
  (newline)
  (do ((iter 0 (+ iter 1)))
      ((>= iter x))
    (set! count 0)
    (set! flags (make-vector 8191 #t))
    (do ((i 0 (+ i 1)))
 ((>= i 8190))
      (if (vector-ref flags i)
   (begin
     (set! prime (+ i i 3))
     (set! k (+ i prime))
     (while (<= k 8190)
     (vector-set! flags k #f)
     (set! k (+ k prime))
     )
     (set! count (+ count 1))))
      ))
  (display count)
  (display " primes")
  (newline)
  )

(define (main args)
  (sieve (string->number (cadr args))))

You tell the program how many times to loop from the command line. The original so-called 8 bit processors, the 8080, the 6800, and so on, which ran at 1 to 4 MHz, took quite awhile to perform one loop, when coded in C. One loop is also sufficient for the 25 MHz Dragonball 68000 CPU in my Handspring Visor Platinum Palm Pilot in Lispme. For modern desktop processors using C, 10,000 loops are used.

The prime number sieve of Eratosthenes discovers the prime numbers by a simple process. First, all the flags are set true. Then all the even numbered flags after the 2nd are set false. The array is checked for the next true flag, which is the third flag. So every third flag is set false after that first one. And so on. However, this version does not represent the even numbered flags. So the formula for what flag to set next is slightly more complicated. It was great for the primitive microprocessors of the 1970's. These processors had no divide instructions, which would usually be needed to test for prime numbers.

The flags variable is an array. It could be of bits. Each element holds a true or false value. Guile supports something called uniform vectors. And vectors of single bits are supported. The Guile Reference manual suggests that uniform vectors should be faster than regular vectors, where every element could be a different type. However, one bit, 8 bit signed and unsigned bytes, and 32 bit signed and unsigned words are all slightly slower than plain vectors. Perhaps some future version will optimize uniform vectors. One bit flags does take less space. Since there are 8,191 flags (2^13 -1), one bit flags should only take 1 KB, instead of 8 KB. There is a shifting and masking penalty, however.

When all is said and done, this sieve doesn't report the actual prime numbers found. It just counts how many numbers are prime, and reports that.

There is kind of an oddity with the vector. First, (define) is used to create the vector, with all flags true. Then, in the loop, (set!) is used to set all the flags to true. There's no way to create a vector without also setting the values. The (make-vector) function requires it.

The do loop is used instead of let loops, recursion, tail recursion, etc., because at least in Guile, the do loop is quickest. However, as much as possible, the original C version has been translated directly. The idea isn't to generate prime numbers. The idea is to create a Scheme version of the benchmark that does the same amount of work done by other versions. Versions of this benchmark exist in C, scheme, BASIC, Perl, Python and other languages. And the idea is to get some idea of how fast each language performs on some given machine.

For one machine, C was 340 times faster than Guile. How does this stack up to other languages? It's faster than Perl or BASIC, but slower than Java. One might think that a factor of 340 is unusably slow. However, some applications don't require much total time. For example, dynamic web pages tend to require a fraction of a second in Perl. A C version isn't much different. If there were some reason to use Scheme for such a task, for example because large integers were needed, then why not? But much more likely for Scheme, some algorithm might lend itself to a functional programming style.

I hesitate publishing this benchmark. I'm a relative novice to Scheme programming. I find it very difficult to judge how long things will take. Scheme, and as i understand it, Lisp in general, is very sensitive to the details of how data is represented. It's possible that a version might be written which is much faster. If you see something that could be changed, let me know.

Scheme For Enlightenment Part Nine - Command Line Parsing

Hello, World is not a real program. Often, real programs have to deal with the command line. Guile has facilities to make this easy. The following allows getopt style command line syntax to be supported. It does so in a way that illustrates how command line parsing may be done.

#!/usr/bin/guile \
-e main -s
!#
(use-modules (ice-9 getopt-long))
(define (main args)
  (let* ((option-spec '((version (single-char #\v) (value #f))
                        (help    (single-char #\h) (value #f))))
         (options (getopt-long args option-spec))
         (help-wanted (option-ref options 'help #f))
         (version-wanted (option-ref options 'version #f)))
    (if (or version-wanted help-wanted)
        (begin
          (if version-wanted
              (display "getopt-long-example version 0.3\n"))
          (if help-wanted
              (display "\
getopt-long-example [options]
  -v, --version    Display version
  -h, --help       Display this help
")))
        (begin
          (display "Hello, World!") (newline)))))

The 2nd line uses Guile's -e option to call the function main once Guile reads the script into memory. Scheme has no equivalent to C's main. There is no starting function. But Guile allows one to name one in it's startup with an option. It doesn't need to be called main.

In the 6th line, option-spec is defined. It defines two command line options, version and help, with single character short cuts that do not take option arguments. If version is given, the version 0.3 message is displayed. If help is given, a usage list is displayed. If neither option is given, the usual Hello, World! message is displayed. This can be used as a template for more complex scripts.

Line 8 actually calls getopt-long to do the parsing. The parameter args is a list of strings from the command line, provided by Guile, starting with argv[0].

Note that another way to display newlines is embodied in this example. In the bit where it displays help, the newlines are inserted into the string literally. Apparently strings in Guile can span multiple lines. No line continuations are needed, as is C.

This essentially trivial program is 22 lines long. While Scheme is touted as being terse and concise, it appears that when it needs to deal with the real world, it can be as verbose as the best of languages.