I have recently started with Paradigms of Artificial Intelligence Programming in order to learn Common-Lisp. I did use it for the AI course that I had in college. The course was mostly a joke, with just a few low-level algorithms being covered (and these too were taught in Prolog), but getting some information about AI I came across Lisp and read through Paul Graham’s excellent book ANSI Common Lisp. Although I didn’t get much chance to use Lisp anywhere else after that, the book and its exercises made me understand recursion at the very basic and grand level.

Now I have a rekindled interest in CL and plan to get a lot of learning out of PAIP. I also have Norvig’s other book AI: A modern approach, but somehow PAIP seems more approachable. The former seems a lot more technical and verbose than PAIP and I think for a quick study the verbosity gets in the way. I would still love to finish it someday, it’s been there since the days I took AI classes in college (only to realise nothing is going to come out of this book that’ll help me get good grades).

Coming back, I do have been awestruck while reading PAIP multiple times. I’m not going 100% in-depth (and not finishing each and every exercise), but the code is just so terse and beautiful that I cannot just help thinking that Mr. Norving thinks at a much higher level. The code has a very high amount of composability. Moreover the programs are minimalistic, to the point of being almost naked (in the sense of being beautiful that comes with nakedness).

So I’m at chapter 6 and here’s the program to search a tree:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

(defun tree-search (states goal-p successors combiner)
  (cond ((null states) nil)
        ((funcall goal-p (first states)) (first states))
        (t (tree-search
                 (funcall combiner
                          (funcall successors (first states))
                          (rest states))
                 goal-p successors combiner))))


(defun depth-first-search (start-state goal-p successors)
  (tree-search (list start-state) goal-p
               successors #'append))

(defun breadth-first-search (start-state goal-p successors)
  (tree-search (list start-state) goal-p
               successors #'prepend))

(defun prepend (x y) (append y x))

It’s known that DFS and BFS use stack and queue respectively, although the algorithm to do the search is same for both internally. But this is like taking a stab at the heart of the entire thing - like removing the clothes that gave the emperor a grandiose feeling.

And then he goes on to extend the tree-search function to use best-first and beam-search algorithms. This is just extensible code at its finest. Language comes second, and I am pretty sure that the same algorithm can be copied into other languages (for instance JS, Python which have the similar minimalistic feel that comes from this code), but yeah the language is also one of the important points.

I’m looking forward to see more CL written in the lispy and elegant way.