Posts

瓜豆原理 一个图形经过任意旋转、缩放、平移、对称之后，与原图形保持相似，且相似比等于缩放比。 非常强大而泛用的定理。可以用来解决一整类初中的几何题。 这篇文章的目的是证明它，从地基开始重构这整套工具箱。所以默认读者已经会了这些东西，主要进行推式子。 定义 1：线性变换与仿射变换 线性变换 我们常常听说，“某某变换（比如缩放，旋转）是线性变换”。那么什么是“线性变换”？ 我们称一个对 $n$ 维点的变换是线性变换，当且仅当存在一组 $\R^n \to \R$ 的线性变换 $\{g_i\}(1\le i \le n)$ 使得： $$f((x_1, x_2, \cdots x_n)) = (g_1((x_1, x_2, \cdots x_n)), g_2((x_1, x_2, \cdots x_n)), \cdots g_n((x_1, x_2, \cdots x_n)))$$这里的“$\R^n\to \R$ 的线性变换”指满足以下两条性质的变换： 可加性。对于变换 $f$，当且仅当 $\forall x\in \R^n, y\in \R^n\; f(x + y) = f(x)+f(y)$ 时它满足这条性质。 齐性。对于变换 $f$，当且仅当 $\forall x\in \R^n, c\in \R\; f(cx) = cf(x)$ 时它满足这条性质。 容易发现，这样的变换一定是形如 $f((x_1, \cdots x_n)) = \sum_{i = 1}^n a_ix_i$ 的变换，其中 $a_i$ 是常数。 ...

一个自动的 24 点求解器。输入四个数字就会自动输出所有解。 目前还有一点局限性：它会输出许多本质相同的解，比如 a 和 -(-a)。所以下一步可以实现表达式正则化和去重。 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 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 #lang racket (define a (make-vector 4)) (let read-a ([i 0]) (when (< i 4) (vector-set! a i (read)) (when (not (number? (vector-ref a i))) (error "Invalid input!")) (read-a (+ i 1))) (vector-sort! a <)) (struct node (val op1 op2 e1 e2) #:transparent #:mutable) (define (print-ans p) (if (eq? (node-e1 p) (void)) (display (node-val p)) (begin (display #\() ; (display #\() (when (eq? (node-op1 p) '-) (display (node-op1 p))) (print-ans (node-e1 p)) (display (node-op2 p)) ; (display #\() (print-ans (node-e2 p)) ; (display #\)) (display #\))))) (define operators (list (cons '+ +) (cons '- -) (cons '* *) (cons '/ /))) (define (solve l r) (if (= l r) (list (node (vector-ref a l) (void) (void) (void) (void))) (let ([res '()]) (let loop ([i l]) (when (< i r) (let ([p1 (solve l i)] [p2 (solve (+ i 1) r)]) (for* ([op1 operators] [op2 operators] [e1 p1] [e2 p2]) (unless (or (and (= (node-val e2) 0) (eq? (car op2) '/)) (eq? (car op1) '*) (eq? (car op1) '/)) (let ([val ((cdr op2) ((cdr op1) (node-val e1)) (node-val e2))]) (set! res (cons (node val (car op1) (car op2) e1 e2) res)))))) (loop (+ i 1)))) res))) (define ans (void)) ; Helper function to reverse a subarray of vector `v` from `start` to `end` inclusive. (define (reverse-subarray v start end) (let loop ([i start] [j end]) (when (< i j) ; Swap elements at index i and j (let ([temp (vector-ref v i)]) (vector-set! v i (vector-ref v j)) (vector-set! v j temp)) (loop (+ i 1) (- j 1))))) ; Implements the C++ std::next_permutation algorithm. ; Mutates global vector 'a' in place to the next lexicographical permutation. ; Returns #t if a next permutation was found, #f if it wrapped around to the first permutation. (define (next-permutation a) (let ([n (vector-length a)]) ; Step 1: Find pivot point 'i' (find first element a[i] < a[i+1] from right) (let loop-find-pivot ([i (- n 2)]) (cond ; Case 1: No pivot found (vector is in reverse order) [(< i 0) ; Reverse the whole vector to get the first permutation. (reverse-subarray a 0 (- n 1)) ; (displayln "!!!!!!!\n") #f] ; Return #f to indicate we wrapped around. ; Case 2: Found pivot point 'i' [(< (vector-ref a i) (vector-ref a (+ i 1))) ; (displayln i) ; Step 2: Find swap element 'j' (find first element a[j] > a[i] from right) (let loop-find-swap ([j (- n 1)]) (if (> (vector-ref a j) (vector-ref a i)) ; Step 3: Swap elements at i and j (let ([temp (vector-ref a i)]) (vector-set! a i (vector-ref a j)) (vector-set! a j temp)) (loop-find-swap (- j 1)))) ; Step 4: Reverse suffix starting from i + 1 (reverse-subarray a (+ i 1) (- n 1)) #t] ; Return #t to indicate a next permutation was found. ; Case 3: Continue searching for pivot point 'i' to the left [else (loop-find-pivot (- i 1))])))) (define (print-a) (let loop ([i 0]) (when (< i 4) (display (vector-ref a i)) (display #\space) (loop (+ i 1)))) (newline)) (let loop ([i 0]) (when (< i 24) ; (print-a) (set! ans (solve 0 3)) (for ([p ans]) (when (= (node-val p) 24) (print-ans p) (newline) #; (exit))) (when (next-permutation a) (loop (+ i 1)))))

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