Meta-interpreters
Write Prolog in Prolog: inspect, trace and extend the language itself.
Because programs are data (clauses are terms), you can write a Prolog interpreter in Prolog in four lines. This is not just a curiosity: meta-interpreters are how people build debuggers, explanation facilities, alternative search strategies, and new logic languages.
The built-in clause(Head, Body) retrieves the clauses of a predicate. Here is a database to interpret:
parent(tom, bob).
parent(bob, ann).
parent(bob, pat).
ancestor(X, Y) :- parent(X, Y).
ancestor(X, Y) :- parent(X, Z), ancestor(Z, Y).?- clause(ancestor(A, B), Body)clause/2 returns each rule's body, here a fact has body true, and a conjunction is the term (A, B).
The vanilla meta-interpreter
solve(Goal) proves a goal by looking at its shape:
solve(true) :- !.
solve((A, B)) :- !, solve(A), solve(B).
solve(G) :- predicate_property(G, built_in), !, call(G). % arithmetic, comparison, ...
solve(G) :- clause(G, Body), solve(Body). % user-defined: resolve against a clause?- solve(ancestor(tom, Who))?- solve((parent(X, Y), Y \= ann))It behaves exactly like the real thing. The point is that now we control how goals are proven. Let's exploit that.
Adding a proof tree
A proof is: for a fact, the fact; for a rule, the head together with the proofs of its body. Add one argument to build it:
prove(true, true) :- !.
prove((A, B), (PA, PB)) :- !, prove(A, PA), prove(B, PB).
prove(G, built_in(G)) :- predicate_property(G, built_in), !, call(G).
prove(G, G-Proof) :- clause(G, Body), prove(Body, Proof).?- prove(ancestor(tom, ann), Proof)That is the explanation of why ancestor(tom, ann) holds: tom is a parent of bob, and bob is an ancestor of ann because bob is a parent of ann. Expert systems use this to answer "why?".
Controlling the search: depth limits
Left recursion makes ordinary Prolog diverge. An interpreter can count depth and cut off:
% solve_depth(Goal, MaxDepth): prove Goal using proofs at most MaxDepth calls deep
solve_depth(true, _) :- !.
solve_depth((A, B), D) :- !, solve_depth(A, D), solve_depth(B, D).
solve_depth(G, _) :- predicate_property(G, built_in), !, call(G).
solve_depth(G, D) :- D > 0, D1 is D - 1, clause(G, Body), solve_depth(Body, D1).
% a bad, left-recursive definition
reach(X, Y) :- reach(X, Z), parent(Z, Y).
reach(X, Y) :- parent(X, Y).?- solve_depth(reach(tom, Y), 5)Where plain Prolog would loop forever, the bounded interpreter returns every answer within the depth bound (some more than once, because it explores the branches multiple times). With iterative deepening, retry with depth 1, 2, 3…, you get a complete search strategy.
Metainterpreters
An interpreter is a program that reads and executes another program. A metainterpreter is an interpreter written in the same language as the program to be interpreted: typically, you do so to be able to enact some change on the interpretation strategy. In Prolog this is actually somewhat easy, since programs are just terms (data), and it is easy to perform "resolution"-like mechanisms that substitute heads with bodies.
Applications: for Prolog programmers, debugging, profiling and changing the resolution strategy; in AI planning and similar, to perform ad-hoc "space exploration" on your DSL.
A preliminary step: simulating resolution
File resolution.pl. The program is represented as rule/2 facts: the head, and the list of body goals. We use unification when calling rule/2, we branch because calling rule/2 branches, and append performs the head/body substitution:
rule(a, []). % means: a.
rule(b, []). % means: b.
rule(d, []). % means: d.
rule(d, []). % means: d.
rule(c, []). % means: c.
rule(c, [c]). % means: c :- c.
solve([]).
solve([Goal | Rest]) :-
rule(Goal, Body),
append(Body, Rest, NewGoals),
solve(NewGoals).?- solve([a])?- solve([d])?- solve([e])?- solve([c])solve([a]) succeeds once, solve([d]) twice (two facts), solve([e]) fails, and solve([c]) has infinitely many answers (yes; yes; yes; ...), through the recursive rule c :- c.
It is actual "full resolution"!
File full-resolution.pl. The very same solve/1, with a search/2 predicate added as rule/2 facts:
rule(a, []).
rule(b, []).
rule(d, []).
rule(d, []).
rule(c, []).
rule(c, [c]).
solve([]).
solve([Goal | Rest]) :-
rule(Goal, Body),
append(Body, Rest, NewGoals),
solve(NewGoals).
rule(search(E, [E|_]), []).
rule(search(E, [_|T]), [search(E, T)]).?- solve([search(X, [10, 20, 30])])It works! A real search predicate, with real unification and backtracking, in about five lines. We just now need to digest standard Prolog clauses. (Loading this file prints a harmless warning: the clauses of rule/2 are not together, since the search rules come after solve/1.)
The vanilla metainterpreter
File vanilla.pl. It reads the program's own clauses through clause/2: clause(G, B) gives, for a goal G, the body B of a matching clause (true for a fact):
solveV(true) :- !.
solveV((A, B)) :- !, solveV(A), solveV(B).
solveV(G) :- clause(G, B), solveV(B).
search(E, [E|_]).
search(E, [_|T]) :- search(E, T).?- solveV(search(X, [10, 20, 30]))Defects... or features? It cannot deal with built-in library predicates (not defined by clauses), and control predicates must be "re-implemented" in the metainterpreter if needed. This might be considered a feature, since it allows you to pick what to use explicitly.
Metainterpretation with built-ins and control
File builtins-control.pl. solveB handles built-ins one by one (each is called as such) and one control predicate at a time (once/1, not/1):
solveB(true) :- !.
solveB((A, B)) :- !, solveB(A), solveB(B).
solveB(X is E) :- !, X is E. % built-ins, one by one
solveB(X = Y) :- !, X = Y.
solveB(X \= Y) :- !, X \= Y.
solveB(X == Y) :- !, X == Y. % possibly more
solveB(once(G)) :- !, once(solveB(G)). % handling once/1
solveB(not(G)) :- !, not(solveB(G)). % handling not/1
solveB(G) :- clause(G, B), solveB(B).
sum([], 0).
sum([H|T], N) :- sum(T, N2), N is N2 + H.?- solveB(sum([10, 20, 30], S))?- solveB(not(sum([10, 20, 30], 50)))?- solveB(not(sum([10, 20, 30], 60)))Notes: rules 3 to 6 deal with built-ins, each called as such; rules 7 and 8 deal with one control predicate at a time. Challenge for you: how to implement the cut?
Altering the order of solutions
File reverse-order.pl. solveI collects all the matching clauses with findall, reverses them, and then tries them: solutions come in reverse order.
solveI(true) :- !.
solveI((A, B)) :- !, solveI(A), solveI(B).
solveI(G) :-
findall(c(G, B), clause(G, B), L),
reverse(L, L2), % inverting solutions!!
member(c(G, B), L2),
solveI(B).
% search/2 is repeated from vanilla.pl
search(E, [E|_]).
search(E, [_|T]) :- search(E, T).?- solveI(search(X, [10, 20, 30]))This general approach can be used to collect "branches", analyse them, and decide what to prioritise and/or discard.
Tracking and constraining computations
File trace-bound.pl. solveT(+Goal, -Trace, -SizeBound) returns the solution along with the whole computation trace, and refuses to go deeper than the size bound: useful for debugging, or for constraining computations, e.g. pruning long computations.
% solveT(+Goal, -Trace, -SizeBound)
solveT(G, T, B) :- solveT(G, T, B, _).
solveT(true, [], N, N) :- !.
solveT((A, B), L, IN, ON) :- !,
solveT(A, LA, IN, ON1),
findall((X, B), member(X, LA), LL),
solveT(B, LB, ON1, ON),
append(LL, LB, L).
solveT(G, [G|T], I, O) :-
I > 0, !, clause(G, B), I2 is I-1, solveT(B, T, I2, O).
% search/2 is repeated from vanilla.pl
search(E, [E|_]).
search(E, [_|T]) :- search(E, T).?- solveT(search(X, [10, 20, 30]), T, 2)With a bound of 2, only the solutions found within two resolution steps are produced: 10 after one, 20 after two; 30 would need three, so it is cut off, and the query ends with no. Each answer carries its trace: the sequence of goals that were resolved.
Exercise: Count the steps
Complete the interpreter solve(Goal, N) so that N is the number of user-defined clauses used in the proof (built-ins are free). The true and built-in cases are given, mind the order of clauses. The family program is loaded.
Examples: solve(parent(tom, bob), N) gives N = 1; solve(ancestor(tom, ann), N) gives N = 4.