序言：“辣椒”表示呼叫堆栈和选择点的解释器 [英] Prolog: "chili" interpreter that expresses call stack and choice points

问题描述

通常的普通解释器使用Prolog回溯
本身来归档回溯。我想这就是
被称为香草的原因：

The usual vanilla interpreter uses Prolog backtracking itself to archive backtacking. I guess this is the reason why its called "vanilla":

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

不使用任何
Prolog回溯的辣椒解释器如何。基本上，谓词 first /？获得第一个解决方案
，而谓词 next /？获得进一步的解决方案。

How about a "chili" interpreter, that doesn't use any Prolog backtracking. Basically a predicate first/? to obtain a first solution and a predicate next/? to obtain further solutions.

在Prolog中，人们将如何实现它并实现这样的解释器。解决方案不必是纯粹的，也可以使用findall和cut。虽然更纯净的解决方案也可以说明问题。

How would one go about it and realize such an interpreter in Prolog. The solution needs not be pure, could also use findall and cut. Although a purer solution could be also illustrative.

推荐答案

此解决方案是Markus Triska的解释器中的一个稍作简化的版本。 Prolog中的几个元解释器（ Prolog的力量 >）下的修正回溯。它比该代码更冗长，效率更低，但可能比该代码更容易理解。

This solution is a slightly dumbed-down version of the interpreter given in Markus Triska's A Couple of Meta-interpreters in Prolog (part of The Power of Prolog) under Reifying backtracking. It is a bit more verbose and less efficient, but possibly a bit more immediately understandable than that code.

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引擎状态表示为分离的列表选择，扮演一堆选择点的角色。每个选择的格式为 Goals-Query ，其中 Goals 是需要满足的目标的联合清单，即SLD树的那个节点处的解析器，而 Query 是原始查询项的实例，其查询变量已根据导致该查询的路径中的统一实例化

The idea is that the Prolog engine state is represented as a list of disjunctive Choices, playing the role of a stack of choice points. Each choice is of the form Goals-Query, where Goals is a conjunctive list of goals still to be satisfied, i.e. the resolvent at that node of the SLD tree, and Query is an instance of the original query term whose variables have been instantiated according to the unifications made in the path leading up to that node.

如果选择的解决方案为空，则其 Query 实例化为答案，我们继续其他选择。请注意，如何在找不到目标的子句时，即失败， Choices1 与 [] 统一，我们进行 Choices0 中的其余选择来进行回溯。还要注意，当列表中没有选择时， next / 3 失败。

If the resolvent of a choice becomes empty, it's Query instantiation is returned as an Answer and we continue with other choices. Note how when no clauses are found for a goal, i.e. it "fails", Choices1 unifies with [] and we "backtrack" by proceeding through the remaining choices in Choices0. Also note that when there are no choices in the list, next/3 fails.

示例会话：

?- 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 做很多分解体的复制，即要在分离分支中证明的目标的剩余并集。我希望看到一种更有效的解决方案，在该解决方案中可以复制术语并更巧妙地共享变量。

The problem with this approach is that findall/3 does a lot of copying of the resolvent i.e. the remaining conjunction of goals to be proved in a disjunctive branch. I would love to see a more efficient solution where terms are copied and variables shared more cleverly.

这篇关于序言：“辣椒”表示呼叫堆栈和选择点的解释器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！