www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Commutative operators and matrix

reply Vladimir <kv11111 mail.ru> writes:
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
next sibling parent Thomas Kuehne <thomas-dloop kuehne.thisisspam.cn> writes:
-----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
prev sibling parent reply Norbert Nemec <Norbert Nemec-online.de> writes:
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
next sibling parent reply Vladimir <kv11111 mail.ru> writes:
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.

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
parent reply Norbert Nemec <Norbert Nemec-online.de> writes:
Vladimir schrieb:
 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.

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.
 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
parent reply Vladimir <kv11111 mail.ru> writes:
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.

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.

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.

 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.

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.
 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.

Without commutation rules, I just do not see a way to introduce such a bug.
 Greetings,
 Norbert

-- Vladimir
Apr 12 2005
parent reply Norbert Nemec <Norbert Nemec-online.de> writes:
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
parent reply Vladimir <kv11111 mail.ru> writes:
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
parent Norbert Nemec <Norbert Nemec-online.de> writes:
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
prev sibling parent reply "TechnoZeus" <TechnoZeus PeoplePC.com> writes:
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
parent reply Norbert Nemec <Norbert Nemec-online.de> writes:
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
parent "TechnoZeus" <TechnoZeus PeoplePC.com> writes:
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