I've got a first draft with the newtype and just an instance for list. If you'd prefer fewer questions, please let me know ;) 0) I've cabalised it ("lazy-binary"), but I don't have anywhere to host it. Would it be appropriate to host on darcs.haskell.org or HackageDB (yet?). Suggestions? 1) The fact that serialisation is fully strict for 32760 bytes but not for 32761 makes the direct application of strictCheck intractable. Do you have any ideas how to circumvent that? ((unLazy . decode . encode . Lazy) `asTypeOf` id) (take 32760 (repeat ()) ++ undefined) => undefined ((unLazy . decode . encode . Lazy) `asTypeOf` id) (take 32761 (repeat ()) ++ undefined) => lots of ()s and then undefined 2) Also, any suggestions for other datatypes to provide default instances for? Tree type structures immediately raise the question of which traversal should be the default. I'm learning towards providing none since the goal of constant space usage actually depends on the serialisation order matching how the deserialised tree will be traversed. 3) I don't think it is applicable in anyway whatsoever to strict types like Int, Data.Set, and Data.Sequence? Counter-arguments? 4) Perhaps the tight correspondence between serialisation and traversal necessary for constant space usage does indeed mean that the instance for the lazy list is the only appropriate one to provide. Perhaps the Chunks data type and a function splitN :: Int -> [a] -> Chunks [a] would also be helpful. Thanks! 16, 2007 12:45 PM, Don Stewart wrote:

dons:

...

nicolas.frisby:

...

I've noticed a few posts on the cafe, including my own experience, where the spine-strictness of the Binary instance for lists caused some confusion. I'd like to suggest an approach to preventing this confusion in the future, or at least making it easier to resolve.

Having decided that it is indeed appropriate for some standard instances to be strict by default [1], I think it would be beneficial to standardize an approach for expressing that a lazy instance is expected. I propose the following newtype be added to Data.Binary. A demonstration immediately follows.

...

newtype Lazily a = Lazily { unLazily :: a }

...

-- example instance instance Binary a => Binary (Lazily [a]) where -- lazy get and put

Now

...

[1..] = (unLazily . decode . encode . Lazily) [1..]

instead of

...

_|_ = (decode . encode) [1..]

This email is a request for comments on this concept. I think it is a minimal way of expressing the intent that the serialisation be lazy [2]. Please share any concerns or suggestions. I'll submit a patch once the discussion is complete... or if it becomes inactive ;)

I think this is a good compromise: allowing laziness for those who need it, in a clean manner. How about we provie

Data.Binary.Lazy

with the Lazy newtype, and lazy instances for types that make sense to be so?

For now, this can be developed as a single module depending on Data.Binary . What do you think, Nick?

I'd like to also use strictCheck, as we did for the stream fusion library, to state and check strictness properties for the instances, since getting this clear and correct seems to be a common FAQ with Binary.

-- Don

On Mon, 2007-11-19 at 13:39 -0800, Don Stewart wrote:

nicolas.frisby:

...

I've got a first draft with the newtype and just an instance for list.

If you'd prefer fewer questions, please let me know ;)

0) I've cabalised it ("lazy-binary"), but I don't have anywhere to host it. Would it be appropriate to host on [1]darcs.haskell.org or HackageDB (yet?). Suggestions?

You can host it on code.haskell.org, ask for an account here:

I think we should consider if a lazier serialisation of lists shouldn't be the default first before thinking about forking the whole library. It depends on how much laziness you want. We could certainly make it so that this is true: (decode . encode) [1..] = [1..] rather than giving _|_. However the approach of Data.Binary is lazy serialisation but in chunks, big chunks. So while the above may be true, this would not be: (head . decode . encode) [1, _|_] = 1 because we generate 32k chunks of data when serialising. But do you really need it to be this lazy? Would it enough for it to be lazy in chunks. There is a good argument I think that the current fully strict serialisation is bad just from a performance perspective, and that instead we should serialise lists semi-lazily, using a chunked representation. For example Neil's serialisation library uses length prefixed chunks with a maximum chunk size of 255. The end of a list is denoted by a 0 length final chunk. This has the advantage that we only have to force a limited number of elements (to find the length) before serialising. If you want it really lazy then it would have to flush after each element to create a new lazy bytestring chunk. Note that flushing this often looses many of the performance advantages of the Data.Binary stuff.

...

1) The fact that serialisation is fully strict for 32760 bytes but not for 32761 makes the direct application of strictCheck intractable. Do you have any ideas how to circumvent that?

Test using a much smaller chunk size. I'd test sizes from 1 to something like one more than the machine word size.

...

2) Also, any suggestions for other datatypes to provide default instances for? Tree type structures immediately raise the question of which traversal should be the default. I'm learning towards providing none since the goal of constant space usage actually depends on the serialisation order matching how the deserialised tree will be traversed.

Lazy Arrays?

...

3) I don't think it is applicable in anyway whatsoever to strict types like Int, Data.Set, and Data.Sequence? Counter-arguments?

Well, atomic types like Int, I don't think it makes sense, but Sets and Sequence are lazy, aren't they?

Sequences are like spine strict lists. Sets are strict in as much as the element type's (==) function is strict.

...

4) Perhaps the tight correspondence between serialisation and traversal necessary for constant space usage does indeed mean that the instance for the lazy list is the only appropriate one to provide. Perhaps the Chunks data type and a function splitN :: Int -> [a] -> Chunks [a] would also be helpful.

Yes, it is probably the only lazy instance anyone cares about, anyway.

Yes. So I think we should be clear about what we want and see if we can't just fix the default. Duncan

On Mon, 2007-11-19 at 20:06 -0600, Nicolas Frisby wrote:

In light of this discussion, I think the "fully spine-strict list instance does more good than bad" argument is starting to sound like a premature optimization. Consequently, using a newtype to treat the necessarily lazy instances as special cases is an inappropriate bandaid.

I agree.

My current opinion: If Data.Binary makes both a fully strict list instance (not []) and a fully lazy list instance (this would be the default for []) available, then that will also make available all of the other intermediate strictness. I'll elaborate that a bit. If the user defines a function appSpecificSplit :: MyDataType -> [StrictList a], then the user can control the compactness and laziness of the serialisation by tuning that splitting function. Niel's 255 schema fits as one particular case, the split255 :: [a] -> [StrictList a] function. I would hesitate to hard code a number of elements, since it certainly depends on the application and only exposing it as a parameter maximizes the reusability of the code.

Fully lazy is the wrong default here I think. But fully strict is also not right. What would fit best with the style of the rest of the Data.Binary library is to be lazy in a lumpy way. This can give excellent performance where as being fully lazy cannot (because the chunk size becomes far too small which increases the overhead). Has anyone actually said they want the list serialisation to be fully lazy? Is there a need for anything more than just not being fully strict? If there is, I don't see it. If it really is needed it can be added just by flushing after serialising each element.

"Reaching for the sky" idea: Does the Put "monad" offer enough information for an instance to be able to recognize when it has filled a lazy bytestring's first chunk? It could cater its strictness ( i.e. vary how much of the spine is forced before any output is generated) in order to best line up with the chunks of lazy bytestring it is producing. This might be trying to fit too much into the interface. And it might even make Put an actual monad ;)

That is something I've considered. Serialise just as much of the list as is necessary to fill the remainder of a chunk. Actually we'd always fill just slightly more than a chunk because we don't know how big each list element will be, we only know when we've gone over. Duncan

On Mon, 2007-11-19 at 20:22 -0600, Nicolas Frisby wrote:

On Nov 19, 2007 4:16 PM, Duncan Coutts wrote:

...

On Mon, 2007-11-19 at 13:39 -0800, Don Stewart wrote:

...

nicolas.frisby:

*snip*

...

...

...

1) The fact that serialisation is fully strict for 32760 bytes but not for 32761 makes the direct application of strictCheck intractable. Do you have any ideas how to circumvent that?

Test using a much smaller chunk size. I'd test sizes from 1 to something like one more than the machine word size.

Let me clarify "circumvent that." strictCheck uses a bounded search starting at 1 and proceeds to some limit. The Binary instance used in the example was the fully lazy one for lists: a get/putWord8 for each constructor. Even so, it was effectively spine-strict up to 32k bytes (which was 32k elements b/c of the use of unit) because (I think that) the first chunk of the lazy bytestring wasn't being generated by encode until it was full. If you asked strictCheck to go from 1 to 32k, I don't think it would finish. So by circumvent, I mean: How can we apply the essential ideas of strictCheck when our chunks are so big?

We don't. We test it with a variety of small chunk sizes. That is the sensible thing to do.

Obviously, the iterative search cannot just proceed by one element at a time; but then we lose the obvious meaning of "add one more _|_. I don't see an obvious candidate for how to alter the _|_-ridden test vector generation. Moreover, it's "proposed output" is wrong when considered from the Big Chunks perspective--we don't necessarily want Chitil's least strictness.

Indeed. As I've said, Data.Binary is lazy but in a chunky way where within each chunk it is strict.

...

Sequences are like spine strict lists. Sets are strict in as much as the element type's (==) function is strict.

Let me refine how I posed that question. A predicate: if you enter "Package.fromList [1..]" at the ghci prompt and you get no intermediate results, then that was a "strict type."

Right, because (==) for Int is strict, and Set.fromList uses (==) on each element. Sorry, I was just being pedantic by saying that it depends on the strictness of (==).

I'm assuming that if the Show instance doesn't produce intermediate results, then the serialisation technique can't handle intermediate results (i.e. chunking) either--at least not in a general enough way to include it in a library.

So if you did this test with my proposed list instance (and you somehow slowed your computer right down so you could see what was going on) you'd see it wait a sec, then print out 32k of serialised list elements, then wait again and emit another chunk. So lazy, but in strict chunks. Duncan