iset-search implementations Wolfgang Corcoran-Mathe (08 Dec 2020 20:01 UTC)
Re: iset-search implementations Marc Nieper-Wißkirchen (08 Dec 2020 20:18 UTC)
Re: iset-search implementations Wolfgang Corcoran-Mathe (09 Dec 2020 18:07 UTC)
Re: iset-search implementations Marc Nieper-Wißkirchen (10 Dec 2020 12:00 UTC)
Re: iset-search implementations Arthur A. Gleckler (10 Dec 2020 16:40 UTC)
Re: iset-search implementations Marc Nieper-Wißkirchen (10 Dec 2020 16:50 UTC)
Re: iset-search implementations Arthur A. Gleckler (10 Dec 2020 16:52 UTC)
Re: iset-search implementations John Cowan (11 Dec 2020 02:24 UTC)
Re: iset-search implementations Wolfgang Corcoran-Mathe (11 Dec 2020 02:47 UTC)
Re: iset-search implementations John Cowan (11 Dec 2020 03:05 UTC)
Re: iset-search implementations Wolfgang Corcoran-Mathe (11 Dec 2020 18:41 UTC)
Re: iset-search implementations Marc Nieper-Wißkirchen (12 Dec 2020 10:59 UTC)
Re: iset-search implementations Wolfgang Corcoran-Mathe (14 Dec 2020 17:44 UTC)
Re: iset-search implementations John Cowan (16 Dec 2020 15:34 UTC)
Re: iset-search implementations Marc Nieper-Wißkirchen (16 Dec 2020 15:42 UTC)
Re: iset-search implementations Wolfgang Corcoran-Mathe (31 Dec 2020 18:23 UTC)
Re: iset-search implementations John Cowan (07 Jan 2021 21:42 UTC)
Re: iset-search implementations Arthur A. Gleckler (08 Jan 2021 04:40 UTC)
Re: iset-search implementations Marc Nieper-Wißkirchen (08 Jan 2021 13:32 UTC)
Re: iset-search implementations Wolfgang Corcoran-Mathe (08 Jan 2021 23:47 UTC)
Re: iset-search implementations Marc Nieper-Wißkirchen (09 Jan 2021 13:28 UTC)
Re: iset-search implementations Wolfgang Corcoran-Mathe (10 Jan 2021 23:35 UTC)
Re: iset-search implementations Arthur A. Gleckler (11 Jan 2021 00:05 UTC)
Re: iset-search implementations Marc Nieper-Wißkirchen (11 Jan 2021 06:33 UTC)
Re: iset-search implementations Wolfgang Corcoran-Mathe (11 Jan 2021 00:28 UTC)
Re: iset-search implementations Marc Nieper-Wißkirchen (12 Jan 2021 14:34 UTC)
Re: iset-search implementations Wolfgang Corcoran-Mathe (12 Jan 2021 18:55 UTC)
Re: iset-search implementations Marc Nieper-Wißkirchen (18 Jan 2021 09:13 UTC)
Re: iset-search implementations Wolfgang Corcoran-Mathe (19 Jan 2021 18:54 UTC)
Re: iset-search implementations Marc Nieper-Wißkirchen (20 Jan 2021 10:53 UTC)
Re: iset-search implementations Wolfgang Corcoran-Mathe (21 Jan 2021 20:31 UTC)
Re: iset-search implementations Marc Nieper-Wißkirchen (11 Dec 2020 08:40 UTC)

Re: iset-search implementations Marc Nieper-Wißkirchen 12 Jan 2021 14:34 UTC

Am Mo., 11. Jan. 2021 um 00:35 Uhr schrieb Wolfgang Corcoran-Mathe
<xxxxxx@sigwinch.xyz>:
>
> Thanks for your thoughts.

And thanks for your thoughts.

> I may be wrong about this, but it seems that using *-search to,
> well, search for an element will consume O(n) space when traversing
> most recursive structures, with or without call/cc.  As perhaps the
> simplest possible example, consider this version of *-search for
> list-sets:
>
>     (define (lset-search lis key failure success)
>       (letrec
>        ((search
>          (match-lambda
>            (()
>             (failure (lambda (obj)  ; insert
>                        (values `(,key) obj))
>                      (lambda (obj)  ; ignore
>                        (values '() obj))))
>            ((x . xs)
>             (if (eqv? x key)
>                 (success key
>                          (lambda (new obj)  ; update
>                            (values (cons new xs) obj))
>                          (lambda (obj)      ; remove
>                            (values xs obj)))
>                 (let-values (((xs* obj) (search xs)))  ; recur
>                   (values (cons x xs*) obj)))))))
>
>         (search lis)))

That is a very good point and one that I failed to consider. Indeed,
while we may skip the `cons` with call/cc, the stack will nevertheless
grow.

Whether we see this as detrimental or not, depends on our view of the
computation model of Scheme. If we want call/cc to be as fast as
possible in a Scheme system, the most obvious solution (and the only
clear one I know) is to CPS-transform the whole program, which
amalgamates the stack with the heap. With such a model, every
(non-optimized) procedure call, whether a tail-call or not, leaves a
frame on the stack, so iteration and recursion become somewhat
equivalent. (Think of Chicken without optimizations as an example.)

> An lset-contains?  procedure implemented in terms of a call/cc-wrapped
> lset-search will accumulate frames through recursive `search' calls.
> Sure, this garbarge will probably be reclaimed quickly, but we can
> avoid creating it entirely by using tail recursion.  It's precisely
> the same situation we'd have if we used fold-right or direct recursion
> instead, things that most functional programmers try to avoid when
> implementing a simple `contains?' function.

Please note that your above code is not a faithful implementation of
the *-search procedure. According to (at least) SRFI 146, it has to
call the `success` and the `failure` continuations in tail position,
which your code does it. What would the best, corrected version of
your `lset-search` be?

> I'd point to this as an example of why *-search is not, in general,
> a prudent way to implement some other core procedures.
>
> In any case, this is tangential to the main point.  I like John's
> PFN text, since I think it allows a choice of approaches.

As far as standardization goes, I don't think that it is that helpful
(unless we agree on (c)). If I want to write portable code (which is
one of the basic ideas of SRFIs), it doesn't help "if the
implementation can choose" because I would have to work with a common
denominator.

Marc