1. 优化 — 让 Prolog 飞起来

学完这章，你能让 Prolog 程序从"跑不动"变成"嗖嗖的"——fib(30) 四千万次推理到一百八十次，就差一行代码。

前置：元编译器 | 难度：★★★ | 后续：—

Prolog 很慢？fib(30) 朴素递归要 3900 万次推理、2.5 秒。加上一行 :- table fib/2.，182 次推理、0.000 秒——差了二十万倍。

慢的不是 Prolog，是你的写法。

这一章我们从"为什么慢"开始，一步步把程序从"能跑"改到"飞起来"。你会学到四个武器：逻辑纯度保证改不错，Tabling让重复计算归零，尾递归让栈不爆，choice point 消除去掉无用回溯。

给 C 系读者：Choice point ≈ 函数入口处保存寄存器状态。每多一个就多一次保存/恢复开销。

给 Python 读者：Tabling ≈ functools.lru_cache，但自动推断依赖关系，不用手动指定缓存键。

1.1. 第一步：Prolog 为什么慢——Choice Point

先看一个"慢"的根因。

当谓词有多个匹配子句时，Prolog 在第一个子句设一个选择点（choice point），记录"还有备选"。回溯时引擎回到该点尝试下一条。每个 choice point 保存执行状态，多了就慢。

%% 有 choice point
color(red).
color(green).
color(blue).

每次调 color(X)，引擎在 color(red) 处设 choice point。如果调用方只要一个答案，这个 choice point 就浪费了。

怎么知道有没有 choice point？用 time/1 看：

?- time((color(_), fail)).
% 9 inferences, 0.000 CPU in 0.000 seconds (100% CPU)
false.

fail 强制回溯，引擎遍历三条子句——9 次推理。

目标：去掉不必要的 choice point，让引擎做更少的事。

1.2. 第二步：认识刀——Green Cut vs Red Cut

去掉 choice point 最直接的工具是 cut（!/0）。但 cut 分两种，用错了出事。

1.2.1. Green Cut——安全的优化

Green cut 切掉的是"不可能成功"的冗余分支，不影响答案集。删掉 cut，答案不变，只是多回溯。

%% Green Cut：子句间互斥
is_digit(X) :- X >= 0, X =< 9, !.

如果 X 不在 0-9，cut 不执行，失败。如果在，cut 提交该子句，告诉引擎"不用看别的了"（这里只有一条子句，! 去除外部 choice point）。

删掉 !，is_digit 的答案集不变——只是每次查询会多一个 false? 的冗余回溯。

1.2.2. Red Cut——危险的手术

Red cut 改变答案集。删掉 cut，程序逻辑不同。子句顺序变得关键。

%% Red Cut：顺序决定语义
max(A, B, A) :- A >= B, !.
max(_, B, B).

交换子句顺序：max(1, 2, M) 返回 M = 1（错的）。因为第一条 max(_, B, B) 先匹配了，_ 匹配 1，B = 2——不对。

1.2.3. 对比

对比维度	Green Cut	Red Cut
删 cut 影响	答案集不变，多回溯	答案集改变
安全性	安全，纯优化	危险，语义依赖 cut
顺序依赖	否	是
典型用途	提交互斥分支	避免不可能路径

1.2.4. 什么时候用 Cut

优先用 (-> ;)/2（if-then-else），隐含 cut 且更清晰：

%% 推荐：-> ; 代替 cut
max_if(A, B, M) :-
    ( A >= B -> M = A
    ; M = B ).

%% 不推荐：bare cut 容易意外语义
max_cut(A, B, A) :- A >= B, !.

Bare cut 只在两种情况下合理：1) Green cut 优化已知互斥的子句；2) 与 fail 配合实现否定。

1.3. 第三步：先写对——逻辑纯度

用 cut 之前，先学会写"不会改错"的代码。

逻辑纯度：谓词的行为不依赖 Prolog 执行顺序，结果与 Horn 子句的逻辑含义一致。纯谓词交换子句顺序不影响答案集：

%% 纯
append([], L, L).
append([H|T], L, [H|R]) :- append(T, L, R).

不管两个子句怎么换，答案一样。

不纯的依赖 cut 或副作用：

%% 不纯
max(A, B, A) :- A >= B, !.
max(_, B, B).

更隐蔽的不纯：

avg(L, Avg) :- sum(L, S), length(L, N), Avg is S / N.

如果 sum/2 或 length/2 参数没实例化——is/2 要求右边全实例化——就抛异常。

保持纯度的方法：

避免 cut，用 if_/3 或 -> ; 替代
用 dif/2 替代 \==
不纯操作（I/O、算术）集中到谓词边界

%% 用 dif/2 保持纯度
different(X, Y) :- dif(X, Y).

?- different(a, b).
true .

?- different(a, a).
false .

规则很简单：先写出纯逻辑版本，确认正确，再在热点路径上加优化。不要上来就切。

1.4. 第四步：终极大招——Tabling / Memoization

现在来真的。

SWI-Prolog 的 library(tabling) 提供记忆化求值——缓存已计算的子目标结果，避免重复递归。

1.4.1. 启用方式

一行就够：

:- use_module(library(tabling)).
:- table fib/2.

对比一下有和没有的效果（参考 code/hello/fib.pl）：

:- use_module(library(tabling)).
:- table fib/2.

fib(0, 1) :- !.
fib(1, 1) :- !.
fib(N, F) :-
    N > 1,
    N1 is N - 1,
    N2 is N - 2,
    fib(N1, F1),
    fib(N2, F2),
    F is F1 + F2.

没 tabling：

?- time(fib(30, F)).
% 39,080,737 inferences, 2.500 CPU in 2.500 seconds (100% CPU)
F = 832040.

有 tabling：

?- time(fib_tabled(30, F)).
% 182 inferences, 0.000 CPU in 0.000 seconds (100% CPU)
F = 832040.

3900 万 → 182。快了二十万倍。而且代码没变——只加了一行声明。

甚至能算 fib(1000)：

?- fib(1000, F).
F = 70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501.

1.4.2. Tabling 还解决了左递归

:- table ancestor/2.
ancestor(X, Z) :- parent(X, Z).
ancestor(X, Z) :- parent(X, Y), ancestor(Y, Z).

没 tabling，这个左递归直接死循环。加上 :- table ancestor/2.，引擎知道"这个目标我之前算过没"，自动避免无限递归。

Prolog 时刻 — 一行 :- table fib/2. 把指数级降到线性级。声明式优化的终极体现——告诉引擎"记住结果"，其它什么都不用改。

1.4.3. Tabling 限制

table 谓词的参数必须充分实例化（有限数量的变体）
有副作用（assert/retract）的谓词不推荐 tabling
增加内存占用——经典的空间换时间

1.5. 第五步：栈不爆——尾递归优化

递归再深也不怕——条件是最后一步必须是递归调用。

对比：

%% 非尾递归 — 递归后还有 is
factorial(0, 1).
factorial(N, F) :-
    N > 0,
    N1 is N - 1,
    factorial(N1, F1),
    F is N * F1.   % 递归后还有工作

%% 尾递归 — 用累加器
factorial_tail(N, F) :-
    factorial_acc(N, 1, F).

factorial_acc(0, Acc, Acc).
factorial_acc(N, Acc, F) :-
    N > 0,
    N1 is N - 1,
    Acc1 is Acc * N,
    factorial_acc(N1, Acc1, F).  % 最后一步是递归

非尾递归版本调 factorial(100000, _) 直接栈溢出。尾递归版本可以跑：

?- factorial_tail(100000, F).  % 成功

Prolog 编译器检测到尾递归时复用当前栈帧，不额外分配。核心在做递归之前把计算结果算好，通过累加器传下去。

1.6. 第六步：实战 Choice Point 消除

1.6.1. 成员检查

%% 有冗余 choice point
member_of(X, [X|_]).
member_of(X, [_|T]) :- member_of(X, T).

?- member_of(a, [a,b,c]).
true ;
false.   % 回溯说"没了"

用 !/0 或 once/1：

member_det(X, [X|_]) :- !.
member_det(X, [_|T]) :- member_det(X, T).

?- member_det(a, [a,b,c]).
true .   % 不再有冗余 choice point

1.6.2. color/1 消除

%% 消除前
color(red).
color(green).
color(blue).

%% 消除后
color_det(red) :- !.
color_det(green) :- !.
color_det(blue) :- !.

对比：

?- time((color(_), fail)).
% 9 inferences, 0.000 CPU in 0.000 seconds (100% CPU)
false.

?- time((color_det(_), fail)).
% 3 inferences, 0.000 CPU in 0.000 seconds (100% CPU)
false.

9 → 3，少了三分之二。

1.6.3. if_/3 模式

SWI-Prolog 的 library(reif) 提供可复用的纯度模式——条件分支不丢失纯度：

:- use_module(library(reif)).

cond_if(P, Then, Else) :-
    if_(P, Then, Else).

不过日常 -> ; 已经够用了：

max_if(A, B, M) :-
    (   A >= B
    ->  M = A
    ;   M = B
    ).

1.6.4. 什么时候不该消除

需要回溯枚举所有答案时不能消
不确定有没有 choice point 时，用 predicate_property/2 检查

?- predicate_property(append([], _, _), P).
P = visible ;
P = interpreted ;
P = nondeterministic ;  % 非确定性 = 有 choice point
...

1.7. 终改！— 决策框架

学了一堆工具，什么场景用哪个？给你一个决策树：

先写纯逻辑——不要边写边 optimize，先跑对
有重复计算？ → Tabling（一行搞定）
递归太深？ → 尾递归（加累加器）
只要求一个答案，但有多余 choice point？ → !/0 或 once/1
条件分支？ → -> ; 或 library(reif)
不确定性能瓶颈？ → 先 time/1 或 profile/1 测

?- time(fib(30, _)).
% 40,317,617 inferences, 2.344 CPU in 2.344 seconds

参考：The Power of Prolog - Purity — Markus Triska 关于逻辑纯度的深度讨论。

1.8. 我们学到了什么

优化不是"写得更快"，是让引擎做更少的事：

逻辑纯度保证优化不改语义
Tabling 用空间换时间，一行代码二十万倍提升
尾递归压缩栈空间，深递归不爆栈
Choice point 消除减少无用回溯

学完这章，下次听到"Prolog 慢"，你会说：不是 Prolog 慢，是你没优化。

优化