Re: Different implementation for lines to fix a space leak (was: Make lines stricter ...)

On Monday 04 October 2010 20:15:07, Duncan Coutts wrote:

On 24 September 2010 15:21, Daniel Fischer wrote:

...

Proposal: A stricter implementation of lines.

Reason: The current implementation causes a space leak (cf. http://homepages.inf.ed.ac.uk/wadler/papers/leak/leak.ps), at least in GHC.

The proposed implementation fixes the leak at the small cost of being stricter if the first _|_ in the String is the first character of a line.

Discussion period: Three weeks, until 15th October (because of ICFP).

Ticket: http://hackage.haskell.org/trac/ghc/ticket/4334

My gut instinct is that we should not make lines stricter.

I didn't see a way without changing the strictness properties at first. Now there *seems* to be one, although I have doubts concerning its reliability to fix the leak. It's certainly more delicate than the stricter version.

Generally the list library is as lazy as possible, except when there are compelling reasons otherwise. I am not yet convinced that this proposal meets that standard.

Have we thought about the opposite issue, that there may be programs that rely on the current non-strict version for correctness or memory behaviour?

The possibility that some programmes rely on the current behaviour certainly exists. Though, the only change in behaviour is when the first Char on a line is bottom, so I don't expect it would affect many programmes. The memory behaviour can only be worse (by more than a few bytes) when the first Char on a line is the result of a space-demanding computation for the stricter version and not at all (as far as I can see) for the new suggestion. I'd be surprised if that affected any programme negatively.

We currently have an open proposal on making intersperse less strict because it caused practical problems (unexpected memory behaviour).

There's also an issue of consistency with other functions in the list library. The lines function is similar in many ways to group / groupBy, and with the proposed change the strictness properties of these functions would be inconsistent. Such inconsistency has a cost in terms of programmers being able to predict and reason about strictness and space use (simply because if its inconsistent then it is harder to remember).

Agreed. That's why I favour the new suggestion (until someone comes forth with a reliable way to fix the leak or someone finds that it doesn't fix the leak in real use cases - it worked in my tests, but those were fairly simple).

The strictness of lines is pretty subtle. I think it would help our discussion if people reading this thread look at the strictness properties given in the ticket.

Duncan