Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Proposal: move tailRecM to FlatMap and remove FlatMapRec #1278

Closed
johnynek opened this issue Aug 9, 2016 · 9 comments
Closed

Proposal: move tailRecM to FlatMap and remove FlatMapRec #1278

johnynek opened this issue Aug 9, 2016 · 9 comments

Comments

@johnynek
Copy link
Contributor

johnynek commented Aug 9, 2016

See this PR: #1216

Note the discussion about adding two different implementations of many of the methods, one using tailRecM the other not.

It seems that all the monads in cats can support tailRecM. In fact, it seems that if look at two classes of Monads we have "strict" (Option, Xor, Either, List, Vector, ...) and "lazy" (Free, Eval, State, ....)

In the case of the lazy monads, they are generally implemented in a stack safe way. In the case of strict monads, we can always implement tailRecM. What is an example of a monad we want to support that is not strict, yet not stack safe? I don't know of one.

Meanwhile, since authors can't depend on tailRecM, they use recursive flatMaps, and ask for Monad, when in reality they need something stronger: a Monad that supports recursive flatMaps or small enough inputs that you don't blow the stack.

To me, I'd rather tax implementers a bit more, or force some Monads into FreeT or such to get tailRecM than to deal with stack overflows due to the monad you are using (say for Xor) not supporting recursive flatMap.

@ceedubs
Copy link
Contributor

ceedubs commented Aug 21, 2016

Resolved in #1280 (@johnynek feel free to reopen if there was a reason for this still being open).

@ceedubs ceedubs closed this as completed Aug 21, 2016
@adelbertc
Copy link
Contributor

adelbertc commented Sep 3, 2016

So after some thought and hearing about @tpolecat and @raulraja 's experience of migrating to Cats 0.7.x, I'm becoming open to the idea of just having tailRecM on FlatMap without the marker trait we currently have. My initial counter-example of tagless final algebras being not stack safe has since been disproven and I fail to find a data type for which tailRecM cannot be implemented in a lawful way.

My concern is primarily that of principle - Monad is a generally well understood, clean, abstraction and adding tailRecM to it muddies it a bit. But then again, monadic stack safety is quite important especially in a runtime like the JVM. Is there perhaps a way to mark a specific law as "optional"?

Tagging people who expressed an opinion on this before: @tpolecat @non @tixxit @travisbrown @mpilquist @ceedubs @zainab-ali @johnynek

I would also appreciate any feedback from @paf31 :-)

@adelbertc adelbertc reopened this Sep 3, 2016
@paf31
Copy link

paf31 commented Sep 3, 2016

Is there a safe implementation for the list monad?

@johnynek
Copy link
Contributor Author

johnynek commented Sep 3, 2016

There is a safe implementation for everything in cats including List and
Vector (both of which use a mutable builder internally).
On Sat, Sep 3, 2016 at 10:20 Phil Freeman notifications@github.com wrote:

Is there a safe implementation for the list monad?


You are receiving this because you were mentioned.
Reply to this email directly, view it on GitHub
#1278 (comment),
or mute the thread
https://github.com/notifications/unsubscribe-auth/AAEJdhyqTqOAk6ZiodPp_X6mjnbktvadks5qmdaMgaJpZM4JghMz
.

@adelbertc
Copy link
Contributor

@paf31 We can make it safe, heap permitting, since Scala allows mutability:

def tailRecM[A, B](a: A)(f: A => List[Either[A, B]]): List[B] = {
- looks like we allocate a mutable buffer and append to it, converting it into an (immutable) list once we're done.

There was also a related question to that here: #1329

@djspiewak
Copy link
Member

I'm assuming this is the issue @johnynek was referencing…

This is a lawful monad which does not have a stack-safe tailRecM implementation. It could be reimplemented to support tailRecM, but that would require altering its algebra to use (A => Eval[R]) => Eval[R] as the core function. This isn't an implementation detail: it would need to be propagated through the public API.

A more practical example is fs2.Task, which cannot have a safe tailRecM if users construct a long bind chain using asyncUnshifted.

These use-cases show up in general if you try to define a function [F[_]] scalaz.Monad[F] => cats.Monad[F], which is not possible without blowing the stack.

@djspiewak
Copy link
Member

Copying over some context from Gitter…

@johnynek countered with the Continuation implementation in #1400, which is stack safe but only in a right-associative context. His Continuation implementation is really just Free[Cont[R, ?], A], which is a perfectly valid implementation, but hints at where the demons are hiding. Conceptual sketch:

// given a conventional Cont implementation and:
type JCont[R, A] = Free[Cont[R, ?], A]

val evil: Cont[R, JCont[R, A]] = ???
val lifted: JCont[R, JCont[R, A]] = JCont.liftM(evil)
val oops = lifted.join

Even assuming a join implemented by composing map and tailRecM, performing this construction will add a stack frame every time. Do this an arbitrary number of times, and you have constructed a counter-example to the stack safety of tailRecM.

Another way of looking at this is in the context of fs2.Task. If you want to define a function A => Task[A], there are three ways to go about it (if you ignore laziness):

object Task {
  def now(a: A): Task[A] = ???
  def async(a: (A => Unit) => Unit)(implicit S: Strategy): Task[A] = ???
  def asyncUnshift(a: (A => Unit) => Unit): Task[A] = ???
}

The first and second functions here will be stack-safe, and if Task only had these two, it would be able to implement a valid tailRecM. The only reason the second one works though is because it is literally trampolining through Strategy, which bounces the stack by thread-shifting. That's not what you want every time, and clearly it's perfectly valid not to use that function. If you use asyncUnshift, there's no bouncing of the call stack, which means that you can construct arbitrarily long bind chains which are entirely within the suspension and grow the stack on each iteration.

Note that the tailRecMStackSafety test will not catch any of this, because it only uses F.pure. The pure constructor delegates to now in Task, or simply pure in @johnynek's Continuation (which is obviously not Cont's pure, but Free's).

@johnynek
Copy link
Contributor Author

It's true that without stack safe functions, which we could add, I see no way to make Cont totally stack safe. @mpilquist did some benchmarks on a function with stack safe andThen and it wasn't totally terrible. I mean, if you have to deal with (A => R) => R you have to use the call stack.

Here is a link to recent discussion: https://gitter.im/typelevel/cats?at=58d83c68b402a53211b5931a

Since this is the only real case we know of, I think we should attack this more directly than giving up tailRecM on all cats.Monads, since so many implementations are non-obvious, yet without them people have empirically just written unsafe code using recursive flatMap. In my view, that is much worse, since unlike tailRecM which is safe for every monad instance in cats, recursive flatMap is unsafe for almost all instances (except Free, FreeT, Eval). Indeed, even getting out or a Free (since there is no free-lunch), requires tailRecM.

@djspiewak
Copy link
Member

djspiewak commented Mar 27, 2017

As I mentioned on Gitter, what this comes down to for me is whether or not we're ok with tailRecM lying. Or equivalently, is the contract of tailRecM "always uses O(1) stack", or is it "tries very hard to use O(1) stack, but might use proportional stack under some rare circumstances." If it's the latter, then we're good all around. If it's the former though, then we're dead by definition.

If we take the strict view on tailRecM, then cats.Monad is strictly more restrictive than the mathematical definition of monad. Which is to say, there are monads which have no (truthful) cats.Monad. If we take the lenient view, then tailRecM can still be used by those that are trying to get stack safety, so long as they understand that certain monads will not be able to give it to them.

I want to be very clear that this isn't a matter of insufficient creativity in Task. There is no way to have a stack-safe tailRecM for all Task values, just like there is no way to have a stack-safe tailRecM for all Cont values. The fact is that cats.Monad only characterizes a subset of monads. Even if there's a way to encode the concepts of Task in some other form which can produce a stack-safe tailRecM (which I greatly doubt), it doesn't change the fact that Task in its original form is a monad but not a cats.Monad.

So I think the only general solution to this is to just accept that tailRecM does not guarantee sub-proportional stack usage.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

5 participants