From 1c2b037e439a707ec4f9382d6ba84985dd089e6e Mon Sep 17 00:00:00 2001 From: bnewbold Date: Fri, 20 Mar 2009 03:50:34 -0400 Subject: ps06 progress --- ps06_rule_systems/bnewbold_ps06.txt | 38 ++++++++++ ps06_rule_systems/bnewbold_ps06_work.scm | 123 +++++++++++++++++++++++++++++++ 2 files changed, 161 insertions(+) create mode 100644 ps06_rule_systems/bnewbold_ps06.txt create mode 100644 ps06_rule_systems/bnewbold_ps06_work.scm (limited to 'ps06_rule_systems') 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 + +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