RE: User defined Ix instances potentially unsafe
[Here's a possible Haskell 98 Library Ix "typo"] | > > An implementation is entitled to assume the following laws about | > > these operations: | > > | > > range (l,u) !! index (l,u) i == i -- when i is in range | > > inRange (l,u) i == i `elem` range (l,u) | > | > So my "bug" is only in my mind. Sorry for bothering everyone. | | I don't think it's quite as straight-forward as that. | Hugs and ghc may conform to the Library Report, but the | behaviour is still undesirable, and IMHO should be fixed. I rather agree with this. But I'm not sure what the fix is. In thinking about this I've realised that there's an assumption in the Ix interface that (*) map index (range (l,u)) = [0..rangeSize (l,u)-1] That is, index maps an index densely into the range 0..N where N is the size of the array. Without this assumption, an array implementation would need to store the Int bounds of the array as well as the ix bounds. I bet that no Haskell implementation does this. If this were not so, the implementation of rangeSize in Section 5.2 would be utterly wrong rangeSize b@(l,u) = index b h + 1 The constraint (*) also specifies that 'range' returns subscripts in increasing order of index. That seems reasonable, but perhaps less important. One could alternatively say (*a) index (l,u) l = 0 (*b) index (l,u) u = rangeSize (l,u) - 1 In the spirit of making minimal changes/additions to H98, perhaps (*a) and (*b) would be better. Any thoughts? Simon PS: none of this answers Matt's original question which I can rephrase thus: if a user provides implementations of index, range etc that do not obey the specified invariants, can that crash the system? I would rather the answer were 'no'. But that means the implementation would have to check the output of 'index' against the size of the array allocated from the supplied bounds. Which means that in the common case that 'index' also makes such a check there'd be two checks. Unless the compiler was clever enough to eliminate one of them, which isn't easy since one is at the 'ix' type and the other at 'Int'.
Mon, 7 May 2001 03:15:16 -0700, Simon Peyton-Jones <simonpj@microsoft.com> pisze:
The constraint (*) also specifies that 'range' returns subscripts in increasing order of index. That seems reasonable, but perhaps less important.
It is important if elems should return elements in the same order as indices returns indices, and as listArray accepts. I'm afraid that making arrays robust wrt. bogus Ix instances at the cost of further overheads means a larger pressure to avoid Ix at all in other contexts. It's already avoided in Manuel's parallel arrays, and it was a trouble for me for making ghc's Array/UArray/IArray/MArray operations faster - for example there is an better implementation of compare which works only for index types with particular properties, including Int but not (Int,Int), and sticking to 0-based Ints would make this much simpler, as well as making packed strings implemented in terms of UArrays more efficient. There are other problems. The report says that repeated indices in array construction is an error. Ghc doesn't check that and lets later values win. To implement what the report says it would have to be less efficient: avoiding a separate array for marking which elements are initialized would need unsafePtrEq on each store and probably a loop after the construction which would replace missing elements with bottoms which are not unsafePtrEq, so initialization of another array can distinguish absent elements from elements taken from this array. I'm not sure whether I should still use Ix-based arrays in my unified collection experiments etc., which don't fit there well, or say STOP at some point, concentrate on 0-based Int-indexed dynamic vectors with the interface of sequences, optionally adding Array support as a Haskell 98 compatibility kludge. Having mutable arrays with immutable bounds is also a small problem. Generally Ix-based Arrays may become a larger trouble to support than they are really worth. -- __("< Marcin Kowalczyk * qrczak@knm.org.pl http://qrczak.ids.net.pl/ \__/ ^^ SYGNATURA ZASTÊPCZA QRCZAK
On 07-May-2001, Simon Peyton-Jones <simonpj@microsoft.com> wrote:
In thinking about this I've realised that there's an assumption in the Ix interface that
(*) map index (range (l,u)) = [0..rangeSize (l,u)-1] ... The constraint (*) also specifies that 'range' returns subscripts in increasing order of index. That seems reasonable, but perhaps less important. One could alternatively say
(*a) index (l,u) l = 0 (*b) index (l,u) u = rangeSize (l,u) - 1
In the spirit of making minimal changes/additions to H98, perhaps (*a) and (*b) would be better.
Given that (*a)+(*b) already pin the end-points, I *think* you might as well go all the way and use (*); I don't *think* the extra flexibility of (*a)+(*b) would be useful. Given a type T which satisfies (*a)+(*b) one can defined a new range function which sorts the elements by index range' b@(l,u) = sortBy compareIndex range b where compareIndex x y = compare (index b x) (index b y) and then after renaming range as e.g. unsortedRange and range' as range, the type will now satisfy (*). So for Haskell 200X, (*) would certainly be preferable, IMHO. For Haskell 98, I'm not sure; perhaps it is best to be conservative.
PS: none of this answers Matt's original question which I can rephrase thus: if a user provides implementations of index, range etc that do not obey the specified invariants, can that crash the system? I would rather the answer were 'no'.
I think the answer should be "no, unless the user specified the appropriate compiler option to disable array bounds checking".
But that means the implementation would have to check the output of 'index' against the size of the array allocated from the supplied bounds. Which means that in the common case that 'index' also makes such a check there'd be two checks.
If you really want to squeeze the last drops of performance out, then there's always that compiler option to disable array bounds checking...
Unless the compiler was clever enough to eliminate one of them, which isn't easy since one is at the 'ix' type and the other at 'Int'.
One possible way to eliminate them would be to add an extra method called unchecked_index or __unchecked_index to the Ix class. By default this would do the same as index class Ix t where ... __unchecked_index = index but you could define the instances for the standard library types such as Int, Char, etc. so that they just skip the check and return an out-of-range Int; for array operations such as (!) where you're going to do a range check on the value returned from index, you can safely use __unchecked_index instead. The reason for using a name such as __unchecked_index rather than just unchecked_index would be for strict compatibility with Haskell 98: to avoid clashing with user-defined identifiers, you need to use a name that is reserved for use by the implementation, Unfortunately, unless I missed something, Haskell 98 does seem to reserved any identifiers at all for use by the implementation, other than the standard reserved words, so I think even using a name like `__unchecked_index' here would not be 100% strictly Haskell 98 compatible. I think it would be good enough in practice, though. For Haskell 200X, where strict backwards compatibility is not required, unchecked_index should be introduced as a documented new method for the Ix class. -- Fergus Henderson <fjh@cs.mu.oz.au> | "I have always known that the pursuit | of excellence is a lethal habit" WWW: <http://www.cs.mu.oz.au/~fjh> | -- the last words of T. S. Garp.
If you really want to squeeze the last drops of performance out, then there's always that compiler option to disable array bounds checking...
If you mean: "disable array bounds checking" == assume that the (possibly user-supplied) Ix instance is correct but still perform the Ix-based range check. [This is the status quo.] "enable array bounds checking" == perform a possibly redundant range check because the Ix instance may be broken then this sounds like an excellent idea. Especially given that Pascal compilers (not exactly new technology) used to do a pretty good job of eliminating redundant bounds checks so I imagine that that redundant check could be eliminated from all the easy cases without too much work.
For Haskell 200X, where strict backwards compatibility is not required, unchecked_index should be introduced as a documented new method for the Ix class.
Is this enough? Most of the array code I write uses the higher-level operations like fmap and ixmap. Do I need unchecked versions of them too? Can the higher-level operations amortise the cost of those extra bounds checks? I think fmap can but ixmap can't and I haven't considered the others. -- Alastair Reid
participants (4)
-
Alastair Reid -
Fergus Henderson -
Marcin 'Qrczak' Kowalczyk -
Simon Peyton-Jones