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