alternatives to subclassing Expr
krastano...@gmail.com
combinations of functions of and operators on mostly commutative
symbols, one needs to subclass Expr and/or add more stuff to Mul, Add,
etc.
Examples: MatrixSymbol and Quantum subclass Expr. Units adds stuff to
Mul and Add.
It seems that this is not sustainable because
1. Adding too much stuff to Mul and Add
https://code.google.com/p/sympy/issues/detail?id=1941
2. Mixing subclasses of Expr can give strange results.
A solution that I like is working on AST trees. See
https://groups.google.com/d/msg/sympy/fCQEdSQybTM/X04kBhbIEGUJ
It is possible that I will need much of this functionality if I
proceed to apply for GSoC with a multi-linear algebra / differential
geometry project.
A first step (that I have requested a few months ago, when I was
working on lambdify) will be to at least have a nice api for
traversing all args. I have asked for that here
https://groups.google.com/d/topic/sympy/Pa3k3WETPC0/discussion
So I plan to add methods that take evaluate=False expressions and
generate the syntax tree (in the form of tuples at first, something
more pythonic later). And also add other methods that work with those
syntax trees (validation, canonicalization).
In one sentence, at the moment Add and Mul and others are both
containers and canonicalizators (if this word exists :). I want to
have them separate, so different canonicalizators can be used on the
same expr (real algebra vs quantum module vs multilinear vs group
theory vs any other system that works on symbols).
This means that at least at the beginning Add, Mul, etc will be used
as they are now - both containers and canonicalizators for the real
algebra that sympy supports, but at the same time they will be used
with evaluate=False as only containers for other symbolic systems.
@Nathan Rice, If I understand correctly, your idea is to have the
entire core of sympy working in that manner. Am I correct? Do you have
some proof of concept code?
@community, Is this an acceptable solution for the possible future
work on Expr and in my case on multi-linear algebra?
@Aaron and community, has this been discussed before? Was there
something about different base algebra systems?
Stefan
Aaron Meurer
This is definitely a huge problem, if not just for the
unmaintatinability of the code. I wanted to change S.NegativeInfinity
to be implemented as just Mul(-1, S.Infinity)
(http://code.google.com/p/sympy/issues/detail?id=3059), but the logic
in Mul.flatten was so complicated that I've yet to muster up the time
to really go through it and make sure everything is right.
>
> This means that at least at the beginning Add, Mul, etc will be used
> as they are now - both containers and canonicalizators for the real
> algebra that sympy supports, but at the same time they will be used
> with evaluate=False as only containers for other symbolic systems.
So you want to separate the canonicalizers from both the objects and
the containers? It seems to me that it would be best to just put them
in the objects themselves, probably just using the Python double
dispatch system, but this is an interesting idea too. Would that make
it more or less extensible?
Let's start a wiki page with these ideas. For starters, I think we
should list every kind of object that would want to have it's own
"canconicalizer", including at least half a dozen that are currently
special cased in the core (Mul.flatten mostly). Then we will get an
idea of what kind of functionality we need, and how we can go about
implementing it.
>
> @Nathan Rice, If I understand correctly, your idea is to have the
> entire core of sympy working in that manner. Am I correct? Do you have
> some proof of concept code?
>
> @community, Is this an acceptable solution for the possible future
> work on Expr and in my case on multi-linear algebra?
>
> @Aaron and community, has this been discussed before? Was there
> something about different base algebra systems?
Not that I know of (or can currently think of anyway), but there could
have been stuff from way before I joined the project, especially
relating to sympy-core.
I guess there was the whole discussion with _op_priority and so on
last year. Was that before you started following things?
Aaron Meurer
>
> Stefan
>
> --
> You received this message because you are subscribed to the Google Groups "sympy" group.
> To post to this group, send email to sy...@googlegroups.com.
> To unsubscribe from this group, send email to sympy+un...@googlegroups.com.
> For more options, visit this group at http://groups.google.com/group/sympy?hl=en.
>
Nathan Rice
> containers and canonicalizators (if this word exists :). I want to
> have them separate, so different canonicalizators can be used on the
> same expr (real algebra vs quantum module vs multilinear vs group
> theory vs any other system that works on symbols).
>
> This means that at least at the beginning Add, Mul, etc will be used
> as they are now - both containers and canonicalizators for the real
> algebra that sympy supports, but at the same time they will be used
> with evaluate=False as only containers for other symbolic systems.
>
> @Nathan Rice, If I understand correctly, your idea is to have the
> entire core of sympy working in that manner. Am I correct? Do you have
> some proof of concept code?
Did you see the github link I posted? https://github.com/nathan-rice/symbolic
The Symbol class in the posted code does the following simultaneously:
1. Builds a closure chain that will execute the sequence of operations
as if the original object had been used
2. Records the necessary information to generate an AST representation
of the code that would perform that sequence of operations.
Even ugly things like attribute setting, augmented assigns, and what
not are supported. Python is obnoxious about crossing from expression
to statement, but that is mostly handled as well. I even dealt with
history bookkeeping when performing operations on two symbols that
were the target of multiple statements.
There are lots of tests, and only a few things are broken off the top
of my head (__divmod__ and performing n-ary (n>1) operations where one
of the arguments is also a Symbol object).
Nathan
Nathan Rice
with a given symbol as an argument, it will function correctly. If
you perform another n-ary operation on the original symbol with that
same other symbol a second time is when the bug occurs. I don't
currently do smart merging of the statement history of the other
symbol with the statement history of the self symbol, so operations
will be repeated. The logic required to do this right is not terribly
complicated, I could probably just give each statement operation on a
symbol a unique identifier, then only merge in unique identifiers, and
maintain the history in sorted order.
Nathan
Ronan Lamy
écrit :
> As it stands now, for building symbolic systems different from simple
> combinations of functions of and operators on mostly commutative
> symbols, one needs to subclass Expr and/or add more stuff to Mul, Add,
> etc.
>
> Examples: MatrixSymbol and Quantum subclass Expr. Units adds stuff to
> Mul and Add.
>
> It seems that this is not sustainable because
> 1. Adding too much stuff to Mul and Add
> https://code.google.com/p/sympy/issues/detail?id=1941
> 2. Mixing subclasses of Expr can give strange results.
+1
> A solution that I like is working on AST trees. See
> https://groups.google.com/d/msg/sympy/fCQEdSQybTM/X04kBhbIEGUJ
How is that different from the existing expression trees? If you really
have *syntax* trees in mind, then it's not a suitable solution since you
can't take advantage of the commutativity of addition or of the
associativity of multiplication (syntactically, "a + b" and "b + a" are
different things).
> It is possible that I will need much of this functionality if I
> proceed to apply for GSoC with a multi-linear algebra / differential
> geometry project.
>
> A first step (that I have requested a few months ago, when I was
> working on lambdify) will be to at least have a nice api for
> traversing all args. I have asked for that here
> https://groups.google.com/d/topic/sympy/Pa3k3WETPC0/discussion
>
> So I plan to add methods that take evaluate=False expressions and
> generate the syntax tree (in the form of tuples at first, something
> more pythonic later). And also add other methods that work with those
> syntax trees (validation, canonicalization).
>
> In one sentence, at the moment Add and Mul and others are both
> containers and canonicalizators (if this word exists :). I want to
> have them separate, so different canonicalizators can be used on the
> same expr (real algebra vs quantum module vs multilinear vs group
> theory vs any other system that works on symbols).
I'm not sure what you mean by canonicaliser, but I'll assume you refer
to Add(*foo) being used to compute the sum of the elements of foo. I
agree that it's a problem and a violation of the single-responsibility
principle. We should replace Add(*foo) with an efficient function
ssum(foo).
> This means that at least at the beginning Add, Mul, etc will be used
> as they are now - both containers and canonicalizators for the real
> algebra that sympy supports, but at the same time they will be used
> with evaluate=False as only containers for other symbolic systems.
evaluate=False isn't usable for what you want to do as it destroys any
attempt at establishing useful invariants for your objects (such as
expr.__class__(*expr.args) == expr).
Joachim Durchholz
Am 09.03.2012 01:51, schrieb Aaron Meurer:
> So you want to separate the canonicalizers from both the objects and
> the containers? It seems to me that it would be best to just put them
> in the objects themselves, probably just using the Python double
> dispatch system, but this is an interesting idea too.
Multiple dispatch or multiple inheritance?
Multiple dispatch (i.e. selecting the function to be executed based on
the type of more than one parameter) makes extending the system via
subclasses unmodular: people cannot extend independently, they must
coordinate.
Assuming that X' is a subclass of some class X,
if we have a function f(A,B),
and some person writes A' and defines f(A',B),
and somebody else writes B' and defines f(A,B'),
and a third person wants to use both A' and B', and calls f(A',B'), that
call is ambiguous, it could go to the A' or the B' variant of f.
In most likelihood, both are wrong since the A' and the B' variants of f
were written because the new subclasses needed new code in f.
So if somebody wants to combine A' and B', he needs to "fill the matrix"
with a new f(A',B').
It would be possible to do this inside SymPy. Just document which
functions are using multiple dispatch, and warn potential subclass
authors that overriding these functions requires coordination with
anybody writing a subclass on another parameter.
Multiple inheritance as done in Python is unsound in the presence of
diamond inheritance.
I have an essay on the topic; see
http://durchholz.org/essays/object-orientation/diamond-inheritance/
IMNSHO, Python's C3 MRO is better than the original mechanism but still
hopelessly inadequate.
In general, this is not a big problem. However, SymPy would be
particularly vulnerable, since it is dealing with a hierarchy of
mathematical concepts, with abundant diamond structures (actually, the
essay uses hypothetical Group and Monoid classes to explain the
difficulties).
> Would that make it more or less extensible?
More extensible, until the mechanisms are in widespread use, then it
will start becoming less extensible.
My advice would be to stick with
- single dispatch
- single inheritance
- finding ways to structure the logic so that these two are enough
- where that does not work (and we will have that), program some
explicit mechanism for resolving what needs to be done in what case.
I hope this has shed some light on the issues.
I'm aware that this were some pretty strong statements on a sometimes
controversial topic. Feel free to ask questions, or to challenge
assumptions and conclusions.
Regards,
Jo
Joachim Durchholz
> The Symbol class in the posted code does the following simultaneously:
>
> 1. Builds a closure chain that will execute the sequence of operations
> as if the original object had been used
> 2. Records the necessary information to generate an AST representation
> of the code that would perform that sequence of operations.
That sounds awesome.
Barring higher-priority interrupts, I'll take a closer look this weekend.
Ronan Lamy
> Wearing my software architect hat:
>
> Am 09.03.2012 01:51, schrieb Aaron Meurer:
> > So you want to separate the canonicalizers from both the objects and
> > the containers? It seems to me that it would be best to just put them
> > in the objects themselves, probably just using the Python double
> > dispatch system, but this is an interesting idea too.
>
>
> Multiple dispatch or multiple inheritance?
In Python, double dispatch refers to the complicated mechanism by which
binary operators get evaluated (e.g. when you have the expression
"a + b"). That reminds me that I started to write an explanation of how
it really works, I ought to finish it some day. Meanwhile, see
http://docs.python.org/library/numbers.html#implementing-the-arithmetic-operations
I don't really get Aaron's meaning either, though.
>
> Multiple dispatch (i.e. selecting the function to be executed based on
> the type of more than one parameter) makes extending the system via
> subclasses unmodular: people cannot extend independently, they must
> coordinate.
>
> Assuming that X' is a subclass of some class X,
> if we have a function f(A,B),
> and some person writes A' and defines f(A',B),
> and somebody else writes B' and defines f(A,B'),
> and a third person wants to use both A' and B', and calls f(A',B'), that
> call is ambiguous, it could go to the A' or the B' variant of f.
>
> In most likelihood, both are wrong since the A' and the B' variants of f
> were written because the new subclasses needed new code in f.
> So if somebody wants to combine A' and B', he needs to "fill the matrix"
> with a new f(A',B').
I'm not sure multiple dispatch is the problem. Calling f[X, Y] the
implementation of f for instances of the classes X and Y, then if both
A' and B' obey Liskov substitutability, f[A', B](a', b') == f[A, B'](a',
b') == f[A, B](a', b'), so there is no ambiguity in what the value of
f(a', b') should be.
>
> It would be possible to do this inside SymPy. Just document which
> functions are using multiple dispatch, and warn potential subclass
> authors that overriding these functions requires coordination with
> anybody writing a subclass on another parameter.
>
>
> Multiple inheritance as done in Python is unsound in the presence of
> diamond inheritance.
>
> I have an essay on the topic; see
> http://durchholz.org/essays/object-orientation/diamond-inheritance/
>
> IMNSHO, Python's C3 MRO is better than the original mechanism but still
> hopelessly inadequate.
> In general, this is not a big problem. However, SymPy would be
> particularly vulnerable, since it is dealing with a hierarchy of
> mathematical concepts, with abundant diamond structures (actually, the
> essay uses hypothetical Group and Monoid classes to explain the
> difficulties).
A few comments on your essay:
* You obviously meant 'Ring' instead of 'Group'.
* It doesn't apply to Python: in Python, you can't rename inherited
methods and 'a = d' can never mean 'hammer square peg d into round hole
a'.
* There is a categorical oversight in your analysis: in mathematical
terms, 'Monoid' and 'Ring' are categories, while specific algebraic
structures (e.g. the ring of integers (ZZ, +, *)) are members of these
categories. The instances of the classes you discuss are elements of
these structures (e.g. the integer 42), so the classes themselves
represent the structures. In Pythonic terms, Monoid and Ring should be
metaclasses, which means you don't have a diamond any more, since B and
C are instances of the same metaclass Monoid, but don't share a common
base class.
>
> > Would that make it more or less extensible?
>
> More extensible, until the mechanisms are in widespread use, then it
> will start becoming less extensible.
>
> My advice would be to stick with
> - single dispatch
We can't. "a + b" necessarily invokes some form of double dispatch.
> - single inheritance
> - finding ways to structure the logic so that these two are enough
> - where that does not work (and we will have that), program some
> explicit mechanism for resolving what needs to be done in what case.
>
Hm, you're just saying that we should avoid multiple inheritance and
multiple dispatch. But the critical question is "How?" Could you take an
existing example of multiple inheritance, for instance AtomicExpr, and
explain what you think we should with it?
krastano...@gmail.com
So you want to separate the canonicalizers from both the objects and
the containers? It seems to me that it would be best to just put them
in the objects themselves, probably just using the Python double
it more or less extensible?
I would prefer to have them (the canonicalizers(my spell checker
insists that the word does not exist)) outside of the objects. I
imagine them just as a special case of crawlers (very similar to what
crawlers the python AST module supports).
Ronan said:
How is that different from the existing expression trees? If you really
have *syntax* trees in mind, then it's not a suitable solution since you
can't take advantage of the commutativity of addition or of the
associativity of multiplication (syntactically, "a + b" and "b + a" are
different things).
I'm not sure what you mean by canonicaliser, but I'll assume you refer
to Add(*foo) being used to compute the sum of the elements of foo. I
agree that it's a problem and a violation of the single-responsibility
principle. We should replace Add(*foo) with an efficient function
ssum(foo).
When I say canonicalizer I mean the algorithm that converts eg
"2*x+1+x+3" to "4+3*x". I don't want commutativity in + or
associativity in *. I want them to be containers. Then, (just giving
an **example**, not necessary my vision of the future) when the AST is
constructed a default canonicalizer is chosen. A way to do this will
be:
0. parse the input and create AST (basically just sympify(..., evaluate=False))
1. call the ChoseGoodCanonicalizer crawler on the AST
2.a. ChoseGoodCanonicalizer returns canonicalizer implementating of
our current algorithms for trees containing only symbols
2.b. it returns another canonicalizer if the AST tree contains stranger things.
This does not directly fix the problem with two people subclassing
Expr for different purposes and then trying to mix those two. But
different canonicalizers can be called only on subtrees. Now as it
stands this is impossible. If I have MatrixSymbols A and B and ket K I
can not do A*B*K and expect good results.
I am sure that my lack of education in CS is preventing me to see a
better solution, that is why I am shooting those ideas here: some of
you should be able to correct me. But separating container and
canonicalizer (hopefully I have defined the word in this mail) seems a
good idea.
Stefan
Aaron Meurer
see two possibilities. There are container objects like Mul and
objects that go inside them (subclasses of Expr). The possibilities
are:
1. Container objects do the canonicalization of the objects that go
inside them (this is the way we do it now, at least for Mul and Add).
2. Objects themselves must define how they are canonicalized (i.e.,
using __mul__ and __rmul__).
I saw Stefan as suggesting a third alternative, which I admittedly am
not entirely clear on myself:
3. There are a third kind of object, canonicalizers, which do the
canonicalization. Somehow the container objects and/or the objects
that go in them hook into them.
Like I said, I'm still vague on how this would actually work, but it
leads to interesting possibilities, like the ability to subclass
canonicalizers.
Or maybe everything there is already possible with the double dispatch rules.
By the way, a Google search reveals that "canonicalizer" has been used
in a similar context before. According to at least one source, you
can add -er and -ee to any verb to make your own agent noun, as they
are called, and it will be perfectly correct English, even if your
spell checker disagrees. So maybe we should call the "objects that go
in the containers" canonicalizees.
Aaron Meurer
krastano...@gmail.com
> Regarding what I meant, I was just interpreting what Stefan said. I
> see two possibilities. There are container objects like Mul and
> objects that go inside them (subclasses of Expr). The possibilities
> are:
>
> 1. Container objects do the canonicalization of the objects that go
> inside them (this is the way we do it now, at least for Mul and Add).
>
> 2. Objects themselves must define how they are canonicalized (i.e.,
> using __mul__ and __rmul__).
>
> I saw Stefan as suggesting a third alternative, which I admittedly am
> not entirely clear on myself:
>
> 3. There are a third kind of object, canonicalizers, which do the
> canonicalization. Somehow the container objects and/or the objects
> that go in them hook into them.
>
> Like I said, I'm still vague on how this would actually work, but it
> leads to interesting possibilities, like the ability to subclass
> canonicalizers.
In: a = parser_function('x+x+3+y*z+Integral(x)')
In: a
Add(x,x,3,Mul(y,z),Integral(x))
In: simple_canonicalizer(a)
Add(3, Mul(2,x), Mul(y,z), Integral(x))
In: crawler_doit(a)
Add(x,x,3, Mul(y,z), Mul(1/2,Pow(x,2)))
So here Add, Mul etc are only containers. parser_function is just
sympify with evaluate=False. Of course there may be a default
canonicalizer that is always called (as it is implicitly done now).
And all the double dispatch rules are the same but with
evaluate=False.
Basically it is the came core, with evalulate=False and all the
evaluate logic moved to "something" that craws the expression tree.
Associativity, commutativity, all is done by that crawler.
By the way, how is code generate by the codegen module without having
ASTs? I will have to look that up.
Aaron Meurer
https://github.com/sympy/sympy/wiki/Canonicalization where I will
write down some of my ideas and what I think are issues to look at.
Feel free to edit that page however you want. I'm basing all of my
discussion on Mul, since that seems to be the most complex one, but
many things apply to any similar classes as well (such as Add, or even
more generic container classes like And and Or). I guess someone
should merge the useful ideas from this thread into that page as well.
For now, I'm starting off by listing all classes that have custom
logic in Mul.flatten, and all classes that would like to have that to
behave properly (like MatrixSymbol). Then we will hopefully get a
good perspective of what we should do, and maybe can start to see some
corner cases by considering combinations of all the possible classes.
By the way, to answer a question posited earlier in this thread,
commutativity matters because we want x*y to equal y*x. This
generally means that we canonicalize the order of the args.
Associativity matters because x*(y*z) and (x*y)*z are evaluated
differently by Python. This is an issue if there are conflicting
rules, but it might also be a problem even with non-conflicting rules.
Aaron Meurer
Joachim Durchholz
> In Python, double dispatch refers to the complicated mechanism by which
> binary operators get evaluated (e.g. when you have the expression
> "a + b"). That reminds me that I started to write an explanation of how
> it really works, I ought to finish it some day. Meanwhile, see
> http://docs.python.org/library/numbers.html#implementing-the-arithmetic-operations
Technically, that is not multiple dispatch, but conversion plus single
dispatch.
If would be multiple dispatch if Python defined a separate function for
int*int, int*float, float*int, and float*float, repeat for all numeric
types.
Which is perfectly fine if you make sure that each cell in the matrix
has a solid definition, and know that the matrix will never be extended
in to directions at once.
>> Assuming that X' is a subclass of some class X,
>> if we have a function f(A,B),
>> and some person writes A' and defines f(A',B),
>> and somebody else writes B' and defines f(A,B'),
>> and a third person wants to use both A' and B', and calls f(A',B'), that
>> call is ambiguous, it could go to the A' or the B' variant of f.
>>
>> In most likelihood, both are wrong since the A' and the B' variants of f
>> were written because the new subclasses needed new code in f.
>> So if somebody wants to combine A' and B', he needs to "fill the matrix"
>> with a new f(A',B').
>
> I'm not sure multiple dispatch is the problem. Calling f[X, Y] the
> implementation of f for instances of the classes X and Y, then if both
> A' and B' obey Liskov substitutability, f[A', B](a', b') == f[A, B'](a',
> b') == f[A, B](a', b'), so there is no ambiguity in what the value of
> f(a', b') should be.
The mathematical definition is fine, but the f(a',b') case never gets
reviewed or tested:
- The author of A' may not be aware of the existence of B'.
- The author of B' may not be aware of the existence of A'.
- Any bugs for the f(a',b') case will happen to the person who first
combines the libraries for A' and B'. If those libraries are buried
somewhere deep down in the software layers, that person may not even be
aware of both A' and B', in will also be the person least equipped to
diagnose the problem when it happens.
As an aside note, this kind of combination effect is what integration
tests are good for.
> A few comments on your essay:
> * You obviously meant 'Ring' instead of 'Group'.
Yes. I somehow never get around to fix the mathematical details.
> * It doesn't apply to Python: in Python, you can't rename inherited
> methods and 'a = d' can never mean 'hammer square peg d into round hole
> a'.
Yes, but the inability to rename isn't making things better.
> * There is a categorical oversight in your analysis: in mathematical
> terms, 'Monoid' and 'Ring' are categories, while specific algebraic
> structures (e.g. the ring of integers (ZZ, +, *)) are members of these
> categories. The instances of the classes you discuss are elements of
> these structures (e.g. the integer 42), so the classes themselves
> represent the structures. In Pythonic terms, Monoid and Ring should be
> metaclasses, which means you don't have a diamond any more, since B and
> C are instances of the same metaclass Monoid, but don't share a common
> base class.
I'm aware of that.
The problem is that the class names get unwieldy if you name them
MonoidElement.
Besides, the class for whole numbers is Integer, not IntegerElement. I'm
in good company with that category error ;-)
>> > Would that make it more or less extensible?
>>
>> More extensible, until the mechanisms are in widespread use, then it
>> will start becoming less extensible.
>>
>> My advice would be to stick with
>> - single dispatch
>
> We can't. "a + b" necessarily invokes some form of double dispatch.
Not necessarily.
Conversion is a linear operation. (Selecting the target type to convert
to is a kind of double dispatch, but it's still linear, not "bilinear".)
There are other forms of linearization. For example, when writing code
for collisions between balls, you could write double-dispatching code to
handle rubber vs. stone, rubber vs. lead, stone vs. lead.
Or you could introduce a mediating parameter, such as impulse (plus spin
etc., I'm grossly oversimplifying here).
That way, the code transforms from a double dispatch between two
materials to a single dispatch on material giving an impulse, plus a
single dispatch on material plus nonpolymorphic impulse to give an
effect (changed movement vector, for example).
>> - single inheritance
>> - finding ways to structure the logic so that these two are enough
>> - where that does not work (and we will have that), program some
>> explicit mechanism for resolving what needs to be done in what case.
>>
> Hm, you're just saying that we should avoid multiple inheritance and
> multiple dispatch. But the critical question is "How?" Could you take an
> existing example of multiple inheritance, for instance AtomicExpr, and
> explain what you think we should with it?
Sometimes it's unavoidable and you have to declare that any new types
need to be integrated at the project level.
I guess that's one of the reasons why mathematics packages are to
tightly integrated, and not easily extensible in their sets of domain types.
Multiple dispatch tends to be problematic if it is used as polymorphism:
you call f(a',b'), test that it works by inspecting f[A',B], and then
some future change of the type hierarchy makes Python choose f[A,B'] and
suddenly you get a bug.
If you make sure that there is an explicit definition for f[A',B'], even
if it just calls a precursor function, no change in the type hierarchy
(or Python's MRO algorithm) will break known and tested code paths.
In C++ terms, the advice would translate to "use overloading in
preference to virtual function overriding, and do not rely on implicit
conversion rules".
The other advice would be to move away from coding and towards rule
specification (as far as possible). Checking the existing definitions
for completeness and soundness is easier if they are encoded as data
structures, not as Python code.
Of course, that's not always possible. I know no easy, 100%,
no-tradeoffs solution to this kind of problem.
Aaron Meurer
You could use Integer to name an element and Integers to name the whole class.
>
>
>>> > Would that make it more or less extensible?
>>>
>>> More extensible, until the mechanisms are in widespread use, then it
>>> will start becoming less extensible.
>>>
>>> My advice would be to stick with
>>> - single dispatch
>>
>>
>> We can't. "a + b" necessarily invokes some form of double dispatch.
>
>
> Not necessarily.
> Conversion is a linear operation. (Selecting the target type to convert to
> is a kind of double dispatch, but it's still linear, not "bilinear".)
I think what he means is that literally a + b (as opposed to add(a, b)
or some other way) uses Python's rules for evaluating operators, which
is double dispatch. If a.__add__ does not know about b, then
b.__radd__ is called. The only other way is to raise an exception or
to return a nonsense value, neither of which is helpful.
>
> There are other forms of linearization. For example, when writing code for
> collisions between balls, you could write double-dispatching code to handle
> rubber vs. stone, rubber vs. lead, stone vs. lead.
> Or you could introduce a mediating parameter, such as impulse (plus spin
> etc., I'm grossly oversimplifying here).
> That way, the code transforms from a double dispatch between two materials
> to a single dispatch on material giving an impulse, plus a single dispatch
> on material plus nonpolymorphic impulse to give an effect (changed movement
> vector, for example).
But to be as general as possible, you have to allow dispatch. We want
to allow objects that do all kinds of crazy things, which may seem to
be out of place in the usual sense. To use your example, what if we
wanted to make a magic ball that, when collided with by another ball,
does nothing but make the other ball disappear. That may sound like an
odd example, but it's more or less the idea at
http://code.google.com/p/sympy/issues/detail?q=1336, which might be
considered as an interesting corner case to study in this dispatch
system.
To try to take the analogy in another direction, what if we wanted to
make special balls that can colide only with certain specific partner
balls? Otherwise, the collision is just not allowed. Again, it
sounds strange in this example, but that is exactly what we want to be
able to do with MatrixSymbols. Two MatrixSymbols should not be
allowed to multiply each other unless their inner dimensions are
equal. They should not be able to add unless both dimensions are
equal.
We can't possibly make a physics engine (which is basically what your
impuls + spin + etc. idea is) that handles all these cases, because we
want to be able to define our own physics. The concept sounds absurd
when talking about physics, but it makes perfect sense in mathematics,
where the same concepts are used to mean things that are very similar,
but technically different, such as multiplication of complex numbers
and multiplication of matrices. You might say, "those are different
concepts, they should be implemented separately," but you can also
multiply a complex number with a matrix, so it's impossible to really
unintwine the two concepts in a truly extensible system.
Sure if we wanted to just allow one "kind" of physics, we could just
use a physics engine. That is what we are doing now with Mul.flatten.
But it's become quite clear that this is very difficult to extend
when done this way, precisely because we have the container trying to
figure out how to do the canonicalization, rather than the objects
just telling the container how to do it (or some other method).
This sounds good, though I can think of some arguments why you might
want to stick with code:
- If you are not careful, it's quite possible to make data much less
easy to read and follow than code. For example, at least with code,
you know exactly what path things will take (assuming you know the
rules of dispatch).
- You have to be careful if you separate the code from the rules that
you still allow things to be extensible. Of course, if you do it
right, it might be even easier to extend (like with the separate
canonicalizer idea).
- Existing code coverage tools make it easier to check the test
coverage when the rules are in code.
- Code can be much simpler if the rules follow some kind of pattern,
because you can then just code the pattern. You might say that that's
also possible with data, but then you are just doing things in code
anyway, but in a more circuitous way.
Don't get me wrong. Data has advantages too, such as making it much
easier to check for duplicate or even wrong rules. But it isn't
always the best way.
Aaron Meurer
Joachim Durchholz
>>> * There is a categorical oversight in your analysis: in mathematical
>>> terms, 'Monoid' and 'Ring' are categories, while specific algebraic
>>> structures (e.g. the ring of integers (ZZ, +, *)) are members of these
>>> categories.
>>
>> The problem is that the class names get unwieldy if you name them
>> MonoidElement.
>> Besides, the class for whole numbers is Integer, not IntegerElement. I'm in
>> good company with that category error ;-)
>
> You could use Integer to name an element and Integers to name the whole class.
That won't work. A class name of "Monoids" has all the wrong connotations.
Besides, all programming languages that I know about says "Integer", not
"Integers". I'm talking to programmers there, not to category theorists,
so I'm sticking with established terminology with that.
>>>> > Would that make it more or less extensible?
>>>>
>>>> More extensible, until the mechanisms are in widespread use, then it
>>>> will start becoming less extensible.
>>>>
>>>> My advice would be to stick with
>>>> - single dispatch
>>>
>>>
>>> We can't. "a + b" necessarily invokes some form of double dispatch.
>>
>>
>> Not necessarily.
>> Conversion is a linear operation. (Selecting the target type to convert to
>> is a kind of double dispatch, but it's still linear, not "bilinear".)
>
> I think what he means is that literally a + b (as opposed to add(a, b)
> or some other way) uses Python's rules for evaluating operators, which
> is double dispatch. If a.__add__ does not know about b, then
> b.__radd__ is called. The only other way is to raise an exception or
> to return a nonsense value, neither of which is helpful.
Ah, okay.
Still, "a + b" does not "necessarily" invoke a double dispatch, even if
Python does something along these lines.
>> There are other forms of linearization. For example, when writing code for
>> collisions between balls, you could write double-dispatching code to handle
>> rubber vs. stone, rubber vs. lead, stone vs. lead.
>> Or you could introduce a mediating parameter, such as impulse (plus spin
>> etc., I'm grossly oversimplifying here).
>> That way, the code transforms from a double dispatch between two materials
>> to a single dispatch on material giving an impulse, plus a single dispatch
>> on material plus nonpolymorphic impulse to give an effect (changed movement
>> vector, for example).
>
> But to be as general as possible, you have to allow dispatch.
Sure.
All I'm maintaining is that you can't have full modularity if you want
full generality.
> We want
> to allow objects that do all kinds of crazy things, which may seem to
> be out of place in the usual sense. To use your example, what if we
> wanted to make a magic ball that, when collided with by another ball,
> does nothing but make the other ball disappear.
What if somebody else defines a material that doubles its weight on
every collision, and a self-weight-doubler and an
other's-weight-nullifier ball interact?
IOW fully general double dispatch means you have to think about and fill
out ALL cells in the matrix.
Which means that the matrix cannot be extended in more than one
direction independently.
> That may sound like an
> odd example, but it's more or less the idea at
> http://code.google.com/p/sympy/issues/detail?q=1336, which might be
> considered as an interesting corner case to study in this dispatch
> system.
I see.
I think the problem here is that we have different kinds of arithmetic
in different contexts.
Inside O notation, we don't care about constants. For integration
result, we don't care about additive constants. When multiplying the
sides of an equation with a factor, all we care about is that the factor
is not zero; with inequalities, we also need to consider the sign of the
factor.
Maybe the best way to deal with this is to have a RuleSet class: a list
of allowed transformations.
And we'd have a different rulesets depending on context: for
transforming isolated arithmetic expressions, for transforming
equations, for transforming expressions inside an integral, for
boolean/temporal/higher-order logic etc.
Here, it is the Context (or RuleSet) that does the "linearization".
>> The other advice would be to move away from coding and towards rule
>> specification (as far as possible). Checking the existing definitions for
>> completeness and soundness is easier if they are encoded as data structures,
>> not as Python code.
>> Of course, that's not always possible. I know no easy, 100%, no-tradeoffs
>> solution to this kind of problem.
>
> This sounds good, though I can think of some arguments why you might
> want to stick with code:
>
> - If you are not careful, it's quite possible to make data much less
> easy to read and follow than code. For example, at least with code,
> you know exactly what path things will take (assuming you know the
> rules of dispatch).
Yes, that can become a problem.
For code, we have debuggers that follow each step of application. For
data, there's no way to set a breakpoint.
On the plus side, data is easier to decompose, so it's easier to strip
the irrelevant parts of some problematic behaviour.
> - You have to be careful if you separate the code from the rules that
> you still allow things to be extensible. Of course, if you do it
> right, it might be even easier to extend (like with the separate
> canonicalizer idea).
Making it easier to extend is usually not a problem.
> - Existing code coverage tools make it easier to check the test
> coverage when the rules are in code.
Testing the rules themselves: Yes.
Counter-question: Do we actually do code coverage analysis?
> - Code can be much simpler if the rules follow some kind of pattern,
> because you can then just code the pattern. You might say that that's
> also possible with data, but then you are just doing things in code
> anyway, but in a more circuitous way.
Patterns can be factored out in code just as in data.
> Don't get me wrong. Data has advantages too, such as making it much
> easier to check for duplicate or even wrong rules. But it isn't
> always the best way.
I guess a lot depends on the design of the library.
If the data is easy to understand and verify, there are no problems.
If the data become complicated, start to need tool support for
inspecting, verifying and debugging the data, and things can become
pretty ugly; for example, having more than two, at most three fallback
levels usually means that people get into trouble determining which
fallback level is going to handle some given case.
Aaron Meurer
Right, we have to accept that there will be certain combinations that
are undefined with this, because of conflicting rules. That's
actually an important consideration, and one of the reasons that I
wanted to make that wiki page that lists everything. FWIW, I think
that undefined combinations should remain just that, undefined, i.e.,
they can return anything within the constructs of either definition.
>
>
>> That may sound like an
>>
>> odd example, but it's more or less the idea at
>> http://code.google.com/p/sympy/issues/detail?q=1336, which might be
>> considered as an interesting corner case to study in this dispatch
>> system.
>
>
> I see.
>
> I think the problem here is that we have different kinds of arithmetic in
> different contexts.
> Inside O notation, we don't care about constants. For integration result, we
> don't care about additive constants. When multiplying the sides of an
> equation with a factor, all we care about is that the factor is not zero;
> with inequalities, we also need to consider the sign of the factor.
I forgot about O-notation. That's actually very similar to the
constant idea, and, unlike the constants, it is currently special
cased very heavily in the core canonicalization routines.
Yes. See the bin/coverage_report.py script. Thanks to the work of
people like Chris, and many of our GCI students, we actually have
pretty good coverage right now.
>
>
>> - Code can be much simpler if the rules follow some kind of pattern,
>> because you can then just code the pattern. You might say that that's
>> also possible with data, but then you are just doing things in code
>> anyway, but in a more circuitous way.
>
>
> Patterns can be factored out in code just as in data.
No, I meant that patterns can be factored out only in code, not in
data. Because you have the full power of programmability when you do
things in code, whereas data will be limited to whatever level of
power you give it (unless you essentially invent your own programming
language, which again would be circuitous and a waste of time).
Aaron Meurer
>
>
>> Don't get me wrong. Data has advantages too, such as making it much
>> easier to check for duplicate or even wrong rules. But it isn't
>> always the best way.
>
>
> I guess a lot depends on the design of the library.
> If the data is easy to understand and verify, there are no problems.
> If the data become complicated, start to need tool support for inspecting,
> verifying and debugging the data, and things can become pretty ugly; for
> example, having more than two, at most three fallback levels usually means
> that people get into trouble determining which fallback level is going to
> handle some given case.
>
>
Ronan Lamy
> Am 11.03.2012 05:21, schrieb Aaron Meurer:
> >>> * There is a categorical oversight in your analysis: in mathematical
> >>> terms, 'Monoid' and 'Ring' are categories, while specific algebraic
> >>> structures (e.g. the ring of integers (ZZ, +, *)) are members of these
> >>> categories.
> >>
> >> I'm aware of that.
> >> The problem is that the class names get unwieldy if you name them
> >> MonoidElement.
> >> Besides, the class for whole numbers is Integer, not IntegerElement. I'm in
> >> good company with that category error ;-)
> >
> > You could use Integer to name an element and Integers to name the whole class.
>
> That won't work. A class name of "Monoids" has all the wrong connotations.
> Besides, all programming languages that I know about says "Integer", not
> "Integers". I'm talking to programmers there, not to category theorists,
> so I'm sticking with established terminology with that.
'Monoid' is a kind of structure, 'integer' is a kind of number. They
aren't on the same level. But I agree that the name of a class should be
the (uppercase version of the) name designating an arbitrary instance of
the class, so the parallels are Integer/MonoidElement and Ring/Monoid.
However, there's another fundamental cause of confusion here.
Mathematically, a set and an algebraic structure over that set aren't
the same thing. If you call the set of integers ZZ, the ring of integers
is (ZZ, +, *), which "contains" 2 monoids: (ZZ, +) and (ZZ, *).
So, integers should be instances of the class Integer and we should,
separately, have an integer_ring object which is an instance of the
class Ring(). On the monoid side, things are a bit different because
MonoidElement is presumably a generic class that should work for any
monoid. So, MonoidElement instances need a reference to the instance of
Monoid they belong to. To have integers fit with this generic framework,
we need a similar RingElement class, with signature RingElement(ring,
*params) and Integer should subclass it, so that Integer(n) is
Liskov-substitutable for RingElement(integer_ring, n).
Joachim Durchholz
> 'Monoid' is a kind of structure, 'integer' is a kind of number. They
> aren't on the same level.
Ah, agreed.
> But I agree that the name of a class should be
> the (uppercase version of the) name designating an arbitrary instance of
> the class, so the parallels are Integer/MonoidElement and Ring/Monoid.
Yes, except MonoidElement is a somewhat unwieldy name for a class.
Besides, the class defines Monoid axioms, so one could still argue that
Monoid, if a category error, is still describing the purpose of the
class well (but not the elements).
Things get even unclearer if you consider that Monoid may be used for a
symbolic math system (not SymPy, Python cannot fully handle diamond
inheritance anyway). In such a situation, Monoid would probably also
have functions that operate on the monoid itself, in which case one
could argue that Monoid is really the better name.
Not that I'm actually arguing for any of these possibilities; it's
pretty unclear to me what the best naming policy would be.
Fortunately, the essay is about multiple inheritance, not about setting
up a type hierarchy for math, so the whole issue isn't too important.
Not in that context anyway :-)
> However, there's another fundamental cause of confusion here.
> Mathematically, a set and an algebraic structure over that set aren't
> the same thing. If you call the set of integers ZZ, the ring of integers
> is (ZZ, +, *), which "contains" 2 monoids: (ZZ, +) and (ZZ, *).
>
> So, integers should be instances of the class Integer and we should,
> separately, have an integer_ring object which is an instance of the
> class Ring().
Yes, that construction would work.
> On the monoid side, things are a bit different because
> MonoidElement is presumably a generic class that should work for any
> monoid.
Ring would be generic, too, and just in the same way as Monoid.
The difference is that we don't need that genericity inside the current
example, but we'd have a Ring<Integer,+,*>, a Ring<Vector<?>,+,*> (I'm
being awfully sloppy here), etc.
> So, MonoidElement instances need a reference to the instance of
> Monoid they belong to. To have integers fit with this generic framework,
> we need a similar RingElement class, with signature RingElement(ring,
> *params) and Integer should subclass it, so that Integer(n) is
> Liskov-substitutable for RingElement(integer_ring, n).
Should work, too.
Not in Python, though. You still don't have the ability to inherit the
Monoid operator twice into Ring and name it + for the additive monoid
and * for the multiplicative monoid.
Of course you could say that Ring is just a container for two Monoids,
but it would become a bit cumbersome: when writing code that deals with
a Monoid variable m, you'd be forced to write m.additive.op and
m.multiplicative.op instead of m.plus and m.times.
If you define m.plus as a new function that does m.multiplicative.op,
you'll be unable to use a group polymorphically instead of a monoid.
Hmm. Okay. You can use the m.plus function where you know you're dealing
with a Group, and m.additive to pass it to code that expects a Monoid.
I'm not 100% sure that this will hold up in all situations, but it
covers the most important cases anyway.
Joachim Durchholz
>> IOW fully general double dispatch means you have to think about and fill out
>> ALL cells in the matrix.
>> Which means that the matrix cannot be extended in more than one direction
>> independently.
>
> Right, we have to accept that there will be certain combinations that
> are undefined with this, because of conflicting rules. That's
> actually an important consideration, and one of the reasons that I
> wanted to make that wiki page that lists everything. FWIW, I think
> that undefined combinations should remain just that, undefined, i.e.,
> they can return anything within the constructs of either definition.
In that case you'd have to check that both constructs Do The Right Thing.
Otherwise, changes somewhere up the hierarchy might make any unit test
that uses subclasses fail.
I'd suggest making the undefined matrix cells truly undefined, i.e.
calling them throws an error. That forces whoever integrates two type
hierarchies to make sure that the combinations are correct (probably by
contacting the authors of the extensions and work the combination out).
>> Counter-question: Do we actually do code coverage analysis?
>
> Yes. See the bin/coverage_report.py script. Thanks to the work of
> people like Chris, and many of our GCI students, we actually have
> pretty good coverage right now.
Ah, sweet. I wasn't aware of that.
>>> - Code can be much simpler if the rules follow some kind of pattern,
>>> because you can then just code the pattern. You might say that that's
>>> also possible with data, but then you are just doing things in code
>>> anyway, but in a more circuitous way.
>>
>> Patterns can be factored out in code just as in data.
>
> No, I meant that patterns can be factored out only in code, not in
> data. Because you have the full power of programmability when you do
> things in code, whereas data will be limited to whatever level of
> power you give it
More power also means more potential for unexpected side effects.
I still stand by my words.
Aaron Meurer
> Am 11.03.2012 22:48, schrieb Aaron Meurer:
>
>>> IOW fully general double dispatch means you have to think about and fill
>>> out
>>> ALL cells in the matrix.
>>> Which means that the matrix cannot be extended in more than one direction
>>> independently.
>>
>>
>> Right, we have to accept that there will be certain combinations that
>> are undefined with this, because of conflicting rules. That's
>> actually an important consideration, and one of the reasons that I
>> wanted to make that wiki page that lists everything. FWIW, I think
>> that undefined combinations should remain just that, undefined, i.e.,
>> they can return anything within the constructs of either definition.
>
>
> In that case you'd have to check that both constructs Do The Right Thing.
> Otherwise, changes somewhere up the hierarchy might make any unit test that
> uses subclasses fail.
>
> I'd suggest making the undefined matrix cells truly undefined, i.e. calling
> them throws an error. That forces whoever integrates two type hierarchies to
> make sure that the combinations are correct (probably by contacting the
> authors of the extensions and work the combination out).
One problem is that it's not really a Matrix. Classes like Mul and
Add are container objects that can hold any number of items. If we
want to assert commutativity and associativity (the latter is actually
implied by the n-ary-ness of the container), we must define operations
on any combination. In practice, this isn't an issue because rules can
be generalized. oo combines with any finite real number in an Add, no
matter how many there are, for example.
Aaron Meurer
>
>
>>> Counter-question: Do we actually do code coverage analysis?
>>
>>
>> Yes. See the bin/coverage_report.py script. Thanks to the work of
>> people like Chris, and many of our GCI students, we actually have
>> pretty good coverage right now.
>
>
> Ah, sweet. I wasn't aware of that.
>
>
>>>> - Code can be much simpler if the rules follow some kind of pattern,
>>>> because you can then just code the pattern. You might say that that's
>>>> also possible with data, but then you are just doing things in code
>>>> anyway, but in a more circuitous way.
>>>
>>>
>>> Patterns can be factored out in code just as in data.
>>
>>
>> No, I meant that patterns can be factored out only in code, not in
>> data. Because you have the full power of programmability when you do
>> things in code, whereas data will be limited to whatever level of
>> power you give it
>
>
> More power also means more potential for unexpected side effects.
> I still stand by my words.
>
>
Alexey U. Gudchenko
> It seems that this is not sustainable because 1. Adding too much
> stuff to Mul and Add
> https://code.google.com/p/sympy/issues/detail?id=1941
Current situation with the flatten, how I imagine it.
Correct me If I am mistaken.
1. `flatten` is the method for associative operations `AssocOp`.
(a op b) op c == a op (b op c) == a op b op c.
`Add` and `Mul` are inherited from AssocOp, which in its turns is
inherited from Expr.
See picture
https://github.com/sympy/sympy/wiki/UD-Core-Docs
2. The original aim for this method was the flatting of the associative
operation trees (the 'name-token' about it.):
Add( x, Add(y, z)) --> Add(x, y, z)
This logic is implemented in AssocOp.flatten
3. Then the commutative and non-commutative symbols was introduced, so
the `flatten` return a few lists: commutative, non commutative.
(Additionally the `order_symbols` is resulted.)
4. Then the problem was raised how to check an equality of two `Expr`
quickly.
x + y = y + z
This problem was solved with the help of the hashes. Hash of the `Add` is
basically hash of the tuple of argument's hashes.
hash(Add(x, y)) == hash(Add.args).
5. The problem of the equality 'x + y' and 'y + x' (commutative case),
was solved with the aim of so-called `canonical ordering` of arguments.
Note, that this sorting is something random and unexpected, because it
is simply based on the sorting of python's hashes (and therefore it
depends on the machine and bits)
Also, there is this comment in code of Add.flatten
# order args canonically
# Currently we sort things using hashes, as it is quite fast. A
better
# solution is not to sort things at all - but this needs some more
# fixing. NOTE: this is used in primitive, too, so if it changes
# here it should be changed there.
In PR 722 I successfully remove this sorting.
6. Note, that ordering of the arguments is implemented and for printing
system also, independently.
(display the objects in a standard sort)
Also sorting of terms is used in classes such as polynomials by them own
internally.
So, the `Canonicalization` is used in a few places and have variouse
aims, (And the aim `help with campare objects` of canonicalization
encapsulated in flatten, not in the hash calculation, is falsly I think)
7. Also, in the constructors of `Add` and `Mul` (in `flatten` now),
there is the so called `simplification-on-the-fly` algorithms.
In particular:
a) Add.flatten: collect similar terms in (x + 2y + 3x --> 4x + 2y)
b) Mul.flatten: convert 1/(x*y) --> x**(-1)*y**(-1)
Conclusion:
We should document and *split* tasks, aims and implementation for:
- flatten
- hashing for comparison
- canonical sorting (for printing, or polytools)
- simplification-on-the-fly
- commutative, non-commutative cases problems.
If we can split the flatten, then (I think) there are no problems with
**It seems that this is not sustainable because 1. Adding too much stuff
to Mul and Add
https://code.google.com/p/sympy/issues/detail?id=1941**
Just polymorph those methods for other objects.
> Commutativity also means that the order of the final expression can
(and should)
> be canonicalized, so that it's easy to assert that x*y == y*x
I think no, we shouldn't.
The comparison algorithm must be separated from `flatten` method.
It can be implemented with the help of hash calculation function,
so it is sufficient to encapsulate the sorting function to the
`_hashable_content`.
--
Alexey U.
Joachim Durchholz
> One problem is that it's not really a Matrix. Classes like Mul and
> Add are container objects that can hold any number of items.
Heh. That would be an infinitely-dimensional hypercube.
I hadn't expected to see that in my career :-)
> If we
> want to assert commutativity and associativity (the latter is actually
> implied by the n-ary-ness of the container), we must define operations
> on any combination.
Urk.
> In practice, this isn't an issue because rules can
> be generalized.
Exactly - that's conversion, not multiple dispatch.
I know of three techniques to deal with varying parameter values:
- Multiple dispatch. Most general, not independently extensible.
- Conversion to the most general common type, along a hierarchy.
Independently extensible.
Less flexible than MD: you cannot (easily) special-case a
specific type combination.
- Overloading. Requires explicit definition of each combination.
Restricted to static types (i.e. useless for dynamic languages
which don't have static types anyway).
Aaron Meurer
I think maybe a problem is that some code assumes that a == b implies
that a.args == b.args. We'd have to try it and run the tests to see
how ingrained this is (but I seem to remember removing the ordering
from Add, and a *ton* of tests failed, but that may have just been
because I failed to correctly redefine __eq__).
But it would be interesting if we could do something like x*y and y*x
and keep the order, but still have them compare equal. Then, we could
make the printer give things in exactly the order they were entered,
for example.
Aaron Meurer
>
> It can be implemented with the help of hash calculation function,
> so it is sufficient to encapsulate the sorting function to the
> `_hashable_content`.
>
>
>
>
> --
> Alexey U.
>
krastano...@gmail.com
Alexey U. Gudchenko
I tried to remove the ordering in PR 722 (rebased it today)
Without redefining __eq__, but with changes in hashable_content, and
remove some another random reordering.
Change some tests to be valid.
For 64-bit (python 2.7.2, 2.5.5, 3.2.2 they all ok.
http://reviews.sympy.org/pullrequest/722
but on 32-bit I meet two fails, which I investigate now.
--
Alexey U.