Hacker News Reader

Memory and Haskell's function calls being allocated on the heap doesn't seem at first glance to be tied to laziness. You could have a strict language with a growable stack that effectively puts function calls on the heap (I mean it's usually not actually the heap per se, but the shrinking and growing of the stack makes it similar from a performance perspective). That's usually not done for ABI compatibility reasons rather than any intrinsic reason.

And moreover I think the majority of programmers can immediately spot when something could lead to a stack overflow. I can't recall the last time I had an issue with a stack overflow that wasn't an infinite looping bug. It's not a difficult problem to begin with in strict languages. This is even more true when I think back to how many times I've written a recursive function by hand rather than use a higher order combinator in functional code. I think less than 1% of the code I write is even recursive to begin with.

Space leaks are a pretty annoying problem in Haskell programs though. There have been quite a few large, widely-used Haskell programs that have battled with them. Heck Shellcheck's author dropped multithreading because he couldn't figure out the issue with space leaks. I can't think of any large program that has ever been forced to a drop a feature because they couldn't solve a stack overflow from overly deep recursion (it is a purely mechanical transformation to take any recursive function's call stack and pass it in instead as an explicit stack on the heap).

And being able to locally reason about performance rather (i.e. only needing to take into account the implementation of a function) than having to take into account nonlocal reasoning (how your function will be called) is a huge win on par with the analogous gain of local vs nonlocal reasoning for correctness in functional programs.

I agree it's a matter of experience and changing your way of thinking, but personally I'm way more confident about what the performance profile of a program I've written in Purescript will look like before extensive testing than what the performance profile of an equivalent Haskell program will look like before extensive testing.

> You could have a strict language with a growable stack

This doesn't fix the more general problem of something that is generated by a (co-)recursive function and consumed gradually.

Non-strictness lets you "pause" the recursion until you need it. You can have a data structure that's bigger than memory (even infinite) and it's not a problem as long as you don't need all of it at once.

Sure, but you can fix that with any number of streaming libraries in strict languages those times when you do actually need that.

And importantly, in line with local reasoning, in a strict language, it will be very apparent when you need it. It won't take you by surprise.

On the other hand, Haskell's default list and its associated functions are just enough to let you get by but have enough pitfalls that can you take you off-guard that in the end, for more complex operations, you just end up using a streaming library anyways (e.g. conduit, pipes, streamly, etc.).

> you can fix that with any number of streaming libraries in strict languages

This is moving the goalposts a bit. Certainly you can do streaming in a strict language if you're willing to use libraries, but we're talking about language primitives.

> you just end up using a streaming library anyways

You generally only do this if you're interleaving effects with your streaming. I use guarded corecursion all the time, e.g. when I write an expression like

    index = zip [1..]

Any strict language that supports something like `[1..]` has a lot more crap to deal with, and usually has to implement something like overloading list expressions to create iterators, which have their own problems.

> This is moving the goalposts a bit.

I don't think so. My original comment was focusing on stack overflow errors, but my wider thesis is this:

By and large, strict languages trade off some level of syntactic convenience for easier, local reasoning about performance. And I am willing to accept that hit. So for example, yeah sure maybe you have to do a mechanical transformation of a recursive function to either use a trampoline or an explicit stack or rewrite with an iterative loop, but that's an acceptable trade-off for me.

Stated another way:

The cases where a lazy language can cause weird performance issues are harder to debug than the cases where a strict language can cause weird performance issues.

Indeed the fact that a library is all that is needed to patch up a lack of language primitives makes me more willing to accept the trade off of syntactic convenience.

  index = zip [1..]

vs

  index = Stream.zip (Stream.from 1)

or even conversions to and from lists if you really don't want streams elsewhere such as

  index xs = Stream.toList . Stream.zip startIndex $ streamedXs
    where
      startIndex = Stream.from 1
      streamedXs = Stream.fromList xs

is a sufficiently small price for me to pay to gain back local performance reasoning (I mean in this case I'd just write index with a fold to begin with in a strict language).

> interleaving effects with your streaming

But the issue that effects are supposed to be values in and of themselves (i.e. if I really take effects as a value seriously, why must my machinery change when I have a list of IO actions vs a list of integers?). This is really a symptom of the deeper issue is that there are a lot of things that should be strict for other reasons that can interfere with purely lazy lists or other structures because they basically represent this sort of weird interleaving of strict and lazy needs (this is why e.g. foldl' fails without strict data fields).

This is a solved problem, see the Racket programming language. I think this may apply to most Scheme implementations actually.

Can you explain how racket solves this?

It's answered here:

https://stackoverflow.com/q/49912204/23567

The answers there seem to suggest racket just allows large amounts of space to be allocated to the stack. This doesn't "solve" the problem at all. It's just a tweak to kick the can down the road a bit.

Non-strict languages fundamentally change the way one can think about function context; unlimited guarded corecursion via thunks is a canonical example.

> I can't think of any large program that has ever been forced to a drop a feature

I have to anecdotes of having to drop features in a large python program due to memory leaks.

The first one was when someone introduced an endpoint that consumed data from a gRPC service. After weeks of effort trying to find where the source of the leak was, we decided to drop the change as we could not find the cause in a reasonable time.

The second case was when introducing jaeger for distributed tracing. Similarly to the previous story, it was cheaper for us to drop the feature and use something else than to figure out where the memory leak was.

I believe that it is a matter of balancing effort vs, benefit. I would not be surprised if someone working on their free time on an open source project decides to drop a feature because they cannot find the time to make it work properly.

I can totally believe that and have fought similar bugs (basically unexpected references that keep memory around way longer than necessary), but memory leaks of that form affect both strict and lazy languages, i.e. it's an independent problem.

Lazy languages can have that same problem in addition to space leaks.

This is making me reconsider a bit my stance on laziness. I'm usually in favor of eager, call by value, cause it's simpler to reason about in terms of complexity; but in OCaml I often have to be careful about deep recursions and it's annoying.

Is tail call elimination particularly problematic?

With Erlang, recursion is effectively the only looping construct, so it becomes second nature to make everything end with a tail call.

Tail call elimination doesn't let you do guarded (co-)recursion. For example, in a strict language you can't have a corecursively defined list like

   loop a b = a : loop b (a + b)
   fibs = loop 0 1

Because tail call elimination can't do anything about the first case.

This example actually does not have a tail-recursive call, so if you mean that a non-tail recursive call is not stack safe in a strict language, that is correct, yes.

I think wyager's point is that you can extract individual Fibonacci numbers from fibs rather than realizing the infinite list immediately.

Right - my point is that tail call elimination doesn’t help you with guarded corecursion, which lazy languages handle just fine. Guarded corecursion represents a huge set of programs it’s useful to be able to evaluate.

Both function calls are in tail position. This is what actually matters (along with the ABI return type matching for runtimes where that matters).

'loop' is not in a tail position. The last operation is the list cons. It can be optimized with TCO modulo cons but that would just make it hang/exhaust heap rather than stack overflow in a strict language.

Tail call elimination works fine in OCaml, same as in Erlang.

Not all recursion is tail recursion. If you traverse trees you either deal with your bounded stack somehow (or ignore the problem) ; derecursify by hand, which is a nightmare ; or refactor to continuation passing style. There are options but none is simple and elegant.

I've come around to preferring laziness by default. The gotchas are few and far between compared to strictness, and quite easy to avoid if you just use -XStrictData to flip the default and explicitly annotate laziness on your data types with ~

The status quo of strictness and lack of general TCO has a real cost. Every abstraction taxes your application!

But general TCO is precisely less important in lazy languages. In fact stack overflows in Haskell often arise when you move a function call to the tail position when it's not supposed to be there. EDIT: perhaps I misunderstood your original comment. You maybe mean that if a language is strict it should have TCO?

Laziness has its own performance tax. It's only performant in Haskell because GHC goes to great lengths to perform various strictness analyses and libraries try to provide fusion. In fact when those optimizations fail to fire (which is the bane of any large Haskell program), Haskell will far under-perform compared to other strict languages in the ML family.

> stack overflows in Haskell often arise when

Do you have some examples for this happening?

I have seen extremely few stack overflows in Haskell since I convinced GHC to default to infinite stack size 7 years ago [1].

[1]: https://gitlab.haskell.org/ghc/ghc/-/issues/8189

Oh you're right!

I was curious and just ran the standard bad `foldl` example and I got a stack overflow in GHCi (8.8.4) but compiling without optimizations in GHC (to avoid strictness analysis) just led to the program taking over all of my system memory.

I do use `runhaskell` quite a bit for my personal utility programs, so I wonder if that's what gave me the impression of those stack overflows (`runhaskell` naturally also gave me a stack overflow).

Of course the wider point is that tail calls in Haskell can often end up not taking constant space and in fact moving the function out of the tail position can go back to constant space, but thanks nonetheless for the correction!

Racket is not lazy (at least by default) and will not stack overflow, it will just run out of memory. The only thing that tail recursion changes is how much memory an operation will take. Folds are also trivial to reason about in Racket whereas Haskell is much more tricky due to laziness.

> The only thing that tail recursion changes is how much memory an operation will take.

Tail recursion specifically changes whether a compiler can optimize away the stack, which means your out of memory will come from lack of memory for a stack. Whether the stack is allowed to use all memory is a decision beyond your control in a language that runs in a browser.

You can do this in the browser as well to a degree. Just use CPS plus a trampoline function (which is also a way to implement general continuations). Using promises also works since it is a restricted form of CPS.