Proposal: tail return recursive calls

[agocke]

Champion issue: #8991

There are a number of instances where it may be clearer to express your algorithm via recursion, especially tail recursion, but unfortunately all recursion in C# currently requires O(n) space for just the call stack, meaning that your algorithm cannot take less than O(n) space.

It is proposed that C# provide a new statement form and a new expression form to allow tail-recursive calls to consume O(1) space.

Syntax and Semantics

The statement form would be tail return <expr>, analogous to yield return, where the expr target is required and must be a tail recursive call.

The expression form would be tail <expr>, where the <expr> would have the same restrictions as the statement form, and the tail <expr> expression would only be legal as the expression in an expression-bodied member.

Codegen

There is a tail instruction in the CLR, but if that instruction is not reliable or desired, the compiler can lower this into a goto after assigning the new arguments for the recursive call.

For instance,

void M(int x)
{
    ...
    tail return M(x - 1);
}

Could be rewritten to

void M(int x)
{
    start:
    ...
    x = x - 1;
    goto start;
}

Limitations

Because the compiler cannot reliably rewrite inter-procedural calls, this would only currently be legal for tail-recursive calls. It would not be allowed for e.g., mutually tail recursive calls. If the CLR can reliably perform tail calls without significant downsides on all supported platforms, the feature could be broadened from the current specification.

[agocke]

cc @gafter

[YairHalberstadt]

Has any analysis been done to see how many locations in eg. Roslyn could benefit from this?

Is a new keyword necessary, or would an attribute be sufficient, as this doesn't change the semantics of the program?

[YairHalberstadt]

Would rewriting mutually recursive local functions be considered?

[CyrusNajmabadi]

So, presumably you can write;

if (x)
{
    tail return MyMethod(a, b, c);
}
else
{
    tail return MyMethod(d, e, f)
}

But would you be able to do:

tail return x ? MyMethod(a, b, c) : MyMethod(d, e, f);

?

[agocke]

@CyrusNajmabadi Not as written, no.

[agocke]

@YairHalberstadt Regardless of what we could do for local functions, the restrictions as listed would not allow mutual tail recursion.

As for attributes, the important part is really the call, not the definition, right? We can't put attributes on expressions, so if the call is really the part we want to annotate, attributes are not suitable.

[CyrusNajmabadi]

@agocke Understood. Probably not critical to support. but it would be nice if it was relaxed to teh generalized definition of tail-calls. Namely that they must be the last thing the function executes. In such a formalization, conditionals would be fine.

Just for my own edification, would this be challenging to support?

[agocke]

Probably not. The nice thing about tail calls is you don't really care about all the stuff nested inside the expression, you only need to know that 1) the outer expression is a call and 2) the call is recursive.

For conditional, that would just add an introspection "through" the conditional to both sides. From a language point of view it's a bit unfortunate to dig through expressions, but it's probably necessary for the broader semantics to work properly with conditional.

[CyrusNajmabadi]

For conditional, that would just add an introspection "through" the conditional to both sides. From a language point of view it's a bit unfortunate to dig through expressions, but it's probably necessary for the broader semantics to work properly with conditional.

Makes sense. Thanks for clarifying!

[HaloFour]

It seems a little weird trying to generate explicit tail call behavior in the C# language given that IL supports it and RyuJIT supports it as an optimization implicitly. I can understand the concerns with the reliability of those features and explicit language support would make it more predictable.

Given that tail recursion and functional programming seem to go hand-in-hand I'd want to ensure that a feature like this would cover those common bases, like being embedded in a switch expression. My (limited) experience with @tailrec in Scala is that it's often somewhat tricky/obnoxious to find the right order of operations to satisfy the compiler.

[CyrusNajmabadi]

One more question:

What if you do:

void M(int x)
{
    ...
    tail return other.M(x - 1);
}

Seems like this should be supported. This would just be equiv to slamming over the 'this' param with 'other' and then tailing, right?

Or will this only be allowed for static methods, or tail-methods with 'this' as the receiver? Thanks!

[CyrusNajmabadi]

It seems a little weird trying to generate explicit tail call behavior in the C# language

I actually don't have a problem with this. It's less about the compiler actually generating something appropraite, and it's more about actually ensuring you either get tail calls, or you fail to compile. For example, in my programming life i've made constant mistake around code i thought should be tail-called. It is so simple to do something accidental that makes tail calls stop working, and you can end up shooting yourself in the foot.

So, i see the presence of tail in the language much more of a check to say "you better not have screwed this up!".

It's similar to a static local function for me. Yes, i can just not capture anything. But static makes sure that if i mess that up in the future it just won't compile.

[HaloFour]

I know that C# does not yet have list patterns, but something like this would be critical to support:

public int Sum(int seed, List<int> list) => list switch {
    [ ] => seed,
    [value ... rest] => tail Sum(seed + value, rest),
};

Edit: Reordered the cases so that the tail call happens last. I believe Scala requires this. Would be nice if C# didn't have to.

[HaloFour]

@CyrusNajmabadi

It's less about the compiler actually generating something appropraite, and it's more about actually ensuring you either get tail calls, or you fail to compile.

This proposal seems to be about emitting the explicit goto IL to implement the tail call and skipping whatever IL/JIT support there is. I'd agree that I'd probably prefer a tail operator (or attribute+analyzer) to simply enforce what the runtime supports, but that's probably a difficult target to nail down. IIRC the runtime is free to ignore the tail. opcode prefix, and implicit support varies quite a bit.

[CyrusNajmabadi]

but something like this would be critical to support:

I would just like the proposal relaxed to "return points". Then, it should "just work" for conditional-exprs, switch-statements (though that likely doesn't need anything special), switch-exprs, expr-bodies, and anything else that has that concept.

[john-h-k]

what do you mean by "do the tail recursion itself" tho - the .tail prefix?

[gafter]

Compiler can also literally just do the tail recursion itself

Not without changing the signature of methods in the case of mutual recursion.

[CyrusNajmabadi]

what do you mean by "do the tail recursion itself" tho - the .tail prefix?

Actually performing the optimization in the method. i.e. not calling the recursive method, but instead just converting it to a goto directly. See the codegen part of the proposal in the OP.

[CyrusNajmabadi]

Not without changing the signature of methods in the case of mutual recursion.

i believe andy's proposal put that out of scope. but i could be mistaken. I thought this only covered self-recursion.

[samuel-vidal]

The design I would favor, would be to strengthen the contract with the runtime in a way that all CLR language could benefit from.
(sorry new here: would you suggest me to make a separate proposal or this discussion is a fine place).

[CyrusNajmabadi]

No worries. Given your interest, i do personally think a coreclr issue would be more relevant if this is about ensuring behavior around the .tail instruction.

[samuel-vidal]

Also, I should not have been that specific. I could change:

The proposed 'tail' syntax should mean exactly that : the compiler is asked to check that the call will be optimized by the Jit and emit the necessary IL.

to

The proposed 'tail' syntax should mean exactly that : the compiler is asked to check that 1) the call is tail and 2) guarantee that the call will be optimized (either by the Jit through emitting the necessary IL or otherwise).

[john-h-k]

@samuel-vidal

That contract already exists

[john-h-k]

Also, that is not the runtime @samuel-vidal , that is just the compiler. There are various different runtimes and JITs

The proposed 'tail' syntax should mean exactly that : the compiler is asked to check that 1) the call is tail and 2) guarantee that the call will be optimized (either by the Jit through emitting the necessary IL or otherwise).

Compiler cannot check JIT behaviour as i said before. It can ONLY:

• Emit the tail. prefix itself, which guarantees desired behaviour according to ECMA 335
• Emit the tail call itself, transforming it to a loop

[samuel-vidal]

@johnbeisner I think that is fair enough. Since the contract exists and is guaranteed to be honored by the runtime then point 2) is simply emitting tail. prefix.

I was under the impression that the tail call optimization is subject to a long list of Byzantine conditions in order to have the actual desired effect. So it would be valuable to have the compiler warn the user if any of those conditions are not met. I came accross that list for example (nb it is quite old and I have no idea how relevant it still is).

[samuel-vidal]

Also interaction with try/catch is another can of worms, a return tail call(param) within a try is not exactly a tail call, you can't erase all the stack state for the caller method. (so the conditions you noted above can't be met). That would have to be one of the case when the compiler says no : 'Tail constraints within a try block are not allowed'.

[Thaina]

Totally +1

I would also wish that the compiler will just error when we put tail into any line that not possible to be tail called

Also, could it be that we would just have tail as a standalone keyword. And support for tail block?

void M(int i)
{
    if(i <= 0)
        return i;

    tail { // tail call all this block
        int tmp = M(i - 1);
        DoSomething(ref tmp);
        return tmp;
    }
}

[hez2010]

IIRC tail recursive call optimization is guaranteed by JIT: https://sharplab.io/#v2:EYLgxg9gTgpgtADwGwBYA0AXEBDAzgWwB8BLAOwwAIBZACjMoQEoBYAKAG82LuLiAzCjQQUAvCIoBGRhQACAdkkBuLj3nUhFOJMbLWAXyA==

[timcassell]

@hez2010 Maybe in simple cases like that, but what about with virtual and non-self recursion?

void Func()
{
    // ...
    FuncVirt();
}

protected virtual void FuncVirt()
{
    // ...
    Func2();
}

void Func2()
{
    // ...
    if (x)
    {
        Func();
    }
}

[bjoli]

I don't really know where this went. It seems like nowhere?

I recently had the experience of writing a recursive descent parser in a language with TCO. It was quite frankly a really nice experience, being able to keep track of state implicitly instead of doing it yourself. The language I used also had a growable stack, which made it possible to do non-tail recursion until memory ran out, which cleaned things up even more, but even rewriting the code relying on that would result in a very clear and deliberate code.

While I understand that tail call recursion is not the happy path in c#, having the tool would be great for some specific cases. It could be limited to self or sibling recursion if a general version leads to issues (like in llvm and rust).

Having a way to wish for it explicitly helps for things like debug builds where it might be turned off because it might not be desired everywhere, and will also make it an error to try to rely on it where it cannot be done.

There are loads of kinks to work out, but how about first allowing it in the simplest cases and then figuring out the rest?