纯Prolog元解释器

Question

我想知道是否有一个纯Prolog元解释器，只有一个规则。通常的Prolog香草元解释器有两个规则。其内容如下：

solve(true).
solve((A, B)) :- solve(A), solve(B). /* rule 1 */
solve(H) :- program(H, B), solve(B). /* rule 2 */

这个Prolog香草元解释器使用了两个规则/* rule 1 */和/* rule 2 */。剩下的就是事实。所执行的程序由程序事实表示。下面是一个示例程序：

program(append([], X, X), true).
program(append([X|Y], Z, [X|T]), append(Y, Z, T)).
program(nrev([], []), true).
program(nrev([H|T], R), (nrev(T, S), append(S, [H], R))).

还有一个示例查询：

?- solve(nrev([1,2,3], X)).
X = [3, 2, 1] .

是否有一种方法以不同的方式将程序表示为事实，然后编写不同的元解释器，它将只使用事实，而不是使用单个规则而不是两条规则？对所有纯Prolog程序都有效的东西，而不仅仅是nrev示例？

Answer 1

这里有一个想法，使用一个列表来保存计算的其余部分：

solve([]).
solve([X|Xs]) :- program(X, Ys, Xs), solve(Ys).

program(true, Xs, Xs).
program(append([],X,X), Xs, Xs).
program(append([X|Y], Z, [X|T]), [append(Y,Z,T)|Xs], Xs).
program(nrev([],[]), Xs, Xs).
program(nrev([H|T],R), [nrev(T,S),append(S,[H],R)|Xs], Xs).

使用测试调用(需要将调用包装在列表中)。

?- solve([nrev([1,2,3],X)]).
X = [3,2,1] ? ;
no

可以说，为了增加可读性，可以将程序/3事实表示为DCG (但这样就不再被认为是“事实”了)。

Answer 2

这是另一种方法，称为带延续的二进制化。

它是从这个逻辑变压器纸这里保罗塔罗(2021年)。

solve(true).
solve(X) :- program(X, Y), solve(Y).

program(append([],X,X,C), C).
program(append([X|Y],Z,[X|T],C), append(Y,Z,T,C)).
program(nrev([],[],C), C).
program(nrev([H|T],R,C), nrev(T,S,append(S,[H],R,C))).

一次小小的理智检查表明：

?- solve(nrev([1,2,3], X, true)).
X = [3, 2, 1] ;
No

Answer 3

如果允许使用;/2，那么这似乎是可行的：

solve(true).
solve(H) :- ((X, Y) = H, solve(X), solve(Y)); (program(H :- B), solve(B)).

program(append([], X, X) :- true).
program(append([X|Y], Z, [X|T]) :- append(Y, Z, T)).
program(nrev([], []) :- true).
program(nrev([H|T], R) :- (nrev(T, S), append(S, [H], R))).

测试：

?- solve(nrev([1,2,3], X)).
X = [3, 2, 1] ;
false.