[abc] Possible reduction in filtering costs

[Please check my algebra, if the optimisation is correct I'll check in]

    "In general the result of turning off negative bindings
     in tracematches in nonsensical, but for this particular
     example it yields correct results..."

I've been thinking about this - surely if we can sometimes safely
ignore skip loops, then there should be an optimisation that determines
some of the cases where its possible and does it automatically.

How about the following:

First a reminder definition:

    skip = AND_{s} ¬match(s,e)

Consider a state i, with a self-loop for symbol "foo".
Assuming the predicate "in" represents constraints for
transitions from other states the update equation for
label_i is:

   label_i

= {update equation}

    in OR (label_i_old AND match("foo", e))
       OR (label_i_old AND skip_i)

= {boolean algebra}
    in OR (label_i_old AND
              (match("foo", e) OR skip_i))

= {skip definition}

    in OR (label_i_old AND
              (match("foo", e) OR AND_{s} ¬match(s,e)))

= {boolean algebra}

    in OR (label_i_old AND
              AND{s} (match("foo", e) OR ¬match(s,e))

= {X OR ¬X === true}

    in OR (label_i_old AND
              AND{s =/= "foo"} (match("foo", e) OR ¬match(s,e))

= {boolean algebra}

    in OR (label_i_old AND
              (match("foo", e) OR AND{s =/= "foo"} ¬match(s,e)))

=

    in OR (label_i_old AND (match("foo", e))
       OR (label_i_old AND AND{s =/= "foo"} ¬match(s,e))

   So we can ignore the symbol "foo" when calculating skip for state i.
Since we calculate skip incrementally for each state anyway, this
idea translates into a 3-line patch.

I ran jhotdraw on musketeer without and with the patch:

without
-------
animation took: 557134
memory used: 1049392

with
----animation took:
animation took: 314668
memory used: 1036064
Received on Fri Mar 10 13:36:36 2006