Archive-name: lisp-faq/part1
Last-Modified: Fri May 27 14:33:54 1994 by Mark Kantrowitz
Version: 1.46
;;; ****************************************************************
;;; Answers to Frequently Asked Questions about Lisp ***************
;;; ****************************************************************
;;; Written by Mark Kantrowitz and Barry Margolin
;;; lisp_1.faq -- 72089 bytes
This post contains Part 1 of the Lisp FAQ.
If you think of questions that are appropriate for this FAQ, or would
like to improve an answer, please send email to us at ········@think.com.
Note that the lisp-faq mailing list is for discussion of the content
of the FAQ posting only. It is not the place to ask questions about Lisp;
use either the ···········@ai.sri.com mailing list or the
comp.lang.lisp newsgroup for that. If a question appears frequently
in one of those forums, it will get added to the FAQ list.
*** Copyright:
Copyright (c) 1992-94 by Mark Kantrowitz and Barry Margolin.
All rights reserved.
This FAQ may be freely redistributed in its entirety without
modification provided that this copyright notice is not removed. It
may not be sold for profit or incorporated in commercial documents
(e.g., published for sale on CD-ROM, floppy disks, books, magazines,
or other print form) without the prior written permission of the
copyright holder. Permission is expressly granted for this document
to be made available for file transfer from installations offering
unrestricted anonymous file transfer on the Internet.
This article is provided AS IS without any express or implied warranty.
*** Topics Covered:
There are currently seven parts to the Lisp FAQ:
1. Introductory Matter and Bibliography of Introductions and References
2. General Questions
3. Common Programming Pitfalls
4. Lisp Implementations and Mailing Lists
5. Object-oriented Programming in Lisp
6. FTP Archives and Resources
7. Lisp Window Systems and GUIs
All parts are posted to comp.lang.lisp. Part 5 is cross-posted to the
comp.lang.clos newsgroup.
Topics Covered (Part 1):
[1-0] What is the purpose of this newsgroup?
[1-1] What is the difference between Scheme and Common Lisp?
[1-2] Lisp books, introductions, documentation, periodicals,
journals, and conference proceedings.
[1-3] How can I improve my Lisp programming style and coding efficiency?
[1-4] Where can I learn about implementing Lisp interpreters and compilers?
[1-5] What is the "minimal" set of primitives needed for a Lisp
interpreter?
[1-6] What does CLOS, PCL, X3J13, CAR, CDR, ... mean?
[1-7] Lisp Job Postings
Topics Covered (Part 2):
[2-1] Is there a GNU-Emacs interface to Lisp?
[2-2] When should I use a hash table instead of an association list?
[2-3] What is the equivalent of EXPLODE and IMPLODE in Common Lisp?
[2-4] Is Lisp inherently slower than more conventional languages such as C?
[2-5] Why does Common Lisp have "#'"?
[2-6] How do I call non-Lisp functions from Lisp?
[2-7] Can I call Lisp functions from other languages?
[2-8] I want to call a function in a package that might not exist at
compile time. How do I do this?
[2-9] What is CDR-coding?
[2-10] What is garbage collection?
[2-11] How do I save an executable image of my loaded Lisp system?
How do I run a Unix command in my Lisp?
[2-12] I'm porting some code from a Symbolics Lisp machine to some
other platform, and there are strange characters in the code.
What do they mean?
[2-13] History: Where did Lisp come from?
[2-14] How do I find the argument list of a function?
How do I get the function name from a function object?
[2-15] How can I have two Lisp processes communicate via unix sockets?
[2-16] How can I create a stream that acts like UNIX's /dev/null
(i.e., gobbles any output and immediately signals EOF on
input operations)?
[2-17] Read-time conditionalization of code (#+ #- and *features*)
[2-18] What reader macro characters are used in major Lisp systems?
[2-19] How do I determine if a file is a directory or not?
How do I get the current directory name from within a Lisp
program? Is there any way to create a directory?
[2-20] What is a "Lisp Machine" (LISPM)?
Common Pitfalls (Part 3):
[3-0] Why does (READ-FROM-STRING "foobar" :START 3) return FOOBAR
instead of BAR?
[3-1] Why can't it deduce from (READ-FROM-STRING "foobar" :START 3)
that the intent is to specify the START keyword parameter
rather than the EOF-ERROR-P and EOF-VALUE optional parameters?
[3-2] Why can't I apply #'AND and #'OR?
[3-3] I used a destructive function (e.g. DELETE, SORT), but it
didn't seem to work. Why?
[3-4] After I NREVERSE a list, it's only one element long. After I
SORT a list, it's missing things. What happened?
[3-5] Why does (READ-LINE) return "" immediately instead of waiting
for me to type a line?
[3-6] I typed a form to the read-eval-print loop, but nothing happened. Why?
[3-7] DEFMACRO doesn't seem to work.
When I compile my file, LISP warns me that my macros are undefined
functions, or complains "Attempt to call <function> which is
defined as a macro.
[3-8] Name conflict errors are driving me crazy! (EXPORT, packages)
[3-9] Closures don't seem to work properly when referring to the
iteration variable in DOLIST, DOTIMES, DO and LOOP.
[3-10] What is the difference between FUNCALL and APPLY?
[3-11] Miscellaneous things to consider when debugging code.
[3-12] When is it right to use EVAL?
[3-13] Why does my program's behavior change each time I use it?
[3-14] When producing formatted output in Lisp, where should you put the
newlines (e.g., before or after the line, FRESH-LINE vs TERPRI,
~& vs ~% in FORMAT)?
[3-15] I'm using DO to do some iteration, but it doesn't terminate.
[3-16] My program works when interpreted but not when compiled!
Lisp Implementations and Mailing Lists (Part 4):
[4-0] Free Common Lisp implementations.
[4-1] Commercial Common Lisp implementations.
[4-1a] Lisp-to-C translators
[4-2] Scheme Implementations
[4-4] Free Implementations of Other Lisp Dialects
[4-5] Commercial Implementations of Other Lisp Dialects
[4-6] What is Dylan?
[4-7] What is Pearl Common Lisp?
[4-9] What Lisp-related discussion groups and mailing lists exist?
[4-10] ANSI Common Lisp -- Where can I get a copy of the draft standard?
Object-oriented Programming in Lisp (Part 5):
[5-0] What is CLOS (PCL) and where can I get it?
How do you pronounce CLOS? What is the Meta-Object Protocol (MOP)?
[5-1] What documentation is available about object-oriented
programming in Lisp?
[5-2] How do I write a function that can access defstruct slots by
name? I would like to write something like
(STRUCTURE-SLOT <object> '<slot-name>).
[5-3] How can I list all the CLOS instances in a class?
[5-4] How can I store data and CLOS instances (with possibly circular
references) on disk so that they may be retrieved at some later
time? (Persistent Object Storage)
[5-5] Given the name of a class, how can I get the names of its slots?
[5-6] Free CLOS software.
FTP Resources (Part 6):
[6-0] General information about FTP Resources for Lisp
[6-1] Repositories of Lisp Software
[6-3] Publicly Redistributable Lisp Software
[6-6] Formatting code in LaTeX (WEB and other literate programming tools)
[6-7] Where can I get an implementation of Prolog in Lisp?
[6-8] World-Wide Web (WWW) Resources
Lisp Window Systems and GUIs (Part 7):
[7-1] How can I use the X Window System or other GUIs from Lisp?
[7-2] What Graphers/Browsers are available?
Search for \[#\] to get to question number # quickly.
*** Recent Changes:
;;; 1.44:
;;; 14-MAR-94 mk CMU CL version 17e released.
;;; 23-MAR-94 mk Updated SchemeWeb entry.
;;; 12-APR-94 mk This FAQ is now available by WWW. See below for details.
;;; 12-APR-94 mk Changed/updated many ftp references to enable them to
;;; appear as links in the WWW version of the FAQ. E-mail
;;; about references that weren't converted and/or other WWW
;;; resources is welcome.
;;;
;;; 1.45:
;;; 14-APR-94 mk Deleted duplicate Graham/Grahm entry in [1-2].
;;; 22-APR-94 mk Updated ftp information for ftp.gmd.de.
;;; 29-APR-94 mk ························@ucbarpa.berkeley.edu now defunct.
;;; 5-MAY-94 mk Added ALU home page to [6-4].
;;; 5-MAY-94 mk Added entry on the Pratt/Doerpmund implementation of the
;;; Paris/Vencovska model of belief (defeasible reasoning) to
;;; the list of ftpable systems.
;;; 12-MAY-94 mk Added info on Edebug to [2-1].
;;; 12-MAY-94 mk Added entry on Jeff Dalton's port of Franz Lisp to 386/486
;;; systems running NetBSD to [4-4].
;;; 12-MAY-94 mk Added Gwydion WWW page and email address to the entry in
;;; [4-6].
;;;
;;; 1.46:
;;; 27-MAY-94 mk Because of the demise of UCBVAX, the official archive site
;;; for Franz Lisp (public domain version) is now the CMU AI
;;; Repository. Added an entry to [4-4] reflecting this.
;;; 27-MAY-94 mk AKCL 1-625 and above no longer depend on kcl.tar and is
;;; covered by the GNU GPL. Added separate entry in part 4,
;;; and changed the KCL text slightly. Now known as
;;; GNU Common Lisp (GCL).
;;; 10-JUN-94 mk Added note about the Screamer Tools Repository to [6-3].
;;; 10-JUN-94 mk Added description of AllegroStore and PCLOS to [5-4]
;;; (Persistent Object Storage Systems).
;;; 10-JUN-94 mk Allegro-CL, Franz-Friends, and Franz-Composers lists now
;;; @cs.berkeley.edu.
;;; 12-JUN-94 mk Updated WINTERP entry in [7-1]. Version 2.01 for X11r6.
*** Introduction:
Certain questions and topics come up frequently in the various network
discussion groups devoted to and related to Lisp. This file/article is
an attempt to gather these questions and their answers into a convenient
reference for Lisp programmers. It (or a reference to it) is posted
periodically. The hope is that this will cut down on the user time and
network bandwidth used to post, read and respond to the same questions
over and over, as well as providing education by answering questions
some readers may not even have thought to ask.
This is not a Lisp tutorial, nor is it an exhaustive list of all Lisp
intricacies. Lisp is a very powerful and expressive language, but with
that power comes many complexities. This list attempts to address the
ones that average Lisp programmers are likely to encounter. If you are
new to Lisp, see the answer to the question "How can I learn Lisp?".
The latest version of this FAQ is available via anonymous FTP from CMU
and Thinking Machines:
To obtain the files from CMU, connect by anonymous FTP to
ftp.cs.cmu.edu:/user/ai/pubs/faqs/lisp/ [128.2.206.173]
using username "anonymous" and password ·····@host" (substitute your
email address) or via AFS in the Andrew File System directory
/afs/cs.cmu.edu/project/ai-repository/ai/pubs/faqs/lisp/
and get the files lisp_1.faq, lisp_2.faq, lisp_3.faq, lisp_4.faq,
lisp_5.faq, lisp_6.faq and lisp_7.faq.
To obtain the files from Thinking Machines, connect by anonymous FTP to
ftp.think.com:/public/think/lisp/
The file faq.text contains all the parts of the FAQ in one file. In
addition, specific versions of the FAQ are available as faq-<version>.text.
You can also obtain a copy of the FAQ by sending a message to
········@cs.cmu.edu with
Send Lisp FAQ
in the message body.
The FAQ postings are also archived in the periodic posting archive on
rtfm.mit.edu:/pub/usenet/news.answers/lisp-faq/ [18.181.0.24]
If you do not have anonymous ftp access, you can access the archive by
mail server as well. Send an E-mail message to
···········@rtfm.mit.edu with "help" and "index" in the body on
separate lines for more information.
An automatically generated HTML version of the Lisp FAQ is accessible by
WWW as part of the AI-related FAQs Mosaic page. The URL for this
resource is
http://www.cs.cmu.edu:8001/Web/Groups/AI/html/faqs/top.html
The direct URL for the Lisp FAQ is
http://www.cs.cmu.edu:8001/Web/Groups/AI/html/faqs/lang/lisp/top.html
Unless otherwise specified, the Lisp dialect referred to is Common Lisp,
as defined by "Common Lisp: the Language" (aka "CLtL1") as well as
corrections (but not enhancements) from "Common Lisp: the Language, 2nd
Edition" (aka "CLtL2"), both by Guy L. Steele, Jr. and published by
Digital Press. Note that CLtL2 is NOT an official specification for
the language; ANSI Committee X3J13 is preparing such a specification.
See question [4-10] for information on the status of the ANSI
specification for Common Lisp. Enhancements such as CLOS, conditions,
and the LOOP macro will be referred to separately.
If you need to cite the FAQ for some reason, use the following format:
Mark Kantrowitz and Barry Margolin, "Answers to Frequently Asked
Questions about Lisp", comp.lang.lisp, <month>, <year>,
ftp.cs.cmu.edu:/user/ai/pubs/faqs/lisp/lisp_?.faq, ········@think.com.
----------------------------------------------------------------
Subject: [1-0] What is the purpose of this newsgroup?
The newsgroup comp.lang.lisp exists for general discussion of
topics related to the programming language Lisp. For example, possible
topics can include (but are not necessarily limited to):
announcements of Lisp books and products
discussion of programs and utilities written in Lisp
discussion of portability issues
questions about possible bugs in Lisp implementations
problems porting an implementation to some architecture
Postings should be of general interest to the Lisp community. See also
question [4-9]. Postings asking for solutions to homework problems are
inappropriate.
Every so often, somebody posts an inflammatory message, such as
My programming language is better than yours (Lisp vs. C/Prolog/Scheme).
Loop (or Series) should/shouldn't be part of the language.
These "religious" issues serve no real purpose other than to waste
bandwidth. If you feel the urge to respond to such a post, please do
so through a private e-mail message.
Questions about object oriented programming in Lisp should be directed
to the newsgroup comp.lang.clos. Similarly, questions about the
programming language Scheme should be directed to the newsgroup
comp.lang.scheme. Discussion of functional programming language issues
should be directed to the newsgroup comp.lang.functional. Discussion
of AI programs implemented in Lisp should sometimes be cross-posted to
the newsgroup comp.ai.
----------------------------------------------------------------
Subject: [1-1] What is the difference between Scheme and Common Lisp?
Scheme is a dialect of Lisp that stresses conceptual elegance and
simplicity. It is specified in R4RS and IEEE standard P1178. (See
the Scheme FAQ for details on standards for Scheme.) Scheme is much
smaller than Common Lisp; the specification is about 50 pages,
compared to Common Lisp's 1300 page draft standard. (See question
[4-10] for details on standards for Common Lisp.) Advocates of Scheme
often find it amusing that the Scheme standard is shorter than the
index to CLtL2.
Scheme is often used in computer science curricula and programming
language research, due to its ability to represent many programming
abstractions with its simple primitives. Common Lisp is often used for
real world programming because of its large library of utility
functions, a standard object-oriented programming facility (CLOS), and
a sophisticated condition handling system.
See the Scheme FAQ for information about object-oriented programming
in Scheme.
In Common Lisp, a simple program would look something like the
following:
(defun fact (n)
(if (< n 2)
1
(* n (fact (1- n)))))
In Scheme, the equivalent program would like like this:
(define fact
(lambda (n)
(if (< n 2)
1
(* n (fact (- n 1))))))
Experienced Lisp programmers might write this program as follows in order
to allow it to run in constant space:
(defun fact (n)
(labels ((tail-recursive-fact (counter accumulator)
(if (> counter n)
accumulator
(tail-recursive-fact (1+ counter)
(* counter accumulator)))))
(tail-recursive-fact 1 1)))
Whereas in Scheme the same computation could be written as follows:
(define fact
(lambda (n)
(letrec ((tail-recursive-fact
(lambda (counter accumulator)
(if (> counter n)
accumulator
(tail-recursive-fact (+ counter 1)
(* counter accumulator))))))
(tail-recursive-fact 1 1))))
or perhaps (using IEEE named LETs):
(define fact
(lambda (n)
(let loop ((counter n)
(accumulator 1))
(if (< counter 2)
accumulator
(loop (- counter 1)
(* accumulator counter))))))
Some Schemes allow one to use the syntax (define (fact n) ...) instead
of (define fact (lambda (n) ...)).
----------------------------------------------------------------
Subject: [1-2] Lisp books, introductions, documentation, periodicals,
journals, and conference proceedings.
There are several good Lisp introductions and tutorials:
1. David S. Touretzky
"Common Lisp: A Gentle Introduction to Symbolic Computation"
Benjamin/Cummings Publishers, Redwood City, CA, 1990. 592 pages.
ISBN 0-8053-0492-4.
Perhaps the best tutorial introduction to the language. It has
clear and correct explanations, and covers some fairly advanced
topics. The book is an updated Common Lisp version of the 1984
edition published by Harper and Row Publishers.
Three free Lisp educational tools which were used in the book --
Evaltrace, DTRACE and SDRAW -- are available by anonymous ftp from
b.gp.cs.cmu.edu:/usr/dst/public/{lisp,evaltrace}. Evaltrace is a
graphical notation for explaining how evaluation works and is
described in "Visualizing Evaluation in Applicative Languages" by
David S. Touretzky and Peter Lee, CACM 45-59, October 1992. DTRACE
is a "detailed trace" which provides more information than the
tracing tools provided with most Common Lisp implementations. SDRAW
is a read-eval-draw loop that evaluates Lisp expressions
and draws the result as a cons cell diagram (for both X11 and ascii
terminals). Also available is PPMX, a tool for pretty printing
macro expansions.
2. Robert Wilensky
"Common LISPcraft"
W. W. Norton, 1986. 500 pages. ISBN 0-393-95544-3.
3. Wade L. Hennessey
"Common Lisp"
McGraw-Hill, 1989. 395 pages.
Fairly good, but jumps back and forth from the simple to the
complex rather quickly, with no clear progression in difficulty.
4. Laurent Siklossy
"Let's Talk LISP"
Prentice-Hall, NJ, 1976. 237 pages.
Good introduction, but quite out of date.
5. Stuart C. Shapiro
"Common Lisp: An Interactive Approach"
Computer Science Press/W.H. Freeman, New York, 1992.
ISBN 0-7167-8218-9
The errata for the book may be obtained by anonymous ftp from
ftp.cs.buffalo.edu:/users/shapiro/clerrata.ps
Other introductions to Lisp include:
1. A. A. Berk.
"LISP, The Language of Artificial Intelligence"
Van Nostrand Reinhold, 1985. 160 pages.
2. Paul Y. Gloess.
"An Alfred handy guide to Understanding LISP"
Alfred Publishers (Sherman Oaks, CA), 1982. 64 pages.
3. Ward D. Maurer.
"The Programmer's Introduction to LISP"
American Elsevier, 1972. 112 pages.
4. Hank Bromley and Richard Lamson.
"LISP Lore: A Guide to Programming the LISP Machine"
Kluwer Academic (Boston), 1987. 337 pages.
5. Sharam Hekmatpour.
"Introduction to LISP and Symbol Manipulation"
Prentice Hall (New York), 1988. 303 pages.
6. Deborah G. Tatar
"A programmer's guide to Common Lisp"
Digital Press, 1987. 327 pages. ISBN 0-932376-87-8.
Good introduction on Common Lisp for programmers familiar
with other programming languages, such as FORTRAN, PASCAL, or C.
7. Timothy Koschmann
"The Common Lisp Companion"
John Wiley & Sons, 1990. ISBN 0-471-503-8-8.
Targeted for those with some programming experience who wish to
learn draft-ANSI Common Lisp, including CLOS and the CL condition
system. Examples progress incrementally from simple numerical
calculation all the way to a logic-programming extension to CL.
More advanced introductions to Lisp and its use in Artificial
Intelligence include:
1. Peter Norvig.
"Paradigms of AI Programming: Case Studies in Common Lisp"
Morgan Kaufmann, 1992. 946 pages. ISBN 1-55860-191-0. $49.95.
Provides an in-depth exposition of advanced AI programming techniques
and includes large-scale detailed examples. The book is the most
advanced AI/Common-Lisp programming text and reference currently
available, and hence is not for the complete novice. It focuses on the
programming techniques necessary for building large AI systems,
including object-oriented programming, and has a strong performance
orientation.
The text is marked by its use of "non-toy" examples to illustrate the
techniques. All of the examples are written in Common Lisp, and copies
of the source code are available by anonymous ftp from
unix.sri.com:/pub/norvig and on disk in Macintosh or DOS format from
the publisher. Some of the techniques described include rule-based
pattern matching (GPS, Eliza, a subset of Macsyma, the Emycin expert
system shell), constraint propagation and backtracking (Waltz
line-labelling), alpha-beta search (Othello), natural language
processing (top-down, bottom-up and chart parsing), logic-programming
(unification and Prolog), interpreters and compilers for Scheme, and
object-oriented programming (CLOS).
The examples are also used to illustrate good programming style and
efficiency. There is a guide to trouble-shooting and debugging Lisp
programs, a style guide, and a discussion of portability problems.
Some of the efficiency techniques described include memoization,
data indexing, compilation, delaying computation, proper use of
declarations, avoiding garbage collection, and choosing and using the
correct data structure.
The book also serves as an advanced introduction to Common Lisp, with
sections on the Loop macro, CLOS and sequences, and some coverage of
error handling, series, and the package facility.
2. Eugene Charniak, Christopher K. Riesbeck, Drew V. McDermott
and James R. Meehan.
"Artificial Intelligence Programming", 2nd edition.
Lawrence Erlbaum Associates (Hillsdale, NJ), 1987. 533 pages.
Provides many nice code fragments, all of which are written
in Common Lisp. The first half of the book covers topics
like macros, the reader, data structures, control structures,
and defstructs. The second half of the book describes
programming techniques specific to AI, such as
discrimination nets, production systems, deductive database
retrieval, logic programming, and truth maintenance.
3. Patrick H. Winston and Berthold K. P. Horn.
"LISP", 3rd edition.
Addison-Wesley (Reading, MA), 1989. 611 pages. ISBN 0-201-08319-1
Covers the basic concepts of the language, but also gives a lot
of detail about programming AI topics such as rule-based expert
systems, forward chaining, interpreting transition trees,
compiling transition trees, object oriented programming,
and finding patterns in images. Not a tutorial. Has many
good examples. Source code for the examples is available by
anonymous ftp from ftp.ai.mit.edu:/pub/lisp3/. (The code runs in
Lucid, Allegro, KCL, GCLisp, MCL, Symbolics Genera. Send mail
with subject line "help" to ···@ai.mit.edu for more information.)
4. John R. Anderson, Albert T. Corbett, and Brian J. Reiser.
"Essential LISP"
Addison-Wesley (Reading, MA), 1987. 352 pages.
Concentrates on how to use Lisp with iteration and recursion.
5. Robert D. Cameron and Anthony H. Dixon
"Symbolic Computing with Lisp"
Prentice-Hall, 1992, 326 pages. ISBN 0-13-877846-9.
The book is intended primarily as a third-year computer science
text. In terms of programming techniques, it emphasizes recursion
and induction, data abstraction, grammar-based definition of Lisp
data structures and functional programming style. It uses
two Lisp languages:
(1) a purely functional subset of Lisp called Small Lisp and
(2) Common Lisp.
An MS-DOS interpreter for Small Lisp (including source) is
provided with the book. It considers applications of Lisp
to formal symbolic data domains: algebraic expressions,
logical formulas, grammars and programming languages.
6. Hasemer and Domingue.
"Common Lisp Programming for Artificial Intelligence"
Addison-Wesley, 1989.
7. Steven Tanimoto
"The Elements of Artificial Intelligence: An Introduction Using Lisp"
Computer Science Press, Rockville, MD, 1987, 530 pages.
8. Patrick R. Harrison
"Common Lisp and Artificial Intelligence"
Prentice Hall, Englewood Clifs, NJ, 1990. 244 pages. ISBN 0-13-155243.
9. Paul Graham
"On Lisp: Advanced Techniques for Common Lisp"
Prentice Hall, Englewood Clifs, NJ, 1994. 400 pages, ISBN 0-13-030552-9.
Emphasizes a bottom-up style of writing programs, which he
claims is natural in Lisp and has advantages over the
traditional way of writing programs in C and Pascal.
Also has in-depth sections on writing macros.
General Lisp reference books include:
1. Guy L. Steele
"Common Lisp: The Language" [CLtL1]
Digital Press, 1984. 465 pages. ISBN 0-932376-41-X.
2. Guy L. Steele
"Common Lisp: The Language, 2nd Edition" [CLtL2]
Digital Press, 1990. 1029 pages. ISBN 1-55558-041-6.
3. Franz Inc.
"Common Lisp: The Reference"
Addison-Wesley, Reading, MA 1988. ISBN 0-201-11458-5
Entries on Lisp (CLtL1) functions in alphabetical order.
Lisp periodicals include:
1. LISP Pointers.
Published by ACM SIGPLAN six times a year. Volume 1, Number 1
was April-May 1987.
Subscriptions: ACM Members $12; ACM Student Members $7; Non-ACM
members $25. Mail checks payable to the ACM to ACM Inc., PO Box
12115, Church Street Station, New York, NY 10249.
2. LISP and Symbolic Computation, Kluwer Academic Press. Volume 1
was published in 1989. (···@lucid.com is the editor). ISSN 0892-4635.
Subscriptions: Institutions $169; Individuals $80. Add $8 for
air mail. Kluwer Academic Publishers, PO Box 322, 3300 AH Dordrecht,
The Netherlands, or Kluwer Academic Publishers, PO Box 358, Accord
Station, Hingham, MA 02018-0358.
A full table of contents of all published issues, aims and scope, and
instructions for authors are available by anonymous ftp from
ftp.std.com:/Kluwer/journals/
as the files lisp.toc and lisp.inf.
3. Proceedings of the biannual ACM Lisp and Functional Programming
Conference. (First one was in 1980.)
4. Proceedings of the annual Lisp Users and Vendors Conference.
Implementation-specific questions:
1. Lucid. See the wizards.doc file that comes with the Lucid
release. It describes functions, macros, variables and constants that
are not official parts of the product and are not supported.
Constructs described in this file include: the interrupt facility, the
source file recording facility, the resource facility, multitasking,
writing your own streams, lisp pipes, i/o buffers, the compiler,
floating-point functions, memory management, debugger information, the
window tool kit, extensions to the editor, the foreign function
interface, clos information, delivery toolkit information, and Lucid
lisp training classes. The wizards.doc file also covers i/o
constructs, functions for dealing with DEFSTRUCT, functions and
constants for dealing with procedure objects, functions and constants
for dealing with code objects, function for mapping objects,
additional keyword argument to DISKSAVE, function used in the
implementation of arrays, function for monitor-specific behavior for a
process, additional keyword argument to RUN-PROGRAM, and load-time
evaluation.
Many books on Scheme are worth reading even if you use Common Lisp,
because many of the issues are similar. Scheme is a simpler language
to learn, so it is often used in introductory computer science
classes. See the Scheme FAQ for a list of introductions and
references for Scheme. The two key introductions are Abelson and
Sussman's "Structure and Interpretation of Computer Programs" and
Friedman and Felleisen's "The Little LISPer".
Special Topics:
Garbage Collection:
Wilson, Paul R., "Uniprocessor Garbage Collection Techniques"
Proceedings of the 1992 International Workshop on Memory Management.
Springer Lecture Notes #637. Surveys garbage collection techniques.
Includes an excellent bibliography. Available by anonymous ftp from
cs.utexas.edu:/pub/garbage/gcsurvey.ps.
The BibTeX format of the bibliography is also available in this
directory, along with several other papers. Contact ······@cs.utexas.edu
for more info.
----------------------------------------------------------------
Subject: [1-3] How can I improve my Lisp programming style and
coding efficiency?
There are several books about Lisp programming style, including:
1. Molly M. Miller and Eric Benson
"Lisp Style and Design"
Digital Press, 1990. 214 pages. ISBN 1-55558-044-0.
How to write large Lisp programs and improve Lisp programming
style. Uses the development of Lucid CL as an example.
2. Robin Jones, Clive Maynard, and Ian Stewart.
"The Art of Lisp Programming"
Springer-Verlag, 1989. 169 pages.
3. W. Richard Stark.
"LISP, Lore, and Logic: An Algebraic View of LISP
Programming, Foundations, and Applications"
Springer-Verlag, 1990. 278 pages. ISBN 0-387-97072-X paper ($42).
Self-modifying code, self-reproducing programs, etc.
4. CMU CL User's Manual, Chapter 7, (talks about writing
efficient code). It is available by anonymous ftp from any CMU CS
machine (e.g., ftp.cs.cmu.edu [128.2.206.173]) as the file
/afs/cs.cmu.edu/project/clisp/docs/cmu-user/cmu-user.ps
[when getting this file by anonymous ftp, one must cd to
the directory in one atomic operation, as some of the superior
directories on the path are protected from access by anonymous ftp.]
5. See also Norvig's book, SICP (Abelson & Sussman), SAP
(Springer and Friedman).
6. Hallvard Tretteberg's Lisp Style Guide is available by anonymous
ftp in ftp.think.com:/public/think/lisp/style-guide.text. There is
a fair bit of overlap between Hallvard's style guide and the notes
below and in part 3 of this FAQ.
7. Rajeev Sangal
"Programming Paradigms in Lisp"
McGraw-Hill, 1991. ISBN 0-07-054666-5.
8. Rodney A. Brooks.
"Programming in Common Lisp"
John Wiley & Sons, New York, 1985. 303 pages. ISBN 0-471-81888-7.
Chapter 5 discusses Lisp programming style.
Here are some general suggestions/notes about improving Lisp
programming style, readability, correctness and efficiency:
General Programming Style Rules:
- Write short functions, where each function provides a single,
well-defined operation. Small functions are easier to
read, write, test, debug, and understand.
- Use descriptive variable and function names. If it isn't clear
from the name of a function or variable what its purpose is,
document it with a documentation string and a comment. In fact,
even if the purpose is evident from the name, it is still worth
documenting your code.
- Don't write Pascal (or C) code in Lisp. Use the appropriate
predefined functions -- look in the index to CLtL2, or use the
APROPOS and DESCRIBE functions. Don't put a close parenthesis
on a line by itself -- this can really aggravate programmers
who grew up on Lisp. Lisp-oriented text editors include tools
for ensuring balanced parentheses and for moving across
pairs of balanced parentheses. You don't need to stick
comments on close parentheses to mark which expression they close.
- Use proper indentation -- you should be able to understand
the structure of your definitions without noticing the parentheses.
In general, the way one indents a form is controlled by the
first symbol of the form. In DEFUNs, for example, one puts the
symbol DEFUN, the function name, and the argument list all on
the same line. If the argument list is too long, one can break
it at one of the lambda keywords. Following the argument list,
one inserts a carriage return and lists the expressions in the
body of the definition, with each form starting on its own
line indented three spaces relative to the open parenthesis of
the parent (in this case the DEFUN). This general style -- of
putting all the significant elements of a form on a single
line, followed by a carriage return and the indented body --
holds for many Lisp constructs. There are, of course, variations,
such as keeping the first clause on the same line as the COND
or CASE symbol, and the rules are relaxed in different ways to
keep line lengths to a manageable size. If you find yourself having
trouble fitting everything in even with line breaking and
relaxing the rules, either your function names are too long or your
code isn't very modular. You should perceive this as a signal that
you need to break up your big definitions into smaller chunks, each
with a clearly defined purpose, and possibly replace long function
names with concise but apt shorter ones.
- Use whitespace appropriately. Use whitespace to separate
semantically distinct code segments, but don't use too much
whitespace. For example,
GOOD:
(defun foo (x y)
(let ((z (+ x y 10)))
(* z z)))
BAD:
(defun foo(x y)(let((z(+ x y 10)))(* z z)))
(defun foo ( x y )
(let ( ( z (+ x y 10) ) )
( * z z )
)
)
Although the Lisp reader and compiler don't care which you
use, most experienced Lisp programs find the first example much easier
to read than the last two.
- Don't use line lengths greater than 80 characters. People who
write code using Zmacs on Symbolics Lisp Machines are notoriously
guilty of violating this rule, because the CPT6 font allows
one to squeeze a tremendous amount of code on the display,
especially if one spreads the code out horizontally. This
makes it more difficult to read when printed out or read on
an 80x24 xterm window. In fact, use a line length of 72 characters
because it leaves a strip of white space at the edge of the window.
The following functions often abused or misunderstood by novices.
Think twice before using any of these functions.
- EVAL. Novices almost always misuse EVAL. When experts use
EVAL, they often would be better off using APPLY, FUNCALL, or
SYMBOL-VALUE. Use of EVAL when defining a macro should set off
a warning bell -- macro definitions are already evaluated
during expansion. See also the answer to question 3-12.
The general rule of thumb about EVAL is: if you think you need
to use EVAL, you're probably wrong.
- PROGV. PROGV binds dynamic variables and is often misused in
conjunction with EVAL, which uses the dynamic environment.
In general, avoid unnecessary use of special variables.
PROGV is mainly for writing interpreters for languages embedded
in Lisp. If you want to bind a list of values to a list of
lexical variables, use
(MULTIPLE-VALUE-BIND (..) (VALUES-LIST ..) ..)
or
(MULTIPLE-VALUE-SETQ (..) (VALUES-LIST ..))
instead. Most decent compilers can optimize this expression.
However, use of this idiom is not to be encouraged unless absolutely
necessary.
- CATCH and THROW. Often a named BLOCK and RETURN-FROM are
more appropriate. Use UNWIND-PROTECT when necessary.
- Destructive operations, such as NCONC, SORT, DELETE,
RPLACA, and RPLACD, should be used carefully and sparingly.
In general, trust the garbage collector: allocate new
data structures when you need them.
To improve the readability of your code,
- Don't use any C{A,D}R functions with more than two
letters between the C and the R. When nested, they become
hard to read. If you have complex data structures, you
are often better off describing them with a DEFSTRUCT,
even if the type is LIST. The data abstraction afforded by
DEFSTRUCT makes the code much more readable and its purpose
clearer. If you must use C{A,D}R, try to use
DESTRUCTURING-BIND instead, or at least SECOND, THIRD,
NTH, NTHCDR, etc.
- Use COND instead of IF and PROGN. In general, don't use PROGN if
there is a way to write the code within an implicit
PROGN. For example,
(IF (FOO X)
(PROGN (PRINT "hi there") 23)
34)
should be written using COND instead.
- Never use a 2-argument IF or a 3-argument IF with a second
argument of NIL unless you want to emphasize the return value;
use WHEN and UNLESS instead. You will want to emphasize the
return value when the IF clause is embedded within a SETQ,
such as (SETQ X (IF (EQ Y Z) 2 NIL)). If the second argument
to IF is the same as the first, use OR instead: (OR P Q) rather
than (IF P P Q). Use UNLESS instead of (WHEN (NOT ..) ..)
but not instead of (WHEN (NULL ..) ..).
- Use COND instead of nested IF statements. Be sure to check for
unreachable cases, and eliminate those cond-clauses.
- Use backquote, rather than explicit calls to LIST, CONS, and
APPEND, whenever writing a form which produces a Lisp form, but
not as a general substitute for LIST, CONS and APPEND. LIST,
CONS and APPEND usually allocate new storage, but lists produced
by backquote may involve destructive modification (e.g., ,.).
- Make the names of special (global) variables begin and end
with an asterisk (*): (DEFVAR *GLOBAL-VARIABLE*)
Some programmers will mark the beginning and end of an internal
global variable with a percent (%) or a period (.).
Make the names of constants begin and end with a plus (+):
(DEFCONSTANT +E+ 2.7182818)
This helps distinguish them from lexical variables. Some people
prefer to use macros to define constants, since this avoids
the problem of accidentally trying to bind a symbol declared
with defconstant.
- If your program is built upon an underlying substrate which is
implementation-dependent, consider naming those functions and
macros in a way that visually identifies them, either by placing
them in their own package, or prepending a character like a %, .,
or ! to the function name. Note that many programmers use the
$ as a macro character for slot access, so it should be avoided
unless you're using it for that purpose.
- Don't use property lists. Instead, use an explicit hash table.
This helps avoid problems caused by the symbol being in the wrong
package, accidental reuse of property keys from other
programs, and allows you to customize the structure of the table.
- Use the most specific construct that does the job. This lets
readers of the code see what you intended when writing the code.
For example, don't use SETF if SETQ will do (e.g., for lexical
variables). Use the most specific predicate to test your conditions.
If you intend for a function to be a predicate, have it return T
for true, not just non-NIL.
- When NIL is used as an empty list, use () in your code. When NIL
is used as a boolean, use NIL. Similarly, use NULL to test for an
empty list, NOT to test a logical value. Use ENDP to test for the
end of a list, not NULL.
- Don't use the &AUX lambda-list keyword. It is always clearer to
define local variables using LET or LET*.
- When using RETURN and RETURN-FROM to exit from a block, don't
use (VALUES ..) when returning only one value, except if you
are using it to suppress extra multiple values from the first
argument.
- If you want a function to return no values (i.e., equivalent to
VOID in C), use (VALUES) to return zero values. This signals
to the reader that the function is used mainly for side-effects.
- (VALUES (VALUES 1 2 3)) returns only the first value, 1.
You can use (VALUES (some-multiple-value-function ..)) to suppress
the extra multiple values from the function. Use MULTIPLE-VALUE-PROG1
instead of PROG1 when the multiple values are significant.
- When using MULTIPLE-VALUE-BIND and DESTRUCTURING-BIND, don't rely
on the fact that NIL is used when values are missing. This is
an error in some implementations of DESTRUCTURING-BIND. Instead,
make sure that your function always returns the proper number of
values.
- Type the name of external symbols, functions, and variables
from the COMMON-LISP package in uppercase. This will allow your
code to work properly in a case-sensitive version of Common Lisp,
since the print-names of symbols in the COMMON-LISP package
are uppercase internally. (However, not everybody feels that
being nice to case-sensitive Lisps is a requirement, so this
isn't an absolute style rule, just a suggestion.)
Lisp Idioms:
- MAPCAN is used with a function to return a variable number of
items to be included in an output list. When the function returns zero
or one items, the function serves as a filter. For example,
(mapcan #'(lambda (x) (when (and (numberp x) (evenp x)) (list x)))
'(1 2 3 4 x 5 y 6 z 7))
Documentation:
- Comment your code. Use three semicolons in the left margin before
the definition for major explanations. Use two semicolons that
float with the code to explain the routine that follows. Two
semicolons may also be used to explain the following line when the
comment is too long for the single semicolon treatment. Use
a single semicolon to the right of the code to explain a particular
line with a short comment. The number of semicolons used roughly
corresponds with the length of the comment. Put at least one blank
line before and after top-level expressions.
- Include documentation strings in your code. This lets users
get help while running your program without having to resort to
the source code or printed documentation.
Issues related to macros:
- Never use a macro instead of a function for efficiency reasons.
Declaim the function as inline -- for example,
(DECLAIM (INLINE ..))
This is *not* a magic bullet -- be forewarned that inline
expansions can often increase the code size dramatically. INLINE
should be used only for short functions where the tradeoff is
likely to be worthwhile: inner loops, types that the compiler
might do something smart with, and so on.
- When defining a macro that provides an implicit PROGN, use the
&BODY lambda-list keyword instead of &REST.
- Use gensyms for bindings within a macro, unless the macro lets
the user explicitly specify the variable. For example:
(defmacro foo ((iter-var list) body-form &body body)
(let ((result (gensym "RESULT")))
`(let ((,result nil))
(dolist (,iter-var ,list ,result)
(setq ,result ,body-form)
(when ,result
,@body)))))
This avoids errors caused by collisions during macro expansion
between variable names used in the macro definition and in the
supplied body.
- Use a DO- prefix in the name of a macro that does some kind of
iteration, WITH- when the macro establishes bindings, and
DEFINE- or DEF- when the macro creates some definitions. Don't
use the prefix MAP- in macro names, only in function names.
- Don't create a new iteration macro when an existing function
or macro will do.
- Don't define a macro where a function definition will work just
as well -- remember, you can FUNCALL or MAPCAR a function but
not a macro.
- The LOOP and SERIES macros generate efficient code. If you're
writing a new iteration macro, consider learning to use one
of them instead.
File Modularization:
- If your program involves macros that are used in more than one
file, it is generally a good idea to put such macros in a separate
file that gets loaded before the other files. The same things applies
to primitive functions. If a macro is complicated, the code that
defines the macro should be put into a file by itself. In general, if
a set of definitions form a cohesive and "independent" whole, they
should be put in a file by themselves, and maybe even in their own
package. It isn't unusual for a large Lisp program to have files named
"site-dependent-code", "primitives.lisp", and "macros.lisp". If a file
contains primarily macros, put "-macros" in the name of the file.
Stylistic preferences:
- Use (SETF (CAR ..) ..) and (SETF (CDR ..) ..) in preference to
RPLACA and RPLACD. Likewise (SETF (GET ..) ..) instead of PUT.
- Use INCF, DECF, PUSH and POP instead instead of the corresponding
SETF forms.
- Many programmers religiously avoid using CATCH, THROW, BLOCK,
PROG, GO and TAGBODY. Tags and go-forms should only be necessary
to create extremely unusual and complicated iteration constructs. In
almost every circumstance, a ready-made iteration construct or
recursive implementation is more appropriate.
- Don't use LET* where LET will do. Don't use LABELS where FLET
will do. Don't use DO* where DO will do.
- Don't use DO where DOTIMES or DOLIST will do.
- If you like using MAPCAR instead of DO/DOLIST, use MAPC when
no result is needed -- it's more efficient, since it doesn't
cons up a list. If a single cumulative value is required, use
REDUCE. If you are seeking a particular element, use FIND,
POSITION, or MEMBER.
- If using REMOVE and DELETE to filter a sequence, don't use the
:test-not keyword or the REMOVE-IF-NOT or DELETE-IF-NOT functions.
Use COMPLEMENT to complement the predicate and the REMOVE-IF
or DELETE-IF functions instead.
- Use complex numbers to represent points in a plane.
- Don't use lists where vectors are more appropriate. Accessing the
nth element of a vector is faster than finding the nth element
of a list, since the latter requires pointer chasing while the
former requires simple addition. Vectors also take up less space
than lists. Use adjustable vectors with fill-pointers to
implement a stack, instead of a list -- using a list continually
conses and then throws away the conses.
- When adding an entry to an association list, use ACONS, not
two calls to CONS. This makes it clear that you're using an alist.
- If your association list has more than about 10 entries in it,
consider using a hash table. Hash tables are often more efficient.
(See also [2-2].)
- When you don't need the full power of CLOS, consider using
structures instead. They are often faster, take up less space, and
easier to use.
- Use PRINT-UNREADABLE-OBJECT when writing a print-function.
- Use WITH-OPEN-FILE instead of OPEN and CLOSE.
- When a HANDLER-CASE clause is executed, the stack has already
unwound, so dynamic bindings that existed when the error
occured may no longer exist when the handler is run. Use
HANDLER-BIND if you need this.
- When using CASE and TYPECASE forms, if you intend for the form
to return NIL when all cases fail, include an explicit OTHERWISE
clause. If it would be an error to return NIL when all cases
fail, use ECASE, CCASE, ETYPECASE or CTYPECASE instead.
- Use local variables in preference to global variables whenever
possible. Do not use global variables in lieu of parameter passing.
Global variables can be used in the following circumstances:
* When one function needs to affect the operation of
another, but the second function isn't called by the first.
(For example, *load-pathname* and *break-on-warnings*.)
* When a called function needs to affect the current or future
operation of the caller, but it doesn't make sense to accomplish
this by returning multiple values.
* To provide hooks into the mechanisms of the program.
(For example, *evalhook*, *, /, and +.)
* Parameters which, when their value is changed, represent a
major change to the program.
(For example, *print-level* and *print-readably*.)
* For state that persists between invocations of the program.
Also, for state which is used by more than one major program.
(For example, *package*, *readtable*, *gensym-counter*.)
* To provide convenient information to the user.
(For example, *version* and *features*.)
* To provide customizable defaults.
(For example, *default-pathname-defaults*.)
* When a value affects major portions of a program, and passing
this value around would be extremely awkward. (The example
here is output and input streams for a program. Even when
the program passes the stream around as an argument, if you
want to redirect all output from the program to a different
stream, it is much easier to just rebind the global variable.)
- Beginning students, especially ones accustomed to programming
in C, Pascal, or Fortran, tend to use global variables to hold or pass
information in their programs. This style is considered ugly by
experienced Lisp programmers. Although assignment statements can't
always be avoided in production code, good programmers take advantage
of Lisp's functional programming style before resorting to SETF and
SETQ. For example, they will nest function calls instead of using a
temporary variable and use the stack to pass multiple values. When
first learning to program in Lisp, try to avoid SETF/SETQ and their
cousins as much as possible. And if a temporary variable is necessary,
bind it to its first value in a LET statement, instead of letting it
become a global variable by default. (If you see lots of compiler
warnings about declaring variables to be special, you're probably
making this mistake. If you intend a variable to be global, it should
be defined with a DEFVAR or DEFPARAMETER statement, not left to the
compiler to fix.)
Correctness and efficiency issues:
- In CLtL2, IN-PACKAGE does not evaluate its argument. Use defpackage
to define a package and declare the external (exported)
symbols from the package.
- The ARRAY-TOTAL-SIZE-LIMIT may be as small as 1024, and the
CALL-ARGUMENTS-LIMIT may be as small as 50.
- Novices often mistakenly quote the conditions of a CASE form.
For example, (case x ('a 3) ..) is incorrect. It would return
3 if x were the symbol QUOTE. Use (case x (a 3) ..) instead.
- Avoid using APPLY to flatten lists. Although
(apply #'append list-of-lists)
may look like a call with only two arguments, it becomes a
function call to APPEND, with the LIST-OF-LISTS spread into actual
arguments. As a result it will have as many arguments as there are
elements in LIST-OF-LISTS, and hence may run into problems with the
CALL-ARGUMENTS-LIMIT. Use REDUCE or MAPCAN instead:
(reduce #'append list-of-lists :from-end t)
(mapcan #'copy-list list-of-lists)
The second will often be more efficient (see note below about choosing
the right algorithm). Beware of calls like (apply f (mapcar ..)).
- NTH must cdr down the list to reach the elements you are
interested in. If you don't need the structural flexibility of
lists, try using vectors and the ELT function instead.
- CASE statements can be vectorized if the keys are consecutive
numbers. Such CASE statements can still have OTHERWISE clauses.
To take advantage of this without losing readability, use #. with
symbolic constants:
(eval-when (compile load eval)
(defconstant RED 1)
(defconstant GREEN 2)
(defconstant BLUE 3))
(case color
(#.RED ...)
(#.GREEN ...)
(#.BLUE ...)
...)
- Don't use quoted constants where you might later destructively
modify them. For example, instead of writing '(c d) in
(defun foo ()
(let ((var '(c d)))
..))
write (list 'c 'd) instead. Using a quote here can lead to
unexpected results later. If you later destructively modify the
value of var, this is self-modifying code! Some Lisp compilers
will complain about this, since they like to make constants
read-only. Modifying constants has undefined results in ANSI CL.
See also the answer to question [3-13].
Similarly, beware of shared list structure arising from the use
of backquote. Any sublist in a backquoted expression that doesn't
contain any commas can share with the original source structure.
- Don't proclaim unsafe optimizations, such as
(proclaim '(optimize (safety 0) (speed 3) (space 1)))
since this yields a global effect. Instead, add the
optimizations as local declarations to small pieces of
well-tested, performance-critical code:
(defun well-tested-function ()
(declare (optimize (safety 0) (speed 3) (space 1)))
..)
Such optimizations can remove run-time type-checking; type-checking
is necessary unless you've very carefully checked your code
and added all the appropriate type declarations.
- Some programmers feel that you shouldn't add declarations to
code until it is fully debugged, because incorrect
declarations can be an annoying source of errors. They recommend
using CHECK-TYPE liberally instead while you are developing the code.
On the other hand, if you add declarations to tell the
compiler what you think your code is doing, the compiler can
then tell you when your assumptions are incorrect.
Declarations also make it easier for another programmer to read
your code.
- Declaring the type of variables to be FIXNUM does not
necessarily mean that the results of arithmetic involving the
fixnums will be a fixnum; it could be a BIGNUM. For example,
(declare (type fixnum x y))
(setq z (+ (* x x) (* y y)))
could result in z being a BIGNUM. If you know the limits of your
numbers, use a declaration like
(declare (type (integer 0 100) x y))
instead, since most compilers can then do the appropriate type
inference, leading to much faster code.
- Don't change the compiler optimization with an OPTIMIZE
proclamation or declaration until the code is fully debugged
and profiled. When first writing code you should say
(declare (optimize (safety 3))) regardless of the speed setting.
- Depending on the optimization level of the compiler, type
declarations are interpreted either as (1) a guarantee from
you that the variable is always bound to values of that type,
or (2) a desire that the compiler check that the variable is
always bound to values of that type. Use CHECK-TYPE if (2) is
your intention.
- If you get warnings about unused variables, add IGNORE
declarations if appropriate or fix the problem. Letting such
warnings stand is a sloppy coding practice.
To produce efficient code,
- choose the right algorithm. For example, consider seven possible
implementations of COPY-LIST:
(defun copy-list (list)
(let ((result nil))
(dolist (item list result)
(setf result (append result (list item))))))
(defun copy-list (list)
(let ((result nil))
(dolist (item list (nreverse result))
(push item result))))
(defun copy-list (list)
(mapcar #'identity list))
(defun copy-list (list)
(let ((result (make-list (length list))))
(do ((original list (cdr original))
(new result (cdr new)))
((null original) result)
(setf (car new) (car original)))))
(defun copy-list (list)
(when list
(let* ((result (list (car list)))
(tail-ptr result))
(dolist (item (cdr list) result)
(setf (cdr tail-ptr) (list item))
(setf tail-ptr (cdr tail-ptr))))))
(defun copy-list (list)
(loop for item in list collect item))
(defun copy-list (list)
(if (consp list)
(cons (car list)
(copy-list (cdr list)))
list))
The first uses APPEND to tack the elements onto the end of the list.
Since APPEND must traverse the entire partial list at each step, this
yields a quadratic running time for the algorithm. The second
implementation improves on this by iterating down the list twice; once
to build up the list in reverse order, and the second time to reverse
it. The efficiency of the third depends on the Lisp implementation,
but it is usually similar to the second, as is the fourth. The fifth
algorithm, however, iterates down the list only once. It avoids the
extra work by keeping a pointer (reference) to the last cons of the
list and RPLACDing onto the end of that. Use of the fifth algorithm
may yield a speedup. Note that this contradicts the earlier dictum to
avoid destructive functions. To make more efficient code one might
selectively introduce destructive operations in critical sections of
code. Nevertheless, the fifth implementation may be less efficient in
Lisps with cdr-coding, since it is more expensive to RPLACD cdr-coded
lists. Depending on the implementation of nreverse, however,
the fifth and second implementations may be doing the same
amount of work. The sixth example uses the Loop macro, which usually
expands into code similar to the third. The seventh example copies
dotted lists, and runs in linear time, but isn't tail-recursive.
- use type declarations liberally in time-critical code, but
only if you are a seasoned Lisp programmer. Appropriate type
declarations help the compiler generate more specific and
optimized code. It also lets the reader know what assumptions
were made. For example, if you only use fixnum arithmetic,
adding declarations can lead to a significant speedup. If you
are a novice Lisp programmer, you should use type declarations
sparingly, as there may be no checking to see if the
declarations are correct, and optimized code can be harder to
debug. Wrong declarations can lead to errors in otherwise
correct code, and can limit the reuse of code in other
contexts. Depending on the Lisp compiler, it may also
be necessary to declare the type of results using THE, since
some compilers don't deduce the result type from the inputs.
- check the code produced by the compiler by using the
disassemble function
----------------------------------------------------------------
Subject: [1-4] Where can I learn about implementing Lisp interpreters
and compilers?
Books about Lisp implementation include:
1. John Allen
"Anatomy of Lisp"
McGraw-Hill, 1978. 446 pages. ISBN 0-07-001115-X
Discusses some of the fundamental issues involved in
the implemention of Lisp.
2. Samuel Kamin
"Programming Languages, An Interpreter-Based Approach"
Addison-Wesley, Reading, Mass., 1990. ISBN 0-201-06824-9
Includes sources to several interpreters for Lisp-like
languages, and a pointer to sources via anonymous ftp.
3. Sharam Hekmatpour
"Lisp: A Portable Implementation"
Prentice Hall, 1985. ISBN 0-13-537490-X.
Describes a portable implementation of a small dynamic
Lisp interpreter (including C source code).
4. Peter Henderson
"Functional Programming: Application and Implementation"
Prentice-Hall (Englewood Cliffs, NJ), 1980. 355 pages.
5. Peter M. Kogge
"The Architecture of Symbolic Computers"
McGraw-Hill, 1991. ISBN 0-07-035596-7.
Includes sections on memory management, the SECD and
Warren Abstract Machines, and overviews of the various
Lisp Machine architectures.
6. Daniel P. Friedman, Mitchell Wand, and Christopher T. Haynes
"Essentials of Programming Languages"
MIT Press, 1992, 536 pages. ISBN 0-262-06145-7.
Teaches fundamental concepts of programming language
design by using small interpreters as examples. Covers
most of the features of Scheme. Includes a discussion
of parameter passing techniques, object oriented languages,
and techniques for transforming interpreters to allow
their implementation in terms of any low-level language.
Also discusses scanners, parsers, and the derivation of
a compiler and virtual machine from an interpreter.
Source files available by anonymous ftp from
cs.indiana.edu:/pub/eopl/ [129.79.254.191].
7. Peter Lee, editor, "Topics in Advanced Language Implementation",
The MIT Press, Cambridge, Mass., 1991.
Articles relevant to the implementation of functional
programming languages.
8. Also see the proceedings of the biannual ACM Lisp and Functional
Programming conferences, the implementation notes for CMU Common Lisp,
Norvig's book, and SICP (Abelson & Sussman).
----------------------------------------------------------------
Subject: [1-5] What is the "minimal" set of primitives needed for a Lisp
interpreter?
Many Lisp functions can be defined in terms of other Lisp functions.
For example, CAAR can be defined in terms of CAR as
(defun caar (list) (car (car list)))
It is then natural to ask whether there is a "minimal" or smallest set
of primitives necessary to implement the language.
There is no single "best" minimal set of primitives; it all depends on
the implementation. For example, even something as basic as numbers
need not be primitive, and can be represented as lists. One possible
set of primitives might include CAR, CDR, and CONS for manipulation of
S-expressions, READ and PRINT for the input/output of S-expressions
and APPLY and EVAL for the guts of an interpreter. But then you might
want to add LAMBDA for functions, EQ for equality, COND for
conditionals, SET for assignment, and DEFUN for definitions. QUOTE
might come in handy as well. If you add more specialized datatypes,
such as integers, floats, arrays, characters, and structures, you'll
need to add primitives to construct and access each.
AWKLisp is a Lisp interpreter written in Lisp, available by anonymous
ftp from ftp.cs.cmu.edu:/user/ai/lang/lisp/impl/awk/. It has thirteen
built-in functions: CAR, CDR, CONS, EQ, ATOM, SET, EVAL, ERROR, QUOTE,
COND, AND, OR, LIST.
A more practical notion of a "minimal" set of primitives might be to
look at the implementation of Scheme. While many Scheme functions can
be derived from others, the language is much smaller than Common Lisp.
See Dybvig's PhD thesis,
R. Kent Dybvig, "Three Implementation Models for Scheme", Department
of Computer Science Technical Report #87-011, University of North
Carolina at Chapel Hill, Chapel Hill, North Carolina, April 1987.
for a justification of a particularly practical minimal set of
primitives for Scheme.
In a language like Common Lisp, however, there are a lot of low-level
primitive functions that cannot be written in terms of the others,
such as GET-UNIVERSAL-TIME, READ-CHAR, WRITE-CHAR, OPEN, and CLOSE,
for starters. Moreover, real Common Lisp implementations are often
built upon primitives that aren't part of the language, per se, and
certainly not intended to be user-accessible, such as SYS:%POINTER-REF.
Beside the references listed in [1-4], some other relevant references
include:
McCarthy, John, "Recursive Functions of Symbolic Expressions and
their Computation by Machine, Part I", CACM 3(4):185-195, April 1960.
[Defines five elementary functions on s-expressions.]
McCarthy, John, "A Micro-Manual for Lisp -- not the whole Truth",
ACM SIGPLAN Notices, 13(8):215-216, August 1978.
[Defines the Lisp programming language in 10 rules and gives
a small interpreter (eval) written in this Lisp.]
McCarthy, John, et al., "LISP 1.5 Programmer's Manual", 2nd edition,
MIT Press, 1965, ISBN 0-262-13011-4 (paperback).
[Gives five basic functions, CAR, CDR, CONS, EQ, and ATOM.
Using composition, conditional expressions (COND), and
recursion, LAMBDA, and QUOTE, these basic functions may be used
to construct the entire class of computable functions of
S-expressions. Gives the functions EVAL and APPLY in
M-expression syntax.]
Abelson and Sussman's SICP, especially chapters 4 and 5 on the
implementation of meta-circular and explicit-control evaluators.
Steele and Gabriel's "The Evolution of LISP".
----------------------------------------------------------------
Subject: [1-6] What does CLOS, PCL, X3J13, CAR, CDR, ... mean?
Glossary of acronyms:
CAR Originally meant "Contents of Address portion of Register",
which is what CAR actually did on the IBM 704.
CDR Originally meant "Contents of Decrement portion of
Register", which is what CDR actually did
on the IBM 704. Pronounced "Cudder" ·····@r/ (as in "a cow
chews its cdr"). The first syllable is pronounced
like "could".
LISP Originally from "LISt Processing"
GUI Graphical User Interface
CLOS Common Lisp Object System. The object oriented
programming standard for Common Lisp. Based on
Symbolics FLAVORS and Xerox LOOPS, among others.
Pronounced either as "See-Loss" or "Closs". See also PCL.
PCL Portable Common Loops. A portable CLOS implementation.
Available by anonymous ftp from parcftp.xerox.com:pcl/.
LOOPS Lisp Object Oriented Programming System. A predecessor
to CLOS on Xerox Lisp machines.
X3J13 Subcommittee of the ANSI committee X3 which is
working on the ANSI Standardization of Common Lisp.
ANSI American National Standards Institute
dpANS draft proposed American National Standard (what an ANS
is called while it's in the public review stage of
standardization).
CL Common Lisp
SC22/WG16 The full name is ISO/IEC JTC 1/SC 22/WG 16. It stands
for International Organization for
Standardization/International Electronics(?)
Congress(?) Joint Technical Committee 1, Subcommittee 22,
Working Group 16. This long-winded name is the ISO
working group working on an international Lisp standard,
(i.e., the ISO analogue to X3J13).
CLtL1 First edition of Guy Steele's book,
"Common Lisp the Language".
CLtL2 Second edition of Guy Steele's book,
"Common Lisp the Language".
----------------------------------------------------------------
Subject: [1-7] Lisp Job Postings
The LISP-JOBS mailing list exists to help programmers find Lisp
programming positions, and to help companies with Lisp programming
positions find capable Lisp programmers. (Lisp here means Lisp-like
languages, including Scheme.)
Material appropriate for the list includes Lisp job announcements and
should be sent to ·········@anzus.com. Resumes should not be sent to
the list. Administrative requests (e.g., to be added to the list)
should be sent to ·················@anzus.com.
----------------------------------------------------------------
;;; *EOF*
Archive-name: lisp-faq/part2
Last-Modified: Thu May 12 21:32:47 1994 by Mark Kantrowitz
Version: 1.45
;;; ****************************************************************
;;; Answers to Frequently Asked Questions about Lisp ***************
;;; ****************************************************************
;;; Written by Mark Kantrowitz and Barry Margolin
;;; lisp_2.faq -- 47146 bytes
This post contains Part 2 of the Lisp FAQ.
If you think of questions that are appropriate for this FAQ, or would
like to improve an answer, please send email to us at ········@think.com.
Topics Covered (Part 2):
[2-1] Is there a GNU-Emacs interface to Lisp?
[2-2] When should I use a hash table instead of an association list?
[2-3] What is the equivalent of EXPLODE and IMPLODE in Common Lisp?
[2-4] Is Lisp inherently slower than more conventional languages such as C?
[2-5] Why does Common Lisp have "#'"?
[2-6] How do I call non-Lisp functions from Lisp?
[2-7] Can I call Lisp functions from other languages?
[2-8] I want to call a function in a package that might not exist at
compile time. How do I do this?
[2-9] What is CDR-coding?
[2-10] What is garbage collection?
[2-11] How do I save an executable image of my loaded Lisp system?
How do I run a Unix command in my Lisp?
[2-12] I'm porting some code from a Symbolics Lisp machine to some
other platform, and there are strange characters in the code.
What do they mean?
[2-13] History: Where did Lisp come from?
[2-14] How do I find the argument list of a function?
How do I get the function name from a function object?
[2-15] How can I have two Lisp processes communicate via unix sockets?
[2-16] How can I create a stream that acts like UNIX's /dev/null
(i.e., gobbles any output and immediately signals EOF on
input operations)?
[2-17] Read-time conditionalization of code (#+ #- and *features*)
[2-18] What reader macro characters are used in major Lisp systems?
[2-19] How do I determine if a file is a directory or not?
How do I get the current directory name from within a Lisp
program? Is there any way to create a directory?
[2-20] What is a "Lisp Machine" (LISPM)?
Search for \[#\] to get to question number # quickly.
----------------------------------------------------------------
Subject: [2-1] Is there a GNU-Emacs interface to Lisp?
ILISP is a powerful GNU-Emacs interface to many dialects of Lisp,
including Lucid, Allegro, {A}KCL, IBCL, and CMU. Written by Chris
McConnell <····@cs.cmu.edu> and now maintained by Ivan Vazquez
<····@haldane.bu.edu>. It is available by anonymous ftp from
haldane.bu.edu:/pub/ilisp/ [128.197.54.25]
as the file ilisp.tar.Z. If you want to be on the ilisp mailing list,
to hear about new releases and patches, send mail to
·············@darwin.bu.edu Please send any comments or code to
·····@darwin.bu.edu. Bugs should be sent to ·········@darwin.bu.edu
(or ··········@darwin.bu.edu).
Franz Inc.'s GNU-Emacs/Lisp interface includes an online Common Lisp
manual. (The manual is available by license from Franz Inc. Contact
····@franz.com for more information.) The Emacs-Lisp interface
(without the online Common Lisp reference manual and some
Allegro-specific code) is available free from
ftp.uu.net:/vendor/franz/emacs/eli-2.0.11.tar.gz
and takes advantage of GNU-Emacs 19.X's newest features, including
support for mouse input, pulldown menus, and multifont text. The
interface also supports Epoch 3.2 and 4.2, and LEmacs 19.6 and 19.8.
For discussion of the Franz lisp-emacs interface, join the
··················@cs.berkeley.edu mailing list.
(See also [1-2] for a hardcopy version of the Common Lisp reference manual.)
The cl-shell package provides a major mode (cl-shell-mode) for running
Common Lisp (CL) as an Emacs subprocess. It provides a general
mechanism for communication between CL and Emacs which does not rely
on extra processes, and should therefore be easily portable to any
version of CL. Features include direct (i.e., not through a temp file)
evaluation and in-package compilation of forms from lisp-mode buffers,
type-ahead and a history mechanism for the cl-shell buffer, and pop-up
help facilities for the CL functions documentation, macroexpand and
describe. Extensions for Lucid Common Lisp provide pop-up arglists
and source file editing. Other extensions are provided to allow
editing source files of CLOS or Flavors methods. Cl-shell is
available on the Lucid tape (in the goodies directory) or via
anonymous ftp from whitechapel.media.mit.edu (18.85.0.125).
Lucid includes some other Emacs-Lisp interfaces in its goodies directory.
Harlequin's LispWorks includes an Emacs-Lisp interface.
Venue's Medley has an optional EMACS Interface.
GNU-Emacs itself is available by anonymous ftp from prep.ai.mit.edu.
Edebug, a debugger for Emacs Lisp, and some utilities for Common Lisp
debugging (Dave Gillespie's version of cl.el) are available by
anonymous ftp from
a.cs.uiuc.edu:/pub/edebug/
To join the Edebug mailing list ······@cs.uiuc.edu send mail to
··············@cs.uiuc.edu. For more information, write to Daniel
LaLiberte <·······@cs.uiuc.edu>.
----------------------------------------------------------------
Subject: [2-2] When should I use a hash table instead of an association list?
Both association lists (alists) and hash tables may be used to
represent tabular data. Hash tables have an O(1) running time and
alists an O(n) running time, so hash tables are ultimately more
efficient than alists. However, if the alists are small, they can be
more efficient than hash tables, which have a large initial overhead.
Alists can sometimes be more efficient if the keys are sorted
according to frequency, with the most heavily accessed keys appearing
at the front of the list. But one doesn't always know this kind of
information, and even then the frequency distribution may be flat.
In Allegro CL 4.1 [SPARC; R1], the rule of thumb is that for less than
24 elements, linear search using alists beats hashing. In Lucid CL
4.0.1 HP 9000/700, the break-even point is at 10 elements. The
break-even points vary in other lisps from as low as 4 elements to as
high as 100 elements. So if you're using alists in your code, using
hash tables instead may speed up your program.
A potential problem may occur, however, when the keys of an EQ or EQL
hash table are Lisp objects such as conses or arrays (or other objects
that are identified by their addresses). In most implementations, such
tables must be re-hashed after garbage collection. If your application
causes frequent GCs, this can adversely affect the performance of hash
table lookup. Since EQL-hashing and =-hashing of fixnums generally
don't require rehashing after GC, one way of avoiding this problem is
to include a unique identifier in each key object and hash on that
instead. Another solution is to use an EQUAL hash table if the keys
are conses or an EQUALP hash table if the keys are arrays or other
(non-circular!) structures.
----------------------------------------------------------------
Subject: [2-3] What is the equivalent of EXPLODE and IMPLODE in Common Lisp?
Hopefully, the only reason you need to do this is as part of trying to port
some old MacLisp code to Common Lisp. These functions predated the
inclusion of strings as a first-class data type in Lisp; symbols were used
as strings, and they ere EXPLODEd to allow the individual characters to be
manipulated in a list.
Probably the best approximations of these are:
(defun explode (object)
(loop for char across (prin1-to-string object)
collect (intern (string char))))
(defun implode (list)
(read-from-string (coerce (mapcar #'character list) 'string)))
An alternate definition of EXPLODE which uses MAP instead of LOOP is:
(defun explode (object)
(map 'list #'(lambda (char)
(intern (string char)))
(prin1-to-string object)))
The creation of N conses of garbage to process a string of N
characters is a hideously inefficient way of doing the job. Rewrite
EXPLODE code with PRIN1-TO-STRING, or better STRING if the arguments
are symbols without funny characters. For IMPLODE, try to make its
caller use strings and try to make the result usable as a string to
avoid having to call INTERN or READ-FROM-STRING.
----------------------------------------------------------------
Subject: [2-4] Is Lisp inherently slower than more conventional languages
such as C?
This is a tough question to answer, as you probably expected. In many
cases, it appears to be. Lisp does not require the programmer to specify
the data type of variables, so generic arithmetic operators may have to
perform type checking at runtime in order to determine how to proceed.
However, Lisp code can also be denser (i.e. there is more expressed in a
single line) than many other languages: the Lisp expression (+ A B) is more
powerful than the C expression A+B (the Lisp version supports bignums,
rationals, and complex numbers, while the C version only supports
limited-size integers and floating point); therefore, one may claim that it
is reasonable that the Lisp version take longer than the C version (but
don't expect everyone to accept this rationalization). Solutions to this
include hardware support (e.g. processors that support type tags in data,
such as SPARC and Symbolics Lisp Machines), declarations, and specialized
variants of functions (e.g. in MacLisp, + accepts and returns only fixnums,
+$ accepts and returns only flonums, and PLUS is generic).
At one time, the MIT PDP-10 MacLisp compiler was compared to DEC's
PDP-10 Fortran compiler. When appropriate declarations were supplied
in the Lisp code, the performance of compiled Lisp arithmetic rivaled
that of the Fortran code. It would hardly be fair to compare Lisp
without declarations to Fortran, since the Fortran compiler would have
more information upon which it could base its optimizations. A more
recent test found that numeric code compiled with optimizations using
CMU CL is within the same ballpark as highly optimized Fortran code.
For unoptimized Fortran code, CMU CL was about 4 times faster.
Even the speed of numeric code generated by other Lisp compilers
(AKCL, Allegro, Lucid) was well within an order of magnitude of good
Fortran and C compilers (although slower than CMU CL). Inspection of
the emitted C code from AKCL doesn't reveal many obvious sources of
inefficiency. (Since AKCL compiles Lisp into C, there are many cases
where KCL code is as fast as hand-written C code.)
See the paper peoplesparc.berkeley.edu:/pub/papers/fastlisp.ps.Z
for a discussion of the speed of Lisp vis a vis Fortran or C.
Since Lisp is a good language for rapid prototyping, it is easy for a
mediocre programmer (or even a good programmer, who isn't being careful) to
generate a large amount of inefficient Lisp code. A good example is the use
of APPEND to link successive lists together, instead of keeping a pointer
to the tail of the list. Often a programmer can obtain significant
speed increases by using a time/space profiler to identify the
functions which waste time (often small functions which are called
frequently) and rewriting those functions.
----------------------------------------------------------------
Subject: [2-5] Why does Common Lisp have "#'"?
#' is a macro-character which expands #'FOO to (FUNCTION FOO). Symbols in
Lisp have two bindings, one for values and one for functions, allowing them
to represent both variables and functions, depending on context. #'FOO
accesses FOO's lexical function binding in a context where the value
interpretation would normally occur. #' is also used to create lexical
closures for lambda expressions. A lexical closure is a function which when
invoked executes the body of the lambda-expression in the lexical
environment within which the closure was created. See pp. 115-117 of CLtL2
for more details.
----------------------------------------------------------------
Subject: [2-6] How do I call non-Lisp functions from Lisp?
Most Lisp implementations for systems where Lisp is not the most common
language provide a "foreign function" interface. As of now there has been
no significant standardization effort in this area. They tend to be
similar, but there are enough differences that it would be inappropriate to
try to describe them all here. In general, one uses an
implementation-dependent macro that defines a Lisp function, but instead of
supplying a body for the function, one supplies the name of a function written
in another language; the argument list portion of the definition is
generally augmented with the data types the foreign function expects and
the data type of the foreign function's return value, and the Lisp
interface function arranges to do any necessary conversions. There is also
generally a function to "load" an object file or library compiled in a
foreign language, which dynamically links the functions in the file being
loaded into the address space of the Lisp process, and connects the
interface functions to the corresponding foreign functions.
If you need to do this, see the manual for your language implementation for
full details. In particular, be on the lookout for restrictions on the
data types that may be passed. You may also need to know details about the
linkage conventions that are used on your system; for instance, many C
implementations prepend an underscore onto the names of C functions when
generating the assembler output (this allows them to use names without
initial underscores internally as labels without worrying about conflicts),
and the foreign function interface may require you to specify this form
explicitly.
Franz Allegro Common Lisp's "Foreign Function Call Facility" is
described in chapter 10 of the documentation. Calling Lisp Functions
from C is treated in section 10.8.2. The foreign function interface in
Macintosh Common Lisp is similar. The foreign function interface for
KCL is described in chapter 10 of the KCL Report. The foreign function
interfaces for Lucid on the Vax and Lucid on the Sun4 are
incompatible. Lucid's interface is described in chapter 5 of the
Advanced User's Guide.
----------------------------------------------------------------
Subject: [2-7] Can I call Lisp functions from other languages?
In implementations that provide a foreign function interface as described
above, there is also usually a "callback" mechanism. The programmer may
associate a foreign language function name with a Lisp function. When a
foreign object file or library is loaded into the Lisp address space, it is
linked with these callback functions. As with foreign functions, the
programmer must supply the argument and result data types so that Lisp may
perform conversions at the interface. Note that in such foreign function
interfaces Lisp is often left "in control" of things like memory
allocation, I/O channels, and startup code (this is a major nuisance
for lots of people).
----------------------------------------------------------------
Subject: [2-8] I want to call a function in a package that might not exist at
compile time. How do I do this?
Use (funcall (find-symbol "SYMBOL-NAME" :pkg-name) ...).
----------------------------------------------------------------
Subject: [2-9] What is CDR-coding?
CDR-coding is a space-saving way to store lists in memory. It is normally
only used in Lisp implementations that run on processors that are
specialized for Lisp, as it is difficult to implement efficiently
in software. In normal list structure, each element of the
list is represented as a CONS cell, which is basically two pointers (the
CAR and CDR); the CAR points to the element of the list, while the CDR
points to the next CONS cell in the list or NIL. CDR-coding takes
advantage of the fact that most CDR cells point to another CONS, and
further that the entire list is often allocated at once (e.g. by a call to
LIST). Instead of using two pointers to implement each CONS cell, the CAR
cell contains a pointer and a two-bit "CDR code". The CDR code may contain
one of three values: CDR-NORMAL, CDR-NEXT, and CDR-NIL. If the code is
CDR-NORMAL, this cell is the first half of an ordinary CONS cell pair, and
the next cell in memory contains the CDR pointer as described above. If
the CDR code is CDR-NEXT, the next cell in memory contains the next CAR
cell; in other words, the CDR pointer is implicitly thisaddress+1, where
thisaddress is the memory address of the CAR cell. If the CDR code is
CDR-NIL, then this cell is the last element of the list; the CDR pointer is
implicitly a reference to the object NIL. When a list is constructed
incrementally using CONS, a chain of ordinary pairs is created; however,
when a list is constructed in one step using LIST or MAKE-LIST, a block of
memory can be allocated for all the CAR cells, and their CDR codes all set
to CDR-NEXT (except the last, which is CDR-NIL), and the list will only
take half as much storage (because all the CDR pointers are implicit).
If this were all there were to it, it would not be difficult to implement
in software on ordinary processors; it would add a small amount of overhead
to the CDR function, but the reduction in paging might make up for it. The
problem arises when a program uses RPLACD on a CONS cell that has a CDR
code of CDR-NEXT or CDR-NIL. Normally RPLACD simply stores into the CDR
cell of a CONS, but in this case there is no CDR cell -- its contents are
implicitly specified by the CDR code, and the word that would normally
contain the CDR pointer contains the next CONS cell (in the CDR-NEXT case)
to which other data structures may have pointers, or the first word of some
other object (in the CDR-NIL case). When CDR-coding is used, the
implementation must also provide automatic "forwarding pointers"; an
ordinary CONS cell is allocated, the CAR of the original cell is copied
into its CAR, the value being RPLACD'ed is stored into its CDR, and the old
CAR cell is replaced with a forwarding pointer to the new CONS cell.
Whenever CAR or CDR is performed on a CONS, it must check whether the
location contains a forwarding pointer. This overhead on both CAR and CDR,
coupled with the overhead on CDR to check for CDR codes, is generally
enough that using CDR codes on conventional hardware is infeasible.
There is some evidence that CDR-coding doesn't really save very much
memory, because most lists aren't constructed at once, or RPLACD is done on
them enough that they don't stay contiguous. At best this technique can
save 50% of the space occupied by CONS cells. However, the savings probably
depends to some extent upon the amount of support the implementation
provides for creating CDR-coded lists. For instance, many system functions
on Symbolics Lisp Machines that operate on lists have a :LOCALIZE option;
when :LOCALIZE T is specified, the list is first modified and then copied
to a new, CDR-coded block, with all the old cells replaced with forwarding
pointers. The next time the garbage collector runs, all the forwarding
pointers will be spliced out. Thus, at a cost of a temporary increase in
memory usage, overall memory usage is generally reduced because more lists
may be CDR-coded. There may also be some benefit in improved paging
performance due to increased locality as well (putting a list into
CDR-coded form makes all the "cells" contiguous). Nevertheless, modern
Lisps tend to use lists much less frequently, with a much heavier
reliance upon code, strings, and vectors (structures).
----------------------------------------------------------------
Subject: [2-10] What is garbage collection?
Garbage Collection (GC) refers to the automatic storage allocation
mechanisms present in many Lisps. There are several kinds of storage
allocation algorithms, but most fall within two main classes:
1. Stop and Copy. Systems which copy active objects from "old"
storage to "new" storage and then recycle the old storage.
2. Mark and Sweep. Systems which link together storage
used by discarded objects.
Generational scavenging garbage collection (aka emphemeral GC) is a
variation in which memory is allocated in layers, with tenured
(long-lived) objects in the older layers. Rather than doing a full GC
of all of memory every time more room is needed, only the last few
layers are GCed during an ephemeral GC, taking much less time.
Short-lived objects are quickly recycled, and full GCs are then much
less frequent. It is most often used to improve the performance of
stop and copy garbage collectors. It is possible to implement
ephemeral GC in mark and sweep systems, just much more difficult.
Stop and copy garbage collection provides simpler storage allocation,
avoids fragmentation of memory (intermixing of free storage with used
storage). Copying, however, consumes more of the address space, since up to
half the space must be kept available for copying all the active objects.
This makes stop and copy GC impractical for systems with a small address
space or without virtual memory. Also, copying an object requires that you
track down all the pointers to an object and update them to reflect the new
address, while in a non-copying system you need only keep one pointer to an
object, since its location will not change. It is also more difficult to
explicitly return storage to free space in a copying system.
Garbage collection is not part of the Common Lisp standard. Most Lisps
provide a function ROOM which provides human-readable information about the
state of storage usage. In many Lisps, (gc) invokes an ephemeral garbage
collection, and (gc t) a full garbage collection.
----------------------------------------------------------------
Subject: [2-11] How do I save an executable image of my loaded Lisp system?
How do I run a Unix command in my Lisp?
There is no standard for dumping a Lisp image. Here are the
commands from some lisp implementations:
Lucid: DISKSAVE
Symbolics: Save World [CP command]
CMU CL: SAVE-LISP
Franz Allegro: EXCL:DUMPLISP (documented)
SAVE-IMAGE (undocumented)
Medley: IL:SYSOUT or IL:MAKESYS
MCL: SAVE-APPLICATION <pathname>
&key :toplevel-function :creator :excise-compiler
:size :resources :init-file :clear-clos-caches
KCL: (si:save-system "saved_kcl")
LispWorks: LW:SAVE-IMAGE
There is no standard for running a Unix shell command from Lisp,
especially since not all Lisps run on top of Unix. Here are the
commands from some Lisp implementations:
Allegro: EXCL:RUN-SHELL-COMMAND
Lucid: RUN-PROGRAM (name
&key input output
error-output (wait t) arguments
(if-input-does-not-exist :error)
(if-output-exists :error)
(if-error-output-exists :error))
KCL: SYSTEM
For example, (system "ls -l").
You can also try RUN-PROCESS and EXCLP, but they
don't work with all versions of KCL.
CMU CL: RUN-PROGRAM (program args
&key (env *environment-list*) (wait t) pty input
if-input-does-not-exist output
(if-output-exists :error) (error :output)
(if-error-exists :error) status-hook before-execve)
LispWorks: FOREIGN:CALL-SYSTEM-SHOWING-OUTPUT
To toggle source file recording and cross-reference annotations, use
Allegro: excl:*record-source-file-info*
excl:*load-source-file-info*
excl:*record-xref-info*
excl:*load-xref-info*
LispWorks: (toggle-source-debugging nil)
Memory management:
CMU CL: (bytes-consed-between-gcs) [this is setfable]
Lucid: (change-memory-management
&key growth-limit expand expand-reserved)
Allegro: *tenured-bytes-limit*
LispWorks: LW:GET-GC-PARAMETERS
(use LW:SET-GC-PARAMETERS to change them)
----------------------------------------------------------------
Subject: [2-12] I'm porting some code from a Symbolics Lisp machine to some
other platform, and there are strange characters in the code.
What do they mean?
The Symbolics Zetalisp character set includes the following
characters not present in other Lisps (^ means control):
^] >= greater than or equal to
^\ <= less than or equal to
^Z != not equal to
^^ == equivalent to
^E not
^G pi
^L +/- plus/minus
^H lambda
^F epsilon
^W <--> left/right arrow
^X <-- left arrow
^Y --> right arrow
^A down arrow
^K up arrow
^D up caret
^_ down caret
^T forall
^U there exists
^B alpha
^C beta
^I gamma
^J delta
^O partial delta
^N infinity
^M circle +
^V circle x
Other special characters to look out for are the font-change characters,
which are represented as a ^F followed by a digit or asterisk. A digit
means to push font #N onto the stack; an asterisk means to pop the most
recent font from the stack. You can clean up the code by replacing "\^F."
with "". In format statements, ^P and ^Q are used to delimit text to
be printed in a particular character style.
----------------------------------------------------------------
Subject: [2-13] History: Where did Lisp come from?
John McCarthy developed the basics behind Lisp during the 1956 Dartmouth
Summer Research Project on Artificial Intelligence. He intended it as an
algebraic LISt Processing (hence the name) language for artificial
intelligence work. Early implementations included the IBM 704, the IBM
7090, the DEC PDP-1, the DEC PDP-6 and the DEC PDP-10. The PDP-6 and
PDP-10 had 18-bit addresses and 36-bit words, allowing a CONS cell to
be stored in one word, with single instructions to extract the CAR and
CDR parts. The early PDP machines had a small address space, which
limited the size of Lisp programs.
Milestones in the development of Lisp:
1956 Dartmouth Summer Research Project on AI.
1960-65 Lisp1.5 is the primary dialect of Lisp.
1964- Development of BBNLisp at BBN.
late 60s Lisp1.5 diverges into two main dialects:
Interlisp (originally BBNLisp) and MacLisp.
early 70s Development of special-purpose computers known as Lisp
Machines, designed specificly to run Lisp programs.
Xerox D-series Lisp Machines run Interlisp-D.
Early MIT Lisp Machines run Lisp Machine Lisp
(an extension of MacLisp).
1969 Anthony Hearn and Martin Griss define Standard Lisp to
port REDUCE, a symbolic algebra system, to a variety
of architectures.
late 70s Macsyma group at MIT developed NIL (New Implementation
of Lisp), a Lisp for the VAX.
Stanford and Lawrence Livermore National Laboratory
develop S-1 Lisp for the Mark IIA supercomputer.
Franz Lisp (dialect of MacLisp) runs on stock-hardware
Unix machines.
Gerald J. Sussman and Guy L. Steele developed Scheme,
a simple dialect of Lisp with lexical scoping and
lexical closures, continuations as first-class objects,
and a simplified syntax (i.e., only one binding per symbol).
Advent of object-oriented programming concepts in Lisp.
Flavors was developed at MIT for the Lisp machine,
and LOOPS (Lisp Object Oriented Programming System) was
developed at Xerox.
early 80s Development of SPICE-Lisp at CMU, a dialect of MacLisp
designed to run on the Scientific Personal Integrated
Computing Environment (SPICE) workstation.
1980 First biannual ACM Lisp and Functional Programming Conf.
1981 PSL (Portable Standard Lisp) runs on a variety of platforms.
1981+ Lisp Machines from Xerox, LMI (Lisp Machines Inc)
and Symbolics available commercially.
April 1981 Grass roots definition of Common Lisp as a description
of the common aspects of the family of languages (Lisp
Machine Lisp, MacLisp, NIL, S-1 Lisp, Spice Lisp, Scheme).
1984 Publication of CLtL1. Common Lisp becomes a de facto
standard.
1986 X3J13 forms to produce a draft for an ANSI Common Lisp
standard.
1987 Lisp Pointers commences publication.
1990 Steele publishes CLtL2 which offers a snapshot of
work in progress by X3J13. (Unlike CLtL1, CLtL2
was NOT an output of the standards process and was
not intended to become a de facto standard. Read
the Second Edition Preface for further explanation
of this important issue.) Includes CLOS,
conditions, pretty printing and iteration facilities.
1992 X3J13 creates a draft proposed American National
Standard for Common Lisp. This document is the
first official successor to CLtL1.
[Note: This summary is based primarily upon the History section of the
draft ANSI specification. More detail and references can be obtained from
that document. See [4-12] for information on obtaining a copy.]
Gabriel and Steele's "The Evolution of Lisp", which appeared in the
1993 ACM History of Programming Languages conference, is available by
anonymous ftp from
ftp.cs.umbc.edu:/pub/Memoization/Misc/ [130.85.100.53]
as Evolution-of-Lisp.ps.Z.
----------------------------------------------------------------
Subject: [2-14] How do I find the argument list of a function?
How do I get the function name from a function object?
There is no standard way to find the argument list of a function,
since implementations are not required to save this information.
However, many implementations do remember argument information, and
usually have a function that returns the lambda list. Here are the
commands from some Lisp implementations:
Lucid: arglist
Allegro: excl::arglist
Symbolics: arglist
LispWorks: lw:function-lambda-list
CMU Common Lisp, new compiler:
#+(and :CMU :new-compiler)
(defun arglist (name)
(let* ((function (symbol-function name))
(stype (system:%primitive get-vector-subtype function)))
(when (eql stype system:%function-entry-subtype)
(cadr (system:%primitive header-ref function
system:%function-entry-type-slot)))))
The draft ANSI standard does include FUNCTION-LAMBDA-EXPRESSION and
FUNCTION-KEYWORDS, which can be used to create an ARGLIST function.
If you're interested in the number of required arguments you could use
(defun required-arguments (name)
(or (position-if #'(lambda (x) (member x lambda-list-keywords))
(arglist name))
(length (arglist name))))
To extract the function name from the function object, as in
(function-name #'car) ==> 'car
use the following vendor-dependent functions:
Symbolics: (si::compiled-function-name <fn>)
(unless (si:lexical-closure-p <fn>) ...)
Lucid: (sys::procedure-ref <fn> SYS:PROCEDURE-SYMBOL)
(when (sys:procedurep <fn>) ..)
Allegro: (xref::object-to-function-name <fn>)
CMU CL: (kernel:%function-header-name <fn>)
AKCL: (system::compiled-function-name <fn>)
MCL: (ccl::function-name <fn>)
Harlequin: (system::function-name <fn>)
If a vendor-dependent function does not exist, the following
(inefficient) code maps over all symbols looking for one whose
function-cell matches the function object.
(defun function-name (fobject)
(do-all-symbols (fsymbol)
(when (and (fboundp fsymbol)
(eq (symbol-function fsymbol) fobject))
(return fsymbol))))
If a vendor supports FUNCTION-LAMBDA-EXPRESSION, the third value is
the name of the function, if available.
----------------------------------------------------------------
Subject: [2-15] How can I have two Lisp processes communicate via unix sockets?
CLX uses Unix sockets to communicate with the X window server. Look at
the following files from the CLX distribution for a good example of
using Unix sockets from Lisp:
defsystem.lisp Lucid, AKCL, IBCL, CMU.
socket.c, sockcl.lisp AKCL, IBCL
excldep.lisp Franz Allegro CL
You will need the "socket.o" files which come with Lucid and Allegro.
To obtain CLX, see the entry for CLX in the answer to question [7-1].
See the file sockets.tar.gz in the Lisp Utilities repository
described in the answer to question [6-1].
----------------------------------------------------------------
Subject: [2-16] How can I create a stream that acts like UNIX's /dev/null
(i.e., gobbles any output and immediately signals EOF on
input operations)?
(defparameter *dev-null*
#-lispm
(make-two-way-stream (make-concatenated-stream) (make-broadcast-stream))
;; Since Lisp Machines have a built-in /dev/null which handles
;; additional, non-standard operations, we'll use that instead.
#+lispm #'system:null-stream)
----------------------------------------------------------------
Subject: [2-17] Read-time conditionalization of code (#+ #- and *features*)
The #+ and #- syntax provides for the read-time conditionalization of
lisp code, depending on the presence or absence of keywords on the
*features* list. The nascent Common Lisp standard does not specify
what keywords an implementation must have on its features list.
Nevertheless, most implementations have features that allow one to
distinguish the implementation from other implementations. This allows
one to write implementation-dependent code that is run only in the
relevant implementations.
Here is a list of the features to use to specify a particular Common
Lisp implementation. Unfortunately, not every vendor has a
unique keyword that distinguishes their family of implementations from
those of other vendors, nor major and minor versions of the implementation.
:lucid Lucid Common Lisp
:lcl3.0 Lucid Common Lisp v3.0 and above
:lcl4.0 Lucid Common Lisp v4.0 and above
----------------
(and :allegro :franz-inc) Franz Allegro Common Lisp
:excl Franz Allegro Common Lisp
:aclpc Franz Allegro Common Lisp\PC.
:allegro-v3.0 Franz Allegro Common Lisp v3.0
:allegro-v3.1 Franz Allegro Common Lisp v3.1
:allegro-v4.0 Franz Allegro Common Lisp v4.0
:allegro-v4.1 Franz Allegro Common Lisp v4.1
----------------
:cmu CMU Common Lisp
(and :cmu :new-compiler) CMU Common Lisp w/Python compiler
(and :cmu :python) CMU Common Lisp w/Python compiler
:cmu17 CMU Common Lisp v17 and above
----------------
kcl Kyoto Common Lisp
akcl Austin KCL
:ibcl Ibuki Common Lisp
----------------
:mcl Macintosh Common Lisp
:coral Coral Lisp; bought by Apple to become
MACL, then MCL
:ccl Coral Common Lisp
[Note: Harlequin LispWorks also uses :ccl]
:ccl-1 Coral Common Lisp v1
:ccl-1.3 Coral Common Lisp v1.3 and higher
:ccl-2 present in Macintosh Common Lisp 2.0 and higher
----------------
:harlequin-common-lisp Harlequin Common Lisp
:harlequin-unix-lisp Harlequin on Unix platforms
:harlequin-PC-lisp Harlequin on PC platforms
:lispworks Harlequin Lispworks development environment
:lispworks3 major release of Harlequin Lispworks
:lispworks3.1 major and minor release of Harlequin Lispworks
:harlequin All Harlequin products. not always present?
----------------
:clisp CLISP Common Lisp
----------------
:symbolics Symbolics Genera
:imach Symbolics Genera for Ivory architecture
:cloe-runtime Symbolics CLOE
:cloe CLOE 3.1
----------------
:procyon Procyon Common Lisp
(and :procyon :macintosh) Procyon Common Lisp, Macintosh version
(and :procyon :os2) Procyon Common Lisp, OS2 version
----------------
:gclisp Golden Common Lisp
----------------
(and dec vax common) DEC VAXlisp
----------------
:explorer TI Explorer Lisp Machine | used
:TI TI Explorer Lisp Machine | interchangeably
:elroy TI Explorer release 3 and successors
----------------
:Xerox Medley (Venue's CL/InterLisp combo) to rel2.01
:medley Medley releases 3.0 and up
Use (IL:UNIX-GETPARM "mach") and (IL:UNIX-GETPARM "arch") to
distinguish platforms under Medley.
----------------
:ecl ECoLisp
----------------
:lispm Symbolics, TI, and LMI Lisp machines
In the cases where a feature is not a keyword, it is almost always
in the LISP package.
The draft ANSI standard defines some other useful features:
:cltl1 Compatible with the 1st edition of Steele
:cltl2 Compatible with the 2nd edition of Steele
:IEEE-Floating-Point IEEE floating point support
:X3J13 conforms to some particular draft of the ANSI
CL specification
:draft-ANSI-CL conforms to first full public review draft
:ANSI-CL conforms to ANSI CL after its adoption
:common-lisp language family "Common Lisp"
Other features used by some Lisps include:
:clos Contains a native CLOS implementation.
:pcl Contains the PCL implementation of CLOS.
:flavors Has an implementation of Symbolics Flavors
:loop Contains the :cltl1 version of the Loop macro
:ansi-loop Contains the ANSI Loop macro
:clx or :xlib Contains CLX
:clxr4 or :CLX-MIT-R4 Contains CLX for X11R4
:clxr5 or :CLX-MIT-R5 Contains CLX for X11R5
:compiler Contains a compiler
:windows MS Windows version
:color Color display
:monochrome Monochrome display
:multiprocessing Has multiprocessing capabilities.
:profiler Has a PC-monitoring based profiler.
Platform-specific features, CPU-dependent features, and
operating-system specific features are also important because they can
indicate changes between different implementations of the same lisp,
such as compiled file extensions (e.g., .sbin, .hbin, etc.).
Unfortunately, not every vendor includes such features, and the naming
conventions are inconsistent. Where there are several names for the
same feature, we've put the preferred name first. Hopefully the
vendors will begin to standardize their use of these features.
CPU-dependent features include :sparc (used in CMU CL, Lucid CL,
Harlequin, and Allegro CL), :mips (used in Allegro CL), :r2000 (used
in Allegro CL even on r4000 machines), :mc68000, and :pa (HP's
9000/800 RISC cpu). Platform-specific features include :sun (used in
Allegro CL and Lucid), :sun4 (used in CMU CL and Allegro CL), :sgi
(used in Allegro CL), :hp300, :hp400, :hp500, :sun3, :vax, :prime,
:dec, :dec3100, :macintosh (used in Procyon but not MCL), :ibm-pc,
:ibm-rt-pc. OS-specific features include :unix (used in CMU CL, IBCL,
and Lucid CL), :vms, :sunos (used in CMU CL), :sun-os (used in Lucid),
:sunos4.0 and :sunos4 (used in various Allegro versions independent of
the actual version of SunOS), :mach (used in CMU CL), :hpux, :ultrix,
:os2, and :svr4.
Notes:
:allegro alone doesn't suffice to distinguish Franz Allegro Common
Lisp from Macintosh Allegro Common Lisp (an early version of
Macintosh Common Lisp). :excl specifies that the EXCL package (a
set of Allegro extensions to Common Lisp) is present, but this has
since become synonymous with Franz Allegro Common Lisp.
Thanks to Vincent Keunen for gathering the information in this list.
----------------------------------------------------------------
Subject: [2-18] What reader macro characters are used in major Lisp systems?
The draft ANSI standard for Common Lisp leaves many dispatching macro
characters unassigned. Of these, the following are explicitly reserved
for the user and hence will never be defined by Common Lisp:
#!, #?, #[, #], #{, and #}.
All other unassigned macro characters are not reserved for the user,
and hence the user has no guarantee that they won't be used by some
Lisp implementation.
As a result, there is the potential of portability clashes between
systems that use the same macro characters. This question lists the
non-standard macro character usage of major Lisp systems, in an effort
to avoid such conflicts.
#" AKCL; pathnames
#$ Macintosh Common Lisp; traps
#% Cyc; references to constants in the representation language
#% Harlequin Lispworks; ?
·@ Macintosh Common Lisp; Points notation
·@ Defsystem
#I Portable Infix Package
#L Allegro Common Lisp; logical pathnames
#M Series
#T Allegro Common Lisp; ?
#Y CLISP; ?
#Z Series
#_ Macintosh Common Lisp; traps
#` Harlequin Lispworks; ?
There is a proposal in the ANSI draft to have COMPILE-FILE and LOAD
bind *READTABLE*, which would allow one to locally redefine syntax
through private readtables. Unfortunately, this doesn't help with the
Infix Package, where one wants to globally extend syntax.
----------------------------------------------------------------
Subject: [2-19] How do I determine if a file is a directory or not?
How do I get the current directory name from within a Lisp
program? Is there any way to create a directory?
There is no portable way in Common Lisp of determining whether a file
is a directory or not. Calling DIRECTORY on the pathname will not
always work, since the directory could be empty. For UNIX systems
(defun DIRECTORY-P (pathname)
(probe-file (concatenate 'string pathname "/.")))
seems to work fairly reliably. (If "foo" is a directory, then "foo/."
will be a valid filename; if not, it will return NIL.) This won't, of
course, work on the Macintosh, or on other operating systems (e.g.,
MVS, CMS, ITS). On the Macintosh, use DIRECTORYP.
Moreover, some operating systems may not support the concept of
directories, or even of a file system. For example, recent work on
object-oriented technology considers files to be collections of
objects. Each type of collection defines a set of methods for reading
and writing the objects "stored" in the collection.
There's no standard function for finding the current directory from
within a Lisp program, since not all Lisp environments have the
concept of a current directory. Here are the commands from some Lisp
implementations:
Lucid: WORKING-DIRECTORY (which is also SETFable)
PWD and CD also work
Allegro: CURRENT-DIRECTORY (use excl:chdir to change it)
CMU CL: DEFAULT-DIRECTORY
LispWorks: LW:*CURRENT-WORKING-DIRECTORY*
(use LW:CHANGE-DIRECTORY to change it)
Allegro also uses the variable *default-pathname-defaults* to resolve
relative pathnames, maintaining it as the current working directory.
So evaluating (truename "./") in Allegro (and on certain other
systems) will return a pathname for the current directory. Likewise,
in some VMS systems evaluating (truename "[]") will return a pathname
for the current directory.
There is no portable way of creating a new directory from within a
Lisp program.
----------------------------------------------------------------
Subject: [2-20] What is a "Lisp Machine" (LISPM)?
A Lisp machine (or LISPM) is a computer which has been optimized to run lisp
efficiently and provide a good environment for programming in it. The
original Lisp machines were implemented at MIT, with spinoffs as LMI (defunct)
and Symbolics (bankrupt). Xerox also had a series of Lisp machines
(Dandylion, Dandytiger), as did Texas Instruments (TI Explorer). The
TI and Symbolics Lisp machines are currently available as cards that
fit into Macintosh computers (the so-called "Lisp on a chip").
Optimizations typical of Lisp machines include:
- Hardware Type Checking. Special type bits let the type be checked
efficiently at run-time.
- Hardware Garbage Collection.
- Fast Function Calls.
- Efficient Representation of Lists.
- System Software and Integrated Programming Environments.
For further information, see:
Paul Graham, "Anatomy of a Lisp Machine", AI Expert, December 1988.
Pleszkun and Thazhuthaveetil, "The Architecture of Lisp Machines",
IEEE Computer, March 1987.
Ditzel, Schuler and Thomas, "A Lisp Machine Profile: Symbolics 3650",
AI Expert, January 1987.
Peter M. Kogge, "The Architecture of Symbolic Computers",
McGraw-Hill 1991. ISBN 0-07-035596-7.
[Derived from a post by Arthur Pendragon <··········@delphi.com>.]
----------------------------------------------------------------
;;; *EOF*