光剑系列的第五作！前四篇： 第一篇：Let’s build our mathematics by using lambda calculus && church encoding! 第二篇：惰性求值、无穷流与发生的魔法 第三篇：协程、生成器与 call/cc 的控制流 第四篇：动态作用域、词法作用域与表达式求值的环境模型 前言 又见面了！上一篇文章中我将动态作用域的实现留作了习题，一定非常恶心吧！毕竟我尝试了两天枚举了各种不用宏和用宏的解决方案都没有任何成果，只能看着看不懂的编译错误或者不期望的展开结果发呆。 如果有哪位读者做出了那个习题，请务必通过本文评论区联系我。 不过，其实只要自己实现一个解释器，就能够轻松而优雅地完成这个习题。 恰好，上一篇文章中介绍了环境模型，这将是我们解释器的原理。 我们将选择 scheme 实现解释器。因为 scheme 的解释器特别好写而作者太菜了只会这个。 实现 在实现一个具有比较多特性的 scheme 子集之前，我们将先实现一个更简单的 lambda 演算解释器。 看过第一作的读者们想必还记得 lambda 演算吧？它只含有函数一种对象，函数抽象和函数应用两种操作，已经是图灵完备的。 那么我们来实现它，使用环境模型和闭包。 预备工作 · 函数 lambda 只有函数一种核心对象。实现函数自然成为了我们的重要任务。 在环境模型下，想要实现词法作用域肯定要用闭包。所以我们的函数也将被表示为一个闭包。 它含有四个字段：第一个是符号 closure，用于标识身份。后面三个字段分别是形式参数、函数体和保存的环境。这些是闭包的核心要素。 我们可以先实现单参数的函数。因为具有一等公民函数的特性，我们可以通过柯里化实现多参数函数。 对于闭包的存储，随便用什么都行。我用的是一个 vector（定长数组）。 1 2 (define (make-closure params body env) (vector 'closure params body env)) 有了函数的数据结构标识，我们还需要有对于闭包的操作： 1 2 3 4 5 6 (define (closure? obj) (and (vector? obj) (eq? (vector-ref obj 0) 'closure))) (define (closure-param closure) (vector-ref closure 1)) (define (closure-body closure) (vector-ref closure 2)) (define (closure-env closure) (vector-ref closure 3)) 然后，为了支持对于函数的应用和抽象，我们需要一些关于环境的操作。 ...

光剑系列的第四作！前三篇： 第一篇：Let’s build our mathematics by using lambda calculus && church encoding! 第二篇：惰性求值、无穷流与发生的魔法 第三篇：协程、生成器与 call/cc 的控制流 引子 在惰性求值、无穷流与发生的魔法中，我们使用无参 lambda 构建了一个 thunk。 想必有读者读完之后苦思冥想，最后发现“不对呀！主播，你为什么要用一个 lambda 呢？这里用 quote 不是也可以起到‘冻结计算’的作用？最后用一次 eval 将被冻结的原始表达式求值就可以得到真实值了。” 比如说，我们使用过的这个示例： 1 2 3 > (define x (lambda () (+ 1 2))) > (x) 3 就可以转化为下面的形式： 1 2 3 > (define x '(+ 1 2)) > (eval x) 3 如果你这么想了，恭喜你！你自己发现了一条通向本文核心内容，函数抽象的动态作用域与词法作用域区别的道路。 接下来，请容我解释动态作用域、词法作用域，它们的区别以及 thunk 两种构建方法与它们的联系。在本文中，我们还将手动在 scheme 中构建一套动态作用域的函数抽象/应用体系。最终成果如下： 1 2 3 4 5 6 7 8 ;; 假设使用支持 SRFI-39 的实现（chez 等很多支持） (define x (make-parameter 10)) (define (f y) (+ (x) y)) (f 5) ; => 15 (parameterize ([x 100]) (f 5)) ; => 105 ; x 按调用链动态解析 分道扬镳——当自由变量出现 上面的两种方法看似都能实现对计算的“冻结”，但是它们的作用真的完全一样吗？ ...

上期回顾 光剑系列的第三作！前两篇： 第一篇：Let’s build our mathematics by using lambda calculus && church encoding! 第二篇：惰性求值、无穷流与发生的魔法 前言与一个震撼的 demo 在上一篇文章中，我们探讨并实现了惰性求值与无穷流。希望你们还对自然数流印象深刻。 自然数流也可以视为一个不断生成新的自然数的生成器。那么，从这个意义上，我们有更简洁而强大的实现方式。 （还是一贯的 scheme 代码） 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 (define (nature-gen return) (let loop ((i 0)) (set! return (call/cc (lambda (state) (return (cons state i))))) (loop (+ i 1)))) (define nature-numbers (let ((k nature-gen)) (define (tmp-interface) (let ((result (call/cc k))) (set! k (car result)) (cdr result))) tmp-interface)) 这就是一个自然数的生成器！每次调用 nature-numbers，它都会返回一个新的自然数。 ...

光剑第二作！ 前言：什么是魔法？ （注：这个前言可以跳过。它是最终成果展示。感到迷惑很正常，请先阅读正文。） 什么是魔法？ 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 (define-syntax delay (syntax-rules () ((delay x) (lambda () x)))) (define (lazy-variable thunk) (cons #f thunk)) (define (is-calculated? variable) (car variable)) (define (force variable) (if (is-calculated? variable) (cdr variable) (begin (set-car! variable #t) (set-cdr! variable ((cdr variable))) (cdr variable)))) (define-syntax stream-cons (syntax-rules () ((stream-cons a b) (cons a (lazy-variable (delay b)))))) (define (stream-car x) (car x)) (define (stream-cdr x) (force (cdr x))) (define (int-from n) (stream-cons n (int-from (+ n 1)))) (define nature-numbers (int-from 1)) 真成四十行代码了。感兴趣的读者可以数一数，刚好 39 行。 ...

致谢 Gemini 2.5 Pro 0325 && 0506：文本润色、事实正确性审查，以及帮助我学习、理解和回忆这些内容。 myster1ous： 给予我巨大的启发，帮助我构建出 prev 函数。 前言 本文是光剑系列的第一作，又名《lambda 演算，邱奇编码与优雅的计算模型》。 本文的目的是带领大家踏上一段奇妙的旅程：我们将使用 λ 演算（Lambda Calculus）这一极简的计算模型，并通过丘奇编码（Church Encoding）这一巧妙的技术，一步步构建出我们日常编程中熟悉和依赖的计算体系，例如数字、布尔逻辑乃至更复杂的数据结构。 为了方便演示和实践，本文中的所有代码示例都将使用 Scheme 语言。Scheme 是 Lisp 家族的一员，它的语法是 S-表达式 (Symbolic Expressions)。S-表达式不仅简洁优雅，而且其结构与 λ 演算的表达方式惊人地契合。 在我们开始之前，让我们先快速了解一下 S-表达式： 核心是列表 (List)： S-表达式的基本形式是由圆括号 () 包围起来的列表。 结构：(操作符 参数1 参数2 ...)： 列表中的第一个元素通常是操作符（即要应用的函数），其余元素则是传递给该操作符的参数。 原子 (Atom) 与嵌套： 列表中的元素可以是原子（如数字 123、符号 x、+），也可以是另一个 S-表达式。这种嵌套能力使得 S-表达式可以表示复杂的树状结构。 例如，表达式 (+ 1 (* 2 3)) 在 Scheme 中表示数学上的 1 + (2 * 3)。 这里： 最外层的 (+ 1 (* 2 3)) 是一个 S-表达式。+ 是操作符，1 和 (* 2 3) 是它的参数。 (* 2 3) 本身也是一个 S-表达式。* 是操作符，2 和 3 是它的参数。执行它会得到 6。 所以整个表达式 (+ 1 6) 最终会计算得到 7。 理解了 S-表达式，我们就可以更顺畅地进入 λ 演算的世界了。 ...

光剑系列的第七作！ 前六作： 第一篇：Let’s build our mathematics by using lambda calculus && church encoding! 第二篇：惰性求值、无穷流与发生的魔法 第三篇：协程、生成器与 call/cc 的控制流 第四篇：动态作用域、词法作用域与表达式求值的环境模型 第五篇：基于环境模型的解释器 第六篇：调用栈、de bruijn 索引与堆栈的内存模型 朱约（juyo）/瓦帕德（vaapad）是光剑七式的最后一技。很高兴我们的“光剑”终于抵达了这里！不过也许会有续集。 [此处应有温杜的图片] 一点说明 我更新了工具，本文使用 racket（scheme 的一种实现和变体）完成。这些代码大多可以直接挪用在 scheme 中，但是 match 除外，请使用自己的模式匹配库。我也转载了一个简单的模式匹配库：https://www.luogu.com.cn/article/4kw6oewn 注意使用 #lang racket。 发现有不少 racket 的在线环境，懒得下 racket 的话可以直接用。给一个：https://onecompiler.com/racket 引子 在前作中，我们提到过“call/cc”也即“call-with-current-continuation”的存在。它可以捕获当前的“续延”（coutinuation）并将它作为一个一等公民值。 续延代表程序的“计算上下文”，也即“我们接下来要做什么？”调用一个续延，可以让我们瞬间跳回续延被捕获的那个时间点，还原环境（包括堆和栈，不过那是具体的内存模型。环境是更抽象的“数据上下文”。）以及更重要的，“计算”。 看上去真是神秘又强大（事实上，从 call/cc 和条件判断，我们可以造出其余的所有控制流。）。我们的第五作实现了一个 scheme 子集的解释器，但是也没有实现这个功能。 那么，这个操作是如何实现的呢？“剩下的计算”是如何被表示的呢？这就是我们今天要探讨的话题。 CPS 变换 一个例子 先看下面这段代码： 1 2 3 4 5 6 (define (fact-cps n k) (if (= n 0) (k 1) (fact-cps (- n 1) (lambda (v) (k (* v n)))))) 从名字就可以看出，这是一个计算阶乘的函数。不过它看上去非常的不同寻常。 那个叫做“k”的参数是什么东西？它在干什么？ 事实上，这个“k”就是一个外部传入的续延。它代表“当前函数执行完毕后，还要进行哪些操作”。 现在让我们来看看代码。条件判断很寻常。 ...