Clojure blog post about laziness
Mark Engelberg
some of the "gotchas" related to Clojure's laziness. He encouraged me
to blog about my thoughts on the matter.
On a related note, about a month ago, I posted comments about
Clojure's laziness. Rich's response was:
"The argument you've made, however, is theoretical.
I've tried what you said. In fact, it's sitting there in the
implementation right now - just uncomment lazy-seq. cached-seq is
there, as is a non-caching LazySeq class implementing ISeq, and all of
the library functions can be defined in terms of it. I also did that,
and then tried it and some common code.
You should too, and report back your actual experience."
So my blog post has a dual purpose. First, I explain the "gotcha"
that Stuart and I discussed. Second, I report back to the community
about the actual experience I had in the past month, exploring
laziness in Clojure. I decided to blog it rather than post it here
primarily due to its length.
If you're at all interested in laziness, check it out:
http://programming-puzzler.blogspot.com/
Konrad Hinsen
> So my blog post has a dual purpose. First, I explain the "gotcha"
> that Stuart and I discussed. Second, I report back to the community
> about the actual experience I had in the past month, exploring
> laziness in Clojure. I decided to blog it rather than post it here
> primarily due to its length.
An interesting analysis. Looking my own applications, I tend to agree
with your observations, but then I also have a similar code base as
you have: almost all of it is purely functional code using Clojure's
basic data structures.
I also agree with your conclusion that the critical point is lazy
sequences whose constructors are not referentially transparent. I
wonder if there is any way to have them detected reliably (at compile
time or at run time), but I expect this can't be done. Another
solution would be to detect lazy sequences guaranteed to be purely
functional because of the exclusive use of safe functions, and make
them uncached by default. That should be doable but perhaps with an
unreasonable effort or a high runtime penalty.
Konrad.
Rich Hickey
No more, no less. It is inherently a persistent abstraction. When you
ask for the nth element/rest, you get the identical item every time.
All laziness adds is the fact that rest might not exist until you ask
for it. Once you do, it's a Lisp list. It doesn't matter whether it
originally came from an ephemeral source or a long-running calculation
or whatever. The claim "So the amazing thing is that whether you
choose to build a cached or uncached sequence, it makes not one bit of
difference to the consumers of your sequence" is simply untrue. The
promise of the abstraction is not merely that the nth item/rest will
be equal - it is that it will be identical. I.e. a seq is persistent
and immutable. There's nothing wrong with Lisp's list abstraction nor
its realization as seqs in Clojure.
Making seqs 'non-caching' makes no sense because they are no longer
the same abstraction. Lazy != ephemeral. Seqs and streams are
different abstractions.
The questions really are, is there room for additional, ephemeral,
abstraction - streams, and can filter/map et al be freed from working
only with the seq abstraction. I've said yes to both of these and have
a working solution that supports transparent interoperation of seqs
and streams, thread safety, and single-source algorithm definition for
both uses. It is not based on non-caching seqs.
I've been holding off on integrating this as it is a fairly
substantial change (under the hood, no change at all for consumers),
introduces a new abstraction (though no impact until you use it), and
might delay 1.0.
Do people want it now?
Rich
Konrad Hinsen
> difference to the consumers of your sequence" is simply untrue. The
> promise of the abstraction is not merely that the nth item/rest will
> be equal - it is that it will be identical. I.e. a seq is persistent
> and immutable. There's nothing wrong with Lisp's list abstraction nor
> its realization as seqs in Clojure.
>
> Making seqs 'non-caching' makes no sense because they are no longer
> the same abstraction. Lazy != ephemeral. Seqs and streams are
> different abstractions.
That makes sense, but I am probably not the only one who has used
lazy sequences to implement streams. It's the closest abstraction
currently available in Clojure.
> I've been holding off on integrating this as it is a fairly
> substantial change (under the hood, no change at all for consumers),
> introduces a new abstraction (though no impact until you use it), and
> might delay 1.0.
>
> Do people want it now?
I'd use it right away in a few places in my code, so for me the
answer is yes. On the other hand, lazy sequences work pretty well for
me as well at the moment. Perhaps the better question is how
important it is to get a version 1.0 out rapidly. Personally I don't
care at all, but I can understand those who do.
Konrad.
Matt Revelle
wait until 1.1.
>
>
> Rich
>
> >
MikeM
>
> Do people want it now?
>
1.0.
chris
forwarded it to a lot of people; I hope you don't mind!
As far as caching goes:
I think, regardless of the theoretical considerations of = that
caching a lot of objects is ridiculous from a performance
perspective. Access to ram takes a long, long time from the CPU's
perspective and on-chip caches are never that big. In a world with
lots of processing power and not that much bandwidth (not to mention
the overhead of garbage collection and various other things) I never
cache anything until I know it will provide a distinct benefit. I
have to break newer programmers of that habit all the time (I work
currently on 3d graphics on NVIDIA's Tegra platform).
Furthermore, moving to Andriod platforms means you are dealing with a
platform that is always going to be bandwidth and resource constrained
as far as ram goes. The tradeoffs here are harder to make and require
more research, but generally trying to compute things instead of store
them will get you a lot farther especially with regards to the anemic
on-chip cache that most ARM processors have.
So clearly, for my applications I will be using the stream abstraction
unless I have a reason to use the truly lazy (I wouldn't consider a
non-caching approach truly lazy) approach. I am not criticizing the
decision to be correct first and performant later, but I think that
streams fit what I do much better than lazy seqs. I agree with Mark's
assessment that the vast majority of the sequences in his program are
either only used once or so cheap to create that caching is
pointless. This matches my world that has an update-render loop where
a lot of the information just doesn't matter after the rendering
engine gets to it.
Chris
On Jan 8, 8:09 am, Matt Revelle <mreve...@gmail.com> wrote:
Mark Engelberg
> The
> promise of the abstraction is not merely that the nth item/rest will
> be equal - it is that it will be identical. I.e. a seq is persistent
> and immutable.
I get that Clojure is making a promise of identity here, which is not
possible if things uncached. But I look at this from a pragmatic
standpoint and wonder how much people are relying on that promise? I
notice that I haven't written any code that uses identical? And if I
did, I don't think I'd mind the overhead of explicitly wrapping the
sequence in a call to cache-seq. If people don't need this promise as
a rule, maybe it's okay to rethink the abstraction, and start thinking
of it as just a way to get the "first" and "rest" of a bunch of items,
possibly generated by need, and with no other promises implied.
As to your question, I'd vote for streams now. As you can tell from
my posts, my own code centers around generating long sequences of
things, and the current seq abstraction is just not quite the right
fit. I'd really like to get my hands on streams and see whether they
work better for my needs.
Rich Hickey
On Jan 8, 2009, at 1:06 PM, Mark Engelberg wrote:
>
> On Thu, Jan 8, 2009 at 5:55 AM, Rich Hickey <richh...@gmail.com>
> wrote:
>> The
>> promise of the abstraction is not merely that the nth item/rest will
>> be equal - it is that it will be identical. I.e. a seq is persistent
>> and immutable.
>
> I get that Clojure is making a promise of identity here, which is not
> possible if things uncached. But I look at this from a pragmatic
> standpoint and wonder how much people are relying on that promise? I
> notice that I haven't written any code that uses identical? And if I
> did, I don't think I'd mind the overhead of explicitly wrapping the
> sequence in a call to cache-seq. If people don't need this promise as
> a rule, maybe it's okay to rethink the abstraction, and start thinking
> of it as just a way to get the "first" and "rest" of a bunch of items,
> possibly generated by need, and with no other promises implied.
I think the real test of non-cached seqs is to swap them in for
regular seqs, rebuild Clojure and some user libs and see what breaks
and why. Then you'll see the dependencies on caching that exist in the
real world. Your purely functional code might not care, other than
perf, but that is not the only user base Clojure and I need to support.
Rich
Mark Engelberg
> On Thu, Jan 8, 2009 at 5:55 AM, Rich Hickey <richh...@gmail.com>
> regular seqs, rebuild Clojure and some user libs and see what breaks
> and why. Then you'll see the dependencies on caching that exist in the
> real world. Your purely functional code might not care, other than
> perf, but that is not the only user base Clojure and I need to support.
>
> Rich
I tried to do that, swapping lazy-cons in core.clj to use the
commented out code from the lazy-seq macro, but I couldn't get Clojure
to build. Clearly something in the bootstrapping code relied on
lazy-cons working exactly the way it works. So yes, it is clear that
there are currently some dependencies on lazy-cons being cached. What
is less clear is whether those depedencies can be easily isolated and
rewritten to explicitly use a separate caching version of lazy-cons,
leaving the rest of the codebase free to use an uncached variation of
lazy-cons by default. I didn't understand the code well enough to
find the conflict that was preventing the code from building, so I
ended up separating out the uncached variations as a separate library
so I could at least experiment within my own code. But I agree that
rebuilding Clojure in this way would be very enlightening. Maybe I'll
take another stab at it...
kkw
workplace constraints.
Kev
Stuart Halloway
add them.
Stuart
Mark Engelberg
> When you
> ask for the nth element/rest, you get the identical item every time.
I know this is nitpicking, but if this is really the promise that the
seq abstraction is supposed to fulfill, then Clojure already violates
this:
(def a (seq [1 2 3]))
(identical? (rest a) (rest a)) yields false
Presumably what you mean is that the nth element should be identical
(but not necessarily the nth rest).
> The sequence abstraction in Clojure is the list abstraction of Lisp.
> No more, no less.
Well, in Lisp, lists are concrete, finite things that are mutable (and
therefore don't provide any kind of guarantee that you'll get the same
element with multiple traversals). So to say that Clojure's sequence
abstraction is no more and no less than the list abstraction of Lisp
is a bit misleading. You have a certain concept of what properties of
this abstraction you want to model, and what promises you want to
keep. And that's great -- honestly, I think it's fantastic that you
have such a clear, coherent design vision that you've maintained
throughout the creation of Clojure. I'm just saying that your
interpretation of what constitutes an abstraction of a Lisp list is
more subjective than your statement implies.
I'm pretty sure my concept of the list abstraction differs from yours.
In my mind the essential abstract concept of a list is anything that
can be explained in this way:
A list has a first and a rest, where first is some kind of element,
and rest is another list or nil.
In other words, I would say a sequence abstraction should apply to
anything that has this sort of nested, self-referential recursive
structure.
There is an elegance to the way that algorithms on self-referential
data structures can be expressed via recursion. To me, a big part of
Clojure's beauty lies in the recognition that so many things can be
converted to this view. Strictly speaking, a vector is not structured
in this way, but you can convert it into something that has this
property, allowing you to program vectors with this sort of recursive
elegance.
When I think about something like the sequence of whole numbers, it
seems like a perfect embodiment of what I consider to be the essential
abstraction of a sequence. You've got a first thing, and the rest
thing is another sequence that has similarity to the original.
Because it has a recursive structure, I want to be able to operate on
it using first and rest. To me, a sequence feels like the "right
abstraction" for the whole numbers, and writing algorithms that
operate on them. And this feels like the right abstraction to me
regardless of implementation details such as whether the traversed
numbers should reside in memory all at once.
> Making seqs 'non-caching' makes no sense because they are no longer
> the same abstraction.
I get that your design vision revolves around the idea that sequences
promise identity, and that there are real technical challenges
surrounding the idea of non-cached sequences. But I don't consider
"non-caching sequences" to be an oxymoron. If it were possible to
implement them in a way that meshed with the rest of Clojure's design,
I think there would be real value to being able to manipulate
non-cached recursive structures with the existing sequence interface.
It's clear you don't think this fits with Clojure's design, but I
haven't yet given up hope of finding a clever way to do this, and
trying to convince you that it is worthwhile :) .
I know that over email, it is all too common for the tone of a post to
be misconstrued. So just in case, I want to emphasize here that these
posts are in no way intended as bashing Clojure or Rich's design
sensibilities. It is precisely because I admire the design, and
already care about Clojure, that I raise these points in the hope that
community discussion can elevate the language even further. I strive
to make my comments as constructive in tone as possible, and I hope
that they are perceived in that light.
Mark Engelberg
If cycle, repeat, and replicate were implemented behind-the-scenes
with LazySeq as opposed to LazyCons, they would still implement the
promise of identical elements for separate traversals, but would be
more efficient. Also, range always returns a sequence of numbers
which are inherently identical when equal, so that would be another
one that makes sense as a LazySeq. There are probably a few more that
could also guarantee identity and would benefit from a LazySeq
implementation (take, takewhile, and butlast come to mind). Is there
any downside to making at least those changes?
Timothy Pratley
I read this as meaning that they wont implement ISeq, they will
implement IStream, but conceptually they would be a non-caching
"sequence" (in the English phrase sense, as opposed to seq in the
interface sense), and they should be referred to as streams because
sequence has a well defined and different meaning.
Mark: You seem unsatisfied with the promise of "streams" which to me
sound to be precisely what you describe as "non-caching seqs".
Am I missing some important point of functional difference?
Regards,
Tim.
Rich Hickey
On Jan 8, 11:22 pm, "Mark Engelberg" <mark.engelb...@gmail.com> wrote:
> > When you
> > ask for the nth element/rest, you get the identical item every time.
>
> I know this is nitpicking, but if this is really the promise that the
> seq abstraction is supposed to fulfill, then Clojure already violates
> this:
> (def a (seq [1 2 3]))
> (identical? (rest a) (rest a)) yields false
>
> Presumably what you mean is that the nth element should be identical
> (but not necessarily the nth rest).
>
'cheat' (for perf), and are thus broken in the identity sense.
> > The sequence abstraction in Clojure is the list abstraction of Lisp.
> > No more, no less.
>
> Well, in Lisp, lists are concrete, finite things that are mutable (and
> therefore don't provide any kind of guarantee that you'll get the same
> element with multiple traversals). So to say that Clojure's sequence
> abstraction is no more and no less than the list abstraction of Lisp
> is a bit misleading.
> You have a certain concept of what properties of
> this abstraction you want to model, and what promises you want to
> keep. And that's great -- honestly, I think it's fantastic that you
> have such a clear, coherent design vision that you've maintained
> throughout the creation of Clojure. I'm just saying that your
> interpretation of what constitutes an abstraction of a Lisp list is
> more subjective than your statement implies.
>
conceive of things is this/my way'.
> I'm pretty sure my concept of the list abstraction differs from yours.
> In my mind the essential abstract concept of a list is anything that
> can be explained in this way:
> A list has a first and a rest, where first is some kind of element,
> and rest is another list or nil.
>
that there is an abstraction in Clojure and it is not that one, and
swapping out caching breaks it.
I had exactly the same idea, evidenced by the fact that I had
implemented it and tested it. So, I don't think it is a bad idea. But
it does break from Clojure's current promises. What I think is
important is that any proposed substitution be clear about what its
promises are, and what tradeoffs are involved.
> In other words, I would say a sequence abstraction should apply to
> anything that has this sort of nested, self-referential recursive
> structure.
>
> There is an elegance to the way that algorithms on self-referential
> data structures can be expressed via recursion. To me, a big part of
> Clojure's beauty lies in the recognition that so many things can be
> converted to this view. Strictly speaking, a vector is not structured
> in this way, but you can convert it into something that has this
> property, allowing you to program vectors with this sort of recursive
> elegance.
>
> When I think about something like the sequence of whole numbers, it
> seems like a perfect embodiment of what I consider to be the essential
> abstraction of a sequence. You've got a first thing, and the rest
> thing is another sequence that has similarity to the original.
> Because it has a recursive structure, I want to be able to operate on
> it using first and rest. To me, a sequence feels like the "right
> abstraction" for the whole numbers, and writing algorithms that
> operate on them. And this feels like the right abstraction to me
> regardless of implementation details such as whether the traversed
> numbers should reside in memory all at once.
>
'laziness' of the collection itself. If (defn whole-numbers []
(iterate inc 0)) is too unbearable, you could attain this right now
with something like this:
(defn fn-coll [f]
(proxy [clojure.lang.IPersistentCollection clojure.lang.Sequential]
[]
(seq [] (seq (f)))
(count [] (count (seq (f))))
(cons [x] (cons x (seq (f))))
(empty [] nil)))
(def whole-numbers (fn-coll #(iterate inc 0)))
Where fn-coll defines an on-demand collection created by a generating
function.
> > Making seqs 'non-caching' makes no sense because they are no longer
> > the same abstraction.
>
> I get that your design vision revolves around the idea that sequences
> promise identity, and that there are real technical challenges
> surrounding the idea of non-cached sequences. But I don't consider
> "non-caching sequences" to be an oxymoron.
probably more correct is - non-caching seq functions would not yield
sequences according to the current seq abstraction.
> If it were possible to
> implement them in a way that meshed with the rest of Clojure's design,
> I think there would be real value to being able to manipulate
> non-cached recursive structures with the existing sequence interface.
> It's clear you don't think this fits with Clojure's design, but I
> haven't yet given up hope of finding a clever way to do this, and
> trying to convince you that it is worthwhile :) .
>
you've shown ArraySeq is non-caching. The real question is - can the
seq library be made non-caching?
> I know that over email, it is all too common for the tone of a post to
> be misconstrued. So just in case, I want to emphasize here that these
> posts are in no way intended as bashing Clojure or Rich's design
> sensibilities. It is precisely because I admire the design, and
> already care about Clojure, that I raise these points in the hope that
> community discussion can elevate the language even further. I strive
> to make my comments as constructive in tone as possible, and I hope
> that they are perceived in that light.
That said, I think it is critical when proposing a change to think
through all use cases, not just your own, and all tradeoffs. To be
explicit about what the new promises will be, i.e. what is the new
abstraction, and to double check that it will provide the benefits
presumed.
Since I had already done this, with lazy-seq/cached-seq, let me
further describe my thoughts.
The idea is much as you've requested - reduce the promise of seqs to
be merely functionally generative, not necessarily persistent. There
is no way for them to guarantee referential integrity, as their source
might not, or, if that was to be the abstraction, enforcing it becomes
a user problem. In short, the sequence functions won't cache - they'll
use lazy-seq instead of lazy-cons.
Users creating seqs from ephemeral or expensive to calculate sources
will have to cache them explicitly. There are currently many such
usages. Some are obviously I/O based, others more subtle - (map #(new
Foo %) ...), (map (agent/ref x) ...), i.e. any identity/reference
generating function. It ends up being quite a handy and pragmatic
thing that Clojure does, taking all this non-functional stuff and
turning it into persistent data (with referential integrity)
automatically. I'm certain the number of people who care about that
far exceeds those who share your expectations for (def whole-numbers
(iterate inc 0)). People have a tough enough time understanding
laziness - e.g. why (map print ...) doesn't do what they expect. Now
they will need to know when they have to cache in order to produce a
reliable sequence.
There are tradeoffs even for functional programmers, and very subtle
ones. You see, LazySeq needs to keep its generating function (usually
a closure), in order to generate new first/rest on-demand. For many
recursive algorithms, that closure will close over the prior head when
creating rest. This results in retaining the entire list anyway during
traversal (i.e. even when not retaining head!) due to this closure
back-chain. LazyCons avoids this by nulling out its generating
function once used, and can do this strictly because it caches.
So, many tradeoffs. What about the benefits? Could the core library
even promise that no seq fn will cache? If so, you could then build
named top-level seq values like whole-numbers that you know won't
retain the seq. But I don't think the library in general can make that
guarantee, due to the back chain problems. So you'd have to qualify
each fn as caching or not.
And the seq abstraction won't guarantee that no seq will ever be
cached - many need be and concrete lists are inherently so. So it
doesn't solve the 'take care not to retain the head' problem for
general purpose functions like filter, which must work correctly for
cached/concrete seqs. There is already aggressive clear-locals-on-
tails calls that remove the vast majority of cases of local head
retention.
Any other benefits? Well, (def whole-numbers (iterate inc 0)) will
work the way you want :) There are slight speed benefits, but the
comparison is not between head-retaining and not, but between non-head-
retaining caching and not, and my tests showed the caching overhead to
be about 10%.
So, in the end I saw few benefits and many tradeoffs, and still do.
Rich
Rich Hickey
real cost is explaining either why lazy-seq is private, or, if public,
when/how to use it.
Rich
Rich Hickey
much overloading both between programming languages and English.
As I envision it, a stream is truly ephemeral. Thus it is quite
different from a sequence. If you say rest/rest/rest to a sequence,
you will get the same thing every time, whereas if you say next!/next!/
next! to a stream you will get something different every time, i.e. a
stream flows.
Rich
Mark Engelberg
helped me understand what you've already tried, and what factors led
to your design decision. You've given me a lot to think about.
Justin Henzie
at some point reify and therefore be cached, to my mind, the
alternative is better describes as a stream or generator.
That is not to say that said stream is not the source of the
reification but that it might be better to keep the two concepts
separate for the purposes of deciding what abstraction one needs in a
particular case.
I don't have the gray matter to fully understand what is being
discussed but it is absolutely fascinating to see the strength and
depth of the community around clojure.
On Jan 8, 10:20 am, Rich Hickey <richhic...@gmail.com> wrote:
> On Jan 8, 2009, at 1:06 PM, Mark Engelberg wrote:
>
>
>
>
>
Mark Engelberg
> When I had lazy-seq in play, many of those were defined that way. The
> real cost is explaining either why lazy-seq is private, or, if public,
> when/how to use it.
I'd certainly make use of lazy-seq if it were public. But assuming
it's not made public, are you thinking right now that the underlying
clojure.lang.LazySeq will eventually go away, or can power users use
it and count on it being there, although not explicitly exposed
through the api?
Rich Hickey
On Jan 18, 5:17 am, Mark Engelberg <mark.engelb...@gmail.com> wrote:
> On Fri, Jan 9, 2009 at 6:00 AM, Rich Hickey <richhic...@gmail.com> wrote:
> > When I hadlazy-seqin play, many of those were defined that way. The
> > real cost is explaining either whylazy-seqis private, or, if public,
> > when/how to use it.
>
> I'd certainly make use oflazy-seqif it were public. But assuming
> clojure.lang.LazySeq will eventually go away, or can power users use
> it and count on it being there, although not explicitly exposed
> through the api?
think you should too :)
Rich