Re: remove all occurence of list

In article <43E8ED61.5D7DB104@xxxxxxxxxxxxx>,
Andre <andre@xxxxxxxxxxxxx> wrote:
This statement is often repeated, but it is not necessarily true. From the
reference implementation of SRFI-1 (Olin Shivers):

;;; A note on recursion and iteration/reversal:
;;; Many iterative list-processing algorithms naturally compute the elements
;;; of the answer list in the wrong order (left-to-right or head-to-tail) from
;;; the order needed to cons them into the proper answer (right-to-left, or
;;; tail-then-head). One style or idiom of programming these algorithms, then,
;;; loops, consing up the elements in reverse order, then destructively
;;; reverses the list at the end of the loop. I do not do this. The natural
;;; and efficient way to code these algorithms is recursively. This trades off
;;; intermediate temporary list structure for intermediate temporary stack
;;; structure. In a stack-based system, this improves cache locality and
;;; lightens the load on the GC system. Don't stand on your head to iterate!
;;; Recurse, where natural.

I don't buy this. Traversing lists tail-recursively is not only an
efficiency issue, it's about limiting your stack space requirements.
Although nowadays platforms are much more flexible about the amount of
stack space available, I still don't think it's a good idea to use
stack in a linear proportion to the length of an arbitrary list.

Moreover, if the list-traversal function captures a continuation (as
is quite possible if it e.g. calls a callback that happens to call
call/cc), then the recursive approach may be much more expensive if
call/cc is implemented by copying the entire stack. If heap were used
(as in the iterative approach), then the context would be shared and
not copied automatically.

Finally, I note that the reference implementation for SRFI-1 uses the
recursive solution even when returning multiple values, resulting in
the style I just questioned in a previous post:

(define (span pred lis)
(check-arg procedure? pred 'span)
(let recur ((lis lis))
(if (null-list? lis) (values '() '())
(let ((x (car lis)))
(if (pred x)
(receive (prefix suffix) (recur (cdr lis))
(values (cons x prefix) suffix))
(values '() lis))))))

For this to be really efficient over the iterative solution, the
multiple return values should be returned directly in the stack
without doing heap allocations.

In short, Shivers' approach puts too many constraints on the
implementation for it to be useful as a general rule of thumb in
Scheme programming.


Lauri
.

Relevant Pages

  • Re: remove all occurence of list
    ... ;;; Recurse, where natural. ... Traversing lists tail-recursively is not only an ... it's about limiting your stack space requirements. ... of reverse, every frame would hold exactly one word plus a return point. ...
    (comp.lang.scheme)
  • Re: Idiom for tail recursion?
    ... describes a reference implementation in Scheme. ... the respective mutually recursive procedures does the recurse. ... doesn't grow the stack. ...
    (comp.lang.ada)
  • pHone the language, draft spec.
    ... The language phone is designed from many influences. ... Logical elements can be nested as lists using ... This leads to the next word LIT meaning literal. ... as which does symbol recall from the top of the stack. ...
    (comp.lang.misc)
  • Re: Linked List & Dynamic Memory Allocation
    ... You can't write in C or C++ without understanding the role of the stack and the heap. ... Cell * ListHead = NULL; ... Note that while C++ using MFC, STL, boost, etc. make it easy to build link lists, none of ...
    (microsoft.public.vc.mfc)
  • Re: charts
    ... PostScript somewhat difficult though. ... Both Forth and Postscript were inspired by the stack model ... novice package I provide Forth with support for lists. ... If the vectored function expects to access ...
    (comp.lang.postscript)