PLT

光剑后日谈 #2. 在 Scheme/Racket 的世界里，我们常说“一切代码皆为 S-expression”。一个函数调用是 (函数名 参数1 参数2)，一个列表是 (元素1 元素2 元素3)，它们都遵循着括号包裹、前缀表示的统一形式。 但细心的你可能会问，'(a b c) 或者 #'(+ 1 stx) 呢？开头的那个 ' 或 #' 字符，怎么看也不像是列表的一部分。它们是如何融入这套 S-expression 体系的？ 答案很简单：它们是一种语法糖。我们都知道 'exp 等价于 (quote exp)，#'exp 等价于 (syntax exp)。这个单引号 ' 仿佛是一个别名，在 Racket 读取我们的代码时，就悄无声息地将它转换成了标准的形式。这种在“读取阶段”就生效的转换规则，被称为读取器宏（Reader Macro）。 读取器宏背后，是整个 Lisp 家族语言引以为傲的宏系统。宏是一种强大的元编程工具，它本质上是一个在编译期（或称为“展开时”）执行的函数。这个特殊的函数，它的输入是代码（以语法对象的形式），输出也是代码。它允许我们对代码进行任意复杂的、图灵完备的变换，从而彻底扩展语言本身的语法。 那么，亲手编写一个宏，究竟是怎样的体验呢？ 宏之初体验：编写你的第一个宏 when 让我们从一个简单的需求开始。在编程中，我们经常遇到一个场景：“当某个条件成立时，执行一系列操作”。用 Racket 的 if 可以这样写： 1 2 3 4 5 (if (< user-level 5) (begin (display "权限不足！") (log-warning "Attempted access by low-level user.")) #f) 每次都写 (begin ...) 有点繁琐（更何况 Racket 强制 if 有两个分支，那个不需要的分支混淆了语义）。如果我们能创造一个新语法 when，让代码变成下面这样，岂不是更清晰？ ...

光剑的后日谈 #1. 在文艺复兴之后，FP 也要大胜利！ 在这篇文章的讨论区中，我进行了引流。为了报答作者，我写了这篇文章。 上面那篇文章中使用了一种伪代码语法来表示 lambda calculus。不过这种语法并不能直接运行。怎么办呢？让我们来构建一个源到源编译器！ 要写一种语言的编译器，显然我们需要知道它的语法和词法。这是第一步。另外还有语义，但是它是 lambda 的一种表示法，所以语义已经被 lambda 定义了，无需考虑。 首先是词法。这种语言会出现哪些 tokens？ 分类一下。lambda 的核心是函数抽象和函数应用。函数抽象用到哪些 tokens？ func 关键字。 冒号。 return 关键字。 参数列表和括号。 函数应用？ 括号 另外还有一个扩展语法，绑定创建。 等号（赋值运算符） 然后我们需要定义它的语法。这篇文章使用的是单参数的原始 lambda，方便了我们的实现。 1 2 3 4 5 6 identifier ::= symbol abstract-exp ::= func : (identifier) { return val-exp } apply-exp ::= val-exp(val-exp) bind-exp ::= identifier = val-exp val-exp ::= identifier | abstract-exp | apply-exp lc-exp ::= val-exp | bind-exp 看来挺简单的。 ...

光剑系列的第六作！ （放一个 Gemini 生成的欧比旺的图来解释一下光剑是什么） 前五作： 第一篇：Let’s build our mathematics by using lambda calculus && church encoding! 第二篇：惰性求值、无穷流与发生的魔法 第三篇：协程、生成器与 call/cc 的控制流 第四篇：动态作用域、词法作用域与表达式求值的环境模型 第五篇：基于环境模型的解释器 我们上篇文章写了解释器。在评论区里面可以看到一个非常神秘的东西：https://www.zhihu.com/question/30262900/answer/1943149381147660845 1 2 3 4 5 6 7 8 9 10 11 12 ; 嵌套的括号不是 scheme 标准语法。表示定义柯里化的函数，和嵌套 lambda 等价。racket 支持这一扩展语法。 (define (Z env) (car env)) (define ((S vp) env) (vp (cdr env))) (define ((Lam e) env) (lambda (x) (e (cons x env)))) (define ((App e1 e2) env) ((e1 env) (e2 env))) ; (define global-env '()) 顺便，还有人问我为什么不再布置一道习题，那么这就是习题！ ...

光剑系列的第五作！前四篇： 第一篇：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”就是一个外部传入的续延。它代表“当前函数执行完毕后，还要进行哪些操作”。 现在让我们来看看代码。条件判断很寻常。 ...