Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Cryptic genetic variation in software: hunting a buffered 41-year-old bug

cryptogenomicon.wordpress.com

Post reply on HN
Print view View original

31–40 of 50 posts

Re: Cryptic genetic variation in software: hunting a buffered 41-year-old bug

#31

Post by kator »

I always cringe when I see or have to write:

    for ( ; ; )
or:

    while ( true )
etc.

You just know you're setting yourself up for undocumented bugs later.

I've been known to build "escape" vars into these like:

    int attempts = 1000;
    for(;attempts > 0;attempts--) {
        ** DO SOMETHING **
    }

    if (attempts
Where 1000 or whatever number is a reasonable estimate of the function's need to loop x 10 or etc.

Re: Cryptic genetic variation in software: hunting a buffered 41-year-old bug

#32

Post by matthewcanty »

vishnugupta wrote: post #11
matthewcanty wrote: post #4

That was a really interesting read, and very well written. I wonder if anyone can clear this up though... I find the terminology of open and closed intervals contradictory to their meaning. Does anyone know why they are described like this? `Closed` makes me think shut or not-including - however it includes its endpoints. `Open` makes me think inclusive - yet does not include its endpoints.

The way I wrap my head around this is "open" == "no defined beginning or end point" and "closed" == "precisely defined beginning/end point". To take your thinking a bit further the interval is "shut" precisely because it's closed exactly at that point. And the interval is thrown "open" by not including the point. BTW; Rudin's classic text (1) covers the fascinating topic of neighborhoods which builds on the concept o…

My word, I'd have to do some studying to get through that!

Thanks for everyone's input. I think I have a clear understanding of the open/closed paradigm now.

Re: Cryptic genetic variation in software: hunting a buffered 41-year-old bug

#33

Post by jschwartzi »

entropy_ wrote: post #13
masklinn wrote: post #9

Earlier quoted context omitted.

The so-called "french notation" is interesting and — I think — clearer: a closed interval is [a, b] and an open interval is ]a, b[.

I learned Math in a french-system school and yes, that's definitely a much better notation in my opinion. The difference between [] and () is not immediately clear, whereas [a,b] versus ]a,b[ makes it obvious that one includes a and b while the other does not. It also makes it easy to remember "open" and "closed" and what they mean in terms of whether or not the interval bounds are included or excluded

I learned it one way in Middle School and the other in High School. What's perplexing is that the schools were literally next door to each other, and in the same school system too.

Re: Cryptic genetic variation in software: hunting a buffered 41-year-old bug

#34

Post by monochromatic »

GFK_of_xmaspast wrote: post #30
jdpage wrote: post #19

Earlier quoted context omitted.

From a real analysis standpoint... the definition of a 'closed set' in an N-dimensional metric space (of which Euclidean space, i.e. normal space, is an example) is as follows: a set C is 'closed' if and only if, given any sequence of elements (x_n) converging on x, such that (x_n) is a subset of C, it follows that x is also in C. Under this definition, 'closed' makes sense in the larger context, since in mathematics…

You can also have sets that are simultaneously closed and open.

Yep. For example, the empty set or the entire real number line.

Re: Cryptic genetic variation in software: hunting a buffered 41-year-old bug

#36

Post by Someone »

db48x wrote: post #10
matthewcanty wrote: post #4

That was a really interesting read, and very well written. I wonder if anyone can clear this up though... I find the terminology of open and closed intervals contradictory to their meaning. Does anyone know why they are described like this? `Closed` makes me think shut or not-including - however it includes its endpoints. `Open` makes me think inclusive - yet does not include its endpoints.

It's a good question. A close reading of the Wikipedia page " rel="nofollow">https://en.wikipedia.org/wiki/Interval_%28mathematics%29#Ter... tells me that an open interval has no definite maximum or minimum. This no doubt sounds strange, but it surely comes down to the slightly odd behavior of real numbers. In an open interval like (0, 1), there is no single real number which is less than one but is greater than all…

I don't see how this is poor UX. If we accept your statement that the terms "open" and "closed" are too similar, what do you suggest?

Also, any notation will have to be learned. Concise ones a bit more, but there is nothing one can do about that.

And that perfectly clear notation requires you to learn quite a bit by memorization, such as the meaning of those {} brackets, the |, and the symbols ∈ and ℝ.

Finally, you don't need Cantor's diagonalization for a proof. It is easy(1) to show that, for any real xAlternatively, assuming 0(1) depending on how deep you want to descend into the foundations of mathematics.

Re: Cryptic genetic variation in software: hunting a buffered 41-year-old bug

#37

Post by lmkg »

ntlve wrote: post #23
jdpage wrote: post #19

Earlier quoted context omitted.

From a real analysis standpoint... the definition of a 'closed set' in an N-dimensional metric space (of which Euclidean space, i.e. normal space, is an example) is as follows: a set C is 'closed' if and only if, given any sequence of elements (x_n) converging on x, such that (x_n) is a subset of C, it follows that x is also in C. Under this definition, 'closed' makes sense in the larger context, since in mathematics…

Out of curiosity, do you have any examples or references to something with examples of sets that are neither open nor closed?

The set of rational numbers that lie inside the interval [0,1].

This set is not closed there are non-rational numbers in that interval which are limit points of sequences that consist only of rationals. For example, any of the algebraic numbers. I think that all real numbers are limits of such sequences, but I might be mis-remembering some subtlety of Dedekind Cuts (one method for constructing the Reals).

This set is not open because any rational is the limit of a sequence of non-rational reals. This probably makes intuitive sense, but just for the sake of formality: To construct such a sequence for any rational r, start with the number x_1 = 1/pi, and approach by a factor of 1/pi at each step, i.e. x_n+1 = x_n + (r-x_n)/pi . x_n is irrational because pi is transcendental.

Any simple interval in R will be either closed or open on each end (but it could be closed on one and open on the other). It's more illustrative to create a set with a non-compact interior. In higher dimensions it's possible to have more exotic borders on an interval, but I think that border will just end up being isomorphic to a non-compact set in a lower dimension.

Re: Cryptic genetic variation in software: hunting a buffered 41-year-old bug

#38

Post by munificent »

kator wrote: post #31

I always cringe when I see or have to write: for ( ; ; ) or: while ( true ) etc. You just know you're setting yourself up for undocumented bugs later. I've been known to build "escape" vars into these like: int attempts = 1000; for(;attempts > 0;attempts--) { ** DO SOMETHING ** } if (attempts Where 1000 or whatever number is a reasonable estimate of the function's need to loop x 10 or etc.

Really? I use "while (true)" pretty frequently in my code. In my mind, all loops are composed of these parts:

1. Some initialization (optional). 2. Some stuff you do each iteration (optional). 3. Check the exit condition and exit the loop (optional). 4. Some stuff you do each iteration (optional).

"while" loops nicely handle the case where 2 is empty. "do while" loops handle 4 being empty. "for" loops handle both 2 and 4 being non-empty but only really accommodate 4 being a single expression.

For any other case where 2 is non-empty and 4 is more than a single expression, I just use a "while (true)" with an "if (...) break;" in the body.

Re: Cryptic genetic variation in software: hunting a buffered 41-year-old bug

#39

Post by munificent »

cgio wrote: post #18
entropy_ wrote: post #13

Earlier quoted context omitted.

I learned Math in a french-system school and yes, that's definitely a much better notation in my opinion. The difference between [] and () is not immediately clear, whereas [a,b] versus ]a,b[ makes it obvious that one includes a and b while the other does not. It also makes it easy to remember "open" and "closed" and what they mean in terms of whether or not the interval bounds are included or excluded

I don't know if it's very intuitive given that a and be are still inside the ][. Maybe a]..[b would make it clearer?

    a[..]b

Re: Cryptic genetic variation in software: hunting a buffered 41-year-old bug

#40

Post by john_b »

imurray wrote: post #7

It would be safest for most rand() functions to omit both zero and one, unless a user was really sure they wanted otherwise. If we were generating real numbers, we'd never see precisely zero or one. The fact that we do is an artifact of limited precision. These boundary cases cause problems in common computations like u.log(u) or (1-u).log(1-u).

Generating random numbers in (0,1) is mathematically different than generating random numbers, even from the same type of distribution, in [0,1), (0,1], or [0,1]. Equating all of these, as the article points out, rarely causes problems in practice, but it is nonetheless a conceptual error.

If you'll pardon me pulling out my soapbox for a moment, this kind of bug would be less common if the "programmers don't need math" attitude was not a successful meme in our culture. The notion of "between zero and one" may seem straghtforward and obvious, but is actually ambiguous. Perhaps, given the number of distinct floating point values that can be represented in the interval (0,1), it would hardly seem to matter what interpretation of "between zero and one" is used. But in mathematics you will never see such terminology used without a qualifying statement that clarifies* the meaning.

*E.g. "between 0 and 1, inclusive", "on the closed interval bounded by 0 and 1", "[0,1]", etc.

Post reply on HN