Hi,

>
> I've been learning about continuation marks so that I can implement
> them in MIT/GNU Scheme, and I've run across some things I'd like to
> discuss.  There are two things: the first is my understanding of the
> underlying model, which seems to be different from the one presented;
> the second is some quirks about the interface.
>

I just read this SRFI for the first time, and I don't consider myself an
expert on the semantics of continuation marks, but I happened to hear of
your message in a Racket chat, and I mostly wanted to suggest asking on
<https://racket.discourse.group>: many people there are more qualified
than I am to answer, including John Clements and Matthew Flatt, who
invented continuation marks, and Jay McCarthy, who advised the master's
thesis setting out the implementation strategy in the SRFI sample code.

>
> 1.
>
> Trying to understand the model shown in the code was very confusing,
> mostly because of the complicated rules about the FLAG value, which is
> supposed to indicate whether the expression being evaluated is in
> tail-recursive position.  In the process, I came up with an
> alternative model in which the flag is unnecessary.
>
> In the alternative model, the MARKS value is a list of frames, as in
> the example code.  Each mark frame is the mark set of the
> corresponding continuation frame.  When a continuation frame is
> created, it contains the value of MARKS at that point, after which
> MARKS is updated by pushing a new empty mark set at the beginning.
> When a continuation frame is invoked, MARKS is restored to the stored
> value.
>
> Now, the model I describe suffers from creating many empty frames when
> continuation marks are used sparingly, so I'd apply a simple
> optimization.  When a continuation frame is created, instead of
> changing MARKS, it is left as is.  Then, which a continuation mark is
> set, the value of MARKS is compared to the one stored in the topmost
> continuation frame, and if they're the same, a new mark frame is
> created.  This avoids creating empty mark frames, and pushes some of
> the cost onto the use of marks.
>
> This seems to me to be a very simple and valid model for continuation
> marks, but I'd like some feedback from those who've spent more time
> thinking about it than I have.
>

I have not thought sufficiently deeply about either the SRFI sample
implementation or your proposal here, but I don't see anything obviously
wrong with the basic idea. One important detail, just to be explicit, is
that "when a continuation frame is created" and "when a continuation
frame is invoked" must apply to the implicit continuation frames created
by each non-tail procedure call, not only to first-class continuations
from CALL/CC and friends. (Maybe the sample code uses the FLAG value to
track non-tail calls in CPSed code? I'd need to look more closely.)

You are right to note that adequite performance requires avoiding costs
for the many frames that don't change continuation marks.

The state-of-the-art implementation strategy for continuation marks is
used in Racket's branch of Chez Scheme (and planned to be upstreamed in
a future major version). It works by implementing an internal primitive
"continuation attachment" and adding the key--value aspect of marks as a
library. Details are in Flatt and Dybvig's PLDI 2020 paper, "Compiler
and runtime support for continuation marks"
<https://doi.org/10.1145/3395632>: there's a corresponding talk at
<https://www.youtube.com/watch?v=PiBpCmWq8yQ>.

>
> 2.
>
> As for the interface, I have two nits.  While I understand that one
> goal of this SRFI is compatibility with Racket, I think that the
> original design is flawed.
>
> First, WITH-CONTINUATION-MARK doesn't really make sense, as it misuses
> the WITH- pattern generally used in Scheme.  This pattern generally
> implies that some change is valid for a particular extent that is
> delimited by the WITH- form.  But that's not the case for
> with-continuation-mark: once the change is made, it persists past the
> end of the form until the enclosing continuation frame is invoked.  As
> such, it would make more sense to have SET-CONTINUATION-MARK! which
> more clearly indicates what's happening.  As a bonus, the latter
> syntax is simpler.
>

I think this might be a misunderstanding. WITH-CONTINUATION-MARKS only
has effect within the dynamic extent of its subform. For example, this
is #true:

    (equal? '((1) (2 1) (1))
            (map (lambda (marks)
                   (continuation-mark-set->list marks 'k))
                 (with-continuation-mark 'k 1
                   (list
                    (current-continuation-marks)
                    (with-continuation-mark 'k 2
                      (current-continuation-marks))
                    (current-continuation-marks)))))

Perhaps you are thinking of the fact that the continuation might be
captured in the dynamic extent of the subform and later restored outside
of the WITH-CONTINUATION-MARKS form. For example, this should print (1):

    (let ([saved-k #f])
      (with-continuation-mark 'x 1
        ((call/cc
          (lambda (k)
            (set! saved-k k)
            values))))
      (when saved-k
        (with-continuation-mark 'x 2
          (saved-k
           (lambda ()
             (set! saved-k #f)
             (write (continuation-mark-set->list
                     (current-continuation-marks)
                     'x))
             (newline))))))

But the same is true of other Scheme WITH- forms, as in this version of
the pervious example using WITH-EXCEPTION-HANDLER:

    #!r6rs
    (import (rnrs))
    (let ([saved-k #f])
      (with-exception-handler (lambda (e) 1)
        (lambda ()
          ((call/cc
            (lambda (k)
              (set! saved-k k)
              values)))))
      (when saved-k
        (with-exception-handler (lambda (e) 2)
          (saved-k
           (lambda ()
             (set! saved-k #f)
             (write (list (raise-continuable 'k)))
             (newline))))))

Note that the SRFI ommits the procedure CONTINUATION-MARKS, which makes
this more useful: CONTINUATION-MARKS extracts marks from a reified
continuation, so CURRENT-CONTINUATION-MARKS becomes equivalent to:

    (call/cc continuation-marks)

(The SRFI also omits CONTINUATION-MARK-SET->ITERATOR, a variant of
CONTINUATION-MARK-SET->LIST* that may have better time complexity,
especially if early termination is possible.)

>
> Second, two different names are used for the set of continuation
> marks.  The procedure CURRENT-CONTINUATION-MARKS retrieves them, and
> CONTINUATION-MARKS? tests for such an object.  But when interrogating
> the sets, CONTINUATION-MARK-SET->*** are used.  So what does the
> latter mean?  Is CONTINUATION-MARK-SET an alias for
> CONTINUATION-MARKS, or is it saying that the parameters specify a
> subset of the marks and the procedure is returning those?  And if the
> latter, it seems that the procedure CONTINUATION-MARK-SET->LIST*
> should be called CONTINUATION-MARK-SETS->LISTS.
>

The names in Racket are confusing. In Racket's branch of Chez Scheme,
names containing MARK-SET were changes to just say MARKS, since the
value in question is not a set data structure. See Racket commit
fc81924cbee7a07fe76aa1c9c2b76d0dfde8d6be or commit
2eedc888b06f6223be15cc800107d468e7dd33ef to
<https://github.com/racket/ChezScheme> for more discussion. With the
renaming, the procedure names become:

  - with-continuation-mark
  - continuation-marks?
  - current-continuation-marks
  - continuation-next-marks [Racket's continuation-marks]
  - continuation-marks-first
  - continuation-marks->list
  - continuation-marks->iterator
  - call-with-immediate-continuation-mark

Hope this helps,
Philip