cats-effect 🚀 - TestContext should NOT have a deterministic mode

@alexandru In general I agree with you. However, in this case, the issue is considerably subtler than it appears on the surface. The deterministic mode for TestContext is not to work around code which is sensitive to order, but rather to work around issues with how Cats' laws are specified, and more specifically, the definition of equality which is used in modern programming languages. Incoming wall of text. I'll tldr it at the end.

Let's take a step back. Consider the meaning of <-> in laws, both Cats' and Cats Effect's. Procedurally (as in, what is actually executed on the machine), the meaning of this operator is "pseudorandomly generate some set of inputs to the function and verify that, for all generated inputs, the left and the right produce values which are considered to be equal by Eq for that type". That's a very very specific definition, and it's actually a lot stricter than what we really want out of laws.

When we talk about laws mathematically, all we really care about is substitutability. Given some pair of expressions e1 and e2, the statement e1 <-> e2 holds iff we may write e1 in all contexts where we see e2 and vice versa. Thus, the expressions are symbolically equivalent. This definition is undecidable in any programming language which can define induction, though, so we generally move very quickly past it and work with aspirational approximations instead, such as Discipline.

Now, for deterministic pure functions, where the value given some input will always be a given output, this works just fine. However, Fiber, Par, and everything similar are not deterministic. They are pure, but they aren't deterministic. This is a complex class of programs which is considerably less scary than impure code, but considerably harder to work with than what we conventionally think of as pure code, and thus we usually over-approximate by modeling them as "impure". That over-approximation works fine in a lot of cases, but not here.

A more accurate approximation would be to say that for a given input, every pure function must have a deterministic probabalistic distribution of results. An intuitive example of this is a coin. Flipping a coin may be considered a pure function, since the result is not dependent on anything but its inputs, but despite being viewable as a pure function, it still has two possible outcomes, heads or tails, each with a probability of 50%, and we cannot determine in isolation what the discrete result will be.

Here's another way of looking at it. Given a function f : a -> b, given an infinite number of runs for some specific value a, there is a set of observed result values and their associated counts which is generated. For what we conventionally think of as a "pure" function, that set contains a single value. For the "coin toss function", that set contains two values, each with the same count. This is still pure, in a sense, but it's not purity the way we conventionally think of it. It's also not something we can calculate with Discipline, ScalaCheck, and most critically Eq.

This brings us back to Alternative[Fiber]. The problem here is that, for any given discrete evaluation of the |+| function, we can't know what the outcome is going to be: will the left win or the right? This means that the laws cannot be checked in the way we conventionally check them, because Eq only deals with discrete values, and ScalaCheck cannot generate infinite inputs in finite time. But despite that, the laws are still satisfied if we take the definition of substitutability to be in terms of the probabalistic distribution of outcomes, rather than a naive discrete result.

To resolve this, TestContext had its non-determinism selectively removed, basically allowing us to fake a set of discrete outcomes. It most definitely is not testing things accurately, but it's doing about the best we can with the tools we have.

TLDR If we don't do this, then we can't have any instances for Fiber or similar, or at the very least we cannot check their laws in any way. The latter seems immensely dangerous, while the former seems highly constraining and unnecessary. Because this is working around a limitation in the fundamental definition of Eq (and to a lesser extent, ScalaCheck), I feel it is justified. If someone submitted a PR which used the deterministic mode for anything other than this specific case, with the attendant rationale, I would reject it.

djspiewak on 28 Jul 2019

👍2

As the author of said mode I can say I fully agree with @djspiewak 's comment and explanation. I can also add that ideally there should be a relaxed set of laws for Alternative (or a way to pick such test) to open a way for non-deterministic implementations. But, for now, that's the least we could do to have _any_ tested implementation. This is not perfect but also please notice that no ordering guarantees are actually needed (or even desired) for a "real-world" execution of the code under these tests.

marcin-rzeznicki on 28 Jul 2019

Also, I know it might be seen as a bit rude to quote oneself, but let me do it for the sake of moving the discussion away from the already closed PR. I wrote there:

The laws for Alternative demand that its instances form a semiring which excludes any non-deterministic implementation of Alternative (not just this one). This seems to be a serious drawback because non-deterministic instances are very useful in context of this type-class - some say that these laws are over-specified. OTOH if one could somehow test these laws as sets rather than values ie. set of observed values is the same for both sides of a law, then the issue would be gone. At the moment we can do neither. So the least one can do is to make sure that a non-deterministic computation is sane in deterministic context which is why this change was needed and useful. Obviously, one should not over-use it.

marcin-rzeznicki on 28 Jul 2019

👍1

Maybe we should make the ability to have a deterministic mode only available within cats-effect itself? (private field and private[cats-effect] constructor for that mode)

SystemFw on 28 Jul 2019

@djspiewak @marcin-rzeznicki thanks for the explanation, I now understand the issue.

However these tests are fragile. Do they actually give us anything? Maybe we should think of ways to test the probabilistic distribution of results.

Note that the laws get specified not via cats.Eq, but via cats.kernel.laws.IsEq. This type specifies a left-hand side and a right-hand side, which then gets converted into a Prop via this function from cats.laws.discipline:

implicit def catsLawsIsEqToProp[A: Eq](isEq: IsEq[A])(implicit pp: A => Pretty): Prop =
  cats.kernel.laws.discipline.catsLawsIsEqToProp[A](isEq)

implicit def catsLawsIsEqToProp[A](isEq: IsEq[A])(implicit ev: Eq[A], pp: A => Pretty): Prop =
  ???

If you don't define Eq[Fiber[A]], then this function doesn't work. What we could do is to define our own implicit conversion IsEq[F[A]] => Prop for cases such as Par.

Am I missing anything?

However, Fiber, Par, and everything similar are not deterministic. They are pure, but they aren't deterministic.

Note that a Fiber instance isn't pure in the same way that Future isn't pure. Its API is, but the Fiber has a variable in it that's shared between invocations of join and cancel. In other words Fiber is memoized and this is a problem because you can't evaluate it multiple times.

So even if we had the capability of testing a distribution of results, it wouldn't work for Fiber.

alexandru on 28 Jul 2019

👍1

Well, _creating_ a Fiber isn't pure (which is clear from the F[Fiber[F, A]] sig), but once you have one (created correctly), there shouldn't be any problems, no?

SystemFw on 28 Jul 2019

👍1

I don't know, that was just off the top of my head — was wondering what we could do with tests that could work for @djspiewak's coin flip example.

alexandru on 28 Jul 2019

@alexandru

However these tests are fragile. Do they actually give us anything?

Well, I don't think they're fragile (as in _flaky_, if that's what you meant). I think that they show that the implementation is sane iff you eliminate nondeterminsm - I believe this is somewhat useful.

What we could do is to define our own implicit conversion IsEq[F[A]] => Prop for cases such as Par. Am I missing anything?

That's very good point! This is probably the way to tackle the problem outlined by Daniel - I am not sure how to exactly do this but this is how I'd start.

So even if we had the capability of testing a distribution of results, it wouldn't work for Fiber

I am not sure tbh but my intuition aligns with what Fabio said

@SystemFw

Maybe we should make the ability to have a deterministic mode only available within cats-effect itself?

It's constrained to TestContext - can it be used by anything else? But, in general, yes, it should be exclusive to cats-effect testing

marcin-rzeznicki on 28 Jul 2019

It's constrained to TestContext - can it be used by anything else?

TestContext is not used by cats-effect only though, everyone can use it (I use it a lot for example for testing several of my libs). So all I'm saying there is that maybe outside of cats-effect one should only be able to use it with deterministic = false. This obviously does not go to the root of the problem, so let's keep the discussion going :)

SystemFw on 28 Jul 2019

@SystemFw Aw, I didn't even know that it was a published artifact! Thanks for pointing it out.

marcin-rzeznicki on 29 Jul 2019

@djspiewak

But despite that, the laws are still satisfied if we take the definition of substitutability to be in terms of the probabalistic distribution of outcomes, rather than a naive discrete result.

The laws come from Haskell, and they are algebraic, not probabilistic, and they are not satisfied by these instances.

@marcin-rzeznicki

Even a simple measure like creating a alleycats-effect project with instances like these could alleviate concerns.

Possibly a better long-term solution could be to deal with the issue in Cats; i.e. introduce new type classes that allow for non-determinism, which sit in-between their parents and the existing type classes (e.g. determinism being a refinement of the type classes with unspecified determinism, with different laws).

For example, ap is sequential _by law_ even though one can argue sequential _ap_ should be a refinement on a different, more general _ap_ that makes no guarantees on consistency with Monad.

Because the Cats hierarchy is unconstrained, it could make a lot of sense to tackle these issues in the hierarchy than to make instances that are only valid if you "squint".

The question is really how conservatively one should interpret laws; if liberally, then a whole host of instances could be defined in Cats which are currently not defined.

On the topic of this ticket, a deterministic TestContext can lead to tests passing in the presence of conditions that will not be observed in the real world.

jdegoes on 29 Jul 2019

@jdegoes

The laws come from Haskell

Not really - MonadPlus has no specific laws specified in the language report, ditto its Applicative counterpart. Even Haskell wiki which you're probably referring to states that: "there isn't universal agreement on what the full set of laws should look like". There is an excellent essay about the conundrum we've been facing at http://okmij.org/ftp/Computation/monads.html#monadplus

Possibly a better long-term solution could be to deal with the issue in Cats; i.e. introduce new type classes that allow for non-determinism, which sit in-between their parents and the existing type classes (e.g. determinism being a refinement of the type classes with unspecified determinism, with different laws).
Because the Cats hierarchy is unconstrained, it could make a lot of sense to tackle these issues in the hierarchy than to make instances that are only valid if you "squint"

Yes, I agree - that would be perfect. I'd even be in favor of relaxing the laws for Alternative and similar type-classes (as opposed to introducing new ones) whose raison d'etre is to express choice, because the current laws exclude a whole bunch of useful instances.

For example, ap is sequential by law even though one can argue sequential ap should be a refinement on a different, more general ap that makes no guarantees on consistency with Monad.

Only if F[_] is a Monad, right?

On the topic of this ticket, a deterministic TestContext can lead to tests passing in the presence of conditions that will not be observed in the real world.

Right, but as Daniel pointed out - it must never be used for "general purpose" tests. I think that, if this mode stays, if someone used it in a PR, it'd raise a few eyebrows.

marcin-rzeznicki on 29 Jul 2019

@marcin-rzeznicki

Not really - MonadPlus has no specific laws specified in the language report, ditto its Applicative counterpart. Even Haskell wiki which you're probably referring to states that: "there isn't universal agreement on what the full set of laws should look like".

Sure, it comes in different flavors (all useful in different cases), but the laws are always _algebraic_. They are not probabilistic. Algebraic reasoning doesn't work probabilistically.

Yes, I agree - that would be perfect. I'd even be in favor of relaxing the laws for Alternative and similar type-classes (as opposed to introducing new ones) whose raison d'etre is to express choice, because the current laws exclude a whole bunch of useful instances.

I agree with that (relaxing laws, even though in some cases it will be useful to introduce more constrained type classes that extend them with existing laws), and this (Alternative) is not the only case of this happening.

Only if F[_] is a Monad, right?

Yes, but in theory you could drop ap consistency with monad law. Which is precisely what I'd do.

Right, but as Daniel pointed out - it must never be used for "general purpose" tests. I think that, if this mode stays, if someone used it in a PR, it'd raise a few eyebrows.

Maybe it should be documented in a contributors guide to alleviate concerns?

jdegoes on 29 Jul 2019

👍1

@jdegoes

instance Alternative Concurrently where
  empty = Concurrently $ forever (threadDelay maxBound)
  Concurrently as <|> Concurrently bs =
    Concurrently $ either id id <$> race as bs

There you go :smile:

Yes, but in theory you could drop ap consistency with monad law. Which is precisely what I'd do.

Ah, sorry, I didn't understand you :+1:

Maybe it should be documented in a contributors guide to alleviate concerns?

Oh, yes, definitely, great idea! (EDIT: I'll make the change once it's decided that it stays)

marcin-rzeznicki on 29 Jul 2019

@marcin-rzeznicki

Async defines an instance, but it's not law-abiding. It's law-breaking, just like HAXL and many other things in Haskell.

Don't forget Haskell gave us fail :: Stirng -> m a on Monad, fromInteger on Num, and an Applicative that isn't related to Monad, among many other crimes against humanity. 😆

Law-breaking things can be useful. In some cases that's a sign the laws are too strict.

Oh, yes, definitely, great idea! (EDIT: I'll make the change once it's decided that it stays)

👍 👍 👍

jdegoes on 29 Jul 2019

👍1

@alexandru

If you don't define Eq[Fiber[A]], then this function doesn't work. What we could do is to define our own implicit conversion IsEq[F[A]] => Prop for cases such as Par.

I think this would be very cool. It would need a margin of accepted error though, since we cannot run infinite trials, and the tests would ultimately not be deterministic (even though we could contrive them to pass with a high probability). We simply cannot determine a completely accurate infinite distribution via discrete sampling.

Note that a Fiber instance isn't pure in the same way that Future isn't pure. Its API is, but the Fiber has a variable in it that's shared between invocations of join and cancel. In other words Fiber is memoized and this is a problem because you can't evaluate it multiple times.

I believe the fact that you cannot create a Fiber directly (but only within the context of an effect) resolves this issue. At the very least, I can't think of a way that you can violate purity with it, and if you could, that would be a problem for other things as well.

@jdegoes

they are algebraic, not probabilistic, and they are not satisfied by these instances.

They are indeed algebraic, which is precisely why this whole line of reasoning is justified. For example, take the definition of left distributivity:

((fa |+| fa2).map(f)) <-> ((fa.map(f)) |+| (fa2.map(f)))

This holds perfectly for Fiber[F, A], despite the fact that we cannot say exactly what either side will return. It is notable that we cannot even evaluate the following with a non-deterministic TestContext:

((fa |+| fa2).map(f)) <-> ((fa |+| fa2).map(f))

When algebraic identity itself is non-evaluable, your definition of equality is overly strict. That is the case here. Your sentence is actually a non-sequitur, as the algebraic nature of the laws is precisely what makes them probabilistic in this case: Fiber is probabilistic, and thus so are any laws which may be applied to it. Laws only care about substitutability. They are, as you say, algebraic, and in this case substitutability is satisfied unless you can show otherwise.

Possibly a better long-term solution could be to deal with the issue in Cats; i.e. introduce new type classes that allow for non-determinism, which sit in-between their parents and the existing type classes (e.g. determinism being a refinement of the type classes with unspecified determinism, with different laws).

Nothing in the current typeclasses forbids non-determinism. In fact, they have to deal with it already. For example:

val ioa = IO(math.random)
ioa.flatMap(IO.pure(_)) <-> ioa

We can't deterministically test the above in the manner we conventionally test laws, and yet the laws are still there, still being usefully applied. No one would suggest that IO is not a monad.

Restating my earlier more explicitly: the laws say nothing about determinism, one way or another. They are simply a question of symbolic substitutability. This implies then that if the type under examination is itself deterministic, then so must be any concrete test of the laws. If the type under examination is non-deterministic (such as Fiber, and really also IO), then any concrete test of the laws must also be non-deterministic (or must cover an incomplete domain, as in the case of today's Arbitrary[IO[A]]).

On the topic of this ticket, a deterministic TestContext can lead to tests passing in the presence of conditions that will not be observed in the real world.

This is certainly true. I'm not aware of any particular way around it though, at least not in Scala or in any other Vonn Neuman derived model of computation.

Algebraic reasoning doesn't work probabilistically.

As I showed above, this is false, and also doesn't make any sense. Presumably statisticians, combinatoricists, and more all use algebra. The mere lack of determinism doesn't in any way obviate algebraic reasoning. In some sense, it actually generalizes it.

djspiewak on 29 Jul 2019

👍2

Your sentence is actually a non-sequitur, as the algebraic nature of the laws is precisely what makes them probabilistic in this case: Fiber is probabilistic, and thus so are any laws which may be applied to it.

To say that x = y is to say that every occurrence of x may be replaced by y without a change in the meaning of the program.

This is an algebraic law, not a "probabilistic law". A _probabilistic law_ is something like _X_ has distribution _F(x)_; which only ascribes a probability to observations of _X_.

Probabilistic laws are completely and totally unconnected to the algebraic laws of statically-typed functional programming; there is no relation; and there is no formal meaning to the phrase "Fiber is probabilistic" (that I am aware of; please define it formally if you think otherwise).

In the case of distributive and associative laws, we can replace any occurrence of the left-hand side with the right-hand side, or visa versa; and chain that with other identities, ad infinitum, ending up with a program whose meaning is exactly the same as the one we started with (modulo CPU and memory usage).

In any case where this does not hold, the algebraic laws are not satisfied.

Nothing in the current typeclasses forbids non-determinism. In fact, they have to deal with it already. For example:

We can show symbolically through analysis of code (_not_ through the unit tests in Cats Effect) that IO(xxx) is definitionally equal to IO(xxx).flatMap(IO.pure); this can be done by ascribing a meaning to the apply constructor of IO rooted in the AST of the Scala code being captured.

In contrast, I am not aware of any way to do that with left distributivity, precisely because race is nondeterministic and lacks a clear denotative semantic.

I've stated my views on the matter (introducing weaker/more general type classes that do not have to satisfy the same laws)—I'm content to rest my case here.

jdegoes on 29 Jul 2019

Well, content to rest after this simple counter-example that _trivially "breaks" left distributivity_:

@tailrec
def work(n: Long)(v: A): A = if (n <= 0L) v else work(n - 1L)(v)

def f[A](value: Either[A, A]): A = value.fold(work(Long.MaxValue)(_), identity)

val fa1: F[String] = F.pure(Left("foo"))
val fa2: F[String] = F.pure(Right("bar"))

// Will terminate half the time with "bar", half the time with "foo":
(fa1 |+| fa2).map(f(_))

// Always terminates "immediately" with "bar"
(fa1.map(f(_))) |+| (fa2.map(f(_)))

One effect that always produces "bar" is in no way "probabilistically equal to" another effect that produces "bar" only half the time.

race allows you to lift "CPU usage" (not classically considered in notions of equality) into value-space where it may be observed; while this example is contrived, it's easy to imagine more realistic examples where the effects of such a transformation would still be manifestly detectable.

It's fine to keep the instance, but it definitely does not satisfy laws, regardless of the existence of a specially-configured TestContext that removes the defining feature of race.

jdegoes on 29 Jul 2019

@jdegoes
A small nitpick
I guess you meant:

val fa1 = F.pure(Left("foo"))
val fa2 = F.pure(Right("bar")))

In the deterministic context the law will be upheld, otherwise yes, the instance does not satisfy the laws which we've already known - the laws exclude any non-determinism. That's a very fine example but isn't it stating the obvious?

marcin-rzeznicki on 29 Jul 2019

@marcin-rzeznicki Good catch!

I think the example is useful because it is perhaps the simplest example that shows that not even a hand-wavy "probabilistically equal" argument applies. In this case, "bar" is produced with 100% probability in the second case, but only 50% probability in the first case, assuming a fair race.

Any transformation that has this effect on your program (e.g. going from producing 50% "foo" to producing 0% "foo") has not preserved the meaning of the program; and there is therefore no handy-wavy sense in which the algebraic laws are satisfied.

They're broken, suggesting either alleycats-effect or new type classes or a change in the law-abiding philosophy previously expressed by Cats maintainers.

jdegoes on 29 Jul 2019

This is an algebraic law, not a "probabilistic law". A probabilistic law is something like X has distribution F(x); which only ascribes a probability to observations of X.

Probabilistic laws are completely and totally unconnected to the algebraic laws of statically-typed functional programming; there is no relation; and there is no formal meaning to the phrase "Fiber is probabilistic" (that I am aware of; please define it formally if you think otherwise).

It's trivial to define and I'd be happy to do so formally at some other time, but there are more pressing matters on this thread. We're literally saying the same thing: substitutability of expressive form is the only thing that matters, whether the result of a calculation is deterministic or not is irrelevant, so long as the substitution makes no difference in the output. When the result of a calculation is non-deterministic, the most reasonable way to model it is probabalistically, which means that one way we can reason about whether or not the substitution has made a difference in the output is by deriving infinite distributions.

As I said, we're saying the same thing, you're just not taking it to its logical conclusion. But also as I said, there's a more important point here.

One effect that always produces "bar" is in no way "probabilistically equal to" another effect that produces "bar" only half the time.

I wish you had simply led with this. It would have circumvented all of the diatribes. Concrete counter-examples are vastly more useful than intuitionist arguments.

First off, clearly your example is valid and neatly demonstrates the problems with the laws. Thank you, I sincerely appreciate it. Second, it's interesting that we don't even need to go to Alternative to see problems. I'm relatively certain that Functor alone is enough, particularly when composed with Functor[IO] and the difference between pure and map(pure) in terms of how it relates to Fiber's evaluation scheduling.

I'm relatively certain that we could make this lawful, but only by playing some slightly tricky games. Intuitively, we cannot define Alternative for Fiber, but we could define it for Coyoneda[Fiber]. Thus, one approach here would be to actually embed Coyoneda within Fiber itself (similar to what is conventionally done for Free). I'm not sure whether or not this is worth doing though, tbh.

race allows you to lift "CPU usage" (not classically considered in notions of equality) into value-space where it may be observed

This is a very good way to think about it. It also illustrates a reasonable maxim: once Fiber has been created, it must be impossible to "add" to its scheduled calculation in a way which would happen prior to a race.

djspiewak on 29 Jul 2019

So looping back around and distilling the conclusion…

I'm almost positive we can make these instances lawful. It doesn't come for free, either in terms of work or complexity. It makes Fiber a little richer in that it would embed a variant of Coyoneda such that the mapping functions will only be sequenced after racePair, and that complexity will get exposed to implementors of Concurrent (since this would need to be specifically handled in each racePair implementation). We can probably make the free functor machinery optional in case implementations want to define their own Fiber#map, but then they must do essentially the same thing.

The alternative is to just delete the instances. So let's take a quick step back and decide how badly we want Alternative[Fiber] (or Functor[Fiber], for that matter).

djspiewak on 29 Jul 2019

Okay sorry for the spam… Dug into this further and not only would we need all of the above, but we would also need a more explicit representation of cancelation. This is possible (and desirable for other reasons), but not without much larger structural changes. We're in Cats Effect 3 territory. I'm going to PR a revert for this. Sorry @marcin-rzeznicki. I still like the instances, and they're doable, just not with the data structures where they currently are.

djspiewak on 29 Jul 2019

@djspiewak I have enormous respect for people who can alter previously expressed views. 👏

I suggest that in addition to the revert, the instance be moved to a new project alleycats-effect, because I think it's useful even if it's not law-abiding, and this would preserve the investment that @marcin-rzeznicki placed in development of the feature.

Then further, perhaps as per @alexandru's concerns, the deterministic mode for TestContext could be removed to discourage future usage.

jdegoes on 29 Jul 2019

👍1

My reverting PR removes the deterministic mode entirely. Regarding @marcin-rzeznicki's work, my plan is to actually just revive it wholesale as part of the CE 3 effort. Fiber has to be enriched in 3.0 anyway to support other features, so I think this a good fit. The real trick is figuring out where we want the coyoneda mechanism to live, and if there's a better way of doing it than what I've expressed in the PR description.

djspiewak on 29 Jul 2019

👍1

@jdegoes Ah, right, I forgot abut the "probabilistic" argument. So assumption that law-abiding will get fixed with better tests is now lost. Nice - thanks for the example. alleycats-effect sounds like a good idea, and I will be happy to contribute.

@djspiewak Maybe a better solution than what is proposed is to either drop some of the problematic laws in cats, or create a new, relaxed typeclass. My reasoning here is that dropping is going to have far more reaching impact and enable more implementations, beyond cats-effect.

I am not sure if I understand coyoneda solution fully. The way I understand Coyoneda - please correct me if I'm wrong - is that it yields a specialized functor which will defer maps, but I can't see how it is going to help write a lawful instance (this functor has to be substituted in Alternative implementation, or am I totally wrong?). It's also a bit unclear to me why signaling empty via a unique, private singleton is a blocker - it seems to me that such a structure can be made aware of such element.
In any case, I'd love to experiment with such design.

Thanks to everyone involved for the most fascinating discussion!

marcin-rzeznicki on 30 Jul 2019

👍1

@marcin-rzeznicki I’ll do a more full write up tomorrow! There’s a bit on the reversion PR (currently open), but I’ll explain the coyoneda idea in more detail. I’d love to hear your thoughts and get some experimental results!

djspiewak on 30 Jul 2019

🚀1 👍1

@marcin-rzeznicki Sorry for the delay!

The idea is pretty simple: accumulate map functions within Fiber rather than attempting to apply them directly. In your encoding, you implement map for Fiber by turning it back into an IO, mapping that and then starting again. Instead of doing this, we can take advantage of the fact that the only two elimination rules for Fiber are race and join, and both yield something which is guaranteed to form a Functor (since it must be Concurrent).

This solves the problem because it gives us control over when the map evaluates. More specifically, it allows us to push that evaluation beyond any race boundaries. This is pretty critical. Once a Fiber starts executing (i.e. once it exists), we can't have anything which modifies its workload. All we can do is declare that, whatever the result is produced, we then apply the map to that:

Very very roughly:

trait Fiber[F[_], A] { self =>
  type Init
  def xform(i: Init): A

  final def map[B](f: A => B)(implicit F: Functor[F]): Fiber[F, B] = new Fiber[F, B] {
    type Init = self.Init
    def xform(i: Init) = f(self.xform(f))

    def cancel = self.cancel
    def join = self.join.map(f)
  }

  def cancel: F[Unit]
  def join: F[A]
}


def racePair[A, B](
    fa: Fiber[F, A],
    fb: Fiber[F, B])
    : F[Either[(A, Fiber[F, B]), (Fiber[F, A], B)]] = {
  // hardcore implementation of racePair here
  // what we're going to get, given the current, is something like this:
  val results: F[Either[(fa.Init, Fiber[F, B]), (Fiber[F, A], fb.Init)]] = ???

  // so we need to transform that according to hte suspended free functor
  results map { e =>
    e.fold(
      _.leftMap(fa.xform),
      _.rightMap(fb.xform))
  }
}

You start to see the problems with this though. We're exposing the Coyoneda structure directly within the abstract Fiber. This isn't amazing. It's actually the opposite of amazing. It also doesn't really solve all of our problems, particularly since, in order to handle Applicative, we need something a bit more powerful than the free Functor so that we can suspend ap. But passing over all that as relatively trivial indirection (hopefully it's clear that it's at least possible), we still have some issues with |+|.

The first problem is the zero. We need the identity that empty |+| fa === fa |+| empty === fa, and the only value for which that holds is a Fiber which is already canceled. We can fake it by hiding things in the error state, which is what your other PR did, but this is a violation of zero uniqueness in groups (not a law which is codified in cats, I believe). It also seems more than a little kludgy.

The best approach for this is to just make it possible to create an already-canceled Fiber, and then we can make the claim that, from the standpoint of |+|, all canceled fibers are equal. This requires some more representational work though. It's relatively reasonable to have a Concurrent[F].canceled[A] function which creates an F[A] which is a canceled action, and then running start on such a value would presumably yield a canceled Fiber, but this is a major change (albeit one which has other benefits). Hence why I said it's definitely a Cats Effect 3-type change.

Finally, we need to be careful about |+|. It's a "bare race" in a sense, producing a new Fiber which is already evaluating, but didn't exist before. That's really quite scary, given the non-referential-transparency of Fiber construction. It would mean that something like this wouldn't work:

for {
  f1 <- makeAFiber[A]
  f2 <- makeAFiber[A]

  _ <- (f1 |+| f2).cancel
  result <- (f1 |+| f2).join
} yield result

// should be the same as

for {
  f1 <- makeAFiber[A]
  f2 <- makeAFiber[A]

  raced = f1 |+| f2
  _ <- raced.cancel
  result <- raced.join
} yield result

// but it's not

Which is a violation of referential transparency.

So I wonder if we can even do the Alternative part of this concept. We should be able to do Applicative by encoding a free applicative in Fiber (or analogously with Functor), but at the cost of some considerable complexity.

Is there any flaw in my reasoning here?

djspiewak on 2 Aug 2019

Cats-effect: TestContext should NOT have a deterministic mode

Most helpful comment

All 28 comments

Related issues