I am for this change.

The continuation cloning facility in Multicore OCaml has been used by researchers as a vehicle for exploring topics in effect handlers and delimited continuations. In particular, @dhil developed a multicore OCaml backend for links [1], Oleg and I developed an implementation of Eff language in Multicore OCaml [2]. Many other recent papers also use OCaml multishot continuations [3,4]. There is interest in the community for this feature [5] for exploring probabilistic programming languages and model checkers.

It was the right decision to remove support for continuation cloning from the compiler since it makes reasoning about resources difficult and breaks compiler optimizations. However, it would be useful to encourage innovation in the ecosystem. The ocaml-multicont library [6] from @dhil allows that by rebuilding the support in an external library. The PR makes it a little bit more robust.

Of course, it would be unwise to provide API stability for this feature and the runtime should be free to make any changes as it deems fit.

[1] https://dhil.net/research/papers/mlabstract2016.pdf
[2] https://arxiv.org/abs/1812.11664
[3] https://www.microsoft.com/en-us/research/publication/generalized-evidence-passing-for-effect-handlers/
[4] https://dl.acm.org/doi/pdf/10.1145/3408975
[5] https://discuss.ocaml.org/t/multi-shot-continuations-gone-forever/9072
[6] https://github.com/dhil/ocaml-multicont

This might require some advice for avoiding broken programs due to incorrect compiler optimizations. @kayceesrk Do you have any advice?

Do you have any advice?

The general advice is to avoid side-effects and linear resources in the computation closed over by the cloned continuation. Here is an example that breaks compiler optimization which converts a heap allocation to a stack allocation. Continuation cloning makes it harder to reason about programs that use linear resources. This advice is best included in the ocaml-multicont library.

Avoiding side-effects might be too strict; there is nothing wrong with printf for instance. It also seems that the conversion of a heap allocation into a stack allocation can be disabled by hand as shown in the example, it is error-prone but possible. Are there other ways to turn off this optimisation?

I'm not sure what we're aiming for with the advice. If it is crash safety, then there should be no restriction. Perhaps you may have other features in mind.

Of course, there's the challenge of ensuring that the linear resources are used linearly. But that's a "feature" of continuation cloning. For example, you may end up double-freeing a malloc'ed memory region and crash, but I would consider this to be an improper use of the linear resource, and not an issue with continuation cloning.

For the ref optimization, perhaps Sys.opaque_identity would be enough? There may be other optimizations on references that may break similar to how weak memory models breaking optimizations, but I haven't thought about this enough.

I am asking specifically about broken compiler optimisations (i.e. linearity assumptions made by the compiler), since this is not something that the programmers can guess. I think you answered my question.

I think that technically the optimisation of references relies on an escape analysis, not linearity (although maybe the two are linked ?).
Effects, and in particular continuations are messing with this by making some variables escape without any way for the compiler to notice it. Typed effects might allow for an analysis correct in presence of continuations, but they're not there. Single-shot continuations are likely fine, since from the interrupted code's point of view performing the effect should be equivalent to calling a function that may or may not return, but not knowing the implementation details I can't be sure.
I don't think it's evident that it's the optimisation that is broken here: not allocating local references has been a key feature of OCaml for a long time, so I'd consider that the expectations from the linked example are wrong. Hopefully we'll have the occasion to discuss this in depth before 5.0 is released.

In any case, passing the reference to a non-simplified function call (typically Sys.opaque_identity) will force the compiler to consider the reference as escaping, disabling the optimisation.

I think you mean that linearity of use (of the continuation) is different from linearity of reference (uniqueness), i.e. why we don't talk about linear “types”.
I agree that the program is broken, not the optimisation. So if you want a clear guideline for 5.0, it is fine to say that naked refs should be avoided.
It is going to be a bit of a bigger problem than solved by having an effect type system inform the escape analysis, because with an effect system you expect some polymorphism that lets you do fewer effects in a context that is ready to handle more effects. You cannot have such polymorphism here: whether the optimisation is done or not gives two different version of a function, and you do not want to use one instead of the other (concretely this would mean disabling the optimisation even when it is valid).

We all seem to agree that there is an issue with refs and continuation cloning. I think the compiler shouldn't attempt to give any recommendations. Such discussions and recommendations may be part of the multicont library.

Leaving this aside for the moment, and getting back to the proposed PR, do we have issues with the proposed changes of making caml_alloc_stack_noexc and caml_rewrite_exception_stack available externally?

CC @damiendoligez who has previously reviewed this code.

Is the proposed approach the best way to support resumptions (GC-handled multishot continuations) in the medium-long term?

I'm asking because the current scenario looks a bit similar to what happened in delimcc, or parts of Coq. The project starts using internal primitives for good reasons; the internal primitives were not conceived as a robust API, they happen to be on the path to the least-effort external implementation of the desired feature. But then other time the internal runtime code evolves, and the external code breaks often and needs updating, to the point that (1) it could have been more robust to design a proper API from the start, provided we had a good vision on what the feature request really was (sometimes it's hard to know because downstream projects won't really tell us).
So we start from something that looks like a simple, minimal choice, and then again and again in the following decade we are forced to work on those downstream packages to support them, and it's delicate because there are few people around with the required internal runtime knowledge and time on their hands.

Are we exposing ourselves to the same issue here? Is there a better way to do things? One advantage we have is that we have a clear specification for the downstream need: multishot continuations.

1. How much work would it be to implement (and maintain) the multishot primitives in the runtime?
2. Would it make it easier to evolve the OCaml runtime and the stack handling, easier than exposing lower-level stack primitives as proposed?

The two primitives needed for "resumptions" (multishot continuations) are:

• promote: converts a linear stack fragment (a continuation) into a GC-handled representation of the stack fragment (a resumption)
• resume: copies a resumption back into a new linear stack fragment.

Remark: currently the implementation of ocaml-multicont is not to store the resumption stack on the heap, but to have a small resumption block on-heap own point to the (linear) resu mption stack, with a finalizer attached to drop the resumption stack if the resumption becomes dead. The code is available at https://github.com/dhil/ocaml-multicont/blob/3f371bc/multicont_stubs.c, where multicont_alloc_stack_noexc and multicont_rewrite_exception_stack are local copies of the runtime primitives that are currently not exported.

In fact I think the only primitive you need (if you go all-in on the "resumption = finalized GC-managed fiber" approach) is reinstating a fiber by copy, without consuming it. Implementation-wise it is the same, but as an API this reduces the surface area and maybe it makes it easier to define expectations.

Nobody objects

Sounds good to me. I will bring the patch up to date with trunk soon.

I think there is a boarder discussion to be had about whether we should make available the rest of the fiber manipulation primitives in runtime/fiber.c too.

What do you have in mind?

I don't recall now, hehe. The fiber implementation has changed sufficiently since my comment that it probably has become dated.

Since this is a small tweak to an internal API, which would open some exploration space for experimental API,
I am planning to merge this change later today without further objections.

I would be in favor of having change entry with an explicit mention that this is an internal change aimed to experimental libraries.

Merged and cherry-picked to 5.0 in 611253d .