`tailrec` to enforce tail recursion

[WhiteBlackGoose]

If tail recursion is impossible, give an error.

Stolen from Kotlin.

[LPeter1997]

Agree, things like this are useful. One thing I'd like is to push these to metadata/attribute level and not have them occupy a keyword.

[aloisdg]

F# has a rec keyword. Why not re-use it?

[LPeter1997]

@aloisdg The rec keyword in F# is essentially heritage from the ML family and denotes that a binding is recursive (can reference itself, like a recursive function). I'm not a fan of the feature, but that's a topic for another discussion. This feature is about telling the compiler that TCO can - and should - be applied to a function to avoid an expensive recursive call and an exploding call stack. This is why I'm not a fan of making it a keyword, as it's not modifying behavior/semantics and more like communication with the compiler that C# already does with attributes.

[WhiteBlackGoose]

Yep, and F# doesn't have this feature :(

[jl0pd]

Making it an attribute will require allowing attributes on local functions, because tailrecs are rarely used as top level function, mostly they're inner functions. Take F# list module as an example (search for "loop"). Attributes on local functions will look too heavyweight

[LPeter1997]

How so? Allowing attributes everywhere seem simply reasonable.

func fact(n: int32): int32 {
    #[TailRecursive]
    func f(acc: int32, n: int32): int32 =
        if (n == 0) acc
        else f(n * acc, n - 1);
    return f(1, n);
}

Seems quite elegant IMO.

[333fred]

One thing to make sure of: iirc the CLR does not guarantee that it can always tailrec, even with the .tail directive. This lack of guarantee is one reason why C# does not have it.

[WhiteBlackGoose]

F# does it on IL level, and that's how I want to have it too.

[333fred]

F# does it on IL level, and that's how I want to have it too.

And because the clr doesn't guarantee .tail is always respected, it can sometimes fail.

[WhiteBlackGoose]

My point is that we don't need to emit IL's tail call at all. We can turn our recursion into a loop, basically, and only then compile it to IL

[333fred]

My point is that we don't need to emit IL's tail call at all. We can turn our recursion into a loop, basically, and only then compile it to IL

You can, but that (as far as I know) isn't how F# does it. It uses .tail.

[WhiteBlackGoose]

It emits tail very rarely. Simple example for turning a rec into loop

That's exactly why unlike C#, it can almost guarantee TCO for tailrec.

[jl0pd]

How so? Allowing attributes everywhere seem simply reasonable.

func fact(n: int32): int32 {
    #[TailRecursive]
    func f(acc: int32, n: int32): int32 =
        if (n == 0) acc
        else f(n * acc, n - 1);
    return f(1, n);
}

Seems quite elegant IMO.

Less elegant than F# version

let fact n =
    let rec loop acc x =
        if x = 0 
        then acc
        else loop (acc * x) (x - 1)
    loop 1 n

Making it an attribute will take same space, as required for entire function definition:

#[TailRecursive]
let loop acc x =