This is quick-n-dirty conversion of the old comp.lang.lisp FAQ into Markup syntax. (Last updated: 2006-01-30T16:59:33+8:00)
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):
Postings should be of general interest to the Lisp community. See also question [4-9]. Postings asking for solutions to homework problems are inappropriate.
The comp.lang.lisp newsgroup is archived in ftp.cs.cmu.edu:/user/ai/pubs/news/comp.lang.lisp/ on a weekly basis.
Every so often, somebody posts an inflammatory message, such as
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.
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) ...)).
There are several good Lisp introductions and tutorials:
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/
b.gp.cs.cmu.edu:/usr/dst/public/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.
3. Wade L. Hennessey. "Common Lisp" McGraw-Hill, New York, 1989. 395 pages. ISBN 0-07-028177-7, $26.95. 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, ISBN 0-13-53276-2-8. 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. 358 pages, 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:
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, ISBN 0-89-85960-9-2, $29.95.
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 ai3@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, ISBN 0-20-11114-8-9, $23.95. 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. Tony Hasemer and John Domingue. "Common Lisp Programming for Artificial Intelligence" Addison-Wesley, Reading, MA, 1989. 444 pages, ISBN 0-20-11757-9-7.
This book presents an introduction to Artificial Intelligence
with an emphasis on the role of knowledge representation. Three
chapters focus on object-oriented programming, including the
construction and use of a subset of CLOS.
The authors' research into the problems faced by novice Lisp
users influenced the content and style of the book. (The authors
are members of the Human Cognition Research Laboratory at the
Open University in the United Kingdom.) The book employs a
tutorial approach, especially in areas that students often find
difficult, such as recursion. Early and progressive treatment of
the evaluator promotes understanding of program execution.
Hands-on exercises are used to reinforce basic concepts.
The book assumes no prior knowledge of Lisp or AI and is a
suitable textbook for students in Cognitive Science, Computer
Science and other disciplines taking courses in Lisp or AI
programming as well as being invaluable for professional
programmers who are learning Lisp for developing AI applications.
7. Steven Tanimoto "The Elements of Artificial Intelligence Using Common Lisp", 2nd edition Computer Science Press, New York, 1995. 562 pages, ISBN 0-71-67826-9-3, (ISBN 0-71-67823-0-8, 1990, $48).
8. Patrick R. Harrison "Common Lisp and Artificial Intelligence" Prentice Hall, Englewood Clifs, NJ, 1990. 244 pages, ISBN 0-13-1552430, $22.50.
9. Paul Graham "On Lisp: Advanced Techniques for Common Lisp" Prentice Hall, Englewood Clifs, NJ, 1994. 413 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 with several nice examples. Source code is available by anonymous ftp from ftp.das.harvard.edu:/pub/onlisp/ as a single 56kb file.
10. John A. Moyne "Lisp: A first language for computing" Van Nostrand Reinhold, New York, 1991. 278 pages, ISBN 0442004265.
General Lisp reference books include:
1. ANSI/X3J13 Programming Language Common Lisp (ANSI/X3.226-1994) American National Standards Institute 11 West 42nd Street, New York, NY 10036. http://www.ansi.org/
2. Kent M. Pitman Common Lisp HyperSpec (TM) Harlequin, Inc., 1996. This is an HTML-only document available via the web. Available for browsing from http://www.harlequin.com/books/HyperSpec/FrontMatter/ Available free for download (subject to some legal restrictions) from http://www.harlequin.com/books/HyperSpec/ Includes text from ANSI/X3.226-1994 and other design rationales.
3. Guy L. Steele "Common Lisp: The Language" [CLtL1] Digital Press, 1984. 465 pages. ISBN 0-932376-41-X.
4. Guy L. Steele "Common Lisp: The Language, 2nd Edition" [CLtL2] Digital Press, 1990. 1029 pages, ISBN 1-55558-041-6 paperbound ($39.95).
[Butterworth-Heinemann, the owners of Digital Press, have made
the LaTeX sources to this book available by anonymous FTP from
cambridge.apple.com:/pub/CLTL/
A copy of the distribution is also available from
ftp.cs.cmu.edu:/user/ai/lang/lisp/doc/cltl/
The paperbound version of the book is, of course, available at
fine bookstores, or contact them directly at Digital Press,
225 Wildwood Street, Woburn, MA 01801, call 800-366-2665
(617-928-2527), or fax 800-446-6520 (617-933-6333). A copy of
the Digital Press book catalog is available from the same FTP location.]
A html version, produced using latex2html on the latex sources,
is accessible via the URL:
http://www.cs.cmu.edu/Web/Groups/AI/html/cltl/cltl2.html
5. Franz Inc. "Common Lisp: The Reference" Addison-Wesley, Reading, MA 1988. ISBN 0-201-11458-5 Entries on Lisp (CLtL1) functions in alphabetical order.
6. Rosemary Simpson "Common Lisp, the Index" Franz Inc., Berkeley, CA, 1987. 71 pages, $4.95. A cross-referenced index to Steele's book, 1st edition.
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. (Robert Kessler <kessler@cons.cs.utah.edu> and Carolyn Talcott <clt@sail.stanford.edu> are the editors). 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 wilson@cs.utexas.edu
for more info.
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, $26.95. 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, ISBN 0-387-19568-8 ($33).
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:
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 programmers find the first example
much easier to read than the last two.
The following functions often abused or misunderstood by novices. Think twice before using any of these functions.
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.
To improve the readability of your code,
(IF (FOO X)
(PROGN (PRINT "hi there") 23)
34)
should be written using COND instead.
Lisp Idioms:
Documentation:
Issues related to macros:
(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.
(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.
File Modularization:
Stylistic preferences:
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.)
Correctness and efficiency issues:
(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 ..)).
(eval-when (compile load eval)
(defconstant RED 1)
(defconstant GREEN 2)
(defconstant BLUE 3))
(case color
(#.RED ...)
(#.GREEN ...)
(#.BLUE ...)
...)
(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.
(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.
There is a long-running discussion of whether pushing items
onto a list and then applying NREVERSE to the result is faster or
slower than the alternatives. According to Richard C. Waters (Lisp
Pointers VI(4):27-34, October-December 1993), the NREVERSE strategy is
slightly faster in most Lisp implementations. But the speed difference
either way isn't much, so he argues that one should pursue the option
that yields the clearest and simplest code, namely using NREVERSE.
Here's code for a possible implementation of NREVERSE. As is
evident, most of the alternatives to using NREVERSE involve
essentially the same code, just reorganized.
(defun nreverse (list)
;; REVERSED is the partially reversed list,
;; CURRENT is the current cons cell, which will be reused, and
;; REMAINING are the cons cells which have not yet been reversed.
(do* ((reversed nil)
(current list remaining)
(remaining (cdr current) (cdr current)))
((null current)
reversed)
;; Reuse the cons cell at the head of the list:
;; reversed := ((car remaining) . reversed)
(setf (cdr current) reversed)
(setf reversed current)))
- 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
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. The source for the interpreters in the book is available by anonymous FTP from a.cs.uiuc.edu:/pub/kamin/kamin.distr/ Tim Budd reimplemented the interpreters in C++, and has made them available by anonymous ftp from cs.orst.edu:/pub/budd/kamin/
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. Includes a few chapters on converting code into a continuation passing style. 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).
9. Christian Queinnec "Les Langages Lisp" InterEditions (in French), 1994. 500 pages. ISBN 2-7296-0549-5, 61-2448-1. (?) Cambridge University Press (in English), 1996. ISBN 0-521-56247-3.
The book covers Lisp, Scheme and other related dialects,
their interpretation, semantics and compilation.
All of the programs described in the book are available by
anonymous ftp from
ftp.inria.fr:/INRIA/Projects/icsla/Books/LiSP94Sep05.tar.gz
For more information, see the book's URL
file://ftp.inria.fr/INRIA/Projects/icsla/WWW/LiSP.html
or contact the author at Christian.Queinnec@inria.fr
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 awk, 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".
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" /kUdd@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 Electrotechnical Commission, Joint Technical Committee 1 Subcommittee 22 (full name "Information Technology — Programming Languages and their Environments"), 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".
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 ai+lisp-jobs@cs.cmu.edu. Resumes should NOT be sent to the list.
[Note: The 'ai+' part of the mailing list name is used for directing submissions to the appropriate mail-server. The list is NOT restricted to AI-related Lisp jobs — all Lisp job announcements are welcome.]
As a matter of policy, the contents of this mailing list is considered confidential and will not be disclosed to anybody.
To subscribe, send a message to ai+query@cs.cmu.edu with subscribe lisp-jobs <First Name> <Last Name>, <Affiliation/Organization> in the message body.
(If your mailer objects to the "+", send subscription requests to "ai+query"@cs.cmu.edu, job announcements to "ai+lisp-jobs"@cs.cmu.edu, etc.)
For help on using the query server, send mail to ai+query@cs.cmu.edu with help in the message body.
Job postings sent to the list are automatically archived in ftp.cs.cmu.edu:/user/ai/jobs/lisp/
If you have any other questions, please send them to ai+@cs.cmu.edu
ILISP is a powerful GNU-Emacs interface to many dialects of Lisp, including Lucid, Allegro, {A}KCL, IBCL, and CMU. Written by Chris McConnell <ccm+@cs.cmu.edu> and now maintained by Marco Antoniotti <marcoxa@cs.nyu.edu> and Rick Busdiecker <rfb@lehman.com>. It is available by anonymous ftp from h.gp.cs.cmu.edu:/usr/rfb/ilisp/ [128.2.254.156] as the file ilisp-5.6.tar.gz. It is also available in the CMU AI Repository in ftp.cs.cmu.edu:/user/ai/lang/lisp/util/emacs/ilisp/ If you want to be on the ilisp mailing list, to hear about new releases and patches, send mail to ilisp-request@lehman.com. Please send any comments, code, or bug reports to ilisp@lehman.com.
Franz Inc.'s GNU-Emacs/Lisp interface includes an online Common Lisp manual. (The manual is available by license from Franz Inc. Contact info@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.franz.com:/pub/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 allegro-cl-request@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 edebug@cs.uiuc.edu send mail to edebug-request@cs.uiuc.edu. For more information, write to Daniel LaLiberte <liberte@cs.uiuc.edu>.
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.
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.
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.
#' 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.
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.
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).
Use (funcall (find-symbol "SYMBOL-NAME" :pkg-name) ...).
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).
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.
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 Be sure to garbage collect before dumping the image. You may need to experiment with the kind of garbage collection for large images, and may find better results if you build the image in stages.
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 (command &key input output error-output wait if-input-does-not-exist if-output-exists if-error-output-exists) 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)
Environment Variable Access: Allegro: (sys:getenv var) (sys:setenv var value) or (setf (sys:getenv var) value) Lucid: (environment-variable var) (set-environment-variable var value) CMU CL 17: (cdr (assoc (intern var :keyword) *environment-list*)) {A}KCL, GCL: (system:getenv var) CLISP: (system::getenv var)
Exiting/Quitting: CLISP: EXIT Allegro: EXIT (&optional excl::code &rest excl::args &key excl::no-unwind excl::quiet) LispWorks: BYE (&optional (arg 0)) Lucid: QUIT (&optional (lucid::status 0)) CMU CL: QUIT (&optional recklessly-p)
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.
*** 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.
brad miller maintains a lisp history web page at
http://www.cs.rochester.edu/u/miller/lisp-history.html
*** 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