2 ms·
Loop Invariants Abbreviate Induction Proofs
- Someone 12y ago"…proves that when the loop terminates…" _if_ the loop terminates. That still is something you will have to prove. For example, one could call 'sum' end up with pointers into different arrays. That in itself triggers undefined behavior in C, but let's ignore that, and also assume that pointer addition wraps around, so that calling sum( &p[1], &p[0]) will eventually return. Even then, there is a troublesome area: the begin and 'end' arguments might have different alignment. (Can one get that within a single C array? Maybe, on some platforms, by creating an array of unions, where the first element of the union contains a short and a double, and the alternative a double and a short)
- robert_tweed 12y agoMy immediate observation was simply that if end < begin then the loop will possibly never terminate, or might terminate after consuming all memory iff the pointer eventually overflows to zero and doesn't cause a null pointer exception in the process. That could be fixed with a guard of course; it just happens that the program as given doesn't have one. (that's essentially the same point as your example showing referencing elements in the wrong order; it also does not address the question of whether the pointers are even in the same logical array or not). Still, apart from that, it's a nice article that succinctly explains a concept in an area where I find most of the literature tends to be somewhat intractable (formal methods). I say this as someone who's had a lot of interest in the topic for many years, but no background in it, so my knowledge is mostly limited to the contents of articles like this one. I do however really like the idea of using axioms and invariants in place of runtime assertions as a way to prove correctness of certain parts of applications. I think in combination with higher level unit & system tests we could have get a fairly practical system of showing both the correctness and applicability of solutions (as there's no point in having a system that is provably correct but solves the wrong problem). It's something I plan to get around to working on some day.
- robert_tweed 12y agoWRT your point about alignment - there is certainly no guaranteed alignment in C, so if you have (double star[1]) where (sizeof double) is 8 there is no guarantee that your pointer is evenly divisible by 8. Most compilers will correctly align something like an array of doubles, but if you have something like a struct with a char followed by a double, it's unlikely that the compiler will add 7-bytes of padding to ensure that the double is aligned correctly. It should not be possible to get two unaligned pointers if they are taken from the same array. However, there's nothing to say that the pointers actually point to an array of doubles as the code assumes. As you rightly point out, there's no guarantee the pointers are even into the same array. To use the struct example again, you could have an array of structs with a total size 9 bytes and therefore, to correctly walk that array, you would need to go in increments of 9. However, by taking the address of just the double element within the struct (rather than the base address of the element itself) you have just performed a sort of "type safe but really unsafe" pointer conversion. The code will now try to walk from point A to point B by adding 8 bytes each time (because it thinks (double star) is an array of doubles), but the elements are actually offset by 9 bytes each. E.g.: struct my_struct { char confusticator; double number; } my_struct my_array[10]; double* first = &my_array[0].number; // base address double* second = &my_array[1].number; // base address + 9 ! There's no alignment issue with unions because if the above were a union rather than a struct then the total size would be 8 bytes (the size of the biggest element) and both elements would have an offset of 0. You're probably thinking of "safe" unions from other languages that resemble structs but are tagged in some way to indicate which of the values is in use. C unions just lay the values over the top of each other, so you better not try to use the wrong one! Trying to prove correctness of anything involving C unions would be a challenge. Incidentally, when I was first starting out with C years ago, I had a lot of problems with pointers (as everyone does). I learned a lot of defensive programming techniques, one of which is to never construct a loop where the termination expression is based on equality; instead use (x < y) because that way, if something happens like begin and end being reversed, the loop will always terminate immediately. It also mitigates the problem is differently aligned pointer comparisons. This is one of the things that bothers me a about iterators in C++11. Fortunately iterators themselves are safe; it's just that they encourage (and in fact, require) writing code in a way that is potentially unsafe. [1] For "star" read an asterisk character. I cannot believe it's 2014 and Hacker News has no way to escape a goddamn asterisk in a comment unless it's in an indented block!