Question About Support for Non-Scoped Resumption

[ymdryo]

Hello. I am currently interested in experimentally implementing an effect system library that supports Non-Scoped Resumption in mpeff, based on speff.

I noticed that you had previously attempted something similar to what I am trying to do in commit 934f2c40, but later removed it in commit 6e2629ea. It would be extremely helpful if you could share what happened during this process. Is there an inherent difficulty in implementing this?

[re-xyr]

Thanks for your interest in the library! I haven't thought about the code of speff for a while now, so my recollection is vague, but I remember that the benchmark I ran on 934f2c4 gave abysmal results (about an order of magnitude slower than scoped resumptions), so I gave it up. I think it would be remarkable to somehow implement unconstrained resumptions with only a small performance penalty (no one has figured it out yet).

The semantics in my code might have also been wrong -- I'm not a good theorist so I wasn't able to reason it through. I would love to be updated on your progress!

[ymdryo]

Thank you for your reply! Over the past two weeks, I've conducted some experiments and have also come to realize that speed becomes a bottleneck when extending speff with NSR. (I, too, am not very confident about the semantics—in fact, the paper of Generalized Evidence Passing is difficult for me, but I managed to analyze the code of mpeff. After extending it and running some tests, it seems to adapt to speff without semantic issues.)

Since I'm not very familiar with the performance characteristics of Haskell, I wasn't very confident about the speed of the code I wrote, so your response was extremely helpful.

The performance of speff, especially regarding evidence vectors, is truly impressive. I will continue working on performance improvements in NSR extensions and will report any progress!

[ymdryo]

It seems that I've managed to resolve the order-level inefficiency of non-scoped resumptions. In coroutine benchmarks, the computation time was $O(n^2)$ with respect to the number of loop iterations $n$, making it extremely slow[^1]. The cause of this issue appeared to be exactly the problem addressed in the paper Reflection without Remorse. Specifically, when the continuations accumulate in the third component (b -> Eff es a) of Control, the left-associative accumulation was the problem. By replacing this part with the FTCQueue[^2] used in freer-simple, the issue was improved.

[^1]: The benchmark regarding the order was conducted by @viercc. [^2]: A data structure that allows efficiently decomposing (uncons) a list that has been snoc-ed (left-associated) in a right-associative direction.

Here is the commit.

https://github.com/ymdryo/speff/commit/d441dcedfc6a5e14f125ba26bbb9e43a89ec92a2

(In this version, a significant amount of code has been removed to simplify the work. In particular, higher-order effects are not functioning correctly. I believe it should be possible to restore them to working without much problem. Additionally, an interesting point is that this order-level slowness seems to be present not only in mpeff but apparently in eff as well.)

I plan to write a more detailed article about this in due course.

I have a question: Currently, I am considering releasing this NSR-supported extension of speff as a practical effect system and uploading it to Hackage. I will take on the maintenance. So, regarding this fork, do you have any requests or preferences? For example, instead of forking the repository, you might prefer me to send PRs to this repository; or you might want me to change the name or keep it as speff, etc.