Hopefully, this isn't too irrelevant: I just made ...

# arrow

[Youssef Shoaib [MOD]]

Hopefully, this isn't too irrelevant:
I just made public a repo where I implemented proper Delimited Continuations using Compose, Coroutines, and (of course) Arrow. I know that Arrow briefly had them before, albeit with significant limitations. This implementation still has limitations, but they're minor and simply annoying to remember.
The only annoying things about it are:
• You need to call bind or by on the shift
• You need to surround the body of reset in maybe
• You need to surround any side-effect or heavy-calculation in an effect block
The first 2 issues are Compose limitations around throwing exceptions, but in theory they should be supported eventually
The 3rd one is unavoidable due to how Compose works. Everything inside shift or effect will run the proper number of times, but anything outside will run as many times as the continuation is run. It's annoying, but again merely surrounding your code in effect fixes the issue.

[Youssef Shoaib [MOD]]

Just realised now that Compose does some magic around if, else, while and for, and probably other control flow, and thus you're not allowed to throw inside them, so I'm having to create special versions of them. This should be the same as problems 1 and 2 though, and hence it should go away if Compose improves. In fact, the solution is so mechanical and simple that I think they could probably implement it in their compiler plugin easily.

[simon.vergauwen]

That's really awesome @Youssef Shoaib [MOD]!! 🤯 👏 👏 👏

We did many attempt without Compose, (or plugins), and whilst we got close we always had too many impactful things. Like having to recreate if, else, while, for, we felt it broke the language too much.

But still super useful! Perhaps something in combination with Inikio @Alejandro Serrano.Mena

[Youssef Shoaib [MOD]]

All the recreations right now are annoying yes, but can be gotten around if you keep unwrapping and wrapping the "end everything and get out of here" signal. E.g. instead of my ifSafe wrapper, one can do (if (condition) maybe { ... } else maybe { ... }).bind()
In fact, Compose is helping a great deal here because it magically transforms for and if etc to "do the right thing", it just does that without supporting exceptions coming from them.
The only reason they exist though isn't because of any conceptual limitations, it's just because Compose can't handle exceptions well just yet. That should hopefully be supported in the future, and then everything I've been complaining about will dissolve away (except writing effects/calculations in specialised blocks. It's practically a manual state-machine transformation, but it's so mindless and simple that I don't think it's that hard to get used to). Thankfully, if one forgets to wrap and unwrap, Compose throws its own exception that seemingly is always guaranteed to happen, and so at least no logical errors happen 🤷🏼‍♂️
If there is a pre-existing way to cancel composition reliably and not immediately schedule recomposition, I'd love to know about it. It would also fix everything magically.

[simon.vergauwen]

Okay, so reset is your entrypoint I assume. So that's going to replay the effect on re-composition. Not sure if bind comes from maybe? But maybe is what protects from exceptions here?

That was indeed the problem we got stuck on last time... Compose can replay from certain points in the tree, but without it you cannot. I'd need to dig up the other gotchas, but this might indeed by solved by Compose.

I assume you cannot put maybe, or something like that in your runtime? The compose generated code in between is what blows up due to exceptions?

[simon.vergauwen]

Very impressive work!!! Btw, why is coroutineContext.cancelChildren() needed in some of the MonadTest.kt?

That seems to point to an older problem I had in the past, this seems to indicate a coroutine is created somewhere but never completed, and thus there will be an accumulation of uncompleted continuations accumulating. Not sure if they get GC'ed or not, might depend on the classpath due to KotlinX Debug 😱... Otherwise can be OOM in long running apps.

[simon.vergauwen]

That might also indicate that try/finally is broken in some places

[Youssef Shoaib [MOD]]

Here's a quick rundown:
reset is the entry point. It launches a composition for me to use.
Whenever shift is called, it needs to do the equivalent of COROUTINE_SUSPENDED, and rn I simulate that with raise(Unit). In other words, we need to stop the execution of the composition until the continuation passed to shift is called. From there, it's smooth sailing. It's that COROUTINE_SUSPENDED idea that's requiring exceptions.

[simon.vergauwen]

Sorry, I spend countless of hours staring at this. I've so far avoided Compose due to instability, complexity of compiler versions, and requiring a compiler plugin.

I think some really cool stuff can be done with Compose, especially within the world of direct style and complex monads like Resource, or Rose.

[Youssef Shoaib [MOD]]

Whenever a shift is controlling the block, it basically replays the block up until the point that this shift was called, then it actually runs any code after that. The only issue I have is giving control to the shift block requires ending the composition

[Youssef Shoaib [MOD]]

coroutineContext.cancelChildren is needed for any lazy value that you want to produce out of a comprehension. For instance, if you're producing Flow, the flow won't get started until you later call collect, so we need to keep the composition coroutine alive. It's just a minor hack for now. My plan is to instead provide a use function perhaps where you're expected to produce a non-lazy value out of it, and then after the block finishes we kill the composition coroutine.

[simon.vergauwen]

Oh, I see so it's only needed for lazyReset?

[simon.vergauwen]

Okay, that would be a non-issue indeed

[Youssef Shoaib [MOD]]

Yes, and again I can design something better that hides that call, just haven't done so yet.
Also, instead of using cancelChildren, I probably want to use a custom Job anyways, just haven't done so yet because cancelChildren did the job just fine.

[simon.vergauwen]

Ye, sounds like low priority while figuring out the rest. Amazing work 👏 👏 👏 A lot of time (and frustrations) has been spend trying to figure this out 😂

cc\\ @Jannis not sure if you'll still see this.

[Jannis]

I do see notifications, just don't check slack to often anymore. Whats this about? o.O

[Jannis]

Oh, multishot delimited continuations? I need to check this after work!

[Youssef Shoaib [MOD]]

It has been a fun couple of weeks trying to figure this out. Especially because Compose should theoretically be the right tool for the job, but of course no one needs the level of control that this requires, and hence finding answers online has been impossible.

To explain the shift better, shift is conceptually just suspendCoroutine. You know how suspendCoroutine returns COROUTINE_SUSPENDED, gives you the continuation, and then later you can resume it? Resuming the continuation is easy to do here. The issue is "suspending" the composition. The way coroutines do this is by rewriting the function to early-return with a special COROUTINE_SUSPENDED value. I can't do that here without a custom compiler plugin, which I'd really like to avoid. I can easily "advance" the composition until the point I want, and I can be sure that it's done whenever it produces a value into my outputBuffer, the only issue is how do I short-circuit the composition? Currently, I use a raise(Unit) and I wrap everything in a value class Maybe which is just an optimized Option. The issue is Compose doesn't play well with raise whenever it "crosses" a @Composable or control-flow (if, while, etc). Hence, we need to "wrap" things in a maybe { } (which just takes a block: Raise<Unit>.() -> R) and then bind them after the boundary (which ends up calling raise(Unit). Alternatively, a user can also just call getOrElse { return@reset nothing() } but that'd need to be done for every reset call, which is incredibly annoying.
So what I need is a way to short-circuit a composition so that the block passed to shift can be allowed to run and can get control over the composition.

[simon.vergauwen]

Probably better to find a shift that doesn't work this way. Might be even possible to avoid exceptions all together if you use my original shift impl.

[simon.vergauwen]

This is going to require more time to discuss 😅 Going to have lunch now, but would love to collaborate on this!!! Even if there are some gotchas you can build some amazing stuff on this, even if it ends up too delicate for regular user code.

[Youssef Shoaib [MOD]]

That one requires suspend though, no? If I could do a @Composable suspend fun, I would've, and it would solve all the issues, sadly the Compose compiler explicitly forbids this construct. One other option is to just hang the composition until shift's continuation is called. That would require the continuation being called at least once though, so for instance you wouldn't be able to bind on List, only on NonEmptyList. Hanging in that way is a waste of a thread also.

[Youssef Shoaib [MOD]]

Currently exploring using a Compose internal (yet marked public) API which is used for early returns. Might be quite promising!

[simon.vergauwen]

Yes, that one requires suspension indeed even if it's @RestrictSuspension, not sure if you could leverage it right before the @Composable function but that'd depends on how the internals are wired.

I am super busy preparing for KotlinConf, but I am going to dig deeper whenever I have time. I have some stuff I'd like to try implementing on top 😅

[Youssef Shoaib [MOD]]

No worries at all. I can imagine the stress!

FYI, I think I just got it working with that internal API detailed in this issue. Gonna test more just to be safe, but if it works this means 1) we can build Compose-specific Raise dsl and 2) all my issues (except surrounding with effect) go away completely 🤯 . It's worrying to use an internal API though, but as a non-production-ready toy this is fantastic!

UPDATE: all tests are running great! The updated version is now in this branch because I'm still cautious about using an internal API.

[simon.vergauwen]

lol that's so sick! And I immediately understood what is going on in Compose now looking at your last commit 🙌

[simon.vergauwen]

Amazing find! 👏 👏 👏

[Jannis]

Ah, so from what I can tell (haven't done kotlin for a while and know next to nothing about compose), it is a similar approach to the hacky multishot thing I did a long time ago. Bindings store their state and on a rerun they use the cached value. My old version needed the good old stack frame copy hack that only worked with reflection and in general was pretty hacky. I assume this uses compose in some way to make the state handling a little nicer and to avoid having to use reflection hacks that only work on the jvm.
Definitely cool! I wish there was a way to avoid the rerun, but even avoiding the need for continuation cloning is already great!

[Youssef Shoaib [MOD]]

Yes that's basically it. I'm cleaning up the code right now to make it a lot clearer, but what it does is exactly that. Every effect block memoizes its result, and only recalculates if we've reached the point where the user previously `shift`ed. Compose is really good at doing this type of memoization and is designed to rerun very cheaply.
This one supports nested reset really easily too. That's because reset is just a simple suspend call, so one can simply shift { k -> k(reset(body)) }. It's also really smart about handling if, for, etc, so the code runs exactly as you'd expect, which is something that even the hacky continuation copying couldn't do. For example (from kotlin-monads):

val result = reset<List<Int>> {
  for (i in 1..10) {
    listOf(0, 0).bind()
  }
  listOf(0)
}
result shouldBe List(1024) { 0 }

With the continuation hack, this fails with a list of size 11 I think, while with my impl, it succeeds with 1024 items as expected. That's because Compose creates 10 different Shift and the first one takes control, reruns the block, then the second one takes control (and thus the first one is waiting), reruns the block, then the third one... Until the end. Right at the end, the 10th one takes control, reruns the block twice, and then gives control back to the 9th one, which reruns the block a second time.

[Jannis]

Oh wait. I am misremembering. The multishot thing I had worked slightly different and was way more hacky. We had the continuation clone trick for a while in arrow and other places, but what I did was a little more creative. I reran the whole block and kept an effect stack and invalidated entries based on some mutable state identifying where in the block we where. It had some major control flow issues around if/for (it did somewhat work, but I always felt that approach was dead without compiler/plugin support).
Re compose: Is compose general purpose enough to use for any application? Isn't it primarily a ui framework or something? As I said, I have no idea what compose is ^^ Spent the last years with java (sad) and quite a bit of haskell

[Jannis]

So anyway: So cool to see multishot continuations in kotlin and even the code right now doesn't seem too hacky, so it looks like a great approach 👍

[Youssef Shoaib [MOD]]

I love when the question of "isn't Compose a UI Framework?" gets brought up because I can link Jake's article. Basically, there's Compose Runtime and Compose UI. Compose Runtime is a general-purpose, multiplatform, tree-management library. It allows you to take some state and emit a tree from it, and the tree changes based on the state. Compose UI is built on the Compose runtime and it specifically emits a UI Tree.
In my impl, I'm not actually emitting any tree, but that's fine too. Composables are allowed to return values, and they're allowed to (very carefully) do side effects. I'm using Jake Wharton's molecule library, which is intended for using Compose without emitting any tree. In fact, that library is practically an example of a comprehension over StateFlow, and thus it's how this rabbit hole even started because I figured that surely if it can do that, it can probably do delimited continuations.

[Jannis]

Thanks 👍
That would have been useful to have/know a few years ago.
Let's see if I get to work with kotlin again in the future, seems like you can do some cool things with this. Wish my employer would be more into kotlin (or just haskell, but kotlin is probably more achievable for a java company)

[Youssef Shoaib [MOD]]

UPDATE: After much work, I've simplified the implementation to use suspend using reflection (yuck!) to clone `Continuation`s. The library now supports coroutineContext properly too, which allows delimited dynamic variables, or in other words the Reader monad is really easily supported! I haven't implemented dynamic-wind yet because frankly I don't quite understand it yet, but I've implemented a ForkingReader that seems to function intuitively.
A lot of examples for different effects are now supported, including List , State, Reader, and prominently resetWithHandler (which means it should support Algebraic Effects with handlers!).
This is a big update, and I'm desperate for more examples and especially for bug reports. My aim is to work similarly to Racket's delimited continuations while also providing an effect handling system.

[Youssef Shoaib [MOD]]

Let me clarify btw, the reflection used is simply to implement a function of the form copy(completion: Continuation<*>) and a val completion. If those 2 methods were added with a bytecode plugin for instance, or by the compiler itself, no reflection would be necessary. This is analogous to "cutting the stack" at a certain point and "gluing it back" at another, which is how delimited continuations are described.

[simon.vergauwen]

Wow, that's really cool stuff. Incredible work @Youssef Shoaib [MOD] 👏 👏