Page 69 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Unit 4: LISP

tree stumps is actually a “pair” of things: an item on the first tree stump, and a pointer leading Notes
to a list of 9 other tree-stumps with things on them. So what is that 9-tree-stump list? It is ALSO
a pair of items: the item on the first tree stump, and a pointer to a list of 8 other tree-stumps with
things on them. This subdivision goes all the way down to the last tree stump which is STILL a
pair of items: the item on the tree stump, and a pointer to nothing (NIL).
Now, why is this distinction important? Because the three basic list-manipulation functions in
lisp are based around this paradigm. Look at the following function call:
> (cons ‘B ‘(O R D E R))
(B O R D E R)
It takes two arguments (an element and a list) and puts them together as a list. Basically, it’s the
same as putting something on another tree-stump (‘B) and tying that tree-stump’s branch to the
first stump in the original list. How about these two:
> (car ‘(L I S P))
L
> (cdr ‘(L I S P))
(I S P)
The CAR function takes a list as a parameter, and returns the first part of the pair (the thing on
the first tree stump). The CDR function takes a list as well, and it returns the SECOND part of the
pair (the list of other tree stumps that the first one points to). If you think about it, you’ll see why
this is important: you can do pretty much anything to a list with those three functions. They are
the building blocks of any functionality you need regarding a list. Here is a good example, it’s
one of the practice exercises from Paul Graham’s “ANSI Common LISP”:
(defun our-list-copy (lst)
(if (atom lst)
lst
(cons (car lst) (list-copy (cdr lst)))))
We’ve just written a new function called “our-list-copy” that takes a list as a parameter and
returns a copy of it by recursively traveling through the list and “CONS”-ing each first-element
(CAR) with a copy of the rest of the list (CDR).

Did u know? This kind of development is core to what lispers describe as bottom up
programming. You start out writing simple, minimalist functions. As your needs become
specific you combine these low-level functions into more powerful functions, which are
in turn used to write domain-specific functions, which in turn become a kind of language
for the construction of your top-level program. Basically, you’re adding to the language as
you go.

4.3.3 List Manipulation—Step 3

Most programs cannot be written without branching at some point. It’s all well and good to be
able to execute various statements, but it doesn’t really become useful until the program can
decide to take a certain action based on some evaluation of a condition (i.e., if it’s below 40
degrees, I will wear a coat outside).
When writing lisp, you base all programmatic logic on predicates (technically this is true for
any language, but because of the prefix syntax all predicates FEEL like predicate functions rather
than X == Y). In mathematics, a predicate is either a relation or the boolean-valued function that
amounts to the characteristic function or the indicator function of such a relation. This is essentially
true in lisp as well: a predicate is a function that returns a true or false value regarding a certain
characteristic of it’s parameter(s). False is represented by NIL, and true is anything that is
Not-NIL (most commonly represented by T).

LOVELY PROFESSIONAL UNIVERSITY 63