Prolog: "chili"表示调用堆栈和选择点的解释器

Question

通常的普通解释器使用 Prolog 回溯 本身进行归档倒缝。我想这就是原因 为什么它被称为“ Vanilla ”:

solve(true).
solve((A,B)) :- solve(A), solve(B).
solve(H) :- clause(H, B), solve(B).

一个不使用任何内容的“chili”解释器怎么样？ Prolog 回溯。基本上是一个谓词 first/? 来获取 第一个解决方案和谓词 next/? 以获得进一步的解决方案。

如何在 Prolog 中实现这样一个解释器。解决方案不需要是纯粹的，也可以使用 findall 和 cut。尽管更纯粹的解决方案也可以说明问题。

Answer 1

这个解决方案是 Markus Triska 的 A Couple of Meta-interpreters in Prolog 中给出的解释器的一个稍微简化的版本。 (Prolog 的力量的一部分)具体化回溯。它有点冗长且效率较低，但可能比该代码更容易理解。

first(Goal, Answer, Choices) :-
    body_append(Goal, [], Goals),
    next([Goals-Goal], Answer, Choices).

next([Goals-Query|Choices0], Answer, Choices) :-
    next(Goals, Query, Answer, Choices0, Choices).

next([], Answer, Answer, Choices, Choices).
next([Goal|Goals0], Query, Answer, Choices0, Choices) :-
    findall(Goals-Query, clause_append(Goal, Goals0, Goals), Choices1),
    append(Choices1, Choices0, Choices2),
    next(Choices2, Answer, Choices).

clause_append(Goal, Goals0, Goals) :-
    clause(Goal, Body),
    body_append(Body, Goals0, Goals).

body_append((A, B), List0, List) :-
    !,
    body_append(B, List0, List1),
    body_append(A, List1, List).
body_append(true, List, List) :-
    !.
body_append(A, As, [A|As]).

这个想法是，Prolog 引擎状态被表示为一个析取的Choices列表，扮演着选择点堆栈的角色。每个选择的形式都是Goals-Query，其中Goals是仍待满足的目标的联合列表，即SLD树的该节点处的解决方案，并且Query 是原始查询项的一个实例，其变量已根据通向该节点的路径中进行的统一进行实例化。

如果选项的解析变为空，则其 Query 实例化将作为 Answer 返回，然后我们继续其他选择。请注意，当没有找到目标子句时，即“失败”，Choices1 与 [] 统一，我们通过继续执行 中的剩余选择来“回溯” >选择0。另请注意，当列表中没有选择时，next/3 会失败。

示例 session :

?- assertz(mem(X, [X|_])), assertz(mem(X, [_|Xs]) :- mem(X, Xs)).
true.

?- first(mem(X, [1, 2, 3]), A0, S0), next(S0, A1, S1), next(S1, A2, S2).
A0 = mem(1, [1, 2, 3]),
S0 = [[mem(_G507, [2, 3])]-mem(_G507, [1, 2, 3])],
A1 = mem(2, [1, 2, 3]),
S1 = [[mem(_G579, [3])]-mem(_G579, [1, 2, 3])],
A2 = mem(3, [1, 2, 3]),
S2 = [[mem(_G651, [])]-mem(_G651, [1, 2, 3])].

这种方法的问题在于，findall/3 会大量复制解析结果，即要在析取分支中证明的目标的剩余合取。我希望看到一种更有效的解决方案，可以更巧妙地复制术语和共享变量。