Fwd: Some ramblings about continuation marks Marc Nieper-Wißkirchen 23 Jun 2023 06:23 UTC

---------- Forwarded message ---------
Von: Marc Nieper-Wißkirchen <xxxxxx@gmail.com>
Date: Mi., 14. Juni 2023 um 07:50 Uhr
Subject: Re: Some ramblings about continuation marks
To: Chris Hanson <xxxxxx@chris-hanson.org>

Dear Chris,

Thanks for discussing this SRFI.

Please note that this SRFI was merged into the much more comprehensive
SRFI 226, but that should not touch the points you make here.

Am Di., 13. Juni 2023 um 23:51 Uhr schrieb Chris Hanson <xxxxxx@chris-hanson.org>:
>
> 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.

This is great news! I am looking forward to see continuation marks in
MIT/GNU Scheme.

> Let me prefix the following by saying that I'm not asking for the SRFI
> to be changed.  I'm simply looking for some clarity and discussion
> about the choices.  Perhaps a future alternative SRFI may come of
> this, if there's anything worthwhile here.
>
> 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.

I didn't find it confusing but that's very subjective, of course. You
may want to take a look at SRFI 226, which implements the whole thing
without a FLAG value.

> 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.

To test your model, you can check the following questions:

1. Does nesting of WITH-CONTINUATION-MARK work as intended if
WITH-CONTINUATION-MARK is evaluated in tail position with respect to
an outer WITH-CONTINUATION-MARK it has to work on the same from?
2. Can CALL-WITH-IMMEDIATE-CONTINUATION-MARK be implemented?
3. Does WITH-CONTINUATION-MARK uphold its tail call guarantee?

The most efficient model to implement continuation marks is, in my
opinion, the following: The current mark set (what is retrieved by
CURRENT-CONTINUATION-MARKS) is stored in a thread-local variable. When
WITH-CONTINUATION-MARK is evaluated, a special return address together
with the then current mark set and the actual return address is pushed
on the stack and the current mark set then (non-destructively)
updated. When code reaches the special return address, the current
mark set is restored and code jumps to the actual return address. Now,
if WITH-CONTINUATION-MARK already finds the special return address at
the top of the stack, no new special frame is pushed on the stack.
(This implements tail-call guarantees).
CALL-WITH-IMMEDIATE-CONTINUATION-MARK tests for the special return
address at the top of the stack to see whether the latest continuation
marks in the current mark come from an immediately enclosing
WITH-CONTINUATION-MARK.

> 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 don't understand your point here; the effect of
WITH-CONTINUATION-MARK is only visible during the dynamic extent of
the form enclosed. Once evaluation is done with the
WITH-CONTINUATION-MARK form, the previous mark set is restored. So,
WITH-CONTINUATION-MARK works like WITH-INPUT-FROM-FILE (with the
difference that the latter takes a thunk, but this is a superficial
difference).

Can you give a short code snippet to demonstrate what you mean?

> 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.

This is historic baggage from Racket and earlier papers introducing
continuation marks. I agree with you that the terminology is not as
simple as it could have been. The part "marks" and "mark-set" mean the
same but sometimes the former, sometimes the latter is used in
identifiers. Before this becomes part of a future RnRS, one should
debate whether to stick with the established names or whether to get
rid of either "marks" or "mark-set".

The procedure CONTINUATION-MARK-SET->LIST* takes one continuation mark
set and returns one list of vectors, so a naming like
CONTINUATION-MARK-SETS->LIST would be wrong.

> Again, I'd appreciate hearing feedback about this.

Thanks again for getting a good look at it.

Marc

>
> Thanks,
> Chris