高阶阅读：本系列是深度代码分析，适合完成全部 Hello Prolog 章节后阅读。

读前须知：本章需先理解 c5 中 clause/2 和 vanilla MI 的工作原理。JavaScript 读者注意——Prolog 的 closure 基于 fact 实现（通过 asserta 存储，回溯不撤销），和 JS 的 lexical scope capture 完全不同。

1. lisprolog

如果说用 Prolog 实现 bencode 解析是牛刀小试，那用 Prolog 实现一个 Lisp 解释器就是真正意义上的"用逻辑写程序"。

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

https://github.com/triska/lisprolog

用 Prolog 写一个 Lisp 解释器。这句话本身就让人兴奋。

两个都是符号处理语言，都源自 1960 年代——John McCarthy 的 Lisp 和 Alan Robinson 的 resolution 原理。但不意味着一个能轻松嵌入另一个。

作者 Markus Triska，SWI-Prolog 的 CLP(FD) 库维护者。他的代码可能是 Prolog 社区最值得读的。

lisprolog 大概 200 行，实现了一个完整的 Lisp 方言：

• S 表达式的表示与解析
• 环境（environment）的建立与查找
• 闭包、函数调用
• 算术、列表操作
• 递归

1.1. 数据结构：S 表达式

Lisp 的核心是 S 表达式。lisprolog 用 Prolog 项直接表达：

% 原子 → Prolog 原子（小写开头）
% 列表 → Prolog 列表
% 点对 → cons(A, B)
% 函数调用 → [fun, arg1, arg2, ...]

映射关系：

注意列表是怎么表示的：Lisp 的 (a b c) 就是 Prolog 的 [a, b, c]。Prolog 列表结构恰好能直接表示 Lisp 列表——这不是巧合，两个语言共享符号处理的 DNA。

1.2. 解析器：纯 DCG

S 表达式的解析用 DCG：

s_expression(E) --> atom(E).
s_expression(E) --> integer(E).
s_expression(cons(A, B)) --> "(", s_expression(A), ".", s_expression(B), ")".
s_expression([E|Es]) --> "(", s_expression(E), s_expressions(Es), ")".

cons/2 表示点对（dotted pair），列表是点对的语法糖。

入口：

read(E) -->
    blanks,
    s_expression(E),
    blanks.

blanks//0 跳过空白，s_expression//1 递归解析。经典 DCG 顶层设计。

注意到文件名是 lisprolog.pl，模块只导出 lisp/1——read/1 覆盖了 SWI-Prolog 内置的 read/1，所以模块隔离做得干净。

1.3. 环境模型

Lisp 执行依赖环境（变量绑定）。lisprolog 的环境用 Prolog fact 实现：

:- dynamic env/2.

env_init :-
    retractall(env(_, _)),
    asserta(env(\'nil\', \'nil\')).

env_lookup(Name, Value) :-
    env(Name, Value).

env_bind(Name, Value) :-
    asserta(env(Name, Value)).

关键设计：asserta/1 插入到事实库最前面，实现变量遮蔽（shadowing）——同名变量最新的绑定最先被 env/2 匹配到。

这是纯正的 Prolog 式符号表：不用哈希表，不用关联列表，database fact 就是环境。

1.4. 求值器：元解释器模式

求值器是 lisprolog 的核心，也是 vanilla meta-interpreter 的变体：

% Vanilla MI：用 Prolog 解释 Prolog
true --> true.
(Goal1, Goal2) --> mi(Goal1), mi(Goal2).
Goal --> {Goal}.

lisprolog 的 eval/2 结构与之类似——每个 Lisp 形式对应一个子句：

eval(Env, Val) :-
    atom(Env),
    env_lookup(Env, Val).
eval([quote, X], X).
eval([if, C, T, E], Val) :-
    eval(C, V),
    (   V == \'nil\'
    ->  eval(E, Val)
    ;   eval(T, Val)
    ).
eval([lambda, Args, Body], closure(Args, Body)).
eval([fun, Name], closure(Args, Body)) :-
    env_lookup(Name, closure(Args, Body)).
eval([Op|Args], Val) :-
    maplist(eval, Args, EArgs),
    apply(Op, EArgs, Val).

逐个拆解：

1. 变量引用：原子直接查环境。这和 vanilla MI 中 Goal --> {Goal} 的思路一致——把控制权交给底层。

2. quote：[quote, X] 不 eval X，直接返回。等价 Lisp 的 \'X。

3. if：只有 nil 是假，其余都是真。Prolog 的 (->;) 控制结构实现条件分支。

4. lambda 和闭包：[lambda, Args, Body] 求值为 closure(Args, Body)，不立即求值 Body。这是词法作用域的关键——闭包捕获当前环境。

5. 函数应用：先 maplist(eval, Args, EArgs) 对所有参数求值，再调用 apply/3。

1.5. Apply 函数

apply(closure([Arg], Body), [Val], Result) :-
    env_bind(Arg, Val),
    eval(Body, Result).
apply(closure([Arg|Args], Body), [Val|Vals], Result) :-
    env_bind(Arg, Val),
    apply(closure(Args, Body), Vals, Result).
apply(+, [X, Y], Z) :- Z is X + Y.
apply(-, [X, Y], Z) :- Z is X - Y.
apply(car, [cons(X, _)], X).
apply(cdr, [cons(_, X)], X).
apply(cons, [X, Y], cons(X, Y)).
apply(list, Args, Args).
apply(eq, [X, X], t) :- !.
apply(eq, [_, _], \'nil\').

闭包应用就是环境扩展：参数绑定到形式参数，然后 eval body。

原始函数（+、-、car、cdr 等）直接映射到 Prolog 内置运算——这是元解释器的"地面层"，链接触摸 Prolog 运行时。

1.6. 自举：Lisp 定义 Lisp 函数

lisprolog 里定义的 Lisp 函数可以互相调用：

lisp("
    (defun fact (n)
        (if (eq n 0)
            1
            (* n (fact (- n 1)))))
    (fact 5)
").

defun 的实现：

eval([defun, Name, Args, Body], Name) :-
    env_bind(Name, closure(Args, Body)).

就是往环境里装一个闭包。没有宏，没有特殊形式——defun 就是 eval 的一个子句。

1.7. Prolog 和 Lisp 的天然映射

读完整段代码，你会发现一个模式：Lisp 的特性恰好都有 Prolog 的对应物。

不是巧合。两个语言共享符号计算的基因。

1.8. 注意事项

闭包环境中 env_bind 用 asserta 实现遮蔽，但闭包返回后绑定不会自动撤销。这个是 toy interpreter 的简化方案——生产环境需要 save/restore。

1.9. 小结

200 行，一个完整的 Lisp 解释器。

读这段代码的最佳方式：

1. 把 lisprolog 的 Lisp 代码跑起来
2. 用 trace 跟踪 eval/2 的调用链
3. 理解每个 Lisp 形式如何对应到 Prolog 子句
4. 尝试加一个自定义原始函数

去 https://github.com/triska/lisprolog 看源码。 在 SWI-Prolog 中 use_module(lisprolog)，然后 lisp("(+ 1 2)").

1.10. 参考

• The Power of Prolog — Meta-interpreters
• The Power of Prolog — DCGs