plogan@mentor.com (Patrick Logan) (09/05/90)
I see a lot of LISP code building lists backwards and then reversing
them. I don't know if I've ever seen any C code doing that. Is it too
easy to write sloppy code in LISP? I don't think it is any more
difficult to write efficient list manipulations in Scheme than it is
in C.
Here is a procedure (in Scheme) that copies a list by adding items to
the end of a list and then returns that list. This isn't taught in the
Little LISPer, but it's not beyond the typical C programmer's
abilities.
(define (COPY-LIST lis)
(let ((header (cons #f '()))) ; Ignore the #f, build the list in the cdr.
(let loop ((tail header) (lis lis))
(if (null? lis)
(cdr header)
(begin (set-cdr! tail (cons (car lis) '()))
(loop (cdr tail) (cdr lis)))))))
Here is an "object" that responds to two messages. For the cost of
building a closure of a few words in size, it abstracts the code for
adding items to the end of a list.
Messages:
((object 'EXTEND!) item) ....... Add item to the end of the list.
(object 'LIST) ................. Return the list.
Scheme->C -- 23feb90jfb -- Copyright 1989 Digital Equipment Corporation
> (define (MAKE-TAIL-LIST)
(let* ((head (cons #f '())) ; Ignore the #f, use for tail-cons'ing.
(tail head))
(lambda (msg)
(case msg
((extend!)
(lambda (item)
(let ((new-tail (cons item '())))
(set-cdr! tail new-tail)
(set! tail new-tail))))
((list) (cdr head))))))
MAKE-TAIL-LIST
> (define a (make-tail-list))
A
> (a 'list)
()
> ((a 'extend!) 1)
(1)
> ((a 'extend!) 2)
(2)
> ((a 'extend!) 3)
(3)
> (a 'list)
(1 2 3)
--
Patrick Logan, uunet!mntgfx!plogan
Mentor Graphics Corp. 8500 SW Creekside, Beaverton, Oregon 97005-7191plogan@mentor.com (Patrick Logan) (09/05/90)
I don't know exactly what the point of your message was. Was it meant to be a
friendly recommendation to non-expert lisp programmers?
Yes. LISP has a reputation of being inefficient, this is historically
true but not so true of many current implementations. What is true
today is that many programmers, many who have used LISP extensively,
do very inefficient things in LISP. These are things the same
programmers would probably never do in C.
Or what is a question of the sort `what do people do when they want to add
to the end of a list'?
No, but that's a reasonable misinterpretation. Comments are welcome.
...functions like TCONC...without putting in your loop the code for keeping
track of the tail.
This is essentially what the "object" does in the second example in my
original message. It maintains the head and the tail abstractly, which
IMO is even better than using TCONC (which keeps the head in the car
and the tail in the cdr of a pair, in Franz?).
--
Patrick Logan, uunet!mntgfx!plogan
Mentor Graphics Corp. 8500 SW Creekside, Beaverton, Oregon 97005-7191krulwich@ils.nwu.edu (Bruce Krulwich) (09/06/90)
plogan@mentor (Patrick Logan) writes: >I see a lot of LISP code building lists backwards and then reversing >them. I don't know if I've ever seen any C code doing that. Is it too >easy to write sloppy code in LISP? It's more complicated than that. In and of itself it's more efficient to construct a list backwards, because a good compiler can use register operations instead of memory operations (in T under Orbit, for example, this makes a big difference). In the cases when you don't have to do the reversal (say, order doesn't matter, or you can keep it reversed for a while) it's better to do it backwards. Obviously, the reversal cost probably outweighs the gains in register op's, so in general you're right if you have to do the reversal, but it's not as simple as you say. >Here is a procedure (in Scheme) that copies a list by adding items to >the end of a list and then returns that list. > >(define (COPY-LIST lis) > (let ((header (cons #f '()))) ; Ignore the #f, build the list in the cdr. > (let loop ((tail header) (lis lis)) > (if (null? lis) > (cdr header) > (begin (set-cdr! tail (cons (car lis) '())) > (loop (cdr tail) (cdr lis))))))) You can make this a bit better (getting rid of the wasted HEADER CONS cell) by special casing the (NULL? lis) case and then starting off header with the copy of the first element: (define (COPY-LIST lis) (if (null? lis) nil (let ((header (list (car lis)))) (let loop ((tail header) (lis (cdr lis))) (if (null? lis) header (begin (set-cdr! tail (cons (car lis) '())) (loop (cdr tail) (cdr lis)))))))) Bruce Krulwich Institute for the Learning Sciences
briscoe-duke@cs.yale.edu (Duke Briscoe) (09/06/90)
In article <1990Sep5.011910.1177@mentor.com> Patrick Logan writes: >I see a lot of LISP code building lists backwards and then reversing >them. I don't know if I've ever seen any C code doing that. Is it too >easy to write sloppy code in LISP? I don't think it is any more >difficult to write efficient list manipulations in Scheme than it is >in C. > I did some timings on compiled T code, and the difference between copying a list using your copy-list function and using a function (define (dcl lis) (reverse! (reverse lis))) was only 20%, the important thing being that this is an algorithmic difference of a small constant factor. The reverse functions in T are coded in T, not hand-coded assembly by the way. If the operations used to build the elements of the list are expensive (just copying the elements is the least expensive thing I can think of) then the reverse! step is going to make relatively less of a percentage difference. I think in many cases there isn't going to be much difference. If someone is using reverse instead of reverse! then that could be more serious because of the extra consing. I think the important thing is that the standard functions be coded efficiently, but for most user applications a person doesn't need to get involved with potentially tricky pointer manipulations. Duke
iam@Gang-of-Four.Stanford.EDU (Ian Mason) (09/06/90)
i am not sure i understand the point of the posting.
it is just as easy to write a tail recursive version
of copy-list that conses onto the front, and the
trick of course generalizes to the usual list
recursion. since i am not fluent in scheme here it is
in vanila lisp
(defun copylist (l)
(if (null l)
l
(let ((w (cons (car l) (cdr l))))(loop (cdr l) w w))))
(defun loop (x y z)
(if (null x) z (let ((w (cons (car x) (cdr x))))
(progn (rplacd y w)(loop (cdr x) w z)))))
a correctness proof can be found in "science of computer
programming 10 1988 177-210"
-iam- jeff@aiai.ed.ac.uk (Jeff Dalton) (09/06/90)
In article <1990Sep5.011910.1177@mentor.com> plogan@mentor.com (Patrick Logan) writes: >I see a lot of LISP code building lists backwards and then reversing >them. I don't know if I've ever seen any C code doing that. Is it too >easy to write sloppy code in LISP? I don't think it is any more >difficult to write efficient list manipulations in Scheme than it is >in C. How soon they forget. What do you think `tconc' (Interlisp, Franz Lisp, etc.) was for? For a more modern approach, look at Appendix B, "Generators and Gatherers" in Guy Steele Jr.'s CLtL II. (It's similar to your object-oriented technique.) -- Jeff
jjacobs@well.sf.ca.us (Jeffrey Jacobs) (09/07/90)
> tconc
Thanks! I was about to post that, coupled with a righteous flame
about just how low the LISP community has sunk!
Jeffrey M. Jacobs
ConsArt Systems Inc, Technology & Management Consulting
P.O. Box 3016, Manhattan Beach, CA 90266
voice: (213)376-3802, E-Mail: 76702.456@COMPUSERVE.COMlgm@cbnewsc.att.com (lawrence.g.mayka) (09/07/90)
In article <3372@skye.ed.ac.uk>, jeff@aiai.ed.ac.uk (Jeff Dalton) writes: > In article <1990Sep5.011910.1177@mentor.com> plogan@mentor.com (Patrick Logan) writes: > >I see a lot of LISP code building lists backwards and then reversing > >them. I don't know if I've ever seen any C code doing that. Is it too > >easy to write sloppy code in LISP? I don't think it is any more > >difficult to write efficient list manipulations in Scheme than it is > >in C. > > How soon they forget. What do you think `tconc' (Interlisp, > Franz Lisp, etc.) was for? > > For a more modern approach, look at Appendix B, "Generators and > Gatherers" in Guy Steele Jr.'s CLtL II. (It's similar to your > object-oriented technique.) The "Series" of Appendix A are often useful here too, as well as old standbys like MAPCAR. Otherwise, I use the COLLECT keyword of the new expanded LOOP macro. Lawrence G. Mayka AT&T Bell Laboratories lgm@iexist.att.com Standard disclaimer.
eliot@phoenix.Princeton.EDU (Eliot Handelman) (09/12/90)
In article <1990Sep5.155100.1264@mentor.com> plogan@mentor.com (Patrick Logan) writes:
;This is essentially what the "object" does in the second example in my
;original message. It maintains the head and the tail abstractly, which
;IMO is even better than using TCONC (which keeps the head in the car
;and the tail in the cdr of a pair, in Franz?).
No, it kept the whole list in the car and the last cons in the cdr.