List Programming
Volume Number: 1
Issue Number: 6
Column Tag: LISP LISTENER
MACINTOSH List Programming
By Andy Cohen
Welcome to The Lisp Listener Window! This is the first of what we hope will
become a regular column on programming Lisp on the Apple Macintosh. Lisp stands for
List Programming and it is used for a very special type of computer programming in a
field typically refered to as Artificial Intelligence or AI. Over the past five years AI has
become a very popular and controversial topic. It has roots in Computer Science and
Cognitive Psychology. The Psychologists found ways of describing human mental
processes and the computer scientists have programmed these processes into
computers, thereby getting the computer to perform human-like processing tasks.
Computers however, are definitely not one to one analogies to people. Computers
process data. Human processes, on the other hand, deal with concepts. Lisp was
designed specifically to handle the coding of these concepts by providing an object
oriented, programm- ing environment. This development has provided us with
programs that generate information by mimicking the same form of inductive
reasoning as a person. In the case of specialized knowledge domains, these programs
have been called Expert Systems. I will eventually try to emphasize on Lisp examples
which will.
Take advantage of what makes Lisp different from the other languages covered in
this publication. That is, it’s ability to manipulate objects, rather than just data, in a
fashion similar to the way people do.
Is Lisp on the Mac Serious?
A friend asked me a little while ago if we will be able to program serious AI
applications using Lisp? My first reaction was that we can’t. The smallest development
system for an AI application has quite a bit more random access memory (from two to
five Mbytes) and usually has a hard disk with more then 30 megabytes of space on
which to read or write. The best we can hope for in the Macintosh environment (at the
time this article was written!) is one megabyte of RAM and ten megabytes on a hard
disk using the Mac XL. However, I also noted that sometimes the application is only
developed using Lisp and then when finalized, the code is translated into a lower level
language, such as Fortran. This recoding is done for speed and compactness.
My secondary feelings were yes, we probably can develop an AI application on the
Mac to some extent, but the program will have to be translated into Pascal, C or even
68K Assembly. As it turns out, the version of Lisp coming from Expertelligence will
allow us to do quite a bit with just 512K and two floppies. I’ll describe this package in
detail later. Will we be able to use the Mac as an AI development machine? I am still
sceptical, however I have a feeling that time will show us that it just might be
possible. If you are asking, why would somebody program Lisp on the Mac at this time?
I can only say one should use Lisp on the Mac for educational purposes. Heck,
educational purposes are more than enough considering that a complete Lisp
development system can cost over $75,000.00! Also consider that just a couple of
years ago having Lisp on a micro-computer was almost as fictional as verbally asking
your Mac to open the pod bay doors.
Different Lisps
Lisp comes in many different versions just like any other computer language.
There is Zetalisp, Interlisp, Maclisp (not Macintosh) and some I’m sure I’ve never
heard of. The versions of Lisp that are or will be available on the Macintosh are very
close to Common Lisp. An excellent text for Common Lisp is “Lisp” 2nd ed. by Winston
and Horn. All that I discuss in this article regarding Common Lisp follows what is in
that text.
At the time this article was written only one version of Lisp was available. It is
called XLisp and was developed by David Betz. It was programmed in C and was
considered by Betz as an experimental language. There are two versions of XLisp that I
have seen on the Mac; version 1.2 and version 1.4. Both versions of XLisp are
interpreted. Only version 1.4 however, can handle object oriented programming.
Unfortunately, XLisp 1.4 takes up most of the available memory on a 128K Mac. Either
version of XLisp however, will work fine on a 128K Mac for demonstrating some of the
arithmetic functions in Common Lisp syntax. The biggest advantage of XLisp is that it is
Public Domain software. In other words, it is free. Look for it on Compuserve’s MAUG
or to your local users’ group. Chances are it is available in one or more versions.
Lisp and Arithmetic
Enough small talk ( oops, sorry about that!) , now lets take a first look at Lisp.
The most fundamental object in Lisp is an Atom. The atom is used in groups to produce
Lists. Atoms and lists make up what are called expressions.
Okay, lets get a little more detail. A procedure specifies how something is
performed. For example “+” or plus sign is a procedure. The “+” by itself is called a
primitive. Numbers or symbols are refered to as arguments. Therefore the numbers
2.56 and 8.34 are arguments. These elements or atoms can be placed into a List:
(+ 2.56 8.54)
The procedure “+” will then operate on the arguments 2.56 and 8.54 to produce
11.1. A bunch of procedures which work together are a program. More examples of
lists are the following:
(+ 2 2)
(* 103 346)
(/ 35 46)
If you have XLisp try typing these in yourself. The answers are produced when
the carriage return is made, then displayed beneath the list. I used bold lettering to
indicate the output.
(+ 2 2)
4
See. Isn’t that easy? Lets make things more interesting. Procedures can also be
more complex, e.g. MIN and MAX (If you are trying this with XLisp be sure to use the
lower case):
(MIN 53 37 95 23)
23
(MAX 74 37 49 20)
74
MIN will print the smallest argument in the list. MAX will print the largest.
One can also use primitives typically used with multiple arguments with
singular arguments.
(- 7)
-7
(- -3)
3
In the first case the negative or subtract symbol turns the argument into a
negative equivalent. In the second the “-” turns the negative argument into a positive
just as -1*-3=3.
Lists can contain other lists.
(- (* 4 9) (+ 8 32))
-4
The equivalent of the above is as follows:
(- 36 40)
-4
As we can see the list is organized and performed in a typical hierarchical
manner. A list, therefore, is made up of a left parenthesis, followed by any number of
atoms or lists and concluded with a right parenthesis.
Dissecting Lists
Enough of numbers, lets start to use symbols as arguments.
(A B C)
or
(Alpha Beta Cookies)
Now lets use more sophisticated procedures. CAR and CDR are used to pull
arguments out of lists. I’m told CAR stands for “Contents of Address Register” and CDR
stands for “Contents of Data Register”. I’m sure there is some meaning in these titles
with regard to the result, but that’s not important right now. What is important is
what these procedures do.
(CAR ‘(Alpha Beta Cookies))
CAR returns the first argument in the list. Note that we are using a list in a list.
(CDR ‘(Alpha Beta Cookies))
(Beta Cookies)
CDR returns the list minus the first argument. What if I am looking for the
second argument in a list of three? In this case the CAR and CDR procedures can be
nested.
(CAR (CDR ‘(Alpha Beta Cookies)))
Beta
In the above example CDR produces the list,
(Beta Cookies)
then CAR produces Beta. I hope you’ve noticed the single quote after the CDR above as
well as in the other samples. This is how Lisp knows that the CDR in the above sample
is a procedure and not just another argument. Without the single quote the following
would be the result:
(CAR (CDR (Alpha Beta Cookies)))
CDR
CDR in this case was not considered by Lisp as a procedure. The CAR procedure
looked to the first argument, in this case the CDR, and displayed it. After playing a bit
with these two procedures and a bunch of arguments one can see ways of making sets of
procedures which will perform specific kinds of searches.
I’ve tried to give a very brief introduction to Common Lisp simply for the
purpose of giving some impression of what Lisp looks like. Most of the above can be
done using XLisp. Since Xlisp is an experimental program and Experlisp from
Expertelligence will be a relatively serious Lisp development package, this column
will probably deal exclusively with Experlisp. Next month The Lisp Listener Window
will give a detailed description of Experlisp as well as discuss composing nested CARs
and CDRs, symbolic assignment and a whole bunch of related procedures. In future
installments I would like to review detailed examples as well as compare the
performance of our little Mac to those of the Lisp machines from Xerox and Symbolics.