视频封面

视频元信息

  • 课程：MIT 6.001 SICP（1986 原版）
  • 本讲主题：逻辑编程（下）——查询系统的实现、规则与合一、逻辑语言的语义陷阱
  • 时长：约 30 分钟

本讲是 SICP 逻辑编程部分的收尾，核心不是"教你怎么用 Prolog"，而是揭示逻辑语言的实现本质与语义局限。视频中段明确警告：本语言的 not 不是逻辑否定，而是"不可从数据库推出"，这属于闭世界假设，是极易踩坑之处。

内容摘要（TL;DR）

本讲从模式匹配器与原始查询的流式实现讲起，说明 and/or/not 如何通过流的串并联与过滤实现组合，并强调闭包原则。随后讲解规则作为抽象手段、合一器（unifier）的对称匹配机制，最后深入剖析逻辑语言的三大问题：求值顺序导致的死循环、not 的闭世界假设、以及"合一"并非真正的逻辑推理。

一、模式匹配器回顾 [00:72]

要点：模式匹配器（matcher）是逻辑语言的最小内核，它回答的是"在已有字典约束下，模式能否与数据一致匹配"。

  • 模式匹配的语法示例：
    • (computer ?x)：匹配两元素列表，第一个是符号 computer
    • (computer ?x . ?rest)：匹配以 computer 开头的任意长列表（点号由列表读取器自动处理）
    • (?x ?x)：两元素列表，两个元素必须相同
    • (?x ?y ?y ?x)：四元素列表，第一等于第四、第二等于第三
    • (a . ?rest)：以 a 开头的任意列表
  • match 过程签名：(match pattern data dictionary)
  • match 提出的问题：是否存在某种方式，在字典已有绑定的约束下，把模式与数据对象匹配起来？
  • 示例：用 (?x ?y ?y ?x) 匹配 (a b b a)，字典为 {x = a}
    • 匹配成功，返回扩展字典 {x = a, y = b}
  • 反例：同样模式匹配 (a b b a)，但字典为 {y = a}
    • 匹配失败，返回 fail

理解：匹配器的本质是一个"约束传播器"——它不接受任何与已有绑定冲突的匹配，返回的始终是扩展后的字典或失败。这与后面合一器的思想一脉相承。

易错点：match 与 unify 不同。match 是"模式 vs 数据"，只能单向；unify 是"模式 vs 模式"，需要双向对称。视频后段会专门讲这个区别。

二、原始查询的流式实现 [04:43]

要点：原始查询（primitive query）被设计为一个"两流进、一流出"的黑盒，为的是让组合子能优雅地级联。

  • 查询示例：(job ?x (?d . ?y))
  • 原始查询的形状：
    • 输入流 1：数据库中的所有事实（facts）
    • 输入流 2：字典流（dictionaries）
    • 输出流：扩展后的字典流
  • 工作过程：对每个进来的字典，遍历数据库中的每条事实，调用 match(pattern, fact, dictionary)，每次成功匹配就输出一个扩展字典
  • 一个字典进来，可能输出很多字典，也可能输出零个
  • 空字典（empty frame）：表示"无历史约束，找出所有可能匹配"——这正是顶层输入查询时的初始状态
  • 顶层行为：系统喂入一个空字典，对输出的每个字典，用原查询实例化，产生实例化模式流并打印到终端

思考：为什么不用简单的递归而要用流？答案在下一节——因为流式结构能无缝扩展到组合子，这就是"闭包"的威力。

三、组合手段：and / or / not 的流式实现 [10:14]

要点：and、or、not 都可以用流的连接、扇出/合并、过滤来实现，且从外部看形状与原始查询完全一致。

3.1 and（串联）

  • 把第一个查询的输出流接到第二个查询的输入流
  • 示例：(and (job ?x (?d . ?y)) (supervisor ?x ?z))
  • 关键机制：第二个查询收到的字典里已经含 x、y、d 的绑定，因此 ?x 在两个子查询中必然指同一事物
  • 理解：这就是约束传递——前一个查询的绑定成为后一个查询的"上下文约束"。

3.2 or（并联）

  • 把数据库流和字典流扇出（fan out），分别送入 p 和 q
  • 用某种合并机制把两路结果揉成一个流
  • 从外部看，整个 or 盒子形状不变

3.3 not（纯过滤器）

  • not p 不扩展任何字典，只做过滤
  • 对进来的字典：找出所有匹配，只要有匹配就丢弃；没有匹配就放行
  • 类比：and 像电阻串联，or 像并联，not 是纯筛选

核心考点：闭包（closure） 组合手段构造出的东西，与它组合的原始东西具有相同的整体结构。因此 and/or/not 的盒子可以互相嵌套，(and (job ...) (not (supervisor ...))) 这种写法才成立。这与 Escher 图像语言、用 pair 构造复杂结构是同一个原理。

四、字典的来源与生命周期 [17:29]

要点：字典是临时生成的约束集合，本质就是环境（environment）。

  • 初始字典来自你输入的内容：系统启动时构造整个结构，喂入一个空字典
  • 在嵌套组合中，字典由上游查询的输出来
  • 具体例子：若顶层输入 (and (job ?x (?d . ?y)) (supervisor ?x ?z))
    • 第一个查询处理空字典，输出一批含 x、y、d 的字典
    • 这些字典成为第二个查询的输入，再输出含 z 的字典
  • 字典是临时对象：匹配完成后即消失，不再被需要时被回收

理解：作者明确指出字典"就是一堆符号的含义"，这正是我们一直叫的 frame 或 environment。所以"评估一个查询"与"在环境中求值"是同一回事。

五、规则的实现与合一器 [23:22]

要点：规则是逻辑语言的抽象手段；实现规则需要比匹配器更一般的合一器（unifier）。

5.1 规则的基本思想

  • 示例规则：(boss ?z ?d) :- (and (job ?x (?d . ?y)) (supervisor ?x ?z))
  • 含义：若存在某人 x 在部门 d 工作，且 z 是 x 的主管，则 z 是 d 的老板
  • 实现方式：把规则体（body）用盒子包起来，命名为结论（conclusion）(boss ?z ?d)

5.2 规则应用的基本流程

  1. 把查询与规则的结论匹配，得到字典
    • 例：查询 (boss Ben-Bitdiddle computer) 匹配结论 (boss ?z ?d)，得字典 {z = Ben-Bitdiddle, d = computer}
  2. 用该字典处理规则体
  3. 若有结果输出，则查询为真

5.3 问题：查询里也可能有变量

  • 若查询是 (boss ?who computer)，那么匹配就变成"模式 vs 模式"
  • 这需要 unifier（合一器）：找出使两个模式同时成立的最一般替换

5.4 合一器示例

  • 模式 (?x ?x) 与模式 (?a ?b . ?z) 合一：
    • 推出 ?x 必须是 a 开头、?y 必须是 b、?z 必须是 c 之类
  • 更复杂情形：(?x ?x) 与 (?y . ?y) 合一
    • 需要解不动点方程：y = (a . y)，即 y 是无限列表 (a a a a ...)

易错点：合一器不是魔法 视频反复强调：合一器只是模式匹配器加了三四行代码——增加一个"变量对变量"的子句，去字典里查一致性。所谓"演绎"只是递归展开匹配的副产品。硬情形（涉及不动点方程）合一器直接放弃，否则会陷入死循环。其他逻辑语言（如 Prolog）就真的会死循环。

5.5 规则的正式定义

  • 应用规则 = 在由"规则结论与查询合一"形成的环境中，求值规则体
  • 与元循环求值器/替换模型形式完全对应：应用过程 = 在"参数绑定到实参"的环境中求值过程体
  • 思考：规则应用与过程应用形式同构——这正是"逻辑语言也是语言"的深层证据。

5.6 变量冲突的暴力解法

  • 问题：规则里的 ?y 与查询里的 ?y 不能是同一个
  • 解法：每次应用规则，把规则中所有变量一致地重命名为全新唯一名字
  • 拓展：这与"用环境链解决局部变量"是同一问题的两种解法——重命名概念上更简单但效率低；环境模型更优雅。

六、逻辑语言的语义陷阱 [34:44]

要点：本语言的 and/or/not/:- 不是逻辑学中的合取/析取/否定/蕴含，这是最深刻的部分。

6.1 陷阱一：求值顺序导致死循环

  • 定义 outranked-by 有两种写法，仅交换两个子句的顺序：
    • 写法 A：先查 supervisor，再递归查 outranked-by
    • 写法 B：先递归查 outranked-by，再查 supervisor
  • 逻辑上二者等价，但写法 B 会无限循环：
    • 它先问"找一个 m 使 m 被 Bitdiddle 超越"，而这个问题又需要先解同一个问题
    • 写法 A 因为先有 supervisor 的约束，m 已被限制，不会失控

易错点：逻辑编程中，子句顺序和规则顺序会极大影响效率，甚至决定程序是否终止。这与逻辑等价性无关，纯属实现细节。相关研究（尤其是并行逻辑编程）试图通过"所有规则并行检查"来缓解。

6.2 陷阱二：not 是"不可推出"而非"不真"

  • 经典逻辑三段论：所有人会死 → 苏格拉底是人 → 苏格拉底会死
  • 数据库示例：
    • Socrates is Greek、Plato is Greek、Zeus is Greek、Zeus is god
    • 所有人类会死；所有希腊人（非神）是人；所有人类会犯错
    • 希腊神的地址是"精神无限"
  • 查询 (and (perfect ?x) (address ?x ?y)) 与 (and (address ?x ?y) (perfect ?x)) 结果不同：
    • 前者返回"精神无限"（Zeus）
    • 后者返回空——因为 not 是过滤器，先由 address 生成候选，再由 not 过滤；反过来时 perfect 一开始找不到任何东西可供过滤

核心考点：闭世界假设（Closed World Assumption） 本语言的 not 含义是"不可从数据库推出"，而非"不真"。任何数据库不知道的事，系统都乐意说"not 它"。

  • 系统不知道 Zeus 是否会死，就说 not mortal Zeus 为真
  • 系统不知道 Zeus 是否会犯错，就说 not fallible Zeus 为真
  • 于是 Zeus 被判定为"完美存在"，得到"精神无限"的地址
  • 但神话里希腊神不死却会犯错，所以正确答案应是"无地址"

这个假设在逻辑上不自洽（not not X 未必等于 X），在工程上极其危险——它等于宣称"我不知道的东西都与本问题无关"。视频调侃：大多数公司的市场部门就是这样运作的。

6.3 陷阱三：合一并非真正的逻辑推理

  • 本语言的全部"推理"都藏在合一器里，而合一器本质只是模式匹配器
  • 真正的逻辑否定推理是可行的，但极其低效，逻辑编程语言普遍不采用
  • 因此本语言"看起来在推理，其实并没有"

七、总结与开放问题 [50:00]

要点：逻辑编程是激动人心的构想，但"真正的逻辑语言"仍是未解难题。

  • 优点：从命令式跨越到声明式，可以谈论关系而不只是"输入输出"，抽象层次更高，威力巨大
  • 问题：
    • 求值顺序敏感（可能死循环）
    • not 依赖闭世界假设（语义不纯）
    • 合一器能力有限（硬情形直接放弃）
  • 开放研究问题：
    1. 如何构造真正的逻辑语言？
    2. 如何桥接逻辑/关系世界与传统语言世界，兼取两者之力？

问答环节要点

  • 为什么不用"显式否定规则"解决闭世界问题？
    • 否定规则数量可能不有限，且有时你根本不想显式列出所有否定
    • 例：连通性推理中，你希望"没告诉我的就是不相连"，但显式否定会变得极其繁琐
  • 这是否是所有编程的普遍问题？
    • 是，但危险在于：如果你相信这就是逻辑，就会误用推论
    • 必须牢记 not 的含义建立在可能不成立的假设上
  • 能否修复而不牺牲推理能力？
    • 存在实现真否定的方法，但极其低效，故逻辑编程语言普遍回避

关键标签 / 关键词

SICP 逻辑编程 Logic Programming Prolog 模式匹配 Pattern Matching 合一器 Unifier 闭包 Closure 流式实现 Streams 规则 Rules 闭世界假设 Closed World Assumption 否定即失败 Negation as Failure 求值顺序 死循环 声明式编程 关系 不动点方程 元循环求值器 环境模型 变量重命名

生成时间：2026-10-11 14:35:00 生成平台：VideoNote www.xygy.top