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.
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.
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.
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.
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:
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:
("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.")
Yeah, I understand what you mean, sorry if I created confusion. My point is that the claim that it makes it difficult to reason about is misguided in most cases because there is an easy way to estimate the upper bound of any function if you know the upper bounds of the same algorithms in a strict language.
Generally speaking, the complexity of any function has an upper bound equal to the most complex algorithm used. Laziness can bring the upper bound for complexity down, though. The fact that upper bound may be lower is almost certainly not something that you care about in the overwhelming majority of programs. And I haven't found the first person upset to find out that their algorithm performed much better than estimated.
If you have an algorithm with O(n) complexity, it will be the same both for a strict and non-strict language if the whole result is consumed.
When the whole result is not entirely consumed, then the upper bound for a lazy language may be lower.
The classic example, as you linked to is this:
minimum = head . sort
If we consume the entire result of the sort function, then the upper bound is O(Nlog(N)). Because of laziness, using head makes the minimum function O(N)
The implementor chose to compose those two functions because laziness makes this possible. If you are in the business of reviewing core code to evaluate their complexity, you are right. It is difficult to nail down get the more accurate upper bound, but that does not mean you cannot guess what a less accurate estimate would be. I would have guessed O(Nlog(N)) the first time for a minimum, and would have been pleasantly surprised that laziness makes that faster.
When has reasoning about time complexity been difficult for you in a lazy language?
I misspoke in my last comment when I referred to space and time complexity. The usual problem in the field isn't figuring out the big O characteristics, it's unpredictable performance due to evaluation of an expression building up a huge chain of thunks. Because of the inherently non-local logic of lazy evaluation (or, whatever evaluation strategy compatible with non-strict semantics that GHC actually chooses to use), it is not always easy to find which piece of code is introducing unwanted laziness.
That said, it's the same fundamental non-locality that also makes it more difficult to figure out the big O complexity of an algorithm implemented in a non-strict language.
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.
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.
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.
Nah, you really don’t. The only notable difference would be in stackless Python, and since for all practical purposes only CPython and PyPy matter for widely discussing Python usage on applied problems, it can be safely omitted.
You really do. "Generators" are APIs, their implementations may vary, even across different CPython versions, and Stackless is not the only implementation (yet a significant one) that you should consider when talking about the differences in memory footprint. Numba, Cython, Nuitka, and a few other more exotic compilers all have their own implementations of compiled generators, and some of them allocate the required tracking structure quite compactly on the stack [1].
But let's say I agree with you. To make the case demonstrably true, I'd like to see the context where a total volume of generator instantiations becomes less efficient than all possible list/tuple allocations with their contained data. Do you mind sharing your stats? What kind of codebase is it? I'd like to understand the layout of it and to draw my own conclusion on whether the mentioned veteran code is sane.
Hey, I actually used to work on the numba compiler team at Continuum. I can say I don’t understand the last rant paragraph at all or why you think it’s related to my point about generators.
> I can say I don’t understand the last rant paragraph at all or why you think it’s related to my point about generators.
This is not a rant, you made a claim about generators' allocations inefficiencies compared to physical list() and tuple() allocations, I'd like to see the case where it's true.
It is true in many many cases. For a very simple illustration consider
def f():
x = list(range(10000))
yield from x
vs
list(range(10000))
The former includes the overhead of memory for both the materialized list and function execution frames.
The same thing happens when people naively split up generators that hold onto a lot of data, for example (this comes from real life experience where someone wanted to essentially “memoize with generators” a membership check on the response from a database call).
def check_expensive_in():
s = large_db_call()
while True:
x = yield
yield x in s
def expensive_filter():
f = check_expensive_in()
next(f)
def helper(item):
v = f.send(item)
f.next()
return v
while True:
items = yield
for item in items:
yield helper(item)
yield None
e = expensive_filter()
next(e)
e.send(some_list)
# iterate e until None.
(Sorry for any typos or minor glitches with send(), I am writing this on my phone as I eat breakfast.)
It’s a very simple issue, which is that memoizing with generators maintains the memory footprint of the memoized data _and_ additional memory footprint of the generator (and also of large sent values into the generator too, but this is less common).
It’s better to just materialize the things you need in memory and reuse them in regular function calls, which don’t have fixed permanent overhead for a long lifetime like generators.
This can absolutely happen with small data examples too, where generators are less efficient than just materializing everything, but normally nobody cares because with small data, the effect of any inefficiency won’t be noticed.
Even in that case though, generators often lead to spaghetti code like my example above, because depending on laziness as you compose multiple functions is just a poor conceptual way to organize code. Very rarely, but sometimes, it’s worth it to avoid memory bottlenecks or to do stream processing. But it’s overstated how often this matters generally - it’s very rare unless you’re in a specialized domain where that’s all do.
Lastly I’d like to say that your tone comes across as needlessly antagonistic and it seems extremely obvious you are engaging in bad faith. You don’t seem open to consider what I am saying, rather in a rush to demand some kind of “proof” with no willingness to think through it, and likely not seeking proof to learn anything but just to try to create shallow, undermining retorts.
I won’t be continuing to check back here or engage any further with you. If you want the last word in the thread, take it.
> You don’t seem open to consider what I am saying, rather in a rush to demand some kind of “proof” with no willingness to think through it
it doesn't work this way, if you state something to be true, the burden of proof lies on your shoulders and I am open to consider the proof, and not just words alone.
It's funny that this subthread was started with a statement that my example of complexity estimation difficulties was deeply contrived, yet the examples for a proof of generators' inefficiences materialize all intermediate values into lists. Why would I want to materialize a list to yield something from it later, if I can just pass the range() stream to the caller instead?
Your second example is an exemplary code smell, as there's no need for a helper() closure. And there's no need to hold resources for check_expensive_in(), as most of DBs have lazy query cursor implementations in one way or the other. Afterall, it's not about doing everything in one expensive DB call and laziness doesn't negate buffered data, it just says that there's an explicit boundary on internal buffers within a single iteration, and every single iteration may perform a separate but less expensive DB call.
In lazy-by-default languages I can at least rely on normal evaluation order.