An apologia of lazy evaluation
epicandmonicisnotiso.blogspot.com
epicandmonicisnotiso.blogspot.com
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.
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...
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.
> 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)
> 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.
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:
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
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
The memory gets freed when the program terminates.
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.
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.
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.
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 spacehttp://h2.jaguarpaw.co.uk/posts/make-invalid-laziness-unrepr...
(the other half are eliminated by disabling the full-laziness transformation).
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.