summaryrefslogtreecommitdiffstats log msg author committer range
diff options
 context: 12345678910152025303540 space: includeignore mode: unifiedssdiffstat only
author committer bnewbold 2009-03-20 03:50:34 -0400 bnewbold 2009-03-20 03:50:34 -0400 1c2b037e439a707ec4f9382d6ba84985dd089e6e (patch) f1d0b2c198455995ac1bb9c4f37e1479f4df3593 bcc309a5db2214ae2ebaab17c54f8d1f8833025b (diff) 6.945-1c2b037e439a707ec4f9382d6ba84985dd089e6e.tar.gz6.945-1c2b037e439a707ec4f9382d6ba84985dd089e6e.zip
ps06 progress
-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.txtnew file mode 100644index 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 ++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.scmnew file mode 100644index 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