summaryrefslogtreecommitdiffstats
path: root/ps06_rule_systems
diff options
context:
space:
mode:
authorbnewbold <bnewbold@eta.mit.edu>2009-03-20 03:50:34 -0400
committerbnewbold <bnewbold@eta.mit.edu>2009-03-20 03:50:34 -0400
commit1c2b037e439a707ec4f9382d6ba84985dd089e6e (patch)
treef1d0b2c198455995ac1bb9c4f37e1479f4df3593 /ps06_rule_systems
parentbcc309a5db2214ae2ebaab17c54f8d1f8833025b (diff)
download6.945-1c2b037e439a707ec4f9382d6ba84985dd089e6e.tar.gz
6.945-1c2b037e439a707ec4f9382d6ba84985dd089e6e.zip
ps06 progress
Diffstat (limited to 'ps06_rule_systems')
-rw-r--r--ps06_rule_systems/bnewbold_ps06.txt38
-rw-r--r--ps06_rule_systems/bnewbold_ps06_work.scm123
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