7 ms·

An apologia of lazy evaluation

54 points by runeks 4y ago

sfvisser 4y ago
My biggest observation from switching from Haskell to Rust is the change in thinking in terms of program composition. In Rust you need to really make some careful design choices in your producer/library code depending on the expected use. All of them quite on the operational level and not really semantically. So many internal choices about refs/arcs/pins/mut/ownership leak out. In Haskell you don’t really do that. If your library internals are neatly written combinators with the right type and semantics you can just expose them and you’re done. Like the article explains, laziness is a big part of this. I understand where that difference comes from, but it’s really a very different way of thinking.
- asplake 4y ago
  How much of that do you think is due to laziness specifically and not GC?
  - sfvisser 4y ago
    Yes, the GC helps tremendously here of course. I guess laziness helps mostly by not dictating the granularity in which to expose both data and building blocks. You can expose more than strictly needed and consumers just pick what’s relevant. Keeping APIs simple and to the point.
- wirrbel 4y ago
  I really wished there was a GC-ed but strictly-evaluating Haskell. A Rust-like syntax would probably help with adoption but I don't have a strong preference in that.
  - discarded1023 4y ago
    Try Standard ML or ocaml. You may be surprised how far the module system can take you, and how limited type classes really are for expressing abstractions. On a different vector, you can see the same story -- type classes are convenient but too limited -- in the development of abstract algebra/topology/analysis/... in Isabelle/HOL. As for laziness, things don't work out too well for a variety of reasons. Bob Harper laid out several many years ago. See e.g. https://news.ycombinator.com/from?site=existentialtype.wordpress.com&next=2481042 https://news.ycombinator.com/from?site=existentialtype.wordp...
    - wirrbel 4y ago
      I really like standard ML. Modules are great but type classes would be … more pragmatic?
      - bmitc 4y ago
        My preference are ML dialects, but it sounds like Idris is something you should check out. It's strict by default and has type classes and dependent types.
        wirrbel 4y ago
        Idris was always filed in my head as some estoric/academic/obscure thing, will have a look at it.
        bmitc 4y ago
        I actually think it's probably less academic than Haskell or Racket. It's intended to be a practical language that people build things with. It just has an advanced type system and a small community.
      - erk__ 4y ago
        There is even a SML that does not use a GC* but instead does "region based" memory mangement. https://elsman.com/mlkit/about https://elsman.com/mlkit/about *most of the time.
  - one-punch 4y ago
    > I really wished there was a GC-ed but strictly-evaluating Haskell. To answer this question literally, there are PureScript (transpile to JavaScript), Idris (dependently typed), OCaml, and Standard ML (as discarded1023 pointed out). But I think the wish for a strictly-evaluating Haskell is sometimes in fact a wish for a Haskell with more predictable performance (especially in memory usage). If so, the Linear Type/Arrow of recent GHC may fit the bill [1]. My wish is for Haskell to have a better runtime [2] with optimal reductions (with more predictable performance and without GC) [3], which could have Rust-like performance without lifetimes, while being lazy. [1]: https://www.tweag.io/blog/2017-03-13-linear-types/ https://www.tweag.io/blog/2017-03-13-linear-types/ [2]: https://discourse.haskell.org/t/high-order-virtual-machine-hvm-an-optional-ghc-like-runtime-for-rust-with-many-comparisons-to-ghc/4118 https://discourse.haskell.org/t/high-order-virtual-machine-h... [3]: https://github.com/HigherOrderCO/HVM https://github.com/HigherOrderCO/HVM
    - noloblo 4y ago
      And faster Compile times haskell compile times relative to golang are super slow
      - one-punch 4y ago
        Golang prioritizes compile time (hence it took them so long to get Generics), which Rust and Haskell are unlikely to beat, as they both prioritize high-levels of abstractions (more compile time for zero cost abstractions at runtime). That said, since GHC is implemented in Haskell, the compile time will likely improve if linear type/arrow, or a better runtime (such as optimal reductions), is used by GHC itself.
        noloblo 4y ago
        what is linear type/arrow?
        one-punch 4y ago
        Linear Type/Arrow makes sure values are consumed exactly once (as they cannot be duplicated nor destroyed), and such runtime can be used for efficient resource management without reference counting or garbage collection [1]. For Linear Type/Arrow in Haskell, see [2][3][4]. For Linear Type (or Relevant Type) in Rust, see [5]. [1]: https://news.ycombinator.com/item?id=16100840 https://news.ycombinator.com/item?id=16100840 "Linear types can change the world" [2]: https://www.tweag.io/blog/2017-03-13-linear-types/ https://www.tweag.io/blog/2017-03-13-linear-types/ "Linear types make performance more predictable" [3]: https://www.tweag.io/blog/2023-01-26-linear-constraints-freeze/ https://www.tweag.io/blog/2023-01-26-linear-constraints-free... "Linear Constraints: the problem with O(1) freeze" [4]: https://www.reddit.com/r/haskell/comments/v3gouc/linear_text_builder_up_to_20x_faster_than/ https://www.reddit.com/r/haskell/comments/v3gouc/linear_text... "Linear Text Builder: up to 20x faster than alternatives" [5]: https://faultlore.com/blah/linear-rust/ https://faultlore.com/blah/linear-rust/ "The Pain Of Real Linear Types in Rust"
  - deleted 4y ago
    [deleted]
  - xmcqdpt2 4y ago
    Scala can be quite Haskell-like and is eager evaluating by default. (It's a lot less opinionated though so you can use it to write Java like code.)
    - wirrbel 4y ago
      I have worked professionally with Scala for two years and while I see its appeal of using it over plain Java, it always felt fairly alien to me and pretty complex (probably due to the Java interop and strong typing).
- bmitc 4y ago
  > Like the article explains, laziness is a big part of this. I don't think the article does a good job addressing this. They have a conclusion they want to get to, but I don't see how they get there with the arguments provided. Languages that are eager by default but support lazy evaluation are also not really discussed, and it's because they are the best of both worlds. Yes, lazy evaluation has its pluses, but more often than not, you don't need it. So it's better to have optional lazy evaluation and then reach for it when you really need it. F#, OCaml, Racket, Elixir, etc. work this way. And F# and Elixir, especially, heavily use compositional code with pipelines. The article states: > On a strict FP language, you end up writing more explicitly recursive functions (hopefully with tail calls) than using higher order functions that express your intent. That is not my experience at all, and I haven't seen anything that supports that. Lastly, Idris has a short FAQ as to why it's eager by default: https://docs.idris-lang.org/en/v1.3.4/faq/faq.html#why-does-idris-use-eager-evaluation-rather-than-lazy https://docs.idris-lang.org/en/v1.3.4/faq/faq.html#why-does-... And that addresses something else the article doesn't get at. Preciseness and explicitness make code much easier to reason about. Lazy evaluation increases mental burden.
  - sfvisser 4y ago
    > Lazy evaluation increases mental burden. In some situations, definitely! In other situations, definitely not! My experience with writing Haskell application code is that you’re thinking way less about the runtime operational aspect of your code than in any other language. The burden is much lower. The exceptions are possibly when writing low level library code that involves a lot of IO and steaming. Or when storing a lot of data in-memory for longer periods of time.
  - runeks 4y ago
    > Languages that are eager by default but support lazy evaluation are also not really discussed, and it's because they are the best of both worlds. Yes, lazy evaluation has its pluses, but more often than not, you don't need it. What makes you say strictness is the right default? I write Haskell at my day job, and I practically never experience crashes due to space leaks. And given that strictness has its own performance issues (unnecessary evaluation), it’s not clear to me that either is the “right” default.
- amelius 4y ago
  It would be great if the language allowed you to defer choices and program like in Haskell and then add constraints later and end up with the advantages of Rust. Or apply a series of correctness preserving transformations (perhaps GPT can help with that).
koito17 4y ago
> Lisp communities care more about syntactic extensibility than performance, etc. Huh? Are SBCL maintainers SIMDifying chunks of their CL implementation, improving static type checking and inference, improving numeric performance, and improving compiler optimizations as much as they can simply for "syntactic extensibility?" Even Clojure cares enough about performance and problems with laziness and copying to give us eductions and transducers, respectively, to work around the inherent performance issues in both. I have no idea what Lisp communities the reader must be referring to.
- lispm 4y ago
  There are some Lisp communities which value syntactic extensibility more than low-level performance. For example when using FEXPRs, which are functions which have access to their source and where the function decides which arguments to evaluate. You'll find that in R, Picolisp, Standard Lisp and a few others. Most other Lisp communities have settled on always strict evaluation and compilable macros as syntactic extensions.
  - antonvs 4y ago
    FEXPRs haven’t been relevant in mainstream Lisp since the 1980s. See Kent Pitman’s 1980 article describing the problems with them: https://www.nhplace.com/kent/Papers/Special-Forms.htmL https://www.nhplace.com/kent/Papers/Special-Forms.htmL The languages you mention probably use them mainly because they’re easy to implement in the language implementation, which has nothing to do with what the community values, except in a post-hoc sense when the community tries to justify to itself why it’s using such an inherently intractable feature.
    - lispm 4y ago
      Usually the arguments are a) it provides runtime access to the source (which for example is useful in R), b) runtime introspection is easier to understand (for the proponents) & less complex than macros and that macros are too static (they want more flexibility at runtime). For example authors of the REDUCE computer algebra system ( https://reduce-algebra.sourceforge.io/ https://reduce-algebra.sourceforge.io/ ) disliked Common Lisp for the lack of FEXPRs and that's why they stayed away from it. There were lots of discussions at the time when Common Lisp was introduced. > The languages you mention probably No, see above. Example: https://picolisp.com/wiki/?pros-and-cons https://picolisp.com/wiki/?pros-and-cons
ummonk 4y ago
The article seems to downplay the effect that space leaks can have on correctness / reliability. If 99.9% of code you write works, but every once in a while code nondeterministically encounters space leaks, that's a bad thing for the reliability of the language as a whole. You can no longer rely on any program you write being guaranteed to execute to completion.
- throwaway81523 4y ago
  I would say in an exaggerated version of the Haskell mindset, the most important thing is to prevent the program from giving wrong answers. The archetypal Haskell program is a compiler, and having it generate wrong code that gets deployed on a space mission is disastrous. Having the compiler crash with a memory leak is merely an annoyance. You would not write realtime code in idiomatic Haskell, if you would write such code in Haskell at all.
  - murdoze 4y ago
    Real-time code has high requirements for correctness and execution deadlines. Which means, w/o deterministic execution Haskell not suitable for a whole niche, where its safety properties are in a high demand. Which is a pity.
    - hexane360 4y ago
      Sure, but currently almost all of the most popular languages are also not suitable for that niche. If you exclude any garbage-collected language, you're basically left with Ada, C, C++, some of the "C/C++ successors" (Zig, D, Carbon, maybe Nim), and Rust.
    - throwaway81523 4y ago
      That's fine, those applications are why Ada was invented. Languages get pulled in too many directions when they try to be everything to everyone.
  - ummonk 4y ago
    "OOM exception" is a wrong answer. If your code terminates on a space mission because lazy evaluation runs out of memory, it's disastrous.
chriswarbo 4y ago
See also Why Functional Programming Matters, from 1984 https://www.cse.chalmers.se/~rjmh/Papers/whyfp.html https://www.cse.chalmers.se/~rjmh/Papers/whyfp.html > Recall that a complete functional program is just a function from its input to its output. If f and g are such programs, then (g . f) is a program which, when applied to its input, computes g (f input) > The program f computes its output which is used as the input to program g. This might be implemented conventionally by storing the output from f in a temporary file. The problem with this is that the temporary file might occupy so much memory that it is impractical to glue the programs together in this way. > Functional languages provide a solution to this problem. The two programs f and g are run together in strict synchronisation. F is only started once g tries to read some input, and only runs for long enough to deliver the output g is trying to read. Then f is suspended and g is run until it tries to read another input. As an added bonus, if g terminates without reading all of f’s output then f is aborted. F can even be a non-terminating program, producing an infinite amount of output, since it will be terminated forcibly as soon as g is finished. This allows termination conditions to be separated from loop bodies - a powerful modularisation. > Since this method of evaluation runs f as little as possible, it is called “lazy evaluation”. It makes it practical to modularise a program as a generator which constructs a large number of possible answers, and a selector which chooses the appropriate one. While some other systems allow programs to be run together in this manner, only functional languages use lazy evaluation uniformly for every function call, allowing any part of a program to be modularised in this way. Lazy evaluation is perhaps the most powerful tool for modularisation in the functional programmer’s repertoire.
quanticle 4y ago
That might seem the case from afar, but once you start writing Haskell and start experimenting these space leaks, you will notice that: 1. 90% of the space leaks you write end up adding a tiny amount of memory usage to your functions, mostly unnoticeable. Think thunks like (1 + 2) that are subjected to demand analysis under optimization. 2. 1-2% of them are serious enough to require profiling your code with cost-centres. But that's pretty much the same as in C. The vast majority of memory leaks in C aren't fatal to the program. They just lead to a little bit of extra memory usage, mostly unnoticeable. And then you have the small fraction of memory leaks that draw the attention of the OOM-killer. A tacit admission that detecting code that is leaking memory in Haskell is no easier than detecting code that is leaking memory in C does not speak well for Haskell. Memory leaks are a matter of correctness and reliability. Our computers are not ideal Turing machines. Their "tapes" are finite. Running out of memory causes the program to crash and produce incorrect results. Arguing that this only happens in a small fraction of cases, and can be handled with testing and profiling isn't persuasive, because one might say the same thing for a dynamically typed language, like Python.
- chriswarbo 4y ago
  "Space leaks" are not "memory leaks". A memory leak means a program will never free some region of memory; e.g. if it's pointer has been discarded without calling 'free'. That is certainly a matter of correctness. That is certainly a problem for finite-memory machines. In constrast, a "space leak" is just a suboptimal usage of memory. As a classic example, we want the sum of a list of integers to fully evaluate the running total at each step, like this: sum(0, [1,2,3]) sum(0+1, [2, 3]) sum(1, [2, 3]) sum(1+2, [3]) sum(3, [3]) sum(3+3, []) sum(6, []) 6 However, lazy evaluation may avoid performing the additions right away; instead building up unevaluated 'thunks' (nullary functions), which only get evaluated at the end, like this: sum(0, [1,2,3]) sum(0+1, [2, 3]) sum((0+1)+2, [3]) sum(((0+1)+2)+3, []) ((0+1)+2)+3 (1+2)+3 3+3 6 This is a perfectly correct calculation; and everything has been 'cleaned up' at the end (no worries about 'infinite tapes', etc.). However, if we're trying to e.g. process a massive data stream from disk, these unevaluated thunks may quickly exhaust our available memory.
mrkeen 4y ago
If you haven't come across space leaks before, here's a small taste. The program should print the first number of a lazily generated stream: import java.util.OptionalInt; import static java.util.stream.IntStream.iterate; public class Main { public static void main(String[] args) { System.out.println(fun().getAsInt()); } static OptionalInt fun() { return iterate(0, a -> a + 1) .flatMap(b -> iterate(b, c -> c + 1) .flatMap(d -> iterate(d, e -> e + 1))) .findFirst(); } } Exception in thread "main" java.lang.OutOfMemoryError: Java heap space
deleted 4y ago
[deleted]
dan-robertson 4y ago
I was surprised by the argument about the distribution of space leaks. In particular, it feels a lot like the kinds of silly arguments C/C++ people make about various safety features – that bugs are unlikely / easy to catch / only made by the inexperienced. Those arguments are silly[1] because evidence from the C/C++ programmers who try hard to write correct programs that avoid these bugs is that they cannot be totally avoided. The existence of these kinds of space leak (and lazy evaluation in general) mean that it is hard to predict the performance characteristics of a program in advance. They mean that it can be easier to dos servers by causing them to do slow things which the programmer didn’t realise would be slow. I think that this is (at least sometimes) a safety issue that a language which cares about safety and correctness should care about. Perhaps it is true that worries about space leaks or surprising performance are overblown. But I think that any apology for lazy evaluation in Haskell should attempt to understand and argue against the reasons that someone like SPJ would say ‘the next Haskell will be strict’. (I’m not totally sure what the reason is; maybe it’s just that lazy evaluation is unpopular) [1] more compelling arguments can exist but they must concede points regarding safety.
- slacknatcher12 4y ago
  Hi Author here > Perhaps it is true that worries about space leaks or surprising performance are overblown. But I think that any apology for lazy evaluation in Haskell should attempt to understand and argue against the reasons that someone like SPJ would say ‘the next Haskell will be strict’. (I’m not totally sure what the reason is; maybe it’s just that lazy evaluation is unpopular) You are completely right. The type (b) of space leaks that are a correctness concern must be addressed. I was intending to do a second post about it. I have a classification of space leaks that gives rise to defensive patterns to avoid the class (b). In general space leaks come in two varieties: - Strictness space leaks: there is thunk that to be evaluated need to enter another thunk and another and another, usually growing in size. If we had evaluated in the reduction we could have collapsed the layers accordingly. The classic "foldl' vs foldl" leak is of this kind. - Liveness space leaks: There is a reference that is kept alive because is needed to evaluate a thunk. If we force the thunk, that reference is marked dead and collected. Type 1 of leaks are a property of functions with recursive calls or functions are that are binding expressions (such as >>=). They are local property leak. Type 2 are a global property and the more common kind. Obviously seq appropriately on a strict monad solves the issue. I will do another blogpost discussing the defensive patterns.
tome 4y ago
In my opinion space leaks are a big deal in Haskell. I come across them fairly often and they cause big problems for the kind of software I write. Luckily they are also easy to avoid. I wrote an article about how to eliminate half of them: http://h2.jaguarpaw.co.uk/posts/make-invalid-laziness-unrepresentable/ http://h2.jaguarpaw.co.uk/posts/make-invalid-laziness-unrepr... (the other half are eliminated by disabling the full-laziness transformation).

54 points by runeks 4y ago

My biggest observation from switching from Haskell to Rust is the change in thinking in terms of program composition. In Rust you need to really make some careful design choices in your producer/library code depending on the expected use. All of them quite on the operational level and not really semantically. So many internal choices about refs/arcs/pins/mut/ownership leak out. In Haskell you don’t really do that. If your library internals are neatly written combinators with the right type and semantics you can just expose them and you’re done. Like the article explains, laziness is a big part of this. I understand where that difference comes from, but it’s really a very different way of thinking.

asplake 4y ago
How much of that do you think is due to laziness specifically and not GC?
- sfvisser 4y ago
  Yes, the GC helps tremendously here of course. I guess laziness helps mostly by not dictating the granularity in which to expose both data and building blocks. You can expose more than strictly needed and consumers just pick what’s relevant. Keeping APIs simple and to the point.
wirrbel 4y ago
I really wished there was a GC-ed but strictly-evaluating Haskell. A Rust-like syntax would probably help with adoption but I don't have a strong preference in that.
- discarded1023 4y ago
  Try Standard ML or ocaml. You may be surprised how far the module system can take you, and how limited type classes really are for expressing abstractions. On a different vector, you can see the same story -- type classes are convenient but too limited -- in the development of abstract algebra/topology/analysis/... in Isabelle/HOL. As for laziness, things don't work out too well for a variety of reasons. Bob Harper laid out several many years ago. See e.g. https://news.ycombinator.com/from?site=existentialtype.wordpress.com&next=2481042 https://news.ycombinator.com/from?site=existentialtype.wordp...
  - wirrbel 4y ago
    I really like standard ML. Modules are great but type classes would be … more pragmatic?
    - bmitc 4y ago
      My preference are ML dialects, but it sounds like Idris is something you should check out. It's strict by default and has type classes and dependent types.
      - wirrbel 4y ago
        Idris was always filed in my head as some estoric/academic/obscure thing, will have a look at it.
        bmitc 4y ago
        I actually think it's probably less academic than Haskell or Racket. It's intended to be a practical language that people build things with. It just has an advanced type system and a small community.
    - erk__ 4y ago
      There is even a SML that does not use a GC* but instead does "region based" memory mangement. https://elsman.com/mlkit/about https://elsman.com/mlkit/about *most of the time.
- one-punch 4y ago
  > I really wished there was a GC-ed but strictly-evaluating Haskell. To answer this question literally, there are PureScript (transpile to JavaScript), Idris (dependently typed), OCaml, and Standard ML (as discarded1023 pointed out). But I think the wish for a strictly-evaluating Haskell is sometimes in fact a wish for a Haskell with more predictable performance (especially in memory usage). If so, the Linear Type/Arrow of recent GHC may fit the bill [1]. My wish is for Haskell to have a better runtime [2] with optimal reductions (with more predictable performance and without GC) [3], which could have Rust-like performance without lifetimes, while being lazy. [1]: https://www.tweag.io/blog/2017-03-13-linear-types/ https://www.tweag.io/blog/2017-03-13-linear-types/ [2]: https://discourse.haskell.org/t/high-order-virtual-machine-hvm-an-optional-ghc-like-runtime-for-rust-with-many-comparisons-to-ghc/4118 https://discourse.haskell.org/t/high-order-virtual-machine-h... [3]: https://github.com/HigherOrderCO/HVM https://github.com/HigherOrderCO/HVM
  - noloblo 4y ago
    And faster Compile times haskell compile times relative to golang are super slow
    - one-punch 4y ago
      Golang prioritizes compile time (hence it took them so long to get Generics), which Rust and Haskell are unlikely to beat, as they both prioritize high-levels of abstractions (more compile time for zero cost abstractions at runtime). That said, since GHC is implemented in Haskell, the compile time will likely improve if linear type/arrow, or a better runtime (such as optimal reductions), is used by GHC itself.
      - noloblo 4y ago
        what is linear type/arrow?
        one-punch 4y ago
        Linear Type/Arrow makes sure values are consumed exactly once (as they cannot be duplicated nor destroyed), and such runtime can be used for efficient resource management without reference counting or garbage collection [1]. For Linear Type/Arrow in Haskell, see [2][3][4]. For Linear Type (or Relevant Type) in Rust, see [5]. [1]: https://news.ycombinator.com/item?id=16100840 https://news.ycombinator.com/item?id=16100840 "Linear types can change the world" [2]: https://www.tweag.io/blog/2017-03-13-linear-types/ https://www.tweag.io/blog/2017-03-13-linear-types/ "Linear types make performance more predictable" [3]: https://www.tweag.io/blog/2023-01-26-linear-constraints-freeze/ https://www.tweag.io/blog/2023-01-26-linear-constraints-free... "Linear Constraints: the problem with O(1) freeze" [4]: https://www.reddit.com/r/haskell/comments/v3gouc/linear_text_builder_up_to_20x_faster_than/ https://www.reddit.com/r/haskell/comments/v3gouc/linear_text... "Linear Text Builder: up to 20x faster than alternatives" [5]: https://faultlore.com/blah/linear-rust/ https://faultlore.com/blah/linear-rust/ "The Pain Of Real Linear Types in Rust"
- deleted 4y ago
  [deleted]
- xmcqdpt2 4y ago
  Scala can be quite Haskell-like and is eager evaluating by default. (It's a lot less opinionated though so you can use it to write Java like code.)
  - wirrbel 4y ago
    I have worked professionally with Scala for two years and while I see its appeal of using it over plain Java, it always felt fairly alien to me and pretty complex (probably due to the Java interop and strong typing).
bmitc 4y ago
> Like the article explains, laziness is a big part of this. I don't think the article does a good job addressing this. They have a conclusion they want to get to, but I don't see how they get there with the arguments provided. Languages that are eager by default but support lazy evaluation are also not really discussed, and it's because they are the best of both worlds. Yes, lazy evaluation has its pluses, but more often than not, you don't need it. So it's better to have optional lazy evaluation and then reach for it when you really need it. F#, OCaml, Racket, Elixir, etc. work this way. And F# and Elixir, especially, heavily use compositional code with pipelines. The article states: > On a strict FP language, you end up writing more explicitly recursive functions (hopefully with tail calls) than using higher order functions that express your intent. That is not my experience at all, and I haven't seen anything that supports that. Lastly, Idris has a short FAQ as to why it's eager by default: https://docs.idris-lang.org/en/v1.3.4/faq/faq.html#why-does-idris-use-eager-evaluation-rather-than-lazy https://docs.idris-lang.org/en/v1.3.4/faq/faq.html#why-does-... And that addresses something else the article doesn't get at. Preciseness and explicitness make code much easier to reason about. Lazy evaluation increases mental burden.
- sfvisser 4y ago
  > Lazy evaluation increases mental burden. In some situations, definitely! In other situations, definitely not! My experience with writing Haskell application code is that you’re thinking way less about the runtime operational aspect of your code than in any other language. The burden is much lower. The exceptions are possibly when writing low level library code that involves a lot of IO and steaming. Or when storing a lot of data in-memory for longer periods of time.
- runeks 4y ago
  > Languages that are eager by default but support lazy evaluation are also not really discussed, and it's because they are the best of both worlds. Yes, lazy evaluation has its pluses, but more often than not, you don't need it. What makes you say strictness is the right default? I write Haskell at my day job, and I practically never experience crashes due to space leaks. And given that strictness has its own performance issues (unnecessary evaluation), it’s not clear to me that either is the “right” default.
amelius 4y ago
It would be great if the language allowed you to defer choices and program like in Haskell and then add constraints later and end up with the advantages of Rust. Or apply a series of correctness preserving transformations (perhaps GPT can help with that).

koito17 4y ago

> Lisp communities care more about syntactic extensibility than performance, etc. Huh? Are SBCL maintainers SIMDifying chunks of their CL implementation, improving static type checking and inference, improving numeric performance, and improving compiler optimizations as much as they can simply for "syntactic extensibility?" Even Clojure cares enough about performance and problems with laziness and copying to give us eductions and transducers, respectively, to work around the inherent performance issues in both. I have no idea what Lisp communities the reader must be referring to.

lispm 4y ago
There are some Lisp communities which value syntactic extensibility more than low-level performance. For example when using FEXPRs, which are functions which have access to their source and where the function decides which arguments to evaluate. You'll find that in R, Picolisp, Standard Lisp and a few others. Most other Lisp communities have settled on always strict evaluation and compilable macros as syntactic extensions.
- antonvs 4y ago
  FEXPRs haven’t been relevant in mainstream Lisp since the 1980s. See Kent Pitman’s 1980 article describing the problems with them: https://www.nhplace.com/kent/Papers/Special-Forms.htmL https://www.nhplace.com/kent/Papers/Special-Forms.htmL The languages you mention probably use them mainly because they’re easy to implement in the language implementation, which has nothing to do with what the community values, except in a post-hoc sense when the community tries to justify to itself why it’s using such an inherently intractable feature.
  - lispm 4y ago
    Usually the arguments are a) it provides runtime access to the source (which for example is useful in R), b) runtime introspection is easier to understand (for the proponents) & less complex than macros and that macros are too static (they want more flexibility at runtime). For example authors of the REDUCE computer algebra system ( https://reduce-algebra.sourceforge.io/ https://reduce-algebra.sourceforge.io/ ) disliked Common Lisp for the lack of FEXPRs and that's why they stayed away from it. There were lots of discussions at the time when Common Lisp was introduced. > The languages you mention probably No, see above. Example: https://picolisp.com/wiki/?pros-and-cons https://picolisp.com/wiki/?pros-and-cons

ummonk 4y ago

The article seems to downplay the effect that space leaks can have on correctness / reliability. If 99.9% of code you write works, but every once in a while code nondeterministically encounters space leaks, that's a bad thing for the reliability of the language as a whole. You can no longer rely on any program you write being guaranteed to execute to completion.

throwaway81523 4y ago
I would say in an exaggerated version of the Haskell mindset, the most important thing is to prevent the program from giving wrong answers. The archetypal Haskell program is a compiler, and having it generate wrong code that gets deployed on a space mission is disastrous. Having the compiler crash with a memory leak is merely an annoyance. You would not write realtime code in idiomatic Haskell, if you would write such code in Haskell at all.
- murdoze 4y ago
  Real-time code has high requirements for correctness and execution deadlines. Which means, w/o deterministic execution Haskell not suitable for a whole niche, where its safety properties are in a high demand. Which is a pity.
  - hexane360 4y ago
    Sure, but currently almost all of the most popular languages are also not suitable for that niche. If you exclude any garbage-collected language, you're basically left with Ada, C, C++, some of the "C/C++ successors" (Zig, D, Carbon, maybe Nim), and Rust.
  - throwaway81523 4y ago
    That's fine, those applications are why Ada was invented. Languages get pulled in too many directions when they try to be everything to everyone.
- ummonk 4y ago
  "OOM exception" is a wrong answer. If your code terminates on a space mission because lazy evaluation runs out of memory, it's disastrous.

chriswarbo 4y ago

See also Why Functional Programming Matters, from 1984 https://www.cse.chalmers.se/~rjmh/Papers/whyfp.html https://www.cse.chalmers.se/~rjmh/Papers/whyfp.html > Recall that a complete functional program is just a function from its input to its output. If f and g are such programs, then (g . f) is a program which, when applied to its input, computes g (f input) > The program f computes its output which is used as the input to program g. This might be implemented conventionally by storing the output from f in a temporary file. The problem with this is that the temporary file might occupy so much memory that it is impractical to glue the programs together in this way. > Functional languages provide a solution to this problem. The two programs f and g are run together in strict synchronisation. F is only started once g tries to read some input, and only runs for long enough to deliver the output g is trying to read. Then f is suspended and g is run until it tries to read another input. As an added bonus, if g terminates without reading all of f’s output then f is aborted. F can even be a non-terminating program, producing an infinite amount of output, since it will be terminated forcibly as soon as g is finished. This allows termination conditions to be separated from loop bodies - a powerful modularisation. > Since this method of evaluation runs f as little as possible, it is called “lazy evaluation”. It makes it practical to modularise a program as a generator which constructs a large number of possible answers, and a selector which chooses the appropriate one. While some other systems allow programs to be run together in this manner, only functional languages use lazy evaluation uniformly for every function call, allowing any part of a program to be modularised in this way. Lazy evaluation is perhaps the most powerful tool for modularisation in the functional programmer’s repertoire.

quanticle 4y ago

That might seem the case from afar, but once you start writing Haskell and start experimenting these space leaks, you will notice that: 1. 90% of the space leaks you write end up adding a tiny amount of memory usage to your functions, mostly unnoticeable. Think thunks like (1 + 2) that are subjected to demand analysis under optimization. 2. 1-2% of them are serious enough to require profiling your code with cost-centres. But that's pretty much the same as in C. The vast majority of memory leaks in C aren't fatal to the program. They just lead to a little bit of extra memory usage, mostly unnoticeable. And then you have the small fraction of memory leaks that draw the attention of the OOM-killer. A tacit admission that detecting code that is leaking memory in Haskell is no easier than detecting code that is leaking memory in C does not speak well for Haskell. Memory leaks are a matter of correctness and reliability. Our computers are not ideal Turing machines. Their "tapes" are finite. Running out of memory causes the program to crash and produce incorrect results. Arguing that this only happens in a small fraction of cases, and can be handled with testing and profiling isn't persuasive, because one might say the same thing for a dynamically typed language, like Python.

chriswarbo 4y ago
"Space leaks" are not "memory leaks". A memory leak means a program will never free some region of memory; e.g. if it's pointer has been discarded without calling 'free'. That is certainly a matter of correctness. That is certainly a problem for finite-memory machines. In constrast, a "space leak" is just a suboptimal usage of memory. As a classic example, we want the sum of a list of integers to fully evaluate the running total at each step, like this: sum(0, [1,2,3]) sum(0+1, [2, 3]) sum(1, [2, 3]) sum(1+2, [3]) sum(3, [3]) sum(3+3, []) sum(6, []) 6 However, lazy evaluation may avoid performing the additions right away; instead building up unevaluated 'thunks' (nullary functions), which only get evaluated at the end, like this: sum(0, [1,2,3]) sum(0+1, [2, 3]) sum((0+1)+2, [3]) sum(((0+1)+2)+3, []) ((0+1)+2)+3 (1+2)+3 3+3 6 This is a perfectly correct calculation; and everything has been 'cleaned up' at the end (no worries about 'infinite tapes', etc.). However, if we're trying to e.g. process a massive data stream from disk, these unevaluated thunks may quickly exhaust our available memory.

mrkeen 4y ago

If you haven't come across space leaks before, here's a small taste. The program should print the first number of a lazily generated stream: import java.util.OptionalInt; import static java.util.stream.IntStream.iterate; public class Main { public static void main(String[] args) { System.out.println(fun().getAsInt()); } static OptionalInt fun() { return iterate(0, a -> a + 1) .flatMap(b -> iterate(b, c -> c + 1) .flatMap(d -> iterate(d, e -> e + 1))) .findFirst(); } } Exception in thread "main" java.lang.OutOfMemoryError: Java heap space

deleted 4y ago

[deleted]

dan-robertson 4y ago

I was surprised by the argument about the distribution of space leaks. In particular, it feels a lot like the kinds of silly arguments C/C++ people make about various safety features – that bugs are unlikely / easy to catch / only made by the inexperienced. Those arguments are silly[1] because evidence from the C/C++ programmers who try hard to write correct programs that avoid these bugs is that they cannot be totally avoided. The existence of these kinds of space leak (and lazy evaluation in general) mean that it is hard to predict the performance characteristics of a program in advance. They mean that it can be easier to dos servers by causing them to do slow things which the programmer didn’t realise would be slow. I think that this is (at least sometimes) a safety issue that a language which cares about safety and correctness should care about. Perhaps it is true that worries about space leaks or surprising performance are overblown. But I think that any apology for lazy evaluation in Haskell should attempt to understand and argue against the reasons that someone like SPJ would say ‘the next Haskell will be strict’. (I’m not totally sure what the reason is; maybe it’s just that lazy evaluation is unpopular) [1] more compelling arguments can exist but they must concede points regarding safety.

slacknatcher12 4y ago
Hi Author here > Perhaps it is true that worries about space leaks or surprising performance are overblown. But I think that any apology for lazy evaluation in Haskell should attempt to understand and argue against the reasons that someone like SPJ would say ‘the next Haskell will be strict’. (I’m not totally sure what the reason is; maybe it’s just that lazy evaluation is unpopular) You are completely right. The type (b) of space leaks that are a correctness concern must be addressed. I was intending to do a second post about it. I have a classification of space leaks that gives rise to defensive patterns to avoid the class (b). In general space leaks come in two varieties: - Strictness space leaks: there is thunk that to be evaluated need to enter another thunk and another and another, usually growing in size. If we had evaluated in the reduction we could have collapsed the layers accordingly. The classic "foldl' vs foldl" leak is of this kind. - Liveness space leaks: There is a reference that is kept alive because is needed to evaluate a thunk. If we force the thunk, that reference is marked dead and collected. Type 1 of leaks are a property of functions with recursive calls or functions are that are binding expressions (such as >>=). They are local property leak. Type 2 are a global property and the more common kind. Obviously seq appropriately on a strict monad solves the issue. I will do another blogpost discussing the defensive patterns.

tome 4y ago

In my opinion space leaks are a big deal in Haskell. I come across them fairly often and they cause big problems for the kind of software I write. Luckily they are also easy to avoid. I wrote an article about how to eliminate half of them: http://h2.jaguarpaw.co.uk/posts/make-invalid-laziness-unrepresentable/ http://h2.jaguarpaw.co.uk/posts/make-invalid-laziness-unrepr... (the other half are eliminated by disabling the full-laziness transformation).