Hoot 是 Spritely Institute 推出的一个雄心勃勃的项目，旨在将 Guile Scheme 代码编译为可在现代浏览器中运行的 WebAssembly（Wasm）二进制文件。它不仅是简单的源代码转换，更是一个完整的编译工具链，试图在保持 Scheme 动态特性的同时，充分利用 Wasm 的性能优势。尾调用优化（Tail Call Optimization, TCO）是函数式编程语言的核心特性之一，Hoot 如何在这一领域进行工程化实践，是一个极具技术价值的课题。
背景：尾调用优化的两面性
在传统的编译原理中，尾调用优化通常是一个 “可选项” 或 “难题”。对于 C/C++ 等语言，编译器需要主动分析代码以识别尾调用位置，并消除栈帧累积。然而，对于 Scheme 这类要求 “正确尾调用”（Proper Tail Calls）的语言而言，尾调用不是优化，而是语言规范的一部分，编译器必须保证其行为。
WebAssembly 在设计之初就考虑到了这一需求。其尾调用提案（Tail Call Proposal）原生引入了return_call和return_call_indirect指令，使得引擎能够通过重置帧指针和栈指针，直接将控制权移交给被调用函数，而无需保留调用者的栈帧。这对于实现递归和迭代的栈空间一致性至关重要。
然而，对于 Hoot 编译器来说，情况变得有些反常识。V8 引擎的博客文章指出，WebAssembly 的原生支持意味着 “优化” 是工具链的责任。但 Hoot 面临的最大挑战并不是实现尾调用本身，而是如何实现那些非尾调用（Push Calls）。因为在 Scheme 中，非尾调用必须保存当前的执行状态（即延续），以便在函数返回后继续执行。
Hoot 的解题思路：晚期 CPS 转换
Hoot 采用了一种独特的策略：晚期持续传递风格（Late-stage CPS）转换。
Hoot 的核心维护者 Andy Wingo 在其技术博客中详细阐述了这一过程。Hoot 并没有从一开始就将 Scheme 代码转换为 CPS 形式，因为那样会过早地破坏优化空间。相反，它保留了 Guile 编译器的中间表示（IR），通常称为 CPS Soup，这是一种直接风格（Direct-style）的图表示。
在优化的后期阶段，Hoot 开始对 CPS Soup 进行转换。这个过程可以概括为三个主要步骤：
- 函数分割（Splitting）：每当遇到一个非尾调用（Push Call），当前函数就会被 “分割” 成多个部分，称为 “Tails”。例如，一个函数
f调用非尾函数g，然后执行h，那么f就会被分割为调用g之前的部分（Tail 1）和调用g之后的部分（Tail 2）。 - 显式栈管理：在分割点，Hoot 引入了一系列原语（Primitives）
save!、restore!和pop!。在调用非尾函数之前，当前的执行状态（延续）和所有活跃变量会被显式地保存到栈上。 - 全尾调用程序：转换完成后，程序中的所有调用指令都变成了尾调用。这意味着递归不再是栈增长的累加器，而是变成了空间复杂度为 O (1) 的循环。
这种转换产生了一个全尾调用的程序，所有复杂的栈管理都通过显式的save!和restore!原语完成，从而绕过了 WebAssembly 缺少通用栈切片原语的限制。
映射到 WebAssembly：三栈机制的工程权衡
WebAssembly 的类型系统与 Scheme 的动态类型存在根本性的冲突。Guile 原生使用统一的SCM类型表示所有值，但在 Wasm 中，没有一种单一的存储位置可以同时容纳 64 位整数和对象引用。
为了解决这个问题，Hoot 引入了三栈机制（Three-Stack Approach）：
- 数值栈（Numeric Stack）：用于存储原始数值（
u64,f64等），在 Wasm 内存中线性分配。 - 引用栈（Reference Stack）：用于存储
eq引用类型的对象，存储在 Wasm 的Table中。 - 延续栈（Continuation Stack）：由于函数类型（
func）的层次结构与eq不相交，延续闭包无法直接存入引用栈，因此需要一个单独的栈来存储和管理函数引用。
Hoot 的博客承认，这看起来 “很恶心”（It's gross）。这种架构设计增加了编译器后端的复杂性，需要精确地追踪每个变量应该被推入哪个栈，并在恢复时按正确的顺序弹出。然而，这种显式的栈管理是实现 Hoot 目标的关键：它不仅支持尾调用，还支持如call-with-prompt等高级控制流构造，甚至为未来的栈切片（Stack Switching）提案奠定了基础。
性能与功能的天平
Hoot 的这种方法并非没有代价。Wingo 在文章中坦言，CPS 转换引入的开销在某些情况下可能高达 10 倍。例如，在函数边界频繁地保存和恢复状态会增加内存带宽的压力。
然而，Hoot 的设计哲学是优先保证功能正确性。通过这种方式，Hoot 实现了：
- 与 JavaScript Promise 的无缝集成：Hoot 可以利用 WebAssembly 的调用约定，将 Scheme 的延续传递给 JavaScript 的 Promise 处理器，从而在不依赖 JSPI（JavaScript Promise Integration）或 Asyncify 的情况下实现异步操作。
- 完整的 Scheme 语义：包括 call/cc（虽有限制）、异常处理和 Fibers（Guile 的轻量级线程）。
结语
Hoot Scheme 编译器对尾调用优化的实现，是函数式编程语言与现代 WebAssembly 运行时交互的一个典范案例。它巧妙地利用了 WebAssembly 原生支持的尾调用指令，通过晚期的 CPS 转换和显式的三栈管理，跨越了动态类型与静态类型、隐式栈与显式栈之间的鸿沟。尽管在性能上可能有所牺牲，但它成功地在浏览器这一全新环境中，重新构建了 Scheme 语言的执行模型，为其他函数式语言的 Wasm 移植提供了宝贵的参考。
资料来源：
- Hoot: Scheme on WebAssembly - Spritely Institute
- cps in hoot - wingolog
- WebAssembly tail calls - V8 JavaScript Engine