Shitcanned

Friendster fired my friend and former co-worker Joyce because in her weblog she posted things like this:

Finally on Friday we launched a platform rearchitecture based on loose-coupling, web standards, and a move from JSP (via Tomcat) to PHP.

and this:

Jon Udell's latest column mentions Friendster's rewrite. He makes exactly the right point: the programming language itself was not really the issue. It's the combination of decisions -- the “it all adds up” factor -- that makes the difference between a platform which fits the task and one which does not.

She says that she was careful to only post about things that were already public knowledge (and it's not as if seeing every Friendster url change from ending in .jsp to .php didn't already tell you everything you needed to know). I wonder if her now-ex-CEO got freaked out seeing the huge amount of attention her posts sometimes got, which was probably more attention than any official Friendster press release has received up to this point. Maybe he didn't stop to think about why that might be.

Technorati already lists 33 [now 49] [now 63] [now 121] weblogs linking to Joyce's story, including Ross Mayfield, Matt Haughey, Jason Shellen, Anil Dash (“someday i'll get fired from six apart for networking socially”), Jeremy Zawodny, Marc Brown, Joyce's husband, Tim, Jon Udell, Robert Scoble and Chris Pirillo. I won't be too surprised if it ends up on slashdot and metafilter [and boingboing, CNET and Wired News].

I doubt Joyce is going to have any trouble finding another job.

PlaneT

The new version of PLT Scheme has an automatic run-time module distribution system, PlaneT [via Gordon Weakliem].

For example, if you wanted to turn a stream of emails into an RSS feed using the mail2rss module, you would first insert the following form into your code:

(require (planet "mail2rss.ss" ("mburns" "mail2rss.plt" 1 0)))

If mail2rss isn't already installed locally, the (require (planet ...)) will automatically download and install it, and make it available to your code.

Nice.

Geiriadur

Dmitri Hrapof's Geiriadur 2.0 is a dictionary lookup engine and editing system. “It's developed as a tool to create Welsh-Russian and Russian-Welsh dictionaries, but it can also be used for other languages, for example, Breton or Irish. I believe it's the only existing Welsh-Russian/Russian-Welsh dictionary for now.”

The Lisp-based server and the Python client use CORBA to communicate. Huh.

Animus Gone Wild!

[I couldn't face the amount of work involved in doing something like Tony Pierce's 53 page(!) photo essay on last weekend's Sunset Junction, and actually it turned out I was too lazy to write even four or five paragraphs. So I asked Lori if she would, and she did. --John]

Warning: This posting contains no references to Lisp. Sorry, Lisp enthusiasts! I did try to come up with a good Lisp joke, but I think it is largely unremarkable:

Q. What's the difference between Lisp and FORTRAN?
A. People remember FORTRAN.

Stay for the veal!

This year's Sunset Junction Street Fair, L.A.'s premier rock'n'roll hipster cavalcade, did not disappoint this attendee, especially since it was fifty feet away from my apartment and proffered a delightful abundance of tasty food on sticks. I thought about taking pictures, but my fingers were coated in a sticky melange of butter, BBQ sauce and beer. If I had taken pictures, they would have featured many attractive, shirtless men in leather short shorts. And rapidly wilting drag queens, families and punk rocks: it was actually 224,000 degrees outside. Celsius. To see all those diverse, sweaty groups of people noshing and boozing together, well, my heart done swole up with love and civic pride.

There were a kajillion booths and vendors; everyone was trying to hawk something, from ironic t-shirts to Super Shammys to Scientology. Some earnest-looking youngsters passed out free copies of a novel called Wild Animus from a card table. A copy was thrust in my hand, the hand that wasn't holding food on a stick, that is, and I greasily flipped through it hoping it was desperately pornographic. Tragically, it was just merely bad. I later thrust my copy into someone else's empty hand.

Sunset Junction features dozens of excellent rock bands. This year's offerings included Ben Kweller, Love, Camper Van Beethoven, and X, none of which I saw because I was at a book reading given by my horrifyingly talented friends, Allyson Shaw and Richard Melo. Both of them have brand new books out (The Bon Bon & Love Token and Jokerman 8, respectively) and you must surely read them.

Truthfully, I only heard one Sunset Junction rock act this year: Linda Stevens. I listened to her band while I took a nap in my apartment (fifty feet away, remember); they made for lovely nap music. Although I think they should pick a different band name, or maybe capitalize on the nap angle. “Linda Stevens is gonna ROCK you to sleep!”

Oops

It turns out that common-lisp.net wasn't attacked after all.

It has been verified that there was no real attack. We were spooked by a misconfiguration that caused software that wasn't supposed to be installed (specifically Samba) to run. Embarrassing but true. In retrospect we do still feel that the decision to take Common-lisp.net down was a reasonable one, given the amount of information he had at hand at the moment.

Scott McCloud on PowerPoint

This really isn't one of those Information Architect/Usability/Tufte worship/Interaction Design -type weblogs (even though I am kind of interested in those things), but since I've posted about PowerPoint before and am a Scott McCloud fan I thought I'd mention this short interview with Scott in which he discusses his thoughts on slides and software.

PowerPoint is merciless. It exposes our levels of apathy. If your message entirely grows out of something about which you have no interest, it’s going to show. PowerPoint will not forgive – it will expose you. It will show the true you. If your day is a tedious drone of facts and figures, I’m afraid that is what is going to hit the screen.

Robotrices

I was googling for images of Robodex when I found someone's collection of Robodex booth babes. No robots, sadly.

These roboboothgirls seem a little washed out compared to, say, the girls from the 2003 Tokyo Auto Salon.

I have no theories about that.

P.S. I googled for “robotrices” and found a page mentioning the term in the context of “robot prostitutes” (well, actually it was “robots prostitutas”), which led to further googling. This turned up a rich collection of results, the first of which mentioned something about decaptitating robot prostitutes. At this point, the sexual politics of this post have become too complex even for my robot gigolo brain to keep track of and so I hand it over to you, as is, taut-bodied, mini-skirted and always smiling.

Epson's MicroRobot System

Epson has a crazy little robot, μFR-II, with a camera, Bluetooth, and the ability to follow a pre-programmed flight path. All in 12.3 grams.

She seems spellbound by the micro-robot. WHO IS THE REAL ROBOT HERE?

“EMRoS” stands for “Epson MicroRobot System.” This series included four main models: Monsieur (listed in the Guinness book of Records as the world's smallest—only 1cm3 in volume, 1993), followed by Nino (a 0.5-cm3 model introduced in 1994), Ricordo (1cm3, equipped with a recording and playback function, 1995), and Rubie (1 cm3, equipped with a capricious wandering function, 1995.) All of these models are independent traveling robots that chase a light source. Sales of the EMRoS series have been discontinued. 

Easy Target: common-lisp.net

It appears that common-lisp.net has been hacked again, and is currently down.

CL-EMB

Stefan Scholl's CL-EMB is a template system using Lisp which can be used to dynamically generate HTML files... such as Stefan's sorta weblog.

Back from the Heartland

chris, me and lori enjoying cream puffs at the wisconsin state fair

Well, I'm back from the midwest. Any food you can think of, I've eaten it on a stick—deep fried. It's good to be back in LA, with fresh sushi and LAPD helicopters.

Bring on the breaded, chocolate-covered Lisp-on-a-stick.

L - A Common Lisp for Embedded Systems

Charles Rosenberg, co-author of the “L” paper mentioned Tuesday, tracked down a copy:

Rod was able to dig up the paper and I've posted it here:

http://www.cs.cmu.edu/~chuck/pubpg/luv95.pdf

We're not sure if this is the final version, but it is probably pretty close.

Thanks, Charles! (And est!)

L, Mars, Venus

From LUV 95, an extended abstract of , “L - A Common Lisp for Embedded Systems”, Lisp Users and Vendors Conference, sec. 2.4a, by Rodney A. Brooks and Charles Rosenberg [link via Rainer Joswig].

This development effort was motivated by IS Robotics main business, the manufacture and programming of small autonomous robots for real world tasks. These robots have relatively small processors, 16 MHz 68020's with 1 megabyte of RAM

Funny how in 1995 they were calling a 16 MHz, 1 MB machine “small”, while here in 2004, the Roomba built by iRobot (formerly known as IS Robotics) has a 40 MHz cpu with just 256 bytes of RAM.

I can't tell if iRobot blocked wayback machine access to isr.com or if it's a technical issue.

lispmachines Yahoo Group

Dave Roberts has started a Yahoo discussion group, lispmachines, for people interested in recreating, for real or just in simluation, lisp machine-style technology [via Rainer Joswig].

From:  "Rainer"  
Date:  Mon Aug 9, 2004  11:03 am 
Subject:  Re: Why this redundant group?

--- In lispmachines@yahoogroups.com,
--- "pl_schmidt" <asholz@t...> wrote:
> Hello all,
>
> why was this group founded? There is the lispm-mailing
> list at lispm-hackers@l...
>
> Andreas

Probably because the person that started this here did not
know the multitude of other Lisp Machine mailing lists
(slug, tunes/lispm, ...), forums (http://smbx.org/html/) and
newgroups (comp.ti.explorer, info.slug)  - which are mostly
dead anyway.

Plus the lispm-hackers list seems to be members-only, mostly
concerned with the Explorer emulator and what else.

eboy

I found the above pixel-perfect image at eboy years ago, and it has been a mainstay of my desktop wallpaper collection ever since. Now, in a rare collision between Internet cool and Lisp, eboy has re-launched their website... and it's powered by CMUCL, Portable Allegroserve, and bknr!

On the new site's front page:

Manuel Odendahl made the announcement. Boing Boing mentioned it, too.

Bloom Filters

I woke up this morning, got out of bed and promptly stepped in a Bloom filter. On my way to work I drove by a dead Bloom filter on the side of the road, bloated and surrounded by clouds of buzzing flies. Seems like they're suddenly everywhere, so maybe it's time to come up with a Lisp implementation.

Never heard of a Bloom filter? This post is mostly about code, but here's the super brief intro: They're like hash tables used for keeping track of set membership, only (i) they're probabilistic, (ii) you can't easily remove keys and (iii) they use a fraction of the memory of a standard hash table. Beyond that, you'll want to look at Maciej Ceglowski's “Using Bloom Filters” article on perl.com, which is a good tutorial and also lists several references.

Code time.

Our Bloom filter class will consist of three things: the filter's bitmap, the maximum size of the bitmap, and a list of the hash functions the filter is using.

(defclass bloom-filter ()
  ((bitmap :accessor bitmap :initform 0 :initarg :bitmap)
   (hash-functions :accessor hash-functions :initform nil :initarg :hash-functions)
   (size :accessor size :initform nil :initarg :size)))

Adding a key to the filter is simple: Construct a bitmap from the key, OR it with the filter's current bitmap and then assign the result back to the filter's current bitmap.

(defmethod add ((self bloom-filter) key)
  "Adds a key to a Bloom filter."
  (setf (bitmap self)
    (logior (bitmap self)
	    (make-bitmap self key))))

Testing for key membership is also simple: AND the key's bitmap with the filter's current bitmap, and if the result is equal to the key's bitmap then the key is (probably) in the filter.

(defmethod contains ((self bloom-filter) key)
  "Returns T if the specified key is in the Bloom filter."
  (let ((bitmap (make-bitmap self key)))
    (= (logand (bitmap self) bitmap) bitmap)))

So how do we construct a bitmap from a key? We map over the hash functions, use the value returned by each hash function for the key as an index into the filter's bitmap, and turn on the bit at those indices. The bitmap itself will be represented as a bignum, and we'll use ldb to access individual bits.

The SHA1 algorithm will be used as our source of good hash bits. The particular SHA1 implementation I'm using, by Nathan Froyd, returns its 160 bits of hash in the form of a vector containing 20 byte values:

CL(10): (sha:sha1sum-sequence "foo")
#(11 238 199 181 234 63 15 219 201 93 13 212 127 60 91 194 117 218
  138 51) 

We'll divide these 20 bytes into 5 blocks of 4 bytes each, consider each block as its own 32 bit number, XOR the numbers together, and use the resulting value as an index into the bitmap (modulo the bitmap size). We'll turn on one bit in the bitmap for each hash function.

(defmethod make-bitmap ((self bloom-filter) key)
  (flet ((subproduct (index hash-seq)
	   (* (elt hash-seq index)
	      (elt hash-seq (+ index 1))
	      (elt hash-seq (+ index 2))
	      (elt hash-seq (+ index 3)))))
    (let ((vector 0))
      (dolist (hash-function (hash-functions self))
	(let* ((hash-bytes (funcall hash-function key))
	       (hashes (list (subproduct 0 hash-bytes)
			     (subproduct 4 hash-bytes)
			     (subproduct 8 hash-bytes)
			     (subproduct 12 hash-bytes)
			     (subproduct 16 hash-bytes))) 
	       (combined-hash (apply #'logxor hashes)))
	  (let ((index (mod combined-hash (size self))))
	    (setf (ldb (byte 1 index) vector) 1))))
      vector)))

[Update 2004/08/10]: Bill Clagett pointed out that the above method's subproduct function wasn't correctly building 32 bit numbers out of blocks of 5 bytes. Here's the corrected version. Thanks, Bill! Note that I'm too lazy to go back and generate new sample output, so what you see might be different from what I have here.

(defmethod make-bitmap ((self bloom-filter) key)
  (flet ((subproduct (index hash-seq)
	   (reduce #'(lambda (a b) (logior (ash a 8) b))
		   hash-seq
		   :start index :end (+ index 4))))
    (let ((vector 0))
      (dolist (hash-function (hash-functions self))
	(let* ((hash-bytes (funcall hash-function key))
	       (hashes (list (subproduct 0 hash-bytes)
			     (subproduct 4 hash-bytes)
			     (subproduct 8 hash-bytes)
			     (subproduct 12 hash-bytes)
			     (subproduct 16 hash-bytes))) 
	       (combined-hash (apply #'logxor hashes)))
	  (let ((index (mod combined-hash (size self))))
	    (setf (ldb (byte 1 index) vector) 1))))
      vector)))

To turn our single source of hash bits, SHA1, into the multiple hash functions that Bloom filters require, we will use multiple “salts” that we prefix to our keys before hashing them.

(defun make-hashing-functions (salts)
  (mapcar
   #'(lambda (salt)
       #'(lambda (seq)
	   (sha:sha1sum-sequence (concatenate 'string salt seq))))
   salts))

We can use arbitrary strings as salts:

CL(11): (make-hashing-functions '("aa" "bb" "cc"))
(#<Closure (:INTERNAL MAKE-HASHING-FUNCTIONS 0) @ #x572b49a>
 #<Closure (:INTERNAL MAKE-HASHING-FUNCTIONS 0) @ #x572b4b2>
 #<Closure (:INTERNAL MAKE-HASHING-FUNCTIONS 0) @ #x572b4ca>)

Now we can finally construct some filters and play around with them.

CL(12): (defparameter *filter1*
         (make-instance 'bloom-filter
           :size 10
           :hash-functions (make-hashing-functions '("a" "b" "c"))))
*FILTER1*
CL(13): (add *filter1* "P. J. Harvey")
148
CL(14): (contains *filter1* "P. J. Harvey")
T
CL(15): (contains *filter1* "The Sounds")
NIL

Since we specified that the filter should only use 10 bits, we can easily demonstrate the probabilistic nature of the Bloom filter. Let's add a few more keys:

CL(16): (add *filter1* "Royal Trux")
725
CL(17): (add *filter1* "Moldy Peaches")
981
CL(18): (add *filter1* "N*E*R*D*")
981

Now let's check some keys that we haven't entered:

CL(19): (contains *filter1* "Beth Orton")
NIL
CL(20): (contains *filter1* "Rick James")
NIL
CL(21): (contains *filter1* "Rick Springfield")
T

Oops. Well, that's what you get for using just 10 bits of memory.

Further work: Write a LOAF implementation in Lisp. Check which has the best performance: Using a bignum to hold the bitmap (can use straightforward logior and logand to add and compare bitmaps) or using a bit vector (have to iterate over bits manually).

DARPA Course Plotter

DARPA Grand Challenge course plotter, via Igor Carron's Nuit Blanche, which I like. This tickles my neat receptors, but I don't know why. The video is kind of hypnotic.

In case you haven't see the waypoints as provided to entrants by DARPA: waypoints.txt.

Via Igor's other page, video as downloaded from the DARPA satellite feed on the day of the race.

Never Cop Out

This exceeds the usual cheeziness allowance for this here web log. But it's the average that's important.

Isaac Hayes' Three Laws of Robotics [via Mike, and jwz]:

1. A robot must risk his neck for his brother man, and may not cop out when there's danger all about.
2. A robot must be a sex machine to all the chicks, except where such actions conflict with the will of his main woman.
3. A robot must at all times strive to be one bad motha-shutchyomouth.

CLSQL 3.0

Kevin Rosenberg has released CLSQL 3.0. It's a major rewrite of the last version, and includes full CommonSQL backward compatibility and new ODBC and Oracle backends.

CMUCL 19a Released

CMUCL 19a has been released.

19a has loads of new features, including stack overflow checking, package locks, weak hash tables, helpful local function names, compiler checking of format strings & arguments, inspect works on CLOS objects, callbacks from foreign code to lisp, fwrappers-style encapsulation, basic simple-streams, enhanced disassemble, fixed and enhanced trace, byte compiled code runs 33% faster, heap overflow checking, enhanced source location recording (works for macros), c functions visible in backtraces (instead of just “Foreign function call land”), modular arithmetic (“so (ldb (byte 32 0) (+ x y)) is a simple machine add instruction if x and y are (unsigned-byte 32)”).

There are lots and lots of bug fixes, too, including lots of ANSI compliance fixes and many improvements to the CLOS implementations.