% file: m3.pro
% author: Robert Keller
% purpose: Predicate m3 succeeds exactly for lists of 1's and 0's
%          that represent multiples of 3 in binary, most-significant bit first.
%          By convention, the empty list is considered a multiple of 3.
%
% In effect, m3 simulates a 3-state machine, with state m3 being both 
% the initial state and the only accepting state.
%
% m3 calls upon helper predicates m1 and m2, which simulate from other
% states of the machine.

% m3(X).

m3([]).

m3([0 | X]) :- m3(X).
m3([1 | X]) :- m1(X).

m1([0 | X]) :- m2(X).
m1([1 | X]) :- m3(X).

m2([0 | X]) :- m1(X).
m2([1 | X]) :- m2(X).

% Tests for numbers divisible by 3.

test(0) :- m3([0]).
test(3) :- m3([1, 1]).
test(6) :- m3([1, 1, 0]).
test(9) :- m3([1, 0, 0, 1]).
test(12) :- m3([1, 1, 0, 0]).

% Tests for numbers not divisible by 3.

test(1) :- \+ m3([1]).
test(2) :- \+ m3([1, 0]).
test(4) :- \+ m3([1, 0, 0]).
test(5) :- \+ m3([1, 0, 1]).
test(7) :- \+ m3([1, 1, 1]).
test(8) :- \+ m3([1, 0, 0, 0]).
test(10) :- \+ m3([1, 0, 1, 0]).
test(11) :- \+ m3([1, 0, 1, 1]).


% testDriver(N) runs test(N) and reports the results.

testDriver(N) :- test(N) -> (write('Test '), write(N), write(' succeeded'), nl) ; 
                            (write('Test '), write(N), write(' failed'), nl).


% enum(M, N, K) binds K to numbers from M through N, one at a time.

enum(M, N, M) :- M =< N.
enum(M, N, K) :- M < N, M1 is M+1, enum(M1, N, K).


% testall runs the available tests.

testall :- enum(1, 12, K), testDriver(K), fail.
testall.