A Taste Of Lisp
Touretzky Reading: Chapters 2,3
Exercises:2.5,2.6,2.13,2.16,2.18,2.20,2.26,2.28
The 4 Big Concepts
- Abstraction
- Simplifying something complicated to make it more easily
understood. In other words, throwing away stuff.
- Synthesis
- Putting two simple things together to make something more
complex. (Opposite of abstraction in some sense.)
- Reference
- Using something by its name.
- Primitives
- The building blocks. These cannot be abstracted further; they are
used in the synthesis process (at least at first).
This lecture is mostly about primitives and synthesis.
Functions
- Box Notation (chaining of boxes is effectively synthesis): click
here
for some examples. Lots of good examples can be found in chapter
1 of Touretzky.
- Order Of Arguments Matters
- Number Of Arguments Matters (Some functions can handle variable
number of arguments)
- Translation of box notation into eval notation
- Using a lisp interpreter
- Don't be afraid to TRY stuff. That's the point of
having and interpreter.
- You can learn lots about the the functions both you write and the
system provides by doing things.
- The lisp "interpreter" in a strict sense (the listener window on
your mac) is a giant loop:
- Read A Lisp Expression
- Evaluate it (this is a box called "eval")
- Print the result
Predicates
- Predicates are functions and usually end in P.
- Predicates return T or NIL (generally)
- NIL is considered false
- Anything else is true... why is this useful? There is an implicit
"If TRUE here is the data you need..."
- Consider a function like "and"... explain how it should work.
Some Info About Lisp Primitives
- Atoms: evaluate to themselves.
- Symbols: they are just names. They can evaluate to other values,
but since we are allowing ANY assignments yet...how can these
get values? Function arguments.
- Lists: evaluate to a function call
At this point, its time to think a little bit about how function calls
work in the interpreter. With a few notable exceptions, lisp
evaluates all the arguments to a function before invoking the
function. All the evaluated parameters have their values substituted
for the parameters to the function, then the function is invoked.
This may seem obvious, but is fundamental to correctly writing lisp
code. Consider some examples:
> (+ 1 2)
3
> (+ (+ 3 5) 2)
10
> (+ (+ 3 (+ 2 4) 5) 2)
16
> (+ (+ 3 2) foobar)
>>Error: The symbol FOOBAR has no global value
Note that the evaluations of arguments form a partial order on the
order of functions being called. A partial order means it determines
what evaluation must follow other evaluations. Note that it does not
form a total order! In the last example the outermost addition can
evaluate its arguments either either order; but both arguments
must be evaluated before the final + may be called! There is a
convention that arguments are evaluated left to right; unfortunately,
this is probably too crucial to too much code to ever change. Note
that a "functionally written" program doesn't care which order its
arguments are evaluated in.
Special Forms
Note that I said with a few notable exceptions arguments to
functions get evaluated. The most important of these exceptions is the
function DEFUN which is short for "DEfine FUNction." This is
the way you go about creating new functions. Eg.
>(defun add-one (x)
(+ 1 x))
This defines a new function called add-one which does the
obvious. Note that the x in parenthesis is the formal which gets bound
to the actual's value at the time of function invocation. (Translation: when
you call add-one with an argument, the arguments value gets made the
value of the symbol x within the function add-one.) Note that x is
not evaluated as a function; this is wht makes defun a
special form; one which does not evaluate all its arguments.
Gratutitous Example: Pitching
> (defun era (er ip)
(* (/ er ip) 9))
ERA
> (era 1 9)
1
> (era 9 1)
81
> (defun cy-young-p (era)
(< era 2.0))
CY-YOUNG-P
> (cy-young-p 2.5)
NIL
> (cy-young-p 0.5)
T
>
> (cy-young-p (era 5 72))
T
A pitcher's earned run average is the number of earned runs divided by
the number of inning's pitched multiplied by nine. I defined
cy-young-p to be true whenever a pitcher's ERA was under 2.
Lists
Lists are the most important data structure in Lisp (thus the
name!). You will need to become very adept at using them this
quarter.
- List in box-n-pointer notation (good examples are chapter 2 of
Touretsky)
- Note how to compute number of elements
- First = car (this takes the first element of the list)
- Rest = cdr (this is remaineder of the list)
- special relationship of car and cdr to nil
> (car nil)
NIL
> (cdr nil)
NIL
>
Nil is both a list and an atom.
There is a special form called QUOTE which is the identity
function in lisp. This is useful to allow you to construct lists
directly on the command line or in a program. This is (effectively) a
way to avoid the "lisp always evaluates its arguments" above when
calling a function. QUOTE can be abbreviated with an apostrophe
(') and this is pronounced, "tick."
> (car (a b c))
>>Error: The function A is undefined
> (car (quote (a b c)))
A
> (car '(a b c))
A
- Boxes in boxes an pointers is the use of cons cells which are
created by CONS
- Cons sets the pointers to point at whatever you give it as
arguments; it is quite possible to form things which are not well
formed lists. Consing starting with NIL is the usual procedure.
Back To The CS2360 Home Page
Ian Smith (iansmith@cc.gatech.edu)
Last Modified 9 Jan 95 by Ian Smith (iansmith@cc.gatech.edu)
