Comment by LegionMammal978
2 days ago
Sometimes the messy translation into an explicit stack and dispatch loop is necessary, if you want to pause the calculation, serialize the current state, and reconstitute it later. (E.g., if you want to add disk-saved checkpoints, a frequent hassle in some of my projects.) Coroutines can get you the equivalent of pausing and resuming for a recursive routine, but I'm not aware of any language that lets you serialize the call stack.
> I'm not aware of any language that lets you serialize a whole call stack.
That's basically what continuations provide. Scheme, SML, and others provide them.
Continuations allow an inactive call stack to sit around in memory. But do any of those languages let you save a continuation to a file and resume it in a different execution of the program, without massive contortions to the code? That's what I mean by serialization.
Seems potentially interesting to explore what would be required to store durable continuations. Feels very related to incrementalization and provenance, as you can see materializing a continuation to disk (whatever storage backend) requiring dependence tracking to do anything other than simply snapshotting the whole program state. I am just spitballing though, not sure if anyone has actually tried this.
It is much easier and more maintainable to convert to continuation passing style. If you also use defunctionalization to allocate closures on a stack instead of a fresh heap allocation for every closure, you will achieve performance on par with an explicit stack. (In fact, defunctionalization is a mechanical transformation the produces exactly the data you would store in an explicit stack!)
Before I knew about CPS and defunctionalization, I wrote a Python decorator that did exactly the transformation you describe. https://github.com/tylerhou/fiber. Now I know about CPS and defunctionalization, I realize that my work was not the best implementation (but it was a fun learning experience!).
It's not just pausing and resuming that I'm looking for, but serialization into a form that can be saved to and loaded from files. (Another commenter calls this "materialization" of continuations.) In that regard, the problem with CPS is that continuations are totally opaque (or nearly so) in every language I'm aware of: you aren't able to do anything with them except resume them within the same execution of the program. Do any of your "defunctionalization" implementations offer such a feature?
Defunctionalization is a general technique that allows one to serialize functions as data. You’ve almost certainly used this technique before without realizing it was an instance of defunctionalization.
There is a library for Haskell that will do it. Though it doesn't support all GHC versions. It's very nifty if you need it.
https://github.com/jberthold/packman