% Arithmetic expression simplifier - The Craft of Prolog/ R.A. O'Keefe

simplify_sum(Sum,Simplified) :-
	simplify_sum(Sum,TopOfTree,HoleAtBottom,0,N),
	simplify_sum1(Simplified,TopOfTree,HoleAtBottom,N).	
simplify_sum1(Simplified,TopOfTree,HoleAtBottom,N):-
	N \== 0,
	HoleAtBottom=N,
	Simplified=TopOfTree,
	!.
simplify_sum1(Simplified,TopOfTree,HoleAtBottom,N):-
	N == 0, 
	var(TopOfTree),
	Simplified=0,
	!.
simplify_sum1(Simplified,TopOfTree,HoleAtBottom,N):-
	N == 0, 
	nonvar(TopOfTree),
	TopOfTree=Simplified+HoleAtBottom ; 
		TopOfTree=Simplified-Last, HoleAtBottom = -Last.

simplify_sum(A+B,Hole0,Hole,N0,N):-!,
	simplify_sum(B,Hole0,Hole1,N0,N1),
	simplify_sum(A,Hole1,Hole,N1,N).
simplify_sum(A-B,Hole0,Hole,N0,N):-!,
	simplify_sum(-B,Hole0,Hole1,N0,N1),
	simplify_sum(A,Hole1,Hole,N1,N). 
simplify_sum(C,Hole,Hole,N0,N):- number1(C), !,
	N is N0 + C.
simplify_sum(-X,Hole - X,Hole,N,N):- !.
simplify_sum(X,Hole + X,Hole,N,N):- !.
number1(C):- number(C).
number1(-C):- number(C).
/* Exemples
| ?- simplify_sum(3+5,S).
  S = 8
| ?- simplify_sum(3+5+b+6+c,S).
  S = 14+b+c
| ?- simplify_sum((3+5)+b+6+c,14+b+c).
  true
| ?- simplify_sum(3+5+b+6+c,S).
S = 14+b+c
| ?-  simplify_sum(3+5+b-6+c,S).

S = 2+b+c

true
| ?-  simplify_sum(3+5+b-6-c,S).

S = 2+b-c
true
| ?-  simplify_sum(3-5+b-6+c,S).

S = -8+b+c
| ?-  simplify_sum(-3-b-c+3,S).

S = -c-b
*/