Andreas Fuchs wrote a visualization tool for string search. I could not resist to add the Knuth-Morris-Pratt algorithm, given that it was just a handful code for the algorithm itself, the visualization then comes for free, thanks to Andreas' preparatory work.

That reminded me, however, that I have a KMP implementation lying around. The KMP algorithm is easy to implement, and works well with streams:

KMP> (with-input-from-string (s "12345AaAaB67890")
       (let ((ts (make-array 10 :element-type 'character
                             :adjustable t :fill-pointer 0)))
         (do-delimited-stream
             ((token expected (read-char s)
                     (multiple-value-call #'values ts (read-line s nil)))
              "AAB"           ; restart-vector generated automatically
              :predicate #'char-equal)
           (vector-push-extend token ts)
           (format *trace-output* "~&Expected ~A, got ~A" expected token))))
Expected A, got 1
Expected A, got 2
Expected A, got 3
Expected A, got 4
Expected A, got 5
Expected A, got A
Expected A, got a
Expected B, got A
Expected B, got a
Expected B, got B
"12345AaAaB"
"67890"
T
KMP> 

KMP works in a way that it does not have to backtrack on the stream after a partial match, unlike a naïve algorithm. Neither does it store parts of the stream.

I used it to read from a stream until the given delimiter is reached, and save everything upto and including the delimiter for further processing. Since it does not seize control of the stream I can, for example, process escape sequences or skip parts of the stream, before I hand stream elements to DO-DELIMITED-STREAM.

It appears that some of the screencasts I am interested in, are recorded in WMV9 format. I do not remember noticing this on Linux, but when I switched to OS X, I could not play them anymore.

I tried various options I was used to, but neither VLC nor MPlayer OSX worked sufficiently nice. Then I found Flip4Mac which allows to play WMV files with QuickTime. No complaints so far, works like a charme.

Except—how to decide when two objects are alike? And what, exactly, is the meaning of alike?

Common Lisp provides a whole bunch of ways to compare two objects (EQ, EQL, EQUAL, EQUALP, not to mention the versions specialized on more specific types), each of which is suited for a particular purpose.

When I define application-specific types, odds are good that at some point I want to compare their instances, and possibly with a coarser equality than pointer equality (which is what any of the functions mentioned above will give me for such objects). I can still define my own specialized equality predicate to compare two of my object directly, but what if I want to compare, e.g., graphs of lists of my objects? The predicate needs to be able to deal not only with my objects, but also with any other type of CL object which I might reference.

One such equivalence (and there are many other possible ways to define one) is MW-EQUIV:OBJECT=. It distinguishes between mutable and frozen objects, and is extensible. The rules are simple:

• Mutable objects are compared by pointer equality. Henry Baker has a lot to say about why that makes sense in his paper Equal Rights for Functional Objects.
• If I promise in some way or other that two object are frozen, i.e., they will not be mutated (even though they might be mutable in principle), then they are compared by looking at their respective constituents.

As an example, I define a class FOO with two slots and check equivalence of two instances.

CL-USER> (defclass foo ()
           ((fred   :initarg :fred   :reader fred)
            (barney :initarg :barney :reader barney)))
#<STANDARD-CLASS FOO>
CL-USER> (equal (make-instance 'foo :fred 'fred :barney 'barney)
                (make-instance 'foo :fred 'fred :barney 'barney))
NIL
CL-USER> (equiv:object= (make-instance 'foo :fred 'fred :barney 'barney)
                        (make-instance 'foo :fred 'fred :barney 'barney))
NIL

Fair enough, by default objects are considered mutable, hence two different instances are not equivalent wrt. OBJECT=.

Now, I promise that I will not modify instances of FOO. Also, both of its slots are relevant to determine equivalence between two instances.

(defmethod equiv:object-frozenp ((foo foo))
  t)

(defmethod equiv:object-constituents ((type (eql 'foo)))
  (declare (ignore type))
  (load-time-value (list #'fred #'barney)))

Here is what I get:

CL-USER> (equiv:object= (make-instance 'foo :fred 'fred :barney 'barney)
                        (make-instance 'foo :fred 'fred :barney 'barney))
T
CL-USER> (let ((fred (list 'fred))
               (barney (list 'barney)))
           (equiv:object= (make-instance 'foo :fred fred :barney barney)
                          (make-instance 'foo :fred fred :barney barney)))
T

Cool, instances of FOO are now compared by their slots. However, this might not be enough:

CL-USER> (equiv:object= (make-instance 'foo :fred (list 'fred)
                                            :barney (list 'barney))
                        (make-instance 'foo :fred (list 'fred)
                                            :barney (list 'barney)))
NIL

Lists are build from cons cells and those are mutable, and so are our instances then, by proxy. I have to promise that at least I will not mutate the conses pointed to in the slots of our FOO instances:

CL-USER> (equiv:object= (make-instance 'foo :fred (list 'fred)
                                            :barney (list 'barney))
                        (make-instance 'foo :fred (list 'fred)
                                            :barney (list 'barney))
                        t)
T

Of course, usual caveats apply. If I do something stupid like breaking my promises, or subclassing a class with mutable instances, and declaring subclass instances as frozen, I will lose.

(It's MW-EQUIV, in case anybody missed link above.)

p.s.: For a brief moment I thought that AND/APPEND method combinations together with NO-APPLICABLE-METHOD would make a nice implementation, but I'll leave that for another time.

Christian Lynbech writes about the script he uses to build his lisp images. As he notes, dumping a custom image is a real time-saver.

Compared to his, my own sbcl-save-core is rather on the low-tech side of the spectrum, so I thought I'd share it as well. As the name suggests, it works for SBCL only.

No surprises in there, except that before calling SB-EXT:SAVE-LISP-AND-DIE, I push :michaelw-core onto *features*. This ends up in the newly generated core. I conditionalize on it in my ~/.sbclrc, not to repeat some parts of the extra initialization performed for a vanilla image.