Irreal

If you’re a Lisper here’s a surprising bit of Common Lisp arcana from Xach’s Common Lisp Tips. Did I mention that you really should subscribe?

I love this simple Common Lisp REPL by Stas Boukarev over at Zach Beane’s Common Lisp Tips. In just 5 lines of code you get a complete REPL that even handles *, **, and ***.

In the comments, Brit Butler adds two more lines that makes it display the current package as well. Good stuff.

I’ve mentioned Common Lisp Tips many times before and can’t recommend it enough. Xach always has something useful to say and, most often, something I didn’t know. If you’re a Lisper, you really should subscribe.

I’ve mentioned Jean-Philippe Paradis’ Common Lisp Tip Tweets before. He’s reorganized the site a bit and categorized the tweets so that it’s easier to find what you’re looking for. If you don’t follow him on Twitter, it’s worth stopping by his site every once in a while to check out the new tips.

My favorite new tip since my last visit:

CL tip: Indentation-saving trick:
 (multiple-value-bind (a1 a2 b c1 c2 c3)
   (multiple-value-call #'values (values 1 2) 3 (values 4 5 6))
  ...)

Steven Goss over at the zero bit stream has another great Common Lisp post. His idea is to compare a minimal Haskell Quicksort routine to the same function written in Common Lisp. A case can be made that the result is not really Quicksort in either language because of the performance profile but they do follow the Quicksort algorithm and are interesting even if they aren’t useful as production code.

Goss’s final result makes use of a list comprehension macro that is interesting in its own right but the first attempt is also nice. Here’s Goss’s code for the first attempt:

(defun quicksort (list)
  (when list
    (destructuring-bind (p . xs) list
      (let ((lesser (remove-if-not (lambda (x) (< x p)) xs))
            (greater (remove-if-not (lambda (x) (>= x p)) xs)))
        (append (quicksort lesser) (list p) (quicksort greater))))))

Notice how it makes the structure of the Quicksort algorithm explicit. Of course it doesn’t choose the pivot in an intelligent way—which can result in n² behavior—and all those remove-if-not and appends are each tacking on O(n) penalties but you still have to love the beauty and brevity of the code.

Quicksort, like any other industrial strength algorithm, is hard to get right. As I mentioned in my post on Jon Bentley, perfecting the Quicksort algorithm is definitely not trivial. This implementation doesn’t come close but it is useful because it makes the structure of Quicksort clear and because it shows how Common Lisp can express algorithms in a beautiful way.