% A Prolog interpreter written in Prolog
% Taken from Musa's cheatsheet.

interpret(true) :-
    format('Done\n'),
    !.

interpret(fail) :-
    format('Failed\n'),
    !, fail.

interpret((G , H)) :-
    format('Attempting to prove ~w and ~w\n', [G, H]),
    !, interpret(G), interpret(H).

interpret((G ; H)) :-
    format('Attempting to prove ~w or ~w\n', [G, H]),
    !, interpret(G); interpret(H).

interpret((\+ G)) :-
    format('Attempting to prove not ~w\n', G),
    !, \+ interpret(G).

interpret(Goal) :-
    format('Searching for clauses of ~w\n', Goal),
    % Find a clause
    clause(Goal,Subgoals),
    format('Found goal ~w\n', Subgoals),
    % Try to prove the goals of the clause
    interpret(Subgoals).


% A small graph
edge(a,b).
edge(b,c).
edge(a,d).

/*

  a ---> b ---> c
  |
  |
  v
  d

*/

% path is the reflexive transitive closure of edge
path(X,X).
path(X,Y) :- edge(X,Z), path(Z,Y).

% Two points are connected if there's a path between them,
% or if we can find two paths which “meet in the middle”.
connected(X,Y) :- path(X,Y);
		  path(Z,X), path(Z,Y);
		  path(X,Z), path(Y,Z).



% THIS IS A BAD GRAPH
% DEPTH FIRST SEARCHES WILL FAIL
family(alice,bob).
family(alice,charlie).

family(X,X).
family(X,Y) :- family(X,Z), family(Z,Y).
family(X,Y) :- family(Y,X).