Tail-recursive function calls that have their parameters passed by the pipe operator are not optimized as loops

[teo-tsirpanis]

Because F# is a language that heavily uses recursion, its compiler employs a trick that is called "tail call optimization". With this trick, the last function a function calls (even when it is not herself) does not burden the stack. This allows tail recursion to be essentially a loop, in terms of stack pressure. Because stack frames are removed, the debugging experience is hindered, so tail call optimization is enabled in the Release mode by default.

What is more, if this last function that gets called is the function itself, in certain circumstances, the compiler removes the recursion completely and converts the function into a real, actual loop. This optimization is done even in Debug mode.

Let's look at the following, tail-recursive factorial function:

let factorial x =
  let rec impl x acc =
    if x = 0UL then
      acc
    else
      impl (x - 1UL) (x * acc)
  impl x 1UL

It gets converted to the following C#-equivalent code:

internal static ulong impl@2-75(ulong x, ulong acc)
{
  while (x != 0L)
  {
    ulong num = x - 1L;
    acc = x * acc;
    x = num;
  }
  return acc;
}

public static ulong factorial(ulong x)
{
  return impl@2-75(x, 1uL);
}

It is a lean and mean while loop, nothing to be envied by C# developers.

However, let's write our function this way:

let factorial x =
    let rec impl x acc =
        if x = 0UL then
            acc
        else
            impl (x - 1UL) <| x * acc
    impl x 1UL

See the penultimate line? It has a pipe operator, that spares us a pair of parentheses. A common practice by functional programmers. The code is semantically the same. However, the generated code is totally different:

internal sealed class impl@2-77 : OptimizedClosures.FSharpFunc<ulong, ulong, ulong>
{
  [CompilerGenerated]
  [DebuggerNonUserCode]
  internal impl@2-77()
  {
  }

  public override ulong Invoke(ulong x, ulong acc)
  {
    return impl@2-76(x, acc);
  }
}

internal static ulong impl@2-76(ulong x, ulong acc)
{
  FSharpFunc<ulong, FSharpFunc<ulong, ulong>> fSharpFunc = new impl@2-77();
  if (x == 0L)
  {
    return acc;
  }
  return fSharpFunc.Invoke(x - 1L).Invoke(x * acc);
}

public static ulong factorial(ulong x)
{
  return impl@2-76(x, 1uL);
}

With this small change, the function turned into normal recursive one, which also uses linear memory (one allocation per loop step). If we compile it in Release mode, there will be no problems, as the compiler will emit tail. calls. But in Debug mode, there is a very real danger of stack overflow for big loops recursions.

---

I also observed that this function:

let factorial x =
  let rec impl x acc =
    if x = 0UL then
      acc
    else
      impl <|| (x - 1UL, x * acc)
  impl x 1UL

generates a loop, just like the first one.

And if we call impl like this: (impl (x-1UL)) (x * acc), the compiler produces suboptimal code once again.

---

My guess is that the compiler cannot understand that we are partially applying a function and immediately apply the rest of it. We didn't even store the curried function in a variable!

The pipe operator x |> f is a shortcut for f x. Same with (x1, x2) ||> f, being f x1 x2. The compiler just has to learn that x2 |> f x1 means f x1 x2, and not (f x1) x2.

Furthermore, because stack overflows are hard-to-diagnose, a developer would have to dig his code deep enough to find that the pipe operator is responsible. A fix would make this kind of elegant functional code more performant.

[cartermp]

This pattern:

x2 |> f x1 --> (f x1) x2

is a soundness behavior. Since f x1 is perfectly valid due to how currying works, and F# uses currying, it's sound. Trying to piece this apart in various scenarios/patterns is tricky business that has the risk of leading to situations where a pipeline that someone wants to "break up" might result in different behavior due to not accounting for something tricky or whatever. In this case, it's always the same behavior.

Another thing worth mentioning:

impl (x - 1UL) <| x * acc

can be thought of as:

op_leftPipe impl (x - 1UL) (x * acc)

And this isn't optimized due to what I mentioned earlier. Everything can change, so I wouldn't consider this behavior immutable. But this is the likely rationale.

[teo-tsirpanis]

I agree, but on our example, we have defined impl like that:

let rec impl x acc = // ...

From the moment we have passed x, until we pass acc (and the function gets executed), no observable side effect happens.

But even if we had defined impl like that:

let rec impl x =
  printfn "x is %d" x
  fun acc ->
    printfn "acc is %d" // ...

and used it like that:

let x = impl 6 17
let y = (impl 10) 3

it would have printed:

x is 6
acc is 17
x is 10
acc is 3

The side effects are still exhibited, and in the same order we have been expecting.

If however we had called the functions like that:

let f = impl 6
let y = impl 10 3
let x = f 7

things are going to change:

x is 6
x is 10
acc is 3
acc is 7

But nobody had said we should optimize this case!

[dsyme]

First, don't use the <| operator so much :)

Second, you are correct, we don't guarantee to optimize uses of f <| x or x |> f or any similar to first-calling tailcalls even if f x is a tailcall.

[teo-tsirpanis]

If we won't fix it, could we at least issue a compiler warning in the likes of "using the pipe operator does not optimize the recursive tail-call into a loop"?

But we should be careful not to warn in cases of something like this:

let rec f x1 x2 =
    // [...]
    (x1 - 1, x2 - 1) ||> f
    // [...]

[abelbraaksma]

I remember that somewhere there's a WIP that attempted to issue a warning if recursive functions were not tail call optimized. I think such warning would've gone a long way helping with analyzing your functions here. I don't recall the status of that effort, though.

Btw, I think the Core definitions for |> and the like are not marked inline. I wouldn't be surprised if tail calls worked as expected by the OP if you overloaded those operators to be inlined (though I didn't check myself).

[teo-tsirpanis]

Btw, I think the Core definitions for |> and the like are not marked inline. I wouldn't be surprised if tail calls worked as expected by the OP if you overloaded those operators to be inlined (though I didn't check myself).

I'm afraid it isn't true. I just tested it.

[cartermp]

Tagging as feature improvement - I think we'd accept a PR that made progress here, but I don't think it's a priority at the moment.

[TysonMN]

I remember that somewhere there's a WIP that attempted to issue a warning if recursive functions were not tail call optimized. I think such warning would've gone a long way helping with analyzing your functions here. I don't recall the status of that effort, though.

Are you thinking of PR #1976?

[abelbraaksma]

@TysonMN, yep, that's one, good find! Iirc, it was far from trivial to implement properly, but maybe someone can resurrect it and continue the effort?

It's quite a common mistake that people use the pipe operators and expect recursion to be tail-called (even though it technically isn't, as there's still "work to be done", the the tail is not clean). A warning would certainly help here.

[TysonMN]

It's quite a common mistake that people use the pipe operators and expect recursion to be tail-called (even though it technically isn't, as there's still "work to be done", the the tail is not clean).

Oh, I never thought of it like that. Interesting. Knowing that will help me front making this mistake.