F# recursive bind in computational expressions and tail recursiveness

Question

I'm trying to understand how to invoke properly recursive functions in computational expressions and don't get stack overflow exception. As I understand this is quite known issue, but still can't grasp the concept. Maybe somebody have simple explanations or examples for this.

Here my the example I want trace builder have behavior similar to seq but not working with seq monad instead with some other one, for example option and return only latest non None value from recursive loop. Is it possible ?

This is just example, code will run infinitely but there is shouldn't be stackowerflow exception

As I understand problem with stack overflow in Combine method, code just keep invoke f() function in recursive loop, and I want to avoid this and make this invocation tail recursive, ie code should be compiled in regular loop.

type TraceBuilder() = 

    member __.Bind (m: int Option, f: int -> int Option) : int Option =
         match m with
         | Some(v) -> f v
         | None -> None

    member this.Yield(x) = Some x

    member this.YieldFrom(x) = x

    member __.Delay(f) = f

    member __.Run(f) = f()

    member __.Combine (a, f) = 
        match a with
        | Some _ -> a    
        | None -> f()    

let trace = new TraceBuilder()

let rec iterRec (xopt: int Option) = 
    trace {        
        yield! None
        let! x = xopt        
        yield! iterRec(Some(x + 1))
    }


[<EntryPoint>]
let main argv = 
    let x = iterRec(Some(0))
    //x = startFrom(0) |> Seq.take(5000) |> Seq.toList  |> ignore
    printfn "%A" x

Thinking code in comp. expression should is compiled

let iterRec xopt = 
    combine (None, (fun () ->
              bind(xopt, fun x -> iterRec(Some(x+ 1)))

And looks like in this case iterRec invocation is not tail recursive, so whats why stackoveflow, is it possible to implement this logic tail recursive ?

Read these links, still can't figure out the solution :

(How) can I make this monadic bind tail-recursive?

Here suggestion how to resolve issue using FsControl lib, but is it possible to resolve issue using regular computational expressions ?

Recursive functions in computation expressions

Avoiding stack overflow (with F# infinite sequences of sequences)

https://fsharpforfunandprofit.com/posts/computation-expressions-builder-part5/

The invocation of f() in Combine is already tail-recursive. It's not quite clear what your problem is. Perhaps it would help if you could construct a smaller example. — Fyodor Soikin
I've update code snippet to most possible concise which could be compiled. — baio
@balo how do you know that it's "not compiled as tail recursive"? — Fyodor Soikin
Note that by default when you run in debug mode tailcalls are not enabled, which might affect your observations. — kvb

Just another metaprogrammer Just another metaprogrammer · Accepted Answer · 2016-10-18T21:39:32

I removed parts of the code I felt wasn't necessary for the issue. Note that I also find your Combine definition confusing. It might be cute but it would throw me off completely as Combine should behave similarily to Bind in that two operations are chained together. Your Combine operation is close what is normally a OrElse operation.

Anyway:

module Trace =
  let treturn a = Some a
  let tbind a b =
      match a with
      | Some(v)  -> b v
      | None     -> None
  let (>>=) a b = tbind a b

open Trace

// Will throw on Debug (and most likely Mono)
let rec iterRec xopt l =
  xopt >>= fun x -> if x < l then iterRec(Some(x + 1)) l else Some x

[<EntryPoint>]
let main argv =
  let x = iterRec_(Some(0)) 100000
  printfn "%A" x
  0

iterRec throws StackOverflowException in Debug and jitters that doesn't recognize the .tail attribute.

It's a bit easier to understand what happening by looking at iterRec disassembled (using ILSpy for instance`)

iterRec is equal to:

public static FSharpOption<int> iterRec(FSharpOption<int> xopt, int l)
{
  return Program.Trace.tbind<int, int>(xopt, new Program.iterRec@13(l));
}


internal class iterRec@13 : FSharpFunc<int, FSharpOption<int>>
{
  public int l;

  internal iterRec@13(int l)
  {
    this.l = l;
  }

  public override FSharpOption<int> Invoke(int x)
  {
    if (x < this.l)
    {
      return Program.iterRec(FSharpOption<int>.Some(x + 1), this.l);
    }
    return FSharpOption<int>.Some(x);
  }
}

The two functions are mutually recursive but on Release builds the .tail attribute helps the Jitter avoid growing the stack.

One sees the .tail attribute when disassembling to IL.

IL_0008: tail.
IL_000a: call class [FSharp.Core]Microsoft.FSharp.Core.FSharpOption`1<!!1> Program/Trace::tbind<int32, int32>(class [FSharp.Core]Microsoft.FSharp.Core.FSharpOption`1<!!0>, class [FSharp.Core]Microsoft.FSharp.Core.FSharpFunc`2<!!0, class [FSharp.Core]Microsoft.FSharp.Core.FSharpOption`1<!!1>>)

Unfortunately not all Jitters care about .tail which is why I am hesistant to rely on it and would rewrite iterRec to a tail recursive function that F# is able to unpack:

let rec iterRec_ xopt l =
  // This F# unpacks into a while loop
  let rec loop xo =
    match xo with
    | Some x  -> if x < l then loop(Some(x + 1)) else xo
    | None    -> None
  loop xopt

Checking this function in ILSpy:

internal static FSharpOption<int> loop@17(int l, FSharpOption<int> xo)
{
  while (xo != null)
  {
    FSharpOption<int> fSharpOption = xo;
    int x = fSharpOption.Value;
    if (x >= l)
    {
      return xo;
    }
    int arg_1E_0 = l;
    xo = FSharpOption<int>.Some(x + 1);
    l = arg_1E_0;
  }
  return null;
}

No longer recursive this function will execute fine on Debug Jitters as well as mono.

Another approach is to implement a trampoline pattern to trade stack space for heap space.

F# recursive bind in computational expressions and tail recursiveness

1 Answers