From: mkant+@cs.cmu.edu (Mark Kantrowitz)
Newsgroups: comp.lang.lisp,news.answers
Subject: FAQ: Lisp Frequently Asked Questions 1/5 [Monthly posting]
Summary: Introductory Matter and Bibliography of Introductions and References
Date: 14 Aug 92 00:37:11 GMT
Article-I.D.: cs.lisp-faq-1.text_713752615
Expires: Sun, 27 Sep 1992 00:36:55 GMT
Reply-To: lisp-faq@think.com
Followup-To: poster
Organization: School of Computer Science, Carnegie Mellon
Supersedes: <lisp-faq-1.text_711014458@cs.cmu.edu>

Archive-name: lisp-faq/part1
Last-Modified: Thu Aug  6 11:54:55 1992 by Mark Kantrowitz
Version: 1.23

;;; ****************************************************************
;;; Answers to Frequently Asked Questions about Lisp ***************
;;; ****************************************************************
;;; Written by Mark Kantrowitz and Barry Margolin
;;; lisp-faq-1.text -- 34247 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 lisp-faq@think.com.

Note that the lisp-faq mailing list is for discussion of the content
of the FAQ posting.  It is not the place to ask questions about Lisp;
use either the common-lisp@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.

There are currently five parts to the Lisp FAQ:
   1. Introductory Matter and Bibliography of Introductions and References
   2. General Questions
   3. Common Pitfalls
   4. Lisp/Scheme Implementations and Mailing Lists
   5. CLOS and PCL Questions
Part 4 is cross-posted to the comp.lang.scheme newsgroup. 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 documentation is available on Lisp? How can I learn Lisp?
  [1-2]	  How can I improve my Lisp programming style and coding efficiency?
  [1-3]	  Where can I learn about implementing Lisp interpreters and compilers?
  [1-4]	  What does CLOS, PCL, X3J13, CAR, CDR, ... mean? 

Topics Covered (Part 2):

  [2-0]   What FTP resources are available?
  [2-1]   Is there a GNU-Emacs interface to Lisp?
  [2-2]   How can I use the X Window System or other GUIs from Lisp?
  [2-3]   When is it right to use EVAL?
  [2-4]   What is the equivalent of EXPLODE and IMPLODE in Common Lisp?
  [2-5]   Is Lisp inherently slower than more conventional languages such as C?
  [2-6]   Why does my program's behavior change each time I use it?
  [2-7]   Why does Common Lisp have "#'"?
  [2-8]   How do I call non-Lisp functions from Lisp?
  [2-9]   Can I call Lisp functions from other languages?
  [2-10]  I want to call a function in a package that might not exist at
          compile time. How do I do this?  
  [2-11]  What is CDR-coding?
  [2-12]  What is garbage collection?
  [2-13]  How do I save an executable image of my loaded Lisp system?
          How do I run a Unix command in my Lisp?
          How do I get the current directory name from within a Lisp program?
  [2-14]  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-15]  History: Where did Lisp come from?
  [2-16]  How do I find the argument list of a function?
  [2-17]  How can I have two Lisp processes communicate via unix sockets?
  [2-18]  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)?

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 and DO.
  [3-10] What is the difference between FUNCALL and APPLY?
  [3-11] Miscellaneous things to consider when debugging code.

Lisp/Scheme Implementations and Mailing Lists (Part 4):

  [4-0]	  Where can I get/buy Lisp and Scheme for the ... architecture?
  [4-1]	  Where can I get an implementation of Prolog in Lisp?
  [4-2]   What is Dylan?
  [4-3]	  What Lisp-related discussion groups and mailing lists exist?

CLOS Questions (Part 5):

  [5-0]	  What is CLOS (PCL) and where can I get it?
	  How do you pronounce CLOS?
  [5-1]	  What documentation is available about object-oriented
	  programming in Lisp?	
  [5-2]	  How 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?
  [5-5]   Given the name of a class, how can I get the names of its slots?


Search for [#] to get to question number # quickly.


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 file is available via anonymous FTP from CMU
and Thinking Machines: 

   To obtain the files from CMU, connect by anonymous ftp to any CMU CS
   machine (e.g., ftp.cs.cmu.edu [128.2.206.173]), using username
   "anonymous" and password "name@host". The files lisp-faq-1.text,
   lisp-faq-2.text, lisp-faq-3.text, lisp-faq-4.text and lisp-faq-5.text
   are located in the directory
       /afs/cs.cmu.edu/user/mkant/Public/Lisp-Utilities/
   [Note: You must cd to this directory in one atomic operation, as
   some of the superior directories on the path are protected from
   access by anonymous ftp.] If your site runs the Andrew File System,
   you can just cp the files directly without bothering with FTP.

   To obtain the files from Thinking Machines, ftp them from ftp.think.com,
   in the directory /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.

Unless otherwise specified, the Lisp dialect referred to is Common Lisp,
as defined by "Common Lisp: the Language" (aka "CLtL") 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. Enhancements such as CLOS, conditions, and the LOOP
macro will be referred to separately.

----------------------------------------------------------------
[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-2].

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 AI programs implemented in Lisp should
sometimes be cross-posted to the newsgroup comp.ai.

----------------------------------------------------------------
[1-1] What documentation is available on Lisp? 
      How can I learn Lisp?

There are several good Lisp introductions and tutorials:

   1. David S. Touretzky
      "Common Lisp: A Gentle Introduction to Symbolic Computation"
      Benjamin/Cummings Publishers, 1990. 384 pages.
	   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.

   2. Robert Wilensky
      "Common LISPcraft"
      W. W. Norton, 1986. 385 pages.

   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

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.

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.

	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 and finding patterns in images. Not 
	   a tutorial. Has many good examples.

   4. Rodney A. Brooks.
      "Programming in Common Lisp"
      Wiley, 1985. 303 pages.

   5. 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.

   6. 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. 

   7. Hasemer and Domingue.
      "Common Lisp Programming for Artificial Intelligence"
      Addison-Wesley, 1989.

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 functions in alphabetical order.

   4. K. Dybvig. 
      "The Scheme programming language"
      Prentice Hall, 1987.
	 Good reference for Scheme.

Lisp periodicals include:
	
   1. LISP Pointers.
      Published by ACM SIGPLAN six times a year. Volume 1, Number 1
      was April-May 1987. 

   2. LISP and Symbolic Computation, Kluwer Academic Press. Volume 1
      was published in 1989. (jlz@lucid.com is the editor).

   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.

Introductions to Scheme (Many books on Scheme are worth reading
even if you use Common Lisp, because many of the issues are similar):

   1. Harold Abelson and Gerald Jay Sussman, with Julie Sussman.
      "Structure and Interpretation of Computer Programs"
      MIT Press (Cambridge, MA) and McGraw-Hill (New York), 1985.
      542 pages. ISBN 0-262-01077-1
	   Starts off introductory, but rapidly gets into powerful
	   Lisp-particular constructs, such as using closures and
	   engines, building interpreters, compilers and
	   object-oriented systems.  

   2. Daniel P. Friedman and M. Felleisen.
      "The Little LISPer"
      Science Research Associates (Chicago), 1974. 58 pages.
      MIT Press (Cambridge, MA), 1987. ISBN 0-262-56038-0.
	   Good for a quick introduction. Uses Scheme instead of
	   Common Lisp.	 (SRA edition uses a dialect of Scheme with
	   footnotes about translating to Scheme or Common Lisp. The
	   MIT Press edition is in Scheme without the footnotes.)

   3. George Springer and Daniel P. Friedman
      "Scheme and the Art of Programming" 
      MIT Press and McGraw Hill, 1989, 400 pages.
      MIT Press and McGraw Hill, 1990, 596 pages.
	   Introduces basic concepts of programming in Scheme. Also deals 
	   with object oriented programming, co-routining, continuations. 

   4. Wolfgang Kreutzer and Bruce McKenzie
      "Programming for Artificial Intelligence: 
       Methods, Tools and Applications"
      Addison-Wesley (Reading, MA), 1990. 682 pages. 
      ISBN 0-201-41621-2.
	   Discusses Scheme, Prolog, and Smalltalk, gives an overview of
	   the history and philosophy of AI, surveys three major
	   programming paradigms (procedural, declarative, and
	   object-oriented), and metaphors to AI programming.

   5. Smith
      "Introduction to Scheme"
       1988.
	   Focuses on PC Scheme.

   6. Michael Eisenberg 
      "Programming in Scheme"
      Scientific Press (Redwood City, CA), 1988. 304 pages.

----------------------------------------------------------------
[1-2] 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
	   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).

Here are some general suggestions/notes about improving Lisp
programming style, readability, correctness and efficiency:

   Functions often abused or misunderstood by novices: 

      - EVAL

      - PROGV. PROGV modifies the dynamic bindings of variables and
	is often misused in conjunction with EVAL, which uses the
	dynamic environment. In general, avoid unnecessary use of
	special variables.

      - CATCH and THROW. Often a named BLOCK and RETURN-FROM are
	more appropriate.

      - 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.

   Think twice before using any of these functions.

   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. 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 second
	argument NIL unless you want to emphasize the return value;
	use WHEN and UNLESS instead.

      - Use backquote, rather than explicit calls to LIST, CONS, and
	APPEND, whenever writing a form which produces a Lisp form.

      - Make the names of special (global) variables start and end
	with an asterisk (*).

   Stylistic preferences:

      - Use (SETF (CAR ..) ..) and (SETF (CDR ..) ..) in preference to
	RPLACA and RPLACD.

      - Many programmers religiously avoid using CATCH, THROW, BLOCK,
	PROG, and TAGBODY.  

   Correctness and efficiency issues:

      - The ARRAY-TOTAL-SIZE-LIMIT may be as small as 1024, and the
        CALL-ARGUMENTS-LIMIT may be as small as 50.

      - Avoid using APPLY to flatten lists. (apply #'append list-of-lists)
	is compiled into a function call, and can run into problems with
	the CALL-ARGUMENTS-LIMIT. Use REDUCE or MAPCAR 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).

      - 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.

      - 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 [2-7].

	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, which
	is necessary unless you've very carefully checked your code
	and added all the appropriate type declarations.

      - Don't add declarations to code until it is fully debugged.
	Incorrect declarations can be an annoying source of errors.
	Use CHECK-TYPE liberally while developing code, if you later
	intend to add declarations.

   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. It's equivalent to the other
	linear-time examples in a lisp that is properly tail-recursive. To
	get an implementation of copy-tree, replace (car list) with
	(copy-list (car list)).

      - 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. 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

----------------------------------------------------------------
[1-3] 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

   2. Samuel Kamin
      "Programming Languages, An Interpreter-Based Approach"
      Addison-Wesley. 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.

   7. Also see the proceedings of the biannual ACM Lisp and
      Functional Programming conferences, and the implementation
      notes for CMU Common Lisp.
----------------------------------------------------------------
[1-4]  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".
   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
   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". 

   SICP		   Abelson and Sussman's book "Structure and
		   Interpretation of Computer Programs".
   SCOOPS	   An experimental object-oriented programming
		   language for Scheme.
   R3RS		   Revised^3 Report on the Algorithmic Language Scheme.
   R4RS		   Revised^4 Report on the Algorithmic Language Scheme.
----------------------------------------------------------------
     
;;; ********************************
;;; Change Log *********************
;;; ********************************
;;; Date      Who     Ver   Reason
;;; ------------------------------------------------------------
;;;  7-FEB-92 mk      1.0   Initial release.
;;; 10-FEB-92 mk      1.1   Pre-release corrections and additions.
;;; 10-FEB-92 mk      1.11  Minor changes from Arun Welch, Mitch Marks, 
;;;			    Mike Meyer, Matthias Felleisen, and John Gateley.
;;; 11-FEB-92 mk      1.12  Corrections by John Carroll, Jason Trenouth, Joel
;;;			    Riedesel, David Neves, Lawrence Mayka and
;;;			    Bruce Miller.
;;; 13-FEB-92 mk      1.13  Renumbering. Split into 3 files. Some more FAQs.
;;; 23-MAR-92 mk      1.14  Updated various FTP entries, bug in EXPLODE.
;;;			    Updated harlequin entry.
;;; 25-MAR-92 mk      1.15  Added question [2-18]: saving data and CLOS
;;;			    instances to disk for later retrieval.
;;;  1-MAY-92 mk      1.17  Added entry for Feel to question [1-5]. Updated CMU
;;;			    ftp machines to point to ftp.cs.cmu.edu. Fixed CMU
;;;			    CL entry to be approximately version independent.
;;;                         Revised entry on Garnet. uunet.uu.net -> ftp.uu.net
;;; 12-MAY-92 mk      1.18  Split questions 1-5, 1-6, and 1-7 into part 4,
;;;                         which is now cross-posted to comp.lang.scheme, and
;;;                         questions 1-8, 2-3, 2-9 and 2-18 into part 5 which
;;;                         is now cross-posted to comp.lang.clos.
;;;                         Added detail to Norvig entry in 1-1.
;;;                         Updated entries for several Lisp implementations.
;;; 26-MAY-92 mk      1.19  Changed 5-2 on the basis of comments by Jeff Greif.
;;; 29-MAY-92 mk      1.20  Added question [2-17] about lisp sockets.
;;; 16-JUN-92 mk      1.21  Moved the question about object oriented
;;;                         programming references to part 5 of the FAQ.
;;;                         Entry on Dylan. Addition to MIT Scheme entry
;;;                         regarding Schematik.
;;; 22-JUN-92 mk            Updated SOAR entry.
;;; 24-JUN-92 mk            Fixed MCL entry to note that CLIM is available 
;;;                         from ILA, not via Apple.
;;; 25-JUN-92 mk      1.22  Added question [2-18].
;;; 17-JUL-92 mk            Added entry on PSD (Portable Scheme Debugger).
;;; 20-JUL-92 mk            Updated entry on T3.1
;;; 30-JUL-92 mk            Added entry on XIT to question 2-2.
;;;  3-AUG-92 mk            Updated PC-Scheme entry (bought by Ibuki).
;;;  6-AUG-92 mk      1.23  Merged in Jeff Dalton's pitfalls list.
;;; ------------------------------------------------------------

;;; *EOF*
Newsgroups: comp.lang.lisp