Cryptic genetic variation in software: hunting a buffered 41-year-old bug(cryptogenomicon.wordpress.com) |
Cryptic genetic variation in software: hunting a buffered 41-year-old bug(cryptogenomicon.wordpress.com) |
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.
Under this definition, 'closed' makes sense in the larger context, since in mathematics, if an operation is 'closed' on a set, that means that applying the operation to elements of the set always yields another element of the same set.
Open is a bit more awkward. A set O is 'open' if and only if the complement of O (i.e. the set of all points not in O) is closed. So open is kind of the opposite of closed, hence the convention. Of course, it isn't really the opposite of closed, since there are sets which are neither closed nor open.
tt;dr (too technical; didn't read) in maths, 'closed' usually means 'I can do stuff inside this set without falling out of it'. In the case of intervals, the 'stuff' in question is taking a limit of a convergent sequence.
With a closed interval it eventually return a bound instead of getting smaller/larger - continuing.
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 other real numbers less than one. (Proof by Cantor's diagonal: write out a list of all such numbers and you can always construct another which wasn't on the list, even when the list is infinite.) In contrast, the closed interval [0, 1] has a definite maximum element, the number 1.
This seems like a good example of poor UX in mathematics; the terms are too similar and can only be learned by memorization, the notations likewise. Good luck changing it though; Wikipedia informs me that there are no less than two ISO standards codifying it.
There is a perfectly clear notation in the Wikipedia page, however: (a,b) = {x∈ℝ|a<x<b}; [a,b] = {x∈ℝ|a≤x≤b}
The rational numbers are like this too.
All the rational numbers between 0 and 1 also increase arbitrarily close to 1 with no largest element. You can prove this by simple contradiction: For every rational number x < 1, there is another rational number y = (x+1)/2 with x < y < 1. So the set of rational numbers less than 1 also has no largest element.
Actually real numbers can be defined (axiomatized) in terms of the least upper bound property -- every set of real numbers that's bounded above has a least upper bound. So you could actually have a set S of rational numbers that gets arbitrarily close to something like sqrt(2) from below. S then has no rational least upper bound -- for every rational number x greater than or equal to every element of S, there is another rational number y greater than or equal to every element of S but smaller than x.
Note that a set of real numbers need not contain its upper bound -- as you noted, a bounded open interval doesn't contain its upper bound.
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 x<1, x+(1-x)/2 is real, less than one, and strictly greater than x.
Alternatively, assuming 0<x<1, write x in decimal, and increase the first digit less than nine by one to get a larger real less than one. There is such a digit because 0.9999999… is not less than one.
(1) depending on how deep you want to descend into the foundations of mathematics.
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 of intervals. It took me a while to completely understand the concept but after that understanding limits was relatively easier; even otherwise "neighborhood" as a concept is interesting in itself.
[1] http://www.math.boun.edu.tr/instructors/ozturk/eskiders/guz1...
Thanks for everyone's input. I think I have a clear understanding of the open/closed paradigm now.
for ( ; ; )
while ( true )
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 <= 0) {
** BAIL ***
}
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.
[0] Or utterly catastrophic. Think embedded system with limited debugging facilities. This kind of bug could manifest as the system completely locking up, and take much, much longer to track down than a "infinite loop detected!" message in an error log.
1) Algorithm FT says:
1. Generate u. Store the first bit of u
as a sign s (s=0 if u<1/2, s=1 if u>=1/2).
if ( u <= 0.5 ) s = 0.0;
else s = 1.0;
a uniform distribution over (1, 2147483562)
More stories like that?
I've never used ranlib; I hope the documentation can be cleaned up at least. On the other hand, anyone who has read A Deepness in the Sky will surely feel that it is unlikely in the long term.
I wonder about the resolution: was snorm() reimplemented correctly, or was an RNG with the 'wrong' interval supplied?
You could use that argument about any of the random numbers that your rng returns. "Hey, 0.023 is infinitesimally unlikely to occur, so let's exclude that as well".
Generally when I use a real-valued rng, the numbers generated are meant to be 'representative' of what I should get from the distribution. And when I get e.g. 0.023, it kind-of means "0.023 and/or numbers near to 0.023". If I excluded 0.023 from the possible results of the rng, then I would have a 'hole' in my distribution 'in the region of' 0.023.
Maybe what you want is to go from the possible rnds:
0.000, 0.001, 0.002, 0.003, ... , 0.999
to:
0.0005, 0.0015, 0.0025, ... , 0.9995
whereas with your suggestion, you are under-representing the boundary numbers near to 0 and/or near to 1. Generally not a problem I guess, but what you are doing is, imo, 'wrong in theory', even though your high-precision floats will probably cover it up ok in almost all cases.
I agree with you about 0 and 1 causing problems when they are fed into other functions - e.g. generating Gaussian rngs by using InverseCumulativeGaussian(0.0) - a bug I wasted some time hunting down in my company's rng library. My view was that the developer who wrote the library did not understand the maths of what he was doing, rather than that the 0to1 random number generator was at fault.
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.
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.
Proof that it's not closed: the sequence (1, 1/2, 1/4, 1/8, ...) is entirely inside the interval, but converges on 0, which is outside the interval, therefore etc.
Proof that it's not open: the sequence (2, 3/2, 5/4, 9/8, ...) is entirely outside the interval (i.e. inside the complement), but it converges on 1, which is inside the interval (i.e. outside the complement). Thus the complement of the interval is not closed, therefore etc.
I don't prefer to exit from the middle of a loop, but if that's the most succinct way to implement the correct behavior, I'll do it. I think short code that exits from the middle is less error-prone than code that has to be more convoluted to put the exit at the top of bottom.
> Putting an escape hatch in the loop setup makes it less likely that an operationally-problematic[0] infinite loop scenario will be triggered.
An escape hatch is yet more code that has to be tested and debugged. What if the escape hatch triggers to early?
> [0] Or utterly catastrophic. Think embedded system with limited debugging facilities.
Sure, but unusual platforms require unusual coding styles. If I was targeting that I might adjust my practices.
Note I said only way out. The point is that if "the" (intended) exit can't reasonably be in the loop condition, then adding an escape hatch to have a second way out is useful.
Assuming C you can even just compress the whole thing to a for_x_tries(n) macro.
> What if the escape hatch triggers to early?
You'll get a helpful message and can bump the count. Easily-isolated errors are preferable to frozen/DoS'd systems.
a[..]b