title: Stackless trampoline Monad/Computation Expression
body: <p>I am working on a functional programming language of my own design and I stumbled on a problem that is beyond my skills to solve. I would like to know if anyone has any advice on how to solve it or a reason for why it is impossible.  </p>
  
  <p>The code below is an overview of a solution that is not the ideal but a compromise.</p>
  
  <p>This problem is at the heart of the runtime system I am currently using. Instead of relying on the .Net stack I am using a monad to perform  operations on a trampoline. This should help with step through debugging and allow for users to not have to worry about stack space. Here is a simplified version of the monad I am currently using.</p>
  
  <pre><code>type 't StackFree =
      |Return of 't                                 //Return a value
      |StackPush of ('t-&gt;'t StackFree)*'t StackFree //Pushes a return handler onto the "Stack"
      |Continuation of (unit-&gt;'t StackFree)         //Perform a simple opperation
  type StackFreeMonad() =
      member this.Delay(fn) = 
          Continuation(fn)
      member this.Bind(expr,fn) =
          StackPush(fn,expr)
      member this.Return(value) =
          Return(value)
      member this.ReturnFrom(x) =x
  let stackfree = StackFreeMonad()
  </code></pre>
  
  <p>This was not the original design but it was the best I could get to work with F# computation expressions in an ideal world the above computation expression would work on this type.</p>
  
  <pre><code>type 't Running = 
      |Result of 't
      |Step of (unit-&gt;'t Running)
  </code></pre>
  
  <p>So in order to convert a StackFree into a Running type I have to use this conversion function</p>
  
  <pre><code>//this method loops through the StackFree structure finding the next computation and managing a pseudo stack with a list.
  let prepareStackFree&lt;'t&gt; :'t StackFree-&gt;'t Running =
      let rec inner stack stackFree = 
          Step(fun ()-&gt; 
              match stackFree with 
              //takes the return values and passes it to the next function on the "Stack"
              |Return(value)-&gt; 
                  match stack with 
                  |[]-&gt;Result(value)
                  |x::xs -&gt; inner xs (x value)
              //pushes a new value on the the "Stack"
              |StackPush(ret,next) -&gt;
                  inner (ret::stack) next
              //performs a single step
              |Continuation(fn)-&gt;
                  inner stack (fn()))
      inner []
  </code></pre>
  
  <p>Here is a brief example of the two types in action. </p>
  
  <pre><code>let run&lt;'t&gt; :'t StackFree-&gt;'t = 
      let rec inner = function 
          |Step(x)-&gt; inner (x())
          |Result(x)-&gt; x
      stackFreeToRunning&gt;&gt;inner
  //silly function to recompute an intiger value using recursion
  let rec recompute number = stackfree {
      if number = 0 then return 0
      else 
          let! next = recompute (number-1)
          return next+1
  }
  let stackFreeValue = recompute 100000
  let result = run stackFreeValue
  do printfn "%i" result
  </code></pre>
  
  <p>I have spent several hours trying to get a Computation Expression that works directly on the Running type and cutting out the middleman StackFree. However I cannot figure out how to do it. At this point I am seriously considering the possibility that a solution to this problem is impossible. However I cannot figure out the reason that it is impossible. </p>
  
  <p>I have gotten close a few times but the resulting solutions ended up using the stack in some confusing way. </p>
  
  <p>Is it possible to have a computation expression that operates on the Running type without utilizing the .Net stack? If this is not possible why is it not possible. There must be some simple mathematical reasoning that I am missing. </p>
  
  <p><strong>NB:</strong> These are not the actual types I am using they are simplified for this questions the real ones keep track of scope and position in the script. Furthermore I am aware of the serious performance cost of this type of abstraction</p>
  
  <p><strong>Edit:</strong> Here is another way to approach the problem. This implementation is flawed because it uses the stack. Is there anyway to get the exact behavior below without using the stack? </p>
  
  <pre><code>type RunningMonad() = 
      member this.Delay(fn) =
          Step(fun ()-&gt;fn ())
      member this.Bind(m, fn) = 
          Step(fun ()-&gt;
              match m with
              |Result(value)-&gt; fn value
              //Here is the problem
              |Step(next)-&gt; this.Bind(next(),fn))
      member this.Return(v) =
          Result(v)
      member this.ReturnFrom(x) = x
  </code></pre>
  
  <p>The bind implementation in the above computation expression creates a function that calls another function. So as you go deeper and call bind more and more you have to chase a bunch of function calls and then eventually you hit a stackoverflow exception. </p>
  
  <p><strong>Edit2:</strong> Clarity. </p>