nightscape
commented
8 months ago Hey @kitlangton, nice to see you back in the Scala + effects world 😃 I enjoyed your Scala videos very much!! Hope you get to do some more when circumstances allow ❤️
Closed kitlangton closed 7 months ago
nightscape
commented
8 months ago Hey @kitlangton, nice to see you back in the Scala + effects world 😃 I enjoyed your Scala videos very much!! Hope you get to do some more when circumstances allow ❤️
fwbrasil
commented
8 months ago Nice report, thanks :) The bug is actually in the Envs implementation. Vars correctly handles this scenario by adding a map at the end of the handling. I've just pushed a fix: https://github.com/getkyo/kyo/commit/83322eb3ba1b3c6e329f5e2375d47b8676ed4fb1.
I like your example impl! Kyo's core evolved from previous designs and it can use some redesigning. The approach moving the definition of the Command (M in the current impl) from the effect definition to the handler simplifies things and would make it easier to implement some of the patterns in the effects. The new Envs encoding is a good example of that. It's simpler and safer than the current one.
I've reimplemented your example to include Kyo's performance-related optimizations: https://gist.github.com/fwbrasil/81eccff3572078171f75023f790a0504.
Main changes:
handleOne to reflect the fact that both the continuation and the handleOne can have suspensions of the effect. It isn't a limitation in your example because Options only halts with Return but there are more complex effects that can produce new suspensions (not necessarily a return) during handling.Something I don't like much is how the Tag is disassociated from the effect since users could make mistakes but I think it's reasonable since defining new effects shouldn't something part of the day-to-day of users. I'm considering adopting this new encoding and call it "The Langton Encoding" if you don't mind.
BTW, isn't it amazing that we can discuss the design of Kyo's core in short and isolated gists 😍
fwbrasil
commented
8 months ago I've just noticed a bug in my version. When a root is found, it was casting to Result directly. I've added a new handleLast for this case. I don't like how similar the implementations of handleLast and handleOne typically are, though. I wonder if there's a better encoding that avoids the duplication.
kitlangton
commented
8 months ago Haha, I wouldn't at all mind. I actually worked on the Langton Encoding (hahaha) a bit more and ended with this implementation. The major difference here is that I tried out the Frank/Unison style of handler which has to explicitly recurse, versus the recursion occurring in the top-level handle. While this puts a bit more of a burden on the handler implementer, to explicitly recurse, I think the type signature is actually bit more straightforward and allows one to cleanly short-circuit with one's intended result type. (I think this might also obviate the handleLast scenario)
Of course, I'm not sure of the performance consequences of this 😄—in fact, my next piece of homework is to learn more about JVM optimization! So thanks so much for the changes and the explanations, I'll dig into them and try to understand.
BTW, isn't it amazing that we can discuss the design of Kyo's core in short and isolated gists
Yes! Actually, amazingly cool! I've learned so much in re-implementing this a few times—I don't think I ever would've figured it out from the Do Be Do Be Do paper, that wall of equations knocked me unconscious ☠️ .
And since we're chatting: One other thing I noticed is that, at least when decompiling in IntelliJ, the type alias variant of Pending < seemed to box Integers.
type <[+A, -S] >: AWhereas the opaque union type did not.
opaque type <[+A, -S] = A | Zero[A, S]I'm JVM performance neophyte, so I could be totally wrong and confused 😃 But I was curious if returning to the opaque type alias might be possible? The main issue seemed to be the invariance of S in Kyo
abstract class Kyo[M[_], E <: Effect[M, _], T, +U, -S]:
// The S in T < S prevents te covariance annotation
def apply(v: T < S, s: Safepoint[M, E], l: Locals.State): U < S
end KyoBut I actually don't think that's necessary. I was able to remove it in Kyo proper and all the tests pass. Once again, caveat, I could be deeply confused 😆
🥳
fwbrasil
commented
8 months ago I'm leaving for a trip so I won't be able to take a look at the new impl now. Yes, I'd prefer to go back to the opaque type encoding since we don't need to worry about Scala 2 anymore. Regarding boxing, I believe primitive types have to be boxed on both encodings but the way the core is structured allows the JIT to avoid allocations in many cases.
The main issue seemed to be the invariance of S in Kyo
Take a look at my gist, I created a trait to hide the variance from the sub-classes.
kitlangton
commented
8 months ago Awesome :) Checking it out now. Enjoy your trip, Flavio!
UPDATE: I edited the newest version to incorporate your optimizations—and fully embraced T -> U over A -> B (my stubborn Haskell habit 😜)
fwbrasil
commented
8 months ago I love the new version! The apply/handle pair makes the api very flexible and it seems we don't need isRoot 🤯 I've made a few minor changes. If you put the core inside an object it's possible to avoid the implicit conversion because the opaque type becomes visible for the other members in the same scope. https://gist.github.com/fwbrasil/34edd85a912f73354654560437a47e29
I think there's an issue with stack safety, though. Kyo already leverages the stack to evaluate pure computations strictly and to unfold the accumulated transformations when resuming after a suspension, which is generally ok if there's no recursion or very long chains of transformations without suspensions. In the new encoding, the effect handling can keep accumulating frames between the apply and handle calls. If a computation has many effect suspensions, even if without recursion, I wonder if the effect handling could accumulate too many frames.
Something I'd like to have in handlers is first-class support for state.Vars uses a mutable value. It's ok with the current set of effects because we don't have any that "travel back" in the execution and Vars can't be used directly when forking fibers. Basically, their use is local and linear. But, for example, implementing something like Unison's Stepwise would not be possible because it'd be incompatible with the current Vars design.
kitlangton
commented
8 months ago I love the new version! The apply/handle pair makes the api very flexible and it seems we don't need isRoot 🤯 I've made a few minor changes.
Woo hoo! Of course, all credit to Frank! (Though it took a while to parse out the actual type signature 😜 )
If you put the core inside an object it's possible to avoid the implicit conversion because the opaque type becomes visible for the other members in the same scope.
Aha! I knew the "secret" of the opaque type should've been visible in some local context. I'd assumed that would be the file or module it was defined in, and I was confused as to why it wasn't. Apparently, gossip travels fast inside an object—(pssst... did you hear NonEmptyString is actually just a String—how embarrassing!)
In the new encoding, the effect handling can keep accumulating frames between the apply and handle calls. If a computation has many effect suspensions, even if without recursion, I wonder if the effect handling could accumulate too many frames.
Ah, do you mean that this mutually-recursive method might end up accumulating frames at double the rate, leading to more accidental overflows?
Something I'd like to have in handlers is first-class support for state.Vars uses a mutable value. It's ok with the current set of effects because we don't have any that "travel back" in the execution and Vars can't be used directly when forking fibers. Basically, their use is local and linear. But, for example, implementing something like Unison's Stepwise would not be possible because it'd be incompatible with the current Vars design.
Ah, interesting. I think the way Unison handles state like abilities is via partial application, so it's more like the traditional State monad, and less of mutable state. Here's an Unison's KeyValueStore ability example.
Here's an example that works with the Frank-style, explicitly-recursive handler (as usual, I'm unsure of the performance implications 😄):
class States[S: Tag] extends Effect[States[S]]:
override type Command[T] = States.Command[S, T]
object States:
enum Command[+S, +T]:
case Get[S]() extends Command[S, S]
case Set[S](value: S) extends Command[S, Unit]
def get[S: Tag]: S < States[S] = States[S].suspend(Command.Get())
def set[S: Tag](value: S): Unit < States[S] = States[S].suspend(Command.Set(value))
def modify[S: Tag](f: S => S): Unit < States[S] = get[S].flatMap(s => set(f(s)))
def run[S: Tag, T, S2](state: S)(value: T < (States[S] & S2)): T < S2 =
val handler = new SimpleHandler[Command[S, *], States[S]]:
def apply[T, U, S2](command: Command[S, T], k: T => U < (States[S] & S2)): U < S2 =
command match
case Command.Set(v) =>
run(v)(k(()))
case _: Command.Get[S] @unchecked =>
handle(k(state))
handler.handle(value)
object StateExample extends App:
def program: Unit < States[Int] =
for
n1 <- States.get[Int]
_ <- States.set(n1 + 1)
n2 <- States.get[Int]
_ <- States.set(n2 + 1)
_ = println(s"n1 = $n1, n2 = $n2")
_ <- if n2 < 9 then program else ()
yield ()
States.run(0)(program)
// OUTPUT
// --------------
// n1 = 0, n2 = 1
// n1 = 2, n2 = 3
// n1 = 4, n2 = 5
// n1 = 6, n2 = 7
// n1 = 8, n2 = 9Ah, do you mean that this mutually-recursive method might end up accumulating frames at double the rate, leading to more accidental overflows?
Yes, Scala is able to make the effect handling loop in the current impl tail recursive (unless it suspends again):
This is using the CFR decompiler in case you want to take a look. I removed inline of the handle method to check out the bytecode more easily.
Here's an example that works with the Frank-style, explicitly-recursive handler (as usual, I'm unsure of the performance implications 😄):
Nice! I'm not sure about stack safety as well. Not only the core effect handling loop can become stack hungry but the handler itself can also recurse. But thinking it through now, I wonder if it could be ok since these frames collapse as soon as a suspension happen. I'll do some testing.
Should we rename this issue to "The Langton Encoding"? 🤔
fwbrasil
commented
8 months ago Yeah, it seems stack safety can indeed be an issue with the new encoding. If you have multiple suspensions of the same effect, the stack keeps growing. I'm not sure that'd be a common scenario besides benchmarks and tests, though.
object StateExample extends App:
def dump =
var s = "\n***********\n"
val t = Thread.currentThread().getStackTrace()
s += s"Depth: ${t.size}\n"
s += t.mkString("\n")
println(s)
end dump
def program: Unit < States[Int] =
for
n1 <- States.get[Int]
_ <- dump
_ <- States.set(n1 + 1)
_ <- dump
n2 <- States.get[Int]
_ <- dump
_ <- States.set(n2 + 1)
_ <- dump
_ = println(s"n1 = $n1, n2 = $n2")
_ <- if n2 < 9 then program else ()
yield ()
States.run(0)(program)
end StateExampleAh, yeah. I see. This Frank-like encoding accumulates frames like hot cakes.
I tested this first with Kyo, then then the Frank-style.
def dump =
var s = ""
val t = Thread.currentThread().getStackTrace()
s += s"Depth: ${t.size}"
println(s)
def program: Int < Envs[Int] =
for
_ <- Envs[Int].get
_ = dump
_ <- Envs[Int].get
_ = dump
_ <- Envs[Int].get
_ = dump
_ <- Envs[Int].get
_ = dump
_ <- Envs[Int].get
_ = dump
_ <- Envs[Int].get
_ = dump
_ <- Envs[Int].get
_ = dump
_ <- Envs[Int].get
_ = dump
yield 0
// With Kyo
// Depth: 33
// Depth: 33
// Depth: 33
// Depth: 33
// Depth: 33
// Depth: 33
// Depth: 33This test holds a steady size in kyo, yet accumulates frames with the mutually recursive Frank encoding:
// With Frank-style
// Depth: 30
// Depth: 34
// Depth: 38
// Depth: 42
// Depth: 46
// Depth: 50
// Depth: 54
// Depth: 58That's a bummer! ☹️ That encoding was growing on me. Alas, I'm not sure there if there are any tricks other than trampolining which could resolve that.
I think the version that returned a special Halt value might still get tail-rec'd away. But perhaps there are some other challenges there, as it adds another case to match on. Also, the Handle.apply signature is going get a bit uglier, having to return a U < (E & S) | Halt[Result[U]] Eek! 😱
Hrmmm. Much to contemplate! 😄
kitlangton
commented
8 months ago I found a potential solution! It's only slightly insane 😆
If the only thing preventing tail recursion is the Scala compiler not optimizing across separate mutually recursive method bodies, so be it! There must be only one method body. However, if we want the same nice Frank-style signature, then we'll need to use a macro to forge the single fused method body—Frank-ensteined together, if you will! 👹
Behold this just-finished monstrosity!
The call-site:
def runEnv[R: Tag, T, S](env: R)(value: T < (Envs[R] & S)) =
defineHandler[Envs.Input, Envs[R]](
[T, U, S] => (command, k, handler) => handler(k(env.asInstanceOf[T]))
)
.handle(value)What it essentially gets expanded to:
def runEnv2[R: Tag, T, S](env: R)(value: T < (Envs[R] & S)) =
val handler = new MacroHandler[Envs.Input, Envs[R]]:
def handle[T, S](value: T < (Envs[R] & S)): T < S =
value match
case suspend: Suspend[Envs.Input, Any, T, S] @unchecked if suspend.tag.tag == tag.tag =>
this.handle(suspend.apply(env.asInstanceOf[T]))
case suspend: Suspend[MX, Any, T, S] @unchecked =>
new Continue[MX, Any, T, S](suspend):
def apply(v: Any) =
handle(suspend(v))
case v: T @unchecked =>
v
handler.handle(value)The macro implementation:
import scala.quoted.*
abstract class MacroHandler[Command[_], E](using val tag: Tag[E]):
def handle[T, S](value: T < (E & S)): T < S
object Macros:
inline def defineHandler[Command[_], E](
inline f: [T, U, S] => (Command[T], T => U < (E & S), U < (E & S) => U < S) => U < S
): MacroHandler[Command, E] = ${
defineHandlerImpl('f)
}
def defineHandlerImpl[Command[_]: Type, E: Type](
f: Expr[[T, U, S] => (Command[T], T => U < (E & S), U < (E & S) => U < S) => U < S]
)(using Quotes): Expr[MacroHandler[Command, E]] =
import quotes.reflect.*
val body = f.asTerm match
case Inlined(tree, deff, term) =>
term match
case Block(List(DefDef(_, _, _, Some(body))), _) =>
Inlined(tree, deff, body)
case Block(List(), Block(List(DefDef(_, _, _, Some(body))), _)) =>
Inlined(tree, deff, body)
def transform(command: Term, k: Term, handle: Term, tType: TypeTree): Term =
val treeMap: TreeMap = new TreeMap:
override def transformTerm(term: Term)(owner: Symbol): Term =
term match
case ident @ Ident("handler") =>
handle
case ident @ Ident("command") =>
command
case ident @ Ident("k") =>
k
case term =>
super.transformTerm(term)(owner)
override def transformTypeTree(tree: TypeTree)(owner: Symbol): TypeTree =
tType
treeMap.transformTerm(body)(Symbol.spliceOwner)
'{
new MacroHandler[Command, E]:
def handle[T, S](value: T < (E & S)): T < S =
value match
case suspend: Suspend[Command, Any, T, S] @unchecked if suspend.tag.tag == tag.tag =>
val command = suspend.command
val k = suspend.apply
${
transform('command.asTerm, 'k.asTerm, 'handle.asTerm, TypeTree.of[T]).asExpr
}.asInstanceOf[T < S]
case suspend: Suspend[MX, Any, T, S] @unchecked =>
new Continue[MX, Any, T, S](suspend):
def apply(v: Any) =
handle(suspend(v))
case v: T @unchecked =>
v
}The test:
object EnvsExample extends App:
def dump =
var s = ""
val t = Thread.currentThread().getStackTrace()
s += s"Depth: ${t.size}"
println(s)
def program: Int < Envs[Int] =
for
_ <- Envs.get[Int]
_ = dump
_ <- Envs.get[Int]
_ = dump
_ <- Envs.get[Int]
_ = dump
_ <- Envs.get[Int]
_ = dump
yield 0
try
runEnv(0)(program)
println("--")
runEnv2(0)(program)
[info] running zero.EnvsExample
Depth: 27
Depth: 27
Depth: 27
Depth: 27
--
Depth: 26
Depth: 26
Depth: 26
Depth: 26So yeah, obviously the polymorphic function at the call site leaves something to be desired:
defineHandler[Envs.Input, Envs[R]](
[T, U, S] => (command, k, handler) => handler(k(env.asInstanceOf[T]))
)I could also move those type params up todefineHandler[Envs.Input, Envs[R], T, U, S]. Or I could even define them as type members elsewhere 😝. But yeah—just an initial ugly experiment. If nothing else, it's good to have as another potential path for optimization exploration.
Another option would be to have the user define a simple trait in the macro body, which could then be transformed. If annotation macros weren't experimental, this would also be a great use-case for those.
fwbrasil
commented
8 months ago This is getting fun but let's not get desperate here 😂 I don't think the core should have macros in it but it might be ok if uses one. I've played with the handler defined via a method and got close to generating tailrec code: https://gist.github.com/fwbrasil/233f6409c454ac73b219ad4b08be7248
If the function application got reduced at compile-time (new inline function macro?), I think the compiler would be able to make it tail-recursive. But even if we go this path, I'm not sure it's worth the decrease in usability. Defining handlers gets much more confusing 😔
public Object handle(Object value) {
Object object = value;
if (object instanceof core.internal$.Suspend) {
core.internal$.Suspend suspend = (core.internal$.Suspend)object;
LightTypeTag lightTypeTag = suspend.tag().tag();
LightTypeTag lightTypeTag2 = this.tag().tag();
if (!(lightTypeTag != null ? !lightTypeTag.equals(lightTypeTag2) : lightTypeTag2 != null)) {
return ((Function3)new Function3(this){
private final /* synthetic */ anon.8 $outer;
{
if ($outer == null) {
throw new NullPointerException();
}
this.$outer = $outer;
}
public Object apply(Object h, Object c, Object k) {
States.Command command = (States.Command)c;
if (command instanceof States.Command$.Set) {
S s;
States.Command$.Set<S> set = States.Command$.Set$.MODULE$.unapply((States.Command$.Set)command);
S v = s = set._1();
return States$.MODULE$.run(v, ((Function1)k).apply((Object)BoxedUnit.UNIT), this.$outer.ttt$States$$anon$8$$evidence$1$4);
}
if (command instanceof States.Command$.Get) {
return ((core.Handler)h).handle(((Function1)k).apply(this.$outer.ttt$States$$anon$8$$state$2));
}
throw new MatchError((Object)command);
}
}).apply((Object)this, suspend.command(), (Object)suspend);
}
}I've tried to use Scala's mechanism that transforms lambdas into classes if the trait has a single method but it doesn't work when apply is marked as inline. I also tried adding @FunctionalInterface just in case but no luck.
trait ~>[T, U] {
inline def apply(v: T): U
}
val a: Int ~> Int = (_: Int) + 1
// Found: Int => Int
// Required: Int ~> IntYeah 😜 I messed around with that formulation a bit as well. Unfortunately, the cannot inline deferred method error blocks the most promising path.
Before abandoning this weird path, one final act of desperation! I just want to present the least worst variant of this macro-assisted API:
// 1. Define the nice handler as you would normally.
def envHandler[R: Tag](env: R) =
new Handler[Envs.Input, Envs[R]]:
def handleOne[T, U, S](value: T < (Envs[R] & S), k: T => U < (Envs[R] & S)): U < S =
handle(k(env.asInstanceOf[T]))
// 2. Ideally this would work as is, but we've learned that the mutually recursive `handle`
// definition won't get flattened. Therefore, by requiring an opaque implicit, simply
// writing the above code would result in this compilation error/guide....
[error] -- [E172] Type Error: /Users/kit/code/zyo/src/main/scala/zero/zero.scala:73:33 -
[error] 73 | new Handler[Envs.Input, Envs[R]]:
[error] | ^
[error] | You must wrap your Handle definition in `makeHandler`
// 3. Then, you'd simply do what the warning suggested.
def envHandler[R: Tag](env: R) =
makeHandler {
new Handler[Envs.Input, Envs[R]]:
def handleOne[T, U, S](value: T < (Envs[R] & S), k: T => U < (Envs[R] & S)): U < S =
handle(k(env.asInstanceOf[T]))
}Et voila, as before (though without the ugly polymorphic function) the macro would define the handle method where handleOne is inlined correctly.
So yeah, if that's too weird—I totally understand 😄. There are probably bigger Kyo fish to fry!
fwbrasil
commented
8 months ago Fair enough. I think we can keep this ticket open to give it another try. There's probably some simple encoding with the properties we're looking for and we might be able to find it later with a fresh mind :)
fwbrasil
commented
8 months ago I've been giving some more thought to this new encoding. My initial intuition was to avoid a type union as the return of handler.apply because it would require an allocation but I think that's actually not a very relevant concern. I've added a mechanism that allows handlers to recurse and even redefine themselves. The way the code is JIT-compiled makes it generally trivial for the Handle allocation to be elided. The handler.apply method will typically be small enough to be inlined and JIT compilers are able to virtualize the object since its use is immediately after the method call.
Could we be witnessing the grand return of the Langton Encoding? 🤔 https://gist.github.com/fwbrasil/f693c2124003fbd390df18a8d2c001d5
kitlangton
commented
8 months ago Amazing! 😄 This looks great. It maintains all of the properties of the Frank (or Langton, if you prefer 😛) encoding—where one can recurse with different handlers + directly short-circuit—all without losing the tail-recursive stack safety. And I fully trust you when it comes to the JIT-ability of the one additional allocation.
The only cost is the additional complexity to the type signature:
def apply[T, U, S](
command: Command[T],
k: T => U < (E & S)
): (Result[U] < S) | Handle[Command, Result, E, U, S]But, as you mentioned earlier on, "defining new effects shouldn't something part of the day-to-day of users." So, I think the trade is totally worth it. And perhaps the API can be defined slightly differently to make the options clearer—perhaps another opaque combining Result[U] < S | Handle[Command, Result, E, U, S]? Maybe that type can be Handle and have a couple of constructors like halt(result) + handle(this, k(v))? Then apply could look like:
def apply[T, U, S](
command: Command[T],
k: T => U < (E & S)
): Handle[Command, Result, E, U, S]Okay 😆 I just explored that idea some more. Here's another gist for the gist god!
The core idea is here:
abstract class ResultHandler[Command[_], Result[_], E](using val tag: Tag[E]):
opaque type Handled[T, S] = Result[T] < S | Handle[Command, Result, E, T, S]
protected inline def halt[T, S](v: Result[T] < S): Handled[T, S] = v
protected inline def handle[T, S](v: T < (E & S)): Handled[T, S] = Handle(this, v)
protected inline def handle[T, S](h: ResultHandler[Command, Result, E], v: T < (E & S)): Handled[T, S] =
Handle(h, v)Which can then be used like this:
def handler[S: Tag](state: S): Handler[[T] =>> Command[S, T], States[S]] =
new Handler[[T] =>> Command[S, T], States[S]]:
def apply[T, U, S2](command: Command[S, T], k: T => U < (States[S] & S2)) =
command match
case Command.Set(v) =>
handle(handler(v), k(()))
case _: Command.Get[S] @unchecked =>
handle(k(state))(P.S. This is really fun! Thanks for going back and forth with me on this for so long 😆)
fwbrasil
commented
8 months ago cool cool! I actually couldn't hold myself and I'm already making the change 😂 It's amazing how multiple effects become simpler and safer 🤯 I'll incorporate your last change.
I've also identified additional optimizations to avoid allocation of effects like Envs by pushing the tag to the handle/suspend methods instead of in the effect itself + a cheaper way to perform suspensions that seems to enable the IOs effect to be implemented without internal core APIs. It's looking promising!
Thanks Kit!!!! 🙏
kitlangton
commented
8 months ago Awesome! Can't wait to see it 🥳
Also, if you are trying this last API tweak, maybe the Handled type can be a super-type of the result, such that the weird halt method ain't necessary.
opaque type Handled[T, S] >: (Result[T] < S) = Result[T] < S | Handle[Command, Result, E, T, S]Anyhow! Woo! Code up a storm, Flavio! 🤘
fwbrasil
commented
7 months ago @kitlangton I'm still deep into compilation errors and there's a handler that I'm not sure how to make tail recursive.Seqs is already problematic because it calls Seqs.run during handling. The challenge with this effect is that it uses a tail to repeat the same effect handling for each of element of the sequence and the new Handle result can't have continuations appended to it. I'd appreciate if you could check if you can see a good solution for it. I'll keep not tail-recursive for now to continue with the change.
kitlangton
commented
7 months ago @fwbrasil I'm not sure if you needed a non-tail recursive example, but here's one 😄
object Seqs:
def get[T](values: T*): T < Seqs = Seqs().suspend(values)
val handler: ResultHandler[Seq, Seq, Seqs] =
new ResultHandler[Seq, Seq, Seqs]:
def pure[T](v: T): Seq[T] = Seq(v)
def apply[T, U, S](command: Seq[T], k: T => U < (Seqs & S)): Handled[U, S] =
def loop(l: Seq[T], acc: Seq[Seq[U]]): Seq[U] < S =
l match
case Seq() => acc.reverse.flatten
case t +: ts => handler.run(k(t)).map(l => loop(ts, l +: acc))
loop(command, Seq.empty)
end Seqs
object SeqsExample extends App:
def program: (Int, String, Boolean) < Seqs =
for
int <- Seqs.get(1, 2, 3)
string <- Seqs.get("a", "b", "c")
boolean <- Seqs.get(true, false)
yield (int, string, boolean)
val result = Seqs.handler.run(program)
println(s"Result: $result")
// Result: List(
// (1,a,true), (1,a,false), (1,b,true), (1,b,false), (1,c,true), (1,c,false),
// (2,a,true), (2,a,false), (2,b,true), (2,b,false), (2,c,true), (2,c,false),
// (3,a,true), (3,a,false), (3,b,true), (3,b,false), (3,c,true), (3,c,false)
// )I can't see any way to make this tail recursive. But, if it's any consolation, I don't think similar "abilities" in Unison would be stack safe either. I found this example in a tutorial on Handling Choice.
Handling Choice
So if that was a handler calling the continuation 0 times, what about 2 times? Let's see a handler for ability Choice where choose : Boolean, which we met here. This handler runs through a whole tree of possible evolutions of the computation, with a fork at each choose, and collects the results in a list.
choiceToPure : Request Choice a -> [a] choiceToPure r = case r of { Choice.choose -> k } -> (handle k false with choiceToPure) ++ (handle k true with choiceToPure) { a } -> [a]This is the first handler we've seen where the call to handle is not in tail position — i.e. where the return value of handle still needs some further processing (with ++) before returning. Recursive calls in tail position can be made any number of times in sequence, while still using constant space (because the function's stack frame can be reused from call to call). choiceToPure does not have this property. In this case that's probably fine — if you're handling a computation that makes a long sequence of calls to choose, you're likely to run into the exponential growth of the [a] list before the linear growth of the handler stack troubles you.
I bolded that bit at the end. Perhaps that's comforting? 😆 Though maybe we could achieve a stack safe variant with the help of IOs?
fwbrasil
commented
7 months ago I'm not sure if you needed a non-tail recursive example, but here's one
I ended up using run + collect: https://github.com/getkyo/kyo/blob/main/kyo-core/shared/src/main/scala/kyo/seqs.scala#L67
I bolded that bit at the end. Perhaps that's comforting? 😆 Though maybe we could achieve a stack safe variant with the help of IOs?
Ha! Yeah, it doesn't seem that bad. I'll create a ticket to see if we can find a solution to make it tail recursive. I played a bit with introducing a Handlers effect in the core itself to suspend the handling but that introduces too much overhead. Basically a nested handling loop for each effect handling. Another approach I tried was adding Handle as a sub-class of Kyo but that increases the size of the core methods too much because they have to account for the new variation.
My toy replica was a great success, in that I feel like I have a pretty solid understanding of Kyo's core now! 🥳 It's such a beautiful design.
After messing around with my simplified clone for a while, a potential issue with Kyo-proper suddenly struck me. I wrote a quick script, and indeed, there's one particular pattern of Kyo execution which will yield unexpected results.
This is currently evident in the
Envseffect:The problem lies in the implementation of the
handlemethod incore.scala:If the
Kyois a root, then it will simply cast its value to the result. Of course, thevalueof the suspendedEnvs[Int].getwill beInput, asInputisn't resolved unless the Envs handler is called, which will only occur if there's a continuation to be called.I'd imagine this would be an issue for any other effect that also uses a command AST as its value, which does not directly translate to the final return value of the effect handler. With Option + Aborts, it's fine to cast the value, as it is the underlying Option/Either which the effect will return.
I initially thought the
Varseffect would similarly fail, but due to the implementation, one cannot run a singleton KyoRoot of aVar.Get, for instance. However, if users create their own effects which interpret some kind of command DSL, this same issue could occur.Of course, it's unlikely someone will directly
runanEnv.getwithout doing anything else—in fact, it's so rare that it hasn't yet come up 😃. However, perhaps it's worth resolving as it could be confusing when it does occur.One solution might be to
handleLooponce more, even in the case of a root node:Of course, this would cause an infinite loop in many cases, as short-circuiting handlers, like Aborts, return singleton KyoRoots as a means of signaling termination—depending upon this very behavior, that the main handler will cease looping and simply cast their value to the result.
In order to account for that, in my toy implementation, I added one more case to
Kyo.This could then be returned in the effect handler, instead of re-suspending.
Then it could simply be matched on in the top-level handle:
(In my test, I also broke apart the
M[_]into aCommand[_], which would be suspended, and aResult[_]—so each handler could potentially interpret the command into a different result monad—but that's a separate thought 😛 )Anyhow, not sure if that's useful as a potential solution—particularly what the impact on performance would be—but thought I'd throw it out there.
Once again, such a cool library. I've been having so much fun reading through the code. Thanks, Flavio! 😍
(Gist of the very messy toy implementation, in case it is at all helpful)