[<TailCall>] does not protect against broken tail calls in nested unit-returning functions

[IS4Code]

Repro steps

type Expr = 
  | Number of int
  | Add of Expr * Expr

module Evaluator =
  [<TailCall>]
  let rec private eval expr (cont: int -> unit) =
    match expr with
    | Number n -> cont n
    | Add(left, right) ->
      eval left (fun leftVal ->
        eval right (fun rightVal -> cont (leftVal + rightVal)))

Expected behavior

The TailCall attribute should be consistent with the actual behaviour of the function. That means either:

• eval is actually tail-recursive, or
• eval is not tail-recursive and using the attribute results in a diagnostic.

Actual behavior

The attribute is accepted without warnings/errors, but the function is not tail-recursive. Compilation reveals two places where it is prevented:

• eval calls cont which, being a function type, returns null : unit, however eval itself is compiled as void-returning, and so pop needs to be used to get rid of the unit value before returning.
• The continuation calls eval but needs to produce a new null value.

Known workarounds

Since this is caused by the duplicity of the unit type, using any other type (even _) works, since in that case the return types match.

Related information

The original issue was brought up first on StackOverflow. I am not sure if this could be fixed entirely in a way that makes the tail-call optimization possible ‒ the only option seems to be to duplicate the method with an actual Unit return and use that version when beneficial, but in either case, this behaviour is counter-intuitive and [<TailCall>] should protect against it.

Tested on .NET 9.

[brianrourkeboll]

using any other type (even _) works, since in that case the return types match.

Interesting. I think this has something to do with where and when the compiler does unit-elimination (compiling unit as void).

Since eval is a module-bound function and is compiled to a regular .NET static method, as long as eval's return type is known to be unit (e.g., by annotating the return type of cont or of eval itself), unit-elimination is applied and its unit return type is compiled as void instead.

The closure types that the compiler generates for the continuations, however, are given Invoke methods with a unit return type. It seems that unit-elimination is not being applied to these, but that unit-elimination has already been applied to eval by the time it is (mutually-recursively) called inside the body of Invoke:

[CompilationMapping(SourceConstructFlags.Module)]
public static class Evaluator
{
    [Serializable]
    internal sealed class eval@11-1 : FSharpFunc<int, Unit>
    {
        public FSharpFunc<int, Unit> cont;

        public int leftVal;

        [CompilerGenerated]
        [DebuggerNonUserCode]
        internal eval@11-1(FSharpFunc<int, Unit> cont, int leftVal)
        {
            this.cont = cont;
            this.leftVal = leftVal;
        }

        public override Unit Invoke(int rightVal)
        {
            return cont.Invoke(leftVal + rightVal);
        }
    }

    [Serializable]
    internal sealed class eval@10 : FSharpFunc<int, Unit>
    {
        public FSharpFunc<int, Unit> cont;

        public Expr right;

        [CompilerGenerated]
        [DebuggerNonUserCode]
        internal eval@10(FSharpFunc<int, Unit> cont, Expr right)
        {
            this.cont = cont;
            this.right = right;
        }

        public override Unit Invoke(int leftVal)
        {
            eval(right, new eval@11-1(cont, leftVal));
            return null;
        }
    }

    [CompilationArgumentCounts(new int[] { 1, 1 })]
    internal static void eval(Expr expr, FSharpFunc<int, Unit> cont)
    {
        while (expr is Expr.Add)
        {
            Expr.Add add = (Expr.Add)expr;
            Expr item = add.item2;
            Expr item2 = add.item1;
            cont = new eval@10(cont, item);
            expr = item2;
        }
        Expr.Number number = (Expr.Number)expr;
        cont.Invoke(number.item); // This actually returns a `Unit` value which is then `pop`ped.
    }
}

It seems like the unit-elimination logic would need to be applied to the generated closure methods as well to make this scenario work as expected (unless you omit the specification of unit as the return type as in cont: int -> _ or else defer it like this).

[brianrourkeboll]

this behaviour is counter-intuitive and [<TailCall>] should protect against it.

For what it's worth, the checking that is done for that attribute for code with this particular structure appears to be correct when the return type is literally anything but unit. This particular scenario could probably be special-cased during tail-recursiveness checking, although that feels like a disappointing outcome.

It would be nice if we could improve the unit-elimination logic such that this code would actually be tail-recursive instead, but see, e.g., here for discussion of some of the kinds of complexity and compatibility considerations that would be involved.