## An Introduction to Common Lisp

### Laboratory Exercise 2

#### Artificial Intelligence Laboratory

[ Goals | Background | Pre-Lab | In-Lab | Post-Lab | More Info ]

### Goals for the Laboratory Exercise

The goal of this lab is to give you some practice working with Common Lisp functions and expressions. In particular, the exercises focus on the idea of higher-order functions, which is one of the benefits of using Lisp and its relatives.

### Background

Common Lisp is an interactive, functional programming language that uses fully-parenthesized prefix notation. As such, it may be quite different from any other language you have used. If so, you will want to do plenty of exercises to become familiar with its syntax and style.

Part of learning any language is learning its vocabulary, the primitive expressions built into the language. The flip side to Common Lisp's simple and uniform syntax is that the language provides over 700 built-in functions. So, as you read the first chapters in Graham's text, pay special attention to the predefined functions they discuss. They will serve as the foundation for the programs we read and write later on.

#### Special Forms

Included in Common Lisp's set of pre-defined operations are a number of special forms. A special form is like a function except that it has its own evaluation rule. Consider setf:

(setf x 10)

This expression assigns the symbol x the value of 10. But setf cannot be a function: if it were, then it would operate on the value of x, not x itself. Instead, it is a special form, with its own evaluation rule: take the first argument literally, evaluate the second argument, and bind the first argument to the value of the second.

We will encounter a number of special forms in the next few labs:

• setf sets a variable or a field to a new value.
• defun defines a function.
• defparameter defines a special variable.
• let binds local variables.
• if provides two-way selection of control.
• cond chooses one of several alternatives.
• function or #' refers to a function by name.
• quote or ' refers to data literal.

#### Higher-Order Functions

One feature that sets Common Lisp apart from most languages that you know is its facility with higher-order functions. A higher-order function takes another function as an argument.

We use this idea in lots of different scenarios in real life. Suppose that I asked you to sort a pile of graded papers. You might ask me whether I want them sorted by name or by score. You then might ask whether I want them sorted in ascending or descending order. Sorting is a function that can be parameterized with functions that specify the comparison to use (less than or greater than) and the field to compare (compare names or compare scores).

Common Lisp makes it easy to write functions like sort by treating functions like any other data. The functions that "define" the sort can be passed as arguments to it.

Among the higher-order functions that you will want to become familiar with soon are Common Lisp's many list-manipulation functions. Graham discusses several in Chapter 3. For example, mapcar applies its first argument, a function, to every item in its second argument, a list. Its value is a list of the answers.

Lisp also provides two ways to invoke a function without using the standard notation:

• apply takes a function and a list as arguments. It returns the result of applying the function to the items in the list.
• funcall takes a function as its first argument and any number of other arguments. It returns the result of applying the function to its remaining arguments.

At first, these two functions will seem a bit strange. But you will later see just how much power they give to the programmer: the ability to select a function and its arguments dynamically. The result is code that can respond to changes in its environment at run-time -- and even apply functions that the programmer did not create!

#### Programming Style

Building a Common Lisp program consists of creating a set of functions that, when applied to an input in an appropriate order, computes the desired output. Given this emphasis on computation as function evaluation, writing large Lisp programs requires a particular sort of programming discipline. (I think that you'll find the same discipline will help you to manage in the face of so many parentheses.)

Two essential components of this discipline are not new to you, but they now become even more imnportant:

• As always, use data abstraction where appropriate! That is, define helper functions with meaningful names that access parts of a data structure. That way, the implementation of a data type (say, a name) is hidden from your client code (say, a first-name accessor function).

• As always, use procedural abstraction where appropriate! That is, define helper functions to implement computations performed by multiple other functions.

Disciplined use of abstractions is an essential part of how humans tame complexity!

### Pre-Lab Activities

Prior to doing the in-lab activity, be sure that you have done the following:

1. Read this document in its entirety.
2. Read Chapter 3 in ANSI Common Lisp.

Please seek clarifications on the topics you see in the first three chapters from me or from one of the Lisp books on reserve at the library. The benefits of early clarification dwarf the cost of obtaining them.

### In-Lab Activities

1. Modify the following function so that it works for negative exponents.
;;
;;  AUTHOR: Peter Norvig
;;
(defun power (x n)
"power raises x to the nth power.  n must be an integer >= 0.
This executes in log n time, because of the check for even n."
(cond ((= n 0) 1)
((evenp n) (expt (power x (/ n 2)) 2))
(t (* x (power x (- n 1))))
))

2. Define functions first-name and last-name that select first and last names, respectively, from a name represented as a list. The name may include honorifics such as Mrs, Sir, Dr, and General. It may also contain typical name suffixes such Jr, II, PhD, and Esq. For example:
>(first-name '(Mark McGwire))
MARK

>(first-name '(Sir Laurence Olivier))
LAURENCE

>(last-name '(Mark McGwire))
MCGWIRE

>(last-name '(Marcus Welby MD))
WELBY

You may assume that the honorifics and suffixes are defined as top-level lists named *name-honorifics* and *name-suffixes*

3. Common Lisp provides a built-in function named assoc that "looks up" a target value in a list of lists and returns the first list whose first element matches the target. For example:
>(assoc 'a '((a 1) (b 2)))
(A 1)

>(assoc 'b '((a 1) (b 2)))
(B 2)

Define a version of assoc named retrieve. Your function should return the first list that has any element that matches the target. For example:

>(retrieve 1 '((a 1) (b 2)))
(A 1)

>(retrieve 2 '((a 1) (b 2)))
(B 2)

>(retrieve 'a '((a 1) (b 2)))
(A 1)

>(retrieve 'b '((a 1) (b 2)))
(B 2)

4. Use mapcar to define the function make-assoc-list. This function takes a list of keys and a list of values as its arguments. It returns as its value an association list of the sort that assoc operates on. For example:
>(make-assoc-list '(a b c d e) '(1 2 3 4 5))
((A 1) (B 2) (C 3) (D 4) (E 5))

#### Deliverables

1. Submit an e-mail message containing only a single, gcl-loadable file containing your solutions to the above exercises.

"gcl-loadable" means that I should be able to do the following:

• save your mail message as a text file (minus the header, of course),
• load the file into CMU/CL or some other Lisp interpreter using the load function, and
• use your functions.

I should not have to edit the file saved from mail. This means that...

• you should not put any extraneous text in your message, such as "Hi, it's me!". Not that I object to personal greetings (hey, I'm a friendly fellow!), but they should be done as separate messages or, if truly necessary, as a Common Lisp comment to your program.

• you send not send your message from a Web browser that encrypts its body as an attachment, adds an HTML-encoded version of the body in the body, adds a banner ad at the top or bottom of the body, or any such thing. I don't want an attachment, just your file as the text of the body of your message.

If you have comments or questions that you would like to send accompanying your submission, please send a separate message.

2. Submit a print-out of your solutions file, properly documented.

Both your message and your print-out should reach me by Wednesday, September 12, at 2:00 PM.

### Post-Lab Exercise

We are still in the phase of learning Common Lisp. As promised, we are moving briskly, leaving you to do a little side reading in an introductory textbook or in a reference manual. I suggest that you do so anyway.

Spend another hour or so playing with Common Lisp after you have completed the in-lab exercises. You would probably be better off to go away for a while and come back for another work session. Try out code that you see in your reading, and experiment with functions to see if you can begin to understand how they work. Try out some of Graham's exercises. The solutions are given in the back of the book, so you can check your understanding immediately.

As a part of your exploration, explain the following Common Lisp transcript:

>(apply 'cdr '((a b c)))
(B C)

>(funcall 'cdr '((a b c)))
NIL

After your second session in the lab, send to me via e-mail your explanation and at least three questions that you have about Common Lisp. Think hard about your questions. Using your time well now to understand Common Lisp will make all the difference in the world in the coming weeks as I ask you to write more, and more complex, Lisp programs.

Your message should reach me by 2:00 PM on Wednesday, September 12.

### Further Information

You have now encountered another way in which Common Lisp is different from many of the languages that know: the same identifier can be used as the name of a function and the name of a data value. For example:

>(setf x 10)
10

>(defun x (y) (+ y y))
X

>(x x)
20

You know how to get the data value associated with x -- just evaluate it:

>x
10

... and you know how to pass its function binding as a value, using the function special form or #'.

>(mapcar #'x (list x))
(20)

How can you find out what the function value associated with a symbol is? Use the function symbol-function:

>(symbol-function 'x)
(LAMBDA-BLOCK X (Y) (+ Y Y))

What you see is something close to the lambda expression that Graham introduces on page 26. (What do you get when you pass a built-in function name to symbol-function?) lambda is the basic internal mechanism with which functions are implemented in Lisp. When you use defun, it builds a lambda expression and associates the expression with the name given.

The Lisp interpreter uses the context in which a symbol appears to determine whether to retrieve the associated data value or function value. In the example above, when x appears in the first position of (x x), the evaluator knows to grab the function value; when it appears in the second position, it knows to grab the data value. That is why we have to use the special form #' whenever we wish to pass a function as an argument: to instruct the evaluator to retrieve the function value associated with the symbol and not the data value.

Eugene Wallingford ==== wallingf@cs.uni.edu ==== September 5, 2001