On Thu, Oct 4, 2012 at 6:17 PM, Matthew Rocklin <[email protected]> wrote:
> Hi Everyone,
>
> I'm planning to add a simplification system for sympy.matrices.expressions
> that is built on rewrite rules. I hope that this will be a nice test case
> for the feasibility of rewrite rules in the rest of SymPy. I would like to
> get feedback on design before I start work.
>
> First, rewrite rules are a way to transform an expression. This way tries to
> separate what happens from how it happens. We create rules like the
> following:
>
> def remove_ones(a_mul):
> """ Remove multiplicative identities from a Mul """
> return Mul(*[arg for arg in a_mul.args if arg != 1])
>
> These rules describe transformations that we might want to apply onto a node
> in our sympy expression. A rule is a function
>
> Expr -> Expr
>
> We combine and arrange rules with strategies. Here are two strategies
>
> def conditional(condition, rule):
> """ Only apply rule if condition is true """
> def new_rule(expr):
> if condition(expr): return rule(expr)
> else : return expr
> return new_rule
>
> def traverse_ast(rule):
> """ Apply a rule down a syntax tree traversing top-down """
> def new_rule(expr):
> if expr.is_Atom: return rule(expr)
> else: return rule(expr.__class__(map(new_rule,
> expr.args)))
> return new_rule
>
> A strategy is generally a function
>
> [Rules] Other-stuff -> Rule
>
> We might then create a rule to remove ones from all muls down a syntax tree
> as follows
>
> remove_all_ones = traverse_ast(conditional(lambda expr: expr.is_Mul,
> remove_ones))
>
> These strategies and rules are generally built up in interesting ways.
>
> What's nice about this is the following
> 1. The strategies are reusable
> 2. The rules are reusable
> 3. The rules supply very clear intent - they are easy to reason about
> 4. Efficiency is separate from logic.
>
> What's bad about this is the following
> 1. It's probably slower than what we have now
Well, it's not clear to me how this would even be used. Is there some
system that lets me say what rules I want (either very specifically,
or in some more general way)? Is there some registry of all defined
rules? The speed depends on how that actual application of the rules
is implemented. If things do end up being slow, we can possibly cache
some stuff, or look at implementing it better.
> 2. It is a bit more sophisticated/clever. Requires you to think about higher
> order functions
I think if you use a good class structure then it won't be. To create
a new rule, one just has to create a subclass of something (maybe a
similar rule, maybe a base Rule class), that just defines the key
components of the rule (i.e., those parts that make that rule
different from other rules). All the if, else, map, etc. stuff should
be abstracted in base classes.
And if several rules are similar, we can also abstract that in in base
classes as well. For example, a rule set like
tan(x) -> sin(x)/cos(x)
cos(x) -> sin(x)/tan(x)
sin(x) -> tan(x)*cos(x)
Are all based on the same concept, i.e., we have the identity t = s/c,
and we can solve that identity for any of the three variables. So the
rule object should be something as simple as
class TanRule(IdentityRule):
def __init__(self):
t, c, s = symbols("t c s")
self.identity = t - s/c
self.mapping = {t: tan, s: sin, c: cis}
Than the logic for figuring out how to convert sin in terms of tangent
and cosine would all be in IdentityRule. And if there's some kind of
rule registry, that could extract from this rule the information
needed to apply a transformation in the kind higher level terms like
that. If it's smart, we could even make it smart enough to combine
rules, so that we only have to tell it about a minimal number of
identities.
Actually, my above example is still a little naive, because it doesn't
work if the functions are not direct functions. For example, the
identity sin(2*x) = 2*sin(x)*cos(x) would require one of the mappings
to be a Lambda. So I think we will also need good pattern matching
for this to work well.
I'm glad that someone is finally taking initiative on this. I think
that MatrixExpressions are both expressive enough but small enough to
make a good testing ground for these ideas.
Aaron Meurer
>
> Again, my plan is to implement this for MatrixExpressions as a test case.
> I'm posting it here now in case people have suggestions/warnings/pointers.
>
> Best,
> -Matt
>
>
> --
> You received this message because you are subscribed to the Google Groups
> "sympy" group.
> To post to this group, send email to [email protected].
> To unsubscribe from this group, send email to
> [email protected].
> For more options, visit this group at
> http://groups.google.com/group/sympy?hl=en.
--
You received this message because you are subscribed to the Google Groups
"sympy" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sympy?hl=en.
