Successful Lisp: How to Understand and Use Common Lisp
Internet Edition - Work in Progress
This book got its start when I responded to an invitation from a publisher of mass-market computer books to write a proposal for a new book on Common Lisp. In between the company's invitation and the proposal's completion, the company's marketing department decided that the market for Lisp books was small and already crowded.
I believe that a well written introduction to Common Lisp not only could support itself in a niche market through self publication, but may serve to involve new programmers in the Lisp tradition. This book departs from many introductory Lisp texts in concentrating immediately on the use of Lisp, rather than on its internal features. This is in keeping with the approach taken by mass-market books on programming in other languages, which seem over the past decade to have dropped the obligatory chapters on boolean logic, binary arithmetic, and machine organization in favor of taking a problem solving approach.
I am making portions of this book available online during its production, and invite comments and criticism from readers. As the book nears completion, I will announce distribution and pricing for the final version. The final version's cost will be quite low in accordance with my low production costs and my desire to reach a large number of readers. Until then, please read and enjoy...
David B. Lamkins
April 1999
================================================================
Successful Lisp:
How to Understand and Use Common Lisp
David B. Lamkins
dlamkins@psg.com
This book:
Provides an overview of Common Lisp for the working programmer.
Introduces key concepts in an easy-to-read format.
Describes format, typical use, and possible drawbacks of all important Lisp constructs.
Provides practical advice for the construction of Common Lisp programs.
Shows examples of how Common Lisp is best used.
Illustrates and compares features of the most popular Common Lisp systems on desktop computers.
Includes discussion and examples of advanced constructs for iteration, error handling, object oriented programming, graphical user interfaces, and threading.
Supplements Common Lisp reference books and manuals with useful hands-on techniques.
Shows how to find what you need among the thousands of documented and undocumented functions and variables in a typical Common Lisp system.
================================================================
About the Author
David Lamkins was born in Watervliet, New York. Very little is known about his childhood except that he started taking things apart as soon as he could hold a screwdriver. It wasn't until David reached the age of twelve that he started putting things back together. David's favorite movie is "The Empire Strikes Back," and his favorite pastime (when not trying to find the precise blend of science fiction, heavy metal music, AI technology, and programming technique to create the Ultimate Application) is to study the effect of industrial-age mind sets on the organization and performance of information-age enterprises.
================================================================
Table of Contents
Dedication
Credits
Copyright
Acknowledgments
Foreword
Introduction
--------------------------------------------------------------------------------
Chapter 1 - Why Bother? Or: Objections Answered
Chapter objective: Describe the most common objections to Lisp, and answer each with advice on state-of-the-art implementations and previews of what this book will explain.
I looked at Lisp before, and didn't understand it.
I can't see the program for the parentheses.
Lisp is very slow compared to my favorite language.
No one else writes programs in Lisp.
Lisp doesn't let me use graphical interfaces.
I can't call other people's code from Lisp.
Lisp's garbage collector causes unpredictable pauses when my program runs.
Lisp is a huge language.
Lisp is only for artificial intelligence research.
Lisp doesn't have any good programming tools.
Lisp uses too much memory.
Lisp uses too much disk space.
I can't find a good Lisp compiler.
--------------------------------------------------------------------------------
Chapter 2 - Is this Book for Me?
Chapter objective: Describe how this book will benefit the reader, with specific examples and references to chapter contents.
The Professional Programmer
The Student
The Hobbyist
The Former Lisp Acquaintance
The Curious
--------------------------------------------------------------------------------
Chapter 3 - Essential Lisp in Twelve Lessons
Chapter objective: Explain Lisp in its simplest form, without worrying about the special cases that can confuse beginners.
Lesson 1 - Essential Syntax
Lists are surrounded by parentheses
Atoms are separated by whitespace or parentheses
Lesson 2 - Essential Evaluation
A form is meant to be evaluated
A function is applied to its arguments
A function can return any number of values
Arguments are usually not modified by a function
Arguments are usually evaluated before function application
Arguments are evaluated in left-to-right order
Special forms and macros change argument evaluation
Lesson 3 - Some Examples of Special Forms and Macros
SETQ
LET
COND
QUOTE
Lesson 4 - Putting things together, and taking them apart
CONS
LIST
FIRST and REST
Lesson 5 - Naming and Identity
A symbol is just a name
A symbol is always unique
A symbol can name a value
A value can have more than one name
Lesson 6 - Binding versus Assignment
Binding creates a new place to hold a value
Bindings have names
A binding can have different values at the same time
One binding is innermost
The program can only access bindings it creates
Assignment gives an old place a new value
Lesson 7 - Essential Function Definition
DEFUN defines named functions
LAMBDA defines anonymous functions
Lesson 8 - Essential Macro Definition
DEFMACRO defines named macros
Macros return a form, not values
Lesson 9 - Essential Multiple Values
Most forms create only one value
VALUES creates multiple (or no) values
A few special forms receive multiple values
Most forms pass along multiple values
Lesson 10 - A Preview of Other Data Types
Lisp almost always does the right thing with numbers
Characters give Lisp something to read and write
Arrays organize data into tables
Vectors are one-dimensional arrays
Strings are vectors that contain only characters
Symbols are unique, but they have many values
Structures let you store related data
Type information is apparent at runtime
Hash Tables provide quick data access from a lookup key
Packages keep names from colliding
Lesson 11 - Essential Input and Output
READ accepts Lisp data
PRINT writes Lisp data for you and for READ
OPEN and CLOSE let you work with files
Variations on a PRINT theme
Lesson 12 - Essential Reader Macros
The reader turns characters into data
Standard reader macros handle built-in data types
User programs can define reader macros
--------------------------------------------------------------------------------
Chapter 4 - Mastering the Essentials
Chapter objective: Reinforce the concepts of Chapter 3 with hands-on exercises.
Hands-on! The "toploop"
Spotting and avoiding common mistakes
Defining simple functions
Using global variables and constants
Defining recursive functions
Tail recursion
Exercises in naming
Lexical binding and multiple name spaces
Reading, writing, and arithmetic
Other data types
Simple macros
Reader macros
--------------------------------------------------------------------------------
Chapter 5 - Introducing Iteration
Chapter objective: Introduce the most common looping constructs.
"There's no such thing as an infinite loop. Eventually, the computer will break." -- John D. Sullivan
Simple LOOP loops forever...
But there's a way out!
Use DOTIMES for a counted loop
Use DOLIST to process elements of a list
DO is tricky, but powerful
--------------------------------------------------------------------------------
Chapter 6 - Deeper into Structures
Chapter objective: Show the most useful optional features of structures.
Default values let you omit some initializers, sometimes
Change the way Lisp prints your structures
Alter the way structures are stored in memory
Shorten slot accessor names
Allocate new structures without using keyword arguments
Define one structure as an extension of another
--------------------------------------------------------------------------------
Chapter 7 - A First Look at Objects as Fancy Structures
Chapter objective: Introduce CLOS objects as tools for structuring data. Object behaviors will be covered in a later chapter.
Hierarchies: Classification vs. containment
Use DEFCLASS to define new objects
Objects have slots, with more options than structures
Controlling access to a slot helps keep clients honest
Override a slot accessor to do things that the client can't
Define classes with single inheritance for specialization
Multiple inheritance allows mix-and-match definition
Options control initialization and provide documentation
This is only the beginning...
--------------------------------------------------------------------------------
Chapter 8 - Lifetime and Visibility
Chapter objective: Show how lifetime and visibility affect the values of Lisp variables during execution. This is pretty much like local and global variables in other languages, but Lisp's special variables change things. This chapter also sets the stage for understanding that lifetime and visibility isn't just for variables.
Everything in Lisp has both lifetime and visibility
Lifetime: Creation, existence, then destruction
Visibility: To see and to be seen by
The technical names: Extent and Scope
Really easy cases: top-level defining forms
Scope and extent of parameters and LET variables
Slightly trickier: special variables
--------------------------------------------------------------------------------
Chapter 9 - Introducing Error Handling and Non-Local Exits
Chapter objective: Show three new ways of transferring control between parts of a program.
UNWIND-PROTECT: When it absolutely, positively has to run
Gracious exits with BLOCK and RETURN-FROM
Escape from anywhere (but not at any time) with CATCH and THROW
Making sure files only stay open as long as needed
--------------------------------------------------------------------------------
Chapter 10 - How to Find Your Way Around, Part 1
Chapter objective: Show how to find things in Lisp without resorting to the manual.
APROPOS: I don't remember the name, but I recognize the face
DESCRIBE: Tell me more about yourself
INSPECT: Open wide and say "Ah..."
DOCUMENTATION: I know I wrote that down somewhere
--------------------------------------------------------------------------------
Chapter 11 - Destructive Modification
Chapter objective: Illustrate the difference between assignment and binding, and show why assignment is harder to understand. Then explore reasons for preferring the more difficult concept, and introduce functions that use destructive modification.
Simple assignment is destructive modification
The risk of assignment
Changing vs. copying: an issue of efficiency
Modifying lists with destructive functions
RPLACA, RPLACD, SETF ...; circularity
Places vs. values: destructive functions don't always have the desired side-effect
Contrast e.g. PUSH and DELETE
Shared and constant data: Dangers of destructive changes
--------------------------------------------------------------------------------
Chapter 12 - Mapping Instead of Iteration
Chapter objective: Categorize and demonstrate the mapping functions. Show appropriate and inappropriate uses. Introduce the concept of sequences.
MAPCAR, MAPC, and MAPCAN process successive list elements
MAPLIST, MAPL, and MAPCON process successive sublists
MAP and MAP-INTO work on sequences, not just lists
Mapping functions are good for filtering
It's better to avoid mapping if you care about efficiency
Predicate mapping functions test sequences
SOME, EVERY, NOTANY, NOTEVERY
REDUCE combines sequence elements
--------------------------------------------------------------------------------
Chapter 13 - Still More Things You Can Do with Sequences
Chapter objective: Introduce the most useful sequence functions, and show how to use them. Show how destructive sequence functions must be used to have the intended effect.
CONCATENATE: new sequences from old
ELT and SUBSEQ get what you want from any sequence (also, COPY-SEQ)
REVERSE turns a sequence end-for-end (also, NREVERSE)
LENGTH: size counts after all
COUNT: when it's what's inside that matters
REMOVE, SUBSTITUTE, and other sequence changers
DELETE, REMOVE-DUPLICATES, DELETE-DUPLICATES, and NSUBSTITUTE
FILL and REPLACE
Locating things in sequences: POSITION, FIND, SEARCH, and MISMATCH
SORT and MERGE round out the sequence toolkit
--------------------------------------------------------------------------------
Chapter 14 - Can Objects Really Behave Themselves?
Chapter objective: Show how generic functions work. Describe multiple dispatch, inheritance, and method combination. Preview the metaobject protocol.
Generic functions give objects their behaviors
The line between methods and objects blurs for multimethods
Methods on non-objects? So where does the method live?
Generic functions work by dispatching on argument specializers
Object inheritance matters after all; finding the applicable method
Method combinations offer further choices
Nothing is cast in stone; a peek at the metaobject protocol
--------------------------------------------------------------------------------
Chapter 15 - Closures
Chapter objective: Show how closures capture free variables for use in other execution contexts. Demonstrate with some practical applications.
Is it a function of the lifetime, or the lifetime of a function?
How to spot a free variable, and what to do about it.
Using closures to keep private, secure information.
Functions that return functions, and how they differ from macros.
--------------------------------------------------------------------------------
Chapter 16 - How to Find Your Way Around, Part 2
Chapter objective: Learn what the Lisp compiler does to your code, and how to watch what your code does as it runs.
"DISASSEMBLE is your friend." -- Bill St. Clair
DISASSEMBLE: I always wondered what they put inside those things...
BREAK and backtrace: How did I end up here?
TRACE and STEP: I'm watching you!
--------------------------------------------------------------------------------
Chapter 17 - Not All Comparisons are Equal
Chapter objective: Tell how and why Lisp has so many different comparison functions. Give guidelines for proper choice.
The longer the test, the more it tells you
EQ is true for identical symbols
EQL is also true for identical numbers and characters
EQUAL is usually true for things that print the same
EQUALP ignores number type and character case
Longer tests are slower; know what you're comparing
Specialized tests run faster on more restricted data types
--------------------------------------------------------------------------------
Chapter 18 - Very Logical, Indeed...
Chapter objective: Describe common logical functions, and conditional evaluation. Introduce bit manipulation functions, bit vectors, and generalized byte manipulation.
AND and OR evaluate only as much as they need
Bits, bytes, and Boole
Bit vectors can go on forever
Chunks of bits make bytes
--------------------------------------------------------------------------------
Chapter 19 - Streams
Chapter objective: Introduce streams as generalized I/O facilities. Emphasize interchangeability of streams attached to different devices.
Streams provide a pipe to supply or accept data
Creating streams on files
Creating streams on strings
Binary I/O
--------------------------------------------------------------------------------
Chapter 20 - Macro Etiquette
Chapter objective: Go beyond the simple examples of chapters 3 and 4 to show how to properly construct macros to solve a wide variety of problems.
Macros are programs that generate programs
Close up: how macros work
Backquote looks like a substitution template
Beyond the obvious, part 1: compute, then generate
Beyond the obvious, part 2: macros that define macros
Tricks of the trade: elude capture using GENSYM
Macros vs. inlining
--------------------------------------------------------------------------------
Chapter 21 - Fancy Tricks with Function and Macro Arguments
Chapter objective: Describe lambda-list options. Show how they can be used to clarify programs.
Keywords let you name your parameters
Default values for when you'd rather not say
Add some structure to your macros by taking apart arguments
--------------------------------------------------------------------------------
Chapter 22 - How to Find Your Way Around, Part 3
Chapter objective: Learn how to find out about objects and methods. Learn specialized techniques to alter or monitor program behavior without changing the source code.
Class and method browsers help you find your way in a sea of objects
ADVISE lets you modify a function's behavior without changing the function
WATCH lets you open a window on interesting variables
--------------------------------------------------------------------------------
Chapter 23 - To Err is Expected; To Recover, Divine
Chapter objective: Show how to create your own error detection and recovery mechanisms.
Signal your own errors and impress your users
Categorize errors using Conditions
Recover from Conditions using Restarts
--------------------------------------------------------------------------------
Chapter 24 - FORMAT Speaks a Different Language
Chapter objective: Describe the most useful functions of the FORMAT function.
FORMAT rhymes with FORTRAN, sort of...
Formatting
Iteration
Conditionals
Floobydust
--------------------------------------------------------------------------------
Chapter 25 - Connecting Lisp to the Real World
Chapter objective: Describe FFI in general, and give examples from actual implementations. Show how to use wrappers to call C++ functions. Show how callbacks allow C programs to call Lisp functions. Give an example using TCP/IP access.
Foreign Function Interfaces let you talk to programs written in "foreign languages"
Would you wrap this, please?
I'll call you back...
Network Interfaces: beyond these four walls
--------------------------------------------------------------------------------
Chapter 26 - Put on a Happy Face: Interface Builders
Chapter objective: Discuss event-driven interfaces and GUI builders in general, then show examples from major desktop Common Lisp platforms. Conclude with a discussion of platform-independent Lisp GUIs such as Garnet and CLIM.
Event-driven interfaces
Graphical programming
Example: MCL's Interface Toolkit
Example: ACL4WIN's Interface Builder
Example: Medley's ROOMS
Platform-independent interfaces
--------------------------------------------------------------------------------
Chapter 27 - A Good Editor is Worth a Thousand Keystrokes
Chapter objective: Show how Lisp's simple syntax combines with an integrated editor to ease many of the common tasks of writing a Lisp program.
Simple syntax; smart editors
Matching and flashing
Automatic indentation
Symbol completion
Finding definitions
On-line documentation
Access to debugging tools
Extending the editor using Lisp
--------------------------------------------------------------------------------
Chapter 28 - Practical Techniques for Programming
Chapter objective: Provide useful guidelines for Lisp style. Give practical advice on tradeoffs among debugging, performance, and readability.
Elements of Lisp style
Property lists are handy for small (very small) ad-hoc databases
Declarations help the compiler, sometimes
DEFVAR versus DEFPARAMETER
Define constants with DEFCONSTANT
Know when (not) to use the compiler
Speed vs. ability to debug
Efficiency: spotting it, testing it
Recognizing inefficiency, profiling; performance vs. readability
--------------------------------------------------------------------------------
Chapter 29 - I Thought it was Your Turn to Take Out the Garbage
Chapter objective: Describe the benefits and costs of garbage collection. Show how to improve program performance by reducing the amount of garbage it generates.
What is garbage?
Why is garbage collection important?
How does garbage collection work?
What effect does garbage have on my program?
How can I reduce garbage collection pauses in my program?
--------------------------------------------------------------------------------
Chapter 30 - Helpful Hints for Debugging and Bug-Proofing
Chapter objective: Describe use of Lisp's debugging tools.
Finding the cause of an error
Reading backtraces, compiler settings for debugging
Simple debugging tools
BREAK, PRINT
Power tools for tough problems
TRACE, STEP, ADVISE, WATCH
Into the belly of the beast
INSPECT, DESCRIBE
Continuing from an error
Problems with unwanted definitions
Package problems; method definitions
The problem with macros
Runtime tests catch "can't happen cases" when they do...
Use method dispatch rather than case dispatch
--------------------------------------------------------------------------------
Chapter 31 - Handling Large Projects in Lisp
Chapter objective: Describe strategies and tools used to organize Lisp programs for large projects and team efforts.
Packages keep your names separate from my names
System builders let you describe dependencies
Source control systems keep track of multiple revisions
Modules: another way to describe file dependencies
PROVIDE and REQUIRE
--------------------------------------------------------------------------------
Chapter 32 - Dark Corners and Curiosities
Chapter objective: Describe some Lisp features that are newer, unstandardized, experimental, or controversial.
Extended LOOP: Another little language
TAGBODY: GO if you must
Processes & Stack Groups: Juggling multiple tasks
Series: Another approach to iteration and filtering
--------------------------------------------------------------------------------
Chapter 33 - Where to Go Next
Chapter objective: Provide pointers to other sources of information and products.
Suggestions for further reading
On-line sources
Commercial vendors
--------------------------------------------------------------------------------
Chapter 34 - Lisp History, or: Origins of Misunderstandings
Chapter objective: Give a short history of Lisp's development, providing insights to some lingering misconceptions.
John McCarthy's Notation
Earliest implementations
Special hardware
Diverging dialects
The DARPA directive
East vs. West, and European competition
The emergence of compilers for stock hardware
The long road to standardization
State of the Art?
--------------------------------------------------------------------------------
Appendix A - Lisp System Feature Comparison
Chapter objective: Describe several Common Lisp development systems, both commercial and freeware. Compare and contrast. Note product and corporate lineage.
Digitool's Macintosh Common Lisp 3.0
Franz's Allegro Common Lisp for Windows 2.0
Venue's Medley 2.01
David Betz's XLISP 2.1
Roger Corman's PowerLisp 1.1
xxx's CLISP ?.?
--------------------------------------------------------------------------------
Appendix B - Successful Lisp Applications
Chapter objective: Describe large successful applications built in Lisp.
Emacs
G2
AutoCad
...
--------------------------------------------------------------------------------
Cover
Dedication
--------------------------------------------------------------------------------
Copyright © 1995-1999, David B. Lamkins
All Rights Reserved Worldwide
================================================================
Chapter 1 - Why Bother? Or: Objections Answered
Everyone knows Lisp, right? Many of us took a course that introduced us to Lisp along with three or four or more other languages. This is how I was introduced to Lisp around 1975, and I thought it was a pretty useless language. It didn't do anything in the usual way, it was slow, and those parentheses were enough to drive anyone crazy!
If your own Lisp experience predates 1985 or so, you probably share this view. But in 1984, the year Big Brother never really became a reality (did it?), the year that the first bleeding-edge (but pathetic by today's standards) Macintosh started volume shipments, the Lisp world started changing. Unfortunately, most programmers never noticed; Lisp's fortune was tied to AI, which was undergoing a precipitous decline -- The AI Winter -- just as Lisp was coming of age. Some say this was bad luck for Lisp. I look at the resurgence of interest in other dynamic languages and the problems wrestled with by practicioners and vendors alike, and wonder whether Lisp wasn't too far ahead of its time.
I changed my opinion of Lisp over the years, to the point where it's not only my favorite progamming language, but also a way of structuring much of my thinking about programming. I hope that this book will convey my enthusiasm, and perhaps change your opinion of Lisp.
Below I've listed most of the common objections to Lisp. These come from coworkers, acquaintances, managers, and my own past experience. For each point, I'll describe how much is actually true, how much is a matter of viewpoint, and how much is a holdover from the dark days of early Lisp implementations. As much as possible, I'll avoid drawing comparisons to other languages. Lisp has its own way, and you'll be able to make your own comparisons once you understand Lisp as well as your usual language. If you eventually understand Lisp enough to know when its use is appropriate, or find a place for Lisp in your personal toolkit, then I've done my job.
Without further introduction, here are a baker's dozen reasons why you might be avoiding Lisp:
--------------------------------------------------------------------------------
I looked at Lisp before, and didn't understand it.
This is a really tough one. Most programming languages are more similar to each other than they are to Lisp. If you look at a family tree of computer languages, you'll see that the most common languages in use today are descendants of the Algol family. Features common to languages in the Algol family include algebraic notation for expressions, a block structure to control visibility of variables, and a way to call subroutines for value or effect. Once you understand these concepts, you can get started with another language in the family by studying the surface differences: the names of keywords and the style of punctuation.
Lisp really is different. If you've only read code in Algol family languages, you'll find no familiar punctuation or block structure to aid your understanding of Lisp code -- just unfamiliar names appearing in seemingly pointless nests of parentheses. In Lisp, the parenthesis is the punctuation. Fortunately, its use is quite simple; simpler than, for example, remembering the operator precedence rules of C or Pascal. Lisp development environments even provide editors that help with matching opening and closing parentheses.
Once you understand how Lisp expressions are put together, you still have to learn what they mean. This is harder because Lisp provides a lot of facilities that aren't found elsewhere, or gives unfamiliar names to familiar concepts. To really understand Lisp, you need to know how it works inside. Like most good programmers, you probably have a mental model of how a computer works, and how your favorite compiler translates statements from your favorite language into machine code. You'll drive yourself crazy if you try this with Lisp, which seems to go to great lengths to isolate you from the details of machine organization. Yes, you sacrifice some control. Perhaps not surprisingly, you gain quite a lot in program correctness once you give up worrying about how your program is mapped by the compiler onto bits in the machine. Is the tradeoff worthwhile? We'll explore that issue in a later chapter.
This book will teach you how to read and write Lisp, how to recognize and understand new words like DEFUN, CONS, and FLET, and -- ultimately -- how to think in Lisp as well as you think in your favorite programming language.
--------------------------------------------------------------------------------
I can't see the program for the parentheses.
Part of this problem is a matter of dealing with the unfamiliar. I talked about that in the previous section. Another part of this problem is real: you have to deal with a lot of parentheses. Fortunately, Lisp programming environments have editors that mechanize the process of counting parentheses by flashing or highlighting matching pairs or by manipulating entire balanced expressions. Finally, there's a matter of style. Judicious indentation improves the readability of Lisp programs, as it does in other languages. But vertical whitespace often hinders readability in Lisp.
I'll cover both the mechanical and stylistic aspects of Lisp code in this book. By the time you're done, you'll have an opinion on what constitues readable code, and you'll be able to defend your position. When you reach that level of confidence, you'll be able to write aesthetic Lisp code, and to read anyone else's code. Parentheses won't be a concern any longer.
--------------------------------------------------------------------------------
Lisp is very slow compared to my favorite language.
Possibly... But the difference may not be as large as you'd expect. First, let's clear the table of an old misconception: that Lisp is an interpreted language. As a rule, most modern Lisp systems compile to machine code. A few compile to byte code that typically runs five times slower than machine code. And one or two freeware Lisp systems only run interpreted code, but they're the exception. So there's part one of the answer: if you're not running a Lisp compiler, you should get one.
Your Lisp coding style affects execution speed. Unfortunately, you won't recognize inefficient Lisp code until you've had some experience with the language. You'll need to think about how Lisp works in order to understand what makes Lisp code run slowly. This is not hard to do, but the issues are different from those for languages which expose more of the underlying machine to you.
Lisp gives you incremental compilation. This means that you can compile one function at a time and be ready to run your program instantly -- there is no linkage step. This means that you can make lots of changes quickly and evaluate them for their effect on the program. Lisp also has built-in instrumentation to help you tune the performance of your program.
You'll experience all of these things as you work your way through this book. By the time you're done, you'll know how to avoid writing inefficient code in the first place, and how to use all of the available tools to identify and fine tune the really critical code in your programs.
--------------------------------------------------------------------------------
No one else writes programs in Lisp.
What? I'm the only one left? I don't think so...
Seriously, though, there are quite a few people who write Lisp code every day. They write programs that solve tough problems, and give their employers a strategic advantage. It's hard to find good Lisp programmers who are willing to move to a new employer; those companies who are using Lisp guard their strategic advantage, and their Lisp programmers, quite jealously.
Now, it's mostly true that you won't find Lisp in consumer products like spreadsheets, databases, word processors, and games. But then, that's not the kind of work that Lisp does best. You will find Lisp in products that must reason about and control complex systems and processes, where the ability to reliably arrive at useful conclusions based upon complex relationships among multiple sources and kinds of data is more important than lightning-fast numerical calculations or spiffy graphics (although modern Lisp systems come pretty close to the leaders even in the latter two categories).
Lisp is also used as an extension language because of its simple, consistent syntax and the ability for system designers to add new functions to Lisp without writing an entire new language. The Emacs editor and the AutoCAD drafting program are two of the best examples of this use of Lisp.
And of course Lisp is still the language most often used for research in artificial intelligence and advanced computer language design, but we won't touch on either of those subjects in this book. When you've finished this book, you'll have the knowledge needed to recognize what problems you should solve using Lisp, and how to approach the solution's design.
Oh, and one more thing: It's not quite true that no mass market product uses Lisp. Microsoft's "Bob" environment for naive computer users was developed (and delivered) in Lisp.
--------------------------------------------------------------------------------
Lisp doesn't let me use graphical interfaces.
This is ironic. Some of the first graphical user interfaces appeared on Lisp machines in the early 1970s. In fact, in 1995 you can still buy a DOS adaptation of one of these early Lisp environments -- with the same GUI it had twenty years ago.
The leading Lisp development environments for Windows and Macintosh support only a subset of their host platform's GUI. It's possible to add support for the missing features, but easier to do it using Microsoft's and Apple's preferred language: C++.
If you want to have the same graphical user interface on your Lisp program when it runs on Windows or Macintosh hosts, you can find at least two Lisp windowing environments that let you do this. The problem is that the Lisp GUI will be familiar to neither Macintosh nor Windows users.
If all you want is a quick, platform-specific graphical interface for your Lisp program, any of the commercial Lisp environments will deliver what you need. They all have graphical interface builders that let you build windows and dialogs with point and click or drag and drop techniques. Just don't expect much in the way of bells and whistles.
--------------------------------------------------------------------------------
I can't call other people's code from Lisp.
This is mostly untrue. Most Lisp environments give you a way to call external routines using either C or Pascal calling conventions. You can also call back into Lisp from the external program. But if you want to call C++ from Lisp, you'll probably have to write a C wrapper around the C++ code.
--------------------------------------------------------------------------------
Lisp's garbage collector causes unpredictable pauses when my program runs.
This should probably be covered in the "Lisp is slow" discussion, but there are enough interesting digressions for this to warrant its own topic. Lisp programs create garbage by destroying all references to some object in memory. In a program written in some other language, the programmer must arrange to release the memory occupied by the object at the same time when the last reference is destroyed. If the program fails to do this reliably, the program has a memory leak -- eventually the program's memory space could fill up with these unreachable objects and not leave enough free memory for the program to continue. If you've ever written a complex program that allocates and manually recycles a lot of dynamic memory, you know how difficult a problem this can be.
Lisp finesses the memory leakage problem by never allowing the programmer to release unused memory. The idea here is that the computer can determine when a block of memory is unreachable with complete accuracy. This unreachable block is said to be garbage because it is no longer useful to any part of the program. The garbage collector runs automatically to gather all these unused blocks of memory and prepare them for reuse. The algorithms that do this are very tricky, but they come built into your Lisp system.
Historically, garbage collection has been slow. The earliest garbage collectors could literally lock up a system for hours. Performance was so poor that early Lisp programmers would run with garbage collection turned off until they completely ran out of memory, then start the garbage collection manually and go home for the rest of the day.
Over the past twenty years, a lot of good software engineering techniques have been applied to improving the performance of garbage collectors. Modern Lisp systems collect garbage almost continuously, a little bit at a time, rather than waiting and doing it all at once. The result is that even on a very slow desktop machine a pause for garbage collection will rarely exceed a second or two in duration.
Later in this book I'll discuss garbage collection in greater detail and show you techniques to avoid generating garbage; the less garbage your program creates, the less work the garbage collector will have to do.
--------------------------------------------------------------------------------
Lisp is a huge language.
If you look at the book Common Lisp: The Language, weighing in at about a thousand pages, or the recent (and bulkier) ANSI Standard X3.226: Programming Language Common Lisp, it's easy to form that opinion. When you consider that the Lisp language has almost no syntax, and only a couple of dozen primitive language elements (called special forms), then Lisp starts to look like a very small language.
In fact, the manuals cited above are mostly concerned with descriptions of what most other languages would call library functions and, to a lesser degree, development tools. Take the language manual for your favorite language. Add the manuals for three or four third-party libraries -- development utilities, fancy data structures, generalized I/O, etc. Take all the manuals for your development tools -- browsers, inspectors, debuggers, etc. and toss them onto the growing pile. Now count the pages. Does a thousand pages still seem like a lot?
By the time you've finished this book, you'll know how to find what you need in Lisp, with or without a manual.
--------------------------------------------------------------------------------
Lisp is only for artificial intelligence research.
Just not true. Lisp gets used for big projects that have to be tackled by one or a few programmers. Lisp is also good for tasks that are not well defined, or that require some experimentation to find the proper solution. As it turns out, artificial intelligence meets all of these criteria. So do a lot of other applications: shop job scheduling, transportation routing, military logistics, sonar and seismological echo feature extraction, currency trading, computer and computer network configuration, industrial process diagnosis, and more. These aren't mass market applications, but they still make lots of money (often by avoiding cost) for the organizations that develop them.
--------------------------------------------------------------------------------
Lisp doesn't have any good programming tools.
I hope to convince you otherwise. Several chapters of this book are devoted to introducing you to the many useful tools provided by a Lisp development environment.
--------------------------------------------------------------------------------
Lisp uses too much memory.
The Lisp development systems on both my Mac and my PC run comfortably in anywhere from 4 to 8 megabytes of RAM. Less in a pinch. The integrated C++ development environments take anywhere from 12 to 20 megabytes. Both have comparable tools and facilities.
--------------------------------------------------------------------------------
Lisp uses too much disk space.
The Lisp development systems on both my Mac and my PC use considerably less disk space than the C++ environments. Lisp space on my hard disk runs from a low of about 5 megabytes for one system to a high of about 30 megabytes for another system that is a total programming environment, including a built in file manager, WYSIWYG word processor, graphics program, appointment calendar, and (almost forgot) Lisp development environment. The C++ systems run from a low of about 20 megabytes to a high of about 150 megabytes.
--------------------------------------------------------------------------------
I can't find a good Lisp compiler.
Depending on what kind of computer you use, this was a problem as recently as a year or two ago. And it's true that there isn't a lot of competition for the Lisp marketplace -- you can count vendors on the fingers of one hand. The vendors who support the Lisp marketplace tend to have been around for a long time and have good reputations. As desktop computers increase in speed and storage capacity, Lisp vendors are increasingly turning their attention to these platforms. Appendix B of this book lists not only the current players in the field, but also their corporate lineage.
================================================================
Chapter 2 - Is this Book for Me?
Depending upon your background, interest, and experience, your need for the information offered in this book is best met by following the material in a certain way. I think that most readers will place themselves in one of the following categories: professional programmer, student, hobbyist, former Lisp user, or merely curious. No matter which category you fit, I've described what I think you can gain by reading this book. As you read through this book, you may decide that you no longer fit your original category. This is fine -- there are no strong dependencies between chapters. If you get stuck on a particular concept, the detailed Table of Contents will help you locate the information you need.
--------------------------------------------------------------------------------
The Professional Programmer
This book tells you what you need to know about Lisp in order to write good programs, and to read Lisp code in journals, magazines, or other people's programs. Beyond that, I will introduce you to some important concepts that you may not have encountered in your use of other languages, or you may find that the Lisp approach to a familiar concept gives you a new perspective on an old idea. Even if you never have occasion to use Lisp on the job, the concepts you'll learn in this book may give you a fresh insight to help solve a tough problem in your favorite language. You'll probably want to skim up through Chapter 6 to make sure you've covered the basics. Then slow down and take a closer look at what interests you in Chapter 7 through Chapter 9, Chapter 11 through Chapter 15, Chapter 17 through Chapter 21, Chapter 23, and Chapter 24; these chapters cover concepts that are either unique to, or best expressed in, the Lisp language.
Beyond all else, I hope to impress upon you the dynamic nature of Lisp program development. Lisp usually is a pleasant surprise to someone accustomed (or resigned) to the usual edit, compile, link, and debug cycle. The biggest change is compilation of functions rather than files. You can change and recompile just one function at a time, even from within the debugger. This is really handy if you've spent hours of testing to find a problem that can be easily fixed with one small change to your program. This is just one example of how the Lisp programming environment supports your programming efforts. You'll find additional examples throughout this book. Chapter 10, Chapter 16, Chapter 22, and Chapter 26 through Chapter 28 will give you an appreciation of how Lisp supports dynamic program development.
Professional Track
--------------------------------------------------------------------------------
The Student
If you've learned Lisp in a typical classroom setting, you may have come to believe that the language is nothing but lists and recursion. This book will show you that Lisp has a rich assortment of data types and control structures. Lists and recursion are only the tip of the iceberg. Chapter 3 through Chapter 24 should fill in the details on the rest of Lisp. Skim the remaining chapters so you know where to look when you have access to a commercial Lisp development environment, for when you begin your first Lisp project outside of an academic setting.
Depending upon whether you're currently taking a Lisp course, or have already finished a course and want to learn what the instructor didn't have time for, this book will help your studies by teaching you an appreciation for the language and the skills you'll need for its most effective use. Appendix A lists sources of Lisp development environments. You can use the freeware versions while you're still a poor, starving student, and refer to the list again when you're gainfully employed and want to either recommend a commercial implementation of Lisp to your employer or buy one for personal use.
Student Track
--------------------------------------------------------------------------------
The Hobbyist
To me, a hobbyist is someone who pursues programming for the challenge, for the learning experience, or as a pastime. The hobbyist is largely self taught. If you fit that mold, I'll warn you now that Lisp can be very challenging, and can teach you a lot about programming.
You can go quite a long way toward learning Lisp with one of the freeware systems available for Macintosh and DOS computers. But if you have aspirations to turn your hobby into a money making venture, you need to ask yourself whether Lisp is appropriate for your anticipated product or service. If you think in terms of databases or scripts or multimedia, you'll probably be happier with a tool that directly addresses your area of interest. If you have dreams of writing the next great videogame, you've probably already discovered that you need a language that lets you program "close to the machine" -- If so, Lisp will disappoint you. But if you want to give your game characters complex interactions, or even the appearance of intelligent behavior, Lisp is a wonderful vehicle in which to design and test prototypes of these behaviors.
No matter what your interest in programming as a hobby, this book will give you the understanding you need to explore Lisp without getting bogged down in the parentheses. Read through all of the chapters, spending more time on those which interest you the most. If you have access to a Lisp development system, spend time on Chapter 10, Chapter 16, Chapter 22, and Chapter 28 through Chapter 30; these chapters will give you the background you need in order to find your way when you get lost -- you'll find this more helpful than trying to develop an encyclopedic knowledge of the language.
Hobbyist Track
--------------------------------------------------------------------------------
The Former Lisp Acquaintance
If you've had a prior experience with Lisp, perhaps in a college or university programming class, this book will update your knowledge. This book will teach you things that a one semester class could never cover due to time constraints. You'll also see how commercial Lisp development systems provide tools and features missing from the freeware Lisp system that your educational institution probably used.
If you've worked on (or have attempted) a Lisp project before, you may not have had the benefit of a mentor to show you how to use Lisp effectively. This book will introduce you to the skills that you need to become a successful Lisp programmer. It is important that you understand what the language does; this book, like others before it, covers that ground. But this book goes beyond other Lisp programming books to tell you why Lisp works as it does, the best way to do things in Lisp, and (perhaps most importantly) how to approach the Lisp development environment to accomplish your goals in the most effective way.
I suggest that you use this book as a reference. The detailed Table of Contents will help you find subject areas that appeal to your interests or needs.
Former User Track
--------------------------------------------------------------------------------
The Curious
If you have no immediate intentions of writing a Lisp program (perhaps you're a student of programming languages), this book is still a good choice. You can learn a lot about Lisp, its development environment, and its use by reading through the chapters in order and working out an occasional bit of code on paper, to check your understanding. I've tried hard to introduce the fundamentals of Lisp in a way that doesn't belabor the details of internal representation.
Curious Reader Track
================================================================
Chapter 3 - Essential Lisp in Twelve Lessons
This chapter will teach you everything you need to know to get started with Lisp. I'll cover all of the core features of the language. I encourage you to think of this core as the Lisp language itself, and everything else as a very large standard library. With this background, you'll be much better equipped to learn the rest of Lisp, either by reading the rest of the book or via a reference manual such as Common Lisp: The Language, 2nd Edition.
You should read this chapter all the way through. At times, I mention other chapters and later sections of this chapter, but you shouldn't have to follow these references to understand this chapter. When you finish this chapter, you should work through Chapter 4 while sitting at the keyboard of your Lisp system.
Lesson 1 - Essential Syntax
Lesson 2 - Essential Evaluation
Lesson 3 - Some Examples of Special Forms and Macros
Lesson 4 - Putting things together, and taking them apart
Lesson 5 - Naming and Identity
Lesson 6 - Binding versus Assignment
Lesson 7 - Essential Function Definition
Lesson 8 - Essential Macro Definition
Lesson 9 - Essential Multiple Values
Lesson 10 - A Preview of Other Data Type
Lesson 11 - Essential Input and Output
Lesson 12 - Essential Reader Macros
================================================================
Chapter 3 - Essential Lisp in Twelve Lessons
Lesson 1 - Essential Syntax
Lists are surrounded by parentheses
This is the first thing you need to know about Lisp: anything surrounded by parentheses is a list. Here are some examples of things that are lists:
(1 2 3 4 5)
(a b c)
(cat 77 dog 89)
As I said, anything surrounded by parentheses is a list. When you hear a statement like that, you probably want to ask two questions:
What if I put parentheses around nothing?
What if I put parentheses around another list?
In both cases the answer is the same. You still have a list. So the following are also lists:
()
(())
((()))
((a b c))
((1 2) 3 4)
(mouse (monitor 512 342) (keyboard US))
(defun factorial (x) (if (eql x 0) 1 (* x (factorial (- x 1)))))
The only time you don't have a list is when you have a right parenthesis without a matching left parenthesis or vice versa, as in the following four examples:
(a b c(
((25 g) 34
((())
(()))
This is nothing to lose sleep over -- Lisp will tell you when there's a mismatch. Also, the editor that you use for writing Lisp programs will almost certainly give you a way to automatically find matching parentheses. We'll look at editors in Chapter 27.
A list can be a lot of things in Lisp. In the most general sense, a list can be either a program or data. And because lists can themselves be made of other lists, you can have arbitrary combinations of data and programs mixed at different levels of list structure -- this is what makes Lisp so flexible for those who understand it, and so confusing for those who don't. We'll work hard to remove that confusion as this chapter continues.
Atoms are separated by whitespace or parentheses Now that you can recognize a list, you'd like to have a name for the things that appear between the parentheses -- the things that are not themselves lists, but rather (in our examples so far) words and numbers. These things are called atoms.
Accordingly, these words and numbers are all atoms:
1
25
342
mouse
factorial
x
Lisp lets us use just about any characters to make up an atom. For now, we'll say that any sequence of letters, digits, and punctuation characters is an atom if it is preceded and followed by a blank space (this includes the beginning or end of a line) or a parenthesis. The following are all atoms:
-
*
@comport
funny%stuff
9^
case-2
One thing you should remember, if you're experienced in another programming language, is that characters traditionally reserved as operators have no special meaning when they appear within a Lisp atom. For example, case-2 is an atom, and not an arithmetic expression.
Since an atom can be marked off by either whitespace or a parenthesis, we could eliminate any whitespace between an atom and a parenthesis, or between two parentheses. Thus, the following two lists are identical:
(defun factorial (x) (if (eql x 0) 1 (* x (factorial (- x 1)))))
(defun factorial(x)(if(eql x 0)1(* x(factorial(- x 1)))))
In practice, we'd never write the second list. In fact, we'd probably split the list across multiple lines and indent each line to improve readability; this list is in fact a small program, and formatting it as follows makes it easier to read for a Lisp programmer:
(defun factorial (x)
(if (eql x 0)
1
(* x (factorial (- x 1)))))
For now, you don't need to worry about what this means or how you'd know to do this kind of indentation. As we get further into this chapter, you'll see more examples of indentation. Subsequent chapters will show additional examples, and I'll point out how to use indentation to improve readability of many new constructs. Chapter 28 will address elements of Lisp style, including the proper use of indentation.
================================================================
Chapter 3 - Essential Lisp in Twelve Lessons
Lesson 2 - Essential Evaluation
A form is meant to be evaluated
A form can be either an atom or a list. The important thing is that the form is meant to be evaluated. Evaluation has a fairly technical definition that we'll gradually expose in this section.
Evaluation is simple if the form is an atom. Lisp treats the atom as a name, and retrieves the value for the name (if a value exists). You probably wonder why I'm avoiding the more direct explanation of calling the atom a variable. The reason is that the atom can have either a variable value or a constant value. And the atom's value can be constant for a couple of reasons.
A number is an atom. (Its value is constant for obvious reasons.) Lisp does not store a value for a number -- the number is said to be self-evaluating.
We're going to introduce a new term without a complete definition. For now, think of a symbol as an atom that can have a value. We'll look at symbols in greater detail when we get to Lesson 5.
A symbol defined in a defconstant form has a constant value. Lisp will store the value as if the atom had a variable value, and add a note to the effect that the value is not allowed to change.
A symbol in the KEYWORD package is self-evaluating. We'll look at packages in detail in Chapter 31. For now, all you need to know is that a symbol beginning with the : character (called the package prefix) is a keyword symbol. Keyword symbols have themselves as their values.
A symbol can get a variable value in many different ways. Lisp actually keeps several different values for a symbol. One has the traditional meaning as the value of the symbol taken as a variable. Another has meaning as the symbol's function. Still others keep track of the symbol's documentation, its printed representation, and properties that the programmer chooses to associate with the symbol. We'll explore some of these in more detail in Lesson 5, Lesson 6, and Lesson 7.
If a form is a list, then the first element must be either a symbol or a special form called a lambda expression. (We won't look at lambda expressions for a while.) The symbol must name a function. In Lisp, the symbols +, -, *, and / name the four common arithmetic operations: addition, subtraction, multiplication, and division. Each of these symbols has an associated function that performs the arithmetic operation.
So when Lisp evaluates the form (+ 2 3), it applies the function for addition to the arguments 2 and 3, giving the expected result 5. Notice how the function symbol, +, precedes its arguments. This is prefix notation. Any time you see a list, look to its first element to find out what Lisp will do to evaluate the list as a form.
A function is applied to its arguments
Lisp, when given a list to evaluate, treats the form as a function call. We'll be looking a lot at Lisp evaluation from now on, so we'll use some visual aids to identify the input to Lisp and its responses:
the Lisp prompt precedes input to Lisp
result of Lisp evaluation
For example:
(+ 4 9)
13
(- 5 7)
-2
(* 3 9)
27
(/ 15.0 2)
7.5
In each case above, the evaluated form is a list. Its first element is a symbol, which names a function. The remaining elements are arguments of the function. Here, the arguments are all numbers, and we know that numbers are self-evaluating.
Here are a few more examples:
(atom 123)
T
(numberp 123)
T
(atom :foo)
T
(numberp :foo)
NIL
ATOM and NUMBERP are predicates. Predicates return a true or false value. NIL is the only false value in Lisp -- everything else is true. Unless a predicate has a more useful value to return, it conventionally returns T to mean true. ATOM returns T if its one argument is a Lisp atom. NUMBERP returns T if its argument is a number.
To evaluate each of the above forms, Lisp first evaluates the arguments (from left to right), then evaluates the first element to get its function, then applies the function to the arguments. With only a handful of exceptions, which we'll learn about at the end of this lesson, Lisp always does the same thing to evaluate a list form:
Evaluate the arguments, from left to right.
Get the function associated with the first element.
Apply the function to the arguments.
Remember that an atom can also be a Lisp form. When given an atom to evaluate, Lisp simply returns its value:
17.95
17.95
:A-KEYWORD
:A-KEYWORD
*FEATURES*
(:ANSI-CL :CLOS :COMMON-LISP)
"Hello, world!"
"Hello, world!"
WHAT-IS-THIS?
Error: Unbound variable
Numbers and keywords are self-evaluating. So are strings. The *FEATURES* variable is predefined by Lisp -- your system will probably return a different value.
The symbol WHAT-IS-THIS? doesn't have a value, because it's not predefined by Lisp, and I haven't given it a value. The system responds with an error message, rather than a value. We mark the message with rather than the marker we use for successful evaluations. Your system will probably print a different message.
A function can return any number of values
Sometimes you'd like to have a function return several values. For example, a function which looks up a database entry might return both the desired result and a completion status code. One way to do this is to pass to the function a location for one of the results; this is possible, but very uncommon for a Lisp program.
Another approach creates a single return value to combine both the result and the status code. Lisp gives you several different ways to do this, including structures. Experienced Lisp programmers don't do this when the created value will just be taken apart into its components and then forgotten, since the composite value then becomes garbage (see Chapter 29) that eventually slows down the operation of the program.
The right way to return multiple values from a function is to use the VALUES form. We'll see VALUES used in the context of a function in a little while. For now, let's see what happens when Lisp evaluates a VALUES form:
(values 1 2 3 :hi "Hello")
1
2
3
:HI
"Hello"
Notice how Lisp returned a value (following the indicator) for each argument to the VALUES form. My Lisp system represents this by printing each value on a new line; yours may separate the values some other way.
Arguments are usually not modified by a function
I mentioned earlier that you can pass a location to a function, and have the function change the location's value. This is a very uncommon practice for a Lisp program, even though other languages make it part of their standard repertoire.
You could specify the location to be modified as either a non-keyword symbol or a composite value -- obviously, you can't modify a constant. If you provide a symbol, then your function must execute code to give the symbol a new value. If you provide a composite data structure, your function must execute code to change the correct piece of the composite value. It's harder to write Lisp code to do this, and it's harder to understand programs written this way. So Lisp programmers usually write functions that get their inputs from parameters, and produce their outputs as the function result.
Arguments are usually evaluated before function application
When Lisp evaluates a function, it always evaluates all the arguments first, as we saw earlier. Unfortunately, every rule has exceptions, and this rule is no exception (as we'll soon see)... The problem is not that Lisp doesn't always evaluate a function's arguments, but that not every list form is a function call.
Arguments are evaluated in left-to-right order
When a list form is a function call, its arguments are always evaluated in order, from left to right. As in other programming languages, it's in poor taste to rely on this, but if you absolutely have to rely on the order, it's good to know that Lisp defines it for you.
Special forms and macros change argument evaluation
So if a list form isn't always a function call, what else can it be? There are two cases, but the result is the same: some arguments are evaluated, and some aren't. Which is which depends upon the form and nothing else. You'll just have to learn the exceptions. Fortunately, most Lisp systems will show you the online documentation for any form with just a keystroke or two.
There are two kinds of forms that don't evaluate all of their arguments: special forms and macros. Lisp predefines a small number of special forms. You can't add your own special forms -- they're primitive features of the language itself. Lisp also defines quite a few macros. You can also define your own macros. Macros in Lisp let you use the full power of the language to add your own features. Later in this chapter we'll look briefly at how to define simple macros. In Chapter 20 we'll cover topics surrounding the creation of more complex macros.
================================================================
Chapter 3 - Essential Lisp in Twelve Lessons
Lesson 3 - Some Examples of Special Forms and Macros
Now we'll look at several special forms and macros. Over the next four lessons, we'll build up a repertoire that will let you write simple functions using the most elementary Lisp data type, the list. Later chapters will cover more complex program structures and data types.
SETQ
Earlier, I told you that Lisp evaluates a symbol form by retrieving its variable value. SETQ gives you a way to set that value:
(setq my-name "David")
"David"
my-name
"David"
(setq a-variable 57)
57
a-variable
57
(setq a-variable :a-keyword)
:A-KEYWORD
SETQ's first argument is a symbol. This is not evaluated. The second argument is assigned as the variable's value. SETQ returns the value of its last argument.
SETQ doesn't evaluate its first argument because you want to assign a value to the symbol itself. If SETQ evaluated its first argument, the value of that argument would have to be a symbol. The SET form does this:
(setq var-1 'var-2)
VAR-2
var-1
VAR-2
var-2
Error: Unbound variable
(set var-1 99)
99
var-1
VAR-2
VAR-2
99
Did you notice the ' in the first form? This keeps the following form, var-2, from being evaluated. Later in this lesson, when we look at QUOTE, I'll explain this in greater detail.
In the example, we first make the value of VAR-1 be the symbol VAR-2. Checking the value of VAR-2, we find that it has none. Next, we use SET (not SETQ) to assign the value 99 to the symbol, VAR-2, which is the value of VAR-1.
The SETQ form can actually take any even number of arguments, which should be alternating symbols and values:
(setq month "June" day 8 year 1954)
1954
month
"June"
day
8
year
1954
SETQ performs the assignments from left to right, and returns the rightmost value.
LET
The LET form looks a little more complicated that what we've seen so far. The LET form uses nested lists, but because it's a special form, only certain elements get evaluated.
(let ((a 3)
(b 4)
(c 5))
(* (+ a b) c))
35
a
Error: Unbound variable
b
Error: Unbound variable
c
Error: Unbound variable
The above LET form defines values for the symbols A, B, and C, then uses these as variables in an arithmetic calculation. The calculation's result is also the result of the LET form. Note that none of the variables defined in the LET have a value after Lisp has finished evaluating the form.
In general, LET looks like this:
(let (bindings) forms)
where bindings is any number of two-element lists -- each list containing a symbol and a value -- and forms is any number of Lisp forms. The forms are evaluated, in order, using the values established by the bindings. LET returns the value(s) returned by the last form.
Indentation doesn't affect the operation of LET, but proper indentation does improve readability. Consider these equivalent forms:
(let ((p 52.8)
(q 35.9)
(r (f 12.07)))
(g 18.3)
(f p)
(f q)
(g r t))
(let ((p 52.8) (q 35.9) (r (f 12.07))) (g 18.3) (f p) (f q) (g r t))
In the first case, indentation makes clear which are the bindings and which are the forms. Even if the reader doesn't know about the different roles played by the two parts of the LET form, the indentation suggests a difference.
In the second case, you'll have to count parentheses to know where the bindings end and the forms begin. Even worse, the absence of indentation destroys visual cues about the different roles played by the two parts of the LET form.
If you define a variable using SETQ and then name the same variable in a LET form, the value defined by LET supersedes the other value during evaluation of the LET:
(setq a 89)
89
a
89
(let ((a 3))
(+ a 2))
5
a
89
Unlike SETQ, which assigns values in left-to-right order, LET binds variables all at the same time:
(setq w 77)
77
(let ((w 8)
(x w))
(+ w x))
85
LET bound W to 8 and X to W. Because these bindings happened at the same time, W still had its value of 77.
Lisp has a variation of LET, called LET*, that does perform bindings in order:
(setq u 37)
37
(let* ((v 4)
(u v))
(+ u v))
8
COND
The COND macro lets you evaluate Lisp forms conditionally. Like LET, COND uses parentheses to delimit different parts of the form. Consider these examples:
(let ((a 1)
(b 2)
(c 1)
(d 1))
(cond ((eql a b) 1)
((eql a c) "First form" 2)
((eql a d) 3)))
2
In the above COND form we defined three clauses. Each clause is a list beginning with a test form and followed by as many body forms as desired. The body forms are simply code that you want to execute if the test succeeds. The clauses are selected in order -- as soon as one test succeeds, the corresponding body forms are evaluated and the value of the last body form becomes the value of the COND form.
COND is more general than the special form, IF, which only allows one test and one form each for the then and else parts.
Let's look at what happened in the example. EQL returns T if its two arguments are identical, or the same number (there's a subtle difference that we'll cover in Chapter 17). Only two of the three tests executed. The first, (EQL A B), returned NIL. Therefore, the rest of that clause (containing the number 1 as its only form) was skipped. The second clause tested (EQL A C), which was true. Because this test returned a non-NIL value, the remainder of the clause (the two atomic forms, "First form" and 2) was evaluated, and the value of the last form was returned as the value of the COND, which was then returned as the value of the enclosing LET. The third clause was never tested, since an earlier clause had already been chosen -- clauses are tested in order.
Conventional use of COND uses T as the test form in the final clause. This guarantees that the body forms of the final clause get evaluated if the tests fail in all of the other clauses. You can use the last clause to return a default value or perform some appropriate operation. Here's an example:
(let ((a 32))
(cond ((eql a 13) "An unlucky number")
((eql a 99) "A lucky number")
(t "Nothing special about this number")))
"Nothing special about this number"
QUOTE
Sometimes we'd like to suppress Lisp's normal evaluation rules. One such case is when we'd like a symbol to stand for itself, rather than its value, when it appears as an argument of a function call:
(setq a 97)
97
a
97
(setq b 23)
23
(setq a b)
23
a
23
(setq a (quote b))
B
a
B
The difference is that B's value is used in (SETQ A B), whereas B stands for itself in (SETQ A (QUOTE B)).
The QUOTE form is so commonly used that Lisp provides a shorthand notation:
(QUOTE form) 'form
The symbol means that the two Lisp forms are equivalent. Lisp arranges the equivalence of ' and QUOTE through a reader macro. We'll take a brief look at how you can define your own reader macros in Lesson 12.
================================================================
Chapter 3 - Essential Lisp in Twelve Lessons
Lesson 4 - Putting things together, and taking them apart
CONS
CONS is the most basic constructor of lists. It is a function, so it evaluates both of its arguments. The second argument must be a list or NIL.
(cons 1 nil)
(1)
(cons 2 (cons 1 nil))
(2 1)
(cons 3 (cons 2 (cons 1 nil)))
(3 2 1)
CONS adds a new item to the beginning of a list. The empty list is equivalent to NIL,
() NIL
so we could also have written:
(cons 1 ())
(1)
(cons 2 (cons 1 ()))
(2 1)
(cons 3 (cons 2 (cons 1 ())))
(3 2 1)
In case you're wondering, yes, there's something special about NIL. NIL is one of two symbols in Lisp that isn't a keyword but still has itself as its constant value. T is the other symbol that works like this.
The fact that NIL evaluates to itself, combined with () NIL, means that you can write () rather than (QUOTE ()). Otherwise, Lisp would have to make an exception to its evaluation rule to handle the empty list.
LIST
As you may have noticed, building a list out of nested CONS forms can be a bit tedious. The LIST form does the same thing in a more perspicuous manner:
(list 1 2 3)
(1 2 3)
LIST can take any number of arguments. Because LIST is a function, it evaluates its arguments:
(list 1 2 :hello "there" 3)
(1 2 :HELLO "there" 3)
(let ((a :this)
(b :and)
(c :that))
(list a 1 b c 2))
(:THIS 1 :AND :THAT 2)
FIRST and REST
If you think of a list as being made up of two parts -- the first element and everything else -- then you can retrieve any individual element of a list using the two operations, FIRST and REST.
(setq my-list (quote (1 2 3 4 5)))
(1 2 3 4 5)
(first my-list)
1
(rest my-list)
(2 3 4 5)
(first (rest my-list))
2
(rest (rest my-list))
(3 4 5)
(first (rest (rest my-list)))
3
(rest (rest (rest my-list)))
(4 5)
(first (rest (rest (rest my-list))))
4
Clearly, chaining together FIRST and REST functions could become tedious. Also, the approach can't work when you need to select a particular element when the program runs, or when the list is of indeterminate length. We'll look at how to solve these problems in Chapter 4 by defining recursive functions. Later, in Chapter 13, we'll see the functions that Lisp provides to perform selection on the elements of lists and other sequences.
FIRST and REST are fairly recent additions to Lisp, renaming the equivalent functions CAR and CDR, respectively. CAR and CDR got their names from an implementation detail of one of the earliest Lisp implementations, and the names persisted for decades despite the fact that the underlying implementation had long since changed.
================================================================
Chapter 3 - Essential Lisp in Twelve Lessons
Lesson 5 - Naming and Identity
A symbol is just a name
A symbol is just a name. It can stand for itself. This makes it easy to write certain kinds of programs in Lisp. For example, if you want your program to represent relationships in your family tree, you can make a database that keeps relationships like this:
(father John Barry)
(son John Harold)
(father John Susan)
(mother Edith Barry)
(mother Edith Susan)
...
Each relationship is a list. (father John Barry) means that John is Barry's father. Every element of every list in our database is a symbol. Your Lisp program can compare symbols in this database to determine, for example, that Harold is Barry's grandfather. If you tried to write a program like this in another language -- a language without symbols -- you'd have to decide how to represent the names of family members and relationships, and then create code to perform all the needed operations -- reading, printing, comparison, assignment, etc. This is all built into Lisp, because symbols are a data type distinct from the objects they might be used to name.
A symbol is always unique
Every time your program uses a symbol, that symbol is identical to every other symbol with the same name. You can use the EQ test to compare symbols:
(eq 'a 'a)
T
(eq 'david 'a)
NIL
(eq 'David 'DAVID)
T
(setq zzz 'sleeper)
SLEEPER
(eq zzz 'sleeper)
T
Notice that it doesn't matter whether you use uppercase or lowercase letters in your symbol names. Internally, Lisp translates every alphabetic character in a symbol name to a common case -- usually upper, but you can control this by setting a flag in the Lisp reader.
When you learn about packages in Lesson 10 (also see Chapter 31), you can create symbol names that are not identical given the same spelling. For now, all you need to know is that any symbol spelled with a : gets special treatment.
A symbol can name a value
Although the ability for a Lisp symbol to stand for itself is sometimes useful, a more common use is for the symbol to name a value. This is the role played by variable and function names in other programming languages. A Lisp symbol most commonly names a value or -- when used as the first element of a function call form -- a function.
What's unusual about Lisp is that a symbol can have a value as a function and a variable at the same time:
(setq first 'number-one)
NUMBER-ONE
(first (list 3 2 1))
3
first
NUMBER-ONE
Note how FIRST is used as a variable in the first and last case, and as a function (predefined by Lisp, in this example) in the second case. Lisp decides which of these values to use based on where the symbol appears. When the evaluation rule requires a value, Lisp looks for the variable value of the symbol. When a function is called for, Lisp looks for the symbol's function.
A symbol can have other values besides those it has as a variable or function. A symbol can also have values for its documentation, property list, and print name. A symbol's documentation is text that you create to describe a symbol. You can create this using the DOCUMENTATION form or as part of certain forms which define a symbol's value. Because a symbol can have multiple meanings, you can assign documentation to each of several meanings, for example as a function and as a variable.
A property list is like a small database with a single key per entry. We'll look at this use of symbols in Lesson 10.
The print name is what Lisp uses to print the symbol. You normally don't want to change this; if you do, Lisp will print the symbol with a different name than it originally used to read the symbol, which will create a different symbol when later read by Lisp.
A value can have more than one name
A value can have more than one name. That is, more than one symbol can share a value. Other languages have pointers that work this way. Lisp does not expose pointers to the programmer, but does have shared objects. An object is considered identical when it passes the EQ test. Consider the following:
(setq L1 (list 'a 'b 'c))
(A B C)
(setq L2 L1)
(A B C)
(eq L1 L2)
T
(setq L3 (list 'a 'b 'c))
(A B C)
(eq L3 L1)
NIL
Here, L1 is EQ to L2 because L1 names the same value as L2. In other words, the value created by the (LIST 'A 'B 'C) form has two names, L1 and L2. The (SETQ L2 L1) form says, "Make the value of L2 be the value of L1." Not a copy of the the value, but the value. So L1 and L2 share the same value -- the list (A B C) which was first assigned as the value of L1.
L3 also has a list (A B C) as its value, but it is a different list than the one shared by L1 and L2. Even though the value of L3 looks the same as the value of L1 and L2, it is a different list because it was created by a different LIST form. So (EQ L3 L1)NIL because their values are different lists, each made of the symbols A, B, and C.
================================================================
Chapter 3 - Essential Lisp in Twelve Lessons
Lesson 6 - Binding versus Assignment
Binding creates a new place to hold a value
Lisp often "creates a binding" for a variable by allocating a piece of storage to hold the variable's value and putting the value into the newly allocated memory. Binding is a very general mechanism for implementing lexical scope for variables, but it has other uses depending upon the lifetime of the binding. We'll revisit this in Chapter 8 when we study lifetime and visibility.
Yes, Lisp allocates storage for new bindings. While this sounds like it could be horribly inefficient, we've said nothing yet about where Lisp allocated the storage. For example, Lisp binds function parameters to actual values, but allocates the storage on the stack just like any other programming language. Lisp creates bindings in the heap if it can't determine that the binding has a lifetime which ends when the binding form finishes executing.
Bindings have names
Lisp gives each binding a name. Otherwise, how would your program refer to the binding? Simple, eh? Hold on...
A binding can have different values at the same time
It is quite common for multiple bindings to share the same name. For example:
(let ((a 1))
(let ((a 2))
(let ((a 3))
...)))
Here, A has three distinct bindings by the time the body (marked by ...) executes in the innermost LET.
This is not to say that the above example is representative of typical Lisp code, however.
One binding is innermost
;; Here, A has no binding.
(let ((a 1))
;; Here, the innermost binding of A has the value 1.
(let ((a 2))
;; Here, the innermost binding of A has the value 2.
(let ((a 3))
;; Here, the innermost binding of A has the value 3.
...)))
As you can see, the notion of innermost binding depends on the relative position of your program's code to the form that established a particular binding. If you look at how binding forms are nested (easy to do if you indent your code as shown above) then the program has access to bindings created around, or enclosing, your program code.
One more thing you should know is that an outer binding is still visible through inner binding forms, as long as the inner binding form does not bind the same symbol:
;; Here, A and B have no binding.
(let ((a 1)
(b 9))
;; Here, the innermost binding of A has the value 1,
;; and the binding of B has the value 9.
(let ((a 2))
;; Here, the innermost binding of A has the value 2.
;; The binding of B still has the value 9.
(let ((a 3))
;; Here, the innermost binding of A has the value 3.
;; B still has the value 9 from the outermost LET form.
...)))
The program can only access bindings it creates
When a binding form binds a new value to an existing symbol, the previous value becomes shadowed. The value of the outer binding is hidden (but not forgotten) while your program code executes inside the inner binding form. But as soon as your program leaves the inner binding form, the value of the outer binding is restored. For example:
(let ((z 1))
;; Here, the innermost binding of Z has the value 1.
(let ((z 2))
;; Here, the innermost binding of Z has the value 2.
...)
;; Now we're outside the inner binding form,
;; and we again see the binding with the value 1.
...)
Assignment gives an old place a new value
The SETQ form changes the value of an existing binding:
(let ((z 1))
;; Here, the innermost binding of Z has the value 1.
(setq z 9)
;; Now the value of Z is 9.
(let ((z 2))
;; Here, the innermost binding of Z has the value 2.
...)
;; Now we're outside the inner binding form,
;; and we again see the outer binding of Z with the value 9.
...)
The SETQ form above changed the value of the outer binding of Z for the remainder of the outer LET form. This is often the wrong thing to do. The problem is that you now have to look in two places to discover the value of Z -- first at the binding forms, then in the program code for assignments such as SETQ. While the binding forms are indented by convention (many Lisp editors do this as you type), the assignment form, as part of the body code of the program, gets no special indentation; this makes it harder to spot when you read the program.
We can quite easily avoid the assignment in the previous example by introducing a new binding:
(let ((z 1))
;; Here, the innermost binding of Z has the value 1.
(let ((z 9))
;; Now the value of Z is 9.
(let ((z 2))
;; Here, the innermost binding of Z has the value 2.
...)
;; Now we're outside the innermost binding form,
;; and we again see the middle binding of Z with the value 9.
...)
;; Here, we see the outermost binding of Z with the value 1.
...)
Now all of the bindings of Z are apparent from the relative indentation of the LET forms. While reading the program, all we have to do to find the right binding for Z at any point in our program code (the ... in the example) is to scan vertically looking for a LET form at an outer level of indentation.
When a SETQ form refers to a variable that is not bound by an enclosing LET form, it assigns a value to the global or special value of the symbol. A global value is accessible anywhere it's not shadowed, and stays available for as long as the Lisp system runs. We'll look at special variables in Chapter 8.
(setq a 987)
;; Here, A has the global value 987.
(let ((a 1))
;; Here, the binding of A to the value 1 shadows the global value.
...)
;; Now the global value of A is again visible.
...
================================================================
Chapter 3 - Essential Lisp in Twelve Lessons
Lesson 7 - Essential Function Definition
DEFUN defines named functions
You can define a named function using the DEFUN form:
(defun secret-number (the-number)
(let ((the-secret 37))
(cond ((= the-number the-secret) 'that-is-the-secret-number)
((< the-number the-secret) 'too-low)
((> the-number the-secret) 'too-high))))
SECRET-NUMBER
We described LET, COND, and ' (a.k.a. QUOTE) in Lesson 3. The numeric comparison functions have the obvious meaning.
The DEFUN form has three arguments:
the name of the function: SECRET-NUMBER,
a list of argument names: (THE-NUMBER), which will be bound to the function's parameters when it is called, and
the body of the function: (LET ...).
Since all three of these should stand for themselves, DEFUN does not evaluate any of its arguments. (If it did, you'd face the inconvenience of having to quote each argument.)
DEFUN returns the name of the defined function, and installs a global definition using the name, parameter list, and body that you supplied. Once you create a function using DEFUN, you can use it right away:
(secret-number 11)
TOO-LOW
(secret-number 99)
TOO-HIGH
(secret-number 37)
THAT-IS-THE-SECRET-NUMBER
When you call the function, its parameter (e.g. 99 in the second example) is bound to the argument name (i.e. THE-NUMBER) you supplied in the definition. Then, the body of the function (i.e. (LET ...)) is evaluated within the context of the parameter binding. In other words, evaluating (SECRET-NUMBER 99) causes the body of the SECRET-NUMBER function definition to be executed with the variable THE-NUMBER bound to 99.
Of course, you can define a function of more than one argument:
(defun my-calculation (a b c x)
(+ (* a (* x x)) (* b x) c))
MY-CALCULATION
(my-calculation 3 2 7 5)
92
When calling a function, parameters are bound to argument names in order. Lisp has several optional variations on the list of argument names. Formally, this list is called a lambda list -- we'll examine some of its other features in Chapter 21.
LAMBDA defines anonymous functions
At times you'll need a function in only one place in your program. You could create a function with DEFUN and call it just once. Sometimes, this is the best thing to do, because you can give the function a descriptive name that will help you read the program at some later date. But sometimes the function you need is so trivial or so obvious that you don't want to have to invent a name or worry about whether the name might be in use somewhere else. For situations like this, Lisp lets you create an unnamed, or anonymous, function using the LAMBDA form. A LAMBDA form looks like a DEFUN form without the name:
(lambda (a b c x)
(+ (* a (* x x)) (* b x) c))
You can't evaluate a LAMBDA form; it must appear only where Lisp expects to find a function -- normally as the first element of a form:
(lambda (a b c x)
(+ (* a (* x x)) (* b x) c))
Error
((lambda (a b c x)
(+ (* a (* x x)) (* b x) c))
3 2 7 5)
92
================================================================
Chapter 3 - Essential Lisp in Twelve Lessons
Lesson 8 - Essential Macro Definition
DEFMACRO defines named macros
A DEFMACRO form looks a lot like a DEFUN form (see Lesson 7) -- it has a name, a list of argument names, and a body:
(defmacro name (argument ...)
body)
Macros return a form, not values
The macro body returns a form to be evaluated. In other words, you need to write the body of the macro such that it returns a form, not a value. When Lisp evaluates a call to your macro, it first evaluates the body of your macro definition, then evaluates the result of the first evaluation. (By way of comparison, a function's body is evaluated to return a value.)
Here are a couple of simple macros to illustrate most of what you need to know:
(defmacro setq-literal (place literal)
`(setq ,place ',literal))
SETQ-LITERAL
(setq-literal a b)
B
a
B
(defmacro reverse-cons (rest first)
`(cons ,first ,rest))
REVERSE-CONS
(reverse-cons nil A)
(B)
SETQ-LITERAL works like SETQ, except that neither argument is evaluated. (Remember that SETQ evaluates its second argument.) The body of SETQ-LITERAL has a form that begins with a ` (pronounced "backquote"). Backquote behaves like quote -- suppressing evaluation of all the enclosed forms -- except where a comma appears within the backquoted form. A symbol following the comma is evaluated.
So in our call to (SETQ-LITERAL A B) above, here's what happens:
bind PLACE to the symbol A.
bind LITERAL to the symbol B.
evaluate the body `(SETQ ,PLACE ',LITERAL), following these steps:
evaluate PLACE to get the symbol A.
evaluate LITERAL to get the symbol B.
return the form (SETQ A 'B).
evaluate the form (SETQ A 'B).
Neither the backquote nor the commas appear in the returned form. Neither A nor B is evaluated in a call to SETQ-LITERAL, but for different reasons. A is unevaluated because it appears as the first argument of SETQ. B is unevaluated because it appears after a quote in the form returned by the macro.
The operation of (REVERSE-CONS NIL A) is similar:
bind REST to the symbol NIL.
bind FIRST to the symbol A.
evaluate the body `(CONS ,FIRST ,REST), following these steps:
evaluate FIRST to get the symbol A.
evaluate REST to get the symbol NIL.
return the form (CONS A NIL).
evaluate the form (CONS A NIL).
Both arguments of REVERSE-CONS are evaluated because CONS evaluates its arguments, and our macro body doesn't quote either argument. A evaluates to the symbol B, and NIL evaluates to itself.
If you want to see how your macro body appears before evaluation, you can use the MACROEXPAND function:
(macroexpand '(setq-literal a b))
(SETQ A 'B)
(macroexpand '(reverse-cons nil a))
(CONS A NIL)
Since MACROEXPAND is a function, it evaluates its arguments. This is why you have to quote the form you want expanded.
The examples in this lesson are deliberately very simple, so you can understand the basic mechanism. In general, macros are trickier to write than functions -- in Chapter 20 we'll look at the reasons and the correct techniques for dealing with more complex situations.
================================================================
Chapter 3 - Essential Lisp in Twelve Lessons
Lesson 9 - Essential Multiple Values
Most forms create only one value
A form typically returns only one value. Lisp has only a small number of forms which create or receive multiple values.
VALUES creates multiple (or no) values
The VALUES form creates zero or more values:
(values)
(values :this)
:THIS
(values :this :that)
:THIS
:THAT
We show how many values are returned by the number of lines produced by the evaluation of the form. The three VALUES forms in the example above produced zero, one, and two values, respectively.
VALUES is a function, and so evaluates its arguments.
A few special forms receive multiple values
What might you want to do with multiple values in a program? The most basic operations are to:
bind each value to a separate symbol, or
collect the values into a list.
Use MULTIPLE-VALUE-BIND to bind each value to a separate symbol:
(multiple-value-bind (a b c) (values 2 3 5)
(+ a b c))
13
If you provide more values than symbols, the excess values are ignored:
(multiple-value-bind (a b c) (values 2 3 5 'x 'y)
(+ a b c))
13
If you provide fewer values than symbols, the excess symbols are bound to NIL:
(multiple-value-bind (w x y z) (values :left :right)
(list w x y z))
(:LEFT :RIGHT NIL NIL)
Most forms pass along multiple values
NOTE: MOST IS TOO STRONG -- CHANGE TO SOME HERE AND IN THE CONTENTS.
Many forms pass along the last value in their body, rather than creating a new value. Examples include the bodies of LET, COND, DEFUN, and LAMBDA.
(let ((a 1)
(b 2))
(values a b))
1
2
(cond (nil 97)
(t (values 3 4)))
3
4
(defun foo (p q)
(values (list :p p) (list :q q)))
FOO
(foo 5 6)
(:P 5)
(:Q 6)
((lambda (r s)
(values r s))
7 8)
7
8
In the case of the function and lambda bodies, the multiple values are actually returned by something called an "implicit PROGN." This is a fancy way of saying that the bodies can contain multiple forms, and only the value of the last form is returned.
You can use the PROGN special form when you want this behavior. (PROGN form1 form2 ... formN) evaluates form1 through formN in order, and returns the value of formN.
================================================================
Chapter 3 - Essential Lisp in Twelve Lessons
Lesson 10 - A Preview of Other Data Types
Lisp almost always does the right thing with numbers
This sounds like a strange thing to say. Don't computers always do the right thing with numbers? Well, no... Not usually.
Numeric calculations can break in lots of different ways. One of the biggest trouble spots is in calculations with floating point numbers (your language may call them real numbers, but that's a lie). There are probably half as many books written on proper use of floating point calculations as there are on visual- or object-oriented-anything -- and that's a lot.
The problem with floating point numbers is that they're not mathematically accurate real numbers, but are often (mis)used as if they are. The main problem is that floating point numbers have a limited accuracy -- only so many digits to the right of the decimal point. Now, if all of the numbers in a calculation are of approximately the same magnitude, then the calculation won't lose accuracy. But if the numbers are of very different magnitude, then a floating point calculation sacrifices accuracy.
Suppose that a floating point number on your computer can accurately represent 7 decimal digits. Then you can add 1897482.0 to 2973225.0 and get a completely accurate answer. But if you try to add 1897482.0 to 0.2973225, the accurate answer has fourteen digits, while your computer will answer with 1897482.0.
The other problem with floating point numbers is more subtle. When you write a program, you write numbers in base 10. But the computer does all arithmetic in base 2. The conversion from base 10 to base 2 does funny things to certain "obviously exact" numbers. For example, the decimal number 0.1 is a repeating fraction when translated into binary. Because the computer can't store the infinite number of digits required by a repeating fraction, it can't store the number 0.1 accurately.
Integer (whole number) arithmetic poses another problem in most computer languages -- they tend to impose a limit on the maximum positive or negative value that an integer can hold. So, if you try to add the number one to the largest integer your language lets the computer handle, one of two things will happen:
your program will terminate with an error, or
you'll get a wildly incorrect answer (the largest positive number plus one yields the largest negative integer in at least one computer language).
So how does Lisp manage to do the right thing with numbers? After all, it seems like these problems are inherent in computer arithmetic. The answer is that Lisp doesn't do use just the built-in computer arithmetic operations -- it adds certain mathematically accurate numeric data types:
bignums are integers with an unlimited number of digits (subject only to limitations of computer memory)
rational numbers are the exact quotient of two integers, not a floating point number resulting from an approximate machine division algorithm
Of course, Lisp also has machine-based integers and floating point numbers. Machine integers are called fixnums in Lisp. So long as a whole number falls within the numeric range of a fixnum, Lisp will store it as a machine integer. But if it gets too big, Lisp automatically promotes it to a bignum.
When I said that Lisp almost always does the right thing with numbers, I meant that it almost always chooses the numeric representation that is mathematically correct:
(/ 1 3)
1/3
(+ (/ 7 11) (/ 13 31))
360/341
(defun factorial (n)
(cond ((= n 0) 1)
(t (* n (factorial (- n 1))))))
FACTORIAL
(factorial 100)
933262154439441526816992388562667004907159682643816214685
929638952175999932299156089414639761565182862536979208272
23758251185210916864000000000000000000000000
You can write calculations to use floating point numbers, but Lisp won't automatically turn an exact numeric result into an inexact floating point number -- you have to ask for it. Floating point numbers are contagious -- once you introduce one into a calculation, the result of the entire calculation stays a floating point number:
(float (/ 1 3))
0.3333333333333333
(* (float (/ 1 10)) (float (/ 1 10)))
0.010000000000000002
(+ 1/100 (* (float (/ 1 10)) (float (/ 1 10))))
0.020000000000000004
(+ 1/100 1/100) ; compare to previous calculation
1/50
(* 3 7 10.0)
210.0
(- 1.0 1)
0.0
(+ 1/3 2/3 0.0)
1.0
(+ 1/3 2/3)
1 ; compare to previous calculation
Lisp prints floating point numbers with a decimal point, and integers without.
Characters give Lisp something to read and write
Basic Lisp I/O uses characters. The READ and WRITE functions turn characters into Lisp objects and vice versa. READ-CHAR and WRITE-CHAR read and write single characters.
(read)
a
A
(read)
#\a
a
(read-char)
a
#\a
(write 'a)
A
A
(write #\a)
#\a
#\a
(write-char #\a)
a
#\a
(write-char 'a)
Error: Not a character
We've introduced some new notation in the above examples. The symbol means that Lisp expects input in response to an input function such as READ. This is different from , which accepts input to be evaluated and printed. The symbol indicates a newline character, generated by the return or enter key.
The indicates output that is printed rather than returned as a value.
You should notice that newline terminates READ input. This is because READ collects characters trying to form a complete Lisp expression. We'll see more of this in Lesson 11. In the example, READ collects a symbol, which is terminated by the newline. The symbol could also have been terminated by a space, a parenthesis, or any other character that can't be part of a symbol.
In contrast, READ-CHAR reads exactly one character from the input. As soon as that character is consumed, READ-CHAR completes executing and returns the character.
Some Lisp systems systems may require you to press the return key before any input is recognized. This is unusual, and can often be fixed by a configuration parameter -- consult your Lisp vendor.
WRITE and WRITE-CHAR both return the value they're given. The way in which they print the value is different. WRITE prints the value so that it could be presented to READ to create the same value. WRITE-CHAR prints just the readable character, without the extra Lisp syntax (the #\) that would identify it to READ as a character.
Lisp represents a single character using the notation #\char, where char is a literal character or the name of a character that does not have a printable glyph.
Character Hex Value Lisp Standard?
--------------------------------------------------------
space 20 #\Space yes
newline -- #\Newline yes
backspace 08 #\Backspace semi
tab 09 #\Tab semi
linefeed 0A #\Linefeed semi
formfeed 0C #\Page semi
carriage return 0D #\Return semi
rubout or DEL 7F #\Rubout semi
Only #\Space and #\Newline are required on all Lisp systems. Systems that use the ASCII character set will probably implement the rest of the character codes shown above.
The #\Newline character stands for whatever convention represents the end of a printed line on the host system, e.g.:
System Newline Hex Value
-----------------------------------
Macintosh CR 0D
MS-DOS CR LF 0D 0A
Unix LF 0A
The 94 printable standard characters are represented by #\char:
! " # $ % & ' ( ) * + , - . /
0 1 2 3 4 5 6 7 8 9 : ; < = > ?
@ A B C D E F G H I J K L M N O
P Q R S T U V W X Y Z [ \ ] ^ _
` a b c d e f g h i j k l m n o
p q r s t u v w x y z { | } ~
Arrays organize data into tables
If you need to organize data in tables of two, three, or more dimensions, you can create an array:
(setq a1 (make-array '(3 4)))
#2A((NIL NIL NIL NIL)
(NIL NIL NIL NIL)
(NIL NIL NIL NIL))
(setf (aref a1 0 0) (list 'element 0 0))
(ELEMENT 0 0)
(setf (aref a1 1 0) (list 'element 1 0))
(ELEMENT 1 0)
(setf (aref a1 2 0) (list 'element 2 0))
(ELEMENT 2 0)
a1
#2A(((ELEMENT 0 0) NIL NIL NIL)
((ELEMENT 1 0) NIL NIL NIL)
((ELEMENT 2 0) NIL NIL NIL))
(aref a1 0 0)
(ELEMENT 0 0)
(setf (aref a1 0 1) pi)
3.141592653589793
(setf (aref a1 0 2) "hello")
"hello"
(aref a1 0 2)
"hello"
You create an array using MAKE-ARRAY, which takes a list of dimensions and returns an array. By default, an array can contain any kind of data; optional arguments let you restrict the element data types for the sake of efficiency.
An array's rank is the same as its number of dimensions. We created a rank-2 array in the above example. Lisp prints an array using the notation #rankA(...). The contents of the array appear as nested lists, with the first dimension appearing as the outermost grouping, and the last dimension appearing as the elements of the innermost grouping.
Your Lisp system will probably not print an array with line breaks as I've shown here. I added these breaks to emphasize the structure of the array.
To retrieve an element of an array, use AREF. AREF's first argument is the array; the remaining arguments specify the index along each dimension. The number of indices must match the rank of the array.
To set an element of an array, use AREF inside a SETF form as shown in the example. SETF is similar to SETQ, except where SETQ assigns a value to a symbol, SETF assigns a value to a place. In the examples, the AREF form specifies the place as an element in the array.
Vectors are one-dimensional arrays
Vectors are one-dimensional arrays. You can create a vector using MAKE-ARRAY, and access its elements using AREF.
(setq v1 (make-array '(3)))
#(NIL NIL NIL)
(make-array 3)
#(NIL NIL NIL)
(setf (aref v1 0) :zero)
:ZERO
(setf (aref v1 1) :one)
:ONE
(aref v1 0)
:ZERO
v1
#(:ZERO :ONE NIL)
Lisp prints vectors using the slightly abbreviated form #(...), rather than #1A(...).
You can use either a single-element list or a number to specify the vector dimensions to MAKE-ARRAY -- the effect is the same.
You can create a vector from a list of values, using the VECTOR form:
(vector 34 22 30)
#(34 22 30)
This is similar to the LIST form, except that the result is a vector instead of a list. There are other similarities between lists and vectors: both are sequences. Sequences are manipulated by the functions we'll see in Chapter 13.
You can use AREF to access the elements of a vector, or you can use the sequence-specific function, ELT:
(setf v2 (vector 34 22 30 99 66 77))
#(34 22 30 99 66 77)
(setf (elt v2 3) :radio)
:RADIO
v2
#(34 22 30 :RADIO 66 77)
Strings are vectors that contain only characters
You already know how to write a string using the "..." syntax. Since a string is a vector, you can apply the array and vector functions to access elements of a string. You can also create strings using the MAKE-STRING function or change characters or symbols to strings using the STRING function.
(setq s1 "hello, there.")
"hello, there."
(setf (elt s1 0) #\H))
#\H
(setf (elt s1 12) #\!)
#\!
s1
"Hello, there!"
(string 'a-symbol)
"A-SYMBOL"
(string #\G)
"G"
Symbols are unique, but they have many values
We saw in Lesson 5 that a symbol has a unique identity, but this bears repeating: A symbol is identical to any other symbol spelled the same way (including its package designation, which we'll learn more about at the end of this lesson). This means that you can have Lisp read a program or data, and every occurrence of a symbol with the same spelling is the same symbol. Since Lisp supplies the mechanism to do this, it's one less thing you have to worry about when you write a program that manipulates symbolic information.
We also learned in Lesson 5 that a symbol can have values as a variable and a function, and for documentation, print name, and properties. A symbol's property list is like a miniature database which associates a number of key/value pairs with the symbol. For example, if your program represented and manipulated objects, you could store information about an object on its property list:
(setf (get 'object-1 'color) 'red)
RED
(setf (get 'object-1 'size) 'large)
LARGE
(setf (get 'object-1 'shape) 'round)
ROUND
(setf (get 'object-1 'position) '(on table))
(ON TABLE)
(setf (get 'object-1 'weight) 15)
15
(symbol-plist 'object-1)
(WEIGHT 15 POSITION (ON TABLE) SHAPE ROUND SIZE LARGE
COLOR RED)
(get 'object-1 'color)
RED
object-1
Error: no value
Note that OBJECT-1 doesn't have a value -- all of the useful information is in two places: the identity of the symbol, and the symbol's properties.
This use of properties predates modern object programming by a few decades. It provides two of the three essential mechanisms of an object: identity and encapsulation (remember that property values could just as well be a function). The third mechanism, inheritance, was sometimes simulated by links to other "objects."
Properties are less often used in modern Lisp programs. Hash tables (see below), structures (described in the next section), and CLOS objects (see Chapter 7 and Chapter 14) provide all of the capabilities of property lists in ways that are easier to use and more efficient. Modern Lisp development systems often use properties to annotate a program by keeping track of certain information such as the file and file position of the defining form for a symbol, and the definition of a function's argument list (for use by informational tools in the programming environment).
Structures let you store related data
A Lisp structure gives you a way to create an object which stores related data in named slots.
(defstruct struct-1 color size shape position weight)
STRUCT-1
(setq object-2 (make-struct-1
:size 'small
:color 'green
:weight 10
:shape 'square))
#S(STRUCT-1 :COLOR GREEN :SIZE SMALL :SHAPE SQUARE
:POSITION NIL :WEIGHT 10)
(struct-1-shape object-2)
SQUARE
(struct-1-position object-2)
NIL
(setf (struct-1-position object-2) '(under table))
(UNDER TABLE)
(struct-1-position object-2)
(UNDER-TABLE)
In the example, we defined a structure type named STRUCT-1 with slots named COLOR, SHAPE, SIZE, POSITION, and WEIGHT. Then we created an instance of a STRUCT-1 type, and assigned the instance to the variable OBJECT-2. The rest of the example shows how to access slots of a struct instance using accessor functions named for the structure type and the slot name. Lisp generates the make-structname and structname-slotname functions when you define a structure using DEFSTRUCT.
We'll look at DEFSTRUCT's optional features in Chapter 6.
Type information is apparent at runtime
A symbol can be associated with any type of value at runtime. For cases where it matters, Lisp lets you query the type of a value.
(type-of 123)
FIXNUM
(type-of 123456789000)
BIGNUM
(type-of "hello, world")
(SIMPLE-BASE-STRING 12)
(type-of 'fubar)
SYMBOL
(type-of '(a b c))
CONS
TYPE-OF returns a symbol or a list indicating the type of its argument. This information can then be used to guide a program's behavior based upon the type of its arguments. The TYPECASE function combines the type inquiry with a COND-like dispatch.
With the introduction of generic functions in CLOS (see Chapter 14), TYPE-OF is not as important as it once was.
Hash Tables provide quick data access from a lookup key
A hash table associates a value with a unique key. Unlike a property list, a hash table is well suited to a large number of key/value pairs, but suffers from excessive overhead for smaller sets of associations.
(setq ht1 (make-hash-table))
#
(gethash 'quux ht1)
NIL
NIL
(setf (gethash 'baz ht1) 'baz-value)
BAZ-VALUE
(gethash 'baz ht1)
BAZ-VALUE
T
(setf (gethash 'gronk ht1) nil)
NIL
(gethash 'gronk ht1)
NIL
T
You create a hash table using MAKE-HASH-TABLE, and access values using GETHASH. GETHASH returns two values. The first is the value associated with the key. The second is T if the key was found, and NIL otherwise. Notice the difference between the first and last GETHASH form in the examples above.
By default, a hash table is created so that its keys are compared using EQ -- this works for symbols, but not numbers or lists. We'll learn more about equality predicates in Chapter 17. For now, just remember that if you want to use numbers for keys, you must create a hash table using the form:
(make-hash-table :test #'eql)
If you want to use lists for keys, create your hash table with:
(make-hash-table :test #'equal)
If you want to remove a key, use the form (REMHASH key hash-table). And if you want to change the value for a key, use GETHASH with SETF, just as if you were adding a new key/value pair.
Packages keep names from colliding
One of the things that's hard about writing programs is naming parts of your program. On one hand, you want to use names that are easy to remember and evocative of the role or purpose of the named object. On the other hand, you don't want to use a name that someone else has already used (or is likely to use) in a different program that you may someday have to make work with your program.
One way to avoid naming conflicts is to give every name in your program a unique prefix that no one else is likely to use. You see this done all the time with libraries -- the prefix is typically one to three characters. Unfortunately, this still leaves a lot of room for two software developers to choose the same prefix; especially since some prefixes are more evocative than others. If you have control over all the software that will be developed for your product, you can choose all of the prefixes and avoid problems. If you're going to buy third-party software that uses a prefix naming scheme, you'll have to work around the names chosen by your vendors and hope that two different vendors don't stumble upon the same prefix.
Another way to avoid naming conflicts is to use qualified names. To do this, the language must provide support for separate namespaces defined and controlled by the programmer. To understand how this works, imagine that all the names you create for your program get written on a sheet of paper with your name written at the top as a title -- this is the qualifier for all of your names. To see whether a name is safe to use, you only have to check the list of names you've written on this page. When someone else's software needs the services of your program, they refer to your names by using both your qualifier and name. Because the other person's software has a different qualifier, and their qualifier is implicit (that is, it doesn't need to be written) for their own names, there's no chance of a name conflict.
You might think that a qualifier is no more than a complicated way to add a prefix to a name. However, there's a subtle but important difference. A prefix is part of the name; it cannot be changed once written. A qualifier is separate from the names it qualifies, and is "written down" in exactly one place. Furthermore, you can point to the "sheet of paper" upon which names are written and refer to it as "those names." If you happen to choose the same qualifier as another programmer, you can still refer to "those names" by a qualifier of your own choosing -- In other words, you can change the qualifier after the software has been delivered for your use.
In the above example, two libraries are delivered in files LIB1 and LIB2. Both library designers used the name UTIL for the name of their namespace, known in Lisp as a package name. Each library lists the names exposed to a client. The programmer who uses the two libraries writes code in the package name MY-PACKAGE. After loading each library, the programmer renames its package so the names are distinct. Then, names in the library are referenced using their renamed qualifiers, as we see in the calls to UTIL-1:INITIALIZE and UTIL-2:INITIALIZE. Notice how the INITIALIZE name is still available to the programmer in its unqualified form -- this is equivalent to MY-PACKAGE:INITIALIZE.
Lisp provides this functionality through a set of functions and macros collective known as the package facility. The DEFPACKAGE macro conveniently provides most package operations, while the IN-PACKAGE macro sets the current package:
;;;; ---- File 1 ----
(defpackage util1
(:export init func1 func2)
(:use common-lisp))
(in-package util1)
(defun init () 'util1-init)
(defun func1 () 'util1-func1)
(defun func2 () 'util1-func2)
;;;; ---- File 2 ----
(defpackage util2
(:export init func1 func2)
(:use common-lisp))
(in-package util2)
(defun init () 'util2-init)
(defun func1 () 'util2-func1)
(defun func2 () 'util2-func2)
;;;; ---- File 3 ----
(defpackage client
(:use common-lisp)
(:import-from util1 func1)
(:import-from util2 func2))
(in-package client)
(defun init () 'client-init)
(util1:init)
(util2:init)
(init)
(func1)
(func2)
The example lists the contents of three files. File 1 and File 2 both define three functions using identical names. File 1 puts names in the UTIL1 package, while File 2 uses the UTIL2 package. The DEFPACKAGE form names the package. The :USE option specifies that names from another package may be used without qualification, while the :EXPORT option specifies the names that are exposed to clients of the package.
The DEFPACKAGE form only creates a package. The USE-PACKAGE form makes a package current -- all unqualified names are in whatever package is current. The COMMON-LISP:*PACKAGE* variable always contains the current package.
File 3 creates the CLIENT package. The :IMPORT-FROM options bring in specific names from the UTIL1 and UTIL2 packages -- these names may be used without qualification in the CLIENT package. Names that are exported from UTIL1 or UTIL2 but not imported by CLIENT may still be referenced within CLIENT by using an explicit qualifier of the form package:name.
This section covered only very basic package operations. We'll cover additional details in Chapter 31, when we look again at packages within the context of constructing large software systems.
================================================================
Chapter 3 - Essential Lisp in Twelve Lessons
Lesson 11 - Essential Input and Output
READ accepts Lisp data
As we saw in Lesson 10, READ turns characters into Lisp data. So far, you've seen a printed representation of several kinds of Lisp data:
symbols and numbers,
strings, characters, lists, arrays, vectors, and structures,
and hash tables.
The Lisp reader does its job according to a classification of characters. The standard classifications are shown below. As we'll see in Lesson 12, you can alter these classifications for your own needs.
Standard Constituent Characters
-------------------------------
a b c d e f g h i j k l m n o p q r s t u v w x y z
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9
! $ % & * + - . / : < = > ? @ [ ] ^ _ { } ~
Standard Terminating Macro Characters
-------------------------------------
" ' ( ) , ; `
Standard Non-Terminating Macro Characters
-----------------------------------------
#
Standard Single Escape Characters
---------------------------------
\
Standard Multiple Escape Characters
-----------------------------------
|
Standard Whitespace Characters
------------------------------
If READ starts with a constituent character, it begins accumulating a symbol or number. When READ encounters a terminating macro character or a whitespace character, it tries to interpret the collected constituent characters first as a number, then as a symbol. If a numeric interpretation is possible, READ returns the number. Otherwise, READ changes the alphabetical characters to a standard case (normally upper case), interns the name as a symbol, and returns the symbol.
Escape characters play a special role. A single escape character forces the following character to be treated exactly as a constituent character. In this way characters that are normally treated as whitespace or terminating macro characters can be part of a symbol. If READ encounters an escape character, it never attempts to interpret the resulting constituents as a number, even if only digits were escaped.
If READ starts with a macro character, the character determines the next step:
"
Read a string.
'
Read a form.
(
Read a list.
;
Ignore everything up to newline.
#
Decide what to do based on the next character.
Finally, some Lisp data is not meant to be read. For example, the printed representation of a hash table looks something like #. It is an error for READ to attempt to read anything beginning with the characters #<.
PRINT writes Lisp data for you and for READ
The PRINT function changes a Lisp object into the sequence of characters that READ would need to reconstruct it:
(print 'abc)
ABC
ABC
(print (list 1 2 3))
(1 2 3)
(1 2 3)
(print "A String")
"A string"
"A string"
(print 387.9532)
387.9532
387.9532
(print (make-hash-table))
#
#
PRINT always begins its output with a newline character (), and follows its output with a space (). This ensures that the PRINT output stands apart from any surrounding output, since newline and space are both treated as whitespace, and cannot be part of the printed representation of a Lisp object (unless escaped).
Other variations of PRINT have different uses. PRIN1 behaves as PRINT, but does not surround its output with whitespace. This might be useful if you are building up a name from successive pieces, for example. PRINC behaves as PRIN1, but generates output intended for display, rather than READ; for example, PRINC omits the quotes around a string, and does not print escape characters.
(print 'a\ bc)
|A BC|
|A BC|
(prin1 'a\ bc)
|A BC|
|A BC|
(princ '|A BC|)
A BC
|A BC|
OPEN and CLOSE let you work with files
Normally, READ reads from the keyboard and PRINT prints to the screen. Both of these functions take an optional argument; the argument specifies an input stream for READ, and an output stream for PRINT. What's a stream? A stream is a source or sink of data, typically -- but not necessarily -- characters. For now, we'll look at how text files can be the source or sink of a character stream. In Chapter 19 we'll look at some of the other possibilities.
You can attach a stream to a file using the OPEN function, which takes as parameters a file name and a keyword argument to specify the direction (input or output) of the stream. To finish operations on the stream and close the associated file, use the CLOSE function.
(setq out-stream (open "my-temp-file" :direction :output))
#
(print 'abc out-stream)
ABC
(close out-stream)
T
(setq in-stream (open "my-temp-file" :direction :input))
#
(read in-stream)
ABC
(close in-stream)
T
In the example, we create an output stream to the file named my-temp-file, and print the symbol ABC to that stream. Notice how PRINT returns its argument as usual, but doesn't print it -- the printed result has gone to the file, instead.
Next, we close the output stream and open an input stream on the same file. We then read the symbol that we printed to the file, and finish by closing the input stream.
Variations on a PRINT theme
Lisp also provides a WRITE function to give you control over more details of printing, using keyword arguments to control these options:
Keyword Argument Default Value Action
---------------- ------------- ------
:stream t set output stream
:escape *print-escape* include escape characters
:radix *print-radix* include radix (base) prefix
:base *print-base* set number base (rationals)
:circle *print-circle* print circular structures
:pretty *print-pretty* add whitespace for readability
:level *print-level* limit nesting depth
:length *print-length* limit items per nesting level
:case *print-case* :upper, :lower, or :mixed
:gensym *print-gensym* prefix uninterned symbols
:array *print-array* print arrays readably
:readably *print-readably* force printing to be readable
:right-margin *print-right-margin* controls pretty-printing
:miser-width *print-miser-width* "
:lines *print-lines* "
:pprint-dispatch *print-pprint-dispatch* "
Coincidentally, the variables named above as the default values of the keyword arguments also control the operation of PRINT. You can get the effect of WRITE with non-default keyword arguments by binding these variables in a LET form around a PRIN1:
(write foo (let ((*print-pretty* t)
:pretty t (*print-right-margin* 60)
:right-margin 60 (*print-case* :downcase))
:case :downcase) (prin1 foo))
We used PRIN1 rather than PRINT because we don't want the preceding newline and following blank that PRINT adds.
If your program changes the *PRINT-...* variables, but you need to ensure the default values at some point in your program, you can wrap that part of the program inside a WITH-STANDARD-IO-SYNTAX form: