Hello Everyone, We have an issue in Arrow with the...

# stdlib

[raulraja]

Hello Everyone,
We have an issue in Arrow with the implementations of the suspension intrinsics in the std library.
Currently the Arrow library uses continuations to enhance syntax when computing over types not just from Arrow but also for third party types we integrate with such as coroutines, rx, reactor, etc.
For example, with KotlinX Couroutines Flow a user may destructure and compute over the Flow with:

val flow = flowOf(1, 2, 3, 4, 5)
fx {
  val n = !flow
  n + 1 //n is each of the elements in the flow
}
// flowOf(2, 3, 4, 5, 6)

This same idiom can work with Deferred, Observable, IO, and pretty much anything that contains or can implement a flatMap method.
For this to work with pure values and across all data types we have to reset the continuation stack so the continuation can be invoked multiple times.
We would like to request that some kind of mechanism for library authors to be able to access the intrinsics of the kotlin.coroutines.jvm.internal.ContinuationImpl.
At the moment resetting the coroutine stack is an exercise of heavy java reflection when this could be avoided if we had protected access to those fields or a means to obtain/clone the continuation state.

https://github.com/arrow-kt/arrow/blob/7d54b31fe240688b4481b8f91767cbb82b9ad78c/modules/core/arrow-typeclasses/src/main/kotlin/arrow/typeclasses/ContinuationUtils.kt#L7

The use of reflection and manual copying the fields like that imposes unnecessary overhead and does not give us a solid solution going forward.

As far as I understand suspension, suspension has been added to the Kotlin std library so other libraries can build on top of it.
This is great because we don’t have the issues in Kotlin I had in Scala from people abusing Future just because it was in the std lib and opens the doors for others to create async/concurrent and in general suspended based frameworks just with the suspension apis.
While this in concept is great, at the moment it just seems to be serving KotlinX Coroutines Core library use cases.
There is other libraries like Arrow Fx where single shot / eager async continuations are not enough to cover these use cases.

Can we get access to those fields without reflection or does anyone know of an alternative to accomplish this that does not require dealing with the ContinuationImpl stack?
We are happy to collaborate with changes in the std lib or whatever it takes to get passed this issue.

[orangy]

@elizarov ^^

[elizarov]

Unfortunately, this is something that cannot be easily done in a safe way in a language like Kotlin, which does not provide a way to distinguish between mutable and immutable classes. At least, I don’t see a way to have this feature. However, I’d like to see arrow-kt succeed, so I’m open to suggestions on what kind of safe primitive we could add to stdlib that would enable it.

[elizarov]

To clarify, if immutable classes were clearly distinguished in Kotlin by some language feature (like immutable modifier), then one could safely introduce a Continuation.copy() extension that creates a separately-resumable copy of continuation or throws exception if that continuation closed over some mutable state that cannot be safely resumed again. But we don’t have this distinction, so we cannot provide this method. Without the appropriate safety precautions it is too brittle.

[raulraja]

@elizarov thanks for the response. In regards to immutable classes in Kotlin, I suppose if this feature was added to the lang it would check that classes annotated with an immutable modifier contain only val in their property list?, or would it require all inner properties to also be immutable?
We are happy to work on a KEEP if you think this is desirable and a better path to support copying the continuation state.

I think an interim solution based on intrinsics may also work. Currently we have suspendCoroutineUninterceptedOrReturn, could we have a similar utility method that is explicit to what it does and automatically copies/rewinds the state? Our current pattern where this is needed looks like:

suspendCoroutineUninterceptedOrReturn { c ->
    val labelHere = c.stateStack // save the whole coroutine stack labels
    value = flatMap { x: B ->
      c.stateStack = labelHere
      c.resume(x)
      value
    }
    COROUTINE_SUSPENDED
  }

This is necessary for a couple of reasons:
- Accessing the inner A value in for example a Flow<A> is multi shot since the Flow may contain multiple values
- Other data types such as IO produce pure values that can be invoked a la carte N times by a user. If we don’t rewind the state they can only invoke this once.

[elizarov]

This primitive is problematic for the reasons I’ve outlined. See, suspendCoroutineUninterceptedOrReturn is not safe, but it is easy to clearly specify under which conditions it can be used. The problem with continuation copying is that there is no way to clearly specify when it is safe to do so. And generally we’d like to avoid this kind of “I feel lucky” functions in Kotlin standard library

[elizarov]

It is not just mutable/immutable distinction. It is a non-transparent property of many stdlib higher-order functions. Many of them would fail is their inline lambda is suspended and resumed more than once, but you cannot tell which ones can be resumed twice and which cannot be just by looking at their declaration — you have to check their implementation, but implementation can change from version to version.

[raulraja]

Can we use restricted suspension for this? That is, only enable the intrinsic functions that are unsafe in certain restricted receivers based on a marker interface that library authors are aware of? If not what would you recommend for us to pursue?

[raulraja]

I’m a little concern about KEEPs because they take a long time to resolve for the most part and this is an issue all Arrow users are facing today and people have already complained about the reflection use several times.
We are kind of in a weird spot now where we are preparing for 1.0 and this issue ties us to the JVM because it uses reflection. Also we are always concerned that on each release the ContinuationImpl internals can change and break Arrow.
This is an important idiom to all of our users since most FP langs support some form of for comprehensions and it’s what users demand and are familiar with for the most part.

[elizarov]

I don’t have a solution for this problem and doubt that solution exists. However, it might be possible to write some kind of compiler plugin in the future that essentially defines a Kotlin dialect that addresses this problem somehow.

[raulraja]

We are also happy to drop this notation if flatMap binding in suspended form was a lang feature for types that structurally contain a flatMap method similar to how Kotlin treats today Iterator

[raulraja]

It looks structurally for methods to enable syntax in for .. in

[pakoito]

I’d suggest looking into generators from Python and JS.

I’m not very happy about “kotlin dialects”, what’s the angle here? We’ve already followed the KEEP and got community support and even forked the compiler to implement typeclasses and not even that got us a peep about the state of compiler plugins. Is it for british eyes only? 😄

[elizarov]

Neither Python nor JS generators provide multi-shot continuations. However, it is known that in theory single-shot continuations are just as powerful as multi-shot ones, they just need a different notation to work with them.

[pakoito]

Do you have a paper we could look into?

[elizarov]

http://www.inf.puc-rio.br/~roberto/docs/MCC15-04.pdf

[elizarov]

(I’m not sure this is the paper I’ve see it in, though)

[pakoito]

thanks!

[elizarov]

Back to your original thread-starting question. A general flow implementation would not work with the notation you’ve outlined at the beginning of the thread, because if a flow happens to use mutable data structure it will get corrupted by an attempt to resume it twice. However, you can use a different notation. Instead of val n = !flow; ...rest... write flow.collect { n -> ... rest ... } and you’ll get the same effect using only single-shot continuations.

[elizarov]

(it is a corollary to a general transformation from multi-shot to single-shot continuations)

[pakoito]

because if a flow happens to use mutable data structure it will get corrupted by an attempt to resume it twice

Could you please expand on this? It it because it captures a user-defined mutable data structure, or because one's used to define some operators? AFAIK Flows are lazy and do not memoize unless explicitly requested and if that's the case then any reuse is bogus anyway, putting it on a different category than observables (!).