blob: 95273a4be3eada8d702e02f9475b488f70ac47e5 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
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
-------------------------------
|
