Re: [Haskell-cafe] Laziness leaks
On 04/06/2008, at 10:12 AM, Ronald Guida wrote: I would ask, how do I examine the evaluation order of my code, but the answer is already available: use a debugger. Haskell already has debugging tools that do exactly what I need. (http://www.haskell.org/haskellwiki/Debugging) In particular, HOOD looks extremely interesting. I would recommend the GHCi debugger for looking at the evaluation order of code. Single stepping can be very illuminating. Bernie. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Laziness leaks
Ronald Guida wrote: [snip] By default, a lazy language will procrastinate. By default, a strict language will anticrastinate. Either way, I can waste resources by blindly accepting the default time management plan. Nice analysis. Would you like to put that (the whole thing, not just that last para) on the wiki? Jules ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
[Haskell-cafe] Laziness leaks
I was looking at the real time queues in [1] and I wanted to see what would happen if I tried to write one in Haskell. The easy part was translating the real time queue from [1], p43 into Haskell. The hard part is testing to see if the rotations really happen what they should. Basically, I decided to use Debug.Trace.trace to see when rotations were actually occurring. I pushed the numbers 1 to 10 into the queue, and then I popped the queue ten times. What I found is that none of the rotations would actually take place until the first time I actually tried to /display the value/ of a popped element. What I realized is that my test driver is lazy. I figured out that I could put a bunch of 'seq' functions in the test driver to get the rotations to happen. My demonstration code is in: http://hpaste.org/8080 This leads to two questions: 1. If I find a laziness leak, is 'seq' the appropriate way to plug it? 2. Is there any way to systematically search for or detect laziness leaks? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Laziness leaks
Ronald Guida wrote: I was looking at the real time queues in [1] and I wanted to see what would happen if I tried to write one in Haskell. The easy part was translating the real time queue from [1], p43 into Haskell. The hard part is testing to see if the rotations really happen what they should. Basically, I decided to use Debug.Trace.trace to see when rotations were actually occurring. I pushed the numbers 1 to 10 into the queue, and then I popped the queue ten times. What I found is that none of the rotations would actually take place until the first time I actually tried to /display the value/ of a popped element. What I realized is that my test driver is lazy. I figured out that I could put a bunch of 'seq' functions in the test driver to get the rotations to happen. My demonstration code is in: http://hpaste.org/8080 This leads to two questions: 1. If I find a laziness leak, is 'seq' the appropriate way to plug it? 2. Is there any way to systematically search for or detect laziness leaks? ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe I want to point out several non-causes of laziness. For a no-magic, no-surprise understanding, it is important to know both what causes laziness and what does not. A. The lazy list at rtqRear, which is originally a strict list. It is an invariant that every thunk you put there is [] or x:y. (As a result, it is unnecessary to make RTQueue a strict record, since you want two of the fields to be lazy, and the remaining field rtqRear is de facto strict.) B. rtqueue's thunked call to rotate, i.e., rtqueue f r []= let f' = rotate f r [] in RTQueue f' [] f' Originally f' is forced before the record is returned (SML convention). In Haskell the rotate call is thunked as f' and the record is returned. But there will not be an accumulation of such rotate thunks. For example if you snoc twice in succession and the first instance builds a rotate thunk: snoc p (snoc q (RTQueue f r [])) - snoc p (rtqueue f (q:r) []) - snoc p (RTQueue f' [] f') where f' = thunk - rtqueue f' p:[] f' where f' = thunk - f' is now forced by rtqueue's pattern matching on the 3rd param So if one snoc builds a rotate thunk, the next snoc kills it. And similarly any interleaving of queue operations. (head and tail add their extra pattern matching.) Thus it can be proved that Haskell lags behind the original by just one step in this regard. This is ok unless you're done with reducing asymptotic cost and start looking at constant factor cost. A true cause of laziness is in accumulating a chain of tail's and snocs without intermediate forcing, as observed. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Laziness leaks
Don Stewart wrote: 2. Is there any way to systematically search for or detect laziness leaks? Profiling, and looking at the Core. Being explicit about the evaluation strategy you want is a fine idea though. Albert Y. C. Lai wrote A true cause of laziness is in accumulating a chain of tail's and snocs without intermediate forcing, as observed. So I just thought of something. If laziness leads to laziness leaks, then is there such a thing as a strictness leak? I realized that the answer is yes. A lazy leak is a situation where I'm wasting resources to delay a sequence of calculations instead of just doing them now. But in a strict language, I might waste resources to compute things that I'll never need. I would call that a strictness leak. Now I could ask the dual question, How do I detect strictness leaks, and I would probably get the same answers: profiling, looking at object code, and being explicit about the evaluation strategy. Both types of leaks share a lot in common. In both cases, I'm wasting resources. If I have a real-time system, then either type of leak can cause me to a miss a deadline. With a strict evaluation strategy, I might miss a nearby deadline because I'm busy calculating things that I don't need until the distant future. With a lazy evaluation strategy, I might miss a distant deadline because I'm lazily putting off a calculation now. If I were a college student, then this would be a laziness leak: Professor X assigns a report, due in a month. Two days before the report is due, I'll head to the drugstore, load up on caffeine, and work for 48 hours straight to get it done. And this would be a strictness leak: Professor X assigns a report, due in a month. As soon as I leave the classroom, I'll head to the drugstore, load up on caffeine, and work for 48 hours straight to get it done. And this would be an effective solution: Professor X assigns a report, due in a month. I'll select 15 days, spaced out over the next month, and allocate four hours per day to work on the report. By default, a lazy language will procrastinate. By default, a strict language will anticrastinate. Either way, I can waste resources by blindly accepting the default time management plan. So the real question is How do I avoid laziness leaks or strictness leaks and apparently, the real answers are (1) learn how to recognize when the default plan will waste resources, and (2) learn how to express reasonable evaluation strategies in code. I would ask, how do I examine the evaluation order of my code, but the answer is already available: use a debugger. Haskell already has debugging tools that do exactly what I need. (http://www.haskell.org/haskellwiki/Debugging) In particular, HOOD looks extremely interesting. ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
Re: [Haskell-cafe] Laziness leaks
On Tue, 2008-06-03 at 20:12 -0400, Ronald Guida wrote: Don Stewart wrote: 2. Is there any way to systematically search for or detect laziness leaks? Profiling, and looking at the Core. Being explicit about the evaluation strategy you want is a fine idea though. Albert Y. C. Lai wrote A true cause of laziness is in accumulating a chain of tail's and snocs without intermediate forcing, as observed. So I just thought of something. If laziness leads to laziness leaks, then is there such a thing as a strictness leak? I realized that the answer is yes. I ask a similar question here albeit for a much narrower and more technical notion: http://lambda-the-ultimate.org/node/2273#comment-40156 and come to the same conclusion (at least for an even more narrow notion). ___ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
