6 ms·

IMHO Haskell's lazy evaluation has some significant disadvantages compared to SML's strict evaluation. In particular, lazy evaluation makes it difficult to find

IMHO Haskell's lazy evaluation has some significant disadvantages compared to SML's strict evaluation. In particular, lazy evaluation makes it difficult to find the performance bottlenecks in a particular piece of code or to determine the time complexity of an algorithm just by reading it. Furthermore, subtle changes in how a function is written (for instance, making a multiplication function not evaluate the right operand if the left operand is zero) can cause wildly unexpected performance changes in that function's callers. In effect, the performance of a function is no longer just determined by that function's structure and by the function calls it contains; performance of one function now depends heavily on the implementation details of others and the context in which that function is used. Granted, any optimizing compiler can have this effect, but it's rarely noticeable in strictly-evaluated languages, where at least to some extent the order of evaluation must correspond to the structure of the code.

zozbot234 4y ago
It would be nice to have a language that could treat both strict and lazy evaluation as equally first-class, as opposed to having one be the default (whether "strict" as in ML or "lazy" as in Haskell) and the other only being expressed by syntactical kludges. This may well be possible by relying on logically-inspired features like polarity and focusing, and endowing data types with strict or lazy "natural" polarities.
- eatonphil 4y ago
  Any strict language can implement laziness. The inverse may(?) not be possible.
  - ravi-delia 4y ago
    It's the opposite, no? Basically every lazy language has some way to force evaluation, but in most strict languages laziness is never fully supported. Closest I can think of is a Scheme with continuations, but even then it takes some extra work. I know in CL even primitive laziness takes a lot of work and a code-walker, and whatever it's other flaws Common Lisp is at least adaptable.
    - eatonphil 4y ago
      I could be totally wrong, happy to be corrected. And I'm less familiar with lazy languages. My very basic impression of implementing laziness is just that you wrap all of your data structures/algorithms in functions that must themselves be called. Like everything is an iterator. See also: https://en.wikipedia.org/wiki/Lazy_evaluation#Simulating_laziness_in_eager_languages https://en.wikipedia.org/wiki/Lazy_evaluation#Simulating_laz...
      - mananaysiempre 4y ago
        Wrapping in bare functions gives you “call by name”, where let y = f(x) in g(y, y) will compute f(x) twice. In effect you just evaluate function applications (and lets) by substituting a copy(!) of the argument text for every occurence of the variable in the body. It’s pretty easy for this to get exponentially bad. If you want conventional lazy evaluation, that is “call by need”, you need to memoize: wrap everything in stateful functions (“thunks” in Haskell-implementer-speak, “promises” in Scheme-speak, but not the same as E/JavaScript-style async promises) that compute the result and save it on the first invocation, but then return it immediately. Apart from efficiency considerations (it’s better to use a tagged union of function pointer and result value instead of calling the function all the time) and a single conceptual wrinkle[1], that’s it. Call-by-name and call-by-need obviously yield very different complexity, but are in fact equivalent regarding termination, and optimal: if any evaluation strategy terminates on a given term, so do they. The lovely recent paper “Call-by-need is clairvoyant call-by-value”[2] shows that lazy evaluation in fact never does more steps than call-by-need and in fact does a subset of them: those and only those that influence the final result. (The problem, of course, is that none of this addresses memory usage.) Emulating eager evaluation with lazy can be done if you have seq: (a `seq` b) means “when this is forced, force (the outermost layer of) a, then replace yourself with b (which will then be forced as much as necessary)”: replacing f(e) with (let x = e in x `seq` f(x)) everywhere is not quite enough IIRC, but gets you most of the way there. In a dynamically-typed language, you can implement seq using some of the built-in strictness, like a `seq` b = if null(a) then b else b, because null (or any other type discriminator) needs to force the outer layer of its argument (though I’m not sure if you can make this work in bare lambda calculus with functions only, oops); in a statically typed language, a polymorphic seq is AFAIU an unimplementable primitive, but if you need to translate a complete program you should always be able to implement seqT for every type T that occurs in it and use that (and every lazy language has seq anyway). [1] https://srfi.schemers.org/srfi-45/srfi-45.html https://srfi.schemers.org/srfi-45/srfi-45.html [2] https://www.cs.nott.ac.uk/~pszgmh/clairvoyant.pdf https://www.cs.nott.ac.uk/~pszgmh/clairvoyant.pdf, https://youtu.be/S69UOGqda8w https://youtu.be/S69UOGqda8w
  - thesz 4y ago
    They are both Turing complete, they can implement each other. But, the effort to implement call-by-need evaluation (graph rewriting or remembrance of computed value) is higher in strict languages than (sparse) addition of annotations in lazy ones.
- astrange 4y ago
  I'd like to see more use of things that are more powerful than evaluation. For instance, in mathematical functions you can differentiate them, or invert them, and both of those are obviously useful in mathematical "metaprogramming". The only PL example I can think of is unification, which logic programming has as well as evaluation.
  - thesz 4y ago
    https://en.wikipedia.org/wiki/Pure_(programming_language) https://en.wikipedia.org/wiki/Pure_(programming_language) A programming language where you can write programs to rewrite programs. It appears that author of Pure is prone to come up with PL names that are quite unsearchable.
- jose_zap 4y ago
  Haskell is such a language. You can enable strict evaluation on a per module basis, or for an entire package.
  - choeger 4y ago
    Is that a Haskell or GHC feature?
    - mhitza 4y ago
      GHC extensions, StrictData (strict data structures) or Strict (strict evaluation for everything).
    - brewmarche 4y ago
      Without extensions you can do it per-case via `seq`, see https://wiki.haskell.org/Seq https://wiki.haskell.org/Seq (although it might get tricky because you might have to do it repeatedly because it only performs one “level" of evaluation) There is also another GHC extension called bang patterns to request strictness on pattern matches. The original bang (`!`) which is Standard Haskell can make fields of data structures strict, see: https://wiki.haskell.org/Performance/Data_types#Strict_fields https://wiki.haskell.org/Performance/Data_types#Strict_field... In general both lazy and strict languages can be strict or lazy. But the way it shows in the data types is different. A strict language can defer evaluation by adding a level of abstraction (instead of type `X` you have `() -> X`). A lazy language can force evaluation (it will have to evaluate at some point anyway) but you might not see it in the type. I’m not sure which one is better to be honest. Being able to infer laziness/strictness from the type is nice, but it also hinders interoperability.
    - jose_zap 4y ago
      At this point there is not difference between the two of them. GHC is Haskell for all practical purposes
- thesz 4y ago
  Lazy evaluation order can be turned into strict one with less effort than vice versa. Also, your suggestion will result in identical code being copied for different contexts. Consider lazy structures in OCaml and C#.

zozbot234 4y ago

It would be nice to have a language that could treat both strict and lazy evaluation as equally first-class, as opposed to having one be the default (whether "strict" as in ML or "lazy" as in Haskell) and the other only being expressed by syntactical kludges. This may well be possible by relying on logically-inspired features like polarity and focusing, and endowing data types with strict or lazy "natural" polarities.

eatonphil 4y ago
Any strict language can implement laziness. The inverse may(?) not be possible.
- ravi-delia 4y ago
  It's the opposite, no? Basically every lazy language has some way to force evaluation, but in most strict languages laziness is never fully supported. Closest I can think of is a Scheme with continuations, but even then it takes some extra work. I know in CL even primitive laziness takes a lot of work and a code-walker, and whatever it's other flaws Common Lisp is at least adaptable.
  - eatonphil 4y ago
    I could be totally wrong, happy to be corrected. And I'm less familiar with lazy languages. My very basic impression of implementing laziness is just that you wrap all of your data structures/algorithms in functions that must themselves be called. Like everything is an iterator. See also: https://en.wikipedia.org/wiki/Lazy_evaluation#Simulating_laziness_in_eager_languages https://en.wikipedia.org/wiki/Lazy_evaluation#Simulating_laz...
    - mananaysiempre 4y ago
      Wrapping in bare functions gives you “call by name”, where let y = f(x) in g(y, y) will compute f(x) twice. In effect you just evaluate function applications (and lets) by substituting a copy(!) of the argument text for every occurence of the variable in the body. It’s pretty easy for this to get exponentially bad. If you want conventional lazy evaluation, that is “call by need”, you need to memoize: wrap everything in stateful functions (“thunks” in Haskell-implementer-speak, “promises” in Scheme-speak, but not the same as E/JavaScript-style async promises) that compute the result and save it on the first invocation, but then return it immediately. Apart from efficiency considerations (it’s better to use a tagged union of function pointer and result value instead of calling the function all the time) and a single conceptual wrinkle[1], that’s it. Call-by-name and call-by-need obviously yield very different complexity, but are in fact equivalent regarding termination, and optimal: if any evaluation strategy terminates on a given term, so do they. The lovely recent paper “Call-by-need is clairvoyant call-by-value”[2] shows that lazy evaluation in fact never does more steps than call-by-need and in fact does a subset of them: those and only those that influence the final result. (The problem, of course, is that none of this addresses memory usage.) Emulating eager evaluation with lazy can be done if you have seq: (a `seq` b) means “when this is forced, force (the outermost layer of) a, then replace yourself with b (which will then be forced as much as necessary)”: replacing f(e) with (let x = e in x `seq` f(x)) everywhere is not quite enough IIRC, but gets you most of the way there. In a dynamically-typed language, you can implement seq using some of the built-in strictness, like a `seq` b = if null(a) then b else b, because null (or any other type discriminator) needs to force the outer layer of its argument (though I’m not sure if you can make this work in bare lambda calculus with functions only, oops); in a statically typed language, a polymorphic seq is AFAIU an unimplementable primitive, but if you need to translate a complete program you should always be able to implement seqT for every type T that occurs in it and use that (and every lazy language has seq anyway). [1] https://srfi.schemers.org/srfi-45/srfi-45.html https://srfi.schemers.org/srfi-45/srfi-45.html [2] https://www.cs.nott.ac.uk/~pszgmh/clairvoyant.pdf https://www.cs.nott.ac.uk/~pszgmh/clairvoyant.pdf, https://youtu.be/S69UOGqda8w https://youtu.be/S69UOGqda8w
- thesz 4y ago
  They are both Turing complete, they can implement each other. But, the effort to implement call-by-need evaluation (graph rewriting or remembrance of computed value) is higher in strict languages than (sparse) addition of annotations in lazy ones.
astrange 4y ago
I'd like to see more use of things that are more powerful than evaluation. For instance, in mathematical functions you can differentiate them, or invert them, and both of those are obviously useful in mathematical "metaprogramming". The only PL example I can think of is unification, which logic programming has as well as evaluation.
- thesz 4y ago
  https://en.wikipedia.org/wiki/Pure_(programming_language) https://en.wikipedia.org/wiki/Pure_(programming_language) A programming language where you can write programs to rewrite programs. It appears that author of Pure is prone to come up with PL names that are quite unsearchable.
jose_zap 4y ago
Haskell is such a language. You can enable strict evaluation on a per module basis, or for an entire package.
- choeger 4y ago
  Is that a Haskell or GHC feature?
  - mhitza 4y ago
    GHC extensions, StrictData (strict data structures) or Strict (strict evaluation for everything).
  - brewmarche 4y ago
    Without extensions you can do it per-case via `seq`, see https://wiki.haskell.org/Seq https://wiki.haskell.org/Seq (although it might get tricky because you might have to do it repeatedly because it only performs one “level" of evaluation) There is also another GHC extension called bang patterns to request strictness on pattern matches. The original bang (`!`) which is Standard Haskell can make fields of data structures strict, see: https://wiki.haskell.org/Performance/Data_types#Strict_fields https://wiki.haskell.org/Performance/Data_types#Strict_field... In general both lazy and strict languages can be strict or lazy. But the way it shows in the data types is different. A strict language can defer evaluation by adding a level of abstraction (instead of type `X` you have `() -> X`). A lazy language can force evaluation (it will have to evaluate at some point anyway) but you might not see it in the type. I’m not sure which one is better to be honest. Being able to infer laziness/strictness from the type is nice, but it also hinders interoperability.
  - jose_zap 4y ago
    At this point there is not difference between the two of them. GHC is Haskell for all practical purposes
thesz 4y ago
Lazy evaluation order can be turned into strict one with less effort than vice versa. Also, your suggestion will result in identical code being copied for different contexts. Consider lazy structures in OCaml and C#.