6 ms·

> If I could suggest just one, it would be lazy evaluation by default, which makes it exceedingly hard to reason about time and space complexity In what scenar

> If I could suggest just one, it would be lazy evaluation by default, which makes it exceedingly hard to reason about time and space complexity In what scenarios does it make hard to reason about those complexities? I find GHCs profiler statistics clear and meaningful[1], I lack the efficiency of its reports in other environments I work with, namely Python. [1] https://downloads.haskell.org/~ghc/latest/docs/html/users_guide/profiling.html https://downloads.haskell.org/~ghc/latest/docs/html/users_gu...

runeks 6y ago
> In what scenarios does it make hard to reason about those complexities? I’m guessing OP is referring to reasoning about time/space usage by reading code, rather than by running the program.
- ghostwriter 6y ago
  This is not trivial in strict languages either, because implementation details of a particular language/library dictate the rules. For instance: l = list(range(N)) for _ in range(M): x = list(l) CPython will have MxN iterations (allocations?), whereas other languages/libraries where data is immutable may decide to optimise the list() constructor and return a reference to the same object when the input is an instance of a list. In lazy-by-default languages I can at least rely on normal evaluation order.
  - foldr 6y ago
    Of course you need to know the semantics of the programming language you're using. The point is that lazy evaluation introduces additional complexity on top of that.
    - ghostwriter 6y ago
      the point is that it's not semantics of a language alone, it's the semantics of the language + the libraries + the data constructors + the flow order. Lazy evaluation doesn't introduce additional complexity on top of that for no good reason, it actually trades a few of these complexities for one additional abstraction that lets you think about your programs in terms of data flows and transformations (instead of allocation semantics at every individual step), where program boundaries define the actual computations to perform and the complexity of the final algorithm. It's an extremely powerful tool and the complexity is justified.
      - foldr 6y ago
        The additional complexity may or may not be justified; the point is that it exists.
        ghostwriter 6y ago
        for some reason you specifically ignore that it's not a complexity on top, but rather a trade-in.
        foldr 6y ago
        That's irrelevant. OP simply said that lazy evaluation makes it harder to reason about time and space complexity. Everyone agrees with this, for goodness sake - even SPJ himself.
        ghostwriter 6y ago
        > Everyone agrees with this, for goodness sake - even SPJ himself oh, then I definitely should stop thinking on my own about the things that I practice on a daily basis.
        jose_zap 6y ago
        It is definitely not harder to reason about time. I don’t think you will find many haskellers agreeing with this.
        foldr 6y ago
        Lazy evaluation makes it difficult to figure out when expressions are evaluated, which is relevant to both space and time complexity. To take an trivial example, whether or not your infinite list is (completely) evaluated could be the difference between your program running in constant time or not terminating at all! Here is a good Stackoverflow response that expands on the point: https://stackoverflow.com/a/12061524 https://stackoverflow.com/a/12061524 I've never before seen the claim that lazy evaluation makes it harder to reason about space but not time complexity. It seems a very odd claim on the face of it, since the two are very closely interrelated. (E.g., if you are evaluating some prefix of an infinite list, then space and time are exactly correlated.) But if that doesn't satisfy you, here is a paper that explains why time analysis is more difficult for lazy evaluation: https://link.springer.com/content/pdf/10.1007%2F3-540-52592-0_74.pdf https://link.springer.com/content/pdf/10.1007%2F3-540-52592-... ("A major obstacle in the time-analysis of lazy languages is the problem of context sensitivity: the cost of evaluating an expression depends on the context in which it is used.")
  - mlthoughts2018 6y ago
    That example seems deeply contrived. I wouldn’t call that an “optimization” at all, since if you’re returning a reference, then mutating x will mutate the underlying original list, which is precisely not what the user requested by using specifically the list() constructor. If they wanted a reference they can just do x = l. This is not at all any kind of similar critique like the issues with reasoning about lazy evaluation from reading Haskell source.
    - ghostwriter 6y ago
      that's why I mentioned "other languages/libraries where data is immutable". Replace a constructor for list() with a constructor for graph() from a random library. You won't be able to estimate the complexity of it just by reading the client code, you need to know implementation details. In Python world, list() may be called to explicitly guarantee an expected shape of a value in runtime. I see it regularly, when various functions call list(iterable) on their input data internally, just to be able to list.append() later on, even though there's itertools.chain() for the same purpose, which is lazy by the way.
      - mlthoughts2018 6y ago
        I think you are missing a lot of details about when it is wise vs. unwise to rely on generators and coroutines in Python for lazy evaluation. Some of the most common mistakes I see Python beginners make are using list or tuple when they could use a generator instead. Rarely it leads to serious memory consumption issues, more often it just leads to messy list-append-copy style code, which is very forgivable. Some of the most common mistakes I see intermediate Python programmers make involve overuse of generators and lazy evaluation in situations where eager evaluation simplifies the code or is needed for other reasons. This class of mistakes is a lot worse than the beginners’ mistakes, because you end up baking a reliance on handling generators deep in the code, often in places you don’t want it. People will cut off their nose to spite their own face, e.g. convert a simple list comprehension into a series of chained helper functions that all use yield to behave as generators, not realizing the memory footprint of this can be far, far worse than just materializing the whole list in memory, depending on the situation. Often in veteran code, you see a lot of calls to list() specifically to remove propagation of bad generators, and ensure a certain function acts as a bottleneck on that type of behavior by design.

runeks 6y ago

> In what scenarios does it make hard to reason about those complexities? I’m guessing OP is referring to reasoning about time/space usage by reading code, rather than by running the program.

ghostwriter 6y ago
This is not trivial in strict languages either, because implementation details of a particular language/library dictate the rules. For instance: l = list(range(N)) for _ in range(M): x = list(l) CPython will have MxN iterations (allocations?), whereas other languages/libraries where data is immutable may decide to optimise the list() constructor and return a reference to the same object when the input is an instance of a list. In lazy-by-default languages I can at least rely on normal evaluation order.
- foldr 6y ago
  Of course you need to know the semantics of the programming language you're using. The point is that lazy evaluation introduces additional complexity on top of that.
  - ghostwriter 6y ago
    the point is that it's not semantics of a language alone, it's the semantics of the language + the libraries + the data constructors + the flow order. Lazy evaluation doesn't introduce additional complexity on top of that for no good reason, it actually trades a few of these complexities for one additional abstraction that lets you think about your programs in terms of data flows and transformations (instead of allocation semantics at every individual step), where program boundaries define the actual computations to perform and the complexity of the final algorithm. It's an extremely powerful tool and the complexity is justified.
    - foldr 6y ago
      The additional complexity may or may not be justified; the point is that it exists.
      - ghostwriter 6y ago
        for some reason you specifically ignore that it's not a complexity on top, but rather a trade-in.
        foldr 6y ago
        That's irrelevant. OP simply said that lazy evaluation makes it harder to reason about time and space complexity. Everyone agrees with this, for goodness sake - even SPJ himself.
        ghostwriter 6y ago
        > Everyone agrees with this, for goodness sake - even SPJ himself oh, then I definitely should stop thinking on my own about the things that I practice on a daily basis.
        jose_zap 6y ago
        It is definitely not harder to reason about time. I don’t think you will find many haskellers agreeing with this.
        foldr 6y ago
        Lazy evaluation makes it difficult to figure out when expressions are evaluated, which is relevant to both space and time complexity. To take an trivial example, whether or not your infinite list is (completely) evaluated could be the difference between your program running in constant time or not terminating at all! Here is a good Stackoverflow response that expands on the point: https://stackoverflow.com/a/12061524 https://stackoverflow.com/a/12061524 I've never before seen the claim that lazy evaluation makes it harder to reason about space but not time complexity. It seems a very odd claim on the face of it, since the two are very closely interrelated. (E.g., if you are evaluating some prefix of an infinite list, then space and time are exactly correlated.) But if that doesn't satisfy you, here is a paper that explains why time analysis is more difficult for lazy evaluation: https://link.springer.com/content/pdf/10.1007%2F3-540-52592-0_74.pdf https://link.springer.com/content/pdf/10.1007%2F3-540-52592-... ("A major obstacle in the time-analysis of lazy languages is the problem of context sensitivity: the cost of evaluating an expression depends on the context in which it is used.")
- mlthoughts2018 6y ago
  That example seems deeply contrived. I wouldn’t call that an “optimization” at all, since if you’re returning a reference, then mutating x will mutate the underlying original list, which is precisely not what the user requested by using specifically the list() constructor. If they wanted a reference they can just do x = l. This is not at all any kind of similar critique like the issues with reasoning about lazy evaluation from reading Haskell source.
  - ghostwriter 6y ago
    that's why I mentioned "other languages/libraries where data is immutable". Replace a constructor for list() with a constructor for graph() from a random library. You won't be able to estimate the complexity of it just by reading the client code, you need to know implementation details. In Python world, list() may be called to explicitly guarantee an expected shape of a value in runtime. I see it regularly, when various functions call list(iterable) on their input data internally, just to be able to list.append() later on, even though there's itertools.chain() for the same purpose, which is lazy by the way.
    - mlthoughts2018 6y ago
      I think you are missing a lot of details about when it is wise vs. unwise to rely on generators and coroutines in Python for lazy evaluation. Some of the most common mistakes I see Python beginners make are using list or tuple when they could use a generator instead. Rarely it leads to serious memory consumption issues, more often it just leads to messy list-append-copy style code, which is very forgivable. Some of the most common mistakes I see intermediate Python programmers make involve overuse of generators and lazy evaluation in situations where eager evaluation simplifies the code or is needed for other reasons. This class of mistakes is a lot worse than the beginners’ mistakes, because you end up baking a reliance on handling generators deep in the code, often in places you don’t want it. People will cut off their nose to spite their own face, e.g. convert a simple list comprehension into a series of chained helper functions that all use yield to behave as generators, not realizing the memory footprint of this can be far, far worse than just materializing the whole list in memory, depending on the situation. Often in veteran code, you see a lot of calls to list() specifically to remove propagation of bad generators, and ensure a certain function acts as a bottleneck on that type of behavior by design.