Tail Call Optimization for Lambdas to Enable Full Functional Programming in C#

[nczsl]

Proposal:
Introduce tail call optimization (TCO) specifically for lambda expressions in C#. Global tail call support is challenging, so restricting it to lambdas makes it technically feasible while unlocking full functional programming potential.

Rationale:

Recursive lambdas can execute safely without stack overflow.

C# can achieve nearly complete functional programming support using only lambda composition.

Functional patterns are naturally parallel-friendly, improving C#’s expressiveness in modern parallel and async programming.

Limiting TCO to lambdas mitigates runtime concerns while providing a powerful FP foundation.

Example:

Func<int, int> factorial = null!;
factorial = n => n <= 1 ? 1 : n * factorial(n - 1);
int result = factorial(100_000); // Works safely with TCO for lambdas

Benefits:

Enables deep recursion in lambda-based FP workflows.

Encourages composable, immutable code.

Strengthens C#’s suitability for parallel and asynchronous computation.

[333fred]

Duplicate of #8991.

[nczsl]

// 函数指针（unsafe delegate*）版：使用真正的函数指针替代委托，保持纯 FP 组合
// 注意：函数指针需要 unsafe 上下文，且不支持泛型类型参数（T 必须具体化）
// 这里以 int 为例演示；泛型版本需为每个 T 单独实现

using System;
using System.Linq;
using System.Collections.Generic;
using System.Threading.Tasks;

#nullable enable

unsafe static class FpPtrUnsafe
{
    // 函数指针类型定义（比较、Min/Max、二元操作等）
    // 注意：函数指针不能作为类字段，只能作为 readonly 静态字段直接赋值

    // 静态方法实现（作为函数指针目标，使用 switch 表达式）
    static int CmpImpl(int a, int b) => a.CompareTo(b);
    static int MinImpl(delegate*<int, int, int> cmp, int a, int b) => cmp(a, b) switch
    {
        <= 0 => a,
        _ => b
    };
    static int MaxImpl(delegate*<int, int, int> cmp, int a, int b) => cmp(a, b) switch
    {
        >= 0 => a,
        _ => b
    };
    static int[] ReplaceAtImpl(int[] arr, int i, int v) => arr.Select((x, k) => k == i ? v : x).ToArray();
    static int[] SwapAdjIfImpl(delegate*<int, int, int> cmp, int[] arr, int i) =>
        (i + 1 >= arr.Length) switch
        {
            true => arr,
            _ => cmp(arr[i], arr[i + 1]) switch
            {
                > 0 => arr.Select((v, k) => k == i ? arr[i + 1] : (k == i + 1 ? arr[i] : v)).ToArray(),
                _ => arr
            }
        };
    static int[] BubblePassImpl(delegate*<int, int, int> cmp, int[] arr, int end) =>
        Enumerable.Range(0, Math.Max(0, end)).Aggregate(arr, (acc, idx) => SwapAdjIfImpl(cmp, acc, idx));
    static int[] BubbleSortImpl(IEnumerable<int> src, delegate*<int, int, int> cmp) =>
        Enumerable.Range(0, Math.Max(0, (((src as ICollection<int>)?.Count) ?? src.Count()) - 1))
            .Aggregate(src.ToArray(), (acc, pass) => BubblePassImpl(cmp, acc, acc.Length - 1 - pass));
    static int[] EvenPhaseImpl(delegate*<int, int, int> cmp, int[] arr) =>
        arr.Select((v, i) => i switch
        {
            _ when (i % 2 == 0 && i + 1 < arr.Length && cmp(arr[i], arr[i + 1]) > 0) => arr[i + 1],
            _ when (i % 2 == 1 && i - 1 >= 0 && cmp(arr[i - 1], arr[i]) > 0) => arr[i - 1],
            _ => v
        }).ToArray();
    static int[] OddPhaseImpl(delegate*<int, int, int> cmp, int[] arr) =>
        arr.Select((v, i) => i switch
        {
            _ when (i % 2 == 1 && i + 1 < arr.Length && cmp(arr[i], arr[i + 1]) > 0) => arr[i + 1],
            _ when (i % 2 == 0 && i + 1 < arr.Length && cmp(arr[i], arr[i + 1]) > 0) => arr[i + 1],
            _ when (i % 2 == 0 && i - 1 >= 0 && cmp(arr[i - 1], arr[i]) > 0) => arr[i - 1],
            _ => v
        }).ToArray();
    static int[] OddEvenSortParallelImpl(IEnumerable<int> src, delegate*<int, int, int> cmp) =>
        Enumerable.Range(0, (((src as ICollection<int>)?.Count) ?? src.Count()))
            .Aggregate(src.ToArray(), (acc, _) => OddPhaseImpl(cmp, EvenPhaseImpl(cmp, acc)));

    // 公开的函数指针实例（readonly，直接赋值）
    public static readonly delegate*<int, int, int> Cmp = &CmpImpl;
    public static readonly delegate*<delegate*<int, int, int>, int, int, int> Min = &MinImpl;
    public static readonly delegate*<delegate*<int, int, int>, int, int, int> Max = &MaxImpl;
    public static readonly delegate*<int[], int, int, int[]> ReplaceAt = &ReplaceAtImpl;
    public static readonly delegate*<delegate*<int, int, int>, int[], int, int[]> SwapAdjIf = &SwapAdjIfImpl;
    public static readonly delegate*<delegate*<int, int, int>, int[], int, int[]> BubblePass = &BubblePassImpl;
    public static readonly delegate*<IEnumerable<int>, delegate*<int, int, int>, int[]> BubbleSort = &BubbleSortImpl;
    public static readonly delegate*<delegate*<int, int, int>, int[], int[]> EvenPhase = &EvenPhaseImpl;
    public static readonly delegate*<delegate*<int, int, int>, int[], int[]> OddPhase = &OddPhaseImpl;
    public static readonly delegate*<IEnumerable<int>, delegate*<int, int, int>, int[]> OddEvenSortParallel = &OddEvenSortParallelImpl;
}

With the introduction of switch expressions and function delegates, C# now provides strong support for functional programming patterns. The example above demonstrates that, through pure lambda expressions, we can already express powerful FP constructs in a concise and declarative way.

Therefore, enabling tail recursion optimization (TCO) specifically for lambda expressions would be a natural and highly valuable next step.

I suggest limiting TCO to lambda expressions, which, based on my understanding, might reduce the implementation complexity and difficulty of this proposal. I cannot state this with certainty, but it seems plausible given the existing compiler infrastructure and the structural simplicity of lambdas compared to full method bodies.

This proposal is entirely built on top of C#'s existing lambda system — it would enhance the language’s FP capabilities without introducing new syntax or breaking existing semantics.

[timcassell]

If you just want an optimization without language changes, that goes to https://github.com/dotnet/roslyn.