November 2002 - Libraries

Instances in libraries (e.g., Control.Monad)
by C.Reinke 15 Nov '02

15 Nov '02

Hi, [yet another haskell list to subscribe to.. and I'll start with a rant, sorry - I've quickly scanned the archive, but this doesn't seem to have come up before, has it?] Problem: As noted elsewhere, we've been running into problems with Haskell's "fine" handling of instances while trying to combine some largish Haskell projects. As long as the language isn't changed, this problem needs to be accounted for in library designs. Concrete examples: Control.Monad.Error, Control.Monad.Reader These modules define lots of instances for (Either a) and ((->) a). Why? Obviously, they want to use them, but that's no excuse. Both Either and (->) are very popular type constructors, and currently, every project that wants to use these instances defines them somewhere. Result: as soon as you put two of these projects together, you get a clash! In current Haskell, defining instances of public classes for public types/constructors has side-effects running through the whole of any program using such a library. Quite apart from the facts that the module names typically gives no indication of these side-effects, and that the modules could have been implemented without them (using standard types/constructors was just more convenient), there's no way to get two such modules to work together in a larger project without changing them! Solution: I'd suggest a two-way approach: 1) There are some commonly expected, but unfortunately not predefined instances of public classes for public types, such as Monad and Functor for (Either a) or for ((->)a) These should go into separate modules, to be imported into every project depending on them. Result: no conflict, and each of the projects works, both on its own and in combination with other such projects. It is important that the instances can be imported selectively, without fear of getting other, unwanted, stuff in the process. ShowFunctions.hs would have been an example of this (where did that go, btw?). In Control.Monad.Error, the case is actually worse: not only does it have the unexpected side-effect of stealing some "standard" instances, it defines some of them in non-standard ways: instance (Error e) => Monad (Either e) where return = Right Left l >>= _ = Left l Right r >>= k = k r fail msg = Left (strMsg msg) Here, Error and strMsg are local to the Error module, and the design prescribes that fail *must* return Left of something, rendering it impossible to use this definition to get any other behaviour. 2) If a module needs instances of public classes for public types/constructors, but in non-standard ways, it should copy&rename either the class or the type/constructor. This way, the standard ADT services of the module mechanism prevent conflicts (the instances are still flowing around, but unseen..). Given that some syntactic sugar and other functionality depends on classes with fixed names, such as Monad, most modules will create their own variant of the type, not of the class. For instance, Control.Monad.Error would probably need to define its own variant of Either. That could be a simple newtype wrapper. I haven't checked the libraries systematically. This is just one example we ran into in practice (meaning that these libraries are actually used, making them vulnerable to complaints;-). Hope this makes sense? Claus PS. perhaps this suggestion got lost in the other thread, but could Haddock please show the source of any instances in the generated documentation?

1 0

RE: IOError vs. Exception vs. IOException
by Simon Marlow 14 Nov '02

14 Nov '02

> > Our feeling over here is that this is an unforced change, so in > > isolation it probably wouldn't be worthwhile. It'll break > some code, > > and the awkward squad paper will have to be updated to > comply (although > > we just noticed it is already wrong about the behaviour of > > Prelude.catch). > > > > However, if there's concensus that folk would prefer the alternate > > definition of IOError, then we're happy to go along with it. > > There have been three responses, all in favour of change. What's your > view now? I would rather see a confusing interface fixed than force > the other implementations to change their Preludes to implement it, > but then I have no investment in the old interface. Fine, I'm happy to go along with the change. Cheers, Simon

1 0

RE: getting a Binary module into the standard libs
by Simon Marlow 14 Nov '02

14 Nov '02

> > 3) I think we can all agree that we should buffer BinIOs. There are > > a few questions, given this: > > > a) Should multiple threads be allowed to write the same BinHandle > > simultaneously? If not, is an error thrown or is the behiour just > > left "unspecified"? > > b) Should multiple threads be allowed to read from the same > > BinHandle simultaneously? If not, ... > > c) Should one thread be allowed to write and another to read from > > the same BH simultaneously? If not, ... > > I believe GHC has a reader-writer lock on Handles so the answer is > that one thread blocks if another is already using it in a conflicting > way. > > Basically, I suggest doing whatever normal file Handles do. This is a tricky one. Doing whatever normal Handles do is the "right" way to approach this, but I fear it might be expensive. Handles have a single file pointer (if they have a file pointer at all), a buffer, and some other state. The Handle itself is protected by a lock, so that only one thread can access the state at a time. Currently, a BinIO handle caches the file pointer for speed, and doesn't protect this with a lock. BinIO handles might also need a cache. The "right" thing to do is to push this inside the Handle - use the Handle's buffer as the cache. Provide something like hOpenBin :: FilePath -> OpenMode -> IO Handle hPutBits :: Handle -> Int -> Word8 -> IO () hGetBits :: Handle -> Int -> IO Word8 hSeekBits :: Handle -> Integer -> IO () I don't know whether this would be acceptably fast or not. (I'll try to do some perf measurements on BinIO vs. BinMem later today, that should give us a rough idea). What about BinMem? Currently a BinMem is basically a flat array and a pointer. It has no lock; if you write or read from two threads simultaneously you can get race conditions. However, even with a lock, reading from two threads simultaneously isn't likely to be a good idea because of the shared file pointer. This is why I suggested having dupBin: dupBin :: BinHandle -> IO BinHandle which essentially gives you another file pointer to work with, so that two threads can safely read the same BinHandle at different points. (writing is still problematic - use BinIO if you want multithreaded writing). dupBin can be implemented for Handles, and hence BinIO too. It's fairly straightforward and seems useful anyway. Summary: - reading/writing the same BinHandle from two threads isn't useful unless the threads can have their own file pointers. ==> need dupBin - cacheing of the data in a BinIO should be done in the Handle, unless that's too expensive. (Hal: for now, just continue with what you had planned, if we decide to make some of these changes we can refactor later). Cheers, Simon

1 0

RE: getting a Binary module into the standard libs
by Simon Marlow 12 Nov '02

12 Nov '02

> Mon, 11 Nov 2002 10:12:57 -0800 (PST), Hal Daume III > <hdaume(a)ISI.EDU> pisze: > > >> putBits :: BinHandle -> Int{-size-} -> Int{-value-} -> IO () > > > Any reason not to make those Word8s instead of Ints? > > Any reason to limit value to 8? > > I've heard: endianness, but if we fiddle with parts smaller > than a byte > we already chose endianness when decided whether to fill > bytes starting > from the low or high bit! Starting from low bit implies LE, starting > from high bit implies BE - anything else is inconsistent. Well, we have to choose an arbitrary endianness for multibyte integers already - it doesn't matter which one we choose, as long as it is consistent. I suggested restricting putBits to a maximum of 8 bits because it's easy to implement and a good compromise. Once you have putBits up to size 8, you can implement everything else: the library is already implemented in terms of putByte/getByte, so the only further change is to use putBits instead of putByte for small numbers such as constructor tags. We could allow putBits to work up to size 32, which would mean our instances of Binary for the other integral types will be simpler, but the complexity is moved into putBits. It's not a big deal. I suppose this way you'd get to take advantage of 23 bit numbers, but that's not going to buy very much. > For the bit count - they are generally expressed as Ints, as anything > which is guaranteed to be quite small. Word8 for bit count is quite > arbitrary and increases explicit conversions which need to be made - > Int is more common than Word8. Agreed. Cheers, Simon

1 0

Re: getting a Binary module into the standard libs
by Marcin 'Qrczak' Kowalczyk 11 Nov '02

11 Nov '02

Mon, 11 Nov 2002 10:12:57 -0800 (PST), Hal Daume III <hdaume(a)ISI.EDU> pisze: >> putBits :: BinHandle -> Int{-size-} -> Int{-value-} -> IO () > Any reason not to make those Word8s instead of Ints? Any reason to limit value to 8? I've heard: endianness, but if we fiddle with parts smaller than a byte we already chose endianness when decided whether to fill bytes starting from the low or high bit! Starting from low bit implies LE, starting from high bit implies BE - anything else is inconsistent. Whether the format is portable or not, allowing the size to be larger than 8 doesn't change its portablility. So value could be Word8 or Word32 etc. For the bit count - they are generally expressed as Ints, as anything which is guaranteed to be quite small. Word8 for bit count is quite arbitrary and increases explicit conversions which need to be made - Int is more common than Word8. -- __("< Marcin Kowalczyk \__/ qrczak(a)knm.org.pl ^^ http://qrnik.knm.org.pl/~qrczak/

1 0

RE: getting a Binary module into the standard libs
by Simon Marlow 11 Nov '02

11 Nov '02

> This doesn't seem like an awful lot of work, and if it would > help getting > Binary into the hier libs, I'd be more than happy to do it. > Given Eray's comments, it might turn out to be faster. Great! > Simon: I have a version of the GHC Binary module, but I know that I've > mucked around with it quite a bit. I've also got the one off > of cvs in > ghc/compiler/utils/Binary.hs, which would probably be a better > (read: safer) starting place. Basically we want to add two functions: > > putBit :: BinHandle -> Bool -> IO () > getBit :: BinHandle -> Bool -> IO () I'd do it this way: putBits :: BinHandle -> Int{-size-} -> Int{-value-} -> IO () and similarly for getBits. It will be easiest if the size is not allowed to go over 8, because then you have to deal with endianness, and in any case we already have put for Int16, Int32 etc. written in terms of putWord8. Currently the binary format is endian-independent for the basic integral types. If you use Int, then a binary file written on one machine is still only useable on a machine of the same word size, but if you want a truly mobile binary file you can restrict yourself to the explicitly sized integral types. I think this is a nice property to keep. > It seems that in order to accomplish this, the BinMem > constructor needs to > be augmented with two fields, one Word8 which contains bits which have > been "put" but haven't yet been written to the array and another Word8 > which stores the current bit position we are at in this > Word8. Then, the > work comes down mostly to bit-twiddling in the putWord8 and putBit > functions (putBit being the simpler of the two). It seems the BinIO > constructor would require basically the identical thing, which means > perhaps this stuff should be added to the BinHandleState variable. BinMem and BinIO differ quite a bit here: for BinMem you can write straight into the array, whereas for BinIO we need a cache - a single byte at the least, but ideally more. BinMem is the most important case to optimise (for us in GHC anyhow), since BinIO is already significantly slower due to the overhead of the Handle interface. There should really be a closeBin function too; it's quite simple to add. Cheers, Simon

2 1

RE: getting a Binary module into the standard libs
by Simon Marlow 11 Nov '02

11 Nov '02

> > - How important is this? > > The motivation for my Binary library was to save space, whereas > Simon's motivation was to be fast (at any rate to be faster than > parsing text). Thus, a bitstream is potentially far more compact > than a bytestream, depending of course on the natural size of the > objects to be serialised. But the tradeoff is that a bytestream > is far quicker to build/read, because there is no tricky logic > required to ensure that bits are shifted to the right place etc. > > Different applications will require different characteristics. > There is no one-size-fits-all. I should add that I never actually benchmarked the speed difference between using bits and bytes, and I don't believe it's clearly a win to use bytes. There's the time to get the data off the disk, caching effects, etc. to take into account, all of which tend to be more important the more recent your machine is. I'd be delighted if someone would add support for bits to GHC's Binary library (to get a fair comparison) and did some measurements. It may be that there's no need to add an abstraction layer to provide support for both bits and bytes. Cheers, Simon

6 6

RE: getting a Binary module into the standard libs
by Simon Marlow 08 Nov '02

08 Nov '02

> I was wondering if it was on the list of things to do to get a Binary > module into the standard libraries. I know SimonM has a > version for GHC > and there's an NHC version (I think the original). I don't know about > Hugs. > > I ask because by putting it in the standard libs, library > developers could > feel more pressured to release their data structures with Binary > instances. Indeed. The only reason I didn't put my version into the libraries yet was because it differed somewhat from the NHC version, and I thought it would be a good idea to discuss what the interface should look like first. FYI, the main differences between GHC's Binary library and NHC's are described below. Keep in mind that GHC's Binary library is heavily tuned for speed, because we use it for reading/writing interface files. GHC's Binary class: class Binary a where put_ :: BinHandle -> a -> IO () put :: BinHandle -> a -> IO (Bin a) get :: BinHandle -> IO a NHC's Binary class: class Binary a where put :: BinHandle -> a -> IO (Bin a) get :: BinHandle -> IO a getF :: BinHandle -> Bin a -> (a, Bin b) putAt :: BinHandle -> Bin a -> a -> IO () getAt :: BinHandle -> Bin a -> IO a getFAt :: BinHandle -> Bin a -> a - For GHC, I added the put_ method. The reason is efficiency: you can often write a tail-recursive definition of put_, but not put, and one rarely needs the return value of put (I found). Each function has a default definition defined in terms of the other (in fact, I think I use put_ exclusively in GHC, and put could be taken out of the class altogether). - For GHC, I didn't implement getF. Instead, I have explicit lazyGet and lazyPut operations, to give me more control over the laziness: I only want laziness in a few well-defined places. - I implemented putAt and getAt as functions rather than class methods. There are lots of instances of Binary, so you save a few dictionary fields, and I didn't come across a case where I needed to override either of these. - GHC's library also works in terms of bytes rather than bits, again for efficiency (time over space). There are putByte and getByte functions for writing your own instances of Binary, whereas NHC has putBits and getBits. There are more differences in the rest of the interface, but these are the most fundamental ones. Cheers, Simon

3 2

getting a Binary module into the standard libs
by Hal Daume III 06 Nov '02

06 Nov '02

Hi, I was wondering if it was on the list of things to do to get a Binary module into the standard libraries. I know SimonM has a version for GHC and there's an NHC version (I think the original). I don't know about Hugs. I ask because by putting it in the standard libs, library developers could feel more pressured to release their data structures with Binary instances. - Hal -- Hal Daume III "Computer science is no more about computers | hdaume(a)isi.edu than astronomy is about telescopes." -Dijkstra | www.isi.edu/~hdaume

1 0

RE: IOError vs. Exception vs. IOException
by Simon Marlow 04 Nov '02

04 Nov '02

> On Mon, Nov 04, 2002 at 01:00:39PM -0000, Simon Marlow wrote: > > Our feeling over here is that this is an unforced change, so in > > isolation it probably wouldn't be worthwhile. It'll break > some code, > > and the awkward squad paper will have to be updated to > comply (although > > we just noticed it is already wrong about the behaviour of > > Prelude.catch). > > What should other implementations do? I'm not sure I understand the question - other implementations should follow whatever is decided for the library interface, right? I'm really not arguing either way, in fact I like the change, but perhaps we should think hard before breaking code. I haven't heard anyone else comment so far on whether they like/dislike the current Exception interface... anyone? Cheers, Simon

3 2