Books of Note

Practical Common
LispThe best intro to start your journey. Excellent coverage of CLOS.

ANSI Common
LispAnother great starting point with a different focus.

Paradigms of Artificial Intelligence
ProgrammingA superb set of Lisp examples. Not just for the AI crowd.

Friday, August 20, 2004

"Lisp" or "LISP" 

I have been reading a lot of Lisp-related books and articles lately. It has been interesting to see how various writings either capitalize or don't the word "Lisp." For instance, in MIT AI Memo #12, John McCarthy, who should know a bit about this, uses "LISP." On the other hand, the Symbolics 3600 Technical Summary uses "Lisp." Nobody would accuse those guys at Symbolics of not knowing Lisp. Guy Steele, who knows a lot about a lot, uses "Lisp" in Common Lisp: The Language. Paul Graham uses "Lisp" in both ANSI Common Lisp and Hackers and Painters.

Well... I'd have to respect McCarthy for kicking the whole thing off, but "LISP" is losing steam, it seems.

Update: I just checked AIM-349, "Scheme: An Interpreter for Extended Lambda Calculus," by Sussman and Steele. Seems they use LISP. Somewhere along the line, Steele switched religions.

Tuesday, August 10, 2004

Better than Lisp 

Lisp is fun. I enjoy programming in it. But there are some things just blow Lisp right out of the water. "What?" you say.

Well, yesterday, at 8:00 AM, my wife gave birth to our third child. Evan Joseph Roberts was 8 pounds, even. Mom and baby are doing great.

And that, my friends, makes Lisp seem pretty unimportant today. He can't code yet, but we'll get to that... ;-)

Sunday, August 08, 2004

Bloom meets Ethernet 

I just read John Wiseman's write up on Bloom filters on Lemonodor. It's a good write-up, so have a read.

If you're an old-time communications guy (like me), you'll recognize Bloom filters right away, although I had never heard them called that. All the early Ethernet MAC chips used simple Bloom filters in the receive logic for multicast packets (and probably every IEEE 802.X MAC, including token ring, 802.11, etc.). Here's how it worked...

The basics of the Ethernet receive logic are pretty simple. Each Ethernet frame ("packet" to you layer 3 and above guys, but more formally a "frame" when it's on the wire) contains both source and destination MAC addresses. These are the 48-bit unique addresses burned into the ROM of each Ethernet board out there at the time of manufacture. Now, an Ethernet MAC is supposed to receive at least the following frames:

There is also multicast processing. Most people understand broadcast pretty well. In Ethernet, when you use the broadcast address, you're sending a frame to every node that can hear you on the local layer 2 domain (think "subnet" in the IP world). Multicast is a bit different. Multicast addresses are used to target a subset of the nodes in the local L2 domain--those that have expressed interest in participating in whatever multicast-based protocol you are running.

For an analogy here, imagine being in a large room with 1000 people. If you wanted to tell something to everybody in the room with a birthday in May, you could do it one of several ways. First, you could take out a bullhorn, interrupt everybody with your message, and assume that everybody who does not have a birthday in May will ignore it. The problem with that is, it's horribly inefficient if the number of people you want to talk to is small relative to the total size of the group. If 10 out of those 1000 people have birthdays in May (statistically unlikely, but possible), then you're going to be disturbing 990 people to talk to those 10. If you have a lot of people trying to do a similar sort of thing (possibly trying to talk to the people with birthdays in March, August, and October, for instance), then everybody will be very busy, but mostly being interrupted and then ignoring messages that aren't meant for them.

Another alternative is to tell all the people with a birthday in May to stand over in one corner of the room. You would do this by prior arrangement, like maybe putting a notice in the invitation of what you intend for them to do. You can then deliver a message without having to use a bullhorn to talk to them. The people with birthdays in March, August, and October can stand in the other corners or along one wall, or whatever. When somebody really does have a message for everybody, like "Dinner is served," for instance, they can use the bullhorn for that. Other systems are also possible, but they often are less efficient (you could tell the message to everybody, one by one, for instance).

Ethernet makes a provision for multicast addresses by dividing up the 48-bit address space based on the most-significant bit. If the most-significant bit is 0, the address is an individual node address. If the most-significant bit is a 1, then the address is a multicast/broadcast address. The broadcast address is special and represented by an all-1s pattern. This means you have 2^47 - 1 multicast addresses available.

The early, 1980s, MAC chips had a problem. The issue is that you want to filter uninteresting frames in the hardware, before you DMA data around and interrupt the software driver. The more you can filter in hardware, the more processor time gets spent on useful work, rather than simply inspecting uninteresting frames and then throwing them away in software. It's fairly easy to create hardware logic that compares the incoming frame's destination address with either a 48-bit value programmed in a register or the all-1s broadcast address, but how do you handle multicast? There are a couple obvious strategies, each with problems.

Now, remember that we're talking early 1980s technology here. Nowdays, there are things that you can do that you couldn't do then. For instance, many modern chips do use large CAMs because semiconductor process technology has advanced to the point there that makes more sense. But back then, the tradeoffs were quite different.

A third alternative is that you get a bit probabalistic in your accept/drop logic with the driver software doing a final perfect comparison once the frame passes the hardware screen. Essentially, you use a Bloom filter. The way this was done in the early Ethernet controllers was to run the destination address thorough a CRC-32 algorithm to hash it. This turns out to be easy to do since Ethernet uses a CRC-32 frame check sequence (FCS) and the destination address is the first field in a frame. Just start computing the CRC-32 over the whole packet as you are receiving it and grab the intermediate value of the CRC-32 once you have received the destination address. Next, use some bits of the CRC-32 as an index into a bit mask. Many early chips used a 32-bit mask, so you would use the low-order 5 bits as the index, for instance. Now, the driver software takes the list of multicast addresses registered by the upper layer software and computes a CRC-32 over each address to calculate its index and sets the corresponding bits of the multicast bit mask in the hardware. The hardware does all the matching at wire speed.

Obviously, this is a probabalistic acceptance function. If multicast addresses are used randomly, which they aren't, and multicast registrations from the upper layers are rare, which they were in the 1980s and generally still are today, you have an n-in-32 chance of mistakenly accepting a multicast packet you aren't interested in, where n is the number of bits set in the bit mask. Obviously, the more addresses that are registered by the upper layer software, the more the probability trends toward 1. In other words, the probability that nearly all the bits in a 32-bit mask being set with less than 32 addresses registered is zero. The probability rises quickly after that point, however.

The nice thing about this technique is that it scales up very easily. It's far cheaper to include a 512-bit mask than to include a 512-entry CAM, for instance. Later model Ethernet controllers from the early 1990s often used larger bit masks to reduce the probability of a "false positive" (where the hardware accepts the packet but the software isn't interested).

So, it's true what they say: "There is nothing new under the sun."

Saturday, August 07, 2004

Am I the only one who wonders... 

...where John Wiseman gets the steady stream of odd images that populate Lemonodor on a regular basis? Some are funny. Some are disturbing. They never stop making me think, however.

Listen to the record! 

If you're looking for something to tell you that the band in question is composed of nearly notable former members of various bands, or how many jam sessions the drummer sat in on with rock superstars who are now dead or disabled or retired, forget it. Unless the names Mother's Milk, Middle Earth, or the Revolting Tones Revue ring any particular bells, where the people who make up this band called Boston came from is irrelevant to who and where they are now.

Listen to the record!

After writing about listening to Boston on BART the other day, I was surfing around the Boston website and found out that they were playing at the Concord Pavilion this last Friday. I decided to buy a ticket and go.

First, let me say that Boston's debut album is simply one of the best pieces of music you'll ever listen to. It was the first rock and roll album I ever bought, back in my youth, and it's probably the only one I have purchased on multiple formats over time. It's coming up on 30 years old and it still rocks like nothing else.

The concert was interesting. Like any major 1970's band, the fans are, well, getting more respectable. The number of minivans in the parking lot at the venue was shocking. The people in front of me were well-past my age and had brought their teenage kids with them. The dad was rocking out. I couldn't really tell what the kids thought. Walking in, I saw a couple of guys wearing the high quality Java-logo jackets that they must have sold one year at JavaOne or something. Silicon Valley always has that blend of rockers and geeks at something like this. I suppose I fell into the clean-cut geek category.

All that said, the show was great. They played just about everything in their collection, including most of the debut album and Don't Look Back. All the good stuff from Third Stage got done. Imagine being there with a few thousand people singing and doing the syncopated claps from Feelin' Satisfied. Walk On (the song) was nice and definitely rocked. They closed up with Smokin'.

The band composition has changed over the years. Tom Scholz is of course still the main man, playing guitar and organ like a madman. Brad Delp was sharing singing honors with Anthony Cosmo. Delp has got to have one of the best falsettos in rock-n-roll, but he's aging and I don't think he can hit the high notes that he used to back in 1976. Cosmo does a great job and the two work through the numbers with Delp providing the old sound and Cosmo nailing the high notes that Delp can't hit.

In short...

Listen to the record!

Dynamic Languages Wizards 

While lurking on IRC yesterday, I noticed somebody mention a link for a set of videos hosted at MIT. These were panel discussions done for the dynamic languages class there. The set of three videos was filmed in the spring of 2001 and features the who's who of dynamic language design, including many people involved with Scheme, Lisp, and Dylan. I recommend watching each of the various videos, which can be a time sink as they are each about 1.5 to 2 hours long. In particular, resist the urge to move straight to the Language Design panel that includes Guy Steele, Jonathan Rees, Paul Graham, and John Maeda. There are some huge nuggets in the panels on Runtime and Compilation.

That said, funny quote of the whole series is in the Q&A of the Language Design panel. A questioner asks the panel whether they see something beyond expressing programs in simple ASCII. Rees asks whether the questioner means something like Unicode, to which the questioner responds with something to the effect of, "Yes, and other things too." Steele starts talking and says that he really doesn't have much need beyond the Latin 1 character set and maybe some of the mathematical portions of Unicode. He says, in particular, that he doesn't feel a need for Croatian characters to be there, but maybe somebody in Croatia might. At that point, Graham pipes up, with, "Maybe in the next version of Perl. Think of all the additional characters you'll have..."

Other things which struck me from these:

Monday, August 02, 2004

Yahoo! group for LISP machine recreation fans 

After my recent postings about the CADR LISP machine and embedded LISP machines I got a fair number of comments from people saying something to the effect of, "Hey, I have been thinking the same thing!" Given the number of people that seem to be interested in such a topic, I decided that a discussion group was probably warranted. I just created a Yahoo! group on LISP machines. You can find it at There are other projects that people have also started previously doing similar sorts of things (software simulators, primarily). I'll post references to those as I find more of them.

This page is powered by Blogger. Isn't yours?