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

11–20 of 53 posts

Re: An apologia of lazy evaluation

#11

Post by [deleted] »

wirrbel wrote: post #6
sfvisser wrote: post #2

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…

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.

[deleted]

Re: An apologia of lazy evaluation

#12

Post by wirrbel »

discarded1023 wrote: post #7
wirrbel wrote: post #6

Earlier quoted context omitted.

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. 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?

Re: An apologia of lazy evaluation

#13

Post by throwaway81523 »

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 such code in Haskell at all.

Re: An apologia of lazy evaluation

#14

Post by quanticle » 

    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.

Re: An apologia of lazy evaluation

#15

Post by mrkeen »

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

Re: An apologia of lazy evaluation

#16

Post by lispm »

koito17 wrote: post #4

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

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.

Re: An apologia of lazy evaluation

#17

Post by bmitc »

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?

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.

Re: An apologia of lazy evaluation

#18

Post by chriswarbo »

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

Re: An apologia of lazy evaluation

#19

Post by bmitc »

sfvisser wrote: post #2

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…

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

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.

Re: An apologia of lazy evaluation

#20

Post by chriswarbo »

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.

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

Post reply on HN