Stackless trampoline Monad/Computation Expression

Question

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.

The code below is an overview of a solution that is not the ideal but a compromise.

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.

type 't StackFree =
    |Return of 't                                 //Return a value
    |StackPush of ('t->'t StackFree)*'t StackFree //Pushes a return handler onto the "Stack"
    |Continuation of (unit->'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()

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.

type 't Running = 
    |Result of 't
    |Step of (unit->'t Running)

So in order to convert a StackFree into a Running type I have to use this conversion function

//this method loops through the StackFree structure finding the next computation and managing a pseudo stack with a list.
let prepareStackFree<'t> :'t StackFree->'t Running =
    let rec inner stack stackFree = 
        Step(fun ()-> 
            match stackFree with 
            //takes the return values and passes it to the next function on the "Stack"
            |Return(value)-> 
                match stack with 
                |[]->Result(value)
                |x::xs -> inner xs (x value)
            //pushes a new value on the the "Stack"
            |StackPush(ret,next) ->
                inner (ret::stack) next
            //performs a single step
            |Continuation(fn)->
                inner stack (fn()))
    inner []

Here is a brief example of the two types in action.

let run<'t> :'t StackFree->'t = 
    let rec inner = function 
        |Step(x)-> inner (x())
        |Result(x)-> x
    stackFreeToRunning>>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

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.

I have gotten close a few times but the resulting solutions ended up using the stack in some confusing way.

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.

NB: 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

Edit: 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?

type RunningMonad() = 
    member this.Delay(fn) =
        Step(fun ()->fn ())
    member this.Bind(m, fn) = 
        Step(fun ()->
            match m with
            |Result(value)-> fn value
            //Here is the problem
            |Step(next)-> this.Bind(next(),fn))
    member this.Return(v) =
        Result(v)
    member this.ReturnFrom(x) = x

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.

Edit2: Clarity.

Answer 1

Better late than never!

This is addressed in section 4 of Stackless Scala with Free Monads. Bjarnason tackles the problem by adding a new constructor to the Trampoline datatype, representing a subroutine call to another trampoline. He keeps this new constructor private, in order to ensure that you can't build left-nested Binds (which would overflow the stack when executing the trampoline).

I am by no means an F#er, but I'll muddle through. In WishF#ul, an imaginary dialect of F# which I just made up, you can express the new existentially quantified constructor directly:

type Tram<'a> =
    | Done of 'a
    | Step of (unit -> Tram<'a>)
    | Call<'x> of Tram<'x> * ('x -> Tram<'a>)  // don't export this

type TramMonad() =
    member this.Return(x) = Done(x)
    member this.Bind(ma, f) = match ma with
        | Call(mx, k) -> Call(mx, fun x -> this.Bind(k(x), f))
        | _ -> Call(ma, f)
    // i confess to not quite understanding what your Delay and ReturnFrom methods are for

let tram = new TramMonad()

let rec runTram t =
    let next mx f = match mx with
        | Done(x) -> f x
        | Step(k) -> Step(fun () -> tram.Bind(k(), f))
        | Call(my, g) -> tram.Bind(my, fun x -> tram.Bind(g x, f))

    match t with
        | Done(x) -> x
        | Step(k) -> runTram(k())
        | Call(mx, f) -> runTram(next mx f)

Note that all of the recursive calls to runTram are in tail position. It takes a bit of puzzling, but you can convince yourself that Bind won't construct a deeply-nested continuation, so runT will always operate in O(1) stack space.

Sadly we're working in F#, not WishF#ul, so we have to resort to an object-oriented encoding of the existential type in the Call constructor. Here goes...

module rec Trampoline =
    type Call<'a> =
        abstract member Rebind<'b> : ('a -> Tram<'b>) -> Tram<'b>
        abstract member Next : unit -> Tram<'a>
    type Tram<'a> =
        | Done of 'a
        | Step of (unit -> Tram<'a>)
        | Call of Call<'a>

    type TramMonad() =
        member this.Return(x) = Done(x)
        member this.Bind(ma, f) =
            match ma with
                | Call(aCall) -> aCall.Rebind(f)
                | _ -> call ma f
    let tram = new TramMonad()

    let rec call<'a, 'x>(mx : Tram<'x>) (f : 'x -> Tram<'a>) : Tram<'a> = Call {
        new Call<'a> with
            member this.Rebind<'b>(g : 'a -> Tram<'b>) : Tram<'b> =
                call<'b, 'x> mx (fun x -> tram.Bind(f x, g) : Tram<'b>)
            member this.Next() =
                match mx with
                    | Done(x) -> f x
                    | Step(k) -> Step(fun () -> tram.Bind(k(), f))
                    | Call(aCall) -> aCall.Rebind(f)
    }

    let rec runTram t =
        match t with
            | Done(x) -> x
            | Step(k) -> runTram(k())
            | Call(aCall) -> runTram(aCall.Next())

I recommend reading the whole paper, which goes on to generalise this stackless construction to any free monad, not just trampolines (which are Free (Unit -> _)). Phil Freeman's Stack Safety for Free builds on this work, generalising the trampoline paper's free monad to a free monad transformer.