[CSL-2117] Allow careful usage of ExceptT over IO

There are two reasons to avoid ExceptT over IO:

it creates a separate exception handling mechanism overlapping with IO exceptions
it doesn't have a MonadMask instance, so bracket cannot be used with it

The first reason can be mitigated by making the sets of ExceptT and IO exceptions disjoint:

throwError must be used only with types that have a TypeError "Not an exception" => Exception e instance (requirement of our guidelines)
throwM and throwIO require a working Exception e instance

This means that the two mechanisms are not in conflict, but actually complement each other. One is useful for checked exceptions and general control flow, while the other — for unchecked exceptions.
As to MonadMask, this will be fixed in the next exceptions release.

There are two reasons to avoid ExceptT over IO:

To be clear: do you mean ruling out ExceptT e m whenever m is MonadIO? Or avoiding ExceptT in favour of IO?

it creates a separate exception handling mechanism overlapping with IO exceptions

It's sad that the names Except and throw are used for the monad transformer. The overloading is confusing. The "separate exception handling mechanism" that ExceptT apparently provides is not a real thing. Case in point: ExceptT is defined in standard Haskell, without any assumptions about GHC or its runtime system. When we come across an ExceptT e m t it's merely an m (Either e t). There's no magic side-channel for exceptions added on by the ExceptT. It uses only purity and the assumption of Monad : Monad m => Monad (ExceptT e m).
Is this not a legit use of ExceptT over IO?
-- An unrecognized ByteString is not an unwanted/exceptional/bad case, it's just
-- something that could come up in this pure function.
parse :: ByteString -> Either NoParse Value

-- A key that is not in the database is not an unwanted/exceptional/bad case, it's
-- just something that could happen in this IO. NB: there could be exceptions, like
-- a file IO or corrupt db etc.
dbLookup :: Key -> IO (Either KeyNotFound ByteString)

type NotAnException = Either KeyNotFound NoParse

-- ExceptT is used as a tool to compose lookup and parse.
-- It does not step on the typical exception path.
-- The ExceptT "exceptions", which are not exceptions, come out inside the
-- inner monad; only the inner monad may throw exceptions.
composite :: Key -> ExceptT NotAnException IO Value
composite k = do
  bs <- withExceptT Left $ ExceptT (dbLookup k)
  withExceptT Right $ ExceptT (pure (parse bs))

it doesn't have a MonadMask instance, so bracket cannot be used with it

I don't believe this is actually a problem. If you're defining an ExceptT e m t and you think you need to deal with asynchronous exceptions, then m must have an IO inside somewhere, so you can bracket in there.
Again, the sort of "exception" that ExceptT deals with is not really an exception, it's just a way of composing Either es; a completely legitimate and sometimes useful way of doing so.

throwError must be used only with types that have a TypeError "Not an exception" => Exception e instance (requirement of our guidelines)
throwM and throwIO require a working Exception e instance

This means that the two mechanisms are not in conflict, but actually complement each other. One is useful for checked exceptions and general control flow, while the other — for unchecked exceptions.

The two mechanism are not in conflict even without these guidelines. Throwing an exception in IO is completely different from throwE = ExceptT . return . Left.
What's the worry here? That a reader might be confused about where the exception will arise?

To be clear: do you mean ruling out ExceptT e m whenever m is MonadIO? Or avoiding ExceptT in favour of IO?

I mean the former, but now this restriction is lifted.

The "separate exception handling mechanism" that ExceptT apparently provides is not a real thing.

It is a real thing, although you might dislike that I called it "exception" handling, and honestly I'm tired of you trying to force your understanding what an "exception" means, because this term is overloaded. Yes, there is very specific technical definition that corresponds to exceptions as implemented in GHC RTS, but there's also a broader sense, exceptions are a mechanism for early exit.
ExceptT has got Except in its name for a reason. Consider also this bit of documentation from the exceptions package:

This instance is only valid if the base monad provides no ability to provide multiple exit. For example, IO or Either would be invalid base monads, but Reader or State would be acceptable.

So Either is in the same list as IO here, they both provide multiple exit paths from the monad. If you like formalisms, consider the following definition of bracket, taken from exceptions-0.8.3:
bracket :: MonadMask m => m a -> (a -> m b) -> (a -> m c) -> m c
bracket acquire release use = mask $ \unmasked -> do
  resource <- acquire
  result <- unmasked (use resource) `onException` release resource
  _ <- release resource
  return result

This definition is only valid for monads m that do not have multiple early exit mechanisms, otherwise we have no guarantee that release will be executed. ExceptT is a transformer that adds an early exit mechanism, so this definition of bracket won't work for it. This is the sense in which I'm speaking of "a separate exception handling mechanism". And when I said "overlapping with IO exceptions", I meant that exceptions of the same types can be thrown both via throwError (for ExceptT) and throwIO (for IO).
Thus in ExceptT E IO we actually always have two options:

throwError E
throwM E

and when we want to catch E, we might need to do it twice, because there's no guarantee that it's thrown only via one of those mechanisms. But now the guidelines make the TypeError "Not an exception" => Exception e instance required for types used with ExceptT, so the overlap is gone.

What's the worry here? That a reader might be confused about where the exception will arise?

The worry is that there's no barrier to writing the code where the same type of exception will arise in both IO and ExceptT.

Case in point: ExceptT is defined in standard Haskell, without any assumptions about GHC or its runtime system. When we come across an ExceptT e m t it's merely an m (Either e t).

This is a revelation to no one.

There's no magic side-channel for exceptions added on by the ExceptT.

And this is true only because you used the word "magic" — ExceptT adds an absolutely normal side-channel for exceptions, not a magic one.

Is this not a legit use of ExceptT over IO?

With this change to guidelines, it's a valid use case, you only need to create TypeError "Not an exception" => Exception e instances for the following types in your example:

NoParse
KeyNotFound
NotAnException

so that we know they aren't thrown using the GHC RTS mechanism of exceptions.

@int-index I'm  just lurking here, but I  was wondering if there is there any working code that uses this technique to disallow Exception instances for a specific data type that you can point me to?

I was wondering if there is there any working code that uses this technique to disallow Exception instances for a specific data type that you can point me to?

I don't think there's such code yet, it's something that came up back when I was writing the initial draft of these guidelines and discussing this issue in Slack.

I  found a TypeError data type in "auxx" package defined as:
data TypeError = TypeError
    { teExpectedType :: !TypeName
    , teActualValue  :: !Value
    } deriving (Eq, Ord, Show)

but that does not seem to be the same TypeError as one you are discussing here.
Would you be able to define this TypeError type or point me to some documentation so I can learn more about this technique?

Would you be able to define this TypeError type or point me to some documentation so I can learn more about this technique?

Oh, I should've made this more clear, the TypeError I have in mind is from base, it's a type family to define custom type errors:
https://hackage.haskell.org/package/base-<IP_ADDRESS>/docs/GHC-TypeLits.html#t:TypeError
And instead of TypeError "Not an exception" it should be TypeError (Text "Not an exception: " :<>: ShowType e).

Thanks @int-index, this is very useful.
At my current employer we are heavy users of EitherT /  ExceptT transformers and tend to avoid the use of exceptions. Currently this is encoded in our code style guidelines and hopefully caught in code review, but with this technique we should be able to turn EitherT over an e type with an Exception instance into a compile error (at least with ghc 8.2 and later). That's a huge win!

It is a real thing, although you might dislike that I called it "exception" handling, and honestly I'm tired of your attempts to force your understanding what an "exception" means, because this term is overloaded.

I'm only trying to cut the confusion here. In your story, ExceptT does throw exceptions, but the only exceptions it throws are TypeError "Not an exception". Why not clear the water? Pick a convention that includes one fewer linguistic ambiguity?

Consider also this bit of documentation from the exceptions package:

This instance is only valid if the base monad provides no ability to provide multiple exit. For example, IO or Either would be invalid base monads, but Reader or State would be acceptable.

This quote is from the documentation for MonadMask referring to CatchT's instance of it. That seems a decent guideline: do not use the MonadMask instance for CatchT m, ever.

This is the sense in which I'm speaking of "a separate exception handling mechanism". And when I said "overlapping with IO exceptions", I meant that exceptions of the same types can be thrown both via throwError (for ExceptT) and throwIO (for IO).

The fact that masking/bracketing doesn't behave as excepted with CatchT m should factor into the guidelines. Don't use this MonadMask instance. If you're masking/bracketing, do it in IO. I support this, but I don't recall reading that in the guidelines... maybe I've just forgotten?
Anyway, that's a point on its own.

With this change to guidelines, it's a valid use case, you only need to create TypeError "Not an exception" => Exception e instances for the following types in your example:

NoParse
KeyNotFound
NotAnException

so that we know they aren't thrown using the GHC RTS mechanism of exceptions.
...
The worry is that there's no barrier to writing the code where the same type of exception will arise in both IO and ExceptT.

I just don't see this being a problem. It's certainly not a problem in the little example I gave. Let's be more practical though: how about the issue that brought this all about? getHeadersRange :: HeaderHash -> HeaderHash -> m (Either GetHeadersRangeError [HeaderHash])? That should be allowed. It will be obvious from its definition that GetHeadersRangeError is not thrown in m. Now, a user can wrap it up in ExceptT and "catch" it in ExceptT without worry. But you have cited the guidelines to support a worse type.
Perhaps the merit of this guideline only appears when we have those massive *Mode constraints, which probably include MonadError e m, MonadIO m, MonadMask m? I could buy that I guess, but the problem is the massive constraint and poor factoring of the definition into pure and impure, the same root problem which motivated that "monadic effects in CSL" document.

Yes, there is very specific technical definition that corresponds to exceptions as implemented in GHC RTS, but there's also a broader sense, exceptions are a mechanism for early exit.
...
And this is true only because you used the word "magic" — ExceptT adds an absolutely normal side-channel for exceptions, not a magic one. As do Either, Maybe, MaybeT, because of their Monad instances.

Again, only trying to erase ambiguity. In the context of pure functional programming, "early exit" and "side-channel" make me raise an eyebrow. Why is Left a side-channel? Why is Nothing a side-channel? There is no privileged constructor, there's no early exit, nothing happens in a pure term. On the other hand, IO exceptions really do suggest early-exit and side-channel, because they can come up at any time, aren't reflected in the type, and may bring about an exception handler.

Case in point: ExceptT is defined in standard Haskell, without any assumptions about GHC or its runtime system. When we come across an ExceptT e m t it's merely an m (Either e t).

This is a revelation to no one.

Good. So you see what I mean? We're dealing with very different animals here so let's call them different things.

ma :: m (Either e a)

mb :: a -> m (Either e b)

example1 :: Monad m => m (Either e b)
example1 = do
  a <- ma
  case a of
    Left e -> pure (Left e)
    Right a -> do
      b <- mb a
      case b of
        Left e -> pure (Left e)
        Right b -> pure (Right b)

example2 :: Monad m => ExceptT e m b
example2 = do
  a <- ExceptT (ma)
  ExceptT (mb a)

example3 :: Monad m => Int -> m x -> m Int
example3 i something =
  if i == 42
  then pure 42
  else do something >> pure 0

Which of these exhibit "side-channels"? Which of these exhibit "early exits"?

I suppose my main issue with these exception guidelines is that they encourage throwing real IO exceptions over using pure alternatives like Either/ExceptT. That was demonstrated in the PR I cited: rather than using Either GetHeadersRangeError, the guidelines indicated that it's better to throw GetHeadersRangeError in the underlying monad, which yields a weaker type and bigger constraint burden.
I do appreciate what you're getting at about the two ways of "early exit", though I have some nits about the terminology. However, I think the solution ought to be: use real exceptions sparingly. If you can (and you probably can), express the "unwanted" or "failure" cases in the type of the function rather than by throwing an exception. This way, the burden falls upon the rarer case, in which a real IO exception is in fact the right thing to use. If such a case comes up in a high-level composite thing inside some big monad transformer stack, consider refactoring to move the low-level exception-throwing IO and masking/bracketing to the bottom where it belongs.

I suppose my main issue with these exception guidelines is that they encourage throwing real IO exceptions over using pure alternatives like Either/ExceptT.

The change in this PR is to allow usage of ExceptT together with IO, so that IO exceptions are not encouraged. So, do I understand correctly that you approve this particular PR?

Why not clear the water? Pick a convention that includes one fewer linguistic ambiguity?

That's why I tried to introduce the "regular error" term, and yet you say this term "has to go". Maybe that's true. But I haven't seen a better suggestion, so far you've been calling these early exit scenarios "exceptions" (in quotes) or "normal outcomes",  neither appears more clear than "regular error" (as opposed to "programmer mistake").

Good. So you see what I mean? We're dealing with very different animals here so let's call them different things.

Indeed. Let's also improve terminology. But this PR stands on its own, I suppose we can merge it and then focus on finding better wording. I just need a better suggestion than "regular error", it's not that I'm happy with this situation either, it caused a lot of confusion.

and masking/bracketing to the bottom where it belongs.

Masking and bracketing is necessary to deal with resources (such as database handles, for instance), so it can occur anywhere in the code. But as I said, ExceptT is going to get a MonadMask instance, so that's alright.

Let's be more practical though: how about the issue that brought this all about? getHeadersRange :: HeaderHash -> HeaderHash -> m (Either GetHeadersRangeError [HeaderHash])? That should be allowed.

Sure, it should be allowed. But it was Either Text, not Either GetHeadersRangeError, which shouldn't be allowed for a different reason.

It will be obvious from its definition that GetHeadersRangeError is not thrown in m.

It's not obvious, there's no quick and reliable way to check that, but you can make it obvious with an Exception instance that implies a TypeError.

Now, a user can wrap it up in ExceptT and "catch" it in ExceptT without worry. But you have cited the guidelines to support a worse type.

This is one of the motivations for this change to the guidelines. Now ExceptT is allowed.

Masking and bracketing are necessary to deal with resources (such as database handles, for instance), so they can occur anywhere in the code.

They can, but it's not obvious whether they should.

But as I said, ExceptT is going to get a MonadMask instance, so that's alright.

Even still, I'm skeptical of whether it should be used. I'm skeptical of masking/bracketing with any m that's not m ~ IO or maybe a reader over IO.

It will be obvious from its definition that GetHeadersRangeError is not thrown in m.

It's not obvious, there's no quick and reliable way to check that, but you can make it obvious with an Exception instance that implies a TypeError.

I suppose the only case in which it might be considered non-obvious is when you have an ExceptT e over another ExceptT e and/or an IO...
instance Exception MyError

-- 3 ways it could come about.
confusingThing :: ExceptT MyError (ExceptT MyError IO) t

I'm all for ruling that out as a horrible style.
But how about
notConfusing :: forall t m . Monad m => ExceptT MyError m t

Sure, in this case it could be specialized over m := IO and a user of notConfusing could throw a MyError in IO, but notConfusing won't be affected: it risks no mistake because it ranges over all monads.

They can, but it's not obvious whether they should.

I'm pretty sure when you acquire a resource, you often should release it later, and that's what bracket is for. And this can happen in any monad, really.

Even still, I'm skeptical of whether it should be used. I'm skeptical of masking/bracketing with any m that's not m ~ IO or maybe a reader over IO.

I share your skepticism, but isn't it your idea to represent some of the normal outcomes with ExceptT? I can see how we might need to both deal with resources (which implies bracket) and have early exit due to a normal outcome (which implies ExceptT).

But how about
notConfusing :: forall t m . Monad m => ExceptT MyError m t

Sure, in this case it could be specialized over m := IO and a user of notConfusing could throw a MyError in IO, but notConfusing won't be affected: it risks no mistake because it ranges over all monads.

I don't see a problem with notConfusing, but I do see it here:
confusing :: forall t m. Monad m => m a -> ExceptT MyError m t

The m a action supplied by the user may throw MyError. To avoid reasoning about these corner cases, I think we should simply create TypeError-based Exception instances for types that are thrown with ExceptT.
This means that:

we avoid the overhead of deciding whether to do this
we avoid the overhead of maintaining the reasoning behind our decision as the codebase evolves (if we only have notConfusing, we do not need to create this instance for MyError, but if we later declare confusing, then we do).

I don't really see any downside to a short and simple instance like this:
instance NotAnExc MyError => Exception MyError

where NotAnExc is a helper (that will go to Pos.Util.Util) defined as
type NotAnExc e = TypeError (Text "Not an exception: " :<>: ShowType e)

Having this instance will statically prevent throwing MyError as an IO exception, since it's meant to be used with ExceptT. Right now we even have a helper, eitherToThrow, which is used to turn a "normal outcome" returned in Either to an exception. Let's prevent these cases statically, they make reasoning about code confusing.
Do you have an objection to declaring such instances?

Just came across this today https://www.reddit.com/r/haskell/comments/7xcfkk/defining_a_negative_type_constraint/
highly relevant

I'm pretty sure when you acquire a resource, you often should release it later, and that's what bracket is for. And this can happen in any monad, really.

I didn't mean you shouldn't release it. I meant you probably should be bracketing in a massive monad transformer stack.

confusing :: forall t m. Monad m => m a -> ExceptT MyError m t
The m a action supplied by the user may throw MyError. To avoid reasoning about these corner cases, I think we should simply create TypeError-based Exception instances for types that are thrown with ExceptT.

Ah but I am not allowed to catch the MyError  thrown by that m a! Because I don't know that it is capable of throwing an exception.

Do you have an objection to declaring such instances?

Yes I suppose so, but it's more akin to the presumption of innocence. I don't think it's worth the bother to do it. That's not to say it's especially bad, it's just to say it's not especially good. Maybe it wouldn't bring any harm, but overall I think it's the wrong way of going about things

we avoid the overhead of maintaining the reasoning behind our decision as the codebase evolves (if we only have notConfusing, we do not need to create this instance for MyError, but if we later declare confusing, then we do).

But if we later declare confusing, then we will have made a mistake. The solution is to structure our programs judiciously, leveraging purity and parametricity.

Yes I suppose so, but it's more akin to the presumption of innocence. I don't think it's worth the bother to do it.

Why would you apply presumption of innocence to code? My viewpoint is that assuming the code is incorrect unless proven correct is a more viable strategy, because bugs happen.
And what's the bother here? A single line per type? I'd share your position if the overhead was big, but a single line doesn't seem too bad to me, we get useful guarantees from it.

Ah but I am not allowed to catch the MyError thrown by that m a! Because I don't know that it is capable of throwing an exception.

Consider this example:
confusing :: forall t m. Monad m => m Bool -> ExceptT MyError m T
confusing mb = do
  b <- mb
  if b then return T
       else throwError MyError

readB :: IO Bool
readB = do
  n :: Int <- readLn
  if | n < 0 -> return True
     | n > 0 -> return False
     | otherwise -> throwIO MyError

Now if I call confusing readB, I have a piece of code that can throw MyError both as an IO exception and via ExceptT, although neither definition includes both.
You say yourself: normal outcomes (that are thrown with ExceptT) and IO exceptions are different beasts. I say: let's represent them by different types. And declaring TypeError => Exception instances is a cheap and simple way to statically verify that indeed we don't use same types for both purposes.

Why would you apply presumption of innocence to code? My viewpoint is that assuming the code is incorrect unless proven correct is a more viable strategy, because bugs happen.

Oh I didn't mean to say software is innocent! :) Hardly. I meant that in adopting a new convention, the objection is by default.

And what's the bother here? A single line per type? I'd share your position if the overhead was big, but a single line doesn't seem too bad to me, we get useful guarantees from it.

Well, it's a new ad-hoc rule that every developer has to learn, and remember to obey and enforce.
RE: the example (copied for ease of reading)
confusing :: forall t m. Monad m => m Bool -> ExceptT MyError m ()
confusing mb = do
  b <- mb
  if b then return ()
       else throwError MyError

readB :: IO Bool
readB = do
  n :: Int <- readLn
  if | n < 0 -> return True
     | n > 0 -> return False
     | otherwise -> throwIO MyError

Now if I call confusing readB, I have a piece of code that can throw MyError both as an IO exception and via ExceptT, although neither definition includes both.

First, let me say that readB is absolutely bogus, and represents the true problem here. There's no good reason to throw an IO exception here; change the type to IO (Maybe Bool) or IO (Either NumberIsZero Bool).
But anyway, I'll entertain the example. If I use confusing readB, I still know by the type that there is a top-level MyError that I can "catch". It's unambiguous what catchError does. If, on the other hand, I know that readB may throw a real exception MyError (perhaps I can see the definition, or its documented), I'm still in a good position to catch it: confusing (readB catch handleMyError). Where do you suppose I'd make a mistake?

First, let me say that readB is absolutely bogus, and represents the true problem here. There's no good reason to throw an IO exception here; change the type to IO (Maybe Bool) or IO (Either NumberIsZero Bool).

Yes, although you were careful here to use a different exception type, NumberIsZero. But assume we actually want to encode the failure as MyError. Then the proper type should be one of these:
readB :: IO (Either MyError Bool)
readB :: ExceptT MyError IO Bool

and that's precisely the thing we enforce here: if the MyError type represents a normal outcome, not an exceptional failure, we can guarantee statically that it's not used as an IO exception.

Where do you suppose I'd make a mistake?

I think it's easy to forget to do both catch and catchError.
Let's say I'm implementing some functionality foo, and I want to use confusing readB. I don't inspect the implementation of readB, so I don't write confusing (catch readB handleMyError) as you suggest.
Then later, another piece of code uses foo. It handles the Left case with MyError, completely unaware that it also needs to handle it as an IO exception.
We have a situation where the same error must be handled both as an IO exception and a Left value in Either or ExceptT.
The property we want here is that the sets of types used in Either / ExceptT and as IO exceptions are disjoint. Then we don't need to think about such cases.

Let's say I'm implementing some functionality foo, and I want to use confusing readB. I don't inspect the implementation of readB, so I don't write confusing (catch readB handleMyError), contrary to your suggestion.
Then later, another piece of code uses foo. It handles the Left case with MyError, completely unaware that it also needs to handle MyError as an IO exception.

But does your proposal really improve upon this? If readB throws some other kind of exception, then I've still failed to catch it. Another program uses foo, handles the Left case with MyError, completely unaware that it also needs to handle some other exception as an IO exception.

Just because confusing and readB can both "throw" the same type, doesn't mean those values have the same semantics. A Left MyError from confusing is semantically distinct from a throwOP MyError is readB. It's not true that if a user wants to catch one, then they want to catch both.

But does your proposal really improve upon this? If readB throws some other kind of exception, then I've still failed to catch it. Another program uses foo, handles the Left case with MyError, completely unaware that it also needs to handle some other exception as an IO exception.

Yes, I think there's an improvement, and the improvement is simplified reasoning. Maybe readB throws another exception type, OK, - but at least I don't have a false sense that I have already handled it. Because it's a different type.
I want to avoid a situation where the developer knows he has to handle MyError, does so in a particular way (let's say via ExceptT), but the code actually throws the same failure in a different way.
That's why I want the sets of types used as normal outcomes in ExceptT and as IO exceptions to be disjoint. I think the technique I propose is lightweight and achieves this purpose well.

I want to avoid a situation where the developer knows he has to handle MyError, does so in a particular way (let's say via ExceptT), but the code actually throws the same failure in a different way.

Yes I think this may be the source of misunderstanding. I just posted a comment about it above.

Just because confusing and readB can both "throw" the same type, doesn't mean those values have the same semantics. A Left MyError from confusing is semantically distinct from a throwOP MyError is readB. It's not true that if a user wants to catch one, then they want to catch both.

If the semantics are different, use different types. With your proposal, for every exception type in existence I have to think about (1) its semantics when it's a "normal outcome", (2) its semantics when it's an IO exception.
When we narrow it down, there's less potential for mistakes and misunderstanding.
Different semantics — different types, sounds reasonable?

If the semantics are different, use different types.  ... Different semantics — different types, sounds reasonable?

Sounds like something to think about. Wouldn't you say that Maybe a can take on many different semantics?  Or how about free monads? A motivating point and source of popularity for this concept is the fact that the semantics can be given after the fact. In particular, one term in a free monad can have many interpretations (semantics).
I'm inclined to say no. One type can be used in many different semantic domains. We do this all the time.

With your proposal, for every exception type in existence I have to think about (1) its semantics when it's a "normal outcome", (2) its semantics when it's an IO exception.

No I think you've mixed it up: not for every exception type, but certainly for every term which either shows an "exception type" (Left e), or claims it may throw an exception in the documentation (IO a).

No I think you've mixed it up: not for every exception type, <...> claims it may throw an exception in the documentation

I think I didn't mix anything up. You have a bold assumption that every IO exception is documented. Let's say we add this to the guidelines: every top-level definition explicitly declares the IO exceptions it throws. Of course, tracking this in documentation would be simply unsustainable. These annotations would propagate transitively, and get out of date quickly. We have the same rules for error right now (documenting the preconditions), but having the same rules for IO exceptions is even more overhead. We are better of tracking this in types, not in the documentation.
I'd be content with an IO-like monad that tracks the exceptions it throws in a type-level set. Then we wouldn't have a situation where the developer thinks he/she handled some type of failure, but actually didn't. This would be tracked by the type system then, not by the developer.
Unfortunately, I think rewriting everything to such a monad would be an insane engineering effort. Although I've seen several prototypes of this idea, here's one of them: https://github.com/snoyberg/trio
So, our options are:
a) track exception in types: too much engineering effort
b) track exceptions in documentation: too much maintenance effort, no static checking, will get out of date and incorrect
c) do not track exceptions: creates potential for confusion for whether exceptions were handled properly
I suggest we pick (c), and ease the reasoning by making the sets of exceptional and non-exceptional failures disjoint. Statically enforce it with simple one-liners.

Wouldn't you say that Maybe a can take on many different semantics? <...> One type can be used in many different semantic domains. We do this all the time.

No, I think this is the sort of reasoning that leads to "boolean blindness" and similar phenomena. I'd hate to deal with something like Maybe (Maybe a) as a result from a database, but dealing with Either FieldNotPresent (Nullable a) is way better, even if we have:
data FieldNotPresent = FieldNotPresent -- unit
data Nullable a = Null | NotNull a

so it's isomorphic to Maybe (Maybe a).
Often we use "dumb" datatypes because we are too lazy to create newtypes or data types with clear semantics.
This brings us to exceptions. Okay, you might say that we have different interpretations of the same MyError in different domains:

as an IO exception: this MyError is fatal, report and die probably
as an ExceptT failure: this MyError is a normal outcome, handle it please

So this is equivalent to attaching an extra bit of information to each exception type, fatal vs non-fatal. I have two objections to this.
First objection, which I have mentioned earlier:

This is not a convention that other libraries use. For instance, readFile throws an exception when a file doesn't exist, although it's a totally expected situation, and the type of readFile should be actually IO (Either FileNotFound Text).

How we can solve this: create wrappers for libraries we use, which change the exception handling conventions to more sensible ones, where ExceptT and Either are used for normal outcomes.
Alternatively: accept this as a fact, and write code that assumes that IO exceptions can happen even in normal situations, and shouldn't always crash the node: there are places where we might want to throw, and places where we might want to handle IO exceptions. If we take this position, then being thrown as an IO exception doesn't have this "fatal" bit of information anymore. Then being able to throw MyError both as an IO exception and via ExceptT only creates confusion.
Second objection: unlike the free monads example that you cite, we do not actually gain anything by reusing the same exception type for throwing in IO and ExceptT. The behavior is the same: early exit from a monadic computation. It's just different means to achieve the same goal. Being able to throw exceptions of the same type by different means is simply redundant. (Unless you assume this "fatal" vs "non-fatal" distinction, which I covered in the first point).

You have a bold assumption that every IO exception is documented.

No I never made that assumption. However it is a fact (for better or for worse) that when you deal with IO, you deal with the possibility of exceptions.

Unfortunately, I think rewriting everything to such a monad would be an insane engineering effort.

Absolutely. Let's not do that.

So, our options are:
a) track exception in types: too much engineering effort
b) track exceptions in documentation: too much maintenance effort, no static checking, will get out of date and incorrect
c) do not track exceptions: creates potential for confusion for whether exceptions were handled properly
I suggest we pick (c), and ease the reasoning by making the sets of exceptional and non-exceptional failures disjoint. Statically enforce it with simple one-liners.

Does this eliminate the potential for confusion? It means I know that a particular type cannot be thrown in the usual IO exception throwing system. It doesn't guarantee that I haven't missed an exception that I must catch regardless... Yes, I see now, this whole argument is pinned on whether the exception type itself carries all of the meaning. On whether, if you want to catch MyError in an ExceptT MyError m t, then you must want to catch MyError in m as well.

No, I think this is the sort of reasoning that leads to "boolean blindness" and similar phenomena.

Boolean blindness is about throwing away information.

Often we use "dumb" datatypes because we are too lazy to create newtypes or data types with clear semantics.

Sometimes it's appropriate to make a newtype, sometimes it's not necessary. There's no hard and fast rule here.

This brings us to exceptions. Okay, you might say that we have different interpretations of the same MyError in different domains:

as an IO exception: this MyError is fatal, report and die probably
as an ExceptT failure: this MyError is a normal outcome, handle it please

So this is equivalent to attaching an extra bit of information to each exception type, fatal vs non-fatal. I have two objections to this.

No, whether it's fatal is not a property of the type itself, nor does the program which throws it declare it to be fatal. It's the caller's choice. Sometimes a nonexistent file is fatal, sometimes it's not. Sometimes a permission error when signalling a process is fatal, sometimes it's not. I would not propose adding this extra bit of information to the type itself.
I'll reiterate: what the MyError means for my program and how I deal with it is not an intrinsic property of the type MyError. It's not always a fatal error when thrown in IO. It depends in which context I'm using it.

No, whether it's fatal is not a property of the type itself, nor does the program which throws it declare it to be fatal. It's the caller's choice. Sometimes a nonexistent file is fatal, sometimes it's not. Sometimes a permission error when signalling a process is fatal, sometimes it's not. I would not propose adding this extra bit of information to the type itself.

Then why not use a simpler decision procedure:

Throw everything as an IO exception. The caller will decide whether the outcome is fatal or not.

Then why not use a simpler decision procedure:

Throw everything as an IO exception. The caller will decide whether the outcome is fatal or not.

Because these IO exceptions don't appear at the type level. Better to use a Left error where possible.

Because these IO exceptions don't appear at the type level. Better to use a Left error where possible.

This leaves me wondering. When would I use an IO exception and when would I use an Either or ExceptT? And when do I use both, but with different semantics? I know there's no hard and fast rule here, but let's at least eliminate this last option to make it easier.

This leaves me wondering. When would I use an IO exception and when would I use an Either or ExceptT? And when do I use both, but with different semantics? I know there's no hard and fast rule here, but let's at least eliminate this last option to make it easier.

It's a good question, when to use an IO exception versus when to give a Left error. I can't imagine you would ever use both in one cohesive definition, like
sillyThingToDo :: Int -> ExceptT MyError IO ()
sillyThingToDo n = do
    when (n == 42) (lift (throwIO MyError))
    when (n == 0) (throwError MyError)
    return ()

But it wouldn't be silly to do this in a modular way
module A where
    a :: Int -> IO ()
    a n = when (n == 42) (throwIO MyError)

module B where
    b :: Monad m => Int -> ExceptT MyError m ()
    b n = when (n == 0) (throwError MyError)

module C where
    c :: Int -> ExceptT MyError IO Bool
    c n = do
        lift (a n)
        b n `catchError` (const False)

a and b are just fine, assuming there is a good reason for a to throwIO rather than use Either MyError () (which there probably isn't, but bear with me). c, as a user of a and b, is completely capable of catching in both contexts, but chooses only to catch from b.

I don't see what makes your "modular" example less silly. Can you clarify?

c, as a user of a and b, is completely capable of catching in both contexts, but chooses only to catch from b.

It's not clear whether this is intentional or that the programmer simply forgot to catch MyError from a.

It's not clear whether this is intentional or that the programmer simply forgot to catch MyError from a.

Right, this is something the programmer must justify, because there's no rule. It could be that MyError from a is in this case fatal, and so should be deferred to the caller (there's nothing c can do about it).
Actually I should have written c like this, in which the MyError from b is eliminated.
module C where
    c :: Int -> IO Bool
    c n = do
        lift (a n)
        -- Catch all MyError in b, so we get ExceptT Void IO Bool
        either absurd pure (runExceptT (b n `catchE` (const False)))

Actually I should have written c like this, in which the MyError from b is eliminated.

Okay, that's different. I'm concerned about terms that have type ExceptT MyError IO a and throw MyError in IO as well as ExceptT.
You seem to agree that's silly. Let's eliminate these cases statically, please?

You seem to agree that's silly. Let's eliminate these cases statically, please?

I agree that sillyThingToDo up there is silly: in the same definition, a MyError is thrown in 2 ways. Maybe there could be a good reason for this, but sure it looks like bad style.
However, I don't think that the first c is a silly thing to do, even though its type is ExceptT MyError IO Bool. The MyError thrown in the underlying IO is semantically distinct from the MyError returned in Left. c presents a contract to its callers: you have to deal with a Left MyError, but there's also IO in here so, as with every IO, there may be other exceptions. These exceptions, however, are deferred to the caller. A MyError raised in this way does not carry the same meaning as a Left MyError. If it did, I would have caught it myself and melded it into the Left MyError.

A MyError raised in this way does not carry the same meaning as a Left MyError. If it did, I would have caught it myself and melded it into the Left MyError.

And either of these cases are legitimate, depending on context.

Can you explain why c (the one with ExceptT MyError IO Bool) isn't silly, but sillyThingToDo is?

Can you explain why c (the one with ExceptT MyError IO Bool) isn't silly, but sillyThingToDo is?

For ease of reading here they are again
sillyThingToDo :: Int -> ExceptT MyError IO ()
sillyThingToDo n = do
    when (n == 42) (lift (throwIO MyError))
    when (n == 0) (throwError MyError)
    return ()

module A where
    a :: Int -> IO ()
    a n = when (n == 42) (throwIO MyError)

module B where
    b :: Monad m => Int -> ExceptT MyError m ()
    b n = when (n == 0) (throwError MyError)

module C where
    c :: Int -> ExceptT MyError IO Bool
    c n = do
        lift (a n)
        b n `catchError` (const False)

sillyThingToDo could easily be generalized to a tighter, more useful type
reasonableThingToDo :: forall m . Monad m => Int -> ExceptT MyError m ()
reasonableThingToDo n = do
    when (n == 42) (throwError MyError)
    when (n == 0) (throwError MyError)
    return ()

whereas c, as a user of a and b, has the IO and ExceptT MyError forced upon it by its components.

whereas c, as a user of a and b, has the IO and ExceptT MyError forced upon it by its components.

Surely it could do this instead:
    c :: Int -> ExceptT MyError IO Bool
    c n = do
        ExceptT (try (a n))
        b n `catchError` (const False)

But you choose not to handle MyError from a. Because the semantics are different. So, why couldn't we have different semantics in sillyThingToDo?

So, why couldn't we have different semantics in sillyThingToDo?

We could. We agree it's bad style though? Maybe there's an example out there of a case in which this actually isn't silly...
Anyway, in this example, it's pretty obvious that MyError is used as an IO exception and in ExceptT. If it weren't obvious, my response would be "make it obvious" by factoring the definition into simple cohesive parts.

We could. We agree it's bad style though? Maybe there's an example out there of a case in which this actually isn't silly...

So is it bad style or not?
I think it is, as well as the "modular" example, which doesn't look all that different to me.

Anyway, in this example, it's pretty obvious that MyError is used as an IO exception and in ExceptT

It's not obvious at all to users of c. And if those users inspect the implementation of c, it's still not obvious, because the actual throwing is happening in modules A and B.
I'd hate to do this sort of chasing to understand throwing behavior of a term.

So is it bad style or not?

I think it is. But our imaginations are limited.

It's not obvious at all to users of c. And if those users inspect the implementation of c, it's still not obvious, because the actual throwing is happening in modules A and B.

It's the same point again: you assume that a MyError thrown by a  has the same meaning as a Left MyError given by c. And therefore that anybody who is concerned with a Left MyError from c also wants to catch every MyError from a. This just isn't true in general.

But our imaginations are limited. <..> This just isn't true in general.

(1) This sort of argumentation can be used to justify anything. Perhaps you have a concrete example in mind? (Although be prepared that I may object to that example that creating separate types would work equally well).

It's the same point again: you assume that a MyError thrown by a has the same meaning as a Left MyError given by c. And therefore that anybody who is concerned with a Left MyError from c also wants to catch every MyError from a.

(2) Indeed, that's how I reason about exceptions. I'm not alone in this — I asked a few coworkers and they all agree that the same type of exception should have the same meaning, regardless of the method of throwing. I even think that you have a tendency to think this way too — that's why you classified your sillyThingToDo as silly.
(3) I can accept (although very reluctant to do that) attaching additional semantics to the method of throwing if and only if you provide concrete semantics for this distinction. That is, we need a decision procedure for developers whether to throw with throwError or throwM, and when to catch with catch or catchError. We don't need this procedure if we assume there's no additional semantics in this, then developers can use whichever is more convenient in a particular situation. But if you claim that the semantics are different, at least specify what it is.

But our imaginations are limited. <..> This just isn't true in general.

(1) This sort of argumentation can be used to justify anything. Perhaps you have a concrete example in mind? (Although be prepared that I may object to that example that creating separate types would work equally well).

Sure, Maybe a. The type is so versatile. Nothing is re-used in different contexts, to mean different things.

(2) Indeed, that's how I reason about exceptions. I'm not alone in this — I asked a few coworkers and they all agree that the same type of exception should have the same meaning, regardless of the method of throwing. I even think that you have a tendency to think this way too — that's why you classified your sillyThingToDo as silly.

That's not why I think it's silly. I think it's silly because a real IO exception (_|_) was used when a plain old regular vanilla value would have sufficed (throwE MyError). And sillier still because the two choices were juxtaposed.

(3) I can accept (although very reluctant to do that) attaching additional semantics to the method of throwing if and only if you provide concrete semantics for this distinction. That is, we need a decision procedure for developers whether to throw with throwError or throwM, and when to catch with catch or catchError. We don't need this procedure if we assume there's no additional semantics in this, then developers can use whichever is more convenient in a particular situation. But if you claim that the semantics are different, at least specify what it is.

Whether or not you accept it, it's built-in to the language. Exceptions even have their own section in the Haskell language report. The meanings of throwIO e and Left e are quite different.
I think a good rule of thumb is: don't throw a (real) exception unless you have a very compelling reason to do so, i.e. using a value such as Left e isn't suitable for reasons x, y, z.

Sure, Maybe a. The type is so versatile. Nothing is re-used in different contexts, to mean different things.

That's not an example of throwing the same exception type via ExceptT and IO with different meaning intentionally attached to each method of throwing.

That's not why I think it's silly. I think it's silly because a real IO exception (_|_) was used when a plain old regular vanilla value would have sufficed (throwE MyError). And sillier still because the two choices were juxtaposed.

First, I mentioned it earlier and I'm saying it again: exceptions in IO aren't _|_ (bottom). See for yourself:
throwIO e `seq` return () = return ()

Second, we are talking about using the throwing method to convey semantics. Now you claim that using IO when ExceptT is available is silly. So there's no useful semantics for IO exceptions as opposed to ExceptT? Your arguments seem contradictory to me.

Whether or not you accept it, it's built-in to the language. Exceptions even have their own section in the Haskell language report. The meanings of throwIO e and Left e are quite different

First, no one is arguing whether throwIO and Left are different mechanisms in the language. The claim is that they are used for the same purpose: early exit from a monadic computation. And the meaning of any particular exceptional value is the same, whether it's thrown via IO or ExceptT.

First, I mentioned it earlier and I'm saying it again: exceptions in IO aren't | (bottom). See for yourself:

Sorry that was imprecise, but I hope you can infer what I meant: throwIO e >>= \t -> -- what is t?.

Second, we are talking about using the throwing method to convey semantics. Now you claim that using IO when ExceptT is available is silly.

No I didn't claim that. It's a part of a particular example that is silly. Each have their merits on their own.

So there's no useful semantics for IO exceptions as opposed to ExceptT? Your arguments seem contradictory to me.

Nor did I make this claim. Of course IO exceptions are useful. I do believe however that it's more often than not preferable to use pure values.

First, no one is arguing whether throwIO and Left are different mechanisms in the language. The claim is that they are used for the same purpose: early exit from a monadic computation. And the meaning of any particular exceptional value is the same, whether it's thrown via IO or ExceptT.

The fact that they are different mechanisms, with different semantics in the language, is a relevant fact in this debate. I also want to stress the point that "early exit" does not do justice: giving a Left MyError is not principally about "exiting a routine", it's about communicating information. The parse failure, for example, delivered by way of Left, stands first and foremost to indicate what it claims: a parse failure. The user is not concerned with when the thing "exited".

Sorry that was imprecise, but I hope you can infer what I meant: throwIO e >>= \t -> -- what is t?.

t isn't bottom here either, bottom is a formalism to denote diverging computations or imprecise exceptions in pure functions. You might be using a different notion, that of a bottom type (Void or forall a. a), which isn't Haskell-specific and isn't related to exceptions at all — in this case, yes, t could be assigned a bottom type. But it's not a bottom that's used to denote exceptions, please don't mix those up.

No I didn't claim that. It's a part of a particular example that is silly. Each have their merits on their own.

Can you specify those merits and a procedure to choose which one to use? This is the third time I'm asking this.

Can you specify those merits and a procedure to choose which one to use? This is the third time I'm asking this.

Well, using Either e, you get a tighter type: callers know that there could be a Left and must deal with it. It's also pure, and I think I don't need to convince you that's a good thing.
As for real IO exceptions: sometimes crashing your program is the right thing to do. The asynchronous variety are also useful but they're not exactly relevant here.
I'm not sure I can give you a decision procedure, and I'm not sure you should expect one. Use your judgement. We're talking about guidelines aren't we?

giving a Left MyError is not principally about "exiting a routine", it's about communicating information

An IO exception MyError communicates the same information. If you think it communicates something else, specify the difference, together with a decision procedure on which way of communication to use in what circumstances.

The user is not concerned with when the thing "exited", whatever that means in a non-strict programming language.

I think there's a simple way to define early exit for monadic computations. m exhibits "early exit" behavior when for any f we have
m >>= f = m

I'm not sure I can give you a decision procedure, and I'm not sure you should expect one. Use your judgement. We're talking about guidelines aren't we?

Yes, the guidelines should guide. No decision procedure = no guidance. You'll notice that in the current version, guidelines provide specific decision procedures on which handling methods to use.

As for real IO exceptions: sometimes crashing your program is the right thing to do.

As long as we have catch, there's no implication that an IO exception will crash anything at all.

Seems like a fair characterization of early exit. It certainly makes sense for IO, and in cases where >>= is used, because of the evaluation order it implies.
f <$> Left e <*> Right 42 = Left e

Can we really speak on an "exit" here? The program could evaluate Right 42 before it evaluates Left e.
Speaking of "early exit" when throwing an IO exception make sense, I'm just challenging the terminology in the context of pure programs. The term ExceptT (Left e) does not itself express "early exit". Yes it can be used in a monadic expression to give something that looks and feels like early exit, but that's contextual.
Sorry if I seem pedantic here. I don't wish to annoy you, but I think digging into the terminology is enlightening.

An IO exception MyError communicates the same information. If you think it communicates something else, specify the difference, together with a decision procedure on which way of communication to use in what circumstances.

I didn't claim that throwing it as an IO exception doesn't communicate the same information. But now that you mention it I will say that it doesn't communicate it quite as well: the type of the thing that throws it makes no mention of MyError.

Yes, the guidelines should guide. No decision procedure = no guidance. You'll notice that in the current version, guidelines provide specific decision procedures on which handling methods to use.

You certainly can have guidance without a decision procedure. But perhaps I took you too literally regarding what "decision procedure" means. Is it correct to say that you want a list of advisory statements about the use of IO exceptions?
I'll try to oblige. Here's an easy one: if you don't have IO, don't throw an IO exception, and never add any constraints just so that you can do so. That's to say, if you're not already doing IO for your business, then don't throw an IO exception.

As for real IO exceptions: sometimes crashing your program is the right thing to do.

As long as we have catch, there's no implication that an IO exception will crash anything at all.

Sure there is: throwIO e is a program. It crashes. catchAll (throwIO e) does not crash, but throwIO e crashes. If I want my program to crash, I can make it crash. Some user of my program can make it not crash, but I've still made my program crash.

Can we really speak on an "exit" here? The program could evaluate Right 42 before it evaluates Left e.

Is the evaluation order relevant here? The definition of early exit that I gave above, m >>= f = m, works for both strict and lazy languages.

I didn't claim that throwing it as an IO exception doesn't communicate the same information. But now that you mention it I will say that it doesn't communicate it quite as well: the type of the thing that throws it makes no mention of MyError.

Oh, I agree! That's why I want to exclude redundancy: if throwing MyError with ExceptT is just a better way of doing the same with IO, then let's statically guarantee that there aren't terms in our program that throw MyError in both ways.

I'll try to oblige. Here's an easy one: if you don't have IO, don't throw an IO exception, and never add any constraints just so that you can do so. That's to say, if you're not already doing IO for your business, then don't throw an IO exception.

That's very good advice, thanks! That's also something that our guidelines already recommend: in pure code, use ExceptT and Either. What we're discussing here is when we already have IO, MonadIO m, or potentially impure code that can be instantiated to m ~ IO. And in this case, all I want is to guarantee that ExceptT and IO aren't used for the same type of exception simultaneously.

Sure there is: throwIO e is a program. It crashes.

I don't think I follow your terminology. throwIO e is a term, not a program. A program consists of types, terms, etc, and in the end compiles to a binary that the user can run. When I use throwIO e, it's not something that crashes either, consider main = const (return ()) (throwIO e). Not even a mention of catch. A program crashes when there's a throwIO e term in it that gets executed (because it's a part of the main term) and doesn't get caught.

I don't think I follow your terminology. throwIO e is a term, not a program. A program consists of types, terms, etc, and in the end compiles to a binary that the user can run.

Yes unfortunately the terminology hasn't really caught on. In pure functional programming we like to talk about composing programs, transforming programs, etc. We build complex programs out of simpler programs. throwIO e is a (relatively simple) program, catchAll (throwIO e) is also a program.
But I'm happy to call them terms instead.
Do you agree there is a difference between "program" and "executable"?

When I use throwIO e, it's not something that crashes either, consider main = const (return ()) (throwIO e). Not even a mention of catch. A program crashes when there's an uncaught exception in it, and the throwIO e term is a way of throwing such an exception, but it must be executed as part of main and not get caught in order to cause a crash.

Sure, const (return ()) (throwIO e) has used my crashing program to construct a program which does not crash.

Is the evaluation order relevant here? The definition of early exit that I gave above, m >>= f = m, works for both strict and lazy languages.

Yes it's relevant and yes it makes sense when we have >>=. I was just digging a little deeper that's all. "Early exit" is laden with connotations from procedural/imperative programming which must be treated with skepticism in the context of pure FP.

That's very good advice, thanks! That's also something that our guidelines already recommend: in pure code, use ExceptT and Either. What we're discussing here is when we already have IO, MonadIO m, or potentially impure code that can be instantiated to m ~ IO. And in this case, all I want is to guarantee that ExceptT and IO aren't used for the same type of exception simultaneously.

RE a type that can be specialized to IO: you can't throw an IO exception unless you commit to the specialization, or add a constraint like MonadThrow. Don't do this. You didn't need IO, you didn't need MonadThrow, so don't commit to it. Give Left instead. If you have MonadIO then I guess you can throw an IO exception. Here you have to use your judgement. How about this as a first iteration: if this failure case was caused by the caller's input, and the caller could avoid it by giving different inputs, then don't throw an IO excecption.

Oh, I agree! That's why I want to exclude redundancy: if throwing MyError with ExceptT is just a better way of doing the same with IO, then let's statically guarantee that there aren't terms in our program that throw MyError in both ways.

My position is that this depends on context and is not a property of the MyError type itself.

Oh, I agree! That's why I want to exclude redundancy: if throwing MyError with ExceptT is just a better way of doing the same with IO, then let's statically guarantee that there aren't terms in our program that throw MyError in both ways.

My position is that this depends on context and is not a property of the MyError type itself.

But I do have to admit, this isn't consistent with the way things are: in Haskell you do have to declare an Exception instance on a type, so whether something is used as an IO exception is de facto a property of the type, for better or for worse.

Do you agree there is a difference between "program" and "executable"?

Not sure. Is there? You seem to call any IO action a program, I usually call them IO actions or "subroutines", "procedures", etc. A program sounds synonymous to executable to me. But unlike you I don't find pondering terminology productive, natural language is always ambiguous anyway, I'm willing to avoid the term "program" altogether in favor of "IO action" for the sense in which you use it and "executable" for the sense in which I tend to use it.

Yes it's relevant and yes it makes sense when we have >>=. I was just digging a little deeper that's all. "Early exit" is laden with connotations from procedural/imperative programming which must be treated with skepticism in the context of pure FP.

Why, writing in Haskell, would I be worried about connotations form other languages? No one confuses Template Haskell with C++ templates, for instance. Or C# generics with Haskell Generic. Or monadic return with C++ return (OK, except for beginners). Etc. All similarities are superficial.
But if you're worried about overloaded terminology, do you have a better term for the m >>= f = m property of the m term? It also implies const <$> m <*> k = m, of course, so it's not limited to monads where evaluation order is forced by data dependencies.

RE a type that can be specialized to IO: you can't throw an IO exception unless you commit to the specialization, or add a constraint like MonadThrow. Don't do this.

Well, the problem here is that there are classes that don't necessarily imply using IO, but might be used with IO nevertheless. MonadThrow, for instance, can be used in pure programs, it has instances for Maybe, e ~ SomeException => Either e, [], etc. User-defined classes can have instances for pure monads that don't throw and IO instances that do. And let's not forget that classes are basically implicitly passed records of methods, so the problem is actually a special case of a more general one, which I have demonstrated earlier:
confusing :: forall t m. Monad m => m Bool -> ExceptT MyError m ()

As long as our "pure" monadic term can be passed an "impure" (IO-capable) monadic term as input, the whole thing is potentially impure.

How about this as a first iteration: if this failure case was caused by the caller's input, and the caller could avoid it by giving different inputs, then don't throw an IO excecption.

Okay, I can't immediately see a problem with this (except for nitpicks as to what counts as user input). But then we seem to have two disjoint cases:

caller's input can cause the error: return it as Left
caller's input cannot cause the error: throw it as an IO exception

There seems to be no case when both would make sense. So let's rule these out to ease reasoning for the caller.

My position is that this depends on context and is not a property of the MyError type itself.

I agree that disallowing it on per-type basis is a bit of an overkill. What I really care about is that there is no term of type IO (Either MyError a) or ExceptT MyError IO a that also throws MyError in IO. When we have several ways of throwing, there's an additional bit of information. We can have

MyError returned in Left
MyError thrown as an IO exception

I claim this bit of information is usually ignored by the programmer, and when it's not, there's no consistent semantics for it. You seem to oscillate between

giving meaning to this bit of information, but not specifying what this meaning is:

It's the same point again: you assume that a MyError thrown by a has the same meaning as a Left MyError given by c. And therefore that anybody who is concerned with a Left MyError from c also wants to catch every MyError from a. This just isn't true in general.

not giving meaning to this bit of information:

I didn't claim that throwing it as an IO exception doesn't communicate the same information. But now that you mention it I will say that it doesn't communicate it quite as well: the type of the thing that throws it makes no mention of MyError.

I am very worried about this bit of information. I want to get rid of it. Free everyone of reasoning about it, minimizing reasoning overhead and confusion. But if you insist on its usefulness, I ask for specific semantics for this bit information, and a reasonably defined procedure for deciding what to set it to in various circumstances (when throwing), and what to expect from it (when catching). If the decision procedure results in disjoint sets of cases, we'd still want to get rid of this bit of information.

Not sure. Is there? You seem to call any IO action a program, I usually call them "IO actions" or "subroutines", "procedures", etc. A program sounds synonymous to executable to me. But I don't find pondering terminology productive, natural language is always ambiguous anyway, I'm willing to avoid the term "program" altogether in favor of "IO action" for the sense in which you use it and "executable" for the sense in which I tend to use it.

Isn't this a program?
not True = False
not False = True

Why, writing in Haskell, would I be worried about connotations frm other languages? No one confuses Template Haskell with C++ templates, for instance. Or C# generics with Haskell Generic. Or monadic return with C++ return (OK, except for beginners). Etc. All similarities are superficial.
But if you're worried about overloaded terminology, do you have a better term for the m >>= f = m property of the m term? It also implies const <$> m <*> k = m, of course, so it's not limited to monads where evaluation order is forced by data dependencies.

We have a term that's more appropriate: zero element, or absorbing element, a la 0 * x = 0 or m >> x = m. Do you see how "early exit" is a little dishonest here? Yes, that applicative identity is implied by the monadic one, but the applicative one does not enforce any evaluation order. Nothing is "exited"; nothing necessarily "happens" earlier than the other; nothing necessarily "happens" at all.

Well, the problem here is that there are classes that don't necessarily imply using IO, but might be used with IO nevertheless. MonadThrow, for instance, can be used in pure programs, it has instances for Maybe, e ~ SomeException => Either e, [], etc. User-defined classes can have instances for pure monads that don't throw and IO instances that do. And let's not forget that classes are basically implicitly passed records of methods, so the problem is actually a special case of a more general one, which I have demonstrated earlier:
confusing :: forall t m. Monad m => m Bool -> ExceptT MyError m ()
As long as our "pure" monadic term can be passed an "impure" (IO-capable) monadic term as input, the whole thing is potentially impure.

Well, confusing is certainly pure. It can't do any side-effects on its own. We know that if it is used in any side-effecting way, then it must be the parameter that did the effects.
How's this for a rule: never use MonadThrow? If you want to throw an IO exception, specialize your type.

We can have

MyError returned in Left
MyError thrown as an IO exception

I claim this bit of information is usually ignored by the programmer, and when it's not, there's no consistent semantics for it.
...
I am very worried about this bit of information. I want to get rid of it.

Don't be so worried about it. If this actually causes confusion for the developer, the problem is in fact a deeper problem with the design of the program itself.

Free everyone of reasoning about it, minimizing reasoning overhead and confusion.

And simultaneously adding a confusing ghost Exception instance to a bunch of types. I'll see instance Exception MyError in the haddocks, but I'll get a type error when I try to throw it as an exception.

But if you insist on its usefulness, I ask for specific semantics for this bit information, and a reasonably defined procedure for deciding what to set it to in various circumstances (when throwing), and what to expect from it (when catching). If the decision procedure results in disjoint sets of cases, we'd still want to get rid of this bit of information.

Specific semantics for IO exceptions versus pure values?

Well, confusing is certainly pure. It can't do any side-effects on its own. We know that if it is used in any side-effecting way, then it must be the parameter that did the effects.

To follow up on this "potentially impure": is const potentially impure? const launchMissiles () is impure...

Isn't this a program?

No, it's a function :slightly_smiling_face: I think this is out of scope.

We have a term that's more appropriate: zero element,

mzero has two laws:
mzero >>= f  =  mzero
v >> mzero   =  mzero

We're interested in the first one only. Okay, I could use "left zero".

Do you see how "early exit" is a little dishonest here?

No, I don't think so. Take "left zero" for example (as in mzero >>= f = mzero), there's no number "zero" here, is the term dishonest? No, it's overloaded.
In case of "early exit", there's the "early" bit — there's no order of evaluation, but there's clearly an order of effects (in case of both Monad and Applicative), and there's "exit" (no further effects will be executed). As an example effect, take Writer — the monoidal accumulator will change right until we deal with early exit (due to ExceptT or MaybeT on top of the Writer):
ghci> runWriter . runMaybeT $ do tell "a"; tell "b"; MaybeT (return Nothing); tell "c"
(Nothing,"ab")

So as I look at it, both "early" and "exit" make sense.

If this actually causes confusion for the developer, the problem is in fact a deeper problem with the design of the program itself.

Right. That's why those guidelines must prevent these deeper problems. One approach is to get rid of this information bit entirely. Another is to give specific semantics for it (which I don't want to pursue because it'll be harder to enforce, there'll be no static checking, but it's still better than nothing).

How's this for a rule: never use MonadThrow? If you want to throw an IO exception, specialize your type.

Yes, that's a good rule. In fact, as part of our monad guidelines, we're getting rid of polymorphic monads, so this will gradually become less of a problem. So the "potentially impure" thing a temporary concern (although, as we know, there's nothing more permanent than temporary — no one knows how long the monad refactoring will take). But let's say we're dealing with a concrete monad, ExceptT MyError IO. That's what we should focus on.

And simultaneously adding a confusing ghost Exception instance to a bunch of types. I'll see instance Exception MyError in the haddocks, but I'll get a type error when I try to throw it as an exception.

Haddock displays instance contexts, so TypeError will be clearly visible.

Specific semantics for IO exceptions versus pure values?

Yeah. Consider this piece of code:
confusingThrowBoth :: ExceptT MyError IO a
confusingThrowBoth = do
  ...
  if ...
    then throwError MyError -- (a) when would I do that...
    else throwIO MyError -- ... (b) as opposed to that?

foo =
  result <- try (runExceptT confusingThrowBoth)
  case result of
    Left e -> ... -- (a) when would I expect that...
    Right (Left e) -> ... -- (b) as opposed to that?
    Right (Right a) -> ...

Case (a): we're dealing with an ExceptT failure. Case (b): we're dealing with an IO exception. Upon rereading I noticed that I mislabeled cases (a) and (b) in foo, because dealing with several throwing mechanisms is confusing, and I'll leave it as is as evidence. But anyway, I hope you understand what I'm asking now. The guidelines should specify what meaning we give to this bit of information, of whether MyError was thrown via IO or ExceptT.
As I mentioned earlier, if these cases happen to be non-intersecting, it's still valuable to guarantee this statically. And if they're intersecting, your earlier example of sillyThingToDo isn't silly after all.

No, it's a function

This program computes the fibonacci sequence, no?
fibs = 0 : 1 : zipWith (+) fibs (tail fibs)
Is it not a program?

mzero has two laws:
...
We're interested in the first one only. Okay, I could use "left zero".

Not mzero, I'm referring to the more general notion from algebra. Sure, "left zero".

Do you see how "early exit" is a little dishonest here?

No, I don't think so. Take "left zero" for example (as in mzero >>= f = mzero), there's no number "zero" here, is the term dishonest? No, it's overloaded.

You really don't appreciate connotation? "Zero element" is an established term in mathematics, equipped with a formal definition, and no allusions to evaluation order or "things happening".

So as I look at it, both "early" and "exit" make sense.

For particular examples, but not in general. Zero element is preferable.

If this actually causes confusion for the developer, the problem is in fact a deeper problem with the design of the program itself.

Right. That's why those guidelines must prevent these deeper problems.

My argument is that the root problem should be fixed. Guidelines are akin to a treatment, but we'd rather have a cure.

Case (a): we're dealing with an ExceptT failure. Case (b): we're dealing with an IO exception. Upon rereading I noticed that I mislabeled cases (a) and (b) in foo, because dealing with several throwing mechanisms is confusing, and I'll leave it as is as evidence. But anyway, I hope you understand what I'm asking now. The guidelines should specify what meaning we give to this bit of information, of whether MyError was thrown via IO or ExceptT.

Refactor the definitions so that they aren't confusing anymore.

This program computes the fibonacci sequence, no?

This term evaluates to the fibonacci sequence.

Is it not a program?

No, it's a CAF expression :slightly_smiling_face:
I'm sorry, I really don't think this thread is relevant to the PR. I get it, you're calling any computation a program, that's totally OK with me, I'll keep this in mind in our further conversations.

You really don't appreciate connotation? "Zero element" is an established term in mathematics, equipped with a formal definition, and no allusions to evaluation order or "things happening".

"Early exit" has precedence, I've quoted a bit of documentation from the exceptions package. This bit of documentation was immediately understandable to me, so I feel that "early exit" has the right connotation. Maybe it has a different connotation for you, but I normally don't reason about evaluation order Haskell unless performance is concerned, so I see no problem with this term.
It's OK, I'll remember to use "left zero" in the future when talking to you to avoid misinterpretation.

My argument is that the root problem should be fixed. Guidelines are akin to a treatment, but we'd rather have a cure.

Oh how I agree. And I offer a cure: disallow using the same exception type with both throwing mechanisms. Do you have a better cure?

Refactor the definitions so that they aren't confusing anymore.

Right. How about a small refactoring after which the same exception type, MyError, won't be thrown via both ExceptT and IO? Hmmm :slightly_smiling_face:

I'm sorry, I really don't think this thread is relevant to the PR. I get it, you're calling any computation a program, that's totally OK with me, I'll keep this in mind in our further conversations.

I'm calling any functional program a program. Just as strawberry jam is jam. And I was hoping to lead you to the realisation that it really is distinct from "executable".

Oh how I agree. And I offer a cure: disallow using the same exception type with both throwing mechanisms. Do you have a better cure?

That's still treatment. It doesn't fix the problem: poorly designed functional programs that are difficult to understand.

Refactor the definitions so that they aren't confusing anymore.

Right. How about a small refactoring after which the same exception type, MyError, won't be thrown via both ExceptT and IO? Hmmm slightly_smiling_face

And they remain confusing. I'm inclined to believe that if the definitions are such that it otherwise wouldn't be clear to the programmer whether they need to catch an exception, then it's a poorly written component.

And they remain confusing. I'm inclined to believe that if the definitions are such that it otherwise wouldn't be clear to the programmer whether they need to catch an exception, then it's a poorly written component.

Yes, let's also make them bug-free and lightning fast while we're at it.
"Don't write bad code" is not an actionable advice, bad code happens. Not everyone is @avieth who can write perfect code on the first try, not everyone can write perfectly understandable components on the first try.
On the other hand, writing NotAnExc MyError => Exception MyError is something everyone can do. Yes it's a treatment, but what you're offering is not a cure, it's "don't get sick, you silly" :slightly_smiling_face:

"Don't write bad code" is not an actionable advice, bad code happens. Not everyone is @avieth who can write perfect code on the first try, not everyone can write perfectly understandable components on the first try.

Please. Everyone can work together to improve it.

On the other hand, writing NotAnExc MyError => Exception MyError is something everyone can do.

Writing good functional programs is something we can all do as well.

what you're offering is not a cure, it's "don't get sick, you silly" slightly_smiling_face

Drop "you silly" and I wouldn't object.

Please. Everyone can work together to improve it.

You could start with stating improvement criteria. For instance, when it comes to exception handling, when should a function throw MyError via both ExceptT and IO?
For instance, I think such code is bad. And if you're working together with me on improving this code, I'll change it so it uses different types for these modes of failure. And then I'll write a NotAnExc MyError => Exception MyError instance to make sure that I or anyone else doesn't introduce this bad behavior by accident.

Writing good functional programs is something we can all do as well.

Mhm. That's what we all strive to do. But I guess if it was possible to simply sit down and write a good functional program, there wouldn't be bad ones.

Drop "you silly" and I wouldn't object.

Well, then there must be preventive measures not to get sick. Maybe, for example, we could disallow throwing MyError via two throwing mechanisms at once, this will rid us of one concern.
If your argument is that we don't need compiler's help to do this, I can't agree with this. Compiler's help is why we're writing in a strongly statically typed language.

If your argument is that we don't need compiler's help to do this, I can't agree with this. Compiler's help is why we're writing in a strongly statically typed language.

No that's not my argument.

Mhm. That's what we all strive to do. But I guess if it was possible to simply sit down and write a good functional program, there wouldn't be bad ones.

Don't belittle the point. You know I did not say it's trivial to write good programs. It's difficult and it takes time and effort, but we're capable of doing it.

Please. Everyone can work together to improve it.

You could start with stating improvement criteria. For instance, when it comes to exception handling, when should a function throw MyError via both ExceptT and IO?

I don't suppose you'll be satisfied with the answer: it depends. Some general rules of thumb:

Make your types as tight as possible.
Make your programs pure wherever possible.

Honestly, I can't imagine a case where you'd want to throw a MyError exception, and give a Left MyError. Nor can I imagine a real-world case in which these guidelines would actually make my job easier.

Honestly, I can't imagine a case where you'd want to throw a MyError exception, and give a Left MyError.

Have we reached consensus on this? Earlier there was a string attached to this, "our imaginations are limited". But I think that even if we encounter the rare case where this would make sense, and I seriously doubt this will happen, — then it's always possible to do one of these:

write a convincing comment that explains why the guidelines were violated
create a different type for the exception anyway

Nor can I imagine a real-world case in which these guidelines would actually make my job easier.

Well, it would make my job easier if I didn't have to think about functions throwing the same type of exception via both methods.
But would it make your job harder if you had to occasionally write instance NotAnExc MyError => Exception MyError? I don't think so, unless typing a couple of words is hard.

Don't belittle the point. You know I did not say it's trivial to write good programs. It's difficult and it takes time and effort, but we're capable of doing it.

I'm sorry, I didn't mean to belittle your point. I'm just stating that being capable of doing something good doesn't mean that we shouldn't prevent doing something bad.

Well, it would make my job easier if I didn't have to think about functions throwing the same type of exception via both methods.

But I don't think you will have to in any case... As a user of a monadic term, you can check its type, and in the vast majority of cases there will be no ambiguity: the monad is general enough to rule out one or both ways of throwing the exception. Furthermore, if there is ambiguity, that's grounds for a bug report. The offending term should be refactored. Of course, assuming everybody follows this ghost Exception instance guideline meticulously, you can be confident in how to catch exceptions. But then again, the term was still too confusing to be used, so doesn't it deserve a peek anyway? It would be prudent to try and factor it in such a way that the pieces which give Left MyError are over a monad which is not capable of throwing IO exceptions.

But would it make your job harder if you had to occasionally write instance NotAnExc MyError => Exception MyError? I don't think so, unless typing a couple of words is hard.

I'm sceptical of making a general rule, which must be followed in every case, for the benefit of a miniscule worry that represents an imperceptible minority of actual cases.

the monad is general enough to rule out one or both ways of throwing the exception

Are we still talking about ExceptT MyError IO and MonadIO m => ExceptT MyError m?

Furthermore, if there is ambiguity, that's grounds for a bug report.

So we're not allowed to use ExceptT over IO, after all? Then this PR can be closed, and the only left zero in IO will be throwIO.

I'm sceptical of making a general rule, which must be followed in every case, for the benefit of a miniscule worry that represents an imperceptible minority of actual cases.

I just think that the rule is so ridiculously easy to follow that it would be a shame to let this minority of actual cases cause a hard-to-notice bug.

So we're not allowed to use ExceptT over IO, after all? Then this PR can be closed, and the only left zero in IO will be throwIO.

I think ExceptT over IO is still allowed. It may help to compose things.

I think ExceptT over IO is still allowed. It may help to compose things.

Okay, but then the types don't guarantee that we don't have MyError thrown both via ExceptT and IO. Previously you said: "that's grounds for a bug report". Can you clarify?

Here are points that I think we agree on:

being able to use ExceptT over IO is convenient, and using ExceptT is better than IO exceptions, because it is reflected in the types
throwing MyError using both mechanisms is bad style, it's confusing
writing a single line of code per failure/exception type is not hard
getting help from the compiler (static analysis) is a good thing

At first our disagreement was about (1). I was arguing that ExceptT is not necessary in IO code, and that's what the guidelines currently state. But after discussing this issue with you, Mikhail, and Ivan, I was convinced otherwise (hence the PR).
Then we discussed (2), and the conclusion is that maybe our imaginations have failed us, but it appears to be true: throwing MyError using both ExceptT and IO is bad style.
I suspect you might not completely agree with (3), but you have not provided a counter-argument. It's easy to write instance NotAnExc MyError => Exception MyError.
And (4) is clearly right.
So according to (4), we should statically disallow what's considered bad style in (2), which can happen because of (1). And doing it is easy because (3).
Let's do this, then.

Okay, but then the types don't guarantee that we don't have MyError thrown both via ExceptT and IO. Previously you said: "that's grounds for a bug report". Can you clarify?

Something along these lines, where ExceptT is used as a tool to compose other monadic terms.
given1 :: Key -> IO ByteString

given2 :: forall m . Monad m => ByteString -> m (Either SomeErrorType Value)

composite :: Key -> IO (Either MyError Value)
composite key = runExceptT $ do
  bs <- withExceptT MyErrorCase1 $ ExceptT $ try (given1 key)
  withExceptT MyErrorCase2 $ ExceptT $ given2 bs

Here, is there any worry that I have mistakenly thrown MyError as an IO exception? Only given1 could have done that, in which case we still pick it up. Also, given1 is completely independent of composite; it could have a good reason to throw MyError as an IO exception.
From the perspective of the caller of composite: there is a Left MyError case that they have to deal with, so little room for error there. But there's also IO, so of course an exception may be thrown. Left MyError is a normal outcome, an IO exception is exceptional. If the caller wants to handle exceptional cases, that can be done.

Something along these lines, where ExceptT is used as a tool to compose other monadic terms.

There are a few reasons I don't find this example compelling.

given2 :: forall m . Monad m => ByteString -> m (Either SomeErrorType Value)

With this type signature, you could just pick m ~ Identity and avoid a monad. But let's assume there are other constraints, some sort of MonadFoo. Then, according to your example, m will be instantiated to IO, and we don't know if the MonadFoo IO instance throws MyError as an IO exception. This makes reasoning difficult and non-local: I now need to consider individual instances for an abstract monad when deciding whether using ExceptT on top is bad style.

Only given1 could have done that, in which case we still pick it up.

What's this MyErrorCase1 wrapper? If you intended to use it, then this is fragile reasoning that will break if MyErrorCase1 is changed to wrap a different exception type — this change can be easily missed during a refactoring. If you didn't mean to use this wrapper, then OK, we can forbid lifting IO actions into ExceptT using lift m or liftIO m, we should use ExceptT (try m) instead — otherwise it's easy to end up in a situation where we have terms that we have agreed are confusing and bad style.

it could have a good reason to throw MyError as an IO exception.

Is there anything preventing it from using a different type instead of MyError? I don't think so.

If the caller wants to handle exceptional cases, that can be done.

If the caller cannot assume that these exceptional cases don't include MyError, then I asked for what the caller can assume (when is MyError throws an an IO exception even though it's also returned in ExceptT or Either) — we have concluded it's bad style. So let's say the caller can assume that if it receives MyError in an Either, then he doesn't have to also deal with it in IO. We can substantiate this assumption by adding the following line:
instance NotAnExc MyError => Exception MyError

Thank you for the example, but I fail to see its appeal. I find it hard to reason about, convoluted, and fragile, for the reasons I explained above.

@avieth Do you agree with my reasoning in https://github.com/input-output-hk/cardano-sl/pull/2507#issuecomment-367115047?


proto: Buffer.Marshal is quadratic on dev branch

I attempted to update an application I maintain from github.com/golang/protobuf v1.0.0 to the dev branch, but encountered a significant regression in CPU and memory usage.
My application has a message type with a single "repeated" field. It uses proto.Buffer to build a large serialized instance of that message out of many smaller ones by calling Marshal with each smaller message. It does not pre-allocate the proto.Buffer.
In v1.0.0, proto.Buffer.Marshal is based on straightforward use of append, which amortizes the cost of allocating a new byte slice when the existing one fills: https://github.com/golang/protobuf/blob/v1.0.0/proto/encode.go#L160-L164
In the dev branch, proto.Buffer.Marshal tries to be clever and allocate only as much memory as it needs immediately: https://github.com/golang/protobuf/blob/9c8fb7a95075eb047ab75e702de52f68ff360f17/proto/table_marshal.go#L2666-L2669
The memory allocations in my real program are attributed to line 2668, p.buf = append(make([]byte, 0, newCap), p.buf...)
The application could be written differently, but that's how it's worked for the past couple years. This is the first application I've attempted to update to protobuf's dev branch.

Here's a reproducer.
With the master branch at v1.0.0, it shows:
$ go test -bench=. -count=5
goos: darwin
goarch: amd64
pkg: repro
BenchmarkProtoBuffer-8   	 3000000	       569 ns/op	     143 B/op	       6 allocs/op
BenchmarkProtoBuffer-8   	 3000000	       520 ns/op	     143 B/op	       6 allocs/op
BenchmarkProtoBuffer-8   	 3000000	       529 ns/op	     143 B/op	       6 allocs/op
BenchmarkProtoBuffer-8   	 3000000	       530 ns/op	     143 B/op	       6 allocs/op
BenchmarkProtoBuffer-8   	 3000000	       514 ns/op	     143 B/op	       6 allocs/op
PASS
ok  	repro	11.106s

With the dev branch at 9c8fb7a95075eb047ab75e702de52f68ff360f17, it shows:
$ go test -bench=. -count=5
goos: darwin
goarch: amd64
pkg: repro
BenchmarkProtoBuffer-8   	  500000	    180284 ns/op	 1004276 B/op	       8 allocs/op
BenchmarkProtoBuffer-8   	  300000	    104283 ns/op	  604249 B/op	       8 allocs/op
BenchmarkProtoBuffer-8   	  300000	    101552 ns/op	  604249 B/op	       8 allocs/op
BenchmarkProtoBuffer-8   	  300000	     99059 ns/op	  604249 B/op	       8 allocs/op
BenchmarkProtoBuffer-8   	  300000	     97260 ns/op	  604249 B/op	       8 allocs/op
PASS
ok  	repro	211.799s

package repro

import (
	"testing"

	"github.com/golang/protobuf/proto"
	"github.com/golang/protobuf/ptypes/struct"
)

func BenchmarkProtoBuffer(b *testing.B) {
	b.ReportAllocs()
	var buf proto.Buffer
	for i := 0; i < b.N; i++ {
		value := &structpb.Value{Kind: &structpb.Value_BoolValue{BoolValue: true}}
		msg := &structpb.ListValue{Values: []*structpb.Value{value}}

		err := buf.Marshal(msg)
		if err != nil {
			b.Fatalf("buf.Marshal(%q); err = %v", msg, err)
		}
	}

	var msg structpb.ListValue
	err := proto.Unmarshal(buf.Bytes(), &msg)
	if err != nil {
		b.Fatalf("proto.Unmarshal(); err = %v", err)
	}
	if have, want := len(msg.Values), b.N; have != want {
		b.Errorf("len(msg.Values); %d != %d", have, want)
	}
}

The total cost in time and memory is O(N^2) in the dev branch rather than O(N) in v1.0.0, but here's the benchstat output with the values of N that go test chose for its default benchtime of 1 second:
name           old time/op    new time/op    delta
ProtoBuffer-8     532ns ± 7%   12006ns ±28%   +2155.00%  (p=0.008 n=5+5)

name           old alloc/op   new alloc/op   delta
ProtoBuffer-8      143B ± 0%    87705B ±28%  +61232.03%  (p=0.008 n=5+5)

name           old allocs/op  new allocs/op  delta
ProtoBuffer-8      6.00 ± 0%      8.00 ± 0%     +33.33%  (p=0.008 n=5+5)

Thank you for the report and reproduction. I'll take a look tomorrow.
\cc @randall77 @LMMilewski

I have a fix and a test case now. I don't know how sensitive the proto.Buffer.Marshal method is to changes, and the benchmark results I'm getting with my laptop (while I use it) are pretty noisy. I also haven't verified that my change addresses the original problem I saw in my application.
I plan to check that and to submit the change by the end of tomorrow.
@dsnet which benchmarks (out of the 105 in the dev branch) are the most important?

@dsnet which benchmarks (out of the 105 in the dev branch) are the most important?

None of them. The benchmarks in this repo aren't that great. Of the 105, did any get drastically worse? If not, I'm not too concerned about them.
Instead, I would run benchmarks on: https://github.com/google/protobuf/blob/master/benchmarks/go_benchmark_test.go.

@rhysh @dsnet @jmhodges After you found proto.Marshal, some of the memory in the library will not be automatically recycled, which will cause a heap. This should be a bug. I found it through pprof tool analysis.


Increase space between next button and form field content

currently at 18px should be closer to 40px

Closed by #2161