boyer.pl

contents

%query: tautology(i).

/*-----------------------------------------------------------------------------
Program: Boyer (toy theorem prover)
Author:  E. Tick (after Lisp by R. Boyer)
Date:    November 12 1985

Notes:
1. To run:
        ?- go(X).
where X is output execution time.

-----------------------------------------------------------------------------*/

%:- module(boyer, [go/1]).
%:- entry(tautology(g)).

tautology(Wff) :-
    write('rewriting...'),nl,
    rewrite(Wff,NewWff),
    write('proving...'),nl,
    tautology(NewWff,[],[]).

tautology(Wff,Tlist,Flist) :-
    (truep(Wff,Tlist) -> true
    ;falsep(Wff,Flist) -> fail
    ;Wff = if(If,Then,Else) ->
        (truep(If,Tlist) -> tautology(Then,Tlist,Flist)
        ;falsep(If,Flist) -> tautology(Else,Tlist,Flist)
        ;tautology(Then,[If|Tlist],Flist),
         tautology(Else,Tlist,[If|Flist])
        )
    ),!.

rewrite(Atom,Atom) :-
    atomic(Atom),!.
rewrite(Old,New) :-
    functor(Old,F,N),
    functor(Mid,F,N),
    rewrite_args(N,Old,Mid),
    ( equal(Mid,Next) ->
      rewrite(Next,New)
    ; New=Mid
    ),!.

rewrite_args(0,_,_) :- !.
rewrite_args(N,Old,Mid) :-
    arg(N,Old,OldArg),
    arg(N,Mid,MidArg),
    rewrite(OldArg,MidArg),
    N1 is N-1,
    rewrite_args(N1,Old,Mid).

truep(t,_) :- !.
truep(Wff,Tlist) :- member(Wff,Tlist).

falsep(f,_) :- !.
falsep(Wff,Flist) :- member(Wff,Flist).

member(X,[X|_]) :- !.
member(X,[_|T]) :- member(X,T).


% should be 106 rules
% but there are only 59
equal(    and(P,Q),
    if(P,if(Q,t,f),f)
    ).
equal(    append(append(X,Y),Z),
    append(X,append(Y,Z))
    ).
equal(    assignment(X,append(A,B)),
    if(assignedp(X,A),
       assignment(X,A),
       assignment(X,B))
    ).
equal(    assume_false(Var,Alist),
    cons(cons(Var,f),Alist)
    ).
equal(    assume_true(Var,Alist),
    cons(cons(Var,t),Alist)
    ).
equal(    boolean(X),
    or(equal(X,t),equal(X,f))
    ).
equal(    car(gopher(X)),
    if(listp(X),
       car(flatten(X)),
       zero)
    ).
equal(    compile(Form),
    reverse(codegen(optimize(Form),[]))
    ).
equal(    count_list(Z,sort_lp(X,Y)),
    plus(count_list(Z,X),
         count_list(Z,Y))
    ).
equal(    countps_(L,Pred),
          countps_loop(L,Pred,zero)
    ).

content may be truncated. 'popout' for larger text window.