Am Di., 12. Jan. 2021 um 19:55 Uhr schrieb Wolfgang Corcoran-Mathe <xxxxxx@sigwinch.xyz>:
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.

If I remember correctly, Oleg's arguments against call/cc are not related to what we have been discussing. Oleg says that there should only be delimited continuations. They have a better space complexity than unbounded continuations. Implementing them time-efficiently is, however, not easier than to implement ordinary call/cc. In fact, it seems harder.
 
> >     (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!

Whether something is called in tail position can be detected through the SRFI 157 continuation marks. The idea is that if I use `with-immediate-continuation-mark` around a call of `*-search` that the `success` and `failure` continuations must see it when they are called.

This is what is meant by tail-calling `success` or `failure` in SRFI 146. (It would have been clearer, and may call for a PFN, had I added "with respect to the original call to `mapping-search`.)
 
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.

Apparently, I didn't update my sample implementation fully after the tail-call guarantees have been added to SRFI 146 in a later draft. When we have resolved everything in this discussion, I will have to revise the SRFI 146 sample implementation.

Thanks for catching this!

Marc