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.

Scheme For Enlightenment Part Eight - Hello, World!

The book, Practical Common Lisp is said to be for people who want to do more than factorials. Hello, World! is the logical next step.

You've got a Linux machine. If your distribution doesn't have guile installed, perhaps this will help:

sudo apt-get install guile

Under Unix, scripts in script languages like the sh, csh, perl, awk, and guile can be executed by having a first line start with the name of the program that will run them. I'm not going to get into a discussion about what is a script, a program, an application, or whatever. Here, a scripting language is one where the source can be executed by some system from the command line, so the operating system needs to know what system will execute it. There is no other valuable distinction.

It turns out that there are many ways to get a script run by guile, but this is one of the easiest:

#!/usr/bin/guile -s
!#
(display "Hello, World\n")

The pound bang and path to guile is reasonable enough. One must pass a command line option, -s to get guile to read the file and run it. The second line is a bit odd. In a departure from Scheme, Guile implements a multiple line comment syntax. It starts with pound bang, and ends with bang pound. Pound bang is not Scheme syntax. Scheme already has a comment to end of line - semicolon. So, Guile's authors decided on a multiple line comment concept. And it can get used for startup. The rest of the file is what you want to execute.

This script starts with a call to the function display, which writes it's argument to the standard output, which might be your terminal. Guile's display allows an embedded newline in the string, just as is done in C and other languages found in Unix environments. You may see this script written this way:

#!/usr/bin/guile -s
!#
(display "Hello, World")
(newline)

It does the same thing, but calls the newline function.

While the command line is important, there are also modules that allow GTK (graphical user interface) and CGI (web interface) applications written for Guile.

Scheme For Enlightenment Part Seven - A Little Fib

The Fibonacci function is another one of those defined recursively. The Fibonacci(0) is 0 and the Fibonacci(1) is 1. The Fibonacci(x) is Fibonacci(x - 1) + Fibonacci(x - 2) for integers more than 1. The Scheme implementation is straight forward.

(define (fib x)
  (if (= x 0)
      0
      (if (= x 1)
          1
          (+ (fib (- x 1)) (fib (- x 2))))))

Since there are two calls to itself, followed by addition, this is not tail recursive friendly. Also, since there are two calls to itself, and each of those calls calls itself, the number of total calls goes up faster than x. The time taken for fib(x + 1) is about 1.6 times as much as fib(x). Large x takes exponentially longer than smaller x.

Since addition, rather than multiplication is used, the answers don't become absurdly huge too quickly. The answers can be stored in a 32 bit unsigned integer for x up to 47, and a 64 bit integer can cope with the answers up to 93. With this in mind, a C version is more practical.

unsigned long long
fib(int x)
{
  if (x == 0) {
    return 0;
  }
  if (x == 1) {
    return 1;
  }
  return (fib(x - 1) + fib(x - 2));
}

This returns the same numbers for up to 93. However, fib(93) will take thousands of years to run. Yet, at this point, the Guile version and the C version can be used as a sort of benchmark. It turns out that the C version is about 100 times faster that Guile for the same x for this benchmark. Neither version requires huge amounts of memory. The call stack doesn't get very deep, nor does much go onto the stack.

The tail recursive friendly version of this function is instructive. A helper function is defined which does all the work. It is passed two additional parameters which allow it to accumulate intermediate answers. They are passed initial constant values to get it going. There's only one call to itself, and it really is the last thing the function does, so it's properly tail recursive. It produces the exact same answers as the above functions.

(define (fib-helper a b x)
    (if (= x 0)
        b
        (fib-helper (+ a b) a (- x 1))))

(define (fib x)
    (fib-helper 1 0 x))

One might expect a small constant speed improvement due to recursion. But this function isn't just a little faster, like four times faster. This function is amazingly fast. For example, (fib 93) requires an essentially unmeasurably small amount of time. That's much less than thousands of years. So what's going on?

The key is that the helper only calls itself once. For a given x, it calls itself that many times. It doesn't have exponential time, it has linear time. Well, it's not exactly linear. As x gets larger, the arithmetic takes longer because the numbers are bigger. Even so, (fib 1000) spits out all 209 digits basically without pause. This algorithm is so much better, that the original recursive version should just be scrapped. More than one Scheme tutorial demonstrates the slow recursive Fibonacci function. One made a cryptic remark that this algorithm computes Fibonacci numbers slowly. This new version was presented as tail recursive friendly, but totally failed to mention that it is a wildly different algorithm. As a point of fact, i have no idea why this function should return the same answers as the original.

This version is so much faster that a C version is pointless. Recall that (fib 93) with this version is essentially instant. The C version might be 100 times faster, but that's still instant, for a total time savings of essentially zero, best case. Actually, a best C version wouldn't do any calculation at all. If one is limited to 64 bit integers, the function can only answer 94 questions (starting with zero). The fastest version would have a small table of answers and just return one of them.

Scheme For Enlightenment Part Six - Recursive Language Comparison

C is a procedural language but it can also do recursion. And, it's call stack is deeper than Guile's. Isn't that odd? Maybe not. Guile is written in C. At least under Linux, sstk(2) is not implemented, so the stack size can't be changed. So Guile is limited in the same way that C is. C's stack is likely more efficiently represented, so more can go in the same sized area, and therefore feels larger. Here's the factorial in C, recursively.

int factorial(int x) {
    if (x == 0) {
 return 1;
    } else {
 return x * factorial(x - 1);
    }
}

It hasn't improved. It's still limited to x = 13. But try this rather spooky equivalent. Is it starting to look like Scheme?

int factorial(int x) { return (x == 0) ? 1 :  x * factorial(x - 1); }

If unsigned 64 bit integers can be used, then factorial(20) can be computed. Or C's double (floating point) type can be easily used. That gives you approximate answers (13 digits) and works up to factorial(170). It has the side effect that it knows when it overflows in the answer, reporting inf.

But let's say we really want exact large integers in C, as we get from Scheme. What do we do? The answer is that we link with an arbitrary precision number library, change the data type to the library's type, and use the library to do the multiplies. The structure would remain, and it would still be fast. After all, Guile's big numbers are written in, uhm, C. And, Guile is open source. At worst, one could use the Guile implementation of big numbers, and the two languages would end in a draw, more or less. It is much more likely is that a convenient package exists that doesn't use garbage collection, and is faster than Guile.

So, is the factorial example a good example? That is, is it fair to the languages involved? Perhaps. While short, it's complicated enough that there is more than one way to write it in each language. It brings up issues that each language enjoys. What's not to like?

Back to enlightenment. The question is, does one have to cope with recursion in order to gain any enlightenment from Scheme? Unfortunately the answer seems to be yes. Functional programming and other styles have their basis here. I'm not out to replace my procedural style with something new. I'm out to add flavor to the stew. However, it's clearly not gonna happen without some kicking and screaming.

Scheme For Enlightenment Part Five - Comparative Languages

The dreaded Scheme factorial example is written in C.

I'm coming most recently from the C world. What does it look like in C? C programmers usually think in loops, so something like this comes out.

int factorial(int x) {
    register int product = 1;

    do {
        product *= x;
    } while (--x);
    return product;
}

The variable product is the factorial being built. In each loop, it is multiplied by the current x. The variable x is decremented by one. When the loop counts down to zero, the result is returned.

It's wickedly fast. And it works for positive arguments all the way up to 13. On 32 bit machines, factorial(14) is larger than an integer. Also, we didn't bother to check for zero (or less), so it loops for a long time before getting the wrong answer in these cases.

The fact that it is six or seven lines instead of three or four does not bother me. All of the lines are reasonably easy to read. Besides, C is free format. All the lines can be jammed together, even if it looks strange.

int factorial(int x) { int f = 1; do f *= x; while (--x); return f; }

Scheme For Enlightenment Part Four - Even More Factorials

The dreaded Scheme factorial example is beaten over the head and shoulders recursively.

Another variant of the loop factorial. It uses a "let loop".

(define (factorial x)
  (let loop ((count x) (product 1))
    (if (= count 0)
 product
 (loop (- count 1) (* product count)))))

The loop starts, creating variables count and product. The variable count starts at x and counts down to 1. But also, product, starts at one. That's the second line. Once each loop, product is multiplied by count, and count is decremented. That's line five. When count is zero, product is returned in the forth line. One odd bit of the syntax is how the loop works. It looks recursive. If so, it's tail recursion and fully optimized. But it really doesn't matter if it's a iterative loop or recursion. Scheme can decide that. That is, unless it can't be nested. The do loop can certainly be nested. It's reasonable to assume that let loops can be nested also. The full inner loop would execute before the outer loop, and each would benefit from tail recursion optimization, at least in theory.

The original version of the above let loop factorial was more confusing. In it, the counting variable was named x. That's the same name as the parameter. One expects that the inner definition hides the outer definition. So how does Scheme know to assign the outer definition to the inner for the initialization? Apparently, it's designed to. But that doesn't make it consistent.

As an aside, in my examples, i've used a short cut syntax for defining all functions. In the Guile Reference, section 3.1.2.4, it is suggested that this form should not be used. The lambda syntax should be used instead.

It could be argued that the alternative define forms are rather confusing, especially for newcomers to the Scheme language, as they hide both the role of lambda and the fact that procedures are values that are stored in variables in the some way as any other kind of value.

Using the lambda syntax, the above example becomes this.

(define factorial
  (lambda (x)
    (let loop ((count x) (product 1))
      (if (= count 0)
   product
   (loop (- count 1) (* product count))))))

While the lambda keyword does indicate that a function is being created, and the define keyword indicates that this function is getting bound to a name, i don't like it much. It has yet another nested set of parenthesis, which means that there is that much more i might get wrong. There's an extra line of code (though there needn't be). The indention of the body of code is deeper, at least in the emacs pretty printer style. And finally, lambda is a Greek letter that doesn't mean anything. Go ahead, look up lambda in Google. It has been assigned all kinds of meanings. Scheme and Lisp are high in the list. I think Dennis Richie got it right. The language keywords are not the important part of the language. The important part is the bits that the programmer has created in it. So, in C, structure uses one character keywords. Here, we have the opportunity to omit a whole keyword entirely. So much the better. As a recent novice, i consider lambda an advanced topic that one can safely ignore for awhile.

Scheme For Enlightenment Part Three - More Factorials

The dreaded Scheme factorial example is continued recursively.

Scheme (and Lisp) purists continue to promote recursion as the right way to do things. Scheme, or at least Guile, Lispme, mzScheme, umb-scheme and probably all others, support free tail recursion. That is, if the very last thing your function does is call itself, then no stack penalty is paid. Unfortunately, the first example has a multiply after the last call to itself, so it must use a stack. There is a solution, but it isn't as simple.

(define (factorial x)
  (letrec ((tr-factorial
     (lambda (count product)
       (if (> count x)
    product
    (tr-factorial (+ count 1)
    (* count product))))))
    (tr-factorial 1 1)))

This tail-recursion version is much more complex. The second line defines a helper function, which calls itself. This helper function takes two parameters. The first is the current number to multiply by, and the second is the current accumulated result. In the forth line, it checks if it's done by comparing with x, the original parameter. If it is done, it returns the answer. Otherwise, it multiplies the current number by the accumulated answer, adds one to the current number and calls itself with these values. The last thing it does is calls itself, so the Scheme implementation can do the tail recursion optimization, and no additional stack is used on each call. The implementation can be said to jump to the start of the function, instead of call it. The outer definition calls the inner definition in the seventh line, starting the count at one and the accumulator at one, and the result from this call is returned. And, if one feeds this version 1000, it quickly spits out all 2,568 digits of the answer.

One is expected to use recursion for loops. And this really seems to be how one is expected to do program recursion in Scheme. Enlightenment isn't going to come easy. It works, but there are some issues with it. First, there's a weird interaction between the nested function definitions. The inner definition needs access to the outer definition's parameter. One supposes that it could just be passed as a third parameter. Then it could be a standalone function, and one would always call it with two extra parameters, set to one. In fact, Guile supports optional arguments with default values. So this can be written as a single function, at least in principal. We won't go there.

Another issue is that it isn't obvious from the source that the inner function is actually tail-recursive. The self call is smack-dab in the middle of the function definition. This has implications if one is going to use this language. As a programmer or debugger, one must know. Are there tools that could quickly tell you? Well, you can (trace) your call to find out. The tutorials talk about how you can do it with inspection. Plan to get good at it.

In timing tests, the looping structure is quicker than recursion. It isn't much faster in this example, because for large factorials, most of the computer's time is spent doing the large multiplies. For one brought up with procedural languages, the loops are easier to write, to read, and to debug. In fact, having variables to watch in a Scheme debugger provides clues as to what is going on. In a pure functional program there are no variables, so the debugger can only tell you what happens in function calls. This can be less than helpful.

Apparently, at least part of incentives to use a pure functional style is that such programs are easier to prove are correct, at least in a mathematical sense. While noting that setting variables is convenient, this quote from The History of Lisp is an example: (Fans of other programming languages are challenged to write a program to concatenate lists and prove that the operation is associative). Presumably, such a proof would involve having another program use logic to make such a statement.

But one still must cope with other language issues. For example, how does one cope with the parenthesis? A good editor can tell you if your parenthesis are lined up. Vi and Emacs can do this. Some editors, like Emacs, and other external tools can pretty print functions. The pretty printing can expose some of the structure. And, after a year of beating on the language, it gets a bit easier. But there's still the problem of where the various bits of the do loop should go. The syntax is horrible. And i've gotten comfortable with the full Unix find command, and regular expressions. I grok horrible.

Scheme For Enlightenment Part Two - More Factorials

The dreaded Scheme factorial example is continued.

Consider this factorial version, which uses a do loop instead of recursion. It has two extra variables, is a little longer, and what is going on anyway? One expects the first example to be better all around. But if one feeds this version 1000, it quickly spits out all 2,568 digits of the answer. Since it works with bigger numbers, and is as quick or quicker for smaller numbers, it's better, right?

(define (factorial x)
  (do ((count 1 (+ count 1))
       (product 1 (* count product)))
      ((> count x) product)))

The second line starts the do loop. The variable count starts at one, and is incremented by one each time through the loop. In the third line, the variable product also starts at one (same loop), and is multiplied by the variable count each time through the loop. The forth line says that the loop continues until count is more than x (the parameter). When all is finished, the value of product is returned. Let's walk an example.

(factorial 3)

Count starts at 1, product starts at one multiplied by count which is also one, and so is 1. The parameter x, which is 3 is compared to count. Since count is not larger than the parameter x, the body, which doesn't have anything in it, is executed. One is added to count, resulting in 2. This is multiplied by product, and product gets the answer, (* 1 2) is 2. count, which is 2, is compared to x, which is 3. Count is still not bigger than 3, so the loop restarts again. One is added to count, and so it now has the value 3. The variable product, 2 is multiplied by count, 3, and the result, 6 is assigned to product. Count, 3, is compared with x, 3, and it isn't bigger yet, so you'd think that the loop continues. However, that's not what it does, and we know this because the answer isn't 24, it's 6. Somehow, count gets incremented so that it is greater than 3, but product is not multiplied by 4. This mystery is solved, i think, by reading the manual. From the Guile Reference, section 5.11.4, The test expression is a termination condition. Looping stops when the test is true. It's evaluated before running the body each time, so if it's true the first time then body is not run at all. So the order of operations isn't exactly the way that i've outlined it.

So, in theory, the pure recursive version is simpler and better. In practice the loop version is faster and gives correct results for a wider range of input. What's the difference between theory and practice? In theory, they are the same...

Scheme For Enlightenment Part One - Factorials

The dreaded factorial example.

This series is starting to look like a Scheme tutorial. While most Scheme tutorials start with this example, they usually gush over the language as the ultimate for expression, hackability, etc. My opinion is that if you invest enough in a language, your tendency is to advocate that others share your pain. My approach here is to expose the weaknesses when noticed, without apology. Even my current favorite language, C (or maybe English), has plenty of warts. This is my approach to sales. I say things like, Have a free bagel. It only has 500 calories. That's probably only a quarter of the calories you consume in a day. So giving away free bagels can be difficult. On the bright side, my investigations continue with the hope that something good will come of it eventually. Feel free to share my pain.

Some Scheme syntax. (First comes an open parenthesis. Then comes a verb, which is a function or a method. Then comes space separated list of all the parameters: the nouns. The list has zero or more of these nouns. The list ends with a close parenthesis.) There is a verb that performs multiplies.

(* 5 6)

The asterisk is for multiplication. The 5 and 6 are things to multiply. The expression returns 30. Since expressions return nouns, they can be used as parameters to other functions.

(+ (* 5 6) 7)

This returns 37. The 30 returned by the multiply is added to the 7. These functions can be nested arbitrarily deep. The Scheme language does not place limits, as far as i know, though implementations certainly do.

This is functional programming. Apparently, the idea that one might assign a value to a variable is not part of functional programming. Scheme allows variables, but there are pure functional languages, like j, which don't.

The factorial of an integer is the product of all the integers from 1 to that number. The factorial of 0 is 1. The factorial of 3 is 6 (3 * 2 * 1). Now the mathematician says, we know the factorial of zero is one. We know the factorial of one is one times the factorial of zero, which we already know is one. And so on - the factorial of a number x is x times the factorial of x - 1. Consider this Scheme implementation.

(define (factorial x)
  (if (zero? x) 1
      (* x (factorial (- x 1)))))

It is purely recursive, it matches the definition of the function, doesn't use any extra variables, and is short. There are a boatload of parenthesis, each one in the correct place. Get used to it. In the second line, the function checks to see if the parameter is zero, and if it is, it returns the number one. This is the factorial that we know - the base condition. In the third line, we are in the else clause of the if, so x is not zero. It subtracts one from it's parameter, calls itself with that, and multiplies the result by it's original parameter. This function works for small positive numbers. Let's step through an example.

(factorial 3)

We're going to substitute the actual numbers. In the first call, 3 is not zero, so the return is (* 3 (factorial 2)). There is still a call to do. In that call, 2 is not zero, so the return is (* 2 (factorial 1)), substituting that in above, real result is (* 3 (* 2 (factorial 1))). The number 1 is still not zero, so (* 1 (factorial 0)) is returned. In this case, 0 is equal to zero, so the number 1 is returned. Substituting that in, we get (* 3 (* 2 (* 1 1))). The inner most multiply is computed, resulting in (* 3 (* 2 1)). The next inner most multiply is computed, resulting in (* 3 2). Then finally, this multiply is computed, resulting in 6. If you type in this example into any Scheme system, the result, 6, is printed.

While it works for small positive numbers, if you feed it a thousand, Guile reports this:

ERROR: Stack overflow

Now, the factorial of 1000 is a very large number indeed. But the stack overflow has little to do with the size of the answer. Scheme supports arbitrarily large integers. Millions of digits, for example are not only supported, but practical. Computations with million digit numbers can be performed in a reasonable amount of time on modern machines.

The reason it gets a stack overflow is that it needs a stack level for each of the thousand calls to itself. The system runs out of stack space. The Earth rests on the back of a turtle. What does that turtle stand on? Another turtle! It's turtles, all the way down.

Scheme For Enlightenment Part Zero

As a part of my ongoing road to enlightenment, i've just finished reading the Guile Reference Manual. Guile is an implementation of the computer language Scheme. Scheme is a dialect of the Lisp language. A million years ago, when i was an undergrad, i managed to get credit for just one computer course, entitled Lisp/Algol. Both are relatively ancient computer languages. Lisp dates from something like 1956, and we used Algol60, the 1960 vintage standard. The seven week course spent some five weeks on Lisp, and the remaining two on Algol. Yet, two weeks in Algol seemed like luxury compared with only five weeks with Lisp.

The idea that a language as sophisticated as Lisp was invented so early came as a complete surprise. In retrospect, early computer users were taken from the pool of mathematicians. And Lisp is a language written by mathematicians for mathematicians, much as C is a language written by systems programmers for systems programmers.

Despite eight semesters of college math, i can't really say that i think like a mathematician. You see, my math was heavy in differential equations for engineering. I actually liked Boundary Value Problems. That's because there are obvious real world applications for this stuff. As a rocket launches, even if the thrust is constant, the mass decreases as fuel is consumed, the air drag decreases with altitude, but increases with speed. So where does the rocket end up?

I know how to go from home to work. I used Yahoo Maps to find out how to get to Phil's house from work. Even if i'm home, i can get to Phil's by going to work, then using my new directions to get to his house. As an engineer, that's OK. Phil happens to live pretty close to where i work, at least compared with the total distance to where i work. Dave happens to live pretty near where i live. So, if one day, i wanted to go directly to Dave's house from work, i'd look that up on Yahoo Maps, and go. But if i then wanted to go to his house from home, i'd look that up again on Yahoo Maps, because going 80 miles out of my way to get to Dave's, only 4 or 5 miles from my house is absurd. But the mathematician considers the problem solved, and optimization is irrelevant. Worse, the mathematician assigns cryptic symbols to the way points. My house is mnemonically labeled 'A', and Phil's 'B', and Dave's 'C'. So, she says, "I know how to get from 'A' to 'B', and from 'B' to 'C', so I know how to get from 'A' to 'C'". Global warming notwithstanding.

And Lisp or Scheme is, so far, like that. There are lots of examples that are very short that are also very slow. It's also not at all clear how they could be made quicker. More on this later.

For a year i plowed through a Scheme tutorial (Teach Yourself Scheme in Fixnum Days), beat on Lispme (a Scheme implementation for the Palm Pilot), and now have Guile loaded on my Nokia hand held computer (i don't care for the term 'tablet', as it seems to limit, rather than enable wide application). Guile is also loaded on my Linux desktop where there's a real editor and keyboard. A real editor is a must.

Scheme, as a language, has some unusual features. Integers can be arbitrarily large. They can be millions of digits long. That suggests certain application classes, like discovering large prime numbers. Guile's implementation of larger numbers also seems to be fast. It also has support for non-local branching, handy for error recovery. And there's this kind of odd speculative computing which seems to be able to search arbitrary decision trees. There's also an odd programming style that seems encouraged - functional programming. There might be something of value here. Who knows?

Guile is an implementation of Scheme. But the Guile developers have added capabilities to encourage certain kinds of work. It is possible to embed a Guile interpreter in an otherwise C application, perhaps as an extension language, or configuration module. Additionally, it is reasonably easy to extend Guile by using C modules, which can be plugged into Guile.

Though Guile has been used this way, i personally don't see it. Lisp has never had the ease of reading that an Algol-like language has. Sure, it has automatic memory management. But it comes at a price. Guile is between 100 and 500 times slower than C. As near as i can tell, all the Scheme implementations are. However, there is a Scheme compiler that i have not examined.

The Guile Reference Manual talks about how one should do things certain ways for speed. In some ways, this is not a shock. A factor of 100 is roughly 10 years of computer speed improvements. So, you fire up your hot new 4 GIPS computer, to get Pentium II performance. And yet everywhere in the manual, recursion is held up as the iteration device. Guile's own do loops work faster, and never suffer stack crashes because you didn't get the tail recursion right.

My guess: mathematician's proofs use indirection. Recursion is indirection, only more so, but with little extra effort, or at least syntax. This blinds them to the fact that computers naturally deal with iteration more efficiently.

Lisp has often been the preferred tool for the development of artificial intelligence. Might the field move forward 10 years with a conversion to C?

Top Ten, 18 of 10

When we last left our hero, we were looking at ten ways to get screwed by the "C" programming language. Today's entry is Fabulously awful "standard libraries"

It turns out that libraries are harder to write than C compilers. Now, designing a good language may be difficult. But implementing an already standard language is a matter of meeting the requirements. Libraries are generally not written to standards. One writes a library by one of two processes. Either one has a task to do, and builds a library to support that task while building an application. Or, one tries to guess what functions programmers might need, and provides functions that do those things. Both approaches have problems. Your application might not need something other programmers will need. Your application might need the same things, but with peculiar semantics, making the implementation difficult to use. Or, you might not have guessed what other programmers might need. C's standard library isn't worse than most. There were a few mistakes, such as scanf(3), and index(3). There were some omissions in the original version, like strstr(3). While the bugs that were designed in are still there, for backward compatibility, solutions to those problems are available. One is told to use the fixed versions. Don't use scanf(3) - use fgets(3), then sscanf(3). Don't use index(3), use the new name strchr(3). I count the standard C library as a success because i actually use it, and don't invent a new string library. At least scanf(3) has a good excuse. The idea was to allow string parsing to work on streams. It's just that scanf(3) isn't a good way to make that happen. That said, i have written a stream based parser that needed it's own version of atof(3). That's about it.