[ghc-steering-committee] Please review #313: Delimited continuation primops, Shepherd: Simon Marlow

Thu Dec 3 10:29:24 UTC 2020

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.

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

Cheers
Simon

On Wed, 2 Dec 2020 at 14:22, Eric Seidel <eric at seidel.io> wrote:

> 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 at 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 at 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 at 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-primops/proposals/0000-delimited-continuation-primops.md
>> > > >
>> > > > *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-continuations?view=inline
>> > > >
>> > > > *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 at 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-primops/proposals/0000-delimited-continuation-primops.md
>> > > > >
>> > > > > 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 at joachim-breitner.de
>> > > > >   http://www.joachim-breitner.de/
>> > > > >
>> > > > >
>> > > > > _______________________________________________
>> > > > > ghc-steering-committee mailing list
>> > > > > ghc-steering-committee at haskell.org
>> > > > >
>> https://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-steering-committee
>> > > > _______________________________________________
>> > > > ghc-steering-committee mailing list
>> > > > ghc-steering-committee at haskell.org
>> > > >
>> https://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-steering-committee
>> > > >
>> > > _______________________________________________
>> > > ghc-steering-committee mailing list
>> > > ghc-steering-committee at haskell.org
>> > >
>> https://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-steering-committee
>> _______________________________________________
>> ghc-steering-committee mailing list
>> ghc-steering-committee at haskell.org
>> https://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-steering-committee
>>
> _______________________________________________
> ghc-steering-committee mailing list
> ghc-steering-committee at haskell.org
> https://mail.haskell.org/cgi-bin/mailman/listinfo/ghc-steering-committee
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.haskell.org/pipermail/ghc-steering-committee/attachments/20201203/d132c1c7/attachment-0001.html>