SICP 第 15 讲：逻辑编程（上）

视频元信息

• 视频标题：【MIT本科一年级必修】6.001 计算机程序的构造与解释（SICP）1986传奇原版·全20讲·中英双语字幕 p16 15-逻辑编程（上）
• 课程来源：MIT 6.001 Structure and Interpretation of Computer Programs（1986 年原版录像）
• 本讲主题：逻辑编程（Logic Programming）上篇——声明式知识、关系与查询语言
• 时长说明：转录文本未提供完整时长，按内容推断为单集课程的上半部分

内容摘要（TL;DR）

本讲引入逻辑编程这一全新范式：与传统的"如何做"（how-to）过程式编程相对，逻辑编程关注声明"什么是真的"（what is true）。课程以《创世记》家谱和归并排序逻辑为例，展示同一份声明式知识可回答多种不同方向的问题。随后介绍查询语言（Query Language）的三大要素——原始查询、逻辑组合（and/or/not）、规则抽象，并演示其在人员数据库上的运行。

一、从过程式思维到声明式思维 [05:07]

核心观点

课程开场重申计算机科学的本质：

"thoughts about computer programming is that it's only incidentally has to do with getting a computer to do something, primarily a computer program has to do with its way of expressing ideas, with communicating ideas." （编程只是偶然地与"让计算机做事"有关，本质上它是表达思想、交流思想的方式。）

理解：这正是 SICP 贯穿始终的哲学——程序是思想的载体。当我们想表达新类型的思想时，就需要发明新的表达模式。今天要做的就是发明一种新语言。

传统编程的局限

• 我们写的程序大多是 how-to knowledge（如何做的知识）：告诉机器输入是什么、要得到什么输出。
• 例如平方根程序能回答"144 的平方根是多少？"，但无法回答"17 是哪个数的平方根？"。
• 思考：这说明过程式程序带有方向性——输入与输出被严格区分，知识被"绑定"在特定的使用方向上。

逻辑编程的设想

核心目标：构建一种语言，你只需陈述事实（facts），语言自动内置通用的推理知识，能自行推导出方法。

• 你告诉它"什么是真的"，它就能回答各种问题。
• 语言内置通用逻辑规则，从事实中演化出推理方法。

二、家谱例子：一份事实，多种问法 [05:52]

事实的陈述

以《创世记》家谱为例，向程序陈述事实：

• 亚当的儿子是亚伯（Abel）
• 亚当的儿子是该隐（Kane/Cain）
• 该隐的儿子是以诺（Enoch）
• 以诺的儿子是……（依此类推）

同一组事实，不同的提问

关键洞察（考点）：一条声明式知识（如"亚当的儿子是该隐"）可以作为多种不同"如何做"知识的基础。

• 对比过程式程序：你必须明确告诉它输入和期望的输出。
• 声明式事实对"要问什么问题"是中立的（unbiased）。

理解：这就是逻辑编程威力的本质——知识与使用方式解耦。而过程式程序因为本身就是 how-to knowledge，天然倾向于寻找某个特定答案。

三、推理规则：从事实到推导 [09:21]

规则示例

在事实基础上加入推理规则（rules of inference）：

如果 x 的儿子是 y，且 y 的儿子是 z，
那么 x 的孙子是 z。

（用问号表示变量，如 ?x、?y、?z）

有了这条规则，就能提问"谁的孙子是谁"，或推导出所有祖孙关系。

归并（Merge）程序与底层逻辑

课程用一个具体例子——归并两个有序列表——来对比"程序"与"逻辑"。

归并程序（过程式）：

• 若 x 为空，答案为 y；
• 若 y 为空，答案为 x；
• 否则比较 x 和 y 的首元素，把较小的那个接到"递归归并剩余部分"的结果上。

底层逻辑（声明式）：

• 若 x 的剩余部分 与 y 归并成 z，且 a 小于 y 的首元素，则 (a . x的剩余部分) 与 y 归并成 (a . z)。
• 类似地有另一条对称规则。
• 边界情形：对任意 x，x 与空列表归并成 x。

重要区别（考点）：

• 过程像一个"盒子"：x、y 进去，答案出来——这是函数，答案由 x、y 唯一决定。
• 逻辑规则谈论的是关系（relation）：x 和 y 归并成 z，三者之间是关系，不指定哪个是输入、哪个是输出。

四、关系 vs 函数：两大本质差异 [25:29]

逻辑编程与传统编程的两大区别（核心考点）

差异一：关系而非函数

• 传统编程计算函数：有明确输入输出。
• 逻辑编程处理关系：原则上没有方向性。
• 同一份知识既能回答"1,3,7 和 2,4,8 归并成什么？"，也能回答"什么和什么归并成 1,2,3,4,7,8？"。

差异二：答案不唯一

• 函数式程序对一个输入只有一个答案。
• 关系可以有多个答案。例如问"哪两个列表归并成 1,2,3,4,7,8？"，理论上有多达 2⁶（64）种答案。

逻辑编程的三句箴言

逻辑编程者常说：

1. 用逻辑表达什么是真的（express what is true）；
2. 用逻辑检验什么是真的（check whether something is true）；
3. 用逻辑发现什么是真的（find out what is true）。

理解：第三点"检验"对应的是是非问句（如"137 和 248 归并成 1,2,6,10 吗？"→ 否），前两点则对应开放式提问。

五、查询语言（Query Language）概览 [29:45]

与 Prolog 的关系

• 最著名的逻辑编程语言是 Prolog。
• 本课要实现的语言叫 查询语言（Query Language），本质上是 Prolog 的核心。
• 区别：查询语言在 Lisp 解释器之上实现（双重解释），因此慢得多，但能力和局限与 Prolog 基本相同。

【拓展】SICP 第 4.4 节正是"Logic Programming"，用 Lisp 实现一个查询系统。这是理解 Prolog 内部机制的绝佳途径。

用三大要素分析该语言

课程再次套用贯穿全课的分析框架：

1. 原始元素（primitives）：有哪些基本构件？
2. 组合手段（means of combination）：如何把原始元素拼起来？
3. 抽象手段（means of abstraction）：如何命名复合构件？

六、原始元素：查询（Query）[33:20]

示例数据库

一个波士顿高科技公司的人员记录片段：

原始查询的语法

• 唯一的原始元素就是查询（query）。
• 语法约定：不带问号的符号是字面量（literal），带问号的（如 ?x）是变量。

示例：

job ?x computer programmer

→ 匹配数据库中所有"职位是计算机程序员"的事实。

job ?x computer ?type

→ ?type 可匹配 wizard 或 programmer。

点号（dot）语法

易错点：computer programmer 匹配的是恰好两个符号的列表。而 Louis 的职位是 computer programmer trainee（三个符号），不匹配。

要匹配变长列表，需用点号表示法：

job ?x computer . ?type

→ ?type 绑定为列表的剩余部分，对 Louis 来说就是 programmer trainee。

理解：这正是 Lisp 的 cons 点对表示法的直接复用，由列表读取器（list reader）自动处理。

运行示例

• job ?x computer . ?y → 找出所有计算机部门的人（4 个答案）。
• supervisor ?x ?y → 列出所有主管关系。
• address ?x Cambridge . ?anything → 只有一人住在 Cambridge。

输出机制：系统把查询用所有可能的变量取值实例化（instantiate）后打印出来。Prolog 则不同，它会输出 x = ...、y = ... 的形式。这只是表面差异。

七、组合手段：逻辑运算 [43:05]

AND

and job ?x computer . ?y
    supervisor ?x ?z

→ 找出所有计算机部门的人及其主管。

注意变量共享：两个 ?x 指同一个 x。x 在计算机部门工作，且 x 的主管是 z。

用 Lisp 谓词增强：lisp-value

and salary ?p ?a
    lisp-value greater-than ?a 30000

→ 找出所有薪水超过 30000 的人。

lisp-value 是一个接口 hack，允许在查询中调用任意 Lisp 谓词，从而获得额外能力。但它不是逻辑，会带来代价（见下文）。

NOT

and job ?x computer . ?y
    not (and supervisor ?x ?z
              job ?z computer . ?w)

→ 找出所有在计算机部门工作、但没有计算机部门主管的人（即部门里的"大人物"）。

组合手段小结

逻辑语言的组合手段是逻辑运算：and、or、not，外加 lisp-value 这个非逻辑的接口扩展。

八、抽象手段：规则（Rule）[48:40]

定义规则

把上面的复杂查询命名为"大人物（big shot）"：

rule (big-shot ?x ?department)
     (and job ?x ?department . ?y
          not (and supervisor ?x ?z
                    job ?z ?department . ?w)))

规则的三部分

规则结构（考点）：

1. 表明这是规则的关键字（rule）；
2. 结论（conclusion）；
3. 主体（body）。

读法：若规则主体为真，则可推出结论为真。要推导 ?x 是某部门的大人物，验证主体即可。

归并逻辑改写为规则

将前面的归并逻辑翻译成规则：

规则 1（空列表情形，无主体）：

rule (merge-to-form () ?y ?y)

无主体的规则永远为真。

规则 2（对称的空列表情形）：

rule (merge-to-form ?y () ?y)

规则 3（递归情形）：

rule (merge-to-form (?a . ?x) (?b . ?y) (?b . ?z))
     (and (merge-to-form ?a . ?x ?y ?z)
          (lisp-value greater-than ?a ?b)))

含义：若 (?a . ?x) 与 ?y 归并成 ?z，且 a > b，则 (?a . ?x) 与 (?b . ?y) 归并成 (?b . ?z)。

规则 4（对称的递归情形）：

rule (merge-to-form (?a . ?x) (?b . ?y) (?a . ?z))
     (and (merge-to-form ?x (?b . ?y) ?z)
          (lisp-value greater-than ?b ?a)))

运行演示

• 当函数用：merge-to-form (1 3 7) (2 4 8) ?z → 得到结果后系统还会继续检查是否还有其他答案（它先验地不知道只有一个答案）。
• 反向用：merge-to-form ?x ?y (1 2 3 4) → 找到多个解。
• 多答案用：merge-to-form ?x ?y (1 2 3 4 5) → 2⁵ = 32 种可能答案。

性能警告（易错点）：查询语言慢的原因有三：

1. 语言是双重解释的（在 Lisp 解释器之上再解释），真实实现会编译成原始操作；
2. 归并算法本身是双重递归；
3. 系统必须穷举所有可能性，无法先验排除。

答案以某种依赖规则尝试顺序的"任意顺序"输出。

九、答疑与关键权衡 [55:30]

提问：lisp-value 是否破坏双向查询能力？

回答：是的，会破坏（重要权衡）。

• 使用 not、lisp-value 或除 and 以外的任何东西，都会使"何时能双向工作"变得非常复杂。
• 引入 lisp-value 带来更多表达能力的同时，牺牲了逻辑编程的部分原则性能力。
• 这是一个必须做出的权衡（trade-off）。

理解：纯逻辑（Horn 子句 + and）有良好的理论性质，能保证较可靠的双向推理；一旦引入否定和外部谓词，就跌入非单调推理/完备性的复杂地带。

本讲小结

查询语言的三大要素：

课程预告：下半部分将讲解该语言如何实现。

关键标签 / 关键词

SICP #逻辑编程 #LogicProgramming #查询语言 #QueryLanguage #Prolog #声明式编程 #DeclarativeProgramming #关系 #Relation #推理规则 #Rule #知识表示 #MIT6001 #Lisp #双重解释 #lisp-value #归并 #Merge #Horn子句

本讲核心记忆点回顾：

• 红色重点：关系 vs 函数的两大差异（无方向性、多答案）；规则的三部分结构；lisp-value 破坏双向性的权衡。
• 蓝色理解：编程是表达思想的方式；声明式知识对提问中立；纯逻辑与引入否定/外部谓词之间的理论代价。
• 黑色事实：查询语言的三大要素、示例数据库、归并规则的四种情形。

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