On Mon, 2008-01-28 at 14:39 -0500, istarex wrote:

On Jan 28, 2008 1:07 PM, Neil Mitchell wrote:

...

To answer the question if Haskell has a "stack depth restriction ... like Java" the answer is no. It has a stack depth restriction, but its absolutely nothing like Java in the way it uses the stack, so you can't compare them. Fair enough.

...

My guess is that Istarex's inner thought might have been along the lines of "in Java if I do too much recursion I get a stack overflow, but Haskell only has recursion, does that mean I get into stack overflows all the time?". I could of course be entirely wrong ;-) Well, it wasn't quite that simplistic :-). I was considering a specifically non-tail recursive solution to a problem, and I was wondering if Haskell has an artificial recursion depth limit. I didn't stop to consider laziness, and I now realize there's a whole dimension of this question that I didn't consider. Thanks for the input guys.

You may want to look at http://www.haskell.org/haskellwiki/Stack_overflow While perhaps for a simple throw-away program it may be beneficial to write code that allocates unnecessary stack, I personally consider unnecessary stack use a bug. A stack overflow, to me, is always indicative of a bug.

Hi Adrian,

The "bug" is in ghc stack management. Why is it so important that the stack size is arbitrarily limited?

It's not, but it makes some things easier and faster. A better question is why is it important for the stack to grow dynamically. The answer is that its not.

It's just an intermediate data structure, no different from any other intermediate data structure you may build on the heap (well apart from it's efficiency). But I guess we would be in danger of having our programs run too fast if folk were silly enough to make use of the stack.

In C putting something on the stack is massively more efficient than putting it on the heap. In Haskell, there is nearly no difference, and I can imagine some situations where the heap is actually faster. I guess your comment about speed relates to that assumption?

So perhaps the current ghc defaults are too generous. What limit do you think should be placed on the stack size that a non buggy program can use?

The current limits are fine for virtually all cases. They abort on buggy programs, but its rare that a non-buggy program will need to change them. i.e. years of experience has ended up with good defaults. Thanks Neil

Jonathan Cast wrote:

http://www.cs.princeton.edu/~appel/papers/45.ps is the traditional cite here, no?

"Can be" is not the same as "is". A lot depends on exactly what you call a "stack" and the relative efficiencies of stack vs. heap implementations. Certainly my experience of library tuning tells me that (with ghc at least), designing your code and data structures to keep heap allocation down to an absolute minimum is very important. So I'm very sceptical about claims that burning heap is just as efficient. Heap allocation maybe just as cheap, but reclaiming costs more. A lot also depends on compiler (and associated rts), such as whether or not it translates to CPS, thereby in effect building a "stack" (in all but name) on the heap. So you could exactly have the same correct and *bug free* program giving a stack "overflow" on ghc, but not on a CPS based compiler (the CPS implementation just uses a shed load of heap instead). Other implementations (Chicken Scheme?) effectively build their heap on the stack, which never shrinks until it "overflows". Is that inherently buggy? Surely the alleged buginess of programs should not be dependent on choice of compiler/rst? As nobody has provided any sensible justification for the assertion that using lots of stack (vs. heap) inherently is bad (and that programs which do have bugs, by definition), it seems to me this is one of those quasi-religious beliefs, like (so called) "global variables" or the cyclic module dependencies being a bug (by definition). Yes, using lots of stack is clearly bad with ghc, but this is a ghc "bug". In fact the only reason these programs do use lots of stack (vs. heap) is just a peculiarity of ghc rts implementation, so it really should be ghc that fixes the problem, or at least admits responsibility :-) Regards -- Adrian Hey

ndmitchell:

Hi

...

implementations. Certainly my experience of library tuning tells me that (with ghc at least), designing your code and data structures to keep heap allocation down to an absolute minimum is very important.

Yes. Keeping allocation low is very important, be it heap or stack. Heap allocation is not free, its just not any more expensive than the stack.

...

A lot also depends on compiler (and associated rts), such as whether or not it translates to CPS, thereby in effect building a "stack" (in all but name) on the heap.

If you burn a lot of heap, for not much gain, that's still a bug, albeit one which large limits might be able to paper over for a short amount of time. Is the GHC stack not stored on the heap? I thought it was. I know the Hugs stack is stored on the stack, and the Yhc one isn't.

...

Surely the alleged buginess of programs should not be dependent on choice of compiler/rst?

Hmm, debatable. Things like the garbage collection inside tuples can change the space behaviour and implementability of some things, and are supported by GHC but not Hugs.

...

As nobody has provided any sensible justification for the assertion that using lots of stack (vs. heap) inherently is bad

My claim is that "any program which needs to adjust the stack size has a laziness leak" - since I've made a universally quantified claim, a couple of real examples should blow it out of the water.

I think that's a reasonable rule of thumb -- Don

Neil Mitchell wrote:

My claim is that "any program which needs to adjust the stack size has a laziness leak" - since I've made a universally quantified claim, a couple of real examples should blow it out of the water.

But people often deliberately introduce lazyness leaks for improved efficency and in order to avoid space leaks. http://haskell.org/pipermail/glasgow-haskell-users/2007-May/012467.html Here there is essentially no difference between stackGobbler and heapGobbler (they both use a stack), but in order to avoid a "stack overflow" heapGobbler is tail recursive and explicitly implements the stack as a reversed list accumulator, which then has to be reversed at the end, so will burn twice as much heap to get a result as stackGobbler (at least if we already know the list has evaluated at least up to the point where it's tail get chopped off). Regards -- Adrian Hey

Simon Peyton-Jones wrote:

| Yes, using lots of stack is clearly bad with ghc, but this is a ghc | "bug". In fact the only reason these programs do use lots of stack | (vs. heap) is just a peculiarity of ghc rts implementation, so it | really should be ghc that fixes the problem, or at least admits | responsibility :-)

I don't think there's anything fundamental here. GHC allocates the stack in the heap, and it can grow as big as you like. The size limit is simply to catch infinite recursion with a more helpful message than "heap overflow". I think. There is one peculiarity though: I don't think we ever shrink the stack, so once it gets big it stays big. This could be fixed, though.

Yikes! Sorry, but if what you say is true then things are even worse than I thought :-( This behaviour seems really bad to me, especially for concurrent programs. Also, I can't help thinking that the common justification for the current limit (that it helps find alleged bugs) is a little lame. It only helps find bugs if one expects ones program to use less than 8M of stack (hence if it's using more, it's a bug by ones *own* definition). But if a program or library is deliberately designed to make use of stack (in preference to heap) for efficiency reasons (or even just to avoid the awkwardness of using explict CPS style), then this is a source of bugs in otherwise perfectly correct and reasonable programs. If we want some way of investigating a programs stack use there must be a better way of doing it than deliberately inducing a crash in any program that exceeds 8M of stack. Thanks for the answer though. I think I'll write a ticket about this :-) Regards -- Adrian Hey

| Sorry, but if what you say is true then things are even worse than I | thought :-( This behaviour seems really bad to me, especially for | concurrent programs. Which behaviour precisely? Can you say what is wrong and what behaviour you expect? S

Hi

First bad thing: Stack size (memory consumed) doubles each time it overflows.

Bad thing? Assume that allocating memory takes some constant amount of time, such as invoking overflow behaviour etc. To get the size of the stack to n bytes with doubling takes O(log n), to get it there with a constant increase takes O(n). If you store the stack in a linear block, then allocation costs O(n) and you can even risk O(n^2) behaviour unless you double each time. I think its fairly well understood that things like hash tables should double in size when they overflow, rather than increasing by some small increment. Also remember that this behaviour never wastes more than 50% of the stack, which is a relatively small amount.

Third bad thing (the really bad thing): If a stack has temporarily grown (to 64M say), it will never shrink back down again to something more typical (< 4K say). If I understand correctly, it will continue to take 64M from the heap regardless.

That would be nice. But its only beneficial if there are programs which takes large amounts of stack at some point, but then shrink down to very little stack and continue for a reasonable amount of time. Console programs probably don't fit this pattern (since they tend to be batch style and exit quickly). GUI programs probably do, so perhaps stack reduction will be more important as the GUI toolkits mature and Haskell starts getting used for UI type things. That said, unless there is a real user with a real problem (rather than a theoretical concern), priority may go to other bugs. Thanks Neil

Hello Matthew, Monday, February 4, 2008, 11:45:51 PM, you wrote:

...

That would be nice. But its only beneficial if there are programs which takes large amounts of stack at some point, but then shrink down to very little stack and continue for a reasonable amount of time.

From the 'when I was a lad' department...

Thinking back to when Java transitioned to a garbage collector that could give memory back to the OS, we got some unexpected benefits. Consider a machine

i would be also happy if ghc will return unused *heap* memory back to OS - it's immediately required for my GUI program where users may open huge files and then close them. but i personally don't have the same need for *stack* -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

Hello Adrian, Tuesday, February 5, 2008, 10:15:59 PM, you wrote:

...

i would be also happy if ghc will return unused *heap* memory back to OS - it's immediately required for my GUI program where users may open huge files and then close them. but i personally don't have the same need for *stack*

How do you know you don't or won't have the same need for stack?

i run my program with rather large datasets - it's happy with current 8m stack. i had problems with filterM function, though, and replaced it with my own, tail-recursive but probably less efficient implementation i know that real problems for my programs will be solved by adding "heap releasing" or, say, x64 support. are you have real problems with stack management? if not, isn't it better to allow ghc developers to solve real problems for me and other people? things will never be ideal from my own POV the only serious argument may be that current situation limits usability of some programming techniques (CPS?) which is able to increase programmer's productivity -- Best regards, Bulat mailto:Bulat.Ziganshin@gmail.com

On Mon, Feb 04, 2008 at 10:13:12PM +0000, Adrian Hey wrote:

...

Also remember that this behaviour never wastes more than 50% of the stack, which is a relatively small amount.

Only if the stack is relatively small. Would you say the same about heap, or about a stack that only needed 50% of heap space but ended up using all of it? Or money? Using twice as much as you need of anything is bad IMO.

Apparently you don't realize that GHC normally uses twice as much heap as is needed, due to the decision to use a two-space copying collector by default for the oldest generation. :) Stefan

Stefan O'Rear wrote:

On Mon, Feb 04, 2008 at 10:13:12PM +0000, Adrian Hey wrote:

...

...

Also remember that this behaviour never wastes more than 50% of the stack, which is a relatively small amount. Only if the stack is relatively small. Would you say the same about heap, or about a stack that only needed 50% of heap space but ended up using all of it? Or money? Using twice as much as you need of anything is bad IMO.

Apparently you don't realize that GHC normally uses twice as much heap as is needed, due to the decision to use a two-space copying collector by default for the oldest generation. :)

Three times in fact, on average. If the old generation contained L live data at the last collection, it is allowed to grow to 2L before being collected again. If it still has L live data at the next collection, L is copied, giving you a total requirement of 3L for a major collection. Compacting GC reduces this to 2L, because the live data is not copied. The factor of 2 is tunable using +RTS -F. Cheers, Simon

Simon Peyton-Jones wrote:

| First bad thing: | Stack size (memory consumed) doubles each time it overflows. | | Second bad thing: | Arbitrary limit on stack size unrelated to overall (heap) memory | available. | | Third bad thing (the really bad thing): | If a stack has temporarily grown (to 64M say), it will never shrink | back down again to something more typical (< 4K say). If I understand | correctly, it will continue to take 64M from the heap regardless. | | What I would like is to be able to set an upper limit on total memory | useage and allow the program to freely use this memory as either stack | or heap. At least that should be the default behaviour, but maybe | also allow +RTS restrictions for "debugging" (though I don't think this | is a very good way of investigating a programs stack use). | | I would also like stack memory allocation to increase (and decrease :-) | in some sane sized linear increment, not double each time. With the | current scheme, as I understand it, if 65M is needed then 128M will be | allocated.

Would you like to create a ticket for this?

OK

I don't know how many people it bites, and how often,

The problem is that the fact that it *might* bite often affects your whole coding style (well mine actually :-) for some problems. It also seems to have given rise to the POV that ghc's current behaviour is good because stack use is bad. MHO is that it's only ghc's current behaviour that *makes* stack use bad. I think it bites a lot less often than it otherwise would because most people will deliberately chose to use heap in preference to stack (at least when writing "eager" code) just to avoid the problem. But it still bites pretty often anyway with "lazy" code for unexpected reasons. Arguably such situations are indeed a "bug" more often than not, but I still think terminating the program unnecessarily (at 8M stack) is bad default policy.

Yes, this is the standard solution, and it's a good one because it has a robust cost model (no quadratic costs). However, it's tricky to get right; copying is simpler. If a significant fraction of runtime (for some interesting program(s)) turned out to be consumed by copying stacks then we could consider this.

Do you really need such evidence? If we agree that allowing stack to grow to arbitrary (limited only by memory availability) size is reasonable then surely we already know that there will be some stack size for which quadratic copying cost is going to get "stupid" :-) Of course there other possible more radical solutions that come to mind, like not using a (C style) "stack" at all. But I guess we'd be talking about a complete re-write of the pretty much all the rts and much of the compiler to do this :-( Regards -- Adrian Hey

On Feb 5, 2008 2:50 AM, Adrian Hey wrote:

I think it bites a lot less often than it otherwise would because most people will deliberately chose to use heap in preference to stack (at least when writing "eager" code) just to avoid the problem. But it still bites pretty often anyway with "lazy" code for unexpected reasons. Arguably such situations are indeed a "bug" more often than not, but I still think terminating the program unnecessarily (at 8M stack) is bad default policy.

Please, after all this, do give an example. Luke

On Feb 5, 2008 6:50 PM, Adrian Hey wrote:

Luke Palmer wrote:

...

On Feb 5, 2008 2:50 AM, Adrian Hey wrote:

...

I think it bites a lot less often than it otherwise would because most people will deliberately chose to use heap in preference to stack (at least when writing "eager" code) just to avoid the problem. But it still bites pretty often anyway with "lazy" code for unexpected reasons. Arguably such situations are indeed a "bug" more often than not, but I still think terminating the program unnecessarily (at 8M stack) is bad default policy.

Please, after all this, do give an example.

If you mean an example of coding style and choice of stack vs. heap, I already have..

http://www.haskell.org/pipermail/haskell-cafe/2008-January/038832.html

Ah, sorry, I must have missed that message. Luke

Neil Mitchell wrote:

Hi

...

If you mean an example of coding style and choice of stack vs. heap, I already have..

http://www.haskell.org/pipermail/haskell-cafe/2008-January/038832.html

I'm at a loss as why you want a strict version of take. It's clearly not for performance, as it performs slower. I'd say both the gobbler programs have a bug, namely that they are not sufficiently lazy.

I have already partially scanned the list looking for the first element that satisfies some condition, using a tail recursive search. If such an element is found I want to split the list at that point. If such an element is not found the entire list has been scanned without using any "extra" stack or heap (other than that used by the list itself and the condition test). I could build the reversed list accumulator on the heap as I did the search, but I don't because this will be completely wasted effort in the case where such an element is not found. So instead I just use an unboxed Int to count how far I get and have the search return this and the unsearched suffix (in the case where a matching element is found). But the lifetimes of the list prefix and suffix from this point on are completely unrelated so I don't want the prefix thunk to be hanging on to the unknown sized suffix. As I already know that the list has been evaluated at least up to the point that it gets "chopped off", I choose to use a strict (eager) take.

As an aside, my version of this function would be:

neilGobbler :: Int -> [x] -> [x] neilGobbler n xs = length res `seq` res where res = take n xs

I have no idea if it takes the heap or the stack, or if it performs faster or slower. If you still have whatever test you used on the gobbler, perhaps you could tell us.

My guess is it will use O(1) stack and burn O(n) heap (in addition that actually used by the result), so assymptotic complexity wise same as heapGobbler, but probably higher constant factors with ghc due to lazy building of take thunks and subsequent reduction and indirection costs.

...

If you mean an example of it biting with lazy code, this is discussed so often you'd be spoiled for choice if you search the mailing list archives. Here's a good one..

http://www.haskell.org/pipermail/haskell-cafe/2005-December/013521.html

This example actually shows the problem twice. In one case it's solvable by using foldl' instead of foldl.

Which reduces the memory from O(n) to O(1).

Are you sure about that? Using foldl' here eliminates one of the two possible sources of stack overflow, but it doesn't eliminate a space leak. It's O(n) either way. Using strict Map insertion will eliminate a space leak (in this case) and also a possible source stack overflow.

Surely thats a good thing,

Would be if it was true :-)

and the code before had a space leak. Space leak is bad, therefore telling people about it is good.

There are plenty of space leaks that won't cause stack overflows, and plenty of stack overflows that aren't caused by space leaks (see above for one example). Again I have to say that even if true, I think this is a pretty lame justification for the current implementation. The *default* behaviour of any useful program should surely be to make best effort to carry on working (and in due course deliver an answer or whatever), even if there is unexpectedly high stack use for some reason (that may or may not be a "bug").

I think its sensible to let people set their own stack bound (which is possible),

I have no objection to people bounding their stack if that's their choice. I can't imagine why anybody who stopped to think about this would actually want this feature, but it's free world. What I object to is it being bounded by default to something other than overall program memory limit. I know that I could probably achieve this effect myself with +RTS options, but I also want to be able to write libraries that other people are going to use safely without having to add a appropriate warning in the documentation to the effect that some parts use O(n) stack space deliberately, by design. But of course this all assumes that underlying implementation is sufficiently robust to make "unbounded" stacks safe (at least as safe as any other "unbounded" data structure). Unfortunately it seems this isn't the case at present if what various folk have told me is true.

but that clearly just from taking an informal poll of respondants to this thread, the current default should indeed be the default. You seem to be the only person clamouring for an unlimited stack,

Yes, this is strange. Same thing happened in the "global variables" debate despite it being obvious to any thinking person that I was correct. Denial of the reality of some very simple examples of the problem was typical of that debate too. :-) Regards -- Adrian Hey

Neil Mitchell wrote:

Hi

...

I have already partially scanned the list looking for the first element that satisfies some condition, using a tail recursive search.

If such an element is found I want to split the list at that point.

span/break? I really can't believe the memory overhead of span is that terrible, you are only duplicating the (:)'s and its only one traversal.

...

...

As an aside, my version of this function would be:

neilGobbler :: Int -> [x] -> [x] neilGobbler n xs = length res `seq` res where res = take n xs

My guess is it will use O(1) stack and burn O(n) heap (in addition that actually used by the result), so assymptotic complexity wise same as heapGobbler, but probably higher constant factors with ghc due to lazy building of take thunks and subsequent reduction and indirection costs.

Sure? Guessing constant factors related to strictness and laziness is incredibly hard! My guess based on "gut feeling" is that the program will take less time, and use half the memory. But given my initial comment, that guess is not very reliable.

But the point is that *both* heapGobbler and neilGobbler are likely to be slower and chew through at least twice as much heap as stackGobbler, which would be the implementation of choice for both simplicity and performance if it wasn't for this stack management problem. Regards -- Adrian Hey

Neil Mitchell wrote:

Hi

...

But the point is that *both* heapGobbler and neilGobbler are likely to be slower and chew through at least twice as much heap as stackGobbler, which would be the implementation of choice for both simplicity and performance if it wasn't for this stack management problem.

Sure?

Yes, though testing stackGobbler with a large enough data set could be problematic for the very reason we've been discsussing. But let's say your hypothesis was correct. If so then presumably *all* Haskell programs could give better performance than they currently do if we nuked the stack completely and have ghc generate CPS style code. This too would be fine with me. The problem with the current situation is that we have perfectly sound and correct programs that "crash" quite unnecessarily (and even if they don't get quite that far, can still cause considerable per thread memory wastage if what SPJ says is true). Why their authors choose to use a "stack greedy" implementation and whether that was by design or a mistake really *isn't* the point. As I said before (this is the third time I think), the fact that these programs use a lot of "stack" at all is just a peculiarity of *ghc* implementation, so it really is a ghc responsibility to do a decent job of stack management IMO. It's not a programmer responsibility to code in such a way that minimal "stack" is used (with ghc).

That sounds like the thing that people can conjecture, but benchmarks can prove. And I'd claim that neilGobbler is the simplest function by a large margin.

AFAICT neilGobbler isn't even entirely safe as an implementation of an eager take. There's nothing the Haskell standard to stop it being transformed into.. neilGobbler :: Int -> [x] -> [x] neilGobbler n xs = length (take n xs) `seq` take n xs Regards -- Adrian Hey

Hi

Yes, though testing stackGobbler with a large enough data set could be problematic for the very reason we've been discsussing.

Yes you are sure, or yes you tested and the results show than neilGobbler is x% slower and consume y% more memory on specific test n?

But let's say your hypothesis was correct.

My hypothesis isn't that the stack is slow.

AFAICT neilGobbler isn't even entirely safe as an implementation of an eager take. There's nothing the Haskell standard to stop it being transformed into..

neilGobbler :: Int -> [x] -> [x] neilGobbler n xs = length (take n xs) `seq` take n xs

Yes, but so much in the Haskell standard is also missing. I think in this case you could reasonably argue that any compiler violating this _is_ violating the Haskell standard as it was intended (albeit not as it was written). You'll also find that the space behaviour of CAF's isn't documented in Haskell, but if people changed it you'd break quite a bit of the nofib suite. Thanks Neil

Simon Marlow wrote:

The point is, GHC has no such thing as the "overall program memory limit" unless by that you mean the total amount of memory + swap in your machine. You can set a limit with +RTS -M, but there isn't one by default. So what happens when you write a program with a space leak is that it gobbles up all the memory, and turns on the hard disk light for a few minutes until the OS gives up and kills it. Or at least, you hope it kills your program and not something else important you were doing at the time.

Well if having "unbounded" (by default) memory use in the form of heap is OK with most users then I can't see why the same should not be OK for stack. An errant program is just as likely to explode the heap as it is the stack AFAICS.

We used to have a default heap limit, for the reason above, but I was persuaded to remove it because it was too much of a pain to keep having to say +RTS -M<whatever> when your program ran out of memory. So we could do the same with the stack limit - the only concern is whether it will be highly inconvenient when we accidentally write programs with infinite loops, which in my experience seem to occur more than space-leaky programs.

To be honest, in all my years of Haskelling I can't think of a single occasion where I've had a program get stuck in an infinite loop. I've had plenty of stack overflows, and they're reported on the mailing lists pretty regularly, but on all such occasions it's been caused by deep but very definitely finite recursion.

We could also set the limit a lot higher than it currently is. Or, we could try to figure out how much memory is in the machine and set it based on that. Basically, I don't care that much, unless it means I have to do a lot of work to implement it :)

I don't think just keeping the implementation as it is and just changing (or removing) the limit is really an option. Unfortunately, as things are at present, using a lot of stack with a program compiled by ghc really is a "bug" and the limit does provide users with some protection against this. But IMO the bug is in the ghc rts, not the users source code most of the time :-( I think at the minimum, the stack shrinking mod you suggested should be implemented before the limit is removed. Regards -- Adrian Hey

Hi

But if a program or library is deliberately designed to make use of stack (in preference to heap) for efficiency reasons then this is a source of bugs in otherwise perfectly correct and reasonable programs.

Can you give an example of a particular library or program, so everyone can be a bit more concrete about what you think should be allowed, but that isn't? Thanks Neil

On Tue, 2008-01-29 at 08:18 +0000, Adrian Hey wrote:

Derek Elkins wrote:

...

While perhaps for a simple throw-away program it may be beneficial to write code that allocates unnecessary stack, I personally consider unnecessary stack use a bug. A stack overflow, to me, is always indicative of a bug.

The "bug" is in ghc stack management. Why is it so important that the stack size is arbitrarily limited? It's just an intermediate data structure, no different from any other intermediate data structure you may build on the heap (well apart from it's efficiency). But I guess we would be in danger of having our programs run too fast if folk were silly enough to make use of the stack.

I said -unnecessary- stack use. It makes no difference if the stack size is only "limited" by how much core+swap space you have. If you have no restrictions on stack use and you get a stack overflow, I still consider it a bug. It's the unnecessary use of the stack, not the overflow that is the bug; as I said, the stack overflow is -indicative- of a bug. However, a question comes up: why is unnecessary "stack" use bad but unnecessary heap use acceptable? The answer is, for me, it isn't, but heap and stack are different: length shouldn't take O(n) space period; whether it's stack space or heap space. I consider an "Out of Memory" error to be indicative of a bug too unless you are operating over large data sets or knowingly using a particularly memory-hungry algorithm. A program that has live sets in the gigabyte range on "small" inputs are buggy to me. Space leaks are bugs whether it's stack space or heap space. But. But, there is a difference (theoretically) on what goes on the heap and what goes on the stack. The stack is the -control- stack. It, in theory, holds (only) "control" information (which may include parameters which are waiting for other parameters to be evaluated, and other such things). Usually stack overflows are caused by "linear" stack use. Usually you need pathological control flow to need "linear" stack use, so either you were unlucky and your data was pathological or you are setting things up so that the actual case is the pathological one. [As you might guess, I consider the pathological (left associative) use of (++) to be a bug as well, albeit more of a "time leak" than a space leak.] Practically speaking, stack overflows almost always indicate a (stack) space leak or an unintended infinite loop.

So perhaps the current ghc defaults are too generous. What limit do you think should be placed on the stack size that a non buggy program can use?

Hopefully, you can see why what, if any, limit is set is irrelevant to my point. All other things being equal, memory being the limit is ideal. Usually, all other things aren't equal. [From a different email]

As nobody has provided any sensible justification for the assertion that using lots of stack (vs. heap) inherently is bad (and that programs which do have bugs, by definition), it seems to me this is one of those quasi-religious beliefs, like (so called) "global variables" or the cyclic module dependencies being a bug (by definition).

Unnecessarily using lots of stack -or- heap is inherently bad, though, it may perhaps be the lesser of two evils.

On Mon, 28 Jan 2008, Jonathan Cast wrote:

Or, to put it another way, the bugs Java's stack overflow is designed to catch are considered good style in Haskell.

I consider explicit recursion in Haskell as bad style. One should use higher order functions like 'map', 'fold', 'filter' and so on whereever possible. Even if one needs explicit recursion one should separate the traversal through a data structure from the particular operation applied to the elements.