从 λ 到 Ret：一次把 Lambda 演算和尾递归优化塞进生产代码的实录

背景undefined组里要给风控规则引擎加一门“小脚本”，语法得像 Lisp，执行得跟 C 一样快。既要支持高阶函数，又得保证递归写起来不爆栈。于是我们把 Lambda 演算当核心语义，把尾递归优化（TCO）当保命符。上线 3 个月，CPU-usage 降 28 %，StackOverflow 工单清零。下面把过程拆开说，所有数字来自生产火焰图和 perf script，表是我手打的，放心抄。

1. Lambda 演算：理论 3 行，落地 3000 行

最初的想法很美好：

• 变量、抽象、应用三条规则，足够 Turing-complete；
• 语法直接贴 S-expr：((lambda (x) (+ x 1)) 5)。

但一到 AST → 字节码就翻车：

结果就是：核心 80 行 λ 语义，外围补丁 3000 行 C++。

教训：“在工业界，Lambda 演算只占 3 % 代码，剩下 97 % 都是为了让机器不崩溃。”

2. 尾递归优化：理论一句话，实现三步走

Lambda 允许随意递归，但 JVM/本地栈可不买账。我们按“检测—转换—回退”三板斧落地 TCO：

2.1 检测

在 AST → 字节码阶段做一次 CFG 扫描：

• 当前函数最后一个表达式是“自身调用” → 标记 TAILCALL；
• 中间若插入 finally / on-error，直接打回普通递归。

2.2 转换

字节码里把 CALLSELF n 改成 TAILCALL n，解释器循环伪码：

loop:
    op = *pc++;
    switch(op){
        ...
        case TAILCALL:
            // 复用当前栈帧
            memcpy(frame->locals, new_args, n * 8);
            pc = func_entry;
            goto loop;
    }

2.3 回退

真遇到 FFI 调用或调试器 attach，就退回到原生栈，防止断点失效。上线后只触发 0.02 % 的回退，肉眼无感。

3. 性能对比：TCO 到底值不值？

我们用同一段“计算 1e8 以内偶数和”做基准：

(define (sum-even n acc)
  (if (< n 0)
      acc
      (sum-even (- n 2) (+ acc n))))

TCO 只比手写循环慢 12 %，但脚本可读性高到爆。老板说：“这 12 % 就当送开发效率了”。

4. 线上事故：一次 “letrec” 导致 TCO 失效的血案

上线第二周，脚本里写了：

(letrec ((f (lambda (x) (if (zero? x) 0 (+ 1 (f (- x 1)))))))
  (f 1e6))

结果还是把栈打穿了。排查发现：

• letrec 展开后多出一条 SET! 指令，不再处于尾位置，TCO 检测失败。
• 修复：把 letrec 的初始化语句提前到函数头，让递归调用回归最后一个表达式。

5. 踩坑小结（现场手抄版）

6. 一句话总结

Lambda 演算让我们 1 天写完解释器，尾递归优化让我们 1 周把它搬上生产；剩下的 3 个月，都在修“理论与现实只差一层抽象”的 bug。