A method to understand lisp code

In the next few posts, I intend to go over the code given by Paul graham in his article "The roots of lisp" in detail. I had simply illustrated the code in my previous post but, here, I will be breaking the code down and explaining it with examples. The reason I want to do this is twofold. Firstly, to explain the way the code works. Secondly, it helps me to recall whatever I learnt and the methods and techniques that helped me to best understand it.

The method I use to understand lisp code is as follows :

1. Construct a mental model by abstracting away all the details and consider the outermost structure.
2. Refine the structure by expanding the next function in the program and create simple examples along the way.
3. Evaluate the simple examples created in the previous step by manually/mentally running the input through the code.
4. Repeat steps 2) & 3).

The subst1 function is given below, the first non-trivial function in "The roots of lisp" article.

(defun subst1 (x y z)
     (cond ((atom z)
            (cond ((eq z y) x)
                  ('t z)))
            ('t (cons (subst1 x y (car z))
                      (subst1 x y (cdr z))))))
     

subst1 takes in three arguments. The first argument x can be any expression while y is an atom and z may be a list or an atom. The subst1 function then replaces every occurence of y in z by x.

This is how my method for understanding subst1 would look like

Step 1) The outermost skeletal structure of subst1

 (defun subst1( x y z)
       (cond (p1 e1)
             (p2 e2)))
     

Step 2) Expanding p1 and e1

Now, p1 is (atom z) and e1 is another cond of the form

     (cond ((eq z y) x)
           ('t z))
    

It is pretty easy to see what the e1 form does so I did not abstract the details out. What it does is if z == y it returns x otherwise it returns z. Now that we know what (p1 e1) does we can expand the subst1 function and have a look inside

    (defun subst1( x y z)
       (cond ((atom z)
              (cond ((eq z y) x)
                  ('t z)))
              (p2 e2)))

    ;Some examples where z is an atom

    (subst1 'a '() '())      ;z = '() is an atom
    (subst1 'a 'b 'b)        ;z = 'b is an atom
    (subst1 'a 'b 'c)        ;z = 'c is an atom
    (subst1 '(+ 1 2) 'b 'b)  ;z = 'b is an atom

Step 3) Running the example through the code

(subst1 'a '() '())
        ==> (cond ((atom '())
                    (cond ((eq '() '()) 'a)
                           ('t '())))
                  (p2 e2))
        ==> (cond ((eq '() '()) 'a)
                   ('t '()))
        ==> a

    (subst1 'a 'b 'c)
        ==> (cond ((atom 'c)
                   (cond ((eq 'c 'b) 'a)
                           ('t 'c)))
                  (p2 e2))
        ==> (cond ((eq 'c 'b) 'a)
                   ('t 'c))
        ==> c

N.B.:- The above process may become cumbersome if you attain a certain level of proficiency. At that time, it is to be discarded and to be used sparringly only for code that becomes really complex.

Step 2) Expanding (p2 e2)

The predicate, p2 is 't which means that if p1 fails then e2 is definitely executed. In other words, if z is not an atom, e2 is executed and the program returns the result of evaluating e2 which is

   (cons (subst1 x y (car z))
               (subst1 x y (cdr z)))

The above code is at the heart of the subst1 function and it consists of two recursive calls to itself. First, as you can see the cons function is being used here. So you must know what the cons function does. You can read it up here or in info.

Thus,

   (cons '5 '(4 3 2 1))
        ==> (5 4 3 2 1)

Now what the e2 form does is, it takes the first element (or car or head) of the list z and calls

    (subst1 x y (car z))

Then it evaluates subst1 on the tail (or cdr) of z.

    (subst1 x y (cdr z))

Finally, it calls a cons to recreate the list z with elements of y replaced by x. Note that the structure of the list remains unchanged, only the elements change.

Let's create a few examples for this,

    (subst1 '5 'x '(+ x 1))
    (subst1 '5 'x '(+ (- x 2) 1 x)) 
    (subst1 'm 'b '(a b (a b c) d))

Step 3) Running the examples through the code

Now, that we have expanded (p2 e2) we can view the entire code of subst1 and run our examples through the entire code,

(defun subst1 (x y z)
     (cond ((atom z)
            (cond ((eq z y) x)
                  ('t z)))
            ('t (cons (subst1 x y (car z))
                      (subst1 x y (cdr z))))))

Let's run the example given below

    (subst1 '5 'x '(+ x 1))

The function calls that will be made can be viewed as a tree as follows,

                        (subst1 '5 'x '(+ x 1))
                                |
                                |
                               cons
                              /    \
                             /      \ 
    (subst1 '5 'x (car'(+ x 1)))   (subst1 '5 'x (cdr '(+ x 1)))      
                |                              |
                |                              |
      (subst1 '5 'x '+)              (subst1 '5 'x '(x 1))
                                               |
                                               |
                                              cons
                                             /    \
                                            /      \
                   (subst1 '5 'x (car '(x 1)))    (subst1 '5 'x (cdr '(x 1)))     
                                |                              | 
                                |                              | 
                      (subst1 '5 'x 'x)             (subst1 '5 'x '(1))
                                                               |
                                                               |
                                                              cons
                                                             /    \
                                                            /      \
                                    (subst1 '5 'x (car '(1)))    (subst1 '5 'x (cdr '(1)))  
                                                |                            |
                                                |                            |
                                      (subst1 '5 'x '1)            (subst1 '5 'x '())

The above tree is the complete expanded expression tree. The manner in which the whole thing is evaluated will differ depending on the intepreter used. If the interpreter evaluates in a depth first manner, which I think is the standard way in which lisp does it, we will get the answer in the following manner

                        (subst1 '5 'x '(+ x 1))
                                |
                                |
                               cons
                              /    \
                             /      \ 
    (subst1 '5 'x (car'(+ x 1)))   (subst1 '5 'x (cdr '(+ x 1)))      
                |                    
                |                    
      (subst1 '5 'x '+)

which in turn evaluates to

                        (subst1 '5 'x '(+ x 1))
                                |
                                |
                               cons
                              /    \
                             /      \ 
                            '+    (subst1 '5 'x (cdr '(+ x 1)))

To convince yourself, see the answer of the expressions given below

  (cons '+ (subst1 '5 'x (cdr '(+ x 1))))
  (subst1 '5 'x '(+ x 1))

Expanding the tree further,

                        (subst1 '5 'x '(+ x 1))
                                |
                                |
                               cons
                              /    \
                             /      \ 
                           '+      (subst1 '5 'x (cdr '(+ x 1)))      
                                               |
                                               |
                                     (subst1 '5 'x '(x 1))
                                               |
                                               |
                                              cons
                                             /    \
                                            /      \
                   (subst1 '5 'x (car '(x 1)))    (subst1 '5 'x (cdr '(x 1)))      
                                |                             
                                |                             
                      (subst1 '5 'x 'x)             

                                 ||
                                 ||
                                 \/

                                  
                        (subst1 '5 'x '(+ x 1))
                                |
                                |
                               cons
                              /    \
                             /      \ 
                           '+      (subst1 '5 'x (cdr '(+ x 1)))      
                                               |
                                               |
                                     (subst1 '5 'x '(x 1))
                                               |
                                               |
                                              cons
                                             /    \
                                            /      \
                                           '5     (subst1 '5 'x (cdr '(x 1)))     
                                                               |
                                                               |
                                                    (subst1 '5 'x '(1))
                                                               |
                                                               |
                                                              cons
                                                             /    \
                                                            /      \
                                     (subst1 '5 'x (car '(1)))    (subst1 '5 'x (cdr '(1)))   
                                                 |                            |
                                                 |                            |
                                     (subst1 '5 'x '1)                (subst1 '5 'x '())



                                 ||
                                 ||
                                 \/


                                  
                        (subst1 '5 'x '(+ x 1))
                                |
                                |
                               cons
                              /    \
                             /      \ 
                           '+      (subst1 '5 'x (cdr '(+ x 1)))      
                                               |
                                               |
                                     (subst1 '5 'x '(x 1))
                                               |
                                               |
                                              cons
                                             /    \
                                            /      \
                                           '5     (subst1 '5 'x (cdr '(x 1)))     
                                                               |
                                                               |
                                                    (subst1 '5 'x '(1))
                                                               |
                                                               |
                                                              cons
                                                             /    \
                                                            /      \
                                                           '1      '()


                                 ||
                                 ||
                                 \/


                                  
                        (subst1 '5 'x '(+ x 1))
                                |
                                |
                               cons
                              /    \
                             /      \ 
                           '+      cons
                                  /    \
                                 /      \
                                '5     cons
                                      /    \
                                     /      \
                                    '1      '()


                                 ||
                                 ||
                                 \/


                               (+ 5 1)

Thus, the above method works well for me. I have not explained the complete process exactly but, the basic idea is to abstract away and then make things concrete one by one. Also I do not always go in detail when I get a good understanding or a strong intuitive feeling as to how it works. Activities such as drawing the expression trees is extremely good if you want to be more formal and more correct.

If you liked this, do drop in your comments and let me know what you think. If you have any issues, again, your comments will really helpful.