这是一个使用一点阻塞编程风格的解决方案。它不使用when/2,而仅使用freeze/2。有一个谓词 expr/2 检查某事物是否是一个没有任何闭包的正确表达式:
expr(X) :- freeze(X, expr2(X)).
expr2([X|Y]) :-
expr(X),
expr(Y).
expr2(quote).
expr2([]).
expr2(cons).
expr2(lambda).
expr2(symbol(_)).
然后再次使用 freeze/2 进行查找谓词,
以等待环境列表。
lookup(S, E, R) :- freeze(E, lookup2(S, E, R)).
lookup2(S, [S-T|_], R) :-
unify_with_occurs_check(T, R).
lookup2(S, [T-_|E], R) :-
dif(S, T),
lookup(S, E, R).
最后是使用 DCG 编码的评估器,
用于限制 cons 的总数并应用调用:
eval([quote,X], _, X) --> [].
eval([], _, []) --> [].
eval([cons,X,Y], E, [A|B]) -->
step,
eval(X, E, A),
eval(Y, E, B).
eval([lambda,symbol(X),B], E, closure(X,B,E)) --> [].
eval([X,Y], E, R) -->
step,
eval(X, E, closure(Z,B,F)),
eval(Y, E, A),
eval(B, [Z-A|F], R).
eval(symbol(S), E, R) -->
{lookup(S, E, R)}.
step, [C] --> [D], {D > 0, C is D-1}.
主谓词逐渐增加允许的
cons 和应用调用的数量:
quine(Q, M, N) :-
expr(Q),
between(0, M, N),
eval(Q, [], P, [N], _),
unify_with_occurs_check(Q, P).
此查询显示 5 个 cons 和 apply 调用足以生成 Quine。在 SICStus Prolog 和 Jekejeke Prolog 中工作。对于 SWI-Prolog 需要使用例如这个unify/2解决方法:
?- dif(Q, []), quine(Q, 6, N).
Q = [[lambda, symbol(_Q), [cons, symbol(_Q), [cons, [cons,
[quote, quote], [cons, symbol(_Q), [quote, []]]], [quote,
[]]]]], [quote, [lambda, symbol(_Q), [cons, symbol(_Q), [cons,
[cons, [quote, quote], [cons, symbol(_Q), [quote, []]]],
[quote, []]]]]]],
N = 5
我们可以手动验证它确实是一个非平凡的 Quine:
?- Q = [[lambda, symbol(_Q), [cons, symbol(_Q), [cons, [cons,
[quote, quote], [cons, symbol(_Q), [quote, []]]], [quote,
[]]]]], [quote, [lambda, symbol(_Q), [cons, symbol(_Q), [cons,
[cons, [quote, quote], [cons, symbol(_Q), [quote, []]]],
[quote, []]]]]]], eval(Q, [], P, [5], _).
Q = [[lambda, symbol(_Q), [cons, symbol(_Q), [cons, [cons,
[quote, quote], [cons, symbol(_Q), [quote, []]]], [quote,
[]]]]], [quote, [lambda, symbol(_Q), [cons, symbol(_Q), [cons,
[cons, [quote, quote], [cons, symbol(_Q), [quote, []]]],
[quote, []]]]]]],
P = [[lambda, symbol(_Q), [cons, symbol(_Q), [cons, [cons,
[quote, quote], [cons, symbol(_Q), [quote, []]]], [quote,
[]]]]], [quote, [lambda, symbol(_Q), [cons, symbol(_Q), [cons,
[cons, [quote, quote], [cons, symbol(_Q), [quote, []]]],
[quote, []]]]]]]