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 Wolfgang Corcoran-Mathe 12 Jan 2021 18:55 UTC

On 2021-01-12 15:34 +0100, Marc Nieper-Wißkirchen wrote:
> 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.)

This is an important issue with serious implications for using
call/cc generally.  I suppose we have to assume an efficient system
like the one you've described; without this, the inefficiencies that
Oleg Kiselyov writes about in
http://okmij.org/ftp/continuations/against-callcc.html seem
unavoidable.

> >     (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)))
>
> 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?

Thanks for raising this point.  Initially I thought "oops!", but now
I wonder if there isn't some ambiguity in the specification here.
If we consider the example above, it is clear that the calls to
`failure' and `success' are indeed in tail position, assuming that
match-lambda is correctly implemented.  These calls may, of course,
occur at the bottom of the recursion; but, then again, so may any
tail-call!

Examining the tree-search procedure from SRFI-146, it seems to do
precisely the same thing, allowing for structural differences.
Here's the recursive case:

> (let search ((tree (redden tree)))
>   (tree-match tree
>     ; ...
>     ((and t (node c a x b))
>      (let ((key (item-key x)))
>        (comparator-if<=> comparator obj key
>
>          (receive (a ret op) (search a)
>            (values (op (node c a x b)) ret op))
>
>          (success
>           key
>           (item-value x)
>           ;; update
>           (lambda (new-key new-value ret)
>             (values (node c a (make-item new-key new-value) b)
>                     ret
>                     identity))
>           ;; remove
>           (lambda (ret)
>              ; ... misc. tree bookkeeping
>              ret
>              rotate)))
>
>          (receive (b ret op) (search b)
>            (values (op (node c a x b)) ret op)))))))

Here too, `success' is tail-called, but `search' must be called
(non-tail-) recursively.

If this somehow avoids the issues you've mentioned with the simple
list example, please let me know how, as I'll need to make changes
to the SRFI 217 implementation.  I'd like some clarification on the
intentions of this particular detail of the *-search procedure.

--
Wolfgang Corcoran-Mathe  <xxxxxx@sigwinch.xyz>

"If one is searching for a needle in a haystack, look in the part
of the haystack that contains more needles." --Bird & Wadler