Comments (11)
Future has StackSafeMonad
, but would fail the "defer does not evaluate" law.
Aside: the stack safety of the current instance depends on the stack safety of its ExecutionContext
.
from cats.
I'm wary of arguments about pure FP that leverage hidden side-effects to show their value. In the case of using defer(loop(a))
in the tailRecM example above, that is only an observable difference because the function f
isn't pure. But when we start admitting impure functions into our code almost everything can fall apart and almost all the laws can be violated.
I know sometimes people do this, but generally, we shouldn't design for it.
That said, FlatMap.tailRecM and Defer.defer (similar to Monoid.combineAll) are making concessions to the fact that we are implementing this code on virtual machines where function evaluations consume a finite resource (stack space), and so by declaring the intent of the code directly we can get a more efficient encoding on those virtual machines. So the law in Defer about not evaluating the argument is really motivated by the desire for O(1) stack usage to do defer(foo(a))
independent of the stack usage of evaluating foo(a)
. In a recursive context especially this is important to convert what could be linear stack depth consumption to constant or logarithmic, which we can then actually run on our machines.
A secondary concern is the ability to short circuit a computation (e.g. foldRight) but that is only about improving the best or average case scenario, it doesn't change the worst case performance.
from cats.
Future has StackSafeMonad, but would fail the "defer does not evaluate" law.
@rossabaker, actually, Future
is an interface, so it can implemented in a way that Defer
can be supported too, check this out:
Custom Future implementation (folded, because even a minimal implementation is fairly large):
final class LazyFuture[+T](get: () => Future[T]) extends Future[T] {
private lazy val future = get()
override def isCompleted: Boolean = future.isCompleted
override def value: Option[Try[T]] = future.value
override def onComplete[U](f: Try[T] => U)(implicit executor: ExecutionContext): Unit =
future.onComplete(f)
override def transform[S](f: Try[T] => Try[S])(implicit executor: ExecutionContext): Future[S] =
future.transform(f)
override def transformWith[S](f: Try[T] => Future[S])(implicit executor: ExecutionContext): Future[S] =
future.transformWith(f)
override def ready(atMost: Duration)(implicit permit: CanAwait): this.type = {
future.ready(atMost)
this
}
override def result(atMost: Duration)(implicit permit: CanAwait): T =
future.result(atMost)
}
Now, the implementation of Defer
for Future
comes out fairly simple:
object FutureDefer extends Defer[Future] {
override def defer[A](fa: => Future[A]): Future[A] =
new LazyFuture[A](() => fa)
}
An example of demo code:
implicit val executor: ExecutionContext = ExecutionContext.parasitic
var evaluated1 = false
var evaluated2 = false
val deferred = FutureDefer.defer {
evaluated1 = true
Future {
evaluated2 = true
12345
}
}
println("allow some time, just in case...")
Thread.sleep(1000)
println(s"evaluated1=$evaluated1; evaluated2=$evaluated2")
println("now await the future...")
val result = Await.result(deferred, Duration.Inf)
println(s"evaluated1=$evaluated1; evaluated2=$evaluated2")
println(s"result=$result")
And here is the output:
allow some time, just in case...
evaluated1=false; evaluated2=false
now await the future...
evaluated1=true; evaluated2=true
result=12345
So it looks working even with the parasitic
context.
That said, I am not sure if we can expect from Future
to fully support the laws due it its lack of referential transparency. The following code code wouldn't work properly just because of that:
val original = Future {
evaluated2 = true
12345
}
val deferred = FutureDefer.defer {
evaluated1 = true
original
}
Apparently, the output is:
allow some time, just in case...
evaluated1=false; evaluated2=true
now await the future...
evaluated1=true; evaluated2=true
result=12345
But even in that case, evaluated1
is still properly deferred.
from cats.
I agree with Oscar's sentiment here.
The motivating case here is the secondary concern: improving the average case of a timeout, when the fallback value requires an expensive stack trace and is rarely returned. We fake that today with the unit.flatMap
, which risks the same miscalculation I opened the thread with. It works in practice, because the base monad of GenTemporal
is usually IO
, which has a lazy flatMap
, even for pure IO
. And if the idiom's assumption fails, it's just slow, not incorrect.
I still wonder whether GenTemporal
's laws imply a lawful Defer
. Nothing jumps out at me. And even then, it would be a Cats-Effect issue.
from cats.
My gut tells me bad idea, and my default position is to be irritable about anything source breaking. But I've almost talked myself into this after a small spike.
from cats.
I think it is a bad idea because strict monads, such as cats.Id would just have to directly evaluate this totally destroying the intent of Defer.
Aside from intend, it would fail the current laws because the current law says defer shouldn't evaluate the arg if you just call it.
That said, maybe that's a bad law... idk.... but if that doesn't work, I don't see how fix
would work, and fix and recursion is the real motivation of Defer. Having a working Defer is what allows us to implement ContT. Basically, when we are cargo culting from Haskell it is easy to not notice when laziness is required since Haskell is non-strict. Defer allows us to declare explicitly where we are leveraging laziness.
I think maybe StackSafeMonad could extend Defer in this way. That said, it's not that hard to add this implementation to the StackSafeMonad you are implementing.
from cats.
You're right. I didn't have enough compiling to run more tests than MiMa, but it definitely breaks both the spirit and the letter of the law in several cases.
A place I've seen this come up repeatedly, and again today, is to avoid the eager instantiation of the fallback value on timeouts. When all people have is GenTemporal
(and specifically don't want Sync
), they resort to the unit.flatMap
trick. Perhaps Defer
could be introduced a bit earlier in the cats-effect hierarchy, but I'm convinced that Monad
is too early. Thanks for validating my gut.
from cats.
I like the idea to consider StackSafeMonad
for adding Defer
as a mixin. At first glance, it looks pretty natural – if we can defer evaluation, then we can afford stack safety in general – can't we?
Moreover, I would say that currently StackSafeMonad
looks a bit awkward – it is nothing but a kind of "marker" trait, i.e. it does not add new functionality, but rather assumes changes in some behavior only.
from cats.
I like the idea to consider
StackSafeMonad
for addingDefer
as a mixin. At first glance, it looks pretty natural – if we can defer evaluation, then we can afford stack safety in general – can't we?
Yes indeed. This idea is discussed before in #3790 (comment).
Moreover, I would say that currently
StackSafeMonad
looks a bit awkward
Daniel explained recently on Discord:
ironically, when I introduced that trait, I intended it to be solely used as a mixin and never as a constraint 😛
I was just trying to solve the problem of everyone cargo-culting the sametailRecM
implementation
from cats.
Actually, I'm inclining to think that StackSafeMonad
could benefit from inheriting to Defer
, check this out:
val M = Monad[Eval]
println("begin")
M.tailRecM(0) { a =>
println(s"a=$a")
Eval.always(Either.cond(a == 3, "done", a + 1))
}
println("end")
Even though we do not ask for the result Eval
's value
the very first call to f
is made eagerly:
begin
a=0
end
I feel it might not be what users would expect in general.
But if StackSafeMonad
was extending Defer
, then it could defer the first call as well:
trait StackSafeMonad[F[_]] extends Monad[F] with Defer[F] {
override def tailRecM[A, B](a: A)(f: A => F[Either[A, B]]): F[B] = {
def loop(aa: A): F[B] =
flatMap(f(aa)) {
case Left(aaa) => loop(aaa)
case Right(b) => pure(b)
}
defer(loop(a))
}
}
from cats.
And if the idiom's assumption fails, it's just slow, not incorrect.
For some definition of correct :) constructing an exception is not pure, it is side-effectful. Depending on where and when you do it, you will capture a different stack trace. If we decide we don't care about stack traces, then it doesn't matter.
I wonder if what we need is a dedicated way to create Exceptions
in the Cats(-Effect) hierarchy. That way we don't have to reach for Defer
or Sync
to suspend when what we specifically need is weaker.
from cats.
Related Issues (20)
- Option size method implicitly selected from UnorderedFoldable HOT 2
- IndexedStateT has superfluous parts HOT 4
- .splitWhen
- Difference in the Applicative inferred for Seq[Seq[?]]#sequence between Scala 2 and 3
- Inconsistent behaviour when using Eval as Applicative
- `Tuple1SemigroupalOps` methods have different names from other `TupleNSemigroupalOps` classes HOT 3
- Instances for Currency HOT 7
- EitherT[Option, ?, ?]] can't be used as a bifunctor HOT 5
- trait EuclidianRing should not be a Ring HOT 4
- OutOfMemoryError when IO.uncancelable is used in recursive function HOT 1
- ambiguous implicit resolution of `Show.ContravariantShow[immutable.SortedMap[K, V]]` HOT 1
- Support Scala Native 0.5 HOT 3
- Adding an alternative version of the method whenA with a different signature
- `Eval` thread safety HOT 4
- Optimize `distinct`/`distinctBy` implementations for non-empty collections
- [PROPOSAL] Aliases for methods `traverse_` and `sequence_` HOT 7
- Any reason `intercalate` isn't exposed directly on the `Semigroup` companion object? HOT 3
- (very breaking) change in Future instances? HOT 5
- Reveal internal but public identifiers and make them `private[cats]`
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from cats.