Lisp/Scheme/Racket

亲手实现一个正则引擎！ 众所周知，一类经典的自动机是有限状态自动机。它们识别的语言是正则语言，而正则表达式能够匹配的字符串的集合也是正则语言。 （如果你之前没有了解过，询问 AI 或是使用搜索引擎都很适合快速了解） 导数法 要匹配一个正则表达式，最经典的方法就是构造对应的 NFA，然后通过一些手法转化为 DFA。但这太复杂了。有没有更简单的方法呢？ 有一种被称为“导数法”的方法。 思想非常简单：我们将构造出的 DFA 编码为一个正则。这样，转移之后相当于产生了一个新的自动机，也就是一个新的正则表达式。 原始正则表达式是 $r$。那么，$r$“吃掉”一个字符 $c$ 之后产生的表达式 $r'$，能匹配的所有字符串就是所有满足 (match? (cat c s) r) 的字符串 $s$。 读者可以自行思考一下导数公式。 我想用代码表示是最清晰的。 1 2 3 4 5 6 7 8 9 10 11 12 13 14 (define (derive re c) (match re [(Void) (Void)] [(Eps) (Void)] [(Dot) (Eps)] [(Chr ch) (if (char=? ch c) (Eps) (Void))] [(Alt e1 e2) (make-alt (derive e1 c) (derive e2 c))] [(Cat e1 e2) (if (nullable? e1) (make-alt (make-cat (derive e1 c) e2) (derive e2 c)) (make-cat (derive e1 c) e2))] [(Star e) (make-cat (derive e c) (Star e))])) 导数法将是我们使用的核心算法。 特性与抽象语法 我们将实现支持连接（cat），选择（alt）与闭包（kleene star）三种特性的正则表达式。同时添加“任意字符”（Dot）这种有用的语法糖（为了辅助包含匹配）。 ...

光剑的后日谈 #3. 这次来聊聊什么是许愿机。 If bird born with no shackles 现在我们需要写一段代码，用矩阵快速幂求解一个递推数列： $$ \begin{cases} f(0)=f(1)=f(2)=1 \\\\ f(n)=f(n-1)+2f(n-2)+5f(n-3), n \geq 3 \end{cases} $$我们知道我们将数列中的相邻几项写成一个向量 $(f(i), f(i+1), f(i+2))$，然后找到一个矩阵乘上它转移到下一个向量 $(f(i+1), f(i+2), f(i+3))$，那么这个矩阵怎么算呢？ 猜肯定是一个办法，但肯定不好。手动求解，待定系数也是一种方法。 然而，我们还有更加优雅的做法。 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 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 from z3 import * def solve_transition_matrix(): # 1. 创建求解器 s = Solver() # 2. 定义我们需要求解的 3x3 转移矩阵 M # 变量 m_r_c 代表矩阵第 r 行第 c 列的元素 (全是整数) M = [[Int(f'm_{r}_{c}') for c in range(3)] for r in range(3)] # 3. 定义“任意”时刻的输入向量状态 # 设 f0, f1, f2 分别代表 f(i), f(i+1), f(i+2) # 我们使用 Ints 创建符号变量，这些将作为全称量词的变量 f0, f1, f2 = Ints('f0 f1 f2') # 构造当前向量 V_i v_current = [f0, f1, f2] # 4. 根据递推公式定义期望的输出向量 V_{i+1} # 题目递推式: f(n) = f(n-1) + 2f(n-2) + 5f(n-3) # 对应到我们的符号: 下一项 f3 = f2 + 2*f1 + 5*f0 f3 = f2 + 2 * f1 + 5 * f0 # 构造下一刻向量 V_{i+1} = [f(i+1), f(i+2), f(i+3)] v_next = [f1, f2, f3] # 5. 核心逻辑：构造约束 # 约束条件：M * v_current == v_next # 这个等式必须对“所有”的 f0, f1, f2 都成立 constraints = [] for r in range(3): # 矩阵乘法：第 r 行 点乘 输入向量 row_product = sum(M[r][c] * v_current[c] for c in range(3)) # 结果必须等于输出向量的对应项 constraints.append(row_product == v_next[r]) # 使用 ForAll (全称量词) # 读作：对于任意整数 f0, f1, f2，上述约束(And(constraints))都必须成立 s.add(ForAll([f0, f1, f2], And(constraints))) # 6. 求解并打印结果 if s.check() == sat: m = s.model() print("成功找到转移矩阵 M：") print("-" * 15) # 将 z3 的解转换为 Python 整数并格式化输出 for r in range(3): row_vals = [m.evaluate(M[r][c]).as_long() for c in range(3)] print(f"| {row_vals[0]:^3} {row_vals[1]:^3} {row_vals[2]:^3} |") print("-" * 15) # 验证一下文章开头的直觉 # 第一行应该是 0 1 0 (输出 f1) # 第二行应该是 0 0 1 (输出 f2) # 第三行应该是 5 2 1 (输出 5f0 + 2f1 + 1f2) else: print("未找到满足条件的矩阵。") if __name__ == "__main__": solve_transition_matrix() 用 Python 运行这段代码（当然你需要先使用 pip install z3-solver 来解决库的依赖），你会得到这样的输出： ...

光剑后日谈 #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-表达式，我们就可以更顺畅地进入 λ 演算的世界了。 ...