Skip to content

Instantly share code, notes, and snippets.

@ejamesc
Created September 14, 2011 00:13
Show Gist options
  • Save ejamesc/1215533 to your computer and use it in GitHub Desktop.
Save ejamesc/1215533 to your computer and use it in GitHub Desktop.
Incomplete, slightly buggy algebraic simplification in Prolog
simplify(X,Res) :- simple(X,Z), simple(Z,Res), !.
simple(X,X) :- atomic(X), ! .
simple(In, Res) :- In =.. [Ope, A],
simple(A, C), unary(Ope,C,Res).
simple(In, Res) :- In =.. [A,B,C],
simple(B, Res1),
simple(C, Res2),
simple(A, Res1, Res2, Res).
/* 1 - 0 or 0 - 1 */
simple(-, X, Y, Res) :- X = 1, Y = 0, Res = 1; X = 0, Y = 1, Res = -1, !.
/* addition with 0 */
simple(+, X, Y, Res) :- X = 0, Res = Y; Y = 0, Res = X, !.
/* subtraction with 0 */
simple(-, X, Y, Res) :- X = 0, Res = Y; Y = 0, Res = X, !.
/* 1 + 0 */
simple(+, X, Y, 0) :- X = 1, Y = 0; X = 0, Y = 1, !.
/* multiply with 1 */
simple(*, X, Y, Res) :- X = 1, Res = Y; Y = 1, Res = X, !.
/* -1 multiply a number */
simple(*, X, Y, Res) :- X = -1, Res = -Y; Y = -1, Res = -X.
/* Negative rearrangement */
simple(+, X, -Y, X-Y).
simple(+, -X, Y, Y-X).
/* a-x-(x+2) change to a-2*x-2 */
/* Problem here is B + 1 is not evaluated */
simple(+, B*A, A, Res*A) :- C is B+1, simple(C, Res), !.
simple(+, A, B*A, Res*A) :- C is B+1, simple(C, Res), !.
simple(+, A*B, A, Res*A) :- C is B+1, simple(C, Res), !.
simple(+, A, A*B, Res*A) :- C is B+1, simple(C, Res), !.
simple(+, A*B, C*B, Res*B) :- D is A + C, simple(D, Res), !.
simple(+, A, A, 2*A).
simple(+, -A, A, 1).
simple(-, A*B, C*B, Res*B) :- D is A - C, simple(D, Res), !.
simple(-, B*A, A, Res*A) :- C is B - 1, simple(C, Res), !.
simple(-, -A, A, -2*A).
simple(-, A, A, 1).
simple(-, -A, A, -2*A).
/* Brackets */
simple(+, A+B, B+C, A+Res+C) :- simple(B + B, Res), !.
simple(+, A-B, B+C, A+Res+C) :- simple(-B + B, Res), !.
simple(+, A+B, B-C, A+Res+C) :- simple(B + B, Res), !.
simple(+, A-B, B-C, A+Res+C) :- simple(-B + B, Res), !.
simple(-, A+B, B+C, A+Res+C) :- simple(B - B, Res), !.
simple(-, A-B, B+C, A+Res+C) :- simple(-B - B, Res), !.
simple(-, A+B, B-C, A+Res+C) :- simple(B - B, Res), !.
simple(-, A-B, B-C, A+Res+C) :- simple(-B - B, Res), !.
/* Unary - well, negative - rules */
unary(-, A+B, -A-B).
unary(-, A-B, -A+B).
unary(-, A*B, -A* -B).
unary(-, C, -C).
unary(A, C+B, A*C+A*B).
unary(A, C-B, A*C-A*B).
/* Base case */
simple(Ope, X, Y, Res) :- atomic(X), atomic(Y),
Ope = '+', Res = X + Y;
Ope = '-', Res = X - Y;
Ope ='*', Res = X * Y;
Ope ='/', Res = X / Y.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment