Simple Common Lisp Programs

Laboratory Exercise 3


810:161

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 more practice working with Common Lisp. You will read some more challenging Lisp functions. You will also write some simple functions of your own.


Background

Learning to write AI programs introduces you to different techniques of programming, most of which can be used even when not writing AI programs. One such programming pattern is Speak the Problem's Language.

Speak the Problem's Language

You are writing a program to model behavior in a complex domain. Many different problems can be solved in the domain, but you are faced with one problem in particular.

How do you construct your model?

Often, the simplest approach is to map the problem directly onto constructs in your programming language. Consider the problem of generating random English sentences. You could take the language grammar and create a Common Lisp function for each arm that generates that part of the grammar.

You are likely to encounter a number of problems when you use this approach:

These problems arise because your solution is written not in terms of the problem domain but in terms of programming language primitives.

Therefore, use the most natural notation possible to describe and solve your problem. Then write an interpreter to operate over that notation.

This solution requires more work, since you now have two distinct steps before you reach working code. But the result is programs that are more flexible, easier to modify and extend, and easier to apply to new problems.

For small problems, the extra effort will seem unfruitful. However, ask yourself: are you always certain that the problem or set of applications will remain small over time? I usually am not.

The idea behind this pattern "is to work with the problem as much as possible on its own terms and to minimize the part of the solution that is written directly" in your programming language. [Peter Norvig, Paradigms of Artificial Intelligence Programming, Page 42].

If your language grammar is specified inductively, consider using Structural Recursion to implement your interpreter. This pattern documents several useful techniques for writing recursive procedures based on the data structure they process.


Pre-Lab Activities

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

  1. Read Chapter 6 in Graham. Play with some of his functions, using his examples and some of your own.

  2. Read this document in its entirety.

Deliverables

Submit by the end of the day Sunday an e-mail message that contains a transcript of your load and evaluations. Use the built-in Common Lisp function dribble or a Lisp/Emacs buffer to capture your session as a text file.


In-Lab Activities

  1. Define a function multiple-member that returns t if its first argument occurs at least twice in its second, and nil otherwise. For example:
         * (multiple-member 'a '(a b))
         NIL
         * (multiple-member 'a '(a b c a b))
         (A B)
    

  2. Define a function (sequence start stop) that returns a list of the numbers in the range [start..stop], inclusive. For example:
         * (sequence 1 10)
         (1 2 3 4 5 6 7 8 9 10)
         * (sequence 14 37)
         (14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37)
         * (sequence 1 1)
         (1)
         * (sequence 14 10)
         NIL
    

  3. Write a boolean function forall takes takes two arguments, a list and a predicate. A predicate is a one-argument function that returns true or false. forall returns true if and only if the predicate returns true for every element in the list. For example:
         * (defun even (n) (= (mod n 2) 0))
         EVEN
         * (forall '(2 4 6 12) #'even)            ;; Is every element an even number?
         T
         * (forall '(1 2 (3) 4) #'even)
         NIL
         * (forall '(nil nil nil nil) #'null)     ;; Is every element null?
         T
         * (forall '(nil definitely-not nil) #'null)
         NIL
    

  4. Write a function prime that takes a positive integer, n > 1, as an argument and returns true if n is prime. A number is prime if it is not divisible by any number in the range [ 2..(floor (sqrt n)) ]. sqrt takes the square root of its argument, and floor rounds down. Use your answer for forall to Problem 3 above, which you may assume is correct. For example:
         * (prime 2)      ==> T
         * (prime 3)      ==> T
         * (prime 4)      ==> NIL
         * (prime 5)      ==> T
         * (prime 6)      ==> NIL
         * (prime 17)     ==> T
         * (prime 18)     ==> NIL
         * (prime 19)     ==> T
         * (prime 20)     ==> NIL
         * (prime 2000)   ==> NIL
         * (prime 2003)   ==> T
    

  5. Define a function that takes one argument, a number, and returns the largest argument it has seen so far. For example:
         * (max-magic 10)
         10
         * (max-magic 9)
         10
         * (max-magic 11)
         11
         * (max-magic 10)
         11
         * (max-magic -2)
         11
         * (max-magic 100)
         100
    

Deliverables

By 4:00 PM on Wednesday, September 19, submit a print-out and an e-mail message containing only a single, gcl-loadable file containing your solutions to the above exercises. If you forget what "gcl-loadable" means, please review my instructions in Laboratory Exercise 2.

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


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. Here are a couple of fun little exercises that should begin to feel more natural after you've read the assigned parts of Graham and studied the Lisp code you've been shown:

Send to me via e-mail your solutions by Wednesday, September 19, at 4:00 PM.


Further Information

The approach I used in Speak the Problem's Language is often helpful because it isolates the problem at hand, the forces that affect how you think about the problem, the solution, and the resulting product in a way that makes the lesson clearer than traditional textbook exposition.

A growing community of industry software engineers is exploring this approach to communicating knowledge. These folks are interested in documenting why their systems work and in helping novice designers learn successful techniques. The so-called software patterns community originated with folks interested in documenting object-oriented design expertise and has now spread into numerous other sub-disciplines of computer science.

Speak the Problem's Language is written in one of the forms favored within the patterns community. This form strives to present the problem, forces, and solution in a way that makes as clear as possible when and why the pattern is useful.

I have written, presented, and published several patterns and pattern languages. You saw a link to one above: Roundabout, which I presented at the 1997 Pattern Languages of Programming conference. (That is the conference I am aattending right now.) Roundabout describes techniques for doing recursion over inductively-defined data. (If you had me for Programming Languages, then you will recognize this material! Those of you who haven't may want to take a look at it...) At the 1999 Pattern Languages of Programming conference, I published Envoy, a pattern language for managing state in a functional program. Feel free to read Envoy now, but you probably have plenty to keep you busy. I will ask you to read Envoy later in the semester when we consider how to implement an object-oriented programming style in Lisp.

Since so many of AI programming's techniques involve creation and interpretation of new languages, you should not be surprised that there is a link between a technique such as Speak the Problem's Language and Roundabout.

My main research goals these days involve documenting patterns of AI design and programming, to create a handbook of techniques for generating useful, reliable, and modifiable AI programs. I have published two patterns of knowledge-based system programming, Sponsor-Selector and Structured Matcher. Sponsor-Selector also appears as a chapter in the book Pattern Languages of Program Design 3. Later this semester, I will ask the whole class to read Structured Matcher and to use it as a way to build a simple knowledge-based system.

As part of my effort to document AI programming patterns, I will continue to study Graham's code, trying to identify the "secret" patterns that distinguishes the code of a Lisp master from that of a novice. If you are interested in being involved on this or a related project, please let me know! I'd even be happy to talk with you if you are interested in patterns in some other area of computer science, too, such as operating systems or software engineering.


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