Bugs ---- Script →#.math← does a poor job of collecting "like terms": math script until ')' x+y + x+y ⍝ good 2*(x+y) x+y + x+y + x+y ⍝ not so good 2*(x+y)+x+y x+y+z + x+y+z ⍝ abysmal x+y+z+x+y+z ) In general, to collect terms that are arbitrarily far apart, we would need arb- itrarily complex reduction templates. One solution would be to install a separate "collection" phase alongside reduce, to do the job. numb──←─┐ ┌────┐ ┌────────┐ ┌─────┐ ├─←─┤show├─←─┤evaluate├─←─┤parse├───←──expr expr──←─┘ └────┘ └─┬────┬─┘ └─────┘ ↓ ↑ ┌─┴────┴─┐ │ reduce │ └─┬────┬─┘ ↓ ↑ ┌─┴────┴─┐ │collect │ └────────┘ The collector would need to know whether each infix function is commutative or associative. The information could be indicated either in the function declarat- ion itself: ← *(×)⍨≡ /(÷) ⍝ mul div │└────────────────── associative └─────────────────── commutative or by ancilliary declarations of the form: :commutative + * :associative + * Note that the _distribution_ of functions with respect to each other (* distrib- utes over + etc) is already handled adequately by the reduction subsystem, as distribution is a _local_ effect within the expression tree. The collector would identify like terms and try to bring them close enough in the expression tree for the reduction rules to take effect. ((((x+y)+z)+x)+y)+z ⍝ fully parenthesised starting expression. ((((x+y)+z)+x)+y)+z ⍝ like terms ¯ ¯ ((((x+y)+z)+x)+y)+z ⍝ + associative ¯ ¯ (((x+(y+z))+x)+y)+z ⍝ + commutative ¯ ((((y+z)+x)+x)+y)+z ⍝ + associative ¯ ¯ (((y+z)+(x+x))+y)+z ⍝ reduction rule ¯¯¯ (((y+z)+(2*x))+y)+z ⍝ like terms ¯ ¯ ... ((2*z)+(2*y))+(2*x) ... 2*(z+x+y) Lexicographical Ordering ------------------------- An alternative might be to introduce a further pattern-matching mechanism, which would allow for lexicographical ordering of expressions and thus, the collection of like terms across commutative and associative infix functions. In the following, let's use >> (and <<) as short-hand for "is lexicographically greater-than (and less-than)" and introduce new pattern-matching symbols ⍋ and ⍒ so that: (..⍋..⍒..) matches (..X..Y..) iff X >> Y A reasonable choice of ordering might be: [1] Expressions ordered by their operator binding strengths, [2] Non-atomic expressions trump atoms. [3] Atoms sort in {⍵[⍋↑⍕¨⍵]} order. For example, using the →##.math← script: a∧b >> a*b ⍝ ∧ binds tighter than *, a*b >> c∧d + e∧f ⍝ * binds tighter than +, x+y >> a ⍝ expressions trump atoms, d << 123 ⍝ literals follow variables, a << b ⍝ "a" precedes "b". This would enable reduction rules, for commutative and associative operators, to collect "heavier" terms to the left, in accordance with mathematical convention. Here is an example for the commutative and associative function +: ⍋+⍒ = ⍒+⍋ ⍝ + is commutative: b+a => a+b p+⍋+⍒ = p+⍒+⍋ ⍝ and associative: (x+z)+y => (x+y)+z which would tend to collect like terms: y + x + z + x + y + z ⍝ ⍋+⍒ => ⍒+⍋ ¯¯¯¯¯ → x + y + z + x + y + z ⍝ p+⍋+⍒ => p+⍒+⍋ ¯¯¯¯¯¯¯ → x + y + x + z + y + z ⍝ p+⍋+⍒ => p+⍒+⍋ ¯¯¯¯¯¯¯ ¯¯¯¯¯¯¯ → x + x + y + y + z + z ⍝ p+p => 2*p ¯¯¯¯¯ ¯¯¯¯¯ ¯¯¯¯¯ → 2*x + 2*y + 2*z ⍝ (p*q)+(p*r) => p*(q+r) ¯¯¯¯¯¯¯¯¯¯¯¯¯¯¯ → 2*(x+y+z) It is tempting to use this mechanism to try to arrange expression terms in a pleasing order. We might prefer: (4*x∧2 + 3*x - 7) rather than (x*3 - 7 + x∧2*4) and to see (x+y) instead of (y+x). This leads to a slight conundrum in that: We like our expression variables in alphabetical order: x+y+z ⍝ x << y << z but our polynomial terms in decreasing order of exponent: x∧3 + x∧2 ⍝ x∧3 << x∧2: implies 3 << 2 ! One way out of this dilema is to define the lex-ordering of variable names to be the reverse of alphabetical ordering. See also: →Differentiation← Back to: →Contents←