I like delimited continuations a lot. They are a fantastic tool of delicious sweetness. So I'm delighted at the idea of delimited continuations coming to GHC. I may not be very objective here. I haven't looked at the proposal for a while. But, last I checked, I found it rather convincing. I have little opinion about the implementation, which touches parts of GHC of which I know very little. But if Simon and Simon, you both find the prototype reasonable, I'll be quite happy to accept the proposal. On Mon, Nov 23, 2020 at 3:38 PM Simon Marlow <marlowsd@gmail.com> wrote:

Committee,

We have been asked to review #313: Delimited continuation primops https://github.com/ghc-proposals/ghc-proposals/pull/313

https://github.com/lexi-lambda/ghc-proposals/blob/delimited-continuation-pri...

*Summary*

The proposal makes no language changes, it only adds three primops <https://github.com/lexi-lambda/ghc-proposals/blob/delimited-continuation-primops/proposals/0000-delimited-continuation-primops.md#proposed-change-specification> .

The main motivation is to support building efficient implementations of Algebraic Effect systems, which depend on being able to efficiently capture a continuation. Currently this is done explicitly, which imposes a severe performance penalty.

These primops are the minimal support needed to be able to capture a continuation and apply it at runtime, together with some basic type safety via the PromtTag type to ensure that at least we don't replace a continuation with a computation of a different type. (there are other ways to go wrong with these primops though, they're not a safe interface by themselves: they need to be wrapped in a safe library).

The primops are implemented by copying chunks of stack into the heap. This is something that GHC's runtime already does a lot of, so it's not a new concept, although it does require a new closure type and knock-on changes across several files in the runtime (though it's mainly mechanical). There's a prototype implementation here: https://gitlab.haskell.org/lexi.lambda/ghc/-/compare/master...first-class-co...

*Decision*

I'm going to tentatively recommend acceptance.

- This is a sensible choice for the primtives, being the most general of the alternatives, as explained in the proposal. <https://github.com/lexi-lambda/ghc-proposals/blob/delimited-continuation-primops/proposals/0000-delimited-continuation-primops.md#operational-semantics> - Would the new primops impose a significant ongoing maintenance burden? Having looked at the patch, although there are some missing pieces, I don't think the new concepts impose any significant new requirements on other parts of the runtime. - I suspect there may be some difficulties around unsafePerformIO, so I raised that on the github thread <https://github.com/ghc-proposals/ghc-proposals/pull/313#issuecomment-732181948>

Thoughts?

On Sat, 12 Sep 2020 at 22:59, Joachim Breitner <mail@joachim-breitner.de> wrote:

...

Dear Committee,

this is your secretary speaking:

Delimited continuation primops has been proposed by Alexis King https://github.com/ghc-proposals/ghc-proposals/pull/313

https://github.com/lexi-lambda/ghc-proposals/blob/delimited-continuation-pri...

I’ll propose Simon Marlow as the shepherd.

Please guide us to a conclusion as outlined in https://github.com/ghc-proposals/ghc-proposals#committee-process

Thanks, Joachim -- Joachim Breitner mail@joachim-breitner.de http://www.joachim-breitner.de/

_______________________________________________ ghc-steering-committee mailing list ghc-steering-committee@haskell.org https://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-steering-committee

_______________________________________________ ghc-steering-committee mailing list ghc-steering-committee@haskell.org https://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-steering-committee

The issue with unsafePerformIO is really just that the proposal says that it's illegal to use the primops with unsafePerformIO. I don't think it's possible to make it "illegal" in any meaningful sense, probably a better way to say it would be "undefined" or "unsupported" or somesuch. Cheers Simon On Mon, 30 Nov 2020 at 01:53, Eric Seidel <eric@seidel.io> wrote:

This is a very well-written and motivated proposal, and I love that it's just three new primops (really two, plus a tag to add some guard rails). I'm not very familiar with the literature on delimited continuations, but I support going with the most general formulation, especially for primops.

I'm not sure we need to be able to detect all uses of the new primops with unsafePerformIO, it's already a deeply unsafe function. Just another thing that advanced users will need to keep in mind.

On Mon, Nov 23, 2020, at 09:37, Simon Marlow wrote:

...

Committee,

We have been asked to review #313: Delimited continuation primops

https://github.com/ghc-proposals/ghc-proposals/pull/313

https://github.com/lexi-lambda/ghc-proposals/blob/delimited-continuation-pri...

...

*Summary*

The proposal makes no language changes, it only adds three primops <

https://github.com/lexi-lambda/ghc-proposals/blob/delimited-continuation-pri...

...

.

The main motivation is to support building efficient implementations of Algebraic Effect systems, which depend on being able to efficiently capture a continuation. Currently this is done explicitly, which imposes a severe performance penalty.

These primops are the minimal support needed to be able to capture a continuation and apply it at runtime, together with some basic type safety via the PromtTag type to ensure that at least we don't replace a continuation with a computation of a different type. (there are other ways to go wrong with these primops though, they're not a safe interface by themselves: they need to be wrapped in a safe library).

The primops are implemented by copying chunks of stack into the heap. This is something that GHC's runtime already does a lot of, so it's not a new concept, although it does require a new closure type and knock-on changes across several files in the runtime (though it's mainly mechanical). There's a prototype implementation here:

https://gitlab.haskell.org/lexi.lambda/ghc/-/compare/master...first-class-co...

...

*Decision* * * I'm going to tentatively recommend acceptance. * This is a sensible choice for the primtives, being the most general of the alternatives, as explained in the proposal. <

https://github.com/lexi-lambda/ghc-proposals/blob/delimited-continuation-pri...

...

* Would the new primops impose a significant ongoing maintenance burden? Having looked at the patch, although there are some missing pieces, I don't think the new concepts impose any significant new requirements on other parts of the runtime. * I suspect there may be some difficulties around unsafePerformIO, so I raised that on the github thread <

https://github.com/ghc-proposals/ghc-proposals/pull/313#issuecomment-7321819...

...

Thoughts?

On Sat, 12 Sep 2020 at 22:59, Joachim Breitner <mail@joachim-breitner.de>

wrote:

...

...

Dear Committee,

this is your secretary speaking:

Delimited continuation primops has been proposed by Alexis King https://github.com/ghc-proposals/ghc-proposals/pull/313

https://github.com/lexi-lambda/ghc-proposals/blob/delimited-continuation-pri...

...

I’ll propose Simon Marlow as the shepherd.

Please guide us to a conclusion as outlined in https://github.com/ghc-proposals/ghc-proposals#committee-process

Thanks, Joachim -- Joachim Breitner mail@joachim-breitner.de http://www.joachim-breitner.de/

_______________________________________________ ghc-steering-committee mailing list ghc-steering-committee@haskell.org

https://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-steering-committee _______________________________________________ ghc-steering-committee mailing list ghc-steering-committee@haskell.org https://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-steering-committee

_______________________________________________ ghc-steering-committee mailing list ghc-steering-committee@haskell.org https://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-steering-committee

Oh I see. I'm always uncomfortable declaring things "undefined" because of how C/C++ compilers can run wild with code that invokes UB. So I kinda prefer saying that it's "illegal but unchecked". On Tue, Dec 1, 2020, at 12:35, Simon Marlow wrote:

The issue with unsafePerformIO is really just that the proposal says that it's illegal to use the primops with unsafePerformIO. I don't think it's possible to make it "illegal" in any meaningful sense, probably a better way to say it would be "undefined" or "unsupported" or somesuch.

Cheers Simon

On Mon, 30 Nov 2020 at 01:53, Eric Seidel <eric@seidel.io> wrote:

...

This is a very well-written and motivated proposal, and I love that it's just three new primops (really two, plus a tag to add some guard rails). I'm not very familiar with the literature on delimited continuations, but I support going with the most general formulation, especially for primops.

I'm not sure we need to be able to detect all uses of the new primops with unsafePerformIO, it's already a deeply unsafe function. Just another thing that advanced users will need to keep in mind.

On Mon, Nov 23, 2020, at 09:37, Simon Marlow wrote:

...

Committee,

We have been asked to review #313: Delimited continuation primops

https://github.com/ghc-proposals/ghc-proposals/pull/313 https://github.com/lexi-lambda/ghc-proposals/blob/delimited-continuation-pri...

*Summary*

The proposal makes no language changes, it only adds three primops <https://github.com/lexi-lambda/ghc-proposals/blob/delimited-continuation-primops/proposals/0000-delimited-continuation-primops.md#proposed-change-specification>.

The main motivation is to support building efficient implementations of Algebraic Effect systems, which depend on being able to efficiently capture a continuation. Currently this is done explicitly, which imposes a severe performance penalty.

These primops are the minimal support needed to be able to capture a continuation and apply it at runtime, together with some basic type safety via the PromtTag type to ensure that at least we don't replace a continuation with a computation of a different type. (there are other ways to go wrong with these primops though, they're not a safe interface by themselves: they need to be wrapped in a safe library).

The primops are implemented by copying chunks of stack into the heap. This is something that GHC's runtime already does a lot of, so it's not a new concept, although it does require a new closure type and knock-on changes across several files in the runtime (though it's mainly mechanical). There's a prototype implementation here: https://gitlab.haskell.org/lexi.lambda/ghc/-/compare/master...first-class-co...

*Decision* * * I'm going to tentatively recommend acceptance. * This is a sensible choice for the primtives, being the most general of the alternatives, as explained in the proposal. <https://github.com/lexi-lambda/ghc-proposals/blob/delimited-continuation-primops/proposals/0000-delimited-continuation-primops.md#operational-semantics> * Would the new primops impose a significant ongoing maintenance burden? Having looked at the patch, although there are some missing pieces, I don't think the new concepts impose any significant new requirements on other parts of the runtime. * I suspect there may be some difficulties around unsafePerformIO, so I raised that on the github thread <https://github.com/ghc-proposals/ghc-proposals/pull/313#issuecomment-732181948> Thoughts?

On Sat, 12 Sep 2020 at 22:59, Joachim Breitner <mail@joachim-breitner.de> wrote:

...

Dear Committee,

this is your secretary speaking:

Delimited continuation primops has been proposed by Alexis King https://github.com/ghc-proposals/ghc-proposals/pull/313 https://github.com/lexi-lambda/ghc-proposals/blob/delimited-continuation-pri...

I’ll propose Simon Marlow as the shepherd.

Please guide us to a conclusion as outlined in https://github.com/ghc-proposals/ghc-proposals#committee-process

Thanks, Joachim -- Joachim Breitner mail@joachim-breitner.de http://www.joachim-breitner.de/

_______________________________________________ ghc-steering-committee mailing list ghc-steering-committee@haskell.org https://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-steering-committee

---

ghc-steering-committee mailing list ghc-steering-committee@haskell.org https://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-steering-committee

_______________________________________________ ghc-steering-committee mailing list ghc-steering-committee@haskell.org https://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-steering-committee

I think the key distinction between “undefined” as used in C/C++ and what I call “illegal but unchecked” is that the optimizer operates under the assumption that “undefined” behavior is impossible. This is what leads to the bizarre and scary stories that people post about UB, but it also lets C/C++ compilers emit much more efficient code in some common places. In contrast, an “illegal but unchecked” operation would be left alone by the optimizer. The runtime behavior would be unspecified and possibly platform-dependent, but still more constrained and predictable than UB. I agree that unsafe primops are fine, but I’m curious now if GHC optimizes based on the assumption that they’re used correctly. Sent from my iPhone

On Dec 2, 2020, at 08:34, Simon Marlow <marlowsd@gmail.com> wrote:

 "Illegal but unchecked" would be fine too, although we do already use the term "undefined" in the documentation for various primops.

We've so far taken the approach that undefined behaviour in primops is OK. The idea is that libraries built on top can provide a safe and fully-defined API. e.g.

* division-by-zero is undefined (libraries are supposed to check before invoking the primop) * The uncheckedIShift family are undefined for arguments outside the allowed bounds * unsafeCoerce is undefined when used in certain ways, of course

There are probably more that aren't documented.

Cheers Siimon

...

On Tue, 1 Dec 2020 at 18:25, Eric Seidel <eric@seidel.io> wrote: Oh I see. I'm always uncomfortable declaring things "undefined" because of how C/C++ compilers can run wild with code that invokes UB. So I kinda prefer saying that it's "illegal but unchecked".

On Tue, Dec 1, 2020, at 12:35, Simon Marlow wrote:

...

The issue with unsafePerformIO is really just that the proposal says that it's illegal to use the primops with unsafePerformIO. I don't think it's possible to make it "illegal" in any meaningful sense, probably a better way to say it would be "undefined" or "unsupported" or somesuch.

Cheers Simon

On Mon, 30 Nov 2020 at 01:53, Eric Seidel <eric@seidel.io> wrote:

...

This is a very well-written and motivated proposal, and I love that it's just three new primops (really two, plus a tag to add some guard rails). I'm not very familiar with the literature on delimited continuations, but I support going with the most general formulation, especially for primops.

I'm not sure we need to be able to detect all uses of the new primops with unsafePerformIO, it's already a deeply unsafe function. Just another thing that advanced users will need to keep in mind.

On Mon, Nov 23, 2020, at 09:37, Simon Marlow wrote:

...

Committee,

We have been asked to review #313: Delimited continuation primops

https://github.com/ghc-proposals/ghc-proposals/pull/313 https://github.com/lexi-lambda/ghc-proposals/blob/delimited-continuation-pri...

*Summary*

The proposal makes no language changes, it only adds three primops <https://github.com/lexi-lambda/ghc-proposals/blob/delimited-continuation-primops/proposals/0000-delimited-continuation-primops.md#proposed-change-specification>.

The main motivation is to support building efficient implementations of Algebraic Effect systems, which depend on being able to efficiently capture a continuation. Currently this is done explicitly, which imposes a severe performance penalty.

These primops are the minimal support needed to be able to capture a continuation and apply it at runtime, together with some basic type safety via the PromtTag type to ensure that at least we don't replace a continuation with a computation of a different type. (there are other ways to go wrong with these primops though, they're not a safe interface by themselves: they need to be wrapped in a safe library).

The primops are implemented by copying chunks of stack into the heap. This is something that GHC's runtime already does a lot of, so it's not a new concept, although it does require a new closure type and knock-on changes across several files in the runtime (though it's mainly mechanical). There's a prototype implementation here: https://gitlab.haskell.org/lexi.lambda/ghc/-/compare/master...first-class-co...

*Decision* * * I'm going to tentatively recommend acceptance. * This is a sensible choice for the primtives, being the most general of the alternatives, as explained in the proposal. <https://github.com/lexi-lambda/ghc-proposals/blob/delimited-continuation-primops/proposals/0000-delimited-continuation-primops.md#operational-semantics> * Would the new primops impose a significant ongoing maintenance burden? Having looked at the patch, although there are some missing pieces, I don't think the new concepts impose any significant new requirements on other parts of the runtime. * I suspect there may be some difficulties around unsafePerformIO, so I raised that on the github thread <https://github.com/ghc-proposals/ghc-proposals/pull/313#issuecomment-732181948> Thoughts?

On Sat, 12 Sep 2020 at 22:59, Joachim Breitner <mail@joachim-breitner.de> wrote:

...

Dear Committee,

this is your secretary speaking:

Delimited continuation primops has been proposed by Alexis King https://github.com/ghc-proposals/ghc-proposals/pull/313 https://github.com/lexi-lambda/ghc-proposals/blob/delimited-continuation-pri...

I’ll propose Simon Marlow as the shepherd.

Please guide us to a conclusion as outlined in https://github.com/ghc-proposals/ghc-proposals#committee-process

Thanks, Joachim -- Joachim Breitner mail@joachim-breitner.de http://www.joachim-breitner.de/

_______________________________________________ ghc-steering-committee mailing list ghc-steering-committee@haskell.org https://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-steering-committee

---

ghc-steering-committee mailing list ghc-steering-committee@haskell.org https://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-steering-committee

_______________________________________________ ghc-steering-committee mailing list ghc-steering-committee@haskell.org https://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-steering-committee

---

ghc-steering-committee mailing list ghc-steering-committee@haskell.org https://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-steering-committee

On Thu, Dec 3, 2020, at 05:29, Simon Marlow wrote:

My understanding of what happened in C compilers is that the optimisers want to do some dataflow analysis to determine the ranges of values that variables can take, in order to eliminate unnecessary conditionals and so forth. These analyses are severely crippled if you can't assume the absence of undefined behaviour in C/C++, because most arithmetic operations have undefined behaviour: overflow is undefined, for example.

Right, I think what leads to the surprising behavior in C/C++ is that compilers sometimes use the results of the dataflow analysis in a manner that violates causality. For example, removing a NULL check because later on the pointer is dereferenced unconditionally. I don't think anyone would complain about the compiler removing NULL checks *after* the dereference, but doing so before is a bit unsettling. Suppose the NULL check the compiler cleverly elided was meant to call into a custom abort() function. Now we have to hope the compiler can figure out that our abort() wrapper doesn't return, and we probably have to annotate our abort() to help the compiler along. Another example that always comes to mind is where the compiler may replace an indirect call via a NULL function pointer with a direct call to a function f() that is never actually assigned to the function pointer, because it detected that f() is the only possible target of the pointer and calling a NULL function pointer is also UB.

We don't do this kind of analysis in GHC at the moment, and we don't have quite so much undefined behaviour floating around. But I can imagine similar issues might arise. I mean, we most definitely assume that the result of `unsafeCoerce#` is a value of the claimed type - what else can you do? I suppose I'm not really clear on what specifically it would mean to adopt "illegal but unchecked" as the policy for undefined behaviour. Does it mean the compiler can't assume anything about the result of an operation that has any undefined behaviour?

That's a fair point. I'm not entirely clear on where to draw the line either, but maybe respecting causality would be a good place to start. So it's fine for us to assume that operations that have UB complete successfully, and to assume the inputs satisfy the operation's contract from that point on, but maybe we should avoid propagating those assumptions back before the call-site that may invoke UB. But then what do we do about loops? It seems we would either have to special case the first iteration or block optimizations in the first section of the loop on every iteration.. Both options sound terrible..

Yeah, I think I convinced myself while writing my last reply that it's not worth the trouble. On Thu, Dec 3, 2020, at 11:58, Iavor Diatchki wrote:

I don't think we should worry about trying to provide sane behavior for when people violate stated assumptions---doing so makes the compiler's work harder, and encourages people to violate the assumptions. It is important to document clearly what the assumptions are, of course.

-Iavor

On Thu, Dec 3, 2020 at 6:52 AM Eric Seidel <eric@seidel.io> wrote:

...

On Thu, Dec 3, 2020, at 05:29, Simon Marlow wrote:

...

My understanding of what happened in C compilers is that the optimisers want to do some dataflow analysis to determine the ranges of values that variables can take, in order to eliminate unnecessary conditionals and so forth. These analyses are severely crippled if you can't assume the absence of undefined behaviour in C/C++, because most arithmetic operations have undefined behaviour: overflow is undefined, for example.

Right, I think what leads to the surprising behavior in C/C++ is that compilers sometimes use the results of the dataflow analysis in a manner that violates causality.

For example, removing a NULL check because later on the pointer is dereferenced unconditionally. I don't think anyone would complain about the compiler removing NULL checks *after* the dereference, but doing so before is a bit unsettling. Suppose the NULL check the compiler cleverly elided was meant to call into a custom abort() function. Now we have to hope the compiler can figure out that our abort() wrapper doesn't return, and we probably have to annotate our abort() to help the compiler along.

Another example that always comes to mind is where the compiler may replace an indirect call via a NULL function pointer with a direct call to a function f() that is never actually assigned to the function pointer, because it detected that f() is the only possible target of the pointer and calling a NULL function pointer is also UB.

...

We don't do this kind of analysis in GHC at the moment, and we don't have quite so much undefined behaviour floating around. But I can imagine similar issues might arise. I mean, we most definitely assume that the result of `unsafeCoerce#` is a value of the claimed type - what else can you do? I suppose I'm not really clear on what specifically it would mean to adopt "illegal but unchecked" as the policy for undefined behaviour. Does it mean the compiler can't assume anything about the result of an operation that has any undefined behaviour?

That's a fair point. I'm not entirely clear on where to draw the line either, but maybe respecting causality would be a good place to start. So it's fine for us to assume that operations that have UB complete successfully, and to assume the inputs satisfy the operation's contract from that point on, but maybe we should avoid propagating those assumptions back before the call-site that may invoke UB. But then what do we do about loops? It seems we would either have to special case the first iteration or block optimizations in the first section of the loop on every iteration.. Both options sound terrible.. _______________________________________________ ghc-steering-committee mailing list ghc-steering-committee@haskell.org https://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-steering-committee

Hi, accepted! Cheers, Joachim -- Joachim Breitner mail@joachim-breitner.de http://www.joachim-breitner.de/