1. 元编译器 — 自己写一个 Prolog

学完这章，你能用三行代码写出一个 Prolog 解释器——附赠调试器、计数器和证明树。

前置：DCG | 难度：★★★ | 后续：优化, lisprolog

写了这么多 Prolog，你想过一个问题吗：Prolog 自己是怎么运行的？

每次查询 ?- father(tom, jerry).，引擎怎么知道该匹配哪条规则？怎么知道先证明 male(tom) 再证明 parent(tom, jerry)？怎么知道还有没有别的答案？

如果你答不上来，Prolog 对你来说就是黑箱——能跑，但不知道为什么能跑。

我们把黑箱拆开。用 Prolog 自己写一个 Prolog 解释器。做完你会发现：原来引擎就三行代码。

给前端读者：Babel plugin 遍历 AST，你的 visitor 控制节点的解析路径。元编译器就是 Prolog 版的"Babel plugin API"——你接管了执行流程。

给后端读者：这就是"写一个自定义 DSL 解释器"的 Prolog 版。

性能提醒：vanilla MI 在生产中有 10x-100x 性能开销，不是要替换 swipl。学它是为了理解引擎，不是为了生产。

1.1. 第一步：认识 clause/2——元编程的钥匙

写 MI 之前，先认识一把钥匙。

clause(+Head, -Body)

clause/2 是 ISO 标准谓词，所有主流 Prolog 都支持。给它一个谓词名，它返回该谓词的子句体。先看事实：

?- clause(male(tom), Body).
Body = true.

事实没有体，Body 是 true。再看规则：

?- clause(father(X, Y), Body).
X = _,
Y = _,
Body = (male(X), parent(X, Y)).

Body 返回逗号连接的目标列表——合取在 Prolog 内部就是 (A, B) 结构。

listing/1 内部就是拿 clause/2 实现的。你调 listing(father/2)，引擎遍历 father/2 的所有子句，每条调 clause/2 拿 Body，再格式化输出。

有了 clause/2，我们就能在运行时"看到"程序每条子句——MI 每层递归都靠它查找当前目标该执行什么。

1.2. 第二步：Vanilla Meta-interpreter——三行

准备好了？最简 MI 叫 Vanilla MI，核心三行：

%% prove(+Goal) — 证明目标成立
prove(true) :- !.
prove((A, B)) :- !, prove(A), prove(B).
prove(H) :- clause(H, Body), prove(Body).

这三行就是 Prolog 执行模型的本质：

true 总是成功——递归终点
(A, B) 先证明 A 再证明 B——合取 = 顺序执行
其他目标通过 clause/2 找子句，递归证明 Body

第三个子句是核心：clause(H, Body) 拿到 H 对应的体，然后 prove(Body) 递归。如果 Body 又是 (male(X), parent(X, Y))，走规则 2 继续拆分。如果 Body 是 true，走规则 1 结束。

cut 呢？vanilla 不处理 cut——!/0 在 Body 里被当普通目标传给 clause/2，SWI-Prolog 的 clause/2 不会展开它。后面补。

1.2.1. 跑起来

假设有：

male(tom).
male(jerry).
parent(tom, jerry).
father(X, Y) :- male(X), parent(X, Y).

跑一下：

?- prove(father(tom, jerry)).
true .

?- prove(father(tom, X)).
X = jerry .

一模一样。三行代码写了一个 Prolog 解释器。

Prolog 时刻 — 用语言本身解释语言本身。Lisp 有 eval，Prolog 有 prove。元循环求值（meta-circular evaluation）——"解释器"和"被解释的语言"是同一个。

1.3. 第三步：加计数器——看引擎走了几步

vanilla 能跑了，但不知道引擎走了多少步。给每条子句装计数器：

:- dynamic rule_used/2.

prove_count(true, 0) :- !.
prove_count((A, B), N) :- !,
    prove_count(A, N1),
    prove_count(B, N2),
    N is N1 + N2.
prove_count(H, N) :-
    clause(H, Body),
    ( rule_used(H, N0) -> retract(rule_used(H, N0)), N1 is N0 + 1
    ; N1 = 1
    ),
    assert(rule_used(H, N1)),
    prove_count(Body, N2),
    N is N2 + 1.

跑完查 rule_used/2：

?- prove_count(father(tom, jerry), N).
N = 3 .

?- rule_used(Clause, Count).
Clause = male(tom),    Count = 1 ;
Clause = parent(tom, jerry), Count = 1 ;
Clause = father(tom, jerry), Count = 1 .

father(tom, jerry) 的证明调了三条子句，每条一次，加 MI 自身递归——三步。引擎工作量一目了然。

调试递归谓词时特别有用——看每条子句命中次数，是不是有意料外的重复调用。

1.4. 第四步：加调试器——看着引擎一步步走

计数器告诉次数，不告诉顺序。让引擎每一步都打印当前目标：

prove_debug(true, _) :- !.
prove_debug((A, B), Depth) :- !,
    prove_debug(A, Depth),
    prove_debug(B, Depth).
prove_debug(H, Depth) :-
    tab(Depth * 2),
    format("~w~n", [H]),
    clause(H, Body),
    D1 is Depth + 1,
    prove_debug(Body, D1),
    tab(Depth * 2),
    format("~w  [ok]~n", [H]).

Depth 控制缩进，进入打印目标名，返回打印 [ok]：

?- prove_debug(father(tom, jerry), 0).
father(tom, jerry)
  male(tom)          % Depth=1，缩进
  male(tom)  [ok]
  parent(tom, jerry)
  parent(tom, jerry) [ok]
father(tom, jerry) [ok]
true .

看到没？引擎先进 father(tom, jerry)，钻 male(tom)，完成，再钻 parent(tom, jerry)，完成，最后 father 自己完成。深度优先遍历，一清二楚。

写 Babel plugin 的读者：就像 AST visitor 加 console.log 看节点遍历顺序。

1.5. 第五步：做 Explainer——让引擎说怎么证明的

打印是给人看的，我们也可以把证明路径存成结构化数据——一棵树：

prove_explain(true, _, []) :- !.
prove_explain((A, B), Depth, Steps) :- !,
    prove_explain(A, Depth, Steps1),
    prove_explain(B, Depth, Steps2),
    append(Steps1, Steps2, Steps).
prove_explain(H, Depth, [step(H, SubSteps)]) :-
    clause(H, Body),
    D1 is Depth + 1,
    prove_explain(Body, D1, SubSteps).

prove_explain/3 返回步骤列表，每步是 step(Goal, SubSteps) 节点。有了树，渲染它（explain/1）：

explain(Goal) :-
    prove_explain(Goal, 0, Steps),
    print_steps(Steps, 0).

print_steps([], _).
print_steps([step(Goal, Subs)|Rest], Depth) :-
    tab(Depth * 2),
    format("~w  :-~n", [Goal]),
    D1 is Depth + 1,
    print_steps(Subs, D1),
    print_steps(Rest, Depth).

跑：

?- explain(father(tom, jerry)).
father(tom, jerry)  :-
  male(tom)  :-
  parent(tom, jerry)  :-
true .

每个 :- 表示"为证明上面目标，引擎去证明了下面子目标"。有了证明树，你不仅能看结果，还能说"引擎是这样推导出来的"。

1.6. 第六步：处理 Cut 和 Disjunction

MI 还不处理 !/0 和 ;/2。加上：

prove(true) :- !.
prove(!) :- !.                 % TODO: 实际 cut 需要控制回溯
prove((A, B)) :- !, prove(A), prove(B).
prove((A; _)) :- !, prove(A).  % 只尝试第一个分支
prove((_; B)) :- !, prove(B).  % 回溯分支
prove(H) :- clause(H, Body), prove(Body).

!/0 完整语义需追踪 choice point，较复杂。实际项目用 call/1 替代即可。

完整专家系统示例见 c9。

1.7. 终改！— 能做的远不止这些

从简单想法出发，一步步加了计数、调试、解释功能。你掌握的不只是 vanilla MI——而是一个可定制的推理引擎框架。

元编译器能做的远不止这些：

加超时控制——限制递归深度
加缓存——避免重复证明（这就是 tabling 的原理！）
加概率——给每条规则附置信度
拦截特定谓词——比如拦截 write/1 做自定义输出

参考：The Power of Prolog - Meta-Interpreters — Markus Triska 深度解读。

1.8. 我们学到了什么

三行代码，拆开了 Prolog 引擎的黑箱：

clause/2 是运行时子句查找核心
合取（,）对应顺序执行
回溯由引擎提供，MI 只管递归
加追踪、计数、解释，就是定制推理引擎的雏形

下次有人说"Prolog 是黑魔法"，你可以说：引擎就三行代码，我写给你看。

元编译器