;;;; Test for CANONICAL Function
;;;;
;;;; File:         normal.in
;;;; Author:       CS 51 (Bob Walton)
;;;; Version:      2

(load "normal.lsp")
--->
;; Loading file normal.lsp ...
;; Loading of file normal.lsp is finished.
T

(setf *trace* t)
--->
T

(normal '(- a b))
--->
((- A B) => (+ A (* -1 B)))
(+ A (* -1 B))

(normal '(+ (/ a b) (/ c d)))
--->
((+ (/ A B) (/ C D)) => (/ (+ A (* B (/ C D))) B))
((* B (/ C D)) => (/ (* B C) D))
((+ A (/ (* B C) D)) => (/ (+ (* A D) (* B C)) D))
((/ (/ (+ (* A D) (* B C)) D) B) =>
  (/ (+ (* A D) (* B C)) (* D B))
)
((* D B) => (* B D))
(/ (+ (* A D) (* B C)) (* B D))

(normal '(* (/ a b) (/ c d)))
--->
((* (/ A B) (/ C D)) => (/ (* A (/ C D)) B))
((* A (/ C D)) => (/ (* A C) D))
((/ (/ (* A C) D) B) => (/ (* A C) (* D B)))
((* D B) => (* B D))
(/ (* A C) (* B D))

(normal '(/ (/ a b) (/ c d)))
--->
((/ (/ A B) (/ C D)) => (/ A (* B (/ C D))))
((* B (/ C D)) => (/ (* B C) D))
((/ A (/ (* B C) D)) => (/ (* A D) (* B C)))
(/ (* A D) (* B C))

(normal '(* (+ a b) (+ c d)))
--->
((* (+ A B) (+ C D)) => (+ (* A (+ C D)) (* B (+ C D))))
((* A (+ C D)) => (+ (* A C) (* A D)))
((* B (+ C D)) => (+ (* B C) (* B D)))
((+ (+ (* A C) (* A D)) (+ (* B C) (* B D))) =>
  (+ (* A C) (+ (* A D) (+ (* B C) (* B D))))
)
(+ (* A C) (+ (* A D) (+ (* B C) (* B D))))

(normal '(+ (+ a b) c))
--->
((+ (+ A B) C) => (+ A (+ B C)))
(+ A (+ B C))

(normal '(+ c (+ b a)))
--->
((+ B A) => (+ A B))
((+ C (+ A B)) => (+ A (+ C B)))
((+ C B) => (+ B C))
(+ A (+ B C))

(normal '(+ (* c a) (+ (* b a) (* 4 d))))
--->
((* C A) => (* A C))
((* B A) => (* A B))
((+ (* A B) (* 4 D)) => (+ (* 4 D) (* A B)))
((+ (* A C) (+ (* 4 D) (* A B))) =>
  (+ (* 4 D) (+ (* A C) (* A B)))
)
((+ (* A C) (* A B)) => (+ (* A B) (* A C)))
(+ (* 4 D) (+ (* A B) (* A C)))

(normal '(* (* a b) c))
--->
((* (* A B) C) => (* A (* B C)))
(* A (* B C))

(normal '(* c (* b a)))
--->
((* B A) => (* A B))
((* C (* A B)) => (* A (* C B)))
((* C B) => (* B C))
(* A (* B C))

(normal '(+ 2 (+ 3 4)))
--->
((+ 3 4) => 7)
((+ 2 7) => 9)
9

(normal '(+ (* 2 a) (+ (* 3 a) (* 4 a))))
--->
((+ (* 3 A) (* 4 A)) => (* 7 A))
((+ (* 2 A) (* 7 A)) => (* 9 A))
(* 9 A)

(normal '(+ a (+ (* 3 a) a)))
--->
((+ (* 3 A) A) => (* 4 A))
((+ A (* 4 A)) => (* 5 A))
(* 5 A)

(normal '(+ (* 2 a) (+ a (* 4 b))))
--->
((+ (* 2 A) (+ A (* 4 B))) => (+ (* 3 A) (* 4 B)))
(+ (* 3 A) (* 4 B))

(normal '(+ a (+ a a)))
--->
((+ A A) => (* 2 A))
((+ A (* 2 A)) => (* 3 A))
(* 3 A)

(normal '(+ a (+ a b)))
--->
((+ A (+ A B)) => (+ (* 2 A) B))
(+ (* 2 A) B)

(normal '(+ 0 (+ a a)))
--->
((+ A A) => (* 2 A))
((+ 0 (* 2 A)) => (* 2 A))
(* 2 A)

(normal '(+ (* 3 a) (* -3 a)))
--->
((+ (* 3 A) (* -3 A)) => (* 0 A))
((* 0 A) => 0)
0

(normal '(+ (* 3 a) (* -2 a)))
--->
((+ (* 3 A) (* -2 A)) => (* 1 A))
((* 1 A) => A)
A

(normal '(* (* 3 a) (* -2 a)))
--->
((* (* 3 A) (* -2 A)) => (* 3 (* A (* -2 A))))
((* A (* -2 A)) => (* -2 (* A A)))
((* 3 (* -2 (* A A))) => (* -6 (* A A)))
(* -6 (* A A))

(normal '(+ w (/ x (/ y z))))
--->
((/ X (/ Y Z)) => (/ (* X Z) Y))
((+ W (/ (* X Z) Y)) => (/ (+ (* W Y) (* X Z)) Y))
(/ (+ (* W Y) (* X Z)) Y)

(normal '(* (/ (* x x) (+ x y)) (+ x y)))
--->
((* (/ (* X X) (+ X Y)) (+ X Y)) =>
  (/ (* (* X X) (+ X Y)) (+ X Y))
)
((* (* X X) (+ X Y)) => (* X (* X (+ X Y))))
((* X (+ X Y)) => (+ (* X X) (* X Y)))
((* X (+ (* X X) (* X Y))) =>
  (+ (* X (* X X)) (* X (* X Y)))
)
(/ (+ (* X (* X X)) (* X (* X Y))) (+ X Y))

(setf *trace* nil)
--->
NIL



(normal '(- (/ a (+ c d))
	       (/ x (+ z w))))
--->
(/
  (+ (* A W)
    (+ (* A Z) (+ (* -1 (* C X)) (* -1 (* D X))))
  )
  (+ (* C W) (+ (* C Z) (+ (* D W) (* D Z))))
)

(normal
  '(- (/ (* (+ x 1) (+ x 3)) (* (+ x 2) (+ x 4)))
      (/ (* (+ y 1) (+ y 3)) (* (+ y 2) (+ y 4)))))
--->
(/
  (+ (* 14 X)
    (+ (* -14 Y)
      (+ (* 5 (* X X))
        (+ (* 2 (* X (* X Y)))
          (+ (* -2 (* X (* Y Y))) (* -5 (* Y Y)))
  ) ) ) )
  (+ 64
    (+ (* 48 X)
      (+ (* 48 Y)
        (+ (* 8 (* X X))
          (+ (* 36 (* X Y))
            (+ (* 6 (* X (* X Y)))
              (+ (* X (* X (* Y Y)))
                (+ (* 6 (* X (* Y Y))) (* 8 (* Y Y)))
) ) ) ) ) ) ) )

(normal '(+ 1 (/ 1 (+ 1 (/ 1 (+ 1 (/ 1 (+ 1 x))))))))
--->
(/ (+ 5 (* 3 X)) (+ 3 (* 2 X)))

(normal
  '(+ -4 (+ (* c 4) (+ 4 (+ (* b 9)
			    (+ (* -4 c)
			       (+ d (* b -8))))))))
--->
(+ B D)



(rr-time (normal '(+ a (+ 1 (+ c (+ 3 (+ e 5)))))))
--->

Real time: 0.003902f0 sec.
Run time: 0.003904f0 sec.
Space: 912 Bytes

Number of Rewrites: 5
Number of failures to find any rewrite: 13

(+ 9 (+ A (+ C E)))

(rr-time
  (normal
   '(+ 5 (+ (* c 4) (+ 4 (+ (* 7 (* 4 b))
			    (+ c (+ d a))))))))
--->

Real time: 0.006829f0 sec.
Run time: 0.006832f0 sec.
Space: 1968 Bytes

Number of Rewrites: 10
Number of failures to find any rewrite: 25

(+ 9 (+ A (+ (* 28 B) (+ (* 5 C) D))))



(compile '<<)
--->
<<
(compile 'normal)
--->
NORMAL
(compile 'apply-rules)
--->
APPLY-RULES



(rr-time (normal '(+ a (+ 1 (+ c (+ 3 (+ e 5)))))))
--->

Real time: 0.002933f0 sec.
Run time: 0.002928f0 sec.
Space: 912 Bytes

Number of Rewrites: 5
Number of failures to find any rewrite: 13

(+ 9 (+ A (+ C E)))

(rr-time
  (normal
   '(+ 5 (+ (* c 4) (+ 4 (+ (* 7 (* 4 b))
			    (+ c (+ d a))))))))
--->

Real time: 0.00586f0 sec.
Run time: 0.005856f0 sec.
Space: 1968 Bytes

Number of Rewrites: 10
Number of failures to find any rewrite: 25

(+ 9 (+ A (+ (* 28 B) (+ (* 5 C) D))))