Posts Tagged: lisp

Feb 11

Merge sort in lisp

I’m currently taking (online) MIT’s algorithms course. I needed a good brush-up on algorithms, starting with the basic theory. I’m going to jump in to help a buddy working on a graph database in lisp Vivace Graph, which should be an open source competitor to AllegroGraph. Allegro has probably the best graph db out there right now. There are some competitors in the java world, but they are either expensive or don’t provide enough features, or don’t provide APIs outside of java. Allegro has an extensive list of client libs. I’ll write up more on the graph db in some future, for now, I got back into lisp and implemented the simplest alg (merge sort) in it.

The reason I’m posting is to get some comments. I’d love to hear your thoughts on how a lisp nOOb can improve this 🙂

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.