6 ms·

> While not directly related to strictness, a pain point on the PureScript side that I didn’t experience in Haskell was stack safety. Stack safety is directly

> While not directly related to strictness, a pain point on the PureScript side that I didn’t experience in Haskell was stack safety. Stack safety is directly related to laziness—Haskell being lazy[1] by default is what lets functions that would cause stack overflows in other languages work in Haskell. If you're incrementally producing or consuming a lazy data structure, memory can be allocated on the heap and garbage collected as you're traversing the data structure without needing to use the stack[2]. Haskell makes recursing over or producing lazy data structures the path of least resistance, so you end up almost never worrying about stack overflows—they only pop up in code written with strict types like numbers. Of course you end up with other issues that are unique to lazy languages—like space leaks—but you really do get some pervasive advantages from having lazy code by default. Some people make it seem like laziness has lots of downsides with only niche upsides, but that hasn't matched my experience at all: I've found laziness makes day-to-day programming better in a few ways (like not thinking about tail calls and stack overflows) that are the opposite of niche—so pervasive it's easy to take them for granted. [1]: Technically Haskell is "non-strict" rather than "lazy", but I've found that distinction obscures the core issues in discussions like this. Just throwing in this footnote as a fig leaf to accurate terminology :). [2]: I feel this explanation is oversimplifying or not quite getting details right, but can't think of a better way to explain it at the moment.

c-cube 6y ago
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.
- macintux 6y ago
  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.
  - wyager 6y ago
    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.
    - yawaramin 6y ago
      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.
      - dwohnitmok 6y ago
        I think wyager's point is that you can extract individual Fibonacci numbers from fibs rather than realizing the infinite list immediately.
      - wyager 6y ago
        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.
    - slaymaker1907 6y ago
      Both function calls are in tail position. This is what actually matters (along with the ABI return type matching for runtimes where that matters).
      - dwohnitmok 6y ago
        '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.
  - yawaramin 6y ago
- whateveracct 6y ago
  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!
  - dwohnitmok 6y ago
    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.
    - nh2 6y ago
      > 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 https://gitlab.haskell.org/ghc/ghc/-/issues/8189
      - dwohnitmok 6y ago
        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!
dwohnitmok 6y ago
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.
- wyager 6y ago
  > 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.
slaymaker1907 6y ago
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.
- foolmeonce 6y ago
  > 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.
  - slaymaker1907 6y ago
    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.

c-cube 6y ago

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.

macintux 6y ago
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.
- wyager 6y ago
  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.
  - yawaramin 6y ago
    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.
    - dwohnitmok 6y ago
      I think wyager's point is that you can extract individual Fibonacci numbers from fibs rather than realizing the infinite list immediately.
    - wyager 6y ago
      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.
  - slaymaker1907 6y ago
    Both function calls are in tail position. This is what actually matters (along with the ABI return type matching for runtimes where that matters).
    - dwohnitmok 6y ago
      '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.
- yawaramin 6y ago
whateveracct 6y ago
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!
- dwohnitmok 6y ago
  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.
  - nh2 6y ago
    > 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 https://gitlab.haskell.org/ghc/ghc/-/issues/8189
    - dwohnitmok 6y ago
      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!

dwohnitmok 6y ago

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.

wyager 6y ago
> 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.

slaymaker1907 6y ago

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.

foolmeonce 6y ago
> 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.
- slaymaker1907 6y ago
  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.