[Pharo-project] Fwd: [ANN] Number comparison, hash, NaN, Point, and other partially ordered sets
Stéphane Ducasse <stephane.ducasse@...> writes:
Nicolas
could you summarize your solution?
Stef
On Jan 5, 2009, at 12:55 AM, nicolas cellier wrote:
Here is the summary: 1) equality relation is not transitive due to inexact asFloat conversion example: (1/2) = 0.5. "This is exact" (1/2) + (1/(2 raisedTo: 100)) = 0.5. "This is an inexact conversion" (1/2) + (1/(2 raisedTo: 100)) ~= (1/2). "If equal where transitive, they should be equal" Solution: base comparison on inexact->exact conversions rather than the contrary... inexact->exact is called #asTrueFraction (#asExactFraction in GNU Smalltalk). This solution is known from the wise lispers for so long... http://www.lispworks.com/documentation/lcl50/aug/aug-170.html This is http://bugs.squeak.org/view.php?id=3374 2) Some numbers are equal, but have different hash codes Since some Float can equal some Integer or Fraction, it is necessary to change at least 2 out of 3 hash implementations. Solution I retained: - preserve Integer hash - change Float hash if they have a fractionPart = 0.0 (they are equal to anInteger) - change Fraction hash if they could be equal to a Float (I only test that denominator is a power of two, which is a necessary but not a sufficient condition). This is http://bugs.squeak.org/view.php?id=6601, and http://bugs.squeak.org/view.php?id=3360, solution has been posted at #3374. Note: this results in loosing a little speed for small Float hash, and lot more for large Float hash. But make it right > make it fast... 3) Comparing Float nan to a Float or an Integer does not follow IEEE 754 conventions comparison should always return false since nan cannot be ordered. Magnitude assume subInstances form a totally ordered set. Thus Number is not a well behaved Magnitude. Consequently, Number must define not only < but also <= >= and > Note that only < and <= would be strictly necessary. The other two could be defined like this:
b ^b < self = b ^b <= self
I choose to change >= implementation in Magnitude, and reimplement everything in Number subclasses (though > and >= would not be strictly necessary). This is http://bugs.squeak.org/view.php?id=6719 But the VM also makes same assumption as Magnitude and must be changed too - this is http://bugs.squeak.org/view.php?id=7260 4) Comparing a Number and a Point is weird (different result with an Integer and a Float) Float did coerce to a Point, then compare. Integer did use a false total order assumption through super Magnitude. Two main solutions: - either coerce Number to a Point (might be implicitely used this way in the image... hard to tell). - or raise an Exception Solution: I choosed to raise an Exception. This is http://bugs.squeak.org/view.php?id=7259
Thanks nicolas I like this kind of discussions because I always learn something. This is cool to have you with us. I will digest that and once marcus is getting better we will certainly start a new harvesting phase. I will probably try to allocate some time soon. We have a deadline for the 15 of January. Argh On Jan 5, 2009, at 7:38 PM, nicolas cellier wrote:
Stéphane Ducasse <stephane.ducasse@...> writes:
Nicolas
could you summarize your solution?
Stef
On Jan 5, 2009, at 12:55 AM, nicolas cellier wrote:
Here is the summary:
1) equality relation is not transitive due to inexact asFloat conversion
example: (1/2) = 0.5. "This is exact" (1/2) + (1/(2 raisedTo: 100)) = 0.5. "This is an inexact conversion" (1/2) + (1/(2 raisedTo: 100)) ~= (1/2). "If equal where transitive, they should be equal"
Solution: base comparison on inexact->exact conversions rather than the contrary... inexact->exact is called #asTrueFraction (#asExactFraction in GNU Smalltalk).
This solution is known from the wise lispers for so long... http://www.lispworks.com/documentation/lcl50/aug/aug-170.html This is http://bugs.squeak.org/view.php?id=3374
2) Some numbers are equal, but have different hash codes
Since some Float can equal some Integer or Fraction, it is necessary to change at least 2 out of 3 hash implementations.
Solution I retained: - preserve Integer hash - change Float hash if they have a fractionPart = 0.0 (they are equal to anInteger) - change Fraction hash if they could be equal to a Float (I only test that denominator is a power of two, which is a necessary but not a sufficient condition).
This is http://bugs.squeak.org/view.php?id=6601, and http://bugs.squeak.org/view.php?id=3360, solution has been posted at #3374.
Note: this results in loosing a little speed for small Float hash, and lot more for large Float hash. But make it right > make it fast...
3) Comparing Float nan to a Float or an Integer does not follow IEEE 754 conventions comparison should always return false since nan cannot be ordered.
Magnitude assume subInstances form a totally ordered set. Thus Number is not a well behaved Magnitude.
Consequently, Number must define not only < but also <= >= and > Note that only < and <= would be strictly necessary. The other two could be defined like this:
b ^b < self = b ^b <= self
I choose to change >= implementation in Magnitude, and reimplement everything in Number subclasses (though > and >= would not be strictly necessary).
This is http://bugs.squeak.org/view.php?id=6719
But the VM also makes same assumption as Magnitude and must be changed too - this is http://bugs.squeak.org/view.php?id=7260
4) Comparing a Number and a Point is weird (different result with an Integer and a Float)
Float did coerce to a Point, then compare. Integer did use a false total order assumption through super Magnitude.
Two main solutions: - either coerce Number to a Point (might be implicitely used this way in the image... hard to tell). - or raise an Exception
Solution: I choosed to raise an Exception.
This is http://bugs.squeak.org/view.php?id=7259
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
Thanks Nicolas, You made really good points! Alexandre On 5 Jan 2009, at 15:38, nicolas cellier wrote:
Stéphane Ducasse <stephane.ducasse@...> writes:
Nicolas
could you summarize your solution?
Stef
On Jan 5, 2009, at 12:55 AM, nicolas cellier wrote:
Here is the summary:
1) equality relation is not transitive due to inexact asFloat conversion
example: (1/2) = 0.5. "This is exact" (1/2) + (1/(2 raisedTo: 100)) = 0.5. "This is an inexact conversion" (1/2) + (1/(2 raisedTo: 100)) ~= (1/2). "If equal where transitive, they should be equal"
Solution: base comparison on inexact->exact conversions rather than the contrary... inexact->exact is called #asTrueFraction (#asExactFraction in GNU Smalltalk).
This solution is known from the wise lispers for so long... http://www.lispworks.com/documentation/lcl50/aug/aug-170.html This is http://bugs.squeak.org/view.php?id=3374
2) Some numbers are equal, but have different hash codes
Since some Float can equal some Integer or Fraction, it is necessary to change at least 2 out of 3 hash implementations.
Solution I retained: - preserve Integer hash - change Float hash if they have a fractionPart = 0.0 (they are equal to anInteger) - change Fraction hash if they could be equal to a Float (I only test that denominator is a power of two, which is a necessary but not a sufficient condition).
This is http://bugs.squeak.org/view.php?id=6601, and http://bugs.squeak.org/view.php?id=3360, solution has been posted at #3374.
Note: this results in loosing a little speed for small Float hash, and lot more for large Float hash. But make it right > make it fast...
3) Comparing Float nan to a Float or an Integer does not follow IEEE 754 conventions comparison should always return false since nan cannot be ordered.
Magnitude assume subInstances form a totally ordered set. Thus Number is not a well behaved Magnitude.
Consequently, Number must define not only < but also <= >= and > Note that only < and <= would be strictly necessary. The other two could be defined like this:
b ^b < self = b ^b <= self
I choose to change >= implementation in Magnitude, and reimplement everything in Number subclasses (though > and >= would not be strictly necessary).
This is http://bugs.squeak.org/view.php?id=6719
But the VM also makes same assumption as Magnitude and must be changed too - this is http://bugs.squeak.org/view.php?id=7260
4) Comparing a Number and a Point is weird (different result with an Integer and a Float)
Float did coerce to a Point, then compare. Integer did use a false total order assumption through super Magnitude.
Two main solutions: - either coerce Number to a Point (might be implicitely used this way in the image... hard to tell). - or raise an Exception
Solution: I choosed to raise an Exception.
This is http://bugs.squeak.org/view.php?id=7259
_______________________________________________ Pharo-project mailing list Pharo-project@lists.gforge.inria.fr http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/pharo-project
-- _,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;: Alexandre Bergel http://www.bergel.eu ^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;._,.;:~^~:;.
participants (3)
-
Alexandre Bergel -
nicolas cellier -
Stéphane Ducasse