I wonder whether there is a pure Prolog meta-interpreter with only one rule. The usual Prolog vanilla meta-interpreter has two rules. It reads as follows:
solve(true).
solve((A, B)) :- solve(A), solve(B). /* rule 1 */
solve(H) :- program(H, B), solve(B). /* rule 2 */
This Prolog vanilla meta-interpreter uses two rules /* rule 1 */
and /* rule 2 */. And the rest is facts. The program that
is executed is represented by program facts. Here is an example program:
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))).
And an example query:
?- solve(nrev([1,2,3], X)).
X = [3, 2, 1] .
Is there a way to represent the program differently as facts, and then code a different meta-interpreter, which would use only facts except for a single rule instead of two rules? Something that would work for all pure Prolog programs, not only the nrev example?
Here is one idea, using a list to hold the rest of the computation:
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).
With test call (where one needs to wrap the call in a list).
?- solve([nrev([1,2,3],X)]).
X = [3,2,1] ? ;
no
Arguably, one could represent the program/3 facts as a DCG instead, for increased readability (but then it might not be considered a "fact" any more).