Thread View: comp.lang.functional
4 messages
4 total messages
Started by Stephen J Bevan
Sun, 26 Jul 1992 17:44
programs that are too lazy
Author: Stephen J Bevan
Date: Sun, 26 Jul 1992 17:44
Date: Sun, 26 Jul 1992 17:44
63 lines
3011 bytes
3011 bytes
I've defended lazy* evaluation in a previous message, now I have
question that may give some ammunition to the strict* camp.
Consider the following Haskell fragment which reads lines data from a
file into the "store" :-
read_ASCII_Store st file fail succ = readFile file fail (succ . store)
where
store = (foldl (flip process_line) st) . (map words) . lines
where "process_line" has the form :-
process_line :: [String] -> Store -> Store
This works fine. It is nice and lazy i.e. if you invoke it, it does
not do anything until you actually try to access some of the values of
"store". However, there is a price to pay for this. When the input
file is reasonably large, this creates a large amounts of "thunks"
when reading in the data, in fact the "thunks" dominate the
proceedings and cause much more heap to be used than should be
necessary. (It runs out of space in a 5Mb for an "interesting" input
file)
This appears to be well known problem (a number of people here have
had similar problems anyway), and the suggested solution is to "force"
the store at regular intervals so that it fully evaluates itself.
This results in the following code, where 100 is the number of lines
to read between "forcing" :-
store xs = store_loop 0 st (lines xs)
store_loop n st [] =
if (st == st) -- force the store
then st
else error "the FORCE is not with us"
store_loop n st stuff =
let st' = process_line (words (head stuff)) st
in if (n `mod` 100 == 0)
then if (st' == st') -- force the store
then store_loop (n+1) st' (tail stuff)
else error "the FORCE was not with us"
else store_loop (n+1) st' (tail stuff)
This works well, and keeps the usage down to under 2Mb for the input
that previously ran out of heap. However, there are a couple of
things that bother me about this :-
1. The extra amount of work that has to be done in "forcing" the store.
This bumps up the runtime.
2. A simple, one-liner using higher order functions has turned into a
10 line tail recursive loop. Now being a Schemer at heart, I have
no particular problem with this, but it does seem to go against the
whole idea of "higher order functions are good" which most fp books
espouse.
So, I'm asking the net at large for advice. Does anybody know of any
other methods of keeping the heap usage low and that do better in
answering 1&2? Something using continuations or monads maybe?
bevan
* apologies for the imprecise terminology, I hope you all know what I
mean anyway.
Re: programs that are too lazy
Author: Julian Seward (DRL PhD)
Date: Sun, 26 Jul 1992 22:26
Date: Sun, 26 Jul 1992 22:26
45 lines
2342 bytes
2342 bytes
Steven J Bevan writes: | This works well, and keeps the usage down to under 2Mb for the input | that previously ran out of heap. However, there are a couple of | things that bother me about this :- | | 1. The extra amount of work that has to be done in "forcing" the store. | This bumps up the runtime. Hmm ... but not by much. | 2. A simple, one-liner using higher order functions has turned into a | 10 line tail recursive loop. Now being a Schemer at heart, I have | no particular problem with this, but it does seem to go against the | whole idea of "higher order functions are good" which most fp books | espouse. I have a couple of comments on this. Firstly, the problem is you are getting 000's of thunks. The problem is *not* the use of a higher-order function. Even if you unfolded the definition of "foldl" at the parameterisation shown, the program would behave the same. Secondly, a few minutes of investigation and a few changed lines made a massive difference to the usability of the program. In my book this is a very small price to pay for the convenience of a language as expressive as Haskell. I believe a few (say five at most) strategically placed hyperstrictnesses (so to speak) can make a big difference to the space behaviour of programs tens of thousands of lines long. Using a heap-profiling compiler, it is easy to spot the functions filling the heap up with thunks. For this reason, I believe the Haskell committee should consider the provision of two built-in functions: hyperstrict, whnf :: Eq a => a -> b -> b both of which evaluate their first argument (fully or to whnf) and return the second. We can simulate this at the moment using Haskell 1.2, but it might be more efficient if compilers could regard these as primitive. Jules
Re: programs that are too lazy
Author: Stephen J Bevan
Date: Mon, 27 Jul 1992 10:22
Date: Mon, 27 Jul 1992 10:22
62 lines
3375 bytes
3375 bytes
In article <SEWARDJ.92Jul26232657@r6.cs.man.ac.uk> sewardj@cs.man.ac.uk (Julian Seward (DRL PhD)) writes:
| 1. The extra amount of work that has to be done in "forcing" the store.
| This bumps up the runtime.
Hmm ... but not by much.
How can we know this? All I committed myself to was that the runtime
increased. I can't say by how much, as without forcing the store it
is either slower or doesn't fit in the available heap. However,
intiution tells me that doing repeated full equality tests on 7 AVL
trees containing 10,000+ elements each cannot be a cheap operation :-)
| 2. A simple, one-liner using higher order functions has turned into a
| 10 line tail recursive loop. Now being a Schemer at heart, I have
| no particular problem with this, but it does seem to go against the
| whole idea of "higher order functions are good" which most fp books
| espouse.
I have a couple of comments on this. Firstly, the problem
is you are getting 000's of thunks. The problem is *not*
the use of a higher-order function.
Ah, but I never said it was. All I pointed out was that a solution to
the problem involved removing the HOF and replacing with an explicit
loop. If I hadn't have been a HOF in the first place, the solution
whouldn't have seemed such a drastic change.
Even if you unfolded the definition of "foldl" at the
parameterisation shown, the program would behave the same.
Actually it runs out of heap quicker than the foldl version. I guess
foldl isn't being optimised by the compiler.
..., I believe the Haskell committee should
consider the provision of two built-in functions:
hyperstrict, whnf :: Eq a => a -> b -> b
both of which evaluate their first argument (fully or to whnf)
and return the second. We can simulate this at the moment using
Haskell 1.2, but it might be more efficient if compilers could
regard these as primitive.
Doesn't this move us back into the realms of separate annotations. I
thought many people don't like as there is too much opportunity for
the user to make a mistake i.e. "hyperstricting" everthing in sight in
the hope of efficiency. Alternately couldn't you argue that as most
of the time you want strict evaluation, you'd be better off with a
language were that was the default and annotating it with "lazy" at
appropriate points? For example, I have a much better feel for where I'd
want a strict version to be lazy than I do about where I'd want a lazy
version to be strict. Is this the mark of a novice lazy programmer?
That notwithstanding, if the above proposal means I can remove the
loop and replace it with one hyperstrict/whnf call in the
read_ASCII_Store definition, then I'm all for it (but then what do I
know :-)
bevan
Re: programs that are too lazy
Author: Andrew Koenig
Date: Mon, 27 Jul 1992 14:06
Date: Mon, 27 Jul 1992 14:06
22 lines
1318 bytes
1318 bytes
In article <SEWARDJ.92Jul26232657@r6.cs.man.ac.uk>, sewardj@cs.man.ac.uk (Julian Seward (DRL PhD)) writes: > I believe > a few (say five at most) strategically placed hyperstrictnesses (so to speak) > can make a big difference to the space behaviour of programs > tens of thousands of lines long. Hmmm... I've heard from my friends in the ML community that they're thinking about introducing a new primitive to make it easier to write lazy programs in ML, much like delay/force in Scheme. Now I see discussion of introducing a strictness primitive in Haskell. The two camps are moving closer together. Indeed, the question begins to look like a human-factors one: is it more convenient to use a strict language where the strictness can be turned off on request or a lazy language that can be made strict in places? -- --Andrew Koenig ark@europa.att.com
Thread Navigation
This is a paginated view of messages in the thread with full content displayed inline.
Messages are displayed in chronological order, with the original post highlighted in green.
Use pagination controls to navigate through all messages in large threads.
Back to All Threads