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.

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... ;-)

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:

• Frames addressed to its own unique MAC address (called a "unicast" address).
• Frames addressed to the global broadcast address.

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.

• First, you could simply pass every multicast frame to the driver software. This is the equivalent of being a person with very, very, sensitive hearing that is able to hear the conversations of everybody in the large room anyway, no matter if they are in another corner or not. Essentially, you'll get interrupted by every frame. It's your choice, though, and some of the earliest MAC chips used this technique because it's easy and it's guaranteed to work, even if it is inefficient. Couple this with the fact that most early network protocols didn't use multicast that much, and you could get away with it.
• The second approach is to compare the incoming frame against not just the node's own unicast address but additional registers containing multicast addresses. The upper layer software tells the driver which multicast addresses the node is interested in receiving, and the driver populates the registers appropriately (the equivalent of, "We're a May birthday, so stand in that corner."). The problem here is threefold. First, how many registers is enough? There are 2^47 - 1 addresses, so having a small number of registers like 2, 4, 8, 16, or 32 seems very small in comparison to the possible range. Second, what do you do when the upper layer software exceeds that number? Do you refuse to listen to all of them? That seems wrong. Do you revert to receiving all multicasts? That seems like a big step backwards in efficiency. Finally, while you might be tempted to just put in a whole lot of registers, like 100 or 1000 say, remember that registers take silicon area and that you also have to compare the incoming frame's destination address against all the registers simultaneously. This last requirement means that you can't use an efficient RAM to store the addresses with a state machine that compares things sequentially, you have to build something called a content addressable memory (CAM) which is both inefficient in space and power dissipation and therefore limits how large you can go. Put another way, you could maybe build a CAM to do a few tens of addresses, but you couldn't do 1000.

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."

...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.

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!

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:

• Scott McKay is a really smart guy. I don't know too much about his background, but he's clearly sharp. He seems like he would be fun to work with.
• It was interesting the almost unanimous consent that languages should strive to save people, namely programmers, time. If that requires a bit of efficiency loss, then fine. In general, people said that virtual machines were a good idea. The main dissenter here was Paul Graham who, thinking from a server-side perspective saw program efficiency as the denominator in the economic equation for how many clients you can serve with a fixed capital budget for servers. He said that to ignore efficiency was a definite pitfall.
• Steele had a lot of really interesting general comments. He has clearly worked on so many different languages fairly closely that he offers a really unique perspective.
• The Runtime panel seemed to be very open about the various battlescars that they had from their various experiences. I think this is important. Theories are great, but tested theories are even better. It's important to run the experiments and see what happens. Even if things fail, at least you have an anti-pattern to write up.
• John Maeda offered an interesting perspective on the Language Design panel. He's working at the MIT media lab and sees the artistic side of the technology. He made the comment that an interesting trend was that there are many artists who are becoming much more familiar with technology, but art is still looked down on by most technologists. When you read some of Richard Gabriel's writings, the theme of a linkage between art and technology (namely programming) is very strong, as well. Graham also wrote about this in Hackers and Painters. The conclusion that I'm rapidly coming to, supported by my own experience, is that most good programmers have a strong appreciation for art. While they may not be artists themselves in other mediums (painters or musicians), they truly are artists in the medium of program design and they need to recognize good design and strive to create it. I'll probably have a lot more to say about that in future blog entries as that's rapidly becoming a theme for me personally.

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 http://groups.yahoo.com/group/lispmachines/. 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.