Irreal

Robert Smith over at Symbo1ics Ideas has a very nice introduction to restarts in Common Lisp. Restarts are a part of the CL error system (more accurately, part of the CL condition system) and provide a way to recover from errors even if they happen in code that is far away from where the error is handled. The example that Smith gives assumes that the code where the error occurs is in a third party library but that the vendor has provided scaffolding to allow graceful recovery from errors.

If you’re new to Lisp or if you aren’t a Lisp user but want to see how error handling can be done right, head on over and take a look at Smith’s post. If you want more after reading Smith’s post, Chapter 19 of Peter Seibel’s excellent Practical Common Lisp gives a reasonably comprehensive introduction to the Common Lisp condition system.

I ran across an interesting interview question the other day: Given a base word and a list of other words, use the Levenshtein distance to find the social network of the base word in the list of other words. More specifically, we call word_b a friend of word_a if the Levenshtein distance between them is 1. The problem is to start with the base word, find all its friends in the other list, then find all the friends of the friends, and so on. This problem is representative of a large class of related problems (such as The Six Degrees of Kevin Bacon) so it’s worthwhile considering how to solve it.

The Wikipedia article on Levenshtein distance has a straightforward pseudocode implementation of an algorithm to find the Levenshtein distance between two words that I translated directly into Lisp. I won’t bother showing the code since it’s pretty much a one-to-one translation.

The basic strategy is to do a breadth-first search of the base word’s social graph. We don’t have the graph, of course, that’s what we want to find. Instead, we build it up piece by piece. The main tool for doing breadth-first searches is a queue or FIFO. I’ve disussed these and given an implementation before. The implementation at the link is in Scheme but it’s trivial to convert it to Common Lisp. Again, I won’t bother showing the Lisp implementation.

With those two pieces in place, it’s pretty easy to implement the algorithm to find the social network.

 1:  (defun social (word words &optional graph)
 2:    "Find the social graph for word in the population words"
 3:    (let ((inside (make-instance 'queue))
 4:          (outside (make-instance 'queue :initial-contents words))
 5:          (new-outside (make-instance 'queue))
 6:          (results (list (cons word 0)))
 7:          nodes)
 8:      (pushq (cons word  0) inside)
 9:      (do ((datum (popq inside) (popq inside)))
10:          ((null datum) (if graph (sgraph (reverse nodes)) (reverse results)))
11:        (destructuring-bind (word . distance) datum
12:          (do ((potential-friend (popq outside) (popq outside)))
13:              ((null potential-friend))
14:            (if (= (levenshtein word potential-friend) 1)
15:                (let ((friend (cons potential-friend (1+ distance))))
16:                  (pushq friend inside)
17:                  (push friend results)
18:                  (push (cons (car datum) potential-friend) nodes))
19:                (pushq potential-friend new-outside))))
20:        (rotatef new-outside outside))))

The implementation uses 3 queues:

• The outside queue that holds words that have not yet been identified as friends. It’s initial value is the list of other words.
• The inside queue that holds friends that are waiting to be processed. It is initialized to the base word with a distance (from the base word) of zero at line 8.
• The new-outside queue that holds words from the outside queue that aren’t friends of head of the inside queue.

The main loop pops off the head of the inside queue at line 9 and checks each word on the outside queue to see if it is a friend. If it is, it adds that word and its distance from the base word to the end of the inside queue (line 16), it adds the same to the results list (line 17), and finally adds the two words being compared onto the nodes list (line 18). If the word being checked is not a friend, it is pushed onto the end of the new-outside queue.

When the outside queue is empty, it is swapped with new-outside and the main loop starts over. When the inside queue goes empty, the process is complete. Assuming graph is NIL, the results are returned.

If *words* is given by

(defparameter *words* '("milk" "silk" "mill" "mails" "mills" "miles" "silly"
                        "smiles" "smile" "mile" "sill" "hilly" "shill"
                        "mall" "bill" "bull"))

and the base word is bilk, the results of a run are:

SOCIAL> (social "bilk" *words* )
(("bilk" . 0) ("milk" . 1) ("silk" . 1) ("bill" . 1) ("mill" . 2) ("mile" . 2)
 ("sill" . 2) ("bull" . 2) ("mills" . 3) ("mall" . 3) ("miles" . 3)
 ("smile" . 3) ("silly" . 3) ("shill" . 3) ("smiles" . 4) ("hilly" . 4))

Thus “milk” is a direct friend of “bilk” and “mills” is a friend of a friend of a friend.

We can see the network more clearly by specifying graph as t. That causes social to call sgraph to output a dot program to produce a graph. Here’s sgraph:

(defun sgraph (edges)
  "Output a dot program for the social graph of word in words."
  (with-output-to-string (stream)
    (format stream "graph G { ~%")
    (mapc (lambda (e) (format stream "~a -- ~a~%" (car e) (cdr e))) edges)
    (format stream "}~%")))

For our example, this produces the program

graph G { 
bilk -- milk
bilk -- silk
bilk -- bill
milk -- mill
milk -- mile
silk -- sill
bill -- bull
mill -- mills
mill -- mall
mile -- miles
mile -- smile
sill -- silly
sill -- shill
miles -- smiles
silly -- hilly
}

which produces the graph

Earlier this week I wrote about Using Quicklisp and mentioned another Xach project, Quickproject (the link takes you to Github, but the best way to get it is with Quicklisp). What quickproject does is to initialize a project.asd, package.lisp, project.lisp, and README.txt files for a project. The idea, as explained in Beane’s post on building small Lisp projects, is to bootstrap a project by setting up initial versions of the files you’ll need for an ASDF loadable project.

I expected that it would be really useful to working on medium sized projects such as libraries. I’m sure it will be but today I wanted to experiment with a small, single .lisp file project. I decided to try out Quickproject to see how it would work for a really small project. It was a revelation as to how much easier it made things. I started with

(quickproject:make-project "~/lisp/levenshtein/")

then opened the ~/lisp/levenshtein/levenshtein.lisp file and started hacking. When I got finished I was able to load it with Quicklisp even though I had not configured ASDF to search ~/lisp/ for projects. I’m really impressed with how easy and useful it is. If you regularly write in Common Lisp you really need to get Quicklisp and Quickproject. They’ll make your life a whole lot more pleasant.

Vladimir Sedach has a post up that describes the cl-test-grid project. The idea is that Quicklisp users download the cl-test-grid, tell it what CL implementations are available, and run the test. It runs tests against many of the libraries in the latest Quicklisp release and sends the results to a public report site and a bug tracker site.

This is a way of helping library writers get their libraries tested in as many environments as possible. It seems like a good idea so if you are willing to donate a few cycles it’s a worthwhile exercise. See Sedach’s post for details.