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, Oct 16 '16 at 18:59
I've update code snippet to most possible concise which could be compiled. — baio, Oct 16 '16 at 20:00
Computational expression code from above, not compiled as tail recursive I wan't to make it so... — baio, Oct 17 '16 at 05:57
@baio - That `iterRec` function looks strange to me. At what point is it ever going to yield any value other than None? Are you perhaps missing a `yield x` line just below the `let! x = xopt` line? — rmunn, Oct 17 '16 at 08:34
@balo how do you know that it's "not compiled as tail recursive"? — Fyodor Soikin, Oct 17 '16 at 12:36
@FyodorSoikin because of stack owerflow exception, and here clearly iterRec is not latest invocation in procedure. — baio, Oct 17 '16 at 13:12
@rmunn I know logic of code doesn't make sense, for issue its not important I just have infinite loop, but this loop shouldn't throw stackoverflow — baio, Oct 17 '16 at 13:15
Yes, `iterRec` _is_ the latest invocation in the function `fun x -> iterRec( ... )`. So you're getting stack overflow? Ok, now we're getting somewhere. Where does SO happen? Which function is the point of recursion? Also of interest: what's your OS and runtime? — Fyodor Soikin, Oct 17 '16 at 13:28
Note that by default when you run in debug mode tailcalls are not enabled, which might affect your observations. — kvb, Oct 17 '16 at 14:52

score 3 · Accepted Answer · answered Oct 18 '16 at 21:39

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.

Still wandering how `seq` monad is implemented since it not throwing exceptions in the cases like in first approach even in debug mode. — baio, Oct 19 '16 at 00:54
I can't check right now but I believe it's because `Seq` is a lazy sequence which essentially turns it into a trampoline. If you are interested I created a generic trampoline snippet: https://gist.github.com/mrange/63dffe4b525e88fd411f28c8a4847946 — Just another metaprogrammer, Oct 19 '16 at 06:58
Wow, new concept to learn ) Have heard about trampolines here https://www.youtube.com/watch?v=hzf3hTUKk8U&t=925s. Thanks again. — baio, Oct 19 '16 at 07:49

F# recursive bind in computational expressions and tail recursiveness

1 Answers1