Re: remove all occurence of list

Lauri Alanko wrote:
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.

Any half-decent implementation of a [semi-]functional programming
language must handle stack overflow gracefully. If recursion is to be
discouraged based on a flaw in some implementations, we might as well do
for-loops in C.

Moreover, the size of the stack in many recursive functions may use just
as much memory as a linked list. For example, in a recursive definition
of reverse, every frame would hold exactly one word plus a return point.

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.

If a continuation is captured in the iterative implementation, the wrong
answer may be returned (as in shared sublists).

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.

Actually, decent implementations would return the multiple values in
machine registers (or as many as could be passed in registers) before
touching the stack.

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.

I don't mind his approach given that an efficient strategy for returning
multiple values has been around for a long time. Implementors have
no execuse for not utilizing it.

Aziz,,,

@inproceedings{156784,
author = {J. Michael Ashley and R. Kent Dybvig},
title = {An efficient implementation of multiple return values in
Scheme},
booktitle = {LFP '94: Proceedings of the 1994 ACM conference on LISP
and functional programming},
year = {1994},
isbn = {0-89791-643-3},
pages = {140--149},
location = {Orlando, Florida, United States},
doi = {http://doi.acm.org/10.1145/182409.156784},
publisher = {ACM Press},
address = {New York, NY, USA},
}

Avaliable online at:
http://www.cs.indiana.edu/~dyb/pubs/mrvs.pdf
.

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. ... I note that the reference implementation for SRFI-1 uses the ...
    (comp.lang.scheme)
  • Re: yield in Forth
    ... the version that prints the words in reverse need a stack of somewhat ... bad-old days of 64K computers for the purpose of saving memory. ... use an intermediate data structure (such as my lists), ...
    (comp.lang.forth)
  • 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: using MISC (post 1987 Forth hardware) opcodes
    ... words to naively sum the integers from 1 to the first element on the stack. ... Instead of "recurse" it uses the definitions name, ... Push and process. ... An environment with six cell stacks cannot traverse this data structure ...
    (comp.lang.forth)
  • Elegant code Was: Re: what kind of non microconroller app are done in forth?
    ... OVER R@ EXECUTE WHILE ... good way to do this without locals. ... can handle 3 stack items. ... /STRING R> RECURSE ...
    (comp.lang.forth)