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.
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.
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.
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.
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.
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.
> 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.
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.
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].
Go lang is just a different class of languages. One picks rust or Haskell or standard ML due to an expressive type system whereas Go features a simple type system
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).
> 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.
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.
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.
> 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.
As someone who worked with F# professionally for multiple years, I think I can quite confidently say that laziness is not ergonomic in F#, at all. I've tried making use of it many times, but because you have to explicitly delay and force values all over the place, it infects and dirties up code whenever you try to use it.
Idris(at least idris2) gets a bit closer with the implicit delaying and forcing, but changing a value from lazy to strict and viceversa still modifies the signature, which is kind of annoying in my opinion. Compared to Haskell, where I can just add bangpatterns and sprinkle `!` in a few places, it's still less ergonomic.
I feel like there isn't really a good implementation of strict-by-default but lazy-on-demand functional programming that is ergonomic and gets out of the way, quite yet.
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).
> 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.
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.
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.
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/ ) 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.
I have to retract my claim about the reason those languages use FEXPRs, but I'm not convinced they're good reasons. There are, however, very good reasons why the FEXPR approach has been abandoned by other languages, as the Pitman article points out.
There are certainly better ways to achieve pretty much anything you might want FEXPR-style source code access for. Aside from the Lisp world, there are things like Template Haskell, Rust macros, Ocaml's Camlp4/5, etc.
But you don't even need a macro-like system to implement most of the kinds of features in question here. For example, here's "A Purely Functional Computer Algebra System Embedded in Haskell": https://arxiv.org/abs/1807.01456
It exploits the type system, lazy evaluation, purity, and property-based testing to implement a computer algebra system without needing to accept all the compromises involved in having programs manipulate their own source code.
I'm thoroughly convinced that fexprs are a bad idea and so, good riddance. Our Lisp hacking predecessors did us a huge favor by figuring this out and documenting it.
Fexprs are hostile toward compiling. Specifically, True Scotsman's ahead-of-time compiling where we take an entire file or set of files and turn them into compiled equivalents, whereby we obtain:
1. Useful diagnostics without running the code.
2. Deliverables which load and execute faster, and don't require any code processing at run time (unless we choose that as part of application logic).
3. Resistance to reverse engineering, so we get paid. :)
Even a macro expander in front of an interpreter can provide error checking, such as finding unbound variables, reporting about misused special forms, and even things like functions being called with wrong numbers of arguments.
Macros themselves can be well written and provide decent error checking. So could fexprs, but fexprs have to be called.
You can't code walk fexprs because you don't know which parts of the argument material of a fexpr contains more fexprs.
It is counterproductive to lose the ability to completely code-walk a program, just to gain the ability to perpetrate trompe d'oeil metaprogramming: the software engineering equivalent of having a hand reach out of the picture, holding a pencil which draws the picture frame.
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.
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.
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.
The code on the space mission wouldn't use Haskell or lazy evaluation. It would be written in something like Ada. In this picture, the Ada compiler would be written in Haskell. If the Ada compiler crashes with OOM, there is a disruption while you fix the leak, or run on a bigger machine as a stopgap. But if the output code crashes, that can ruin the space mission.
So the main concern is that if the compiler doesn't crash, the generated code should be correct. Haskell's type system helps you write compilers that don't generate wrong code.
As an even more extreme example, look at CompCert (compcert.inria.fr), which is a C compiler written in Coq. You can think of Coq as a dependently typed dialect of ML. For much of the backend, there are formal proofs that the output assembly code does the same thing as the input C code. The compiler is guaranteed to be free of a wide class of code generation bugs. But, AFAIK it is not guaranteed to be free of memory leaks or other crashes. Its reliability in that regard is just like any other software that has passed a reasonable amount of testing and has worked ok in production.
> 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.
I don't know what you mean by "nondeterministic"? The behavious is occasionally hard to predict, but it's completely deterministic.
Compare it to e.g. writing C in a certain style, relying on GCC to optimise it. Those optimisations might not apply for one chunk of code, so we end up with bad performance. Yet it's completely deterministic.
I should have said "undefined". What I meant was that the space the program will use isn't defined by the language itself and can't be known at compile time. It's dependent on implementation details of the compiler (GHC), and the particular input you feed to the program when executing it.
> What I meant was that the space the program will use isn't defined by the language itself and can't be known at compile time.
You can know the space usage (in relation to input size) of some Haskell programs at compile-time — e.g. if you use a constant-memory streaming abstraction.
I don’t know much about Rust, but I don’t think it guarantees known space usage of all possible programs at compile-time.
Don't know if Rust has this ability, but SPARK (a subset of Ada for safety-critical code) does have the ability to guarantee known space usage, as well as guarantee that a program will terminate.
> 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.
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.
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:
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:
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.
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
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.
> 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.
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:
52 comments
[ 5.2 ms ] story [ 101 ms ] threadIn 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.
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.
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.wordp...
https://elsman.com/mlkit/about
*most of the time.
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/
[2]: https://discourse.haskell.org/t/high-order-virtual-machine-h...
[3]: https://github.com/HigherOrderCO/HVM
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.
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 "Linear types can change the world"
[2]: 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-free... "Linear Constraints: the problem with O(1) freeze"
[4]: 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/ "The Pain Of Real Linear Types in Rust"
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-...
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.
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.
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.
Idris(at least idris2) gets a bit closer with the implicit delaying and forcing, but changing a value from lazy to strict and viceversa still modifies the signature, which is kind of annoying in my opinion. Compared to Haskell, where I can just add bangpatterns and sprinkle `!` in a few places, it's still less ergonomic.
I feel like there isn't really a good implementation of strict-by-default but lazy-on-demand functional programming that is ergonomic and gets out of the way, quite yet.
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.
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.
> The languages you mention probably
No, see above.
Example: https://picolisp.com/wiki/?pros-and-cons
I have to retract my claim about the reason those languages use FEXPRs, but I'm not convinced they're good reasons. There are, however, very good reasons why the FEXPR approach has been abandoned by other languages, as the Pitman article points out.
There are certainly better ways to achieve pretty much anything you might want FEXPR-style source code access for. Aside from the Lisp world, there are things like Template Haskell, Rust macros, Ocaml's Camlp4/5, etc.
But you don't even need a macro-like system to implement most of the kinds of features in question here. For example, here's "A Purely Functional Computer Algebra System Embedded in Haskell": https://arxiv.org/abs/1807.01456
It exploits the type system, lazy evaluation, purity, and property-based testing to implement a computer algebra system without needing to accept all the compromises involved in having programs manipulate their own source code.
Fexprs are hostile toward compiling. Specifically, True Scotsman's ahead-of-time compiling where we take an entire file or set of files and turn them into compiled equivalents, whereby we obtain:
1. Useful diagnostics without running the code.
2. Deliverables which load and execute faster, and don't require any code processing at run time (unless we choose that as part of application logic).
3. Resistance to reverse engineering, so we get paid. :)
Even a macro expander in front of an interpreter can provide error checking, such as finding unbound variables, reporting about misused special forms, and even things like functions being called with wrong numbers of arguments.
Macros themselves can be well written and provide decent error checking. So could fexprs, but fexprs have to be called.
You can't code walk fexprs because you don't know which parts of the argument material of a fexpr contains more fexprs.
It is counterproductive to lose the ability to completely code-walk a program, just to gain the ability to perpetrate trompe d'oeil metaprogramming: the software engineering equivalent of having a hand reach out of the picture, holding a pencil which draws the picture frame.
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.
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.
So the main concern is that if the compiler doesn't crash, the generated code should be correct. Haskell's type system helps you write compilers that don't generate wrong code.
As an even more extreme example, look at CompCert (compcert.inria.fr), which is a C compiler written in Coq. You can think of Coq as a dependently typed dialect of ML. For much of the backend, there are formal proofs that the output assembly code does the same thing as the input C code. The compiler is guaranteed to be free of a wide class of code generation bugs. But, AFAIK it is not guaranteed to be free of memory leaks or other crashes. Its reliability in that regard is just like any other software that has passed a reasonable amount of testing and has worked ok in production.
I don't know what you mean by "nondeterministic"? The behavious is occasionally hard to predict, but it's completely deterministic.
Compare it to e.g. writing C in a certain style, relying on GCC to optimise it. Those optimisations might not apply for one chunk of code, so we end up with bad performance. Yet it's completely deterministic.
You can know the space usage (in relation to input size) of some Haskell programs at compile-time — e.g. if you use a constant-memory streaming abstraction.
I don’t know much about Rust, but I don’t think it guarantees known space usage of all possible programs at compile-time.
> 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
> 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.
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.
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:
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: 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.The memory gets freed when the program terminates.
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.
> 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.
http://h2.jaguarpaw.co.uk/posts/make-invalid-laziness-unrepr...
(the other half are eliminated by disabling the full-laziness transformation).