ps06 progress

2 files changed, 161 insertions, 0 deletions

diff --git a/ps06_rule_systems/bnewbold_ps06.txt b/ps06_rule_systems/bnewbold_ps06.txt
new file mode 100644
index 0000000..95273a4
--- /dev/null
+++ b/ps06_rule_systems/bnewbold_ps06.txt
@@ -0,0 +1,38 @@
+;;; 6.945 Problem Set #6 Comments
+;;; 03/18/2009
+;;; Bryan Newbold <bnewbold@mit.edu>
+
+Problem 6.1: Commutators
+--------------------------------
+If the well ordering rule check wasn't in place, then the rule would match over
+and over swapping the order, leading to an infinite loop. If the expressions
+are equal than no reordering is required.
+
+Problem 6.2: n-arity Commutators 
+------------------------------------
+Imposing an ordering means that numerical simplification can be done on the 
+leading elements instead of searching over the entire n-element list. This is
+big savings!
+
+For the straight numerical rules, the elements don't really all have to be
+ordered, just the numbers brought to the front in a given order.
+
+Problem 6.3: Ordering Sort
+------------------------------------
+For sure! There are a number of ways to make this search easier, something 
+resembling a radix sort would be a big help: bin all subexpressions by type,
+then sort those (eg all numbers up front, then variables, etc).
+
+Depending on how many and what sort of rules we've got, heuristics would 
+probably pay off well: for short expressions do the sort then match, for
+longer expressions use a more complicated sort and search for simplifications
+first (eg zero or unitary factors and zero terms).
+
+Problem 6.4: Collect Terms
+-------------------------------
+
+[see code in bnewbold_ps06_work.scm]
+
+Problem 6.5: A Memoizer
+-------------------------------
+
diff --git a/ps06_rule_systems/bnewbold_ps06_work.scm b/ps06_rule_systems/bnewbold_ps06_work.scm
new file mode 100644
index 0000000..4358ccf
--- /dev/null
+++ b/ps06_rule_systems/bnewbold_ps06_work.scm
@@ -0,0 +1,123 @@
+
+(load "load")
+
+;;; Problem 6.4
+
+(define algebra-3
+  (rule-simplifier
+   (list
+
+    ;; Sums
+
+    (rule (+ (? a)) none (? a))
+
+    (rule (+ (?? a) (+ (?? b)))
+	  none
+	  (+ (?? a) (?? b)))
+
+    (rule (+ (+ (?? a)) (?? b))
+	  none
+	  (+ (?? a) (?? b)))
+
+    (rule (+ (?? a) (? y) (? x) (?? b))
+	  (expr<? x y)
+	  (+ (?? a) (? x) (? y) (?? b)))
+    
+
+    ;; Products
+
+    (rule (* (? a)) none (? a))
+
+    (rule (* (?? a) (* (?? b)))
+	  none
+	  (* (?? a) (?? b)))
+
+    (rule (* (* (?? a)) (?? b))
+	  none
+	  (* (?? a) (?? b)))
+
+    (rule (* (?? a) (? y) (? x) (?? b))
+	  (expr<? x y)
+	  (* (?? a) (? x) (? y) (?? b)))
+
+    ;; Distributive law
+
+    (rule (* (? a) (+ (?? b)))
+	  none
+	  (+ (?? (map (lambda (x) `(* ,a ,x)) b))))
+
+    ;; Numerical simplifications below
+
+    (rule (+ 0 (?? x)) none (+ (?? x)))
+
+    (rule (+ (? x number?) (? y number?) (?? z))
+	  none
+	  (+ (? (+ x y)) (?? z)))
+
+
+    (rule (* 0 (?? x)) none 0)
+     
+    (rule (* 1 (?? x)) none (* (?? x)))
+
+    (rule (* (? x number?) (? y number?) (?? z))
+	  none
+	  (* (? (* x y)) (?? z)))
+
+    ;; Collect terms
+
+    (rule (+ (?? s) (? x) (? x) (?? e))
+	  none
+	  (+ (?? s) (* 2 (? x)) (?? e)))
+
+    (rule (+ (?? s) (* (?? x)) (* (?? x)) (?? e))
+	  none
+	  (+ (?? s) (* 2 (?? x)) (?? e)))
+
+    (rule (+ (?? s) (? x) (?? m) (* (? n number?) (? x)) (?? e))
+	  none
+	  (+ (?? s) (?? m) (* (? (+ 1 n)) (? x)) (?? e)))
+
+    (rule (+ (?? s) (* (? n number?) (?? x)) (* (? p number?) (?? x)) (?? e))
+	  none
+	  (+ (?? s) (* (? (+ n p)) (? x)) (?? e)))
+
+    )))
+
+#| Test!
+
+(algebra-3 '(+ x (* 4 x)))
+;Value 15: (* 5 x)
+
+(algebra-3 '(+ (* 8 1 f 34) (* 3 f)))
+;Value 16: (* 275 x)
+
+(algebra-3 '(+ x x))
+;Value 42: (* 2 x)
+
+(algebra-3 '(+ 4 s u s p))
+;Value 39: (+ 4 p u (* 2 s))
+
+(algebra-3 '(+ 1 2))
+;Value: 3
+
+(algebra-3 '(+ (* -2 h) (* 2 h)))
+;Value: 0
+
+(algebra-3 '(+ h (* 4 h)))
+;Value 83: (* 5 h)
+
+(algebra-3 '(+ (* w h) (* 4 h)))
+;Value 84: (+ (* 4 h) (* h w))
+
+(algebra-3 '(+ (* -1 h) (* 2 h)))
+;Value 85: (h)
+
+(algebra-3 '(+ x (* a x)))
+;Value 86: (+ x (* a x))
+
+(algebra-3 '(+ y (* x -2 w) (* x 4 y) (* w x) z (* 5 z) (* x w) (* x y 3)))
+;Value 87: (+ y (* 6 z) (* 7 (x y)))
+
+|#
+
+;;; Problem 6.5
\ No newline at end of file