Laws questions

[durban]

A few questions (mostly) about laws:

1. Are there any laws about stack safety? I found one for Defer in cats, but not here, e.g., about flatMap stack safety. (I think there used to be for Sync in 2.x.)
2. It seems, that Defer#defer is not for capturing side effects. I remember a suspend method with the same signature (I think in Sync), but that seems to be removed. What should be used? Simply delay(...).flatten?
3. Relatedly, AsyncDeferred is using Defer#defer for effect capture in get and complete...

[armanbilge]

It seems, that Defer#defer is not for capturing side effects.

That's correct. This is an important difference because defer is allowed to cache its (pure) value vs side-effects which must be re-evaluated every time they are sequenced.

However we have Sync <: Defer (since defer is implementable with delay) so in theory Sync#defer could strengthen its API contract to guarantee it suspends side-effects. That's not currently the case though AFAIK.

Are there any laws about stack safety

For tailRecM and for defer, besides that can't recall any. To be honest I consider stack-safety guarantees sort of a mess: instead of requesting Defer constraints in many places assume stacksafe flatMap and use a F.unit >> ...

What should be used? Simply delay(...).flatten?

Yes, that is my preference.

Relatedly, AsyncDeferred is using Defer#defer for effect capture in get and complete...

I wouldn't oppose rewriting those to delay(...).flatten. That's the effect agnostic implementation anyway so it makes sense that it should try hard to be lawful. We already have the optimized IO variant.

[joroKr21]

We have StackSafeMonad but the type classes don't extend it. While the IO instance does.

[durban]

in theory Sync#defer could strengthen its API contract to guarantee it suspends side-effects. That's not currently the case though AFAIK.

Re-reading the Sync#defer scaladoc, it might already do this:

  /**
   * Suspends the evaluation of an `F[_]` reference.
   *
   * Equivalent to `FlatMap.flatten` for pure expressions, the purpose of this function is to
   * suspend side effects in `F[_]`.
   */

The last sentence is somewhat confusing to me, but it seems to say more or less that. The migration guide also recommends using Sync#defer instead of the (2.x) suspend. If this is true, then the use in AsyncDeferred (and also Queue) seems to be fine.

To be honest I consider stack-safety guarantees sort of a mess: instead of requesting Defer constraints in many places assume stacksafe flatMap and use a F.unit >> ...

"A mess", meaning "we tend to assume things not guaranteed by the typeclasses"? Or am I misunderstanding you?

[armanbilge]

but it seems to say more or less that

Oh, indeed it does! In that case, I agree then that seems fine.

"A mess", meaning "we tend to assume things not guaranteed by the typeclasses"? Or am I misunderstanding you?

Yes, in a handful places where we actually want defer instead we assume that we have a StackSafeMonad. Also some occurrences in FS2.

cats-effect/kernel/shared/src/main/scala/cats/effect/kernel/Resource.scala

Line 294 in 8905b98

(release, _) => storeFinalizer(fin => ec => F.unit >> fin(ec).guarantee(release(ec)))

cats-effect/kernel/shared/src/main/scala/cats/effect/kernel/Resource.scala

Lines 419 to 420 in 8905b98

	// we insert a bind to get stack safety
	suspend(G.unit >> source.mapK(f).pure[G]).flatMap(x => f0(x).mapK(f))

cats-effect/kernel/shared/src/main/scala/cats/effect/kernel/Resource.scala

Lines 488 to 489 in 8905b98

	// Insert F.unit to emulate defer for stack-safety
	val rel2 = (ec: ExitCase) => rel(ec).guarantee(F.unit >> release(ec))

cats-effect/kernel/shared/src/main/scala/cats/effect/kernel/Resource.scala

Line 748 in 8905b98

finalizers.update(fin => ec => F.unit >> fin(ec).guarantee(release(ec)))

[durban]

In 2.x there used to be a lot of laws for stack safety:

cats-effect/laws/shared/src/main/scala/cats/effect/laws/SyncLaws.scala

Line 85 in 1b51cb1

def stackSafetyOnRepeatedLeftBinds(iterations: Int) = {

Maybe we should create some of these in 3.x too? Or is the "new" way to use Defer instead of relying on a stack-safe flatMap?

[djspiewak]

I can add some color here to what's already been said!

Regarding flatMap laws… We had these in 2.x but they were always somewhat statistical in nature, and they took a startlingly long time to run in some cases. Additionally, they violate our general law philosophy of each law representing an extensional axiom (e.g. don't do something like <-> F.pure(true), but instead show a symbolic rewrite). I think that philosophy has, in general, significantly improved the reasonability and usefulness of our laws, but it does mean that some things which deserve tests don't get them. If I remember correctly, we made a conscious decision sometime in like, 2019, to not include flatMap stack safety tests in the 3.x laws, despite the fact that we assert it to be so.

Regarding defer… You can use it to capture side effects (and I frequently do so). Notionally, strengthens the defer guarantees in two ways. First, defer already represents a lazy suspension, meaning that it is ample for capturing side effects if two additional properties hold: it handles exceptions, and we are willing to "bless" the symbol with "magic side-effect capturing" meaning (like delay and async_). In general, most people are very comfortable with the latter, and the former is already strongly implied by the type signatures (and in fact, exactly true in the implementation). To that end, we consider defer to be the direct replacement for suspend, and its use in Fs2 (and Cats Effect!) mirrors this fact.

I don't really find defer to be that useful on a regular basis, but when I do find it useful it's very awkward to work without it. A good example of this is #3923, where we're frequently mixing pure and impure logic. I also came across this often when working on heavily performance-sensitive Fs2-using code at a previous company, where we needed to have a bunch of low-level impure logic for performance which would dynamically bail out into pure suspensions to maintain memory and stack incrementality (as well as obviously asynchrony). That type of dynamic bouncing back and forth between pure and impure suspensions is annoying if you do it using delay, but it's really clear and natural with defer.

Regarding StackSafeMonad, it was never intended to be a type-level constraint, but rather a convenience mixin. Literally all it does is derive tailRecM from flatMap so that you don't have to do this again and again and again for every monad which is naturally stack-safe. Now, with that said, it's a strong enough convention that we've started to exploit it in a few areas (e.g. the erstwhile traverse optimizations in Cats), but in fairness IO alone using it makes it strong enough to pay attention to.

The general problem here is that "stack" as a rule is an untracked side effect, similar to how memory is an untracked side effect. This is unprincipled in a sense, but it's also pragmatic since there's simply no way we could track memory or stack allocation with that level of rigor within the bounds of the Scala language (or Haskell, for that matter). Since it's an untracked side-effect, we end up in this awkward spot where we have to make assertions about a thing without really encoding those assertions in any particularly strong way at the type level, which is obviously the opposite of how we normally work. If you think about it, we make a very similar set of implicit assertions around IO's memory safety (e.g. the fact that left-associated binds are constant memory usage, even in the face of errors, is something that people implicitly rely on but isn't encoded anywhere in the type system). This gets us into trouble now and then, with the gotchas around Fs2's Pull and non-tail-recursive state machines being the most common example that I'm aware of.

[durban]

Thanks for the background info!

Since it's an untracked side-effect, we end up in this awkward spot where we have to make assertions about a thing without really encoding those assertions in any particularly strong way at the type level

For example, that release in MonadCancel#bracket in uncancelable is also not encoded at the type level. But, crucially, it is in the scaladoc of the method (and probably also in the laws), so implementers know that they have to make it so; and users also know that they can rely on it. If it is not written down either in the laws, or in the scaladoc (or somewhere), that (e.g.) Concurrent#flatMap has to be stack-safe... I mean, why would we not write this down, if we're assuming it anyway?

[djspiewak]

It surprises me that we didn't document this, at least in the scaladoc.

[durban]

Ah, so it's not intentional. That makes much more sense. I guess I'll open a documentation issue...