digitalmars.D - Commutative operators and matrix
- Vladimir (9/9) Apr 07 2005 D manual says that compiler always treats '*' as commutative operator.
- Thomas Kuehne (15/22) Apr 07 2005 -----BEGIN PGP SIGNED MESSAGE-----
- Norbert Nemec (7/16) Apr 10 2005 Actually, the specs do not force '*' and '+' to be commutative, they
- Vladimir (15/21) Apr 11 2005 Suppose I have the following code:
- Norbert Nemec (33/55) Apr 11 2005 You seem to misunderstand something:
- Vladimir (19/77) Apr 12 2005 In my example v*m means transponse(v)*m which is legal. v is a vector an...
- Norbert Nemec (31/31) Apr 20 2005 Hi Vladimir,
- Vladimir (18/60) Apr 21 2005 Thanks for good summary. Yes, you are right. If library written in corre...
- Norbert Nemec (5/11) Apr 21 2005 Guess, the additional complication really is the reason here. Also, be
- TechnoZeus (3/19) Apr 21 2005 Where can one find these "new specs"?
- Norbert Nemec (3/4) Apr 22 2005 "New specs" is what you find on the regular page now. "Old specs" is,
- TechnoZeus (3/7) Apr 23 2005 Okay. Thoought so, but... good to have my assumption verified.
D manual says that compiler always treats '*' as commutative operator.
It does not allow to implement matrix class (for matrix '*' is not
commutative).
This is just a simple example, for some mathematical quantities even '+' is
not commutative. May be at some point D language will be used by
mathematicians too ? (C++ already does).
Does anyone really need to force '*' and '+' to be commutative ?
--
Vladimir
Apr 07 2005
Thomas Kuehne <thomas-dloop kuehne.thisisspam.cn> -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Vladimir schrieb am Thu, 07 Apr 2005 11:46:23 +0400:D manual says that compiler always treats '*' as commutative operator. It does not allow to implement matrix class (for matrix '*' is not commutative). This is just a simple example, for some mathematical quantities even '+' is not commutative. May be at some point D language will be used by mathematicians too ? (C++ already does). Does anyone really need to force '*' and '+' to be commutative ?How about stating that operations between the following types are commutative but that the compiler assumes all operations between other types aren't treated as non-communtative? types: byte ubyte short ushort int uint long ulong cent ucent float double real ifloat idouble ireal cfloat cdouble creal Thomas -----BEGIN PGP SIGNATURE----- iD8DBQFCVOzW3w+/yD4P9tIRAn7kAKCopZxBS4B3i1ldyUPmzlZt27t8pwCgoPXU LvcIFGuKyCNBUg50BwTatTI= =w+ze -----END PGP SIGNATURE-----
Apr 07 2005
Actually, the specs do not force '*' and '+' to be commutative, they just make them commutative by default. The compiler will only swap operands if there is no overload for the given order. Meaning - if all combinations of types are correctly implemented, commutation will never happen. Actually, this is due to a slight change in the specs a few months ago. Vladimir schrieb:D manual says that compiler always treats '*' as commutative operator. It does not allow to implement matrix class (for matrix '*' is not commutative). This is just a simple example, for some mathematical quantities even '+' is not commutative. May be at some point D language will be used by mathematicians too ? (C++ already does). Does anyone really need to force '*' and '+' to be commutative ?
Apr 10 2005
Norbert Nemec wrote:Actually, the specs do not force '*' and '+' to be commutative, they just make them commutative by default. The compiler will only swap operands if there is no overload for the given order. Meaning - if all combinations of types are correctly implemented, commutation will never happen.Suppose I have the following code: class Vector { Matrix opCast(); } class Matrix { Vector opMul(Vector v); } Vector v; Matrix m, m1; m1 = v*m; Last line is treated as m.opMul(v).opCast() that is m*v and my program works well. And than I'm deciding to add opMul_r to class Matrix: Matrix opMul_r(Vector v); and my line change it's meaning to m.opMul_r(v) which is totally different and *sould* be different ! Now my program is broken. And compiller will never help me to find this bug.Actually, this is due to a slight change in the specs a few months ago.-- Vladimir
Apr 11 2005
Vladimir schrieb:Norbert Nemec wrote:You seem to misunderstand something: Regularly, i.e. without commutation, "m*v" is mapped to "m.opMul(v)", just like "m/v" would be mapped to "m.opDiv(v)" Therefore, if you write the above, you are already exploiting the implicit commutation, which is probably not what you want: The compiler finds "v*m" realizes, that there is no "Vector.opMul(Matrix)", so it continues searching with "Matrix.opMul_r(Vector)" (still no commutation done) and only after it did not find that, it falls back to the routine you defined, using the commutation of the product. In general, your example seems rather flawed, since "v*m" is mathematically illegal if you follow the usual convention of interpreting "v" as a column vector. Furthermore, "m*v" will produce a vector, and casting a vector to a matrix seems a rather weird thing to do.Actually, the specs do not force '*' and '+' to be commutative, they just make them commutative by default. The compiler will only swap operands if there is no overload for the given order. Meaning - if all combinations of types are correctly implemented, commutation will never happen.Suppose I have the following code: class Vector { Matrix opCast(); } class Matrix { Vector opMul(Vector v); } Vector v; Matrix m, m1; m1 = v*m; Last line is treated as m.opMul(v).opCast() that is m*v and my program works well.And than I'm deciding to add opMul_r to class Matrix: Matrix opMul_r(Vector v); and my line change it's meaning to m.opMul_r(v) which is totally different and *sould* be different ! Now my program is broken. And compiller will never help me to find this bug.Actually, this is correct behavior: translating the (mathematical nonsensical) "v*m" to m.opMul_r(v) does not involve a commutation, so that is what the compiler prefers. The rules for commutative operators in D are written in such a way that adding routines will never introduce illegal commutations. Only if a routine is missing, the compiler might fall back to trying commuting the operators. What you would want to do in the above example, is to introduce both all variants: Matrix.opMul(Vector) (or alternatively Vector.opMul_r(Matrix) to implement the regular multiplication Vector.opMul(Matrix) or alternatively Matrix.opMul_r(Vector) raising an error (preferrably a compile-time error, but that is not possible in D) the second definition is necessary to detect bugs like your above "v*m"-expression. Greetings, Norbert
Apr 11 2005
Norbert Nemec wrote:I do understand it.You seem to misunderstand something: Regularly, i.e. without commutation, "m*v" is mapped to "m.opMul(v)", just like "m/v" would be mapped to "m.opDiv(v)" Therefore, if you write the above, you are already exploiting the implicit commutation, which is probably not what you want: The compiler finds "v*m" realizes, that there is no "Vector.opMul(Matrix)", so it continues searching with "Matrix.opMul_r(Vector)" (still no commutation done) and only after it did not find that, it falls back to the routine you defined, using the commutation of the product.Actually, the specs do not force '*' and '+' to be commutative, they just make them commutative by default. The compiler will only swap operands if there is no overload for the given order. Meaning - if all combinations of types are correctly implemented, commutation will never happen.Suppose I have the following code: class Vector { Matrix opCast(); } class Matrix { Vector opMul(Vector v); } Vector v; Matrix m, m1; m1 = v*m; Last line is treated as m.opMul(v).opCast() that is m*v and my program works well.In general, your example seems rather flawed, since "v*m" is mathematically illegal if you follow the usual convention of interpreting "v" as a column vector.In my example v*m means transponse(v)*m which is legal. v is a vector and transponse(v) is 1-form, but it can be denoted by one letter becouse of isomorphism of vectors and 1-forms, and in any expression it's obvious what that letter means: vector or 1-form.Furthermore, "m*v" will produce a vector, and casting a vector to a matrix seems a rather weird thing to do.I do not understand why. Vector is just a kind of matrix.In my example I've tried to show not a compiller bug, but rather possible user bugs. Just imagine: I wrote a library for linear algebra. Someone used my library, and (by mistake) wrote v*m instead of m*v. And than I extent my library by adding Vector.opMul(Matrix). Now program is broken. Not by modifying something, but just by defining one method. And just imagine, how hard is to find this bug.And than I'm deciding to add opMul_r to class Matrix: Matrix opMul_r(Vector v); and my line change it's meaning to m.opMul_r(v) which is totally different and *sould* be different ! Now my program is broken. And compiller will never help me to find this bug.Actually, this is correct behavior: translating the (mathematical nonsensical) "v*m" to m.opMul_r(v) does not involve a commutation, so that is what the compiler prefers. The rules for commutative operators in D are written in such a way that adding routines will never introduce illegal commutations. Only if a routine is missing, the compiler might fall back to trying commuting the operators.What you would want to do in the above example, is to introduce both all variants: Matrix.opMul(Vector) (or alternatively Vector.opMul_r(Matrix) to implement the regular multiplication Vector.opMul(Matrix) or alternatively Matrix.opMul_r(Vector) raising an error (preferrably a compile-time error, but that is not possible in D)This is static assert(0), isn't it ?the second definition is necessary to detect bugs like your above "v*m"-expression.Yes, you are right, I can do it. But if I forget, that will be a bug. Without commutation rules, I just do not see a way to introduce such a bug.Greetings, Norbert-- Vladimir
Apr 12 2005
Hi Vladimir,
I must confess that I'm somewhat lost in your argumentation. Your
original code seems so twisted, that it is hard to tell what the core
problem is.
Independent of mathematical issues of vectors, 1-forms, matrices,
implicit and explicit casting between them and so on, I see the one
fundamental problem: You original code was:
class Vector { Matrix opCast(); }
class Matrix { Vector opMul(Vector v); }
Vector v; Matrix m, m1;
m1 = v*m;
In this code, the given opMul is only called *because* the compiler does
implicit commutation of the "*"-operator. The compiler first checks
whether it can resolve Vector.opMul(Matrix) directly. Only after this is
not found, it commutes the factors and falls back to the given routine.
Of course, if you now implement the uncommuted routine, the behavior of
the code will change, because the compiler will always prefer to avoid
commutation if that is possible.
The general behavior of the language specs is: use commutation only as a
last resort, if the uncommuted routine is not specified.
The key to write a library that does not break in the way you describe
is to always specify both orders to avoid illegal implicit commutations.
If both order are to be legal but different, it is clear that both have
to be implemented. If only one order is to be legal, still both have to
be implemented with the illegal one throwing a runtime exception.
Once both orders are correctly implemented in some way, adding
additional methods will not change the behavior and there is no risk of
hard-to-find bugs.
Hope, this clears up the situation?
Greetings,
Norbert
Apr 20 2005
Norbert Nemec wrote:
Hi Vladimir,
I must confess that I'm somewhat lost in your argumentation. Your
original code seems so twisted, that it is hard to tell what the core
problem is.
Independent of mathematical issues of vectors, 1-forms, matrices,
implicit and explicit casting between them and so on, I see the one
fundamental problem: You original code was:
class Vector { Matrix opCast(); }
class Matrix { Vector opMul(Vector v); }
Vector v; Matrix m, m1;
m1 = v*m;
In this code, the given opMul is only called *because* the compiler does
implicit commutation of the "*"-operator. The compiler first checks
whether it can resolve Vector.opMul(Matrix) directly. Only after this is
not found, it commutes the factors and falls back to the given routine.
Of course, if you now implement the uncommuted routine, the behavior of
the code will change, because the compiler will always prefer to avoid
commutation if that is possible.
The general behavior of the language specs is: use commutation only as a
last resort, if the uncommuted routine is not specified.
The key to write a library that does not break in the way you describe
is to always specify both orders to avoid illegal implicit commutations.
If both order are to be legal but different, it is clear that both have
to be implemented. If only one order is to be legal, still both have to
be implemented with the illegal one throwing a runtime exception.
Once both orders are correctly implemented in some way, adding
additional methods will not change the behavior and there is no risk of
hard-to-find bugs.
Hope, this clears up the situation?
Greetings,
Norbert
Thanks for good summary. Yes, you are right. If library written in correct
way compiler won't do anything unexpected.
I've just said that this could be error-prone.
One more point. If compiler tries to commutate '+' operator, why it can't
also try rewrite
a-b as a + (-b)
a&b as ~(~a | ~b)
a%b as a - (a/b)*b
and so on ? I think because it's too complicated.
I think this is done in right way in C++ boost::operators library
(http://www.boost.org/libs/utility/operators.htm) where you can specify
what kind of arithmetics support your object by deriving from templates
such as equivalent<T, U>, partially_ordered<T, U>, equality_comparable<T,
U>, multipliable<T> and so on.
It D this can be implemented even more perfectly using mixins.
--
Vladimir
Apr 21 2005
Vladimir schrieb:One more point. If compiler tries to commutate '+' operator, why it can't also try rewrite a-b as a + (-b) a&b as ~(~a | ~b) a%b as a - (a/b)*b and so on ? I think because it's too complicated.Guess, the additional complication really is the reason here. Also, be aware that some of these mathematical identities may not hold for numerical data types. (But then, of course, commutation also is dependent of the operands.)
Apr 21 2005
Where can one find these "new specs"? TZ "Norbert Nemec" <Norbert Nemec-online.de> wrote in message news:d3cbg6$tnn$1 digitaldaemon.com...Actually, the specs do not force '*' and '+' to be commutative, they just make them commutative by default. The compiler will only swap operands if there is no overload for the given order. Meaning - if all combinations of types are correctly implemented, commutation will never happen. Actually, this is due to a slight change in the specs a few months ago. Vladimir schrieb:D manual says that compiler always treats '*' as commutative operator. It does not allow to implement matrix class (for matrix '*' is not commutative). This is just a simple example, for some mathematical quantities even '+' is not commutative. May be at some point D language will be used by mathematicians too ? (C++ already does). Does anyone really need to force '*' and '+' to be commutative ?
Apr 21 2005
TechnoZeus schrieb:Where can one find these "new specs"?"New specs" is what you find on the regular page now. "Old specs" is, what you would have found a few months ago.
Apr 22 2005
Okay. Thoought so, but... good to have my assumption verified. Thanks. "Norbert Nemec" <Norbert Nemec-online.de> wrote in message news:d4b18m$2idt$1 digitaldaemon.com...TechnoZeus schrieb:Where can one find these "new specs"?"New specs" is what you find on the regular page now. "Old specs" is, what you would have found a few months ago.
Apr 23 2005