Skip to content
Tutorials Center
My learning

Topics

Lesson 35 of 40 ยท Applications

Meta-Interpreters and Expert Systems

Write a Prolog interpreter in three lines with clause/2, extend it to build proof trees and count depth, then build a rule-based expert system that asks questions and explains its reasoning.

Prolog programs are also Prolog data: a clause is just a term, and the program can inspect other clauses with clause/2. This makes it remarkably easy to write an interpreter for Prolog in Prolog, called a meta-interpreter. Meta-interpreters are the traditional route to expert systems: programs that reason from a knowledge base of rules, ask the user for missing facts and explain their conclusions. This lesson builds both, step by step.

Prolog is not available on this site, so the examples run on the stand-in interpreter (a Python program that supports facts, rules, clause/2, assertion and the cut). The programs themselves are ordinary Prolog.

The vanilla meta-interpreter

To prove a goal, there are three cases: the goal is true; the goal is a conjunction, so prove both parts; or the goal is a user predicate, so find a clause for it and prove the clause body.

PROLOG
solve(true).
solve((A, B)) :- solve(A), solve(B).
solve(Goal)   :- clause(Goal, Body), solve(Body).

clause(Head, Body) unifies Head and Body with a clause in the database; a fact has the body true. Prolog's own backtracking, unification and variable handling do all the work, so the interpreter needs no machinery of its own. That is why it is called vanilla: it is the plain, smallest version.

Built-in predicates such as is/2 and >/2 have no clauses to inspect, so they must be called directly. In SWI-Prolog you can test with predicate_property(Goal, built_in):

PROLOG
solve(Goal) :-
    predicate_property(Goal, built_in), !,
    call(Goal).

Put that clause before the one using clause/2; calling clause/2 on a built-in raises a permission error. The stand-in interpreter has no predicate_property/2, so the demo below lists the built-ins it needs in an is_builtin/1 table instead.

Why bother? Extending the interpreter

Because the interpreter is a Prolog program, you can change what "proving" means by adding an argument:

Extension What it adds
a proof argument returns a proof tree explaining why a goal holds
a depth counter measures proof depth, or stops runaway recursion with a limit
a counter counts inferences (a profiler)
a print statement a custom tracer
a certainty value multiplies confidence factors through the proof
a goal reordering step tries a cheaper goal first

The proof-tree version is a three-line change:

PROLOG
prove(true, true).
prove((A, B), (PA, PB)) :- prove(A, PA), prove(B, PB).
prove(Goal, proof(Goal, Proof)) :- clause(Goal, Body), prove(Body, Proof).

The second argument records, for every goal, the proof of the clause body that justified it. That tree is the explanation that an expert system shows to its user.

Python Vanilla meta-interpreter, proofs and depth (Python stand-in interpreter)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The proof for ancestor(tom, ann) reads: it holds because parent(tom, bob) is a fact and ancestor(bob, ann) holds, and that in turn holds because parent(bob, ann) is a fact. The meta-interpreter returns this as a nested term you can print, store or render as a tree.

Limits of the vanilla version. It does not handle the cut correctly (a cut inside an interpreted clause would cut the interpreter's clause, not the program's), nor negation, if-then-else or built-ins that manipulate the database. Those need extra clauses, each written with care. Meta-interpreters are an excellent tool for DSLs and explanation, and a poor tool for general speed: interpreting costs several times a direct call.

Expert systems

An expert system has four parts, which is also a nice way to organize a Prolog program:

Parts of an expert system

Knowledge base Rules written as facts and clauses.
Inference engine Chains rules to reach a conclusion.
Dialogue Asks the user for missing facts.
Explanation Shows how a conclusion was reached.

Prolog supplies the inference engine for free.

1 / 2

The most natural style in Prolog is backward chaining: to prove a hypothesis, find a rule that concludes it and prove each condition in turn. Conditions that no rule can derive are askable: the system asks the user and remembers the answer, so no question is ever asked twice.

A small car-troubleshooting system makes this concrete. The rules are data, as rule(Conclusion, Conditions):

PROLOG
rule(dead_battery,  [no_lights, no_click]).
rule(starter_fault, [click, no_start]).
rule(out_of_fuel,   [engine_cranks, fuel_gauge_empty]).

askable(no_lights).  askable(no_click).  askable(click).
askable(no_start).   askable(engine_cranks).  askable(fuel_gauge_empty).

The engine is short:

PROLOG
:- dynamic known/2.

holds(Fact) :- rule(Fact, Conditions), all_hold(Conditions).
holds(Fact) :- askable(Fact), ask(Fact).

all_hold([]).
all_hold([C|Cs]) :- holds(C), all_hold(Cs).

ask(Fact) :- known(Fact, Answer), !, Answer = yes.
ask(Fact) :-
    format("Is this true: ~w? (yes/no) ", [Fact]),
    read(Answer),
    assertz(known(Fact, Answer)),
    Answer = yes.

diagnose(D) :- rule(D, _), holds(D).

holds/1 first tries to derive the fact from a rule, then asks the user if the fact is askable. ask/1 checks the memory known/2 first (the cut makes the first clause final), and otherwise reads an answer and stores it with assertz/1, the dynamic database at work. Backtracking into diagnose/1 finds further explanations while reusing recorded answers.

The stand-in cannot read from a keyboard, so the demo replaces the user with script/2 facts that hold prepared answers. Everything else is the same program.

Python A tiny diagnostic expert system (Python stand-in interpreter)

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The first answer is dead_battery, after two questions. The system did not ask about fuel_gauge_empty for that answer, because the first rule was enough. Only when the search continues (more answers requested) does it ask about the other rules, and each answer is stored in known/2.

Adding explanation and uncertainty

Combine the two halves of this lesson to make the system explain itself. A how/2 explanation prints the proof tree of the conclusion, and a why explanation shows the rule that is currently being tried when the system asks a question. Real systems usually attach a certainty factor to each fact and rule. The meta-interpreter then multiplies the factors along the proof: a conclusion supported by a rule of confidence 0.9 and conditions at 0.8 and 0.5 gets 0.9 * min(0.8, 0.5) = 0.45, for example. The structure stays the same; only the arithmetic changes.

Forward chaining works the other way: starting from the known facts, fire every rule whose conditions hold, assert its conclusion, and repeat until nothing new appears. It is a good fit when facts arrive continuously (monitoring, configuration), and it is written with assertz/1 and a failure-driven loop over rules.

Common mistakes

  • Using clause/2 on built-ins or library predicates; it raises a permission error. Test for built-ins first.
  • Forgetting that cuts and negation need their own meta-interpreter clauses.
  • Asking the same question twice because the answer was not recorded; store answers with assertz/1.
  • Writing rules in the knowledge base as clauses when they should be data (rule/2 facts); data is much easier to inspect, explain and edit.
  • Mixing the knowledge and the engine in one file when domain experts need to maintain the rules separately.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. What does clause(Head, Body) do?

    clause/2 inspects the clauses of a predicate; facts have the body true.
  2. 2. Why is a meta-interpreter easy to write in Prolog?

    The three-clause interpreter reuses the host system's search and unification.
  3. 3. In the expert system, why does ask/1 start with known(Fact, Answer), !?

    If the answer is already known, the cut commits to it, so the second clause never asks.
  4. 4. Which reasoning style does Prolog's execution model naturally use?

    To prove a goal Prolog looks for clauses concluding it and then proves their conditions.

Summary

  • solve(true). solve((A,B)) :- ... . solve(G) :- clause(G, B), solve(B). is a complete vanilla meta-interpreter.
  • Extra arguments turn it into a proof-tree builder, depth counter, tracer or certainty calculator.
  • An expert system is a rule base, an inference engine (backward chaining), a dialogue that asks for missing facts and an explanation facility.
  • Store answers with assertz/1; keep rules as data (rule/2).
  • Vanilla interpreters do not handle cut or negation without extra clauses.

Next: Tabling and Performance