Why is Lisp so great? or Why so many parenthesis?

gistfile1.lisp

;; Why is Lisp so great? or Why so many parenthesis?

;; The funny thing about Lisp is that everybody asks why it has so may parenthesis. Quite a few friends of mine who have studied Lisp in college don’t like it that much. I couldn’t really understand why, until I realized they usually take a class that uses the book Concepts of Programming Languages by Robert W. Sebesta as a textbook. I’m in no position to review this book because I haven’t read it. But from what I’ve skimmed, Lisp is not very well represented in this book, to put it very nicely. He describes Lisp only as a functional programming language, tells a little bit about cons cells, and that’s pretty much it! No object orientation in lisp, no syntactic abstraction, no meta-programming, and so on. My feeling is that if I didn’t know Lisp and read this book I wouldn’t be very impressed by Lisp.

;; So why is Lisp so great and why so many parenthesis? These two different questions have the same answer; because Lisp have syntactic abstraction trough the use of macros. If you are used to macros in languages like C, forget it. Lisp macros have nothing to do with C macros, except by the unfortunate coincidence of having the same name.

;; Lisp syntax is composed of lisp expressions and it uses a prefix syntax so expressions can be represented unambiguously. And since lisp expressions can be nested, the representation of the program will be like a tree, pretty much like an abstract syntactic tree. And because lisp code is composed of lisp expressions, the code can be changed in compile-time or run-time. That’s the idea of macros, they are programs that write programs. How that works? Imagine that the language doesn’t have support for a construction like if elif … elif-n else. In most languages there is not much you can do, you can’t define if as a function like if(clause,elif-clause1,elif-clause2) because all the elif statements would be evaluated, and you want one to be evaluated only if the previous clause evaluated to false. In lisp you have special forms, usually defined as macros, that are evaluated differently. You could easily define this kind of if construct if it wasn’t available in lisp.

;; This is a quick, dirty, and incomplete description of lisp syntax and macros. If you want a more deep and complete explanation, I recommend the chapter Syntax and Semantics of Practical Common Lisp. My point here is that you can expand the syntax the language in any way you can.

;; I have friends who are very impressed by Haskell’s syntactic powers (who wouldn’t? it’s a very nice language). For example, the quick sort algorithm can be implemented in Haskell with as little code as:

qsort []     = []
qsort (x:xs) = qsort elts_lt_x ++ [x] ++ qsort elts_greq_x
                 where
                   elts_lt_x   = [y | y < - xs, y < x]
                   elts_greq_x = [y | y <- xs, y >= x]
	

;; While lisp has a more verbose implementation (In Paul Graham
;; ANSI Common Lisp
;; ):

(defun quicksort (vec l r)
  (let ((i l)
        (j r)
        (p (svref vec (round (+ l r) 2))))    ; 1
    (while (< = i j)                           ; 2
      (while (< (svref vec i) p) (incf i))
      (while (> (svref vec j) p) (decf j))
      (when (< = i j)
        (rotatef (svref vec i) (svref vec j))
        (incf i)
        (decf j)))
    (if (> (- j l) 1) (quicksort vec l j))    ; 3
    (if (> (- r i) 1) (quicksort vec i r)))
  vec)

;; Although the lisp version is nice and elegant, why is the Haskell version so concise? Because it uses an appropriate abstraction called list comprehension. A few languages like Haskell, Python, and Miranda have list comprehension built-in. Common Lisp doesn’t. So, how one would implement a major syntactic feature like list comprehension in a language like C or Pascal? It’s “impossible” unless one have access to the source of the particular compiler he is working and change it to implement this feature. That would mean dealing with the parser of the compiler, recompiling the compiler, and so on. It would also mean that the language was changed and that the code written for this compiler wouldn’t run in another compiler.

;; Well in case you haven’t noticed, lisp is different. You can change the language all the time and you don’t have to change the compiler for that. In fact, if you do it in ANSI Common Lisp, your code will run in any Common Lisp implementation.

;; So, in Miranda one can write list comprehension using a syntax like [x | x < - xs ; odd x]. That’s very different from lisp, right? How about implementing list comprehension in lisp and been able to write directly in lisp the expression above as
[x (x < - xs) (oddp x)]?
;; That’s what macros are for.

;; Guy Lapalme has a 20+ lines macro for list comprehension in the article Implementation of a “Lisp comprehension” macro:

(defun open-bracket (stream ch)
  (defmacro comp ((e &rest qs) l2)
    (if (null qs) `(cons ,e ,l2)               ; rule A
        (let ((q1 (car qs))
              (q (cdr qs)))
          (if (not(eq (cadr q1) `< -))          ; a generator?
              `(if ,q1 (comp (,e ,@q),l2) ,l2) ; rule B
              (let ((v (car q1))               ; rule C
                    (l1 (third q1))
                    (h (gentemp \"H-\"))
                    (us (gentemp \"US-\"))
                    (us1 (gentemp \"US1-\")))
                `(labels ((,h (,us)             ; corresponds to a letrec
                            (if (null ,us) ,l2
                                (let ((,v (car ,us))
                                      (,us1 (cdr ,us)))
                                  (comp (,e ,@q) (,h ,us1))))))
                   (,h ,l1)))))))
  (do ((l nil)
       (c (read stream t nil t)(read stream t nil t)))
      ((eq c `|]|) `(comp ,(reverse l) ()))
    (push c l)))

(defun closing-bracket (stream ch) `|]|)

;; This is necessary to tell the lisp reader what to do when it sees an open or closing bracket:

(eval-when (compile load eval)
  (set-macro-character #\[ #'open-bracket)
  (set-macro-character #\] #'closing-bracket))

;; And this is it! Less than 30 lines and you not only have a full implementation of list comprehension, but you have one that is very close to the mathematical representation (and close to Haskell’s and Miranda’s).

;; Having list comprehension, the quick sort algorithm can be expressed as:

(defun qsort (ax)
  (and ax
       (let ((a (car ax))
             (x (cdr ax)))
         (append (qsort [y (y < - x) (< y a)])   ; A
                 (list a)          ; B
                 (qsort [y (y <- x) (>= y a)])))))   ; C

;; Which is very close to the Haskell code. The Haskell code has 5 lines and this has 7. But it hasn’t to do with counting lines. I could represent it with the same number of lines as Haskell’s version, if I kept the A, B, and C expressions together, like in Haskell version (second line).

(defun qsort (ax)
  (and ax
       (let ((a (car ax))
             (x (cdr ax)))
         (append (qsort [y (y < - x) (< y a)]) (list a) (qsort [y (y <- x) (>= y a)])))))

;; If the goal was to reduce lines, I would even get one line less then the Haskell version:

(defun qsort (ax)
  (and ax
       (let ((a (car ax)) (x (cdr ax)))
         (append (qsort [y (y < - x) (< y a)]) (list a) (qsort [y (y <- x) (>= y a)])))))

;; But that’s not the point. The point is that one can implement a different syntactic abstraction in lisp like it was part of the language. And because it captures the basic idea of the abstraction, it serves not only for one particular case but for all kinds of stuff. This is a very powerful technique and lispers use it all the time. Of course one (for example a python user) might think something like “all that trouble to implement what I already got in my language”. But what if you are dealing with an abstraction that is different, specific and is not implemented in your language? In lisp all you have to do is to define a few macros…

 

;; update 2006-03-15:
;; The main point of this article is, of course, to show how Lisp can be extended and changed in any way you want. Don’t have a feature in it? Just write it. But, as Tommy Hallgren pointed to me, Common Lisp already has a good support for lisp comprehension, especially using loop:

(defun qsort (lst)
   (when lst
     (let* ((x  (car lst))
	   (xs (cdr lst))
	   (lt  (loop for y in xs when (< y x) collect y))
	   (gte (loop for y in xs when (>= y x) collect y)))
       (append (qsort lt) (list x) (qsort gte)))))

;; This code is as elegant, concise and easy to understand as the Haskell version. The great thing about Common Lisp is that the language has so many cool things that many times you will not have to extend it, even if you can.

;; The loop macro is very powerful and comprehensive. If you don’t know it very well, start learning today!