Basic Lisp Techniques

David J. Cooper, Jr.

February 14, 2011

ii

0
Copyright
c 2011, Franz Inc. and David J. Cooper, Jr.
Foreword1

Computers, and the software applications that power them, permeate every facet of our
daily lives. From groceries to airline reservations to dental appointments, our reliance
on technology is all-encompassing. And, it’s not enough. Every day, our expectations of
technology and software increase:

• smart appliances that can be controlled via the internet

• better search engines that generate information we actually want

• voice-activated laptops

• cars that know exactly where to go

The list is endless. Unfortunately, there is not an endless supply of programmers and
developers to satisfy our insatiable appetites for new features and gadgets. Every day,
hundreds of magazine and on-line articles focus on the time and people resources needed to
support future technological expectations. Further, the days of unlimited funding are over.
Investors want to see results, fast.
Common Lisp (CL) is one of the few languages and development options that can meet
these challenges. Powerful, flexible, changeable on the fly — increasingly, CL is playing
a leading role in areas with complex problem-solving demands. Engineers in the fields of
bioinformatics, scheduling, data mining, document management, B2B, and E-commerce
have all turned to CL to complete their applications on time and within budget. CL,
however, no longer just appropriate for the most complex problems. Applications of modest
complexity, but with demanding needs for fast development cycles and customization, are
also ideal candidates for CL.
Other languages have tried to mimic CL, with limited success. Perl, Python, Java,
C++, C# — they all incorporate some of the features that give Lisp its power, but their
implementations tend to be brittle.
The purpose of this book is to showcase the features that make CL so much better
than these imitators, and to give you a “quick-start” guide for using Common Lisp as a
development environment. If you are an experienced programmer in languages other than
Lisp, this guide gives you all the tools you need to begin writing Lisp applications. If you’ve
had some exposure to Lisp in the past, this guide will help refresh those memories and shed
some new light on CL for you.
1
this Foreword was authored by Franz Inc.

iii
iv

But be careful, Lisp can be addicting! This is why many Fortune 500 companies will
use nothing else on their 24/7, cutting-edge, mission-critical applications. After reading
this book, trying our software, and experiencing a 3 to 10 times increase in productivity,
we believe you will feel the same way.
Contents

1 Introduction 1
1.1 The Past, Present, and Future of Common Lisp . . . . . . . . . . . . . . . . 1
1.1.1 Lisp Yesterday . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.2 Lisp Today . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1
1.1.3 Lisp Tomorrow . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Convergence of Hardware and Software . . . . . . . . . . . . . . . . . . . . 3
1.3 The CL Model of Computation . . . . . . . . . . . . . . . . . . . . . . . . . 3

2 Operating a CL Development Environment 5

2.1 Installing a CL Environment . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Running CL in a Shell Window . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2.1 Starting CL from a Terminal Window . . . . . . . . . . . . . . . . . 6
2.2.2 Stopping CL from a Terminal Window . . . . . . . . . . . . . . . . . 6
2.3 Running CL inside a Text Editor . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3.1 A Note on Emacs and Text Editors . . . . . . . . . . . . . . . . . . . 8
2.3.2 Emacs Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3.3 Starting, Stopping, and Working With CL inside an Emacs Shell . . 9
2.4 Running CL as a subprocess of Emacs . . . . . . . . . . . . . . . . . . . . . 10
2.4.1 Starting the CL subprocess within Emacs . . . . . . . . . . . . . . . 10
2.4.2 Working with CL as an Emacs subprocess . . . . . . . . . . . . . . . 10
2.4.3 Compiling and Loading a File from an Emacs buffer . . . . . . . . . 11
2.5 Integrated Development Environment . . . . . . . . . . . . . . . . . . . . . 12
2.6 The User Init File . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12
2.7 Using CL as a scripting language . . . . . . . . . . . . . . . . . . . . . . . . 13
2.8 Debugging in CL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
2.8.1 Common debugger commands . . . . . . . . . . . . . . . . . . . . . . 14
2.8.2 Interpreted vs Compiled Code . . . . . . . . . . . . . . . . . . . . . 15
2.8.3 Use of (break) and C-c to interrupt . . . . . . . . . . . . . . . . . . . 15
2.8.4 Profiling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.9 Developing Programs and Applications in CL . . . . . . . . . . . . . . . . . 16
2.9.1 A Layered Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
2.9.2 Compiling and Loading your Project . . . . . . . . . . . . . . . . . . 16
2.9.3 Creating an Application “Fasl” File . . . . . . . . . . . . . . . . . . 17
2.9.4 Creating an Image File . . . . . . . . . . . . . . . . . . . . . . . . . 17

v
vi CONTENTS

2.9.5 Building Runtime Images . . . . . . . . . . . . . . . . . . . . . . . . 18

2.9.6 Using an Application Init File . . . . . . . . . . . . . . . . . . . . . . 18

3 The CL Language 19
3.1 Overview of CL and its Syntax . . . . . . . . . . . . . . . . . . . . . . . . . 19
3.1.1 Evaluation of Arguments to a Function . . . . . . . . . . . . . . . . 21
3.1.2 Lisp Syntax Simplicity . . . . . . . . . . . . . . . . . . . . . . . . . . 21
3.1.3 Turning Off Evaluation . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.1.4 Fundamental CL Data Types . . . . . . . . . . . . . . . . . . . . . . 22
3.1.5 Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.1.6 Global and Local Variables . . . . . . . . . . . . . . . . . . . . . . . 25
3.2 The List as a Data Structure . . . . . . . . . . . . . . . . . . . . . . . . . . 27
3.2.1 Accessing the Elements of a List . . . . . . . . . . . . . . . . . . . . 28
3.2.2 The “Rest” of the Story . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.3 The Empty List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.4 Are You a List? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
3.2.5 The conditional If . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.6 Length of a List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
3.2.7 Member of a List . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31
3.2.8 Getting Part of a List . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2.9 Appending Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
3.2.10 Adding Elements to a List . . . . . . . . . . . . . . . . . . . . . . . . 33
3.2.11 Removing Elements from a List . . . . . . . . . . . . . . . . . . . . . 33
3.2.12 Sorting Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.13 Treating a List as a Set . . . . . . . . . . . . . . . . . . . . . . . . . 34
3.2.14 Mapping a Function to a List . . . . . . . . . . . . . . . . . . . . . . 35
3.2.15 Property Lists . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3 Control of Execution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.3.1 If . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3.2 When . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3.3 Logical Operators . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36
3.3.4 Cond . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37
3.3.5 Case . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.3.6 Iteration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38
3.4 Functions as Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4.1 Named Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39
3.4.2 Functional Arguments . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4.3 Anonymous Functions . . . . . . . . . . . . . . . . . . . . . . . . . . 40
3.4.4 Optional Arguments . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.4.5 Keyword Arguments . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.5 Input, Output, Streams, and Strings . . . . . . . . . . . . . . . . . . . . . . 42
3.5.1 Read . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.5.2 Print and Prin1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42
3.5.3 Princ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
3.5.4 Format . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43
CONTENTS vii

3.5.5 Pathnames . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.5.6 File Input and Output . . . . . . . . . . . . . . . . . . . . . . . . . . 44
3.6 Hash Tables, Arrays, Structures, and Classes . . . . . . . . . . . . . . . . . 45
3.6.1 Hash Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45
3.6.2 Arrays . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46
3.6.3 Structures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.6.4 Classes and Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . 47
3.7 Packages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48
3.7.1 Importing and Exporting Symbols . . . . . . . . . . . . . . . . . . . 49
3.7.2 The Keyword Package . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.8 Common Stumbling Blocks . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.8.1 Quotes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49
3.8.2 Function Argument Lists . . . . . . . . . . . . . . . . . . . . . . . . 50
3.8.3 Symbols vs. Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . 50
3.8.4 Equality . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 52
3.8.5 Distinguishing Macros from Functions . . . . . . . . . . . . . . . . . 53
3.8.6 Operations that cons . . . . . . . . . . . . . . . . . . . . . . . . . . . 54

4 Interfaces 55
4.1 Interfacing with the Operating System . . . . . . . . . . . . . . . . . . . . . 55
4.2 Foreign Function Interface . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55
4.3 Interfacing with Corba . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.4 Custom Socket Connections . . . . . . . . . . . . . . . . . . . . . . . . . . . 56
4.5 Interfacing with Windows (COM, DLL, DDE) . . . . . . . . . . . . . . . . . 58
4.6 Code Generation into Other Languages . . . . . . . . . . . . . . . . . . . . 58
4.7 Multiprocessing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58
4.7.1 Starting a Background Process . . . . . . . . . . . . . . . . . . . . . 58
4.7.2 Concurrency Control . . . . . . . . . . . . . . . . . . . . . . . . . . . 59
4.8 Database Interfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60
4.8.1 ODBC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.8.2 MySQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
4.9 World Wide Web . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
4.9.1 Server and HTML Generation . . . . . . . . . . . . . . . . . . . . . . 62
4.9.2 Client and HTML Parsing . . . . . . . . . . . . . . . . . . . . . . . . 63
4.10 Regular Expressions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.11 Email . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.11.1 Sending Mail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64
4.11.2 Retrieving Mail . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65

5 Squeakymail 67
5.1 Overview of Squeakymail . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.2 Fetching and Scoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67
5.2.1 Tokenizing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.2.2 Scoring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72
5.3 Browsing and Classifying . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73
viii CONTENTS

A Squeakymail with Genworks’ GDL/GWL 77

A.1 Toplevel Squeakymail Home Page . . . . . . . . . . . . . . . . . . . . . . . . 77
A.2 Page for Browsing and Classifying . . . . . . . . . . . . . . . . . . . . . . . 78

B Bibliography 83

C Emacs Customization 85
C.1 Lisp Mode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
C.2 Making Your Own Keychords . . . . . . . . . . . . . . . . . . . . . . . . . . 85
C.3 Keyboard Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

D Afterword 87
D.1 About This Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
D.2 Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
D.3 About the Author . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87
Chapter 1

Introduction

1.1 The Past, Present, and Future of Common Lisp

1.1.1 Lisp Yesterday
John McCarthy discovered the basic principles of Lisp in 1958, when he was processing
complex mathematical lists at MIT. Common Lisp (CL) is a high-level computer language,
whose syntax follows a simple list-like structure. The term “Lisp” itself originally stood for
“LISt Processing.” When developing, testing, and running a CL program, at the core is a
modern-day version of the original List Processor which processes (compiles, evaluates, etc.)
the elements of your program. These elements, at the source code level, are represented
as lists. A list, in this context, is just a sequence of items, much like a familiar shopping
list or checklist. Originally the list was pretty much the only data structure supported by
Lisp, but modern-day Common Lisp supports a wide range of flexible and efficient data
structures.
A typical Common Lisp development and runtime environment behaves like a complete
operating system, with multiple threads of execution and the ability to load new code
and redefine objects (functions, etc.) dynamically, i.e. without stopping and restarting the
“machine.”
This “operating system” characteristic also makes CL significantly more flexible than
other popular programming languages. Whereas some other languages, such as shell scripts
or Perl CGI scripts, need to pipe data around, in CL all data manipulations can run
interactively within one single process with a shared memory space.

1.1.2 Lisp Today

The most popular form of Lisp used today, “ANSI Common Lisp,” was initially designed by
Guy Steele in Common Lisp, the Language, 2nd Edition (“CLtL2”) — (see the Bibliogra-
phy in Appendix B). This version of Lisp became the accepted industry standard. In 1995,
the American National Standards Institute recognized a slightly updated version as ANSI
Common Lisp, the first object-oriented language to receive certification, and ANSI CL re-
mains the only language that meets all of the criteria set forth by the Object Management
Group (OMG) for a complete object-oriented language.

1
2 CHAPTER 1. INTRODUCTION

Paul Graham outlines ANSI CL in his 1996 book ANSI Common Lisp, also listed in
Appendix B.
Official language standardization is important, because it protects developers from be-
coming saddled with legacy applications as new versions of a language are implemented.
For example, this lack of standardization has been a continuing problem for Perl developers.
Since each implementation of Perl defines the behavior of the language, it is not uncommon
to have applications that require outdated versions of Perl, making it nearly impossible to
use in a mission-critical commercial environment.

1.1.3 Lisp Tomorrow

Many developers once hoped that the software development process of the future would be
more automated through Computer-aided Software Engineering (CASE) tools. Such tools
claim to enable programmers and non-programmers to diagram their applications visually
and automatically generate code. While useful to a certain extent, traditional CASE tools
cannot cover domain-specific details and support all possible kinds of customizations — so
developers inevitably need to hand-code the rest of their applications, breaking the link
between the CASE model and the code. CASE systems fall short of being a true “problem-
solving tool.”
The recursive nature of CL, and its natural ability to build applications in layers and
build upon itself — in essence, code which writes code which writes code..., makes CL a
much better software engineering solution. CL programs can generate other CL programs
(usually at compile-time), allowing the developer to define all parts of the application in
one unified high-level language. Using macros and functions, naturally supported by the CL
syntax, the system can convert applications written in the high-level language automatically
into “final” code. Thus, CL is both a programming language and a powerful CASE tool,
and there is no need to break the connection.
Several other features of CL also save significant development time and manpower:

• Automatic Memory Management/Garbage Collection: inherent in CL’s basic archi-

tecture.

• Dynamic Typing: In CL, values have types, but variables do not. This means that
you don’t have to declare variables, or placeholders, ahead of time to be of a particular
type; you can simply create them or modify them on the fly1 .

• Dynamic Redefinition: You can add new operations and functionality to the running
CL process without the need for downtime. In fact, a program can be running in one
thread, while parts of the code are redefined in another thread. Moreover, as soon as
the redefinitions are finished, the application will use the new code and is effectively
modified while running. This feature is especially useful for server applications that
cannot afford downtimes – you can patch and repair them while they are running.

• Portability: The “abstract machine” quality of CL makes programs especially portable.

1
While you don’t have to declare variable types, you may declare them. Doing so can help CL’s compiler
to optimize your program further.
1.2. CONVERGENCE OF HARDWARE AND SOFTWARE 3

• Standard Features: CL contains many built-in features and data structures that are
non-standard in other languages. Features such as full-blown symbol tables and pack-
age systems, hash tables, list structures, and a comprehensive object system are sev-
eral “automatic” features which would require significant developer time to recreate
in other languages.

1.2 Convergence of Hardware and Software

The most common criticism of Lisp usually made by programmers unfamiliar with the
language is that Lisp applications are too big and too slow. While this may have been true
20 years ago, it is absolutely not the case today. Today’s inexpensive commodity computers
have more memory than some of the most powerful machines available just five years ago,
and easily meet the computing needs of a typical CL application. Hardware is no longer
the critical factor. Programmers and development time are!
Further, CL programming teams tend to be small, because the inherent features in CL
empower developers to do more. Without excessive effort, a single CL developer can create
and deploy a sophisticated, powerful program in a much shorter period of time than if
another language were used.

1.3 The CL Model of Computation

Programming in CL is distinguished from programming in other languages due to its unique
syntax and development mode. CL allows developers to make changes and test them im-
mediately, in an incremental manner. In other languages, a developer must follow the
“compile-link-run-test” cycle. These extra steps add minutes or hours to each cycle of de-
velopment, and break the programmer’s thought process. Multiply these figures by days,
weeks, and months — and the potential savings are phenomenal.
4 CHAPTER 1. INTRODUCTION
92 INDEX

tables
hash, 45
test-expression forms
for cond, 37
threads, 1
toplevel, 19
turning off evaluation, 22
Typing
Dynamic, 22

union, 34
Unix, 44

variables
global, 25
special, 25

webserver, 62
With-open-file, 45