实现Scala类蹦床在Rust中实现尾叫优化

Question

在尾呼叫优化的主题上，我发现了两个RFCS：271和一八八八年。

在此之前，我想做一些受Scala Trampoline功能启发的事情。

实际的实现远非成熟的尾调用优化，因为它用迭代函数替换递归函数调用，但它用于保持堆栈深度低。我的实际工作情况如下：

enum Trampoline<A, R> {
    Continue(A, R),
    End(R),
}

impl<A, R> Trampoline<A, R> {
    fn start(function: &Fn(A, R) -> Trampoline<A, R>, mut arg: A, mut sum: R) -> R
    {
        loop {
            match function(arg, sum) {
                Trampoline::Continue(r_arg, r_sum) => {
                    arg = r_arg;
                    sum = r_sum;
                },
                Trampoline::End(result) => return result,
            }
        }
    }
}

fn recurse_trampolin(arg: i32, sum: i32) -> Trampoline<i32, i32> {
    if arg == 0 {
        Trampoline::End(sum)
    } else {
        Trampoline::Continue(arg - 1, sum + arg)
    }
}

fn recurse_normal(arg: i32, sum: i32) -> i32 {
    if arg == 0 {
        sum
    } else {
        recurse_normal(arg - 1, sum + arg)
    }
}

fn main() {
    println!("{}", recurse_normal(5, 0));
    println!("{}", Trampoline::start(&recurse_trampolin, 5, 0));
}

除了使用引用与非Copy类型兼容之外，该结构是否可以进一步优化或简化/美化代码？

Answer 1

1. 运行拉斯特夫特。它将自动修复诸如之类的东西。
   • 打开大括号与函数签名放在同一行(除非函数签名已经是多行)。
   • 在使用大括号的match臂的末尾没有逗号。

2. 函数名有一个错误：recurse_trampolin
3. 与其接受特征对象引用(&Fn(...) -> ...)，不如使用泛型。这样可以进行更好的优化，避免不必要的间接影响。

enum Trampoline<A, R> {
    Continue(A, R),
    End(R),
}

impl<A, R> Trampoline<A, R> {
    fn start<F>(function: F, mut arg: A, mut sum: R) -> R
    where
        F: Fn(A, R) -> Trampoline<A, R>,
    {
        loop {
            match function(arg, sum) {
                Trampoline::Continue(r_arg, r_sum) => {
                    arg = r_arg;
                    sum = r_sum;
                }
                Trampoline::End(result) => return result,
            }
        }
    }
}

fn recurse_trampoline(arg: i32, sum: i32) -> Trampoline<i32, i32> {
    if arg == 0 {
        Trampoline::End(sum)
    } else {
        Trampoline::Continue(arg - 1, sum + arg)
    }
}

fn recurse_normal(arg: i32, sum: i32) -> i32 {
    if arg == 0 {
        sum
    } else {
        recurse_normal(arg - 1, sum + arg)
    }
}

fn main() {
    println!("{}", recurse_normal(5, 0));
    println!("{}", Trampoline::start(recurse_trampoline, 5, 0));
}