Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

An apologia of lazy evaluation

epicandmonicisnotiso.blogspot.com

Post reply on HN
Print view View original

41–50 of 53 posts

Re: An apologia of lazy evaluation

#41

Post by ummonk »

runeks wrote: post #38
ummonk wrote: post #37

Earlier quoted context omitted.

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.

Re: An apologia of lazy evaluation

#42

Post by ummonk »

chriswarbo wrote: post #18
quanticle wrote: post #14

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-cent…

"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 r…

"A memory leak means a program will never free some region of memory"

The memory gets freed when the program terminates.

Re: An apologia of lazy evaluation

#43

Post by ummonk »

throwaway81523 wrote: post #13
ummonk wrote: post #8

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 suc…

"OOM exception" is a wrong answer. If your code terminates on a space mission because lazy evaluation runs out of memory, it's disastrous.

Re: An apologia of lazy evaluation

#44

Post by sudosysgen »

ummonk wrote: post #42
chriswarbo wrote: post #18

Earlier quoted context omitted.

"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 r…

"A memory leak means a program will never free some region of memory" The memory gets freed when the program terminates.

This is the memory management technique that many programs, such as GCC, used to very good results.

Re: An apologia of lazy evaluation

#45

Post by noloblo »

one-punch wrote: post #35
noloblo wrote: post #31

Earlier quoted context omitted.

And faster Compile times haskell compile times relative to golang are super slow

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.

what is linear type/arrow?

Re: An apologia of lazy evaluation

#46

Post by erk__ »

wirrbel wrote: post #12
discarded1023 wrote: post #7

Earlier quoted context omitted.

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 l…

I really like standard ML. Modules are great but type classes would be … more pragmatic?

There is even a SML that does not use a GC* but instead does "region based" memory mangement.

https://elsman.com/mlkit/about

*most of the time.

Re: An apologia of lazy evaluation

#47

Post by throwaway81523 »

ummonk wrote: post #43
throwaway81523 wrote: post #13

Earlier quoted context omitted.

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 suc…

"OOM exception" is a wrong answer. If your code terminates on a space mission because lazy evaluation runs out of memory, it's disastrous.

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.

Re: An apologia of lazy evaluation

#48

Post by antonvs »

lispm wrote: post #33
antonvs wrote: post #28

Earlier quoted context omitted.

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 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 justif…

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…

Thanks for the correction and info.

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.

Re: An apologia of lazy evaluation

#49

Post by wirrbel »

noloblo wrote: post #31
one-punch wrote: post #10

Earlier quoted context omitted.

> 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/Ar…

And faster Compile times haskell compile times relative to golang are super slow

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

Re: An apologia of lazy evaluation

#50

Post by one-punch »

noloblo wrote: post #45
one-punch wrote: post #35

Earlier quoted context omitted.

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.

what is linear type/arrow?

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 "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"

Post reply on HN