View mode: basic / threaded / horizontal-split · Log in · Help
April 28, 2011
Matrix creation quiz
A little quiz. This is related to a recent post of mine in the main D newsgroup, but please don't take a look at that post yet. This is the original function:


double[][] matgen(int n) {
   double[][] a;
   double tmp = 1.0 / n / n;
   a.length = n;
   for (int i = 0; i < n; ++i) a[i].length = n;
   for (int i = 0; i < n; ++i)
       for (int j = 0; j < n; ++j)
           a[i][j] = tmp * (i - j) * (i + j);
   return a;
}


Second "improved" version:

double[][] matgen(int n) {
   double tmp = 1.0 / n / n;
   auto a = new double[][](n, n);
   foreach (i, row; a)
       foreach (j, ref x; row)
           x = tmp * (i - j) * (i + j);
   return a;
}


But the second nicer version has a bug, do you see it? :-)

Bye,
bearophile
April 28, 2011
Re: Matrix creation quiz
On 28-04-2011 13:02, bearophile wrote:
> A little quiz. This is related to a recent post of mine in the main D newsgroup, but please don't take a look at that post yet. This is the original function:
>
>
> double[][] matgen(int n) {
>      double[][] a;
>      double tmp = 1.0 / n / n;
>      a.length = n;
>      for (int i = 0; i<  n; ++i) a[i].length = n;
>      for (int i = 0; i<  n; ++i)
>          for (int j = 0; j<  n; ++j)
>              a[i][j] = tmp * (i - j) * (i + j);
>      return a;
> }
>
>
> Second "improved" version:
>
> double[][] matgen(int n) {
>      double tmp = 1.0 / n / n;
>      auto a = new double[][](n, n);
>      foreach (i, row; a)
>          foreach (j, ref x; row)
>              x = tmp * (i - j) * (i + j);
>      return a;
> }
>
>
> But the second nicer version has a bug, do you see it? :-)
>
> Bye,
> bearophile

The fact that 'i' and 'j' are deduced to type 'uint' in the second 
version. That's the kind of bug that would keep me up at night.

Cheers,
Pedro Rodrigues
April 28, 2011
Re: Matrix creation quiz
On Thu, 28 Apr 2011 08:02:40 -0400, bearophile <bearophileHUGS@lycos.com>  
wrote:

> A little quiz. This is related to a recent post of mine in the main D  
> newsgroup, but please don't take a look at that post yet. This is the  
> original function:
>
>
> double[][] matgen(int n) {
>     double[][] a;
>     double tmp = 1.0 / n / n;
>     a.length = n;
>     for (int i = 0; i < n; ++i) a[i].length = n;
>     for (int i = 0; i < n; ++i)
>         for (int j = 0; j < n; ++j)
>             a[i][j] = tmp * (i - j) * (i + j);
>     return a;
> }
>
>
> Second "improved" version:
>
> double[][] matgen(int n) {
>     double tmp = 1.0 / n / n;
>     auto a = new double[][](n, n);
>     foreach (i, row; a)
>         foreach (j, ref x; row)
>             x = tmp * (i - j) * (i + j);
>     return a;
> }
>
>
> But the second nicer version has a bug, do you see it? :-)

I read the other answer, I thought it was because the indexing is  
different, but that's only on initialization.  So I was wrong :)

-Steve
April 28, 2011
Re: Matrix creation quiz
bearophile Wrote:

>     auto a = new double[][](n, n);

And this really allocs tag array?

ps lol, didn't see the unsigned bug.
April 28, 2011
Re: Matrix creation quiz
On Thu, 28 Apr 2011 08:02:40 -0400, bearophile wrote:

> A little quiz. This is related to a recent post of mine in the main D
> newsgroup, but please don't take a look at that post yet. This is the
> original function:
uhm, very sneaky.
I wonder, can there be done smth. on behalf of the language to prevent 
this kind of bug?
April 28, 2011
Re: Matrix creation quiz
Pedro Rodrigues:

> The fact that 'i' and 'j' are deduced to type 'uint' in the second 
> version. That's the kind of bug that would keep me up at night.

Almost right answer. i and j are size_t, that is not uint in 64 bit compilations. Unsigned numbers cause the (i-j) sub-expression to give wrong results.

------------------------

Moritz Warning:

> I wonder, can there be done smth. on behalf of the language to prevent
> this kind of bug?

Two possible solutions, both refused by Walter:
- Dmd may use signed word for array indexes and lenghts.
- dmd may introduce runtime overflows.

Bye,
bearophile
April 28, 2011
Re: Matrix creation quiz
On 28-04-2011 16:39, Moritz Warning wrote:
> On Thu, 28 Apr 2011 08:02:40 -0400, bearophile wrote:
>
>> A little quiz. This is related to a recent post of mine in the main D
>> newsgroup, but please don't take a look at that post yet. This is the
>> original function:
> uhm, very sneaky.
> I wonder, can there be done smth. on behalf of the language to prevent
> this kind of bug?
There sure is: disallow implicit conversion of types. That's how 
languages like Haskell work. It can be annoying having the compiler 
complain because you're using and 'int' where it expected a 'double' for 
example, but on the other hand it avoids many hard to detected bugs 
(like this one).

Pedro Rodrigues
April 28, 2011
Re: Matrix creation quiz
Pedro Rodrigues:

> There sure is: disallow implicit conversion of types.

In this program what are the implicit type conversions that cause the bug?

Bye,
bearophile
April 29, 2011
Re: Matrix creation quiz
On 4/28/11 8:02 PM, bearophile wrote:
> A little quiz. This is related to a recent post of mine in the main D newsgroup, but please don't take a look at that post yet. This is the original function:

What are unsigned values good for?
April 29, 2011
Re: Matrix creation quiz
bearophile wrote:
> Pedro Rodrigues:
> 
>> The fact that 'i' and 'j' are deduced to type 'uint' in the second 
>> version. That's the kind of bug that would keep me up at night.
> 
> Almost right answer. i and j are size_t, that is not uint in 64 bit compilations. Unsigned numbers cause the (i-j) sub-expression to give wrong results.
> 
> ------------------------
> 
> Moritz Warning:
> 
>> I wonder, can there be done smth. on behalf of the language to prevent
>> this kind of bug?
> 
> Two possible solutions, both refused by Walter:
> - Dmd may use signed word for array indexes and lenghts.
Yes -- but see below.

> - dmd may introduce runtime overflows.
That would not fix this problem. You're doing arithmetic on unsigned 
values, where overflow doesn't happen.


Solution 3:
Dmd could use a special size_t type internally, defined as an integer of 
range equal to the address space. Internally, the compiler would view it 
as a long of range 0..cast(long)uint.max.
Thus, although it would implicitly convert to uint, it would not have 
uint semantics (size_t*size_t would no longer convert to uint).
But it wouldn't be an int, either. ( int a; if (a>b.length).. would be a 
signed/unsigned mismatch).

Incidentally a size_t type would allow us to catch bugs like:

uint n = a.length;
-- which compiles happily on 32 bits, but won't compile on a 64 bit 
system. I think it should be rejected on all systems.
« First   ‹ Prev
1 2
Top | Discussion index | About this forum | D home