面向 V 的 Lisp,尾调用真正不花钱

建立在显式 CEK 机器上的小型 Lisp 方言。处于尾位置的调用会复用其栈帧而不是压入新的,因此循环就是循环,而不是一个不断增长直到崩溃的栈。

阅读文档 源代码

本节尚未翻译成你的语言,暂时以英文显示。欢迎提交翻译。

A taste

(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1))
         (fib (- n 2)))))

(fib 20)          ;=> 6765

本节尚未翻译成你的语言,暂时以英文显示。欢迎提交翻译。

这是什么

Real tail calls

A quarter of a million iterations end with an empty continuation stack. Mutual recursion tail-calls too, which is the part most trampolines skip.

An explicit machine

Evaluation is a data structure you can inspect, not a recursive function you have to trust. Every step is counted, and every limit is a field you can set.

Embeddable by shape

The machine is a library with no global state. print output is collected into a field, so a host can capture it rather than fight it.

本节尚未翻译成你的语言,暂时以英文显示。欢迎提交翻译。

Where it stands

Working: the reader, closures, arithmetic, branching, loop, dotimes, letrec, cond, case, and proper tail calls including mutual recursion.

Not yet: let*, rest parameters, callable keywords, modules, and macros. Each one is named in the repository rather than quietly missing.