05
Aug 10

Powerful multi-method dispatch with Lisp

I’ve been doing quite a bit of common Lisp lately. I really like it. It’s very powerful and has a combination of simple syntax with quite powerful abstractions abilities. Abstractions comes in different flavors in Lisp (functional, OO, etc…), but the most powerful one is the macro system. I won’t touch more on that in the post, as I’m quite a beginner and probably don’t even grasp its full power and potential.

Unlike many languages which define the abstractions you can use, Lisp gives you all of them and also allows you to build most abstractions you want that are not a part of the language. Some of these powerful features are also present in other languages, as many languages that came after, took notice of some features, but the combination of all of these and the ability to build your own core language abstractions is what makes Lisp probably the most powerful language out there.

Multimethods is the ability to do runtime method dispatch based on arguments and their specialization. Multimethods are not supported in languages like Java with single dispatch, but some other languages support it either through libraries or similar facilities (i.e. pattern matching). Although pattern matching is different, in some context is can provide similar levels of abstraction/flexibility.

Here is an example of multimethods from my cl-kyoto-cabinet project, where I found quite a use for them.

Update: Thanks to Drewc for pointing out that my original example was single dispatch. I was trying to demonstrate the conciseness of polymorphic method definitions inline with defgeneric and completely overlooked the fact that the method dispatch was only occurring on one specialization. The original version is here. Below is the updated version…

The multimethods dispatch is very flexible and concise for accomplishing method-level polymorphism. Same can be accomplished in a less flexible OO language like Java using interfaces and the Strategy pattern, but that usually ends up being more verbose and ceremonious in most non-rudimentary scenarios.

Scala has a similar ability through pattern matching, and so does Erlang.

Tags: ,

7 comments

  1. I think you're confused. The example you show is single dispatch using EQL specialization, and not an example of multiple dispatch at all.

  2. Drewc, I'm not sure how my example differs from a multimethod definition of: a function or method that is dynamically dispatched based on the run time (dynamic) type of more than one of its arguments. I know I only used one argument, but I could of easily used more. The fact is that you're defining methods inline vs. defmethod, right? I could of easily defined the same with defmethod, which would of dispatched based on derived type and EQL specializers.

    I might be wrong. I'm very new to LISP, but I think generally multimethods is what I described. Let me know.

  3. So maybe I'm confused with the theoretical definition of multimethods. In practice, although more concise in LISP, doesn't seem much different than standard polymorphism and method overloading in single dispatch languages like java. Yes, method overloading in Java is limited, that's irrelevant to being able to dispatch based on polymorphism as well as method overloading.

    Am I off base here?

  4. Whether you define methods via DEFMETHOD or DEFGENERIC makes zero difference. That's just a syntactical issue.

    You show 'Multimethods' only dispatching over one argument, which works, but does not show the 'Multimethods' feature of dispatching over more than one arg.

  5. I would not use a generic function for what you do, I would just use a hash table of keywords to functions. That's what hash tables are for: associate keys with values.

  6. Here is a good example of multiple dispatch :

    (defclass stick ())
    (defclass brush ())
    (defclass drum ())
    (defclass hat ())

    (defgeneric hit (hitter hittee))

    (defmethod hit ((hitter stick) (hittee drum)) “BANG”)
    (defmethod hit ((hitter brush) (hittee drum)) “WSSSSHH”)
    (defmethod hit ((hitter stick)(hittee cat)) “MEOW! HISSSS SCRATCH”)
    (defmethod hit ((hitter brush) (hittee cat)) “PRRRR”)

    (let ((cat (make-instance 'cat))
    (drum (make-instance 'drum))
    (stick (make-instance 'stick))
    (brush (make-instance 'brush)))
    (hit stick drum) ;=> “BANG”
    (hit stick cat) ;=> “MEOW! HISSSS SCRATCH”
    (hit brush cat) ;= “PRRRR”
    (hit cat drum) ; => runtime error “No applicable method HIT when called with the arguments (CAT DRUM)”
    )

    In this case, as i hope is obvious, the method is dispatching on the CLASS (not the type) of BOTH arguments to the method, not just the first like in single dispatch.

    Also, it's called “Lisp” these days (note that we have lowercase letters there) 🙂

  7. Drewc, thanks for pointing this out. In the process of making a more concise example, I overlooked that it was completely single dispatch. I updated the post with more inline to what I was thinking and what actually cl-kyoto is going to use this for.

    foo – very true RE: hashtable, but the design of cl-kyoto benefits from polymorphic dispatch. It's not evident just yet, as we haven't created any derived type specializations yet, but that's coming. So hashtable, although for my example would of worked, it's not ideal, as we'll be dispatching based on class types. Thanks though for the tip, I'll keep in in mind.

Leave a comment