## CPSC 453: Artificial Intelligence

28 January 2005 Lab: LISP

This purpose of this lab is to give you a chance to get some hands-on experience with clisp and to get you started on your first homework assignment of the term. This Web page includes a brief summary of what we covered in class about Common Lisp, plus information on a few more features of Lisp and clisp. Homework assignments are at the end of the Web page.

## More About Clisp and Files

Clisp, which was demonstrated in class, is an implementation of Common Lisp. It is installed on the cslab computers and can be started using the

clispcommand. You can specify a file on the command line with the "-i" option. The file should contain Lisp code, which is read and executed before the clisp input prompt is displayed. Usually, a file contains mostly function definitions, but it can also define variables, print messages, and do anything else that can be done by evaluating Lisp expressions. For example, the file/classes/s05/cs453/gramgen.lispis a sample Lisp file. To use it, you could sayclisp -i /classes/s05/cs453/gramgen.lispYou could leave off the ".lisp", since this is the default extension for Lisp files. This file defines a function (

sentence) that prints a random sentence from the language generated by a a simple grammar. The grammar is defined in the file. Try it, and take a look at the file if you are interested in how it's done.Another way to use a file is to load it after entering the clisp program. To load the same file in this way, you could use the

loadcommand(load "/classes/s05/cs453/gramgen")at the clisp prompt. (Of course, if you were working in the directory

/classes/s05/cs453, you would just call the file "gramgen" or "gramgen.lisp".Since it's usually easier to edit a file than to type function definitions directly into clisp, the typical way to write clisp programs is to keep a file open in an editor while clisp is also open. When you modify the file, save it and re-load it into clisp. It does no harm to load a file many times -- when you load a file, old function definitions are simply replaced with the new definitions.

## Common Lisp

Here is a summary of some of the most common Common Lisp built-in functions. Some of them were not covered in class, including

cond,dolist,prog, some output functions, and a few of the boolean functions.Note about boolean values: False is represented by NIL, which is the same as the empty list. Any non-NIL value is considered to be true. The special symbol T, whose value is also T, is often used to represent the boolean value true, but any non-NIL value would do just as well.

Remember that in general, functions evaluate their arguments, but there are some important exceptions to this. All exceptions are noted.

(+ x y), (- x y), (* x y), (/ x y)--- Arithmetic functions of numbers. You can do things like (+ x y z w).(random x)--- If x is a positive integer, returns a random integer R satisfying 0 <= R < x. If x is a positive real number, returns a random real number satisfying the same condition. (Note that (random 1) is always equal to 0, while (random 1.0) is a real number between 0.0 and 1.0.)(first lst), (second lst), ... (tenth lst)--- Extract one of the elements of a list(rest lst)--- Returns the list obtained by removing the fist element inlst.(car lst), (cdr lst)--- Traditional names for (first lst) and (rest lst)(cons expr lst)--- Returns the list obtained by adding (the value of)expronto the front oflst. Note that (car (cons expr lst)) is the same as expr, and (cdr (cons expr lst)) is the same as lst.(list expr1 expr2 ...)--- Returns the list whose elements are (the values of) expr1, expr2, ...(append lst1 lst2 ...)--- Returns the list obtained by stringing together the elements of lst1, lst2, ... into a single list.(quote foo)--- Returns its parameter without evaluating it. So, for example, the value of (quote a) is the symbolaand the value of (quote (a b c)) is the list(a b c). (quote foo) is almost always abbreviated using the special notation'foo. For example, 'a or '(a b c).(= x y), (< x y), (> x y), (<= x y), (>= x y), (/= x y)--- Boolean functions for testing numbers. ("/=" is "not equal")(equal a b), (eq a b)--- Tests whether a and b are equal. These have the same effect for numbers, symbols, and strings. For lists,equaltests whether the lists have the same members, whileeqtests whether they actually occupy the same memory location; it is like pointer equality. Thus, (eq '(a b) '(a b)) is false, but after (setq lst '(a b)), (eq lst lst) would be true.(null x)--- Tests whether x is NIL.(atom x), (listp x), (stringp x), (numberp x), (symbolp x), (floatp x), (integerp x)--- Test whether x is of the specified type.(oddp x), (evenp x), (zerop x)--- Test properties of numbers.(not p), (and p q ...), (or p q ...)--- The usual boolean functions. Note thatandandorcan take multiple arguments. Also, AND and OR are often used as control structures: AND evaluates its arguments until one comes out false, OR evaluates its arguments until one comes out true (i.e. non-NIL); if OR finds a non-NIL value, that value becomes the value of the OR.(print x), (prin1 x), (terpri), (princ x)---Output functions. (print x) outputs the value of x, followed by a carriage return. (prin1 x) outputs the value of x without a carriage return. (terpri) outputs a carriage return. Note that the value returned by prin1 or print is the same as the value that was printed. (princ x) is like (print x), except that, for example, quotes around strings are NOT included in the output.(read)--- An input function. Lets the user type in a Lisp expression, and returns that expression as its value.(setq var expr)--- Assigns the value ofexprtovar.varis not evaluated and must be a symbol. Note that the value that is returned by setq is the same as the value assigned to the variable.(defun func (arg1 arg2 ...) expr1 expr2 ...)--- Defines a function named func. arg1, arg2, ... are dummy parameters for the function. func, arg1, arg2, ... are not evaluated and must be symbols. When the function is called, expr1, expr2, ... are evaluated in order. The value returned by the function is the value of the last expression, unless a (return) causes the function to return early.(return expr)--- Breaks out of a loop, function, progn, etc. The value ofexprbecomes the value of the loop or function.expris optional; if it is omitted, then the value is NIL.(if test expr1 expr2)--- Evaluatestest. If it is true,expr1is evaluated and its value becomes the value of theifexpression. In this case,expr2is never evaluated. Iftestis false, thenexpr2is evaluated, its value becomes the value of theifexpression, andexpr1is never evaluated.expr2is optional. If it is missing and iftestis false, then the value of theifis NIL.(loop expr1 expr2 ...)--- Repeatedly evaluatesexpr1,expr2, ... until a (return) or (return expr) is executed. The value of the loop is the value returned by the (return).(progn expr1 expr2 ...)--- Executesexpr1,expr2, once, in order. (This can be useful, for example in anif, if you want to evaluate more than one one expression.)(let ( (var1 val1) (var2 val2) ... ) expr1 expr2 ...)---var1,var2, ... become local variables that are assigned the specified values as their initial values.var1,var2, ... must be symbols, and they are not evaluated.expr1,expr2, ... are then evaluated. The value of theletexpression is the value of the lastexpr.(dolist (var lst) expr1 expr2 ...)---var(which is not evaluated and must be a symbol) takes on the value of each element of the listlstin turn. For each of these values, the expressionsexpr1,expr2, are evaluated. For example, (dolist (x '(a b c)) (print x)) will print a, then b, then c.(cond (test1 expr expr ...) (test2 expr expr ...) . . . (testn expr expr ...) )--- This is the traditional (if... else if... else if...) in Lisp.test1is evaluated. If it is true, the expressions followingtest1are executed. Thecondterminates, and its value is the value of the last expression that was executed. Iftest1is false, thentest2is checked in the same way. And so on. If all the tests are false, then the value of thecondis NIL. Note that the last test is often the atom T, whose value is true, guaranteeing that the last set of expressions will be executed if none of the previous ones are.

## Assignments

These homework assignments are due before class next Friday, February 4. Except for Exercise 1, each exercise is a short Lisp problem. Your solutions to the Lisp problems should be turned in as a single file. Please

Exercise 1:A.L.I.C.E. is a conversation 'bot. It (she?) can be found on the Web at http://www.pandorabots.com/pandora/talk?botid=f5d922d97e345aa1. Spend some time with Alice. Then do the following:(a)Write a PEAS specification for ALICE considered as an agent.(b)Write a paragraph speculating about what the internal architecture of the ALICE bot might be.

Exercise 2:Write a Lisp function(cube x)that returns the cube (x*x*x) of its argument. (Assume that the parameter is a number.)

Exercise 3:We looked at a recursive version of the factorial function in class. Write a Lisp function(fact n)that computes the factorial of n, using a loop. Use aletto introduce any local variables that you need. Assume that the parameter is a non-negative integer. (Try out your function to compute the factorial of 10000.)

Exercise 4:Write arecursivefunction (count lst) that counts the number of elements in a list. For example, (count '(a (b c) d)) would be 3. (Note that an element that is a list is still a single element.)

Exercise 5:Write anon-recursiveversion of thecountfunction from the previous exercise. The name of the function should be countnr. Usedolistin your definition.

Exercise 6:Write a recursive function (atomcount expr) that counts the total number of non-NIL atoms on every level of expr. For example, (atomcount '(a (b c) d)) would be 4, (atomcount 'a) would be 1, and (atomcount nil) would be zero. (Hint: the number of atoms in a non-NIL list is the number in its CAR plus the number in its CDR.)

Exercise 7:If N is a positive integer, then the 3N+1 sequence starting from N is defined as follows:Repeat the following: If N is 1, quit else if N is odd, set N to 3*N+1 else set N to N/2Write a function (ThreeN-count N) that counts the number of terms in the 3N+1 sequence starting from N. Assume that N is a positive integer. For example, (ThreeN-count 3) is 8 because the 3N+1 sequence starting from 3 is 3, 10, 5, 16, 8, 4, 2, 1.

Exercise 8:Write a function (ThreeN N) that returns a list containing the actual 3N+1 sequence starting from N. For example, (ThreeN 3) is (3 10 5 16 8 4 2 1).

Exercise 9:Write a Lisp function that implements the REFLEX-VACUUM-AGENT from page 46 of the textbook. The function takes two parameters. The value of the first parameter is A or B. The value of the second is Dirty or Clean. The return value can be Suck, Right, or Left. Usecondin your function.