Subject: Re: The empty list and the end of a list
From: rpw3@rpw3.org (Rob Warnock)
Date: Mon, 21 Apr 2008 21:40:21 -0500
Newsgroups: comp.lang.lisp
Message-ID: <1cmdna1MK_iIzZDVnZ2dnUVZ_vyinZ2d@speakeasy.net>
Gene <eugene.ressler@frontiernet.net> wrote:
+---------------
| Tail consing is adding new list elements in sequence by destructively 
| modifying the cdr of the last cons.  It's efficient, but the code to
| make it work is more complex than your append solution.
+---------------

True, but most LOOP implementations do tail-consing for the COLLECT
clause when they can, so if you can cast your task into LOOP's COLLECT
syntax the performance is often quite good. E.g., in CMUCL [I'm using
WALKER:MACROEXPAND-ALL here since plain MACROEXPAND leaves a bunch of
internal macros unexpanded]:

    > (walker:macroexpand-all
	'(loop for item in list
	    when (plus item)
	      collect item))

    (BLOCK NIL
      (LET ((ITEM NIL) (#:G1583 LIST))
	(DECLARE (TYPE LIST #:G1583))
	(LET* ((#:G1584 (LIST NIL)) (#:G1585 #:G1584))
	  (TAGBODY
	   ANSI-LOOP::NEXT-LOOP
	    (IF (ENDP #:G1583)
		(PROGN
		  NIL
		  (GO ANSI-LOOP::END-LOOP))
		NIL)
	    (SETQ ITEM (CAR #:G1583))
	    (SETQ #:G1583 (CDR #:G1583))
	    (IF (PLUS ITEM) (RPLACD #:G1585 (SETQ #:G1585 (LIST ITEM))))
	    (GO ANSI-LOOP::NEXT-LOOP)
	   ANSI-LOOP::END-LOOP
	    (RETURN-FROM NIL (CDR #:G1584))))))
    > 

Note the tail-consing in the 4th line from the bottom.


-Rob

-----
Rob Warnock			<rpw3@rpw3.org>
627 26th Avenue			<URL:http://rpw3.org/>
San Mateo, CA 94403		(650)572-2607