call-in-continuation and immediate continuation marks

[mnieper]

Consider the following expression:

(call/cc
  (lambda (k1)
    (call-in-continuation k1
      (lambda ()
        (call/cc
          (lambda (k2)
            (eqv? k1 k2)))))))

It evaluates to #t, which reflects the fact that the last expression of the thunk argument to call-in-continuation is evaluated in the continuation of the whole expression.

This, however, is not reflected by the implementation of immediate continuation marks. Consider:

(with-continuation-mark 'key 'tail
  (call/cc
    (lambda (k1)
      (call-with-immediate-continuation-mark 'key values))))

This expression evaluates to tail, which reflects the fact that key is part of the immediate table of marks of the continuation of the whole expression.

Now consider:

 (with-continuation-mark 'key 'tail
    (call/cc
      (lambda (k1)
        (call-in-continuation k1
          (lambda ()
            (call-with-immediate-continuation-mark 'key values))))))

In the current implementation of continuation marks, this evaluates to #f. In other words, the implementation of call-with-immediate-continuation-mark fails to deliver the immediate marks of the continuation to the call of the thunk argument to call-in-continuation.

[mflatt]

That's the intended behavior. The documentation of call-in-continuation notes that it restores the continuation with an empty immediate mark frame. To support a different choice, call-in-continuation accepts a second argument; using that second argument on the restore side normally means pairing call/cc with current-continuation-marks on the capture side.

Your example partly illustrates why it's implemented and (intended to be) defined the way it is in Chez Scheme. If a captured continuation includes immediate marks, then nested call/ccs do not produce eq? values, or else with-continuation-mark is an effectful operation that can change previous captured continuations.

Racket makes s different choice here. Nested call/ccs do not produce eq? values. Instead, call/cc (and similar) is implemented with call/cc and current-continuation-marks (essentially) at that the Chez Scheme level, and call-in-continuation takes one argument but turns into a two-argument call to Chez Scheme's call-in-continuation. But changing Chez Scheme itself to do something like that would have imposed some combination of cost and changed behavior on existing Chez Scheme programs.

[mnieper]

Thanks for pointing out the particular behaviour of call-in-continuation. I used it in my example primarily to demonstrate the presence or, rather, non-presence of immediate marks on the captured continuation. As you point out, it is not supposed to work in a way that it can be used for that purpose.

From the way the documentation on continuation marks in the CSUG is written, I have read it in a way that the immediate continuation marks are part of the continuation that is reified by call/cc. In that case, it should have been reflected in continuation equality, which is exposed through eqv?.

You write that with-continuation-mark would have to be an effectful operation. Wouldn't it be possible to just change the link to the underflow record if the return address marks the underflow handler and if the stored table of immediate continuation marks is not the same as the current one? This would create a new continuation frame but would not overwrite the existing one. (It may be a problem that equality checking for immediate continuation marks might become expensive because a trivial eq? probably does not have the right semantics.)

That said, I think it is probably best to just leave the implementation and semantics as they are and as they have been intended. In that case, I would like to make two suggestions:

1. Amend the documentation so that the immediate continuation mark table is no longer conceptionally part of the continuation that is reified. Instead, it behaves more like a thread-local variable.
2. Add a continuation=? primitive that is initially just eq? for continuation procedures but prominently documented. Should the model of continuations need later amendments, it will be easier to incorporate it into a dedicated procedure continuation=?. Moreover, it fits better with R6RS, where procedure equality using eq? is mostly undefined.

If you think 1. and 2. are a good idea, I can make a suggestion as a pull request.

PS I still think that Chez should get some primitives for delimited continuations. I would be willing to implement or help to implement them, but I would like to discuss strategies/the API first. It may make sense to implement it in a way so that parts of Racket's rumble/control.ss can be moved into Chez Scheme proper.

What should probably be avoided is wrapping native continuations into structures as it is done in control.ss. The fields referencing a metacontinuation, etc., should be part of the native continuation record. What is to be done with Chez's current dynamic-wind support also needs to be discussed; Racket does not seem to use it.

[mflatt]

I think we're mostly on the same page here, but to check:

• If call/cc captured marks on the immediate frame as well as the rest of the continuation, then capturing a continuation with different marks should not produce eq? values or equal? values. There could be a continuation=? comparison operator that checked whether two continuations are the same ignoring marks, and that could replace current uses of eq?. Or maybe some of those current uses really should be equal? in that world, because they'd want to check for the same marks, too.
• To implement that extra capturing by call/cc, there would need to be more allocation somewhere. It could be that with-continuation-mark allocates something that pairs the continuation frame with the new mark, or it could be that call/cc pairs the (otherwise) continuation with immediate marks.
• The current implementation is a way of side-stepping this question. By not delivering the immediate frame's marks with the continuation, it doesn't have to perform extra allocation in either with-continuation-mark or call/cc to pair those things, and a program that wants those can pair itself. The implementation is in some sense optimized to call/cc with continuation invoked by applying them, in which case marks on the immediate continuation frame would be immediately discarded, anyway.

Assuming we're on the same page that far, I don't think it helps to describe the immediate table as thread-local. Then you have o specify more machinery about how the table gets attached to extensions of the continuation as a new one is created, and so on — closer to the implementation, but less clear as a model. I grant that the behavior of call/cc is a little surprising with respect to marks, and better explanations are always a good idea, but it still seems cleanest to me to describe it as a shortcut and limitation of call/cc, instead of changing the model to make the current call/cc more natural.

I agree that there are better ways to build a delimited-continuation layer on top of Chez Scheme's existing functionality. I think the dynamic-wind stack could be replaced by marks, for example, and I have prototyped that direction a couple of times. The reason I didn't go further with the prototype is just figuring out how much of the Racket layer's mark-table representation to replicate; it relies on persistent maps (as HAMTs) to implement some lookups that are meant to be effectively constant-time, but I'm not sure how much those matter, or whether it would be worth having persistent maps in Chez Scheme, anyway, and so on.

[mnieper]

[...]

Assuming we're on the same page that far, I don't think it helps to describe the immediate table as thread-local. Then you have o specify more machinery about how the table gets attached to extensions of the continuation as a new one is created, and so on — closer to the implementation, but less clear as a model. I grant that the behavior of call/cc is a little surprising with respect to marks, and better explanations are always a good idea, but it still seems cleanest to me to describe it as a shortcut and limitation of call/cc, instead of changing the model to make the current call/cc more natural.

This makes a lot of sense to me. Changing the continuation machinery before thinking of how to potentially implement delimited continuations in Chez doesn't seem worth the effort because delimited continuations will likely need their own share of changes.

What do you think of replacing (in the CSUG)

When a continuation is captured with call/cc, only the marks of the rest of the continuation are captured, and continuation-next-marks returns the captured marks.

by something like

The procedures call/cc and call/1cc (see below) do not, in spite of their names, capture the (full) current continuation but only the current continuation stripped from the immediate table of marks. In other words, only the marks of the rest of the continuation are captured, and continuation-next-marks returns the captured marks.

I have to fix the guard form, which uses call-in-continuation and which does yet not restore the immediate mark table.

I agree that there are better ways to build a delimited-continuation layer on top of Chez Scheme's existing functionality. I think the dynamic-wind stack could be replaced by marks, for example, and I have prototyped that direction a couple of times. The reason I didn't go further with the prototype is just figuring out how much of the Racket layer's mark-table representation to replicate; it relies on persistent maps (as HAMTs) to implement some lookups that are meant to be effectively constant-time, but I'm not sure how much those matter, or whether it would be worth having persistent maps in Chez Scheme, anyway, and so on.

The current implementation of marks in Chez does not use a HAMT either but a cache, which may have worse algorithmic complexity. Maybe we can work in steps. If delimited continuations are moved to the core of Chez, Racket does not need to use them directly but only after HAMTs have been implemented at a later step so that the situation for Racket does not worsen. Implementing HAMTs for Chez independently makes sense in my opinion because implementing them portably is problematic when the key is eq? or eqv? based.