Hi everyone,
I’ve stumbled upon this : https://github.com/Kindelia/HVM/blob/master/HOW.md on twitter while reading a thread about different Garbage Collection tech for Unison by Paul Chiusano.
I don’t have a sufficient understanding of GHC’s internals to assess whether the claims in the article are valid/interesting and potentially usable as guiding ideas for improving GHC’s execution model, so I’m curious about anyone’s judgement on this.
I’m especially curious about the following excerpts regarding GHC’s handling of lambdas and thunks :
For example, Haskell is lazy. To avoid “cloning computations”, it implements thunks, which are nothing but memoized references to shared expressions, allowing the
(2 * 2)example above to be cached. This solution, though, breaks down when there are lambdas.
And then
References. They ruin everything. They’re the reason Rust is so hard to use. They’re the reason parallel programming is so complex. They’re the reason Haskell isn’t optimal, since thunks can’t share computations that have free variables (i.e., any expression inside lambdas). They’re why a 1-month-old prototype beats GHC in the same class of programs it should thrive in. It isn’t GHC’s fault. References are the real culprits.
And the purported solution beeing a lazy layer-by-layer clone (like the rust clone, but lazier).
HVM’s runtime has no references. Instead, it features a
.clone()primitive that has zero cost, until the cloned value needs to be read. Once it does, instead of being copied whole, it’s done layer by layer, on-demand.
Why are thunks unable to share computations with free variables, and what does it mean in practice (as in, in a real world program) ? If this is all true as-is (and no nuance is needed), can this idea of a lazy clone primitive be implemented in GHC and would it make sense ?
And then there is the part about beta optimality :
Similar uses of this idea can greatly speed up functional algorithms. For example, a clever way to implement a
Data.Listwould be to let all algorithms operate on Church-encoded Lists under the hoods, converting as needed. This has the same “deforestation” effect of Haskell’s rewrite pragmas, without any hard- coded compile-time rewriting, and in a more flexible way. For example, usingmapin a loop is “deforested” in HVM. GHC can’t do that, because the number of applications is not known statically.
Why GHC can’t know the number of applications statically ? My understanding is that it’s simply because we can’t know when the recursion end (because infinite lists are allowed), but then is the proposed solution preventing inifinite lists or is it something entirely different ?
Thanks for any explanation