iset-search implementations Wolfgang Corcoran-Mathe 08 Dec 2020 20:00 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:51 UTC
Re: iset-search implementations John Cowan 11 Dec 2020 02:23 UTC
Re: iset-search implementations Wolfgang Corcoran-Mathe 11 Dec 2020 02:47 UTC
Re: iset-search implementations John Cowan 11 Dec 2020 03:04 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:39 UTC
Re: iset-search implementations Marc Nieper-Wißkirchen 08 Jan 2021 13:31 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:04 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:27 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