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

- Construct a mental model by abstracting away all the details and consider the outermost structure.
- Refine the structure by expanding the next function in the program and create simple examples along the way.
- Evaluate the simple examples created in the previous step by manually/mentally running the input through the code.
- 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))
```

(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)))

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))

(subst1 x y (cdr z))

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,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.

## 0 comments:

## Post a Comment