3 ms·
And how exactly do you propose to do that? Here's a variable length array. Valid indexes are either [0...length-1] or [1...length], depending on which indexin
by AnimalMuppet 4y ago
And how exactly do you propose to do that? Here's a variable length array. Valid indexes are either [0...length-1] or [1...length], depending on which indexing arrangement you prefer. You can make -1 impossible by using an unsigned type. But for the index of a variable length array, how do you make length+1 unrepresentable?
- lmm 4y agoUse some kind of range type, or, better, a type that represents "index into this array" (which needs some form of dependent typing, but is very much doable).
- AnimalMuppet 4y agoA range type has the problem that it's not necessarily valid indexes for this array - it could be for some other array. "Index into this array" is, as you say, better (presumably it keeps a pointer or a reference or something to the array), but even that isn't bulletproof. Something like realloc could shrink the array but keep the same pointer, or the array could be deallocated and a new one allocated that happened to get the same address. What you really need is that the array keeps track of its own limits - something like std::vector or Java's ArrayList. But then you're back to the overhead of checking each access. So... I'm still not seeing how you're making illegal states unrepresentable.
- lmm 4y ago> "Index into this array" is, as you say, better (presumably it keeps a pointer or a reference or something to the array), but even that isn't bulletproof. Something like realloc could shrink the array but keep the same pointer, or the array could be deallocated and a new one allocated that happened to get the same address. You can address that with some concept of lifetimes or ownership. > What you really need is that the array keeps track of its own limits - something like std::vector or Java's ArrayList. But then you're back to the overhead of checking each access. IME that's less good than having a dedicated type for "index into this array", even if the latter isn't perfect. A bounds-checked access using an offset from a different array might not be reading from uninitialized memory, but it's still overwhelmingly likely to be a programming bug.