6 ms·

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 complexit

by 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
  Tail call elimination works fine in OCaml, same as in Erlang.
- c-cube 6y ago
  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.
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!

by c-cube 6y ago

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
Tail call elimination works fine in OCaml, same as in Erlang.
c-cube 6y ago
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.

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!