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 clisp command. 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.lisp is a sample Lisp file. To use it, you could say
clisp -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 load command
(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 in lst. (car lst), (cdr lst) --- Traditional names for (first lst) and (rest lst) (cons expr lst) --- Returns the list obtained by adding (the value of) expr onto the front of lst. 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 symbol a and 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, equal tests whether the lists have the same members, while eq tests 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 that and and or can 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 of expr to var. var is 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 of expr becomes the value of the loop or function. expr is optional; if it is omitted, then the value is NIL. (if test expr1 expr2) --- Evaluates test. If it is true, expr1 is evaluated and its value becomes the value of the if expression. In this case, expr2 is never evaluated. If test is false, then expr2 is evaluated, its value becomes the value of the if expression, and expr1 is never evaluated. expr2 is optional. If it is missing and if test is false, then the value of the if is NIL. (loop expr1 expr2 ...) --- Repeatedly evaluates expr1, expr2, ... until a (return) or (return expr) is executed. The value of the loop is the value returned by the (return). (progn expr1 expr2 ...) --- Executes expr1, expr2, once, in order. (This can be useful, for example in an if, 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 the let expression is the value of the last expr. (dolist (var lst) expr1 expr2 ...) --- var (which is not evaluated and must be a symbol) takes on the value of each element of the list lst in turn. For each of these values, the expressions expr1, 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. test1 is evaluated. If it is true, the expressions following test1 are executed. The cond terminates, and its value is the value of the last expression that was executed. If test1 is false, then test2 is checked in the same way. And so on. If all the tests are false, then the value of the cond is 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 email a copy of your file to me. You can also email to me your response to Exercise 1. I expect you to get started on these in lab, where you can ask questions and get help.
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 a let to 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 a recursive function (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 a non-recursive version of the count function from the previous exercise. The name of the function should be countnr. Use dolist in 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. Use cond in your function.