Jump to page: 1 2
Thread overview
Matrix creation quiz
Apr 28, 2011
bearophile
Apr 28, 2011
Pedro Rodrigues
Apr 28, 2011
bearophile
Apr 29, 2011
Don
May 02, 2011
bearophile
Apr 28, 2011
Kagamin
Apr 28, 2011
Moritz Warning
Apr 28, 2011
Pedro Rodrigues
Apr 28, 2011
bearophile
Apr 29, 2011
Ary Manzana
April 28, 2011
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
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
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
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
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
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
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
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
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
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