Integral overflow, Order relations
bearophile
bearophileHUGS at lycos.com
Sun Aug 19 01:06:39 PDT 2007
I have used some C in the past, so I really like that D puts some efforts in avoiding some common bugs, like disallowing:
for(i= 0;i<10;i++);
while(n = func(x)) {}
I have read that in complex C/C++ programs up to 30% of all bugs are caused by integer overflow, so I think D must help the programmer avoid some simple integer bugs too, like:
writefln(-6 >= "abc".length); // Prints: true
Or even (less easy to avoid):
long n1 = -6; // (64 bit)
ulong n2 = 3; // (64 bit)
writefln(n1 >= n2); // Prints: true
The ObjectPascal language (Delphi) is a very fast statically-typed language, and it has the {$Q} compiler flag that *optionally* activates checks overflow for integral operations (so the program stops running if you go over/under the max/min value that a shortint, smallint, integer, can represent). And the following little Delphi program prints FALSE regardless the compiler flags you use:
{$APPTYPE CONSOLE}
uses
SysUtils;
var
n1: integer; // an int (32 bit)
n2: cardinal; // an uint (32 bit)
begin
n1 := -6;
n2 := 3;
writeln(n1 >= n2); // prints: FALSE
n1 := -2147483647;
n2 := 4294967295;
writeln(n1); // prints: -2147483647
writeln(n2); // prints: 4294967295
writeln(n1 >= n2); // prints: FALSE
end.
The compilation gives the following warning:
[Warning] temp.dpr(10): Comparing signed and unsigned types - widened both operands
(Successive tests have shown that Microsoft C++ has the same bug, while the "managed C++" has it fixed).
--------------------
Using AAs I have almost implemented a Set() class really close to the built-in set() type of Python. The main problem I have found is relative to the opCmp.
Real numbers have a total order relation, so if you have two real numbers, like:
a = 5.2
b = 7.3
They can be:
1) a < b
2) a = b
3) a > b
(For Floating point numbers there are other situations, that D manages well).
But sets have just a partial order relation. Python sets have the following overloaded operators too:
s.issubset(t), with operator: s <= t (test whether every element in s is in t).
s.issuperset(t), with operator: s >= t (test whether every element in t is in s).
I think with D you can only use opCmp to define <= and >=, that returns only -1, 0, 1, as seen for reals. So if you have two sets like:
A = {1, 2, 3}
B = {1, 2, 5}
Generally on a set you can't define a true opCmp, because sometimes:
A < B? No.
A = B? No.
A > B? No.
C++ order operators are all separated, like in Python, but D has opCmp that I think can't be used to implement those <= and >= among sets (but it's not a big problem because Python sets can be used by normal English named methods too, so those two operations can be accessed by methods instead of methods and operators).
Adding a fourth possible return value to opCmp (with meaning "undefined") can solve this problem, allowing to represent partial order relations too.
Bye,
bearophile
More information about the Digitalmars-d
mailing list