diff options
Diffstat (limited to 'ps06_rule_systems/bnewbold_ps06.txt')
-rw-r--r-- | ps06_rule_systems/bnewbold_ps06.txt | 38 |
1 files changed, 38 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 +------------------------------- + |