www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Integer overflow and underflow semantics?

reply "Gary Willoughby" <dev nomad.so> writes:
This was asked a few years ago and i could find a definitive 
answer.

http://forum.dlang.org/thread/jo2c0a$31hh$1 digitalmars.com

On Saturday, 5 May 2012 at 04:57:48 UTC, Alex Rønne Petersen 
wrote:

 I don't think the language really makes it clear whether 
 overflows and underflows are well-defined. Do we guarantee that 
 for any integral type T, T.max + 1 == T.min and T.min - 1 == 
 T.max?


What is the current situation of integer overflow and underflow?
Jul 16 2014
next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 7/16/2014 2:26 PM, Gary Willoughby wrote:

 What is the current situation of integer overflow and underflow?


https://github.com/D-Programming-Language/druntime/pull/839
Jul 16 2014
parent Timon Gehr <timon.gehr gmx.ch> writes:
On 07/17/2014 12:18 AM, Walter Bright wrote:

 On 7/16/2014 2:26 PM, Gary Willoughby wrote:

 What is the current situation of integer overflow and underflow?


 https://github.com/D-Programming-Language/druntime/pull/839


(His question was whether there is wrap-around behaviour for signed 
types, which I think does not have a good answer at the moment.)
Jul 16 2014
prev sibling next sibling parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Wednesday, 16 July 2014 at 21:26:41 UTC, Gary Willoughby wrote:

 This was asked a few years ago and i could find a definitive 
 answer.

 http://forum.dlang.org/thread/jo2c0a$31hh$1 digitalmars.com

 On Saturday, 5 May 2012 at 04:57:48 UTC, Alex Rønne Petersen 
 wrote:

 I don't think the language really makes it clear whether 
 overflows and underflows are well-defined. Do we guarantee 
 that for any integral type T, T.max + 1 == T.min and T.min - 1 
 == T.max?


 What is the current situation of integer overflow and underflow?


My understanding:

Every machine D will feasibly support will do T.max + 1 == T.min 
and T.min - 1 == T.max for native integral operations, signed or 
unsigned.

BUT:

We are using C(++) backends, which may assumed an undefined 
result for signed over/underflow. Optimisers could cause us pain 
here.

BUT:

It's probably not taken advantage of due to the amount of C code 
that assumes the expected semantics. Also, there may be ways of 
telling backends that it is defined and we may be using those 
ways, I don't know.
Jul 17 2014
parent reply "David Nadlinger" <code klickverbot.at> writes:
On Thursday, 17 July 2014 at 08:50:12 UTC, John Colvin wrote:

 Every machine D will feasibly support will do T.max + 1 == 
 T.min and T.min - 1 == T.max for native integral operations, 
 signed or unsigned.


In fact, the spec mandates this (see AddExpression): "If both 
operands are of integral types and an overflow or underflow 
occurs in the computation, wrapping will happen."


 It's probably not taken advantage of due to the amount of C 
 code that assumes the expected semantics. Also, there may be 
 ways of telling backends that it is defined and we may be using 
 those ways, I don't know.


Oh dear, you'd be in for a very nasty surprise if you relied on 
this. ;)

Compiling the following code as C++ using Clang
---
bool foo(int a) {
   return a > (a + 1);
}
---
yields
---
; Function Attrs: nounwind readnone uwtable

   ret i1 false
}
---
That is, the optimizer completely gets rid of the check, as the 
overflow would be undefined behavior and thus cannot happen!

On the other hand, compiling it using LDC yields
---
; Function Attrs: nounwind readnone uwtable

   %tmp3 = icmp eq i32 %a_arg, 2147483647
   ret i1 %tmp3
}
---
just as it should. In other words, your suspicion that LLVM might 
offer a way to toggle whether overflow is defined is true, and 
LDC uses the correct variant of the arithmetic instructions.

GDC seems to be broken in that regard, though: 
http://bugzilla.gdcproject.org/show_bug.cgi?id=141

Cheers,
David
Jul 17 2014
next sibling parent reply Artur Skawina via Digitalmars-d <digitalmars-d puremagic.com> writes:
On Thursday, 17 July 2014 at 08:50:12 UTC, John Colvin wrote:

 there may be ways of telling backends that it is defined and we may be using
those ways, I don't know.


For GDC, it's the '-fwrapv' switch, but it's not enabled by default for D.

artur
Jul 17 2014
parent "bearophile" <bearophileHUGS lycos.com> writes:
Artur Skawina:


 For GDC, it's the '-fwrapv' switch, but it's not enabled by 
 default for D.


I think it has to be enabled by default, plus you can add a 
switch to disable that standard D semantics.

Bye,
bearophile
Jul 17 2014
prev sibling next sibling parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 7/17/2014 4:56 AM, David Nadlinger wrote:

 Oh dear, you'd be in for a very nasty surprise if you relied on this. ;)


When I wrote that part of the spec, it was long before these sorts of 
optimizations appeared, and it never occurred to me that they would be.
Jul 18 2014
parent reply "John Colvin" <john.loughran.colvin gmail.com> writes:
On Friday, 18 July 2014 at 08:49:43 UTC, Walter Bright wrote:

 On 7/17/2014 4:56 AM, David Nadlinger wrote:

 Oh dear, you'd be in for a very nasty surprise if you relied 
 on this. ;)


 When I wrote that part of the spec, it was long before these 
 sorts of optimizations appeared, and it never occurred to me 
 that they would be.


Does the dmd backend do any such optimisations? I assume not.
Jul 18 2014
parent reply Walter Bright <newshound2 digitalmars.com> writes:
On 7/18/2014 1:59 AM, John Colvin wrote:

 On Friday, 18 July 2014 at 08:49:43 UTC, Walter Bright wrote:

 On 7/17/2014 4:56 AM, David Nadlinger wrote:

 Oh dear, you'd be in for a very nasty surprise if you relied on this. ;)


 When I wrote that part of the spec, it was long before these sorts of
 optimizations appeared, and it never occurred to me that they would be.


 Does the dmd backend do any such optimisations? I assume not.


No, it doesn't, and I don't intend to add them. I believe they cause more 
trouble than they're worth. That applies to some other optimizations I've also 
refused to implement, because while legal, they mess up code that most users 
believe is correct.
Jul 18 2014
parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Friday, 18 July 2014 at 19:02:48 UTC, Walter Bright wrote:

 No, it doesn't, and I don't intend to add them. I believe they 
 cause more trouble than they're worth. That applies to some 
 other optimizations I've also refused to implement, because 
 while legal, they mess up code that most users believe is 
 correct.


But if the compiler can prove that the computation stays within 
the bounds or throws then there is no reason to not allow it. 
Since such optimizations can effect generics performance it would 
be nice to think about ways to help the compiler to establish the 
proof.

Even simple means such as annotating an int type with 
 assume_nowrap or  expect_wrapping etc.
Jul 18 2014
prev sibling parent reply "Kagamin" <spam here.lot> writes:
On Thursday, 17 July 2014 at 11:56:24 UTC, David Nadlinger wrote:

 ---
 ; Function Attrs: nounwind readnone uwtable

   %tmp3 = icmp eq i32 %a_arg, 2147483647
   ret i1 %tmp3
 }
 ---


Can't it simply generate code as is? Seems wasteful to spend 
compilation time on this.
Jul 19 2014
parent reply "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Saturday, 19 July 2014 at 08:34:39 UTC, Kagamin wrote:

 Can't it simply generate code as is? Seems wasteful to spend 
 compilation time on this.


Not if you want fast code, consider a template with:

if (a.length+M < b.length+N) {}

then you alias b = a in the template instantiation:

if(a.length+M < a.length+N){}

you want this reduced to:

if (M<N){
}

which can be resolved at compile time.
Jul 19 2014
parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Saturday, 19 July 2014 at 19:49:24 UTC, Ola Fosheim Grøstad 
wrote:

 On Saturday, 19 July 2014 at 08:34:39 UTC, Kagamin wrote:

 Can't it simply generate code as is? Seems wasteful to spend 
 compilation time on this.


 Not if you want fast code, consider a template with:

 if (a.length+M < b.length+N) {}

 then you alias b = a in the template instantiation:

 if(a.length+M < a.length+N){}

 you want this reduced to:

 if (M<N){
 }

 which can be resolved at compile time.


Yes, but that is the optimizer's job. The front-end doesn't need 
to spend time on it, if the back-end then anyway does the same 
optimization again.
Jul 20 2014
parent reply =?UTF-8?Q?Tobias=20M=C3=BCller?= <troplin bluewin.ch> writes:
"Marc Schütz" <schuetzm gmx.net> wrote:

 On Saturday, 19 July 2014 at 19:49:24 UTC, Ola Fosheim Grøstad wrote:

 On Saturday, 19 July 2014 at 08:34:39 UTC, Kagamin wrote:

 Can't it simply generate code as is? Seems wasteful to spend >> compilation
time on this.


 
 Not if you want fast code, consider a template with:
 
 if (a.length+M < b.length+N) {}
 
 then you alias b = a in the template instantiation:
 
 if(a.length+M < a.length+N){}
 
 you want this reduced to:
 
 if (M<N){
 }
 
 which can be resolved at compile time.


 
 Yes, but that is the optimizer's job. The front-end doesn't need to spend
 time on it, if the back-end then anyway does the same optimization again.


I don't think anyone has said that the frontend does that.
But the language semantics forbid such optimizations if overflow is defined
as wrapping.
If the optimizer respects that is a different chapter, as the experiment
with GDC shows.

Tobi
Jul 20 2014
parent reply "Marc =?UTF-8?B?U2Now7x0eiI=?= <schuetzm gmx.net> writes:
On Sunday, 20 July 2014 at 11:09:45 UTC, Tobias Müller wrote:

 "Marc Schütz" <schuetzm gmx.net> wrote:

 On Saturday, 19 July 2014 at 19:49:24 UTC, Ola Fosheim Grøstad 
 wrote:

 On Saturday, 19 July 2014 at 08:34:39 UTC, Kagamin wrote:

 Can't it simply generate code as is? Seems wasteful to spend

 compilation time on this.






 
 Not if you want fast code, consider a template with:
 
 if (a.length+M < b.length+N) {}
 
 then you alias b = a in the template instantiation:
 
 if(a.length+M < a.length+N){}
 
 you want this reduced to:
 
 if (M<N){
 }
 
 which can be resolved at compile time.


 
 Yes, but that is the optimizer's job. The front-end doesn't 
 need to spend
 time on it, if the back-end then anyway does the same 
 optimization again.


 I don't think anyone has said that the frontend does that.


I do ;-) This is how I interpret Kagamin's post.
Jul 20 2014
parent =?UTF-8?Q?Tobias=20M=C3=BCller?= <troplin bluewin.ch> writes:
"Marc Schütz" <schuetzm gmx.net> wrote:

 On Sunday, 20 July 2014 at 11:09:45 UTC, Tobias Müller wrote:

 "Marc Schütz" <schuetzm gmx.net> wrote:

 On Saturday, 19 July 2014 at 19:49:24 UTC, Ola Fosheim Grøstad >> wrote:

 On Saturday, 19 July 2014 at 08:34:39 UTC, Kagamin wrote:

 Can't it simply generate code as is? Seems wasteful to spend

 compilation time on this.
 Not if you want fast code, consider a template with:
 if (a.length+M < b.length+N) {}
 then you alias b = a in the template instantiation:
 if(a.length+M < a.length+N){}
 you want this reduced to:
 if (M<N){






 }

 which can be resolved at compile time.




 Yes, but that is the optimizer's job. The front-end doesn't >> need to spend




 time on it, if the back-end then anyway does the same >> optimization again.


 
 I don't think anyone has said that the frontend does that.


 
 I do ;-) This is how I interpret Kagamin's post.


Hm I interpreted it the other way round, it's wasteful to spend time for
such optimizations, just.
But my english is probably not as good as yours.

Tobi
Jul 21 2014
prev sibling parent reply "Basile Burg" <basile.burg gmx.com> writes:
On Wednesday, 16 July 2014 at 21:26:41 UTC, Gary Willoughby wrote:

 This was asked a few years ago and i could find a definitive 
 answer.

 http://forum.dlang.org/thread/jo2c0a$31hh$1 digitalmars.com

 On Saturday, 5 May 2012 at 04:57:48 UTC, Alex Rønne Petersen 
 wrote:

 I don't think the language really makes it clear whether 
 overflows and underflows are well-defined. Do we guarantee 
 that for any integral type T, T.max + 1 == T.min and T.min - 1 
 == T.max?


 What is the current situation of integer overflow and underflow?


If you still feel ok today then dont read this:
-----------------
module meh;

import std.stdio;

//https://stackoverflow.com/questions/24676375/why-does-int-i-1024-1024-1024-1024-compile-without-error

static shared immutable int o = 1024 * 1024 * 1024 * 1024;

void main(string args[])
{
     writeln(o);
}
-------------------------------------------------------------
Jul 21 2014
parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Basile Burg:


 If you still feel ok today then dont read this:
 -----------------
 module meh;

 import std.stdio;

 //https://stackoverflow.com/questions/24676375/why-does-int-i-1024-1024-1024-1024-compile-without-error

 static shared immutable int o = 1024 * 1024 * 1024 * 1024;

 void main(string args[])
 {
     writeln(o);
 }
 -------------------------------------------------------------


See:
https://issues.dlang.org/show_bug.cgi?id=4835
https://github.com/D-Programming-Language/dmd/pull/1803

Bye,
bearophile
Jul 21 2014
next sibling parent reply Artur Skawina via Digitalmars-d <digitalmars-d puremagic.com> writes:
On 07/21/14 16:32, bearophile via Digitalmars-d wrote:

 https://github.com/D-Programming-Language/dmd/pull/1803


Disallowing integer overflow just at CT is not (sanely) possible
in a language with D's CTFE capabilities. (Would result in code
that compiles and works at runtime, but is not ctfe-able)

artur
Jul 21 2014
parent reply "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Monday, 21 July 2014 at 19:33:32 UTC, Artur Skawina via 
Digitalmars-d wrote:

 Disallowing integer overflow just at CT is not (sanely) possible
 in a language with D's CTFE capabilities. (Would result in code
 that compiles and works at runtime, but is not ctfe-able)


I'd like to see compile time _constants_ be unbounded rational 
numbers with explicit truncation. It is when you assign it to an 
in-memory location that you need to worry about bounds. The same 
goes for calculations that doesn't do division.

No need to copy the bad parts of C.
Jul 21 2014
next sibling parent reply Artur Skawina via Digitalmars-d <digitalmars-d puremagic.com> writes:
On 07/21/14 21:53, via Digitalmars-d wrote:

 On Monday, 21 July 2014 at 19:33:32 UTC, Artur Skawina via Digitalmars-d wrote:

 Disallowing integer overflow just at CT is not (sanely) possible
 in a language with D's CTFE capabilities. (Would result in code
 that compiles and works at runtime, but is not ctfe-able)


 
 I'd like to see compile time _constants_ be unbounded rational numbers with
explicit truncation. It is when you assign it to an in-memory location that you
need to worry about bounds. The same goes for calculations that doesn't do
division.
 
 No need to copy the bad parts of C.


Actually, C/C++ could get away with treating overflow during constant
folding as an error (or at least emitting a warning) because of the
lack of CTFE (and no templates in C's case). The code will either
compile or it won't.
For D that is not possible -- if an expression is valid at run-time
then it should be valid at compile-time (and obviously yield the same
value). Making this aspect of CT evaluation special would make CTFE
much less useful and add complexity to the language for very little gain.
Trying to handle just a subset of the problem would make things even
worse -- /some/ code would not be CTFE-able and /some/ overflows wouldn't
be caught.

   int f(int a, int b) { return a*b; }
   enum v = f(100_000, 100_000);

artur
Jul 21 2014
next sibling parent reply "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Monday, 21 July 2014 at 21:10:43 UTC, Artur Skawina via 
Digitalmars-d wrote:


 For D that is not possible -- if an expression is valid at 
 run-time
 then it should be valid at compile-time (and obviously yield 
 the same
 value). Making this aspect of CT evaluation special would make 
 CTFE
 much less useful and add complexity to the language for very 
 little gain.


CT and runtime give different results for floats.
Overflow in the end result without explicit truncation should be 
considered a bug. Bugs can yield different results.

Overflow checks on add/sub expressions mess up reordering 
optimizations. You only care about overflows in the end result.

Exact, truncating, masking/wrapping or saturating math results 
should be explicit. (It is a flaw to use the same div operator 
for floats and ints.) It should be the programmers resposibility 
to provide the proofs or turn on extra precision in debug mode.

Turning off reordering optimizations and add checks ought to be 
the rare case for both ints and floats.

Ideally all ctfe would be done as real intervals with rational 
bounds, then checked against the specified precision of the end 
result (or numerically solving the whole expression to the 
specified precision).


 Trying to handle just a subset of the problem would make things 
 even
 worse -- /some/ code would not be CTFE-able and /some/ 
 overflows wouldn't
 be caught.

    int f(int a, int b) { return a*b; }
    enum v = f(100_000, 100_000);


NUMBER f(NUMBER a, NUMBER b) ...
Jul 21 2014
parent reply Artur Skawina via Digitalmars-d <digitalmars-d puremagic.com> writes:
On 07/22/14 05:12, via Digitalmars-d wrote:

 On Monday, 21 July 2014 at 21:10:43 UTC, Artur Skawina via Digitalmars-d wrote:
 

 For D that is not possible -- if an expression is valid at run-time
 then it should be valid at compile-time (and obviously yield the same
 value). Making this aspect of CT evaluation special would make CTFE
 much less useful and add complexity to the language for very little gain.


 
 CT and runtime give different results for floats.


Both CT and RT evaluation must yield correct results, where "correct"
means "as specified". If RT FP is allowed to use extra precision (or
is otherwise loosely specified) then this also applies to CT FP.
But integer overflow _is_ defined in D (unlike in eg C), so CT has to
obey the exact same rules as RT. Would you really like to use a language
in which 'enum x = (a+b)/2;' and 'immutable x = (a+b)/2;' results in
different values?... And functions containing such 'a+b' expressions,
which rely on wrapping arithmetic, are not usable at CT?...


 Overflow in the end result without explicit truncation should be considered a
bug. Bugs can yield different results.


 
Integer overflow is defined in D. It's not a bug. It can be relied upon.
(Well, now it can, after Iain recently fixed GDC ;) )


 Overflow checks on add/sub expressions mess up reordering optimizations. You
only care about overflows in the end result.


This would be an argument _against_ introducing the checks.


 Exact, truncating, masking/wrapping or saturating math results should be
explicit. 


That's how it is in D - the arguments are only about the /default/, and in
this case about /using a different default at CT and RT/. Using a non-wrapping
default would be a bad idea (perf implications, both direct and indirect -
bounds checking would make certain optimizations invalid), and using different
evaluation modes for CT and RT would be, well, insane.


 Ideally all ctfe would be done as real intervals with rational bounds, then
checked against the specified precision of the end result (or numerically
solving the whole expression to the specified precision).


Not possible (for integers), unless you'd be ok with getting different
results at CT.


 Trying to handle just a subset of the problem would make things even
 worse -- /some/ code would not be CTFE-able and /some/ overflows wouldn't
 be caught.

    int f(int a, int b) { return a*b; }
    enum v = f(100_000, 100_000);


 
 NUMBER f(NUMBER a, NUMBER b) ...


Not sure what you mean here. 'f' is a perfectly fine existing
function, which is used at RT. It needs to be usable at CT as is.
The power of D's CTFE comes from being able to execute normal D
code and not having to use a different dialect.

artur
Jul 22 2014
parent reply "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Tuesday, 22 July 2014 at 11:40:08 UTC, Artur Skawina via 
Digitalmars-d wrote:

 obey the exact same rules as RT. Would you really like to use a 
 language
 in which 'enum x = (a+b)/2;' and 'immutable x = (a+b)/2;' 
 results in
 different values?...


With the exception of hash-functions the result will be wrong if 
you don't predict that the value is wrapping. If you do, I think 
you should make the masking explicit e.g. specifying 
'(a+b)&0xffffffff' or something similar, which the optimizer can 
reduce to a single addition.


 That's how it is in D - the arguments are only about the 
 /default/, and in
 this case about /using a different default at CT and RT/. Using 
 a non-wrapping
 default would be a bad idea (perf implications, both direct and


Yes, but there is a difference between saying "it is ok that it 
wraps on addition, but it shouldn't overflow before a store takes 
place" and "it should be masked to N bits or fail on overflow 
even though the end-result is known to be correct". A system 
level language should encourage using the fastest opcode, so you 
shouldn't enforce 32 bit masking when the fastest register size 
is 64 bit etc. It should also encourage reordering so you get to 
use efficient SIMDy instructions.


 Not possible (for integers), unless you'd be ok with getting 
 different
 results at CT.


You don't get different results at compile time if you are 
explicit about wrapping.


 NUMBER f(NUMBER a, NUMBER b) ...


 Not sure what you mean here. 'f' is a perfectly fine existing
 function, which is used at RT. It needs to be usable at CT as 
 is.


D claims to focus generic programming. So it should also 
encourage pure functions that can be specified for floats, ints 
and other numeric types that are subtypes of (true) reals in the 
same clean definition.

If you express the expression in a clean way to get down to the 
actual (more limited type) then the optimizer sometimes can pick 
an efficient sequence of instructions that might be a very fast 
approximation if you reduce the precision sufficiently in the 
end-result.

To get there you need to differentiate between a truncating 
division and a non-truncating division etc.

The philosophy behind generic programming and the requirements 
for efficient generic programming is quite different from the the 
machine-level hand optimizing philosophy of classic C, IMO.
Jul 22 2014
next sibling parent reply Artur Skawina via Digitalmars-d <digitalmars-d puremagic.com> writes:
On 07/22/14 17:31, via Digitalmars-d wrote:

 On Tuesday, 22 July 2014 at 11:40:08 UTC, Artur Skawina via Digitalmars-d
wrote:

 obey the exact same rules as RT. Would you really like to use a language
 in which 'enum x = (a+b)/2;' and 'immutable x = (a+b)/2;' results in
 different values?...


 
 With the exception of hash-functions the result will be wrong if you don't
predict that the value is wrapping. If you do, I think you should make the
masking explicit e.g. specifying '(a+b)&0xffffffff' or something similar, which
the optimizer can reduce to a single addition.


D is defined as it is, with wrapping two's complement integer arithmetic
and defined integer sizes.

My point is that the language must be consistent; adding special
cases would create a language in which one expression yields several
different results, depending on evaluation context. That would be a
very significant regression, and would severely cripple the language.
Maybe the harm done by that particular pull request wouldn't be
catastrophic, but it would be a step in a very dangerous direction.

artur
Jul 22 2014
parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Tuesday, 22 July 2014 at 21:06:09 UTC, Artur Skawina via 
Digitalmars-d wrote:

 D is defined as it is, with wrapping two's complement integer 
 arithmetic
 and defined integer sizes.


Integer promotion is locked to 32 bits. That is a mistake. Why 
wrap everything below 32bit at 32 on a 64 bit ALU? That's 
inconvinient and will lead to undetected bugs.

I also think it is a mistake to lock to C rules, which were 
defined when multiply often were done in software. In most modern 
ALUs a N bit multiply yields a 2*N bit result. Why discard the 
high word?

With forced wrapping/masking (a*b)>>32 is turned into 
((a*b)&0xffffffff)>>32 which is zero, so you have to cast 'a' to 
64 bit before the multiply, then downcast the result to 32 bit.


 My point is that the language must be consistent; adding special
 cases would create a language in which one expression yields 
 several
 different results, depending on evaluation context.


I understand this point, but I think code that would yield such 
errors most lkely is buggy or underspecified.

Ola.
Jul 22 2014
prev sibling next sibling parent reply "Don" <x nospam.com> writes:
On Tuesday, 22 July 2014 at 15:31:22 UTC, Ola Fosheim Grøstad 
wrote:

 On Tuesday, 22 July 2014 at 11:40:08 UTC, Artur Skawina via 
 Digitalmars-d wrote:

 obey the exact same rules as RT. Would you really like to use 
 a language
 in which 'enum x = (a+b)/2;' and 'immutable x = (a+b)/2;' 
 results in
 different values?...


 With the exception of hash-functions the result will be wrong 
 if you don't predict that the value is wrapping. If you do, I 
 think you should make the masking explicit e.g. specifying 
 '(a+b)&0xffffffff' or something similar, which the optimizer 
 can reduce to a single addition.


 That's how it is in D - the arguments are only about the 
 /default/, and in
 this case about /using a different default at CT and RT/. 
 Using a non-wrapping
 default would be a bad idea (perf implications, both direct and


 Yes, but there is a difference between saying "it is ok that it 
 wraps on addition, but it shouldn't overflow before a store 
 takes place" and "it should be masked to N bits or fail on 
 overflow even though the end-result is known to be correct". A 
 system level language should encourage using the fastest 
 opcode, so you shouldn't enforce 32 bit masking when the 
 fastest register size is 64 bit etc. It should also encourage 
 reordering so you get to use efficient SIMDy instructions.


 Not possible (for integers), unless you'd be ok with getting 
 different
 results at CT.


 You don't get different results at compile time if you are 
 explicit about wrapping.


 NUMBER f(NUMBER a, NUMBER b) ...


 Not sure what you mean here. 'f' is a perfectly fine existing
 function, which is used at RT. It needs to be usable at CT as 
 is.


 D claims to focus generic programming. So it should also 
 encourage pure functions that can be specified for floats, ints 
 and other numeric types that are subtypes of (true) reals in 
 the same clean definition.


I think it's a complete fantasy to think you can write generic 
code that will work for both floats and ints. The algorithms are 
completely different.

One of the simplest examples is that given float f;  int i;

(f + 1) and  (i +  1)  have totally different semantics.

There are no values of i for which i + 1 == i,
but if abs(f) > 1/real.epsilon, then f + 1 == f.

Likewise there is no value of i for which i != 0 && i+1 == 1,
but for any abs(f) < real.epsilon, f + 1 == 1.



 If you express the expression in a clean way to get down to the 
 actual (more limited type) then the optimizer sometimes can 
 pick an efficient sequence of instructions that might be a very 
 fast approximation if you reduce the precision sufficiently in 
 the end-result.



 To get there you need to differentiate between a truncating 
 division and a non-truncating division etc.


Well, it's not a small number of differences. Almost every 
operation is different. Maybe all of them. I can't actually think 
of a single operation where the semantics are the same for 
integers and floating point.

Negation comes close, but even then you have the special cases 
-0.0 and -(-int.max - 1).



 The philosophy behind generic programming and the requirements 
 for efficient generic programming is quite different from the 
 the machine-level hand optimizing philosophy of classic C, IMO.


I think that unfortunately, it's a quest that is doomed to fail. 
Producing generic code that works for both floats and ints is a 
fool's errand.
Jul 23 2014
next sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 7/23/2014 12:49 AM, Don wrote:

 On Tuesday, 22 July 2014 at 15:31:22 UTC, Ola Fosheim Grøstad wrote:

 D claims to focus generic programming. So it should also encourage pure
 functions that can be specified for floats, ints and other numeric types that
 are subtypes of (true) reals in the same clean definition.


 I think it's a complete fantasy to think you can write generic code that will
 work for both floats and ints. The algorithms are completely different.

 One of the simplest examples is that given float f;  int i;

 (f + 1) and  (i +  1)  have totally different semantics.

 There are no values of i for which i + 1 == i,
 but if abs(f) > 1/real.epsilon, then f + 1 == f.

 Likewise there is no value of i for which i != 0 && i+1 == 1,
 but for any abs(f) < real.epsilon, f + 1 == 1.



 If you express the expression in a clean way to get down to the actual (more
 limited type) then the optimizer sometimes can pick an efficient sequence of
 instructions that might be a very fast approximation if you reduce the
 precision sufficiently in the end-result.



 To get there you need to differentiate between a truncating division and a
 non-truncating division etc.


 Well, it's not a small number of differences. Almost every operation is
 different. Maybe all of them. I can't actually think of a single operation
where
 the semantics are the same for integers and floating point.

 Negation comes close, but even then you have the special cases -0.0 and
 -(-int.max - 1).



 The philosophy behind generic programming and the requirements for efficient
 generic programming is quite different from the the machine-level hand
 optimizing philosophy of classic C, IMO.


 I think that unfortunately, it's a quest that is doomed to fail. Producing
 generic code that works for both floats and ints is a fool's errand.


I quoted you on https://github.com/D-Programming-Language/phobos/pull/2366 !
Jul 23 2014
prev sibling parent "Ola Fosheim =?UTF-8?B?R3LDuHN0YWQi?= writes:
On Wednesday, 23 July 2014 at 07:49:28 UTC, Don wrote:

 I think it's a complete fantasy to think you can write generic 
 code that will work for both floats and ints. The algorithms 
 are completely different.


Not really a valid line of reasoning.

Bool < uints < ints < fixed point < floats < interval arithmetic

You can make the same argument about all these types. Moreover, 
any float can be accurately represented as a rational number.


 (f + 1) and  (i +  1)  have totally different semantics.


Not if you view floats as a single sample on a real interval. You 
can compute this interval on CT and sample a float on it.

If you are speaking of iterative methods, sure, it might not 
converge. But that us not unique for floats, happens with ints vs 
uints too.


 Well, it's not a small number of differences. Almost every 
 operation is different. Maybe all of them. I can't actually 
 think of a single operation where the semantics are the same 
 for integers and floating point.


Double can emulate 32 bit ints. Fixed point is essentially 
subnormal floats with limited exponent. Fixed point IS integer 
math. All int types are fixed point. If you find a clean way to 
support transaparent use of fixed point, you probably also 
resolve the issues with floats.


 I think that unfortunately, it's a quest that is doomed to 
 fail. Producing generic code that works for both floats and 
 ints is a fool's errand.


Of course not. Not if the semantic analysis deals with precision 
and value ranges. Not trivial, but not impossible either.
Jul 23 2014
prev sibling parent "Kagamin" <spam here.lot> writes:
On Tuesday, 22 July 2014 at 15:31:22 UTC, Ola Fosheim Grøstad 
wrote:

 A system level language should encourage using the fastest 
 opcode, so you shouldn't enforce 32 bit masking when the 
 fastest register size is 64 bit etc.


This is what int_fast32_t is for, but unfortunately it's not 
guaranteed to be the fastest, but you can use something similar.
Jul 23 2014
prev sibling next sibling parent reply "Don" <x nospam.com> writes:
On Monday, 21 July 2014 at 21:10:43 UTC, Artur Skawina via 
Digitalmars-d wrote:

 On 07/21/14 21:53, via Digitalmars-d wrote:

 On Monday, 21 July 2014 at 19:33:32 UTC, Artur Skawina via 
 Digitalmars-d wrote:

 Disallowing integer overflow just at CT is not (sanely) 
 possible
 in a language with D's CTFE capabilities. (Would result in 
 code
 that compiles and works at runtime, but is not ctfe-able)


 
 I'd like to see compile time _constants_ be unbounded rational 
 numbers with explicit truncation. It is when you assign it to 
 an in-memory location that you need to worry about bounds. The 
 same goes for calculations that doesn't do division.
 
 No need to copy the bad parts of C.


 Actually, C/C++ could get away with treating overflow during 
 constant
 folding as an error (or at least emitting a warning) because of 
 the
 lack of CTFE (and no templates in C's case). The code will 
 either
 compile or it won't.
 For D that is not possible -- if an expression is valid at 
 run-time
 then it should be valid at compile-time


Why do you think that? There are many cases where that is not 
true. Comparing pointers to two unrelated objects will work at 
runtime, but causes an error in CTFE. You can read global 
variables at runtime, not in CTFE. Etc.

The converse is true, though -- if it works at CTFE, it must work 
at runtime.


Disallowing integer overflow in CTFE could certainly be 
implemented. It's not a difficult experiment to run. It would be 
interesting to see how many instances of overflow are bugs, and 
how many are intentional.
Jul 23 2014
parent Artur Skawina via Digitalmars-d <digitalmars-d puremagic.com> writes:
On 07/23/14 09:16, Don via Digitalmars-d wrote:

 On Monday, 21 July 2014 at 21:10:43 UTC, Artur Skawina via Digitalmars-d wrote:



 Actually, C/C++ could get away with treating overflow during constant
 folding as an error (or at least emitting a warning) because of the
 lack of CTFE (and no templates in C's case). The code will either
 compile or it won't.
 For D that is not possible -- if an expression is valid at run-time
 then it should be valid at compile-time


 
 Why do you think that? There are many cases where that is not true. Comparing
pointers to two unrelated objects will work at runtime, but causes an error in
CTFE. You can read global variables at runtime, not in CTFE. Etc.


Obviously, any allowed operation must still yield a meaningful result.
The CTFE restrictions you list could actually be relaxed. Eg __gshared
object pointers could be (more) exposed; static immutable objects already
are exposed, it would be possible to give read-only access to mutable
ones too. (Not that I'm suggesting doing that)

But the context was _integer arithmetic_ expressions -- those needs to
work at CT exactly like they do at RT. Anything else would mean that
CTFE would be crippled; either some (sub-)programs wouldn't be usable
at CT, or they would give different results. A compromise that would
disallow just some "obviously" wrong expressions is not a real option, 
because D is too powerful (the "wrong" code could itself come from CTFE).

Sure, it would be /technically/ possible to trap on overflow at CT, but
the result wouldn't be sane. And it would make the language even more
complex. Just imagine all the extra posts asking why something doesn't
work at CT. And if OF is allowed in certain situations, then also all
the complaints about the compiler not catching some overflow...

artur
Jul 24 2014
prev sibling parent Walter Bright <newshound2 digitalmars.com> writes:
On 7/21/2014 2:10 PM, Artur Skawina via Digitalmars-d wrote:

 Actually, C/C++ could get away with treating overflow during constant
 folding as an error (or at least emitting a warning) because of the
 lack of CTFE (and no templates in C's case). The code will either
 compile or it won't.
 For D that is not possible -- if an expression is valid at run-time
 then it should be valid at compile-time (and obviously yield the same
 value). Making this aspect of CT evaluation special would make CTFE
 much less useful and add complexity to the language for very little gain.
 Trying to handle just a subset of the problem would make things even
 worse -- /some/ code would not be CTFE-able and /some/ overflows wouldn't
 be caught.

     int f(int a, int b) { return a*b; }
     enum v = f(100_000, 100_000);


One difficulty with breaking with C rules is we are working with optimizers and 
code generators developed for C. Coming up with different semantics for D may 
cause all sorts of problems.
Jul 23 2014
prev sibling next sibling parent reply Iain Buclaw via Digitalmars-d <digitalmars-d puremagic.com> writes:
On 21 Jul 2014 22:10, "Artur Skawina via Digitalmars-d" <
digitalmars-d puremagic.com> wrote:

 On 07/21/14 21:53, via Digitalmars-d wrote:

 On Monday, 21 July 2014 at 19:33:32 UTC, Artur Skawina via




Digitalmars-d wrote:

 Disallowing integer overflow just at CT is not (sanely) possible
 in a language with D's CTFE capabilities. (Would result in code
 that compiles and works at runtime, but is not ctfe-able)


 I'd like to see compile time _constants_ be unbounded rational numbers




with explicit truncation. It is when you assign it to an in-memory location
that you need to worry about bounds. The same goes for calculations that
doesn't do division.

 No need to copy the bad parts of C.


 Actually, C/C++ could get away with treating overflow during constant
 folding as an error (or at least emitting a warning) because of the
 lack of CTFE (and no templates in C's case). The code will either
 compile or it won't.
 For D that is not possible -- if an expression is valid at run-time
 then it should be valid at compile-time (and obviously yield the same
 value).


...most of the time.

CTFE is allowed to do things at an arbitrary precision in mid-flight when
evaluating an expression.

Iain
Jul 21 2014
parent Walter Bright <newshound2 digitalmars.com> writes:
On 7/21/2014 11:15 PM, Iain Buclaw via Digitalmars-d wrote:

 CTFE is allowed to do things at an arbitrary precision in mid-flight when
 evaluating an expression.


For floating point, yes. Not for integral arithmetic.
Jul 23 2014
prev sibling next sibling parent Artur Skawina via Digitalmars-d <digitalmars-d puremagic.com> writes:
On 07/22/14 08:15, Iain Buclaw via Digitalmars-d wrote:

 On 21 Jul 2014 22:10, "Artur Skawina via Digitalmars-d"
<digitalmars-d puremagic.com <mailto:digitalmars-d puremagic.com>> wrote:

 For D that is not possible -- if an expression is valid at run-time
 then it should be valid at compile-time (and obviously yield the same
 value).


 
 ...most of the time.
 
 CTFE is allowed to do things at an arbitrary precision in mid-flight when
evaluating an expression.


That will work for FP, where excess precision is allowed, but will not work
for integer arithmetic. Consider code which uses hashing and hash-folding
functions which rely on wrapping arithmetic. If you increase the precision
then those functions will yield different values. Now a hash value
calculated at CT is invalid at RT...

artur
Jul 22 2014
prev sibling next sibling parent Iain Buclaw via Digitalmars-d <digitalmars-d puremagic.com> writes:
On 22 July 2014 12:40, Artur Skawina via Digitalmars-d
<digitalmars-d puremagic.com> wrote:

 On 07/22/14 08:15, Iain Buclaw via Digitalmars-d wrote:

 On 21 Jul 2014 22:10, "Artur Skawina via Digitalmars-d"
<digitalmars-d puremagic.com <mailto:digitalmars-d puremagic.com>> wrote:

 For D that is not possible -- if an expression is valid at run-time
 then it should be valid at compile-time (and obviously yield the same
 value).


 ...most of the time.

 CTFE is allowed to do things at an arbitrary precision in mid-flight when
evaluating an expression.


 That will work for FP, where excess precision is allowed, but will not work
 for integer arithmetic. Consider code which uses hashing and hash-folding
 functions which rely on wrapping arithmetic. If you increase the precision
 then those functions will yield different values. Now a hash value
 calculated at CT is invalid at RT...

 artur


I can still imagine a possibility of such occurring if cross-compiling
from a (doesn't exist) platform at does integer operations at 128bit
to x86, which at runtime is 64bit.

This is just brushing on the idea of a potential porting bug rather
than an actual problem.

Iain
Jul 22 2014
prev sibling parent Artur Skawina via Digitalmars-d <digitalmars-d puremagic.com> writes:
On 07/22/14 18:39, Iain Buclaw via Digitalmars-d wrote:

 On 22 July 2014 12:40, Artur Skawina via Digitalmars-d
 <digitalmars-d puremagic.com> wrote:

 On 07/22/14 08:15, Iain Buclaw via Digitalmars-d wrote:

 On 21 Jul 2014 22:10, "Artur Skawina via Digitalmars-d"
<digitalmars-d puremagic.com <mailto:digitalmars-d puremagic.com>> wrote:

 For D that is not possible -- if an expression is valid at run-time
 then it should be valid at compile-time (and obviously yield the same
 value).


 ...most of the time.

 CTFE is allowed to do things at an arbitrary precision in mid-flight when
evaluating an expression.


 That will work for FP, where excess precision is allowed, but will not work
 for integer arithmetic. Consider code which uses hashing and hash-folding
 functions which rely on wrapping arithmetic. If you increase the precision
 then those functions will yield different values. Now a hash value
 calculated at CT is invalid at RT...


 
 I can still imagine a possibility of such occurring if cross-compiling
 from a (doesn't exist) platform at does integer operations at 128bit
 to x86, which at runtime is 64bit.


In D integer widths are well defined; exposing the larger range
would not be possible.

   static assert (100_000^^2!=100_000L^^2);

[Whether requiring specific integer widths was a good idea or not, 
 redefining them /now/ is obviously not a practical option.]


artur
Jul 22 2014
prev sibling parent "Basile Burg" <basile.burg gmx.com> writes:
On Monday, 21 July 2014 at 14:32:38 UTC, bearophile wrote:

 Basile Burg:


 If you still feel ok today then dont read this:
 -----------------
 module meh;

 import std.stdio;

 //https://stackoverflow.com/questions/24676375/why-does-int-i-1024-1024-1024-1024-compile-without-error

 static shared immutable int o = 1024 * 1024 * 1024 * 1024;

 void main(string args[])
 {
    writeln(o);
 }
 -------------------------------------------------------------


 See:
 https://issues.dlang.org/show_bug.cgi?id=4835
 https://github.com/D-Programming-Language/dmd/pull/1803

 Bye,
 bearophile


oOPS...I've just missed an oportunity to shut up my 
mouth...However, I'm glad to see that someone else noticed that 
the real issue is that it's a <<const>>.
Jul 21 2014