Transcript Introduction to Artificial Intelligence

For Monday
• Read Chapter 3
• Homework:
– Lisp handout 2
Atoms
• The simplest thing in Lisp is an atom
• Numbers are atoms
• Anything that would be a standard identifier
in C++, etc., is also an atom.
• But alphanumeric atoms must be quoted
when we refer to them (otherwise Lisp
assume that they are variable names and
tries to evaluate them by finding their
contents--which may not exist)
Evaluating Atoms
>9
9
> abc
*** - EVAL: variable ABC has no value
> 32.0
32.0
> 'abc
ABC
> 43.2e02
4320.0
> 'fred
FRED
> 1000000000000
1000000000000
> 'H2O
H2O
Lists
• Lists are the crucial data structure in LISP
• They look like a list of atoms (or lists)
enclosed in parentheses:
(a b c 24 (a b))
• The list above has 5 members, one of them
a list with two members
• Like alphanumeric atoms, lists must be
quoted when you type them in to the
interpreter to keep Lisp from evaluating
them
nil
• nil or () is the empty list
• It is the only item in Lisp which is both an
atom and a list (at the same time)
• It is also Lisp’s value for FALSE (just like 0
is the value for FALSE in C and C++
• Note that Lisp also has a value for true: it is
t
More Examples
> '(a b c)
(A B C)
> ()
NIL
• Note that Lisp is not case sensitive. clisp
echoes everything in uppercase. Some
Lisps use lower case.
Function Calls in Lisp
• (functionname parameter1 parameter2 ...)
• (+ 3 5)
• All functions return values
Taking Lists Apart
• (first ‘(lisp is fun))
lisp
• (rest ‘(lisp is fun))
(is fun)
• (first ‘((the dog) likes me))
(the dog)
Why the Quote?
• Quoting prevents Lisp from attempting to
evaluate the list
• If we had
(first (a b c d))
Lisp would try to find a function a and
apply that function to b c d, then apply first
to the result
The Old Way
• In the original lisp, first was spelled car and
rest was spelled cdr
• Allowed short-cuts
• (cadr ‘(a b c))
≡ (car (cdr ‘(abc))
≡ (first (rest ‘(abc))
• Not often needed, because Common Lisp
provides second, third, etc. to tenth
SETF
• Lisp does use variables
• Values are given using setf
(setf friends ‘(elf dwarf human))
(setf enemies ‘(orc kobold))
(setf pi 3.14)
(setf ab-list ‘(a b) xy-list ‘(x y))
True and False
• Lisp has built-in true and false values
• nil, or the empty list, is the false value
• t is the true value (though any non-nil value
will be interpreted as true)
• No other values can be assigned to these
two atoms
Making Lists
• To add an item to the head of a list, use cons
– (cons ‘a ‘(b c))
(a b c)
• To combine two lists, use append
– (append ‘(a b c) ‘(d e f))
(a b c d e f)
• To make a list from a set of items, use list
– (list ‘a ‘b ‘c)
(a b c)
– (list ‘(a b) ‘c)
((a b) c)
Tricky Stuff
• (append ‘(a b c) ‘( ))
• (list ‘(a b c) ‘( ))
• (cons ‘(a b c) ‘( ))
Shortening Lists
• Use nthcdr to trim multiple off the front of a list
– (nthcdr 2 ‘(a b c d))
(c d)
– (nthcdr 50 ‘(a b c d))
nil
• Use butlast to trim elements off the back of a list
– (butlast ‘(a b c d))
(a b c)
– (butlast ‘(a b c d) 3)
(a)
• Use last to get a list containing just the last
element of a list
– (last ‘(a b c d))
(d)
Length
• The length primitive counts the number of
top-level elements in a list
– (length ‘(a b))
2
– (length ‘((a b) (c d)))
2
– (length (append ‘(a b) ‘((a b) (c d))))
4
Reverse
• The reverse primitive reverses the order of
the top-level elements of a list
– (reverse ‘(a b c))
(c b a)
– (reverse ‘((a b) (c d)))
((c d) (a b))
Association Lists
• Provide hash-type capabilities
• Example:
– (setf sarah ‘((height .54) (weight 4.4)))
– (assoc ‘weight sarah)
(weight 4.4)
• If multiple matches, only first is returned
Numbers
• (/ 1.234321 1.111)
1.111
• (/ 27 9)
3
• (/ 22 7)
22/7
• (float (/ 22 7))
3.14286
• (round (/ 22 7))
3
1/7
• (- 8)
-8
• (- -8)
8
• (/ 2)
1/2
More Numbers
• (max 2 4 3)
4
• (min 2 4 3 6)
2
• (expt 2 3)
8
• (expt 3 2)
9
• (expt 3.3 2.2)
13.827085
• (sqrt 9)
3
• (abs 5)
5
• (abs –5)
5
Defining Functions
• (defun both-ends
(whole-list)
(cons (first whole-list)
(last whole-list)))
• (defun both-end-two-params (l m)
(cons (first l) (last m)))
Let’s Try One
• Define palindromize, a function that takes a
list as its argument and returns a
“palindrome” twice as long as the original.
LET and LET*
• Allow you to bind values to locals
• (defun both-ends-with-let (whole-list)
(let ((element (first whole-list))
(trailer (last whole-list)))
(cons element trailer)))
• LET does binding “in parallel”
• LET* allows binding to occur in sequence–
so variables can use previous variable in
value computation
Equality
•
•
•
•
equal: same expression
eql: same symbol or number (of same type)
eq: same symbol
=: same number
Examples
• (equal (+ 2 2) 4)
t
• (equal (+ 2 3) 3)
nil
• (equal ‘(this is a list) (setf l ‘(this is a list)))
t
• (eql 4 4.0)
nil
• (eql 4 4)
t
• (= 4 4.0)
t
Member
• (setf sentence ‘(tell me about your mother
please))
• (member ‘mother sentence)
(mother please)
• (setf pairs ‘((father son) (mother daughter)))
• (member ‘mother pairs)
nil
Keyword Arguments
• (setf pairs ‘((maple shade) (apple fruit)))
• (member ‘(maple shade) pairs)
nil
; uses EQL by default
• We can change using a keyword
• (member ‘(maple shade) pairs :test #’equal)
((maple shade) (apple fruit))
Type Predicates
• atom
– (atom ‘pi)
t
– (atom pi)
t
– (atom ‘(red black))
nil
• numberp
– (numberp ‘pi)
nil
– (numberp pi)
t
• symbolp
– (symbolp ‘pi)
t
– (symbolp pi)
nil
• listp
– (listp ‘pi)
nil
– (listp pi)
nil
– (listp ‘(a list with pi in it))
t
Detecting Empty Lists
• Use NULL or ENDP
• (null ‘(this is not empty))
nil
• (endp ‘(this is not empty))
nil
• (null ())
t
• (endp ())
t
• (null ‘aSymbol)
nil
• (endp ‘aSymbol)
error
Number Predicates
•
•
•
•
•
•
zerop
plusp
evenp
>
<
< and > may take multiple arguments
AND, OR, and NOT
• AND and OR work as expected
–
–
–
–
–
AND returns nil if any of its arguments return nil
OR return nil if all of its arguments return nil
Both are short-circuiting
AND returns value of last argument if non return nil
OR returns value of first non-nil argument
• NOT turn non-nil values into nil and nil into t
Selection
•
•
•
•
(if <test> <then form> <else form>)
(if (symbolp day-or-date) ‘day ‘date)
(when <test> <then form>)
(when (> temp high)
(setf high temp)
‘new-record)
• (unless <test> <else form>)
COND
• (cond
(<test 1> <consequent 1-1> …)
(<test 2> <consequent 2-1> …)
…
(<test m> <consequent m-1> …))
• (cond
((eq thing ‘circle) (* pi r r))
((eq thing ‘sphere) (* 4 pi r r)))
COND cont.
• If no test matches, returns nil
• Often include a final test clause t (matching
anything)
• (cond
((> p .75) ‘very-likely)
((> p .5) ‘likely)
((> p .25) ‘unlikely)
(t ‘very-unlikely))
Recursion
• Standard method for doing “repetition” in
functional languages is recursion
• (defun myexpt (m n)
(if (zerop n)
1
(* m (myexpt m (- n 1)))))
Recursion Inefficiency
• (defun count-elements (l)
(if (endp l)
0
(+ 1 (count-elements (rest l)))))
Tail Recursion
• If we don’t manipulate the result of a recursive
call before passing it on, that is called tail
recursion
• In a tail recursive function, you need not save any
but the most recent call (because the result of the
last call is the result of all calls)
• Good lisps (and prologs) optimize tail-recursive
functions/predicates, making them just as efficient
as a corresponding loop
Counting More Efficiently
• (defun count-elements-cleverly (lis)
(count-elements-cleverly-aux lis 0))
• (defun count-elements-cleverly-aux (lis result)
(if (endp lis)
result
(count-elements-cleverly-aux
(rest lis)
(+ 1 result))))
Iteration
• Lisp has several constructs that support
iteration.
• DOTIMES is the equivalent of a for loop.
• DOLIST iterates through a list.
• DO and LOOP are general purpose
structures.
DOTIMES
(defun dotimes-expt (m n)
(let ((result 1))
(dotimes (count n result)
(setf result (* m result)))))
DOLIST
(defun count-outlyers (list-of-elements)
(let ((result 0))
(dolist (element list-of-elements result)
(when (or (> element boiling)
(< element freezing))
(setf result (+ result 1)))))))
DO
(defun do-expt (m n)
(do ((result 1)
(exponent n))
((zerop exponent) result)
(setf result (* m result))
(setf exponent (- exponent 1))))
LOOP
• LOOP is simply an infinite loop which can
be exited using a return form.
• If no return statement is ever executed, the
loop is truly infinite.
• Form is simply (loop <body forms>)
Transforming Lists
• MAPCAR applies a function to each
member of a list, producing a list of the
results
• (mapcar #’oddp ‘(1 2 3))
(t nil t)
• Can use with your own functions.
• Do not have to be predicates
More List Processing
• All of the following take a predicate and a
list and return a list based on the predicate
• Remove-if
• Remove-if-not
• Count-if
• Count-if-not
Explicitly Calling Functions
•
•
•
•
•
•
•
•
funcall
(funcall #’append ‘(a b) ‘(x y))
(funcall #’+ 1 2 3 4 5 6)
(funcall #’first ‘(a b c))
apply
(apply #’append ‘((a b) (x y)))
(apply #’+ (1 2 3 4 5 6))
(apply #’first ‘((a b c)))
And More
• Common Lisp is a huge language
• The handouts are intended to encourage you
to try out and explore the language.
• This is the end of lecture on Lisp, but I will
answer questions at the beginning of each
class.