On Sat, Mar 10, 2012 at 3:22 AM, Joachim Durchholz <[email protected]> wrote: > Am 09.03.2012 19:55, schrieb Ronan Lamy: > >> 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 ;-)
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). > > >>> - 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. 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 -- 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.
