Posts Tagged: lisp

Uncategorized — No Comments
10
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 :-)

(defun merge-sort (lst)
  (let ((size (length lst)))
    (if (= size 1)
        lst
        (progn
          (let ((seq1 (merge-sort (subseq lst 0 (floor (/ size 2)))))
                (seq2 (merge-sort (subseq lst (floor (/ size 2)) size))))
            (merge-it seq1 seq2))))))


(defun merge-it (l1 l2)
  (let ((new-arr (make-array (+ (length l1)
                                (length l2))
                             :fill-pointer 0)))
    (loop for idx from 0 to (+ (length l1) (length l2)) do
         (let ((x (car l1))
               (y (car l2)))
           (when (and (not (null x)) (not (null y)))
             (if (<= x y)
                 (progn
                   (setf l1 (cdr l1))
                   (vector-push x new-arr))
                 (progn
                   (setf l2 (cdr l2))
                   (vector-push y new-arr))))))
    (mapcar #'(lambda (e) (vector-push e new-arr)) (append l1 l2))
    (coerce new-arr 'list)))

view raw mergesort.lisp This Gist brought to you by GitHub.
Uncategorized — 7 Comments
5
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…

(defclass kc-dbm ()
  ()
  (:documentation "A KC database."))
  
(defclass kc-bdb (kc-dbm)
  ()
  (:documentation "A KC B+ tree database."))

(defclass kc-hdb (kc-dbm)
  ()
  (:documentation "A KC hash database."))

(defgeneric put (db key value &key mode))

(defmethod put ((db kc-bdb) key value &key mode)
  (funcall (put-method-for db mode) key value))

(defmethod put ((db kc-hdb) key value &key mode)
  (funcall (put-method-for db mode) key value))


(defgeneric put-method-for (mode)
  (:method ((db kc-bdb) (mode (eql :replace))) #'bdbset)
  (:method ((db kc-bdb) (mode (eql :keep))) #'bdbadd)
  (:method ((db-kc-bdb) (mode (eql :concat))) #'bdbappend)
  
  (:method ((db kc-hdb) (mode (eql :replace))) #'hdbset)
  (:method ((db kc-hdb) (mode (eql :keep))) #'hdbadd)
  (:method ((db-kc-hdb) (mode (eql :concat))) #'hdbappend))
  

;; definitions of methods for kcdbset, kcdbadd, and kcdbappend define methods
;; that store key/value pairs with different behaviors based on whether
;; that key already exists.  
;; For more info see: http://github.com/isterin/cl-kyoto-cabinet
  
;; Usage...

(defparameter *kchdb* (make-instance 'kc-hdb))
(defparameter *kcbdb* (make-instance 'kc-bdb))

;; Will store some_val under some_key
(put *kchdb* "some_key" "some_val" :mode :replace)
(put *kchdb* "some_key" "some_val" :mode :keep)

(put *kcbdb* "some_key" "some_val" :mode :replace)
(put *kcbdb* "some_key" "some_val" :mode :concat)

view raw gistfile1.cl This Gist brought to you by GitHub.

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.