[Idea] Stack-Safe variant of ContT (not 100% sure)
clinuxrulz opened this issue · 17 comments
One obvious problem with JavaScript is the lack of tail call elimination. Continuations are tail-recursive, it would be nice if we could have a stack-safe implementation for JavaScript.
One trick under our belt is the Trampoline monad.
a -> b happens to be isomorphic to a -> Trampoline b
so we can actually go newtype ContT r m a = ContT ((a -> Trampoline (m r)) -> Trampoline (m r))
here is an attempt: http://pastebin.com/VHet6yA4
and the test.
> runIdentity $ runContT (tailRecM (\(Tuple a n) -> if n<=100000 then return $ Left (Tuple (a+n) (n+1)) else return $ Right a) (Tuple 0 0)) pure
705082704
Which has avoided stack overflow in ContT.
However I am unsure if this methods. Because the MonadRec instance for ContT r m was not defined in terms of any MonadRec instance for m. So this implementation can not be quite right, but I think its close. Maybe a MonadSuspend class will work around that issue?
Sounds useful. We should try to construct a sequence of left and right-associated binds, like in the tests in free.
Thinking about free, Co is built on FreeT
Maybe something like the following will work.
data Suspend a =
| Suspend (Unit -> a)
| Done a
type Suspender = Co Suspend
newtype ContT r m a = ContT ((a -> Suspender m r) -> Suspender m r)
using a Coroutine to add the ability to suspend to any base monad.
I haven't had time to test this one. But it may have a more sane MonadRec instance.
Edit: would need m to be an instance of something like MonadSuspend in order to go from Suspender m r to m r in runContT. I guess the coroutine does not help the situation. :p
After having a bit of a play with the code. A Suspender coroutine seems more tidy than a MonadSuspend class. With the MonadSuspend class you would need to design another variant of Eff to mix Eff with ContT, but with Suspender you can have a simple forever loop on the outside of runContT breaking free of the loop when Suspender is done (with of course means a different type-signature for this version of runContT).
The problem now is that purescript-transformers would end up with a cyclic dependency with purescript-free, I've put my hands into fire again. :p
So I guess it should be another library like purescript-stacksafe, purescript-stacksafe-contt or something like that.
Isn't type Suspender = FreeT Identity enough?
Using FreeT Identity. ContT Unit (Eff eff) a with a large number of binds would execute fine producing Eff eff a. However the moment you go to unbox Eff eff a (or perform the effect of Eff eff a) you would get a Stack Overflow. So the code way up top is effectively only safe for Cont r a, not ContT r m a. Thats why I'm hunting type Suspender = FreeT, to put the actual work of suspension into the base monad.
Either way, I think this would be best solved outside transformers, in another library. That way, circular dependencies are not an issue.
agreed
Edit: I'll close this for now.
I'm going to reopen this because I've had great success. The stack-safe ContT no longer depends on FreeT. I've looped 1000000 times with a base monad of Eff (console :: CONSOLE) with no stack overflow. Plus it uses MonadRec to avoid stack overflow.
and the test case: https://github.com/clinuxrulz/purescript-cont-stack-safe/blob/master/test/Main.purs
I tried my best to use FreeT but evaluation kept leading to stack overflow.
Also ContT now has the exact same type signature as the proper ContT apart from the extra constraint.
You may want to consider this as a part of transformers
Interesting, thanks.
Does this work for both left and right associated binds?
Is there a simple (informal) proof of its safety?
I believe ContT re-associates binds from left associative to right associative. But I would need some benchmarks / profiling to confirm this.
This is an new invention, and there is no proof yet. I lack the skills to create a vigorous proof.
But I can say that it is exciting if this does work, for it is stack-less. Imagine stack-less Aff, stack-less green threads etc. And the fact that every monad in existence can be implemented in terms of callCC, means that every monad in existence can be implemented in a stack-less way (ContT is the mother of all monads, all monads can be implemented with ContT). That said I would not implement every monad that way, for it does have additional overhead and would hurt performance a little.
Edit: As for proof of stack safety, every call that wants to go deeper has suspend applied to it in its implementation, which makes in fall back to the MonadRec instance of m to carry on. Thats all I can say.
This is definitely exciting if it can be shown to work, but I think the best way forward for now would be to develop a proof of concept in a separate repo, along with a test suite to demonstrate the safety of various nested binds and measure performance.
When I said "proof", I just meant something informal, not necessarily rigorous. Like for FreeT, we can see that binds get thunked, and only evaluated one-by-one in the tail recursive runFreeT function.
ok, i'll keep it a separate repo... where I ran into trouble with FreeT was, when I had SuspendT implemented with FreeT, the use of SuspendT did not have a single bind in it, and the stack overflow was caused in the SuspendF's (the F-algrebra of suspend?) map function.. It avoided all bind thunks.
I'll see if I can understand how Free's benchmarks work and try to make the same sort of thing.
some results are in. My computer ran out of heap space on the larger tests (probably because of playing youtube for my daughter).
See: https://github.com/clinuxrulz/purescript-cont-stack-safe/blob/master/README.md
Edit: On the larger tests I had to keep my number of binds below a million, because my computer ran out of heap space (with youtube closed :p). My computer is a 4GB Mac Mini.
The shape of the plots seems to be linear with the number of binds in both Free and the stack-safe ContT.
Just to mention, for running larger tests it might help to add the node option --max_old_space_size when running the tests. For my machine with 8GB of ram I used --max_old_space_size=8000 in the past to get iterations into the millions.
@ethul thanks for the suggestion. It did help me get passed 1 million, but then I crashed on 1.5 million. I'll have to wait until I can hop on a better computer.
Glad it helped a bit!
I'm going to close this issue now. So I'm not spamming this project. Further discussions can be made by making Issues on the stack-less project repositories.
The project is renamed and split into two parts.
The stack-safe ContT is now: https://github.com/clinuxrulz/purescript-stackless-cont
The stack-less monad transformer is now: https://github.com/clinuxrulz/purescript-stackless
The stackless monad transformer StacklessT is code-wise is Identical to stack-safe ContT. Just that it is built around a Codensity rather than a Continuation. Due to the code being identical, the performance is also identical (roughly 3 times the speed of Free for both left and right associative binds).
Codensity is just a smaller fish than a Continuation. And it just so happens that CodensityT m a is isomorphic to m a. This is what makes StacklessT a general stack-less monad transformer for any given base monad that is an instance of MonadRec.
A side node: A quick and easy stackless Aff can be made by StacklessT Aff, this allows heavy use of purescript-foldable-traversable without blowing the stack. It still decends 100 levels into the stack, then swaps stack-space for heap space as tailRecM does, but it allows you to use other methods like those in purescript-folable-traversable that do not use tailRecM and still avoid stack overflow.