09 Aug 09 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
target="_blank">“The roots of lisp” in detail. I had simply illustrated the
code in my
target="_blank">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 :
- 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))
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
target="_blank">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.
