Hacker News Reader

Comment by olenhad | Hacker News Reader

I wonder what's the primary reason for their "Mu" compiler adopting a "strict-ish" evaluation strategy.

A pretty common idea in Haskell-land is that "the next Haskell would be strict". Laziness was once a dreamy ideal execution strategy, but thanks to Haskell the practical tradeoff is better understood.

At the same time (as the slides note) the strict/lazy divide is hardly decided! As many people who would rather Haskell be strict are willing to defend laziness to the death for being the key reason Haskell is so composable. [0]

So Lennart Augustsson—the author of the first standard's compliant Haskell compiler, I believe—wrote up Mu and made it strict. There is probably a justification in SC's case for why it was an experiment worth trying.

[0] At the very least it's indisputable that laziness forced Haskell's hand with purity and that ended up being an enormous win in everyone's opinion.

This is interesting, because the well-known paper "Why functional programming matters" identifies two key aspects of FP: higher-order functions and lazy evaluation. I wonder if John Hughes has reviewed his opinion on this, or if the FP community thinks the paper is no longer an accurate insight into FP...

In particular, I'm thinking of the last paragraph of Hughes' conclusions:

"It is also relevant to the present controversy over lazy evaluation. Some believe that functional languages should be lazy, others believe they should not. Some compromise and provide only lazy lists, with a special syntax for constructing them (as, for example, in SCHEME [AS86]). This paper provides further evidence that lazy evaluation is too important to be relegated to second-class citizenship. It is perhaps the most powerful glue functional programmers possess. One should not obstruct access to such a vital tool."

Maybe it turned out that practical evidence has shown that lazy evaluation wasn't as important for modularity as Hughes thought, or at least that its drawbacks have been found unacceptable in practice?

I think that there is no cut and dried answer. Laziness appears to dramatically improve modularity, but it's unclear whether all of the tradeoffs are worth it. It's difficult to analyze the downsides still since (a) more research is needed and (b) a lot of it can be shrugged off as "weirdness", but it's clear that there are reasons to prefer strictness as well as to prefer laziness.

I've grown to be of the opinion that neither is best and that languages ought to be developed which allow free and clear choice between evaluation strategies throughout. Lazy defaults at the right times and clear strictness types might be a way forward, but it's hardly anything I have expertise in.

It's so weird to me that in a world of more asynchronicity than ever we want to bring Haskell to strict-land.

On the opposite end, there is so much boilerplate optimisation out there to get around the strictness of other programming languages that would be solved with a non-strict mode

Strictness can always embed laziness---this is sometimes an argument for the natural superiority of strictness---so long as you have lightweight lambdas. Thus, in OCaml you'll see a lot of

    thunk () = long_computation

effectively. Is that syntactic noise enough to disable the advantages of laziness? Actually, maybe!

> Strictness can always embed laziness

And vice versa, although I think embedding strictness in laziness is probably more syntactically heavyweight.

http://h2.jaguarpaw.co.uk/posts/strictness-in-types/

> Is that syntactic noise enough to disable the advantages of laziness? Actually, maybe!

Hmm, if that's the case then it seems that

    thunk = return long_computation

is enough to disable the advantages of monads! :)

But note that achieving the strictness type requires the use of `seq` which is perhaps, arguably, a more arbitrary language feature than function abstraction and unit are! In particular, it's been a big debate as to what the proper semantics for seq are—the dust is technically unsettled, despite the long history of seq in Haskell.

And w.r.t. to monads, for a lot of people it is! Most use of monads is done implicitly, right? ;) The only reason Haskellers tolerate the extra syntax is because it's statically required (I claim).

There's an advantage here, of course, in statically ensuring that people do something more explicitly than they would like to. Perhaps the same advantage applies to thunking.

Honestly, I'd rather not comment. I don't know that I or nearly anyone has enough information to make strong, confident opinions about the "right way" to do lazy/strict. I'm hoping that the research into total languages will provide answers!

I tend to feel this is one area where perhaps Scheme had the right idea (if you ignore set!). Now, I don't know a whole lot about Haskell, but one of (IMO) the elegant parts of Scheme is that you can choose when and where to use streams instead of lists.

The main benefits of streams vs. lists is usually composability, but also that delayed computation can save you from computing something you'll never need. In this way, I think that being able to choose when and where you apply laziness is a huge gain. Now, of course this is where people will complain that streams are either a bad abstraction, or that doing stream-cons vs cons is annoying, but I like to think "what if it was the other way around?". Namely, if you had streams used by default (a la laziness in Clojure), but could switch to lists when it was really necessary or made reasoning about your code easier.

Is there a language that does this smoothly? From what I understand, to work around laziness, you typically have to bend over backwards in Haskell, but if there was a good way to just transform lazy data structures into strict structures similar to the relationship between [stream]-map or [stream]-cons/car/cdr and the list equivalents, I think it'd be pretty exciting. Though to be honest, I'm not sure how this would interact with Monads / Type Classes / etc, especially if you have Type Classes relying on both lazy and non-lazy structures.

The typical idea is that you almost always want "spine lazy" data structures. So, streams are almost always more valuable than strict lists.

In my mind, I tend to think of this as being true up to the point where the size of the structure is statically known. Thus for fixed-sized vectors (or arrays), spine strictness is very important—it gives you better control over memory usage in the very least.

Unfortunately, no language I know of has a good concept of "strictness polymorphism" so in Haskell you end up with duplicate implementations of Strict and Lazy data structures. This ends up being not so much duplicated code, but a whole hell of a lot of duplicated API.

And I think the stream-cons/cons distinction is trivial. It's a lack of proper polymorphism that you're dealing with there and that can be easily implemented in any language with good polymorphism. In Haskell we have a very nice (very nice if you tolerate lenses, anyway, which you should) interface called Cons which is an elaboration of

    class Cons s where
      type Elem s
      _Cons :: Prism s (Elem s, s)

which works like this

    instance Cons [a] where
      type Elem [a] = a
      _Cons = ... -- more complex than worth explaining

    instance Cons (Stream a) where
      type Elem (Stream a) = a
      _Cons = ...

and then gives you

    cons   :: Cons s => Elem s -> s -> s
    uncons :: Cons s => s -> Maybe (Elem s, s)

which are generic in Stream a and [a].

I don't know, but in my limited experience, lazy evaluation makes memory use worse (usually not much), but more importantly makes performance (time and memory) harder to reason about, because you don't easily know when something will actually evaluate.

Besides that, there's also not much practical gain from it, IMO. One commonly cited benefit is a function that doesn't use all of it's arguments, therefore saving computation time when they're not evaluated. But realistically, an unused parameter should probably be removed.

Some level of lazyness is nessasary for Haskell to work. For example, you can do:

    a=1:a
    main = show $ head a

With lazy evaluation, this will print "1", but with strict evaluation, this program will never terminate as it attempts to fully evaluate "a=1:a", which creates an infinite list.

>But realistically, an unused parameter should probably be removed. You also have cases where a parameter is only used some of the time.

Generally the argument is never around saved computation but instead around composability. Lazy languages ensure that everything behaves like a value and in that domain operations compose much more effortlessly. You can't reason about operation as easily, so you don't, and the language can cope with making that work more or less correctly.

Which is definitely suboptimal in some cases!

I think honestly the goal should be reasoning about evaluation order statically instead of trying to find some clever argument such that laziness or strictness is clearly "correct".

> But realistically, an unused parameter should probably be removed.

Think about the function if-then-else, which you may be familiar with from your favorite language :)

    if-then-else true branch1 branch2 = branch1
    if-then-else false branch1 branch2 = branch2

Obviously you don't want both branches evaluated in any given invocation, and obviously you cannot remove the unused parameter. Note that the purpose is not to "save computation", since for example branch1 may be undefined if cond is false!

When using a language with support for lazy evaluation, you encounter this kind of functions all the time.

Of course, in OCaml that's just

    if_then_else c t e = 
      match c with
      | true  -> t ()
      | false -> e ()

So the question sort of becomes one of how painful thunking or anonymous function syntax is.

> One commonly cited benefit is a function that doesn't use all of it's arguments, therefore saving computation time when they're not evaluated. But realistically, an unused parameter should probably be removed.

How do you do that when the values of the other arguments determine whether or not that argument will be used?

an unused parameter should probably be removed.

It doesn't have to be completely unused to be avoided. In a case like:

if a then b + c else c + d

a and c are always evaluated, only b or d is evaluated not both. Removal isn't an option because b and d maybe used.

https://news.ycombinator.com/item?id=8964949

It may be that their applications have high memory usage, which lazy evaluation would make slightly worse. Alternatively, they may have found that the applications that they tend to run benefit from a slightly stricter evaluation strategy, and have thus changed the compiler to better reflect that...

Not sure, but having encountered laziness in Clojure and Haskell, it can be non-intuitive and it can be a bitch to debug. It allows for some conceptual beauty, though, and there are certainly some use cases in which laziness is the right behavior. The question is what should be the default; both ought to be allowed. In Haskell, they are, but you start using bangs a lot (e.g. Point !Int !Int and the ($!) operator instead of ($)) and there are also shallow vs. deep considerations, because forcing a thunk only evaluates it one constructor-level deep-- to "weak head normal form".

That said, I much prefer Haskell's laziness or Clojure's laziness in seqs over the broken laziness in other languages. There's a lot to like about R's libraries but... fuck this:

    > Map(function(x) (function(y) x + y), 1:5)[[3]](0)
    [1] 5

Python can be tricked into the same evil if you build closures in a loop. Haskell doesn't have that, thankfully.

Laziness in data structures has the biggest benefit in the spine. Leaf laziness is just more surface area to hide unexpected thunks. If you really want that, do something like

    data Box a = Box a

    type Lazier a = Tree (Box a)

Generally, I find that a little habit around leaf strictness ends up eliminating laziness concerns entirely until you get to explicit concurrent programming and need to think carefully about what thread is forcing what execution.

Reply on news.ycombinator.com