I think what bjoli is getting at is that in an ideal world with lazy sequences you don't have any iteration over any of the intermediate "collections" until some step occurs that requires the entire collection. I put collections in quotes because they aren't really collections, they're generators that produce an element on demand.
So you never really iterate over more than one collection; you only have one iteration where you successively ask each generator to produce a single element and then apply a function to it. For example, if you only asked for the first element of a lazy sequence formed by a series of maps, you would (in theory, in practice see my note about chunks) never iterate over any of the intermediate sequences and only ever examine the first element of each of them.
However, the act of asking a generator to produce an element (that is unwrapping a thunk) has overhead of its own and that's the overhead that a transducer would be removing (not iteration itself in the case of lazy sequences). This can have far more overhead than a procedure call because of bad cache locality (in the absence of fusion optimizations you're pointer chasing and potentially generating garbage for each thunk). Clojure tries to get around that by often (but not always) chunking its thunks, in which case we do have multiple rounds of iteration on smaller chunks, but never the entire sequence (unless the entire sequence is smaller than a chunk).
What I am saying is that lazy sequences in my world should mean you don't have to realize any intermediate collections. In the case of the srfi-158 generator (gmap square (gfilter odd? (list-generator big-list))) the overhead for getting one element from the generator would be 3 procedure calls. Without any intermediate steps. The same transducer would have one procedure call less, but would be in the same vicinity.
Does clojure's sequences not work similarly? That seems like a very lax definiti
I stand by what I said (even though I am partial to transducers): there is no reason for lazy sequences overhead to be much more than a procedure call, which is exactly what a step in the reduction in the case of transducers is. At least when implemented as in clojure or srfi-171.
I understand that there might be some overhead to creating new sequence objects, but removing intermediate sequence object creation should be simple, at least for built in map-filter-take-et-al.
Edit: I seem to be wrong. People are recommending transducers over clojure's lazy map-filter-take-et-al because of overhead, which to me seems off, but there might be something about clojure's lazy sequences that I haven't grooked.
This article is somewhat puzzling for me. On one hand, the OP clearly knows Clojure very well. The disadvantages of laziness are real and well described.
On the other hand, though, this sounds like a theoretical/academic article to me. I've been using Clojure for 15 years now, 8 of those developing and maintaining a large complex SaaS app. I've also used Clojure for data science, working with large datasets. The disadvantages described in the article bothered me in the first 2 years or so, and never afterwards.
Laziness does not bother me, because I very rarely pass lazy sequences around. The key here is to use transducers: that lets you write composable and reusable transformations that do not care about the kind of sequence they work with. Using transducers also forces you to explicitly realize the entire resulting sequence (note that this does not imply that you will realize the entire source sequence!), thus limiting the scope of lazy sequences and avoiding a whole set of potential pitfalls (with dynamic binding, for example), and providing fantastic performance.
I do like laziness, because when I need it, it's there. And when you need it, you are really happy that it's there.
In other words, it's something I don't think much about anymore, and it doesn't inconvenience me in any noticeable way. That's why I find the article puzzling.
TIL that the Clojure rationale doesn't mention or motivate lazy sequences which are all over the place in Clojure.
That laziness (in collection APIs, duh) was a major reason that I stopped using the language more after 1 or 2 years of toying around. Maybe that concept was too foreign for me, but objectively lazy seqs don't compose with other language features like dynamic scoping.
Yet I'm happy I tried it, learned a bunch of stuff along the way.
I think the main issue with lazy sequences is understanding and controlling their scope. Transducers, particularly when utilized within an `into` scope, can encapsulate laziness very neatly. Indeed, transducers utilize lazy sequences internally, and the OP shows their clear performance advantage. I think the article would be more effective if it shifted tone to "Clojure laziness best practices" rather than damning the idea wholesale. There be dragons for sure.
Some times in clojure I've found it easier to express a sequence recursively, rather than iteratively. Using lazy-seq is not only braindead simple for this - just wrap the whole function in it, it is the only way to keep your stack use from growing on the recursive calls. I haven't compared the performance of this to eager evaluation but I'd guess it isn't that poor.
I can't speak about Haskell, but Clojure's lazy sequences also generate a lot of intermediate allocs.
For example, here's Clojure's implementation of `map`[1]. It internally uses `cons` to build a cell[2] and `map` to recursively walk the collection (but all wrapped up in `lazy-seq` to delay evaluation).
Transducers[3] do help with this if you are applying a stack of collection transformations. But, and this is just my opinion as a very occasional Clojure user, transducers are harder for me to grok and so I generally avoid using them. If I was doing performance critical work, I might try to build up a better mental model.
My biggest complaint about the Java streams API is that it makes it hard to write your own stream transformation functions. Or rather, you can, but then calling them is awkward. You generally transform a Stream by calling instance methods - e.g. `myStream.map(::f)`. But since Java doesn't have extension functions, there's no way for you to make a custom function callable in the same way as the built-in functions. I ended up writing a small shim to build a stream pipeline without using member functions. You would use it something like this:
Clojure's normal transducerless lazy sequences are fine for early-terminating sequences.. mostly. They're fine as long as you are ok with realizing up to 31 extra items.
> Laziness does not bother me, because I very rarely pass lazy sequences around.
Sounds like that is going to the point the article is making - the best way to use lazy sequences is not to. Lazy sequence bugs make for a miserable experience. Clojure already has an onboarding problem where every new learner has to discover all the obscure do- and don't-s and go through the lessons of which parts of the language are more of a gimmick vs the parts that do real work. Attempting to do tricks with lazy sequences is part of that but it is polite to warn people before they try rather than when they get to Stack Overflow after hours of head-to-desk work.
Although I will put in a small plug for lazy sequences because they work well in high latency, high data i/o bound situations like paged HTTP calls or reading DB collections from disk. When memory gets tight it can be helpful to be processing partially realized sequences. But the (map println [1 2 3]) experience that everyone has is a big price to pay.
> They can be useful for certain constructions, but they don’t really enable anything amazing that you can’t do otherwise, just with a slightly different algorithm.
One really nice property of laziness is dealing with data larger than RAM. A couple of months ago I wrote some ML processing of the wikipedia XML in Clojure. In about 5 lines, I had a lazy sequence of every <Article> tag from the XML. Then I can (map my-fn all-articles-from-wikipedia), without blowing the heap (the wikipedia XML was like ~10GB, zipped).
Yes, it's possible to do non-lazy, but this was cleaner and simpler.
One algorithmic advantage of lazy seqs is that (map foo (map bar (map baz my-big-seq))) makes only one pass over the data, as opposed to 3 when non-lazy.
Laziness can actually make things faster in some scenarios. Take Python2's range() function for instance, which eagerly builds the entire list and returns it. range() is commonly used for for loops, so Python builds this list (an N operation) and returns it, and then the for loop iterates over it (another N operation). But if you use xrange(), you get a generator instead, which can lazily construct values when asked for one. It turns the for loop case into a single N operation. Similarly if you have nested function call chains, if everything is returning an eagerly evaluated list, you have to construct the whole list in memory at each call and pass it to the next stage which will eagerly iterate over the whole thing to generate its list in memory and so forth, eventually the old list can be freed / GC'd when the new list has been made.. but with lazy sequences, you only need memory for the whole list at the very end, if you want it and not just individual values. Python3's range() replaced Python2's with xrange(). (The other option is a numpy-like approach where you eagerly allocate the list and then every stage just mutates that single thing.)
The 'memory stays around indefinitely' problem is caused by not cleaning up references to generators. You can make your own xrange() clone in Python easily, and start consuming values, but if you stop before consuming all of them (assuming it's not an infinite generator), that xrange() generator object still lives and has to keep around whatever references it needs to generate the next value if you ask it for one. When your whole language is based around laziness, you might have a lot of these and it may not be clear what references are still around that keep the GC from cleaning them up.
I wouldn't say reasoning about performance is necessarily more difficult, and profiling will light up a slow part of a lazy pipeline just as well as an eager one. My own struggles with laziness in Clojure were all around my own confusions about "I thought this sequence was going to be evaluated, but it wasn't!" which may have led to unnecessary calls to (doall), which forcibly walks a sequence and puts the whole thing in memory.
In Haskell this goes even deeper because the lazy evaluation strategy allows the compiler to optimize the order of evaluation of the expressions within a function and create thunks without you explicitly telling it to. Haskell needs to be pure in order to be lazy, because if it were impure it would be very difficult to reason about if, when, and in what order, the side effecting operations will take place. So like you said, if a side-effectful expression evaluates to nothing, its return value is not "needed" in a further computation, therefore it may not be evaluated at all.
This doesn't really apply to Clojure because Clojure is strictly evaluated--except when you're explicitly working with a lazy stream data structure. If you were to put side-effectful expressions inside of a lazy stream, you would have a hard time controlling when they are evaluated, especially since Clojure "chunks" lazy streams by default in groups of 32 as an optimization.
Here's a SO question demonstrating what happens when you mix laziness and side-effects and don't understand the implications--you find yourself trying to restrict the optimizations you allow the compiler to do (which will hurt performance): http://stackoverflow.com/questions/3407876/how-do-i-avoid-cl...
It’s too bad that transducers were created long after clojure’s inception. Can you always replace a lazy seq with a transducer? Could the language theoretically be redesigned to replace all default usages of lazy seqs with transducers, even if it were a major breaking change? And have lazy operations be very explicit?
if you use Clojures primitives you pretty much end up with laziness by default. for, map and most of the other list processing functions all return lazy lists. So while Clojure does technically require you to "turn on" laziness in most cases you'll find it's turned on already.
> But in Swift, C++, Common Lisp, OCaml, Python, Ruby, Perl, Java, Scheme, and many others, adding another map/filter/etc. will add another pass through the sequence unless you're going out of the way to avoid it.
I think this is wrong in the case of Python -- map/filter/reduce are lazy, and so chaining them does not result in multiple iterations of the source sequence.
In Ruby, its definitely sometimes wrong, because whether or not iteration is lazy depends on the particular Enumerable object; and, in the worst case, in Ruby, you don't have to go very far out of your way. In the event that the Enumerable you are operating on isn't already a lazy one, you just call its lazy method, and chain your operations after that.
So you never really iterate over more than one collection; you only have one iteration where you successively ask each generator to produce a single element and then apply a function to it. For example, if you only asked for the first element of a lazy sequence formed by a series of maps, you would (in theory, in practice see my note about chunks) never iterate over any of the intermediate sequences and only ever examine the first element of each of them.
However, the act of asking a generator to produce an element (that is unwrapping a thunk) has overhead of its own and that's the overhead that a transducer would be removing (not iteration itself in the case of lazy sequences). This can have far more overhead than a procedure call because of bad cache locality (in the absence of fusion optimizations you're pointer chasing and potentially generating garbage for each thunk). Clojure tries to get around that by often (but not always) chunking its thunks, in which case we do have multiple rounds of iteration on smaller chunks, but never the entire sequence (unless the entire sequence is smaller than a chunk).
reply