Wednesday, March 5, 2008

A problem with monads?

It took me a while, but I've finally gotten to the point I wanted to make.

Take a look at the state monad:
(define (bind M f)
  (lambda (ma)
    (let* ((intermediate (M ma))
           (i-state (get-state intermediate))
           (i-value (get-value intermediate))
           (next    (f i-value)))
      (next i-state))))

We would use this monad to chain together a bunch of procedures that will pass a `state variable' around. The procedures aren't actually `chained' though, they are `nested'. In order to extend the chain, we put a wrapper around the existing chain, catch its return value and feed the appropriate elements through to the next function in the chain. The structure is like a set of Russian dolls where the initial function is the smallest and the subsequent functions wrap around it.

When we run this monad, the first thing we have to do is invoke the next inner monad. Of course this monad has to invoke its next inner monad, etc. etc. until we get to the innermost one. The problem is this: each invocation is consuming resources that cannot be released until the inner invocations finish. So before we even start executing the first chained procedure we are allocating resources for every chained procedure that comes after it. A sequence of chained procedures will allocate the stack frame for the last procedure first, and this frame will be retained until the entire monadic computation is complete. If a sequence has, say, twenty chained procedures, we'll push twenty stack frames as the very first operation.

The state monad is not tail recursive.

I suppose this is a trivial point for some people, but I find this to be remarkable. The lack of tail recursion would place limits on the number of procedures that could be chained together in this way. It is unlikely a person would write a program that exceeds the limit and overflows the stack, but it is not at all impossible for a meta-computation to do so. (Imagine an x86 emulator that used the state monad and chained together the procedures that implemented the instruction set.) What I find remarkable is that there appears to be no underlying logical reason why this isn't tail recursive. The chain of procedures is obviously linear and the resources for the final element in the chain aren't really used until that element is computed, yet they are the first to be allocated.

I have some notions about why this isn't tail recursive, but I'm not enough of an expert in monads or category theory to be sure, yet. I'm hoping that someone who is more of an expert can validate or refute the problem. I think the answer is one of these:
  1. Yes, it is a problem and
    • tail-recursion is just incompatible with monads, or
    • monads are so cool that we're willing to live with the problem, or
    • only Haskell people use monads in real life, and in the theoretical realm you can have as much stack as you can imagine
  2. No, it isn't a problem because you can simply rewrite the state monad like this ...
  3. No, it isn't a problem, just wrap your code in the `tail recursion' monad and magic will happen.
  4. You're an idiot because this obvious thing you clearly didn't understand fixes it.
Any opinions or ideas?