More Lists And Lisp
Touretzky Reading: Chapters 3,4
Exercises: 3.4, 3.9, 3.10, 3.13-19, 3.21, 3.22 (w/keyboard)
Exercises: 4.3, 4.4, 4.7, 4.9, 4.12, 4.18, 4.22,
4.28
A couple of oversights from the last lecture:
- CONS should be used with care. The overwhelmingly
normal case is to CONS an atom, symbol or list into another
list. This keeps your lists "well formed" which means that all the
normal operations on lists (car, cdr, etc) will work on
them. To start a list from scratch with an atom or symbol,
CONS it with NIL.
- Although we said that (strictly speaking) order of evaluation
didn't matter, there is a Lisp convention that arguments are
evaluated left to right.
- You need an algorithm for the evaluation model (evaluation of a
function in Lisp). Here is the one that Kurt suggests you use at
first:
- Look up and retrieve the function definition.
- Evaluate the arguments to the function (by passing the
arguments themselves to the LISP evaluation function---
numbers evaluate to themselves, symbols evaluate to
the objects they're bound to, while lists are treated
as function calls and evaluated accordingly).
- Apply the function definition to the evaluated arguments
(i.e., replace the argument place-holders in the new
function definition with the corresponding evaluated
arguments).
- Substitute the result of all that for the original
function call from step 1.
- Go back to step 1 with this new expression.
If you are having trouble understanding the evaluation (substitution)
model, you may want to take a close look at the evaltrace diagrams in
Touretzky (also look at exercise 3.4).
Scoping (3.12)
- Example of quadruple built with two calls to double
-> (defun double (x) (* 2 x))
DOUBLE
> (defun quadruple (x) (double (double x)))
QUADRUPLE
> (quadruple 10)
40
- When the second call to double is made, why is x bound to 20?
- In effect, DEFUN creates a new scope. Lisp is
lexically scoped by default; it has dynamic scoping also. More on
this later.
Equality (Fraternity? Egality?)
Lisp has a variety of equality predicates. Good examples in 6.3 of Steele.
- EQUAL
- This is the predicate you generally want to use. It (more or
less) considers things equal if they print the same.
- EQ
- Two things are EQ only when they are the same object. Thus things
which print the same, but are represented as different objects in the
machine are not eq. Consider:
> (eq '1.2 '1.2)
NIL
> (eq "foobar" "foobar")
NIL
> (eq 1 1)
T
The final EQ is not required to be T, it just is on my
implementation.
- EQL
- Same eq, but is guaranteed to be T for numbers of the same type.
Thus:
> (eql 1 1)
T
> (eql 1 1.0)
NIL
>
The reason you may be need to aware of this is some built-in Lisp
function need to determine equality (e.g. to determine membership in a
set) and you'll need to think about which predicate they use.
Quoting
As mentioned last time, you can use QUOTE to prevent the interpreter
from evaluating an expression. I.e.:
> (car '( 1 2 3))
1
However, there are a variety of common programming mistakes that
involve the QUOTE function:
- Quoting something you should not have.
- This is most common inside a function. Consider:
> (defun foobar (x)
(car 'x))
FOOBAR
> (foobar '(a b c))
>>Error: The value of X, X, should be a LIST
The example here the programming probably wanted to not quote this;
the programmer actually needed the interpreter to evaluate x again.
- Not quoting something you should have.
- These usually result in an error telling you that
something is not defined as a function. This is because
something was the first element of a list that the interpreter
should be evaluated as a function:
> (car (d e f))
>>Error: The function D is undefined
- Quoting the elements inside a list instead of outside it. Lists
should be quoted as a unit.
> (car ('d 'e 'f))
>>Error: Unknown operator (QUOTE D) in (FUNCTION (QUOTE D))
> (car '(d e f))
D
-
EVAL (Digression)
Since someone asked about what function names are bound to last time
(and we'll get into this in more detail later), I thought I might want
to throw out there the idea of the EVAL function. Consider:
> (eval '(car '(1 2 3)))
1
> (eval '(car (list 1 2 3))))
1
> (eval '(car (eval '(list 1 2 3 ))))
1
If you were confused about the equivalence of data and code this may
help you think about it. This is not a high priority item, so if you
don't get it right off, just let it sink in.
Conditionals
Programming without conditions is theoretically impossible, you have
to be able to alter the program's control flow. Lisp has host
of conditional functions; all of them do not imply evaluation of all
their arguments. (Consider if they did! They'd hardly be
"conditional!")
IF
If is the simplest Lisp conditional and the one I prefer. It takes
three arguments, a test part, a true part, and a false part. The test
part is evaluated and if its non-NIL the true part is evaluated,
otherwise the else part. E.g.
> (if (oddp 1) 'odd 'even)
ODD
> (if (oddp 2) 'odd 'even)
EVEN
> (if t 'odd 'even)
ODD
> (if (oddp 1) (+ 2 2) (+ 3 3))
4
> (defun my-oddp (x)
(if (equal (mod x 2) 0)
nil
t))
MY-ODDP
> (my-oddp 10)
NIL
> (my-oddp 5)
T
> (defun my-abs (x)
(if (< x 0) (- x) x))
COND
The original lisp conditional was COND. COND takes a
list of pairs of expressions. Each element (which is a pair) is
considered in order. When an element is considered the first element
is evaluted. If it is true, the COND function evaluates the
second argument and returns the second elements value as its return
value (the COND is done). If the first elemenent of a pair is
false (NIL) then the second element is not evaluated and the next pair
is considered.
(defun relationship (x y)
(cond ((< x y) 'less-than)
((> x y) 'greater-than)
((equal x y) 'equal)))
Be sure to note that if the first part of a pair evaluates to non-nil,
that is the "branch" of the cond that gets executed. Thus, if you
want to have a "else" or "fail-safe" clause in a COND you can
use T. E.g:
(defun relationship2 (x y)
(cond ((< x y) 'less-than)
((> x y) 'greater-than)
(t 'equal)))
Again, the return value of the COND is the value of the 2nd
part of the executed pair, or NIL if no first part of a pair is true.
AND and OR
AND and OR must be considered conditionals in Lisp
because they evaluate their arguments conditionally. They return the
value of the evaluation of the last test evaluated.
This first example is a predicate for small integers. It returns T if
its input is less than 100 and more than 0.
(defun small-positive-number (x)
(and
(< x 100)
(> x 0 )))
It should be noted that some Lisp programmers are found of using
AND in a particular way: "Execute the following tests until one
of them is NIL." Similarly for OR : "Execute the following tests
until one of them is non-NIL."
A More Complex Example
Another good example can be found in Turetsky in section 4.9.
You should be able to understand what the function ground-out does and
explain why it works.
(defun baseball-position (n)
(cond
((equal n 1) 'pitcher)
((equal n 2) 'catcher)
((equal n 3) 'first-baseman)
((equal n 4) 'second-baseman)
((equal n 5) 'third-baseman)
((equal n 6) 'short-stop)
((equal n 7) 'left-fielder)
((equal n 8) 'center-fielder)
((equal n 9) 'right-fielder)
(t 'bad-position-number)))
(defun ground-out (fielder1 fielder2)
(if (equal fielder1 fielder2)
(list 'unassisted 'put-out 'by (baseball-position fielder1))
(cond ((and (< fielder1 10) (> fielder1 6))
(list 'great 'throw 'from (baseball-position fielder1)
'to (baseball-position fielder2)))
(t (list 'ground-out (baseball-position fielder1)
'to (baseball-position fielder2))))))
Recursion
Without too much intro, let me say that recursion is almost always
the way to construct/process lisp (list) data structures. Consider
this function:
(defun ith-element (array desired-index starting-index)
(if (equal starting-index desired-index)
(car array)
(ith-element (cdr array) desired-index (+ starting-index 1))))
This function gets the element from the list numbered desired-index,
if we consider the first element to be numbered starting-index.
What is this? Its an array.
Another interesting example is a dictionary (sometimes called a
table). Assume that a dictionary is set up as a list of 2 element
lists, where the key element is the first of the pair and the value
is the second. E.g. a dictionary that maps first names to last
names ( ( ian smith) (lyman taylor) (alex
snoeren)). Here's a function that can find an element in such a
dictionary:
(defun find-element (dictionary target-key)
(cond ((not dictionary) nil)
((equal (car (car dictionary)) target-key)
(car (cdr (car dictionary))))
(t (find-element (cdr dictionary) target-key))))
What happens if the key is not in the dictionary?
We'll get more into recursion next time.
Back To The CS2360 Home Page
Ian Smith (iansmith@cc.gatech.edu)
Last Modified 9 Jan 95 by Ian Smith (iansmith@cc.gatech.edu)