%	Production system interpreter.

%	The arrow operator is defined as --> on the 70's but ==> on the VAX

op(900, xfx, ==>)!

%	The main interpreter loop is implemented by repeated backtracking.
%	Each cycle consists of a matching phases in which we find out which
%	rules can fire. If there is more than one way for a rule to match
%	data (due to different variable bindings) then all instances of the
%	rule are fired.
%	After finding all the rules, delete the antecedents and add the
%	consequents.

interpret :-
	repeat,
	match(Rules),
	delete_antecedents(Rules),
	add_consequents(Rules),
	Rules = [],
	!.

%	Match will return a list of all instances of rules which can fire in
%	a particular cycle.

match(Rules) :-
	bagof(Rule, can_fire(Rule), Rules).

%	To find out if a rule can fire, make sure that each condition on
%	the left hand side of a rule matches a fact in working memory.

can_fire(A ==> B) :-
	A ==> B,
	satisfied(A).

satisfied(A & B) :- !,
	A,
	satisfied(B).
satisfied(A) :- A.

%	Scan through all the rules, deleting conditions in antecedent.

delete_antecedents([Antecedent ==> _ | Rest]) :- !,
	delete(Antecedent),
	delete_antecedents(Rest).
delete_antecedents([]).

%	Delete the first condition and then delete rest.

delete(A & B) :- !,
	retract_conditional(A),
	delete(B).
delete(A) :- retract_conditional(A).

%	Don't try to delete a condition if it is not in database.
%	It may have been removed by another rule in this cycle.

retract_conditional(A) :- A, !, retract(A).
retract_conditional(A).

%	Scan through firing rules to add consequent to database.

add_consequents([_ ==> Consequent | Rest]) :- !,
	add(Consequent),
	add_consequents(Rest).
add_consequents([]).

add(A & B) :- !,
	assert_conditional(A),
	add(B).
add(A) :- assert_conditional(A).

%	Don't add a fact if it is already in the database.

assert_conditional(A) :- A, !.
assert_conditional(A) :- assert(A).

% Rule Memory

a & b ==> c & d.

c(X) ==> e(X).

e(X) & f ==> g.

g & d ==> h.

a & p ==> q.

% Working Memory

a.

b.

f.

p.

c(a).

c(b).
