Tuesday, January 22, 2008

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?

No comments: