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