I got to see Steve Wozniak speak at Columbia University last night, promoting his new book iWoz. Strongest impression: The man has an incredible amount of energy. He talked in a strong voice at high speed for nearly an hour before rushing off to tape a spot on The Colbert Report. Most interesting fact: he hooked up his Apple I to his television set — creating the first practical video monitor — because he needed a cheaper input/output method than the teletypes everyone was using at the time.

He’s obviously obsessed with engineering and programming to a degree that most mortals can barely imagine. Who else would think of building a 10-bit digital computer as a middle school science fair project?

Another thing that struck me was his stated desire to start fresh on each computer he designed, building in capabilities — like color for the Apple II — from the ground up. That seems like the complete opposite of the approach most of the PC industry has taken of layering new functionality on top of old, to the point where it takes 5 minutes to boot a modern PC. What might the Woz come up with if he started today designing a new PC from the ground up, taking advantage of all the advances of the past two decades but leaving behind the legacies?

Been too busy with work and class to post much, but here’s a link for all the IANALs out there: Project Posner. It’s an on-line database collecting the case opinions of Richard A. Posner, judge on the 7th Circuit Court of Appeals. This was the brainchild of law professor and former Posner clerk Tim Wu. I wrote all the code to parse and format the cases, in 100% Common Lisp! Specifically, about 800 lines of code that spits out 36 MB of static HTML in about 5 minutes — whee! Currently having some problems with Google’s free web search; maybe they’ll crawl the site now that I’ve linked to it. Or maybe I’ll break down and implement my own search function. In any case, take a look, comments welcome.

I’m playing some more with the early chapters of Artificial Intelligence: A Modern Approach, looking at basic tree search techniques for the 8-puzzle. I wrote simple breadth-first and depth-first search algorithms for this puzzle in Common Lisp. Here’s the code. It’s an interesting demonstation of how inefficient these alogrithms really are.

I represent the puzzle as a simple list of integers numbered 0 through 7, with the symbol B representing the “hole.” The “winning” position is (0 1 2 3 4 5 6 7 B). I also added a little code to have the algorithm track the number of iterations; how many “nodes,” or board positions, it has to expand in the search tree; and the maximum number of positions it has to keep stored in memory.

Just to test that I’ve coded it right, I make sure the algorithm does nothing when given a solved puzzle to start with:

CL-USER> (breadth-first-search '(0 1 2 3 4 5 6 7 B))
"Found (0 1 2 3 4 5 6 7 B) in 0 steps.
Expanded 0 nodes, stored a maximum of 0 nodes."

Next, I try it on a puzzle that is just one move away from a solution:

CL-USER> (breadth-first-search '(0 1 2 3 4 5 6 b 7))
"Found (0 1 2 3 4 5 6 7 B) in 3 steps.
Expanded 9 nodes, stored a maximum of 5 nodes."

All well and good. Now lets try shuffling the pieces a bit more:

CL-USER> (breadth-first-search '(0 1 2 b 3 6 4 5 7))
"Found (0 1 2 3 4 5 6 7 B) in 18327 steps.
Expanded 49075 nodes, stored a maximum of 8422 nodes."

Ouch. That’s kind of slow. And that wasn’t even the hardest possible starting arrangement. So much for that.

Let’s see how depth-first search does on the one-move-away puzzle:

CL-USER> (depth-first-search '(0 1 2 3 4 5 6 b 7))

Dum de dum dum. Tick tock.

Half an hour later, I get bored and interrupt it. Obviously depth-first search is not a very good algorithm for solving the 8-puzzle. I’ll have to wait for the next chapter, which introduces A* and other informed searches.

It’s funny to me, because both of these algorithms seem like reasonable ways of searching a tree of possibilities. I guess it’s hard for my mind to grasp just how overwhelmingly large exponential growth really is.

Ran across an interesting remark in a discussion of Microsoft hiring interviews:

If I remember, a lot of MIT people back in the 70s broke the computer world into the Lisp and non-Lisp data typers. The Lisp folk took a casual attitude towards data structures – just shove them in a list, put them on a plist, stash them in a cache. If it gets slow or confusing, add some tags and a hash algorithm. Most non-Lisp folk were appalled at this. They wanted to see the data structure design up front, the data relationship dictionary, complete and comprehensive, even before any coding started.

This sounds like it could be a language-induced habit as much as a programming style. E.g., in Java you have to write “class foo” at the start of a program before you can do anything else, so it makes sense that you’d start by defining data structures. In Lisp, it’s really easy to jump straight to the algorithms, making up “casual” data structures as you go along, so that’s what you do.

The “stuff everything into a list, add some tags later when it gets too big or confusing” is exactly how my largest-to-date Lisp programming project panned out. It worked fine, and made the code pretty short and simple. As the big list got too big to handle in-place, I wrote a handful of functions that pulled out specific pieces of data. Since function calls look identical to method calls in Lisp, the code looked like I had defined a class with a bunch of accessor methods, while in fact it was still just a big list. This was especially helpful given that I was working with free-form data parsed from text files, not a table of predetermined fields. (This could also have been handled somewhat less elegantly with XML.)

Update Oct. 3, 2006: In case anyone was misled, the title was a joke. Data structures are certainly useful. I was merely commenting on the programming styles induced by different languages.

I was looking at a problem in the early chapters of Artificial Intelligence: A Modern Approach. It’s called Vacuum World. This is a very simple agent problem consisting of a vacuum placed on a grid. The grid has only two squares, each of which is either dirty or clean. The vacuum has three actions: move left, move right, and suck.

I wrote a simple implementation of this in Java (because the course I’m taking uses Java), starting out something like this:

public class Vacuum {
    private GridSquare location;
    public void moveLeft() { ... };
    public void moveRight() { ... };
    public void suck() { ... };
}

Obvious, beginner’s OOP, right? But then I start to second-guess myself. Is location really a property of the vacuum? Or is it a property of the vacuum in its environment? That is, does the location variable belong in the Vacuum class, in the Grid class (the environment), or in some “world” object that encompasses both the vacuum and the grid? Should Vacuum even be allowed to have a reference directly to its location, or should it query the environment indirectly, as in “Is the square I am currently occupying (wherever it may be) dirty?”

The example code on the A.I.M.A. web site seems to go out of its way to be inscrutably OO, with the behavior of the vacuum divided among half a dozen abstract “agent” classes. I think the vacuum there stores its location as an integer, but I couldn’t swear it to you.

I decide to play around with the Java logging facility. I write a simple test program:

import java.util.logging.*;

public class LoggingTest {
    public static void main(String[] args) {
	Logger log = Logger.getLogger("com.stuartsierra");
	log.entering("LoggingTest", "main");
	log.info("Info Message");
	log.warning("Warning Message");
	log.exiting("LoggingTest", "main");
    }
}

Compile, run, and I get this:

Aug 30, 2006 10:48:45 AM LoggingTest main
INFO: Info Message
Aug 30, 2006 10:48:45 AM LoggingTest main
WARNING: Warning Message

Hmm. Not quite what I expected. Two out of my four log messages don’t appear. Back to the API docs. Ah, yes, I need to set the logging level if I want to get finer-grained messages like “entering” and “exiting.” So I add the line,

log.setLevel(Level.FINEST);

just after getLogger(), compile, and run again. Same exact result — the “entering” and “exiting” messages don’t appear. I look at the API docs again. Nothing strikes me. The Java (TM) Logging Overview doesn’t enlighten me either. I try Level.ALL, just to make sure. Nope, Java doesn’t want to print those messages.

Now if I were on a deadline, I would say screw it and go do some real work. But I want to understand why this doesn’t work. After three or four web searches I find An Introduction to the Java Logging API. As it turns out, I need to set the level not just of my Logger, but also of each of the Handlers receiving messages from it. The article suggests this code:

Handler[] handlers =
   Logger.getLogger( "" ).getHandlers();
for ( int index = 0; index < handlers.length; index++ ) {
   handlers[index].setLevel( Level.FINE );
}

I insert that into my test code, and lo and behold, it works:

Aug 31, 2006 11:05:53 AM LoggingTest main
FINER: ENTRY
Aug 31, 2006 11:05:53 AM LoggingTest main
INFO: Info Message
Aug 31, 2006 11:05:53 AM LoggingTest main
WARNING: Warning Message
Aug 31, 2006 11:05:53 AM LoggingTest main
FINER: RETURN

So what's the lesson of all this? It's easy just to say "Java's logging API is weird." But I'm sure those Handlers are in there for a reason. I can imagine wanting to send the same stream of log messages to a file and a window at the same time. I can even imagine wanting to send different levels of log detail to different outputs. I do think it is a mistake to have the level-setting code duplicated in both Logger and Handler, as it means more work for me, the client programmer who gets frustrated when his code doesn't do what he expects it to. At the least, the API documentation for Logger.setLevel() should mention that you need to set the level on all the Handlers too.

More generally, I think this is an example of how a library can be too customizable. Picture the feature list: "Custom logging levels per-logger and per-output." Sounds great, until you have to remember to set them both to the same value to get what you want.