Macintosh Common Lisp and CLOS

Jeffrey W. Stulin

This article is the first in a series of three on Macintosh Common Lisp (MCL) and Common Lisp Object System (CLOS).

MCL is worth learning about, even for those of you who don't think you'll use it-because it's likely that there will eventually be Macintosh object programming environments and operating systems to come that are based upon technology strongly influenced by Lisp.

This first article introduces the MCL series, and presents a basic Lisp tutorial. The second article will discuss the MCL environment and tools, and introduce CLOS. The third article will present an MCL version of the author's MacApp sample program Game Of Life, and discuss how developing Life in MCL was different than developing it in MacApp and Pascal.

Macintosh Common Lisp 2.0b1 (MCL) offers a refreshingly different approach to software prototyping and development. In this series of three articles, I'll describe the feel of development using MCL, and explore how MCL development can lead to a lower "cost of innovation" than development using MPW and MacApp.

AN author's dilemma

The classic approach of showing a language is to compare its syntax and features with those already known by the reader. Alas, Lisp has almost no syntax. Even if it did, that approach would be a dismal failure. What makes Lisp interesting is its "feel of development," which has no equivalent in Pascal or C++.

Do you remember first learning about object programming? How many times did you have to hear about classes, instances, and inheritance before the concepts behind the words finally took root? Do you truly understand them, or are there still things for you to learn?

Lisp concepts are even more different than the concepts of object programming. A new vocabulary filled with subtle connotations must be mastered. This can't be done by reading a formal specification of the language. (Not to mention that the current definition of Lisp is contained in a 1000 page book with a 10-point typeface.)

So my dilemma is this: do I take the safe route and compare Lisp syntax to that of Pascal, or do I live dangerously, and try to present the "feel" of Lisp instead of Lisp itself?

Since "feel" is subjective, I would risk accusations of language bigotry and unprofessionalism. Perhaps even have my articles rejected. How embarrassing. Oh, well. Life is short.

This first article is philosophical. It introduces the series, presents the concept of "cost of innovation," explains (without yet proving) that Lisp provides a much lower cost of innovation than MPW and MacApp, presents a basic Lisp tutorial, and concludes with a guide and bibliography on how to learn Lisp.

The second article in the series will be more concrete. It will present additional Lisp concepts, discuss the MCL development environment and tools (editor, debuggers, etc.), and present CLOS, the Common Lisp Object System.

The third article will pull everything together. It will present the sample program Game Of Life and discuss how developing Life in MCL was different than in Pascal and MacApp. Both the development process and the quality of the final programs will be considered, and source code for both versions will be included on the FrameWorks Disk..

What is Lisp?

Lisp is the second oldest programming language still in use. It was developed by John McCarthy at MIT in the 1950's. Lisp was originally designed for problems in calculus, logic, game playing, and artificial intelligence.

Lisp rapidly evolved into incompatible dialects reflecting the needs of several organizations; for example, MacLISP at MIT, ZetaLisp for Lisp machines, and FranzLisp for Unix.

In 1984, a new dialect, Common Lisp, sought to create a portable, unified language on which further extensions could be built. Common Lisp was well received and is now working its way toward being an ANSI standard.

Many approaches to object programming have been implemented in Lisp. There has been much cross-fertilization between Lisp and SmallTalk. A standard object programming extension to Common Lisp, called Common Lisp Object System (CLOS), which includes many ideas from these earlier approaches, has recently been accepted as part of the forthcoming ANSI standard. CLOS is based on classes, multiple inheritance, generic functions, and methods. It will eventually include a meta-object protocol. CLOS's flexibility has to be seen to be believed.

Not everyone was happy with the standardization of Lisp. In particular, the fans of Scheme, a Lisp dialect oriented toward teaching, objected to several decisions incorporated in the standard. So it can be expected that other Lisp dialects will continue to be popular.

A few years ago, Apple acquired Coral Software, whose flagship product was a version of Lisp based on the 1984 Common Lisp standard. This was before CLOS, so Coral developed their own object programming standard, Object Lisp, with a Macintosh Class library built on top.

Apple has renamed the product Macintosh Common Lisp (MCL), replaced Object Lisp with CLOS, brought it up to the latest almost-ANSI standard, improved the class library, and released it in beta form, MCL 2.0b1. These articles are based on MCL 2.0b1.

Why Macintosh Common Lisp?

MCL offers a powerful environment for software development:

• A complete implementation of Lisp as defined in [Steele 1990], including almost 1000 functions, macros and special forms.
• CLOS, a uniquely flexible object programming paradigm.
• A user interface class library.
• The full set of Lisp data types, including linked lists, arrays, structures, objects and hash tables.
• FRED, a Lisp-sensitive text editor.
• Extensive debugging facilities, including single stepping, tracing, interactive break points, and extensive object inspection.

Most important, however, is the Lisp approach to software development. I will now explore two aspects of programming that show, by contrast, the Lisp approach. This is a theoretical exploration; specific examples demonstrating these points will be presented later.

The design approach

In university, computer science students are taught (or at least they used to be) that the correct way to develop a software project is from the top down. In top-down design, one starts with a description of the program and then breaks that into more manageable subproblems until each subproblem piece can be easily coded. Traditional languages encourage top-down development.

This approach assumes that while designing the top level we can ignore nasty realities about the bottom levels; that is, that the chosen abstractions will protect the program design from messy details.

Consider this painful counter-example from my past. In graduate school, I took a software engineering course. Its final project required us to develop a certain program. Computer facilities consisted of an IBM computer with punched card input and PL/C, a teaching version of PL/1.

My project required a stack of punched cards almost a foot high. I started debugging at 10 a.m. the day before it was due. At 11 a.m., I had finished debugging individual program components and was ready to put it all together. I figured on being done by lunch. Ten frustrating hours later, I finally traced a program bug down to the fact that PL/C did not handle subroutine parameter passing the same way as PL/1. My entire design required this missing feature. I had to throw away my foot of cards, redesign, retype, and re-debug the program; I was not happy.

Low level details can doom designs; so, in reality, programs must be developed both from the top down and the bottom up. Top down to allow for consistency and clarity of design, and bottom up to test that things work as expected in terms of both functionality and performance.

Bottom-up development is a "bits and pieces" approach; you want to exercise a certain program part quickly and in isolation from the rest of the program. Also, bottom up is where a lot of innovation comes from. It is low level "tinkering" with the toolbox and Macintosh hardware that's exciting, and that inspires me to explore new ways of doing things.

Neither Pascal nor C++ makes "bits and pieces" development easy. Pascal and C++ programs are centered around a "main" block or function which imposes a hierarchical ordering. It's difficult to test a program feature in isolation.

Assume you are in the late stages of developing a substantial C++ and MacApp program and you have a brainstorm, possibly a better way to represent program data. How can you experiment with this idea?

There are two choices. One is to incorporate your new idea in the current program. Since the program is hierarchical, you must rip out the old code, develop a fairly complete implementation of the new code, and hook it up. Even in a well designed modular system this could take considerable effort, just to test an idea that might not fly.

The second choice is to create a separate program to test out the idea. Setting up a new program is costly under both MPW and Think. Additionally, the new data representation may require part of the original program code to test. The code must be incorporated piecemeal in the new program, a confusing and time consuming operation.

A Lisp program has no conventionally imposed hierarchical ordering. There is no "main" function. A new data representation could easily be prototyped and tested in the current program environment without bothering the working code. If successful, it can be easily integrated. If not, it can be just as easily discarded. Thus there is no penalty for exploring new ideas.

Turn-around time

Consider another contrived example. Assume you are developing a large program. Part of this program displays a window with a square drawn in it. For some reason, you want to know what it would look like with a circle instead. (I chose this example because it explores the "cost" of a trivial experiment.)

On the IBM system described above, you would have to terminate the program, grab your deck of cards, find the card that drew the square, repunch the card, schedule time to use the graphics room, place the cards in the hopper, walk into the graphics room, and wait for your program to be run. Average turn around would be about 24 hours.

On a Macintosh with MPW, you would terminate the program, return to MPW, find the correct DrawContents method, change a line from FrameRect(r) to FrameOval(r), rebuild the application, rerun it, and view the result. Turn around would be five minutes or so.

In Think Pascal with MacApp, you would reset the program, find the proper method, make a similar change, rebuild, and rerun the application. Turn around would be a minute or two.

In MCL, you would click on the editor window, scroll to the ViewDrawContents method, change a line from (draw-rect r) to (draw-circle r), reevaluate only that one method, and immediately observe the new behavior in the same window that previously drew the square. Turn around time would be about ten seconds.

Think compilers achieve quick turn around by closely integrating the development tools, the development environment, and the running environment. This effectively blurs the distinction between developing and running a program.

MCL eliminates this distinction. Windows, objects, and functions created by the user even while your program is running are available immediately after creation. They run as first-class objects next to MCL's own. There is no time consuming context switching between development and execution.

Furthermore, MCL offers an incrementally compiled environment. After a function is written, it can be compiled and linked into your development environment instantaneously. No damned spinning beach ball to watch.

The cost of innovation

The cost of innovation is my term for the difficulty of trying out an idea. Trying out an idea requires a language to express the idea and a development environment to give it life. The language and the environment cannot be separated. Assume your choice for a project is either C++ on the above described IBM system, or Pascal and MacApp on a Macintosh. Wouldn't even the most rabid C++ fanatic choose Pascal in that case?

MCL wins in both language and environment areas (well… almost). It is a more expressive language than Pascal or C++. Its development tools are complete and very, very quick. It supports top down, bottom up, side to side, right to left or whatever type of design methodology your program requires. Other aspects of MCL further reducing the cost of innovation will be demonstrated later.

So why doesn't everybody program in Lisp?

Why not Macintosh Common Lisp?

Currently, it isn't practical to deliver applications in MCL. Major reasons include performance, memory requirements, and incompleteness of the MCL class library. These and other negative aspects of MCL will be discussed in subsequent articles.

Despite this, don't give up on MCL. It has immediate potential as a superior prototyping tool, it can teach us much about software development, and it points the way to the future of development systems. Furthermore, despite Lisp's reputation as a slowpoke, performance of delivered applications is almost acceptable. One more round of hardware improvements may clinch it.

On a purely subjective note, MCL is in many ways a far more enjoyable and productive environment than any other I have used in 20 years of software experience.

A Basic introduction to Macintosh Common Lisp

While it isn't the goal of these articles to teach Lisp, I will present basic Lisp concepts here so subsequent discussions and code fragments can be understood. What follows is a very brief and shallow Lisp tutorial. I plead for your patience, and promise that subsequent articles will make this lengthy introduction worthwhile.

All program code and user input are shown in a plain font. All Listener responses are shown in bold.

Lisp basics

After you start MCL, a special window called the Listener prompts for input with a question mark. The Listener reads what you type, evaluates it, and prints its result. This is known as the read-eval-print loop. Every evaluated expression in Lisp produces a value. The Listener reads symbolic expressions (s-expressions). An s-expression is either an atom or a list. Atoms are things such as numbers or symbols. The value of a number is the number itself. Thus:

? 123.45
123.45

Symbols may have values. If the symbol my-bike has the value "Huffy", then:

? my-bike
"Huffy"

A list is a finite sequence of s-expressions surrounded by parentheses. Here are some lists:

(* (+ 3 4) (- 5 6))
(1 2 3)
(the cat (in the) hat)

When you enter a list, the Listener assumes the first item in the list is a function name and that all following items are arguments to that function. This is prefix notation. Thus:

? (* (+ 3 4) (- 5 6))
-7

A form is an s-expression that is to be evaluated. In the previous example, we typed the form (* (+ 3 4) (- 5 6)) into the Listener. When evaluating a function form, Lisp applies the function to its evaluated arguments. In this case, the function is *, the multiplication operation. Its arguments are two forms, (+ 3 4) and (- 5 6). These are evaluated and the results are passed to *. (+ 3 4) evaluates to 7, (- 5 6) to -1. Thus * is called with arguments of 7 and -1 resulting in -7, which is what the Listener prints. Note that lists are recursively defined, and that evaluation is also recursive.

You can give a value to a symbol via the setf macro.

? (setf my-bike "Ross")
"Ross"

The value of the setf macro is the value of the symbol being defined. In this case, we are defining my-bike to be "Ross".

? my-bike
"Ross"

When the first element of a list form is a function name, the listener evaluates its arguments before application. The two other types of list forms, macros and special forms, work differently.

We need special forms because we don't always want arguments evaluated. Assume we have a Lisp function, in-fix, that could evaluate an infix expression:

? (in-fix ((3 + 4) * (5 - 6)))
> Error: Car of ((3 + 4) * (5 - 6)) is not a function name or 
                                                  lambda-expression.
> While executing: 
CCL::CHEAP-EVAL-IN-ENVIRONMENT
> Type Command-. to abort.
See the Restarts… menu item for further choices.
1 > 

The problem is that Lisp will attempt to evaluate ((3 + 4) * (5 - 6)) before passing it to in-fix. Since Lisp assumes the first element of a form being evaluated is a function, and the first element of this list is another list, (3 + 4), Lisp signals an error.

What we want is to pass ((3 + 4) * (5 - 6)) unevaluated to in-fix. Lisp provides a special form, quote, which returns its unevaluated argument. This would work (after we develop in-fix, of course):

? (in-fix (quote ((3 + 4) * (5 - 6))))
-7

It's common to want to avoid evaluating an argument, so Lisp provides a shorthand notation for quote-a single quote character before a form:

? (in-fix '((3 + 4) * (5 - 6)))
-7

There are about 30 special forms. No more can be added. However, you can write Lisp macros that provide control over the evaluation of arguments. Macros are beyond the scope of these articles.

A list form can be either a macro, a special form, or a function call. The developer must memorize which is which. Understanding the distinctions between these list forms and the how and why of Lisp's evaluation rule is a difficult task for the beginner.

Lists

Lisp stands for List Processing. The most basic data structure in Lisp is the list. Lisp code is also constructed from lists. This fact is one of Lisp's most annoying and most powerful aspects. Beginning Lispers may consume many bottles of aspirin before Lisp's list notation becomes comfortable. But it eventually does.

The cons function (constructor) puts lists together:

? (cons 'a '(b c))
(a b c)

In this example, we added the atom a to the list (b c). Note the use of quote to delay evaluation. The result is the list (a b c).

You can also take lists apart. The car function returns the first element of a list; the cdr function returns the rest of the list (for historical reasons, some of Lisp's function names are distressingly non-mnemonic):

? (car '(a b c))
a
? (cdr '(a b c))
(b c)
? (cons (car '(a b c)) (cdr '(a b c)))
(a b c)

Note how cons, car and cdr are related. I'll cover Lisp's extensive list handling forms as needed.

User -defined functions

The defun macro allows us to define new functions. Its simplified form is:

(defun function-name (list of parameters)
forms to be evaluated)

This function computes the average of three numbers:

(defun average-three (one two three)
(/ (+ one two three) 3))

A Lisp function body is a series of forms that are evaluated sequentially. The value of the function is the result of the last form. In this example, the body consists of one form (/ (+ one two three) 3) that adds the parameters together and divides by three.

First, we must tell Lisp about average-three by typing it in to the Listener:

? (defun average-three (one two three)
(/ (+ one two three) 3))
AVERAGE-THREE
? (average-three 7 8 9)
8
? 

Note that the value of a defun is the name of the function; a side effect is the association of the function with its name. In this case, we are more interested in defun's side effect than its value. After Lisp knows about average-three, it can be called like any pre-defined Lisp function.

Lisp is a naturally recursive language. We can easily write a function to return the number of elements of a list:

? (defun list-size (some-list)
  (if (null some-list)
    0
    (+ 1 (list-size (cdr some-list)))))
LIST-SIZE
? (list-size '(this is a short list))
5
? (list-size '(this list (has a sub) list))
4

A predicate is a function that returns true or false. The null predicate returns true when given an empty list. The if special form has this structure:

(if (test-form)
(then-clause)
(else-clause))

In this example, test-form is evaluated. If true, the then-clause is evaluated and its result becomes the result of the if. Else, the (optional) else-clause is evaluated and its result is used.

The function list-size can be described as follows: if some-list is empty, then return a zero, else return one plus the value of list-size applied to the rest of some-list. Thus list-size recursively traces through the list counting elements as it goes.

Note that list-size only counts elements in its top level; count-all-elements transverses all elements of the list:

(defun count-all-elements (some-list)
  (if (null some-list) 
    0
    (if (atom some-list)
      1
      (+ (count-all-elements (car some-list))
         (count-all-elements (cdr some-list)))))) 

The atom predicate returns true if given an atom (as opposed to a list). This can be read as: if some-list is empty, then return 0; else if some-list is an atom, then return one; else return the sum of count-all-elements applied to the first element of some-list plus count-all-elements applied to the rest of some-list. A recursive divide and conquer approach.

? (count-all-elements '((this list) has (sub) lists))
5

and even:

? (count-all-elements 
'(defun count-all-elements (some-list)
    (if (null some-list) 
    0
    (if (atom some-list)
      1
      (+ (count-all-elements (car some-list))
         (count-all-elements (cdr some-list)))))))
18

In this example, we give count-all-elements a listing of itself to process. Because data and programs are both represented as lists, and Lisp has many functions to manipulate lists, Lisp programs can be self-modifying. A Lisp program can take and modify pieces of itself on the fly, changing functions and adding new ones as needed. In fact, as you'll see when we explore CLOS, this self-modification is completely natural in Lisp!

Learning lisp-a road map

To learn Lisp, you must have Lisp. MCL is available from APDA for $495. This includes the works: Lisp, development tools, class libraries, CLOS, etc. Unfortunately, no student version of this excellent product is currently available.

Other versions of Lisp are also available. One is MacScheme, offering the Scheme dialect of Lisp instead of Common Lisp, by Lightship Software. A student version of MacScheme is available from the MIT Press for $37.50, including manual. I hope to evaluate MacScheme shortly.

An excellent Common Lisp tutorial for programmers is The Common Lisp Companion by Timothy Kroschmann from Wiley. This book is well written, up-to-date, covers large parts of the language, and presents numerous exercises with solutions.

Another tutorial is Lisp 3rd Edition by Patrick Henry Winston and Berthold Klaus Paul Horn, available from Addison Wesley. This book is geared more toward nonprogrammers and has an Artificial intelligence slant. It is a companion to Artificial Intelligence 2nd edition, also by Patrick Henry Winston.

Lisp, more than other languages, has many different ways of doing the same thing. Deciding which Lisp tools to use in solving a problem is especially overwhelming for the beginner. Lisp Design and Style by Molly M. Miller and Eric Benson, available from Digital Press, is an excellent book for these issues. Both the Kroschmann and Winston books deal incompletely with CLOS. A thorough treatment is presented in Object Oriented Programming in Common Lisp by Sonya E. Keene, available from Addison Wesley. This is not an easy book to read. However, after learning enough Lisp and CLOS to understand what was being said, I found myself exclaiming "It can really do that?" after reading each page.

All of the books mentioned above present simplified subsets of Lisp. Even together, they are incomplete. Common Lisp The Language, second edition by Guy L. Steele Jr., available from Digital Press, is the current definition of Common Lisp. This book is required for serious Common Lisp development. It is not a tutorial and is difficult for the beginner to follow. It is, however, the most amazing, and often amusing, language definition I have ever read.

The Winter 1991 issue of Apple's technical Journal develop contained an article, The Power of Macintosh Common Lisp by Ruben Kleiman. This article is more readable with some prior knowledge of Common Lisp. It briefly covers the MCL tools, compares the MCL class library with MacApp, and details the development of an application that uses the MCL class library. Source code and detailed explanations are available on the accompanying CD.

A fascinating book that every software developer should own is Structure and Interpretation of Computer Programs by Harold Abelson and Jay Sussman, available from MIT Press. This book uses Scheme to teach basic concepts in programming and computer science.

Finally, a real kick is the Lisp 1.5 Programmer's Manual , also from the MIT Press. This is the (still in print!) users manual from Lisp 1.5, one of the earliest implementations of Lisp. It was originally published in 1962, and is now in its 15th printing. It offers historic insights into Lisp and the computer science of the early sixties. n