# Unrelated comments have been replaced with "..." 2013-07-25 14:24:10 ToxicFrog I'm running into something really weird with a recursively defined lazy infinite seq: http://hastebin.com/duforatapi.lisp ... 2013-07-25 14:25:40 ToxicFrog I would expect that (0 1 2) are in the seq (because they are < 3), and then 3 and 4 should be also (because by the time it's calling (tasty? 3) it's realized the list head and discovered that is (= 0) 2013-07-25 14:26:15 ToxicFrog Instead it seems to be the case that (first tasty) is something other than 0 until it calls (tasty? 32) and then suddenly it is 0. 2013-07-25 14:26:31 ToxicFrog Is this a weird interaction with (declare)? Am I not understanding something fundmental about how lazy seqs work? 2013-07-25 14:27:17 gfredericks ToxicFrog: this is super weird 2013-07-25 14:27:27 ToxicFrog (this is 1.4.0, btw) 2013-07-25 14:27:34 gfredericks I get it in 1.5.1 too 2013-07-25 14:28:26 ToxicFrog Also I'm glad it's not just me who thinks it's weird 2013-07-25 14:28:38 gfredericks ToxicFrog: this has something to do with chunking 2013-07-25 14:28:48 gfredericks which you can tell by replacing (range) with (iterate inc 0) ... 2013-07-25 14:29:00 gfredericks but I haven't figured out why that should be relevant though ... 2013-07-25 14:29:48 stuartsierra ToxicFrog, gfredericks: You're running into chunked lazy sequences there. 2013-07-25 14:30:14 stuartsierra The 32 is a giveaway. 2013-07-25 14:30:18 gfredericks stuartsierra: oh definitely 2013-07-25 14:30:28 gfredericks stuartsierra: that's what I just said -- it's just not clear why it's relevant 2013-07-25 14:30:43 gfredericks as best I can tell, the act of computing a chunk of a chunked lazy seq is calling first on itself 2013-07-25 14:30:54 gfredericks which is not throwing an exception but is instead returning something weird ... 2013-07-25 14:32:25 ToxicFrog Adding a (println) says that it's nil until the first 32 elements have been evaluated, then 0 2013-07-25 14:32:58 gfredericks looks like (first my-chunked-seq) is nil during the computation of the first chunk 2013-07-25 14:33:11 gfredericks oh you just found out the same thing 2013-07-25 14:33:20 ToxicFrog Is there any documentation on chunked sequences? The docs for (range) don't mention that it chunks, nor that this optimization(?) may break things. 2013-07-25 14:33:24 gfredericks ToxicFrog: yeah I'd say a self-referential chunked lazy seq is a bad idea :) 2013-07-25 14:33:43 gfredericks ToxicFrog: in general a self-referential lazy seq probably shouldn't be necessary I don't think 2013-07-25 14:34:05 ToxicFrog gfredericks: necessary, no, but it's a convenient way to write some things 2013-07-25 14:34:32 ToxicFrog (I ran into this when making a simple prime generator as practice; when testing to see if the next number is prime it's useful to be able to refer to earlier primes) 2013-07-25 14:35:00 ToxicFrog (there are undoubtedly non-toy applications for this technique) ... 2013-07-25 14:36:20 ToxicFrog gfredericks: in any case it should probably be mentioned in the docs for functions that generate chunked sequences that they do so and are thus not safe for recursion. 2013-07-25 14:37:16 ToxicFrog I would not normally expect replacing (range) with (iterate inc 0) to change the results of my code. 2013-07-25 14:38:10 stuartsierra Most of the core sequence functions used chunking when possible as an optimization. 2013-07-25 14:38:21 stuartsierra s/used/use/ 2013-07-25 14:38:58 stuartsierra In general, Clojure's lazy sequences make no guarantees about *when* a particular part of the seq is realized. 2013-07-25 14:39:36 ToxicFrog I think the underlying surprise here is that I thought it was guaranteed that (first foo) would be realized before (rest foo) 2013-07-25 14:40:10 ToxicFrog When this is not actually the case. ... 2013-07-25 14:40:51 ToxicFrog IT seems likely that this guarantee isn't actually stated anywhere, but it's still super surprising. ... 2013-07-25 14:44:44 ToxicFrog gfredericks, stuartsierra: to make it even more confusing, (chunked-seq? tasty) returns false in both versions 2013-07-25 14:45:23 ToxicFrog As does (chunked-seq? (take 5 tasty)) ... 2013-07-25 14:46:56 stuartsierra chunked-seq? isn't documented, probably an internal function. ... 2013-07-25 14:49:18 ToxicFrog stuartsierra: anyways - is there literature on sequence chunking, which functions I should beware of, etc? 2013-07-25 14:50:21 stuartsierra ToxicFrog: Not that I'm aware of. Assume any core function which generates a sequence may use chunking. 2013-07-25 14:50:28 ToxicFrog :( 2013-07-25 14:51:08 llasram ToxicFrog: What's the actual ultimate problem? 2013-07-25 14:51:26 gfredericks he wants to use haskell-style laziness-backed self-reference 2013-07-25 14:51:31 ToxicFrog ^ that 2013-07-25 14:51:42 stuartsierra Then use Haskell. 2013-07-25 14:51:56 llasram Oh. You can always explicitly unchunk your sequences 2013-07-25 14:51:59 ToxicFrog Sadly my underlying assumption that the n'th value in the seq won't be realized until after the (n-1)th value has been turns out to be false. 2013-07-25 14:52:33 bbloom ToxicFrog: decompile the problem into a lazy traversal and a state machine 2013-07-25 14:52:39 bbloom s/decompile/decompose 2013-07-25 14:52:48 ToxicFrog llasram: how? (and how did you learn about chunking?) 2013-07-25 14:53:01 bbloom if you need linear execution, just loop over a sequence and conduct your side effects in the loop 2013-07-25 14:53:16 ToxicFrog bbloom: there are no side effects. 2013-07-25 14:53:23 bbloom ToxicFrog: evaluation is a side effect 2013-07-25 14:53:42 ToxicFrog I'm just trying to compute an infinite lazy sequence where the value of later values in the sequence is an expression of values earlier in the sequence. 2013-07-25 14:53:51 SegFaultAX IIRC chunked seqs are implemented in such a way that they should be transparent. 2013-07-25 14:54:10 ToxicFrog If evaluation is a noticeable side effect your abstraction is leaking, IMO. 2013-07-25 14:54:25 bbloom ToxicFrog: this is why people complain about understanding space complexity in haskell, b/c you can get UNBOUNDED lookahead w/ laziness 2013-07-25 14:54:27 llasram ToxicFrog: I read about it in /Joy of Clojure/ very early in my Clojure-programming. /JoC/ has this function: https://www.refheap.com/16909 2013-07-25 14:54:31 SegFaultAX Should being the operative term. They exist only as a performance optimization. 2013-07-25 14:54:33 ToxicFrog SegFaultAX: the genesis of this discussion is that they are actually not; I have code that returns different values when using a chunked seq vs. a non-chunked one. 2013-07-25 14:54:39 bbloom you can achieve what you want, but you must be explicit about your buffering 2013-07-25 14:54:55 SegFaultAX ToxicFrog: Bummer :/ 2013-07-25 14:55:02 ToxicFrog bbloom: I would prefer unbounded lookahead (and thus terrible performance, OOMs, etc) to getting the wrong answers quickly. 2013-07-25 14:55:04 llasram It still depends on the implementation detail that `lazy-seq` recursion is evaluated one thunk at a time, but in practice it works 2013-07-25 14:55:14 ToxicFrog llasram: thank you. 2013-07-25 14:56:05 bbloom ToxicFrog: the answer is right, your assumption about the semantics are wrong :-P if you want to achieve haskell-like semantics, you need to implement either A) fully lazy evaluation or B) a particular data structure for your use case 2013-07-25 14:56:52 bbloom this is why i'm suggesting: use a state transducer 2013-07-25 14:56:56 SegFaultAX Probably option b is easier. 2013-07-25 14:57:13 llasram ToxicFrog: Note that the docstring (which I wrote when I stole the function) isn't actually right -- it doesn't de-chunk the input seq, but returns a new seq which isn't chunked. So you wrap your input, not the seq your producing (if that wasn't obvious) 2013-07-25 14:57:15 SegFaultAX bbloom: Can you define that term? 2013-07-25 14:57:50 bbloom https://github.com/brandonbloom/transduce 2013-07-25 14:58:07 llasram oooh 2013-07-25 14:58:09 ToxicFrog bbloom: so, the objection I'm arriving at here is that chunking is an optimization that (a) does not seem to be documented outside JoC and (b) when applied can result in actual functional changes even in pure code 2013-07-25 14:58:52 ToxicFrog There is no indication which library functions produce chunked sequences, or even that chunked sequences are a thing, and if an optimization is meant to be that completely invisible it had better not change the results of code that triggers it! 2013-07-25 14:58:56 SegFaultAX bbloom: Ah, neat. 2013-07-25 14:59:01 llasram omg, bbloom, these are great 2013-07-25 14:59:24 ToxicFrog Alternately, a warning like "don't try to use self-referential lazy sequences, they will produce garbage due to internal optimizations used by clojure's lazy seq implementation" would be nice,. 2013-07-25 14:59:43 bbloom SegFaultAX: llasram: thanks! ... 2013-07-25 15:00:34 bbloom ToxicFrog: i just joined the conversation a tad late, so i need to look at your particular paste & understand the problem 2013-07-25 15:00:39 llasram ToxicFrog: The problem is that there really isn't a good way to tell when you're building a self-referential lazy-seq. If there were, I'd agree there should be a warning 2013-07-25 15:00:49 SegFaultAX bbloom: That's really useful. I'm sad to only just be learning about this library. 2013-07-25 15:00:49 ToxicFrog bbloom: http://hastebin.com/duforatapi.lisp ... 2013-07-25 15:01:14 ToxicFrog bbloom: If you replace (range) with (iterate inc 0) it works. 2013-07-25 15:01:47 SegFaultAX ToxicFrog: The whole point of range chunking is that it's more efficient to generate groups of numbers rather than single values. ... 2013-07-25 15:01:55 SegFaultAX If you're ok with the potential performance hit, though... ... 2013-07-25 15:02:18 bbloom ToxicFrog: neither range nor iterate is bugged. your example is using declare to create mutual recursion but you're missing one level of indirection 2013-07-25 15:02:26 ToxicFrog SegFaultAX: which is fine. But it's a performance optimization that can change program behaviour and thus should be more visible than it is. ... 2013-07-25 15:02:35 ToxicFrog bbloom: how/where? ... 2013-07-25 15:04:07 ToxicFrog What should I have done instead to avoid this? What should I have read to know I was meant to do that? ... 2013-07-25 15:04:49 bbloom ToxicFrog: (first tasty) is going to be a constant 2013-07-25 15:04:53 bbloom or should be 2013-07-25 15:04:55 llasram ToxicFrog: I don't think there was anything official you could have read. It's come up a few times on the mailing list, but AFAIK is basically tribal knowledge 2013-07-25 15:05:38 ToxicFrog bbloom: this is just a minimal test case; in practice (first tasty) might be some more complicated expression involving, say, (take limit tasty) where limit is some function of n. 2013-07-25 15:06:22 bbloom ToxicFrog: change (first tasty) to (doto (first tasty) prn) and you'll see what's happening 2013-07-25 15:06:31 bbloom you're getting 32 nils 2013-07-25 15:06:35 ToxicFrog I already know that 2013-07-25 15:06:39 bbloom b/c (first UNDEFINED-VAR) is bad 2013-07-25 15:06:59 gfredericks bbloom: he knows what's happening he thinks it should not happen or be better documented 2013-07-25 15:07:03 bbloom if you want mutual recursion, you must define things simultaneously 2013-07-25 15:07:09 bbloom i dunno what he want's documented 2013-07-25 15:07:19 gfredericks "don't use self-referential chunked seqs" 2013-07-25 15:07:25 gfredericks and also "chunked seqs exist" 2013-07-25 15:07:30 ToxicFrog ...how do I do that? Because last time I looked for "how do I do mutual recursion in clojure" the answer I got was "(define) one of the things first" ... 2013-07-25 15:07:37 bbloom no, it's don't use mutual recursion without a layer of indirection 2013-07-25 15:07:38 ToxicFrog bbloom: what gfredericks said. ... 2013-07-25 15:07:47 bbloom it's more than just chunked sequences 2013-07-25 15:07:50 ToxicFrog Ok, what layer of indirection? You keep saying I'm missing one and I'm asking what 2013-07-25 15:08:10 bbloom you're trying to evaluate tasty? while tasty is being defined 2013-07-25 15:08:16 bbloom that's undefined behavior b/c it's mutually recursive 2013-07-25 15:08:21 bbloom you need to add a delay or a fn call 2013-07-25 15:08:57 bbloom and if you do that, you'll get a stack overflow, which is precisely what your function is trying to do :-P 2013-07-25 15:09:03 gfredericks now we need documentation saying "Don't be mutually recursive because it's undefined" 2013-07-25 15:09:23 gfredericks bbloom: it works perfectly well w/o chunking 2013-07-25 15:09:29 bbloom by luck 2013-07-25 15:09:41 ToxicFrog ...well, no, because by the time (tasty?) needs to evaluate part of tasty, the parts of tasty it's referring to are already realized non-recursively 2013-07-25 15:09:44 bbloom b/c of some internal order of execution 2013-07-25 15:10:11 gfredericks bbloom: if "some internal order of execution" means "evaluating lazy seqs in order one item at a time" then yeah 2013-07-25 15:11:00 ToxicFrog The first three values of tasty (0 1 2) are evaluated without any recursion; 3 onwards require evaluation only of (head tasty). It does not seem controversial that "the elements of a lazy seq are realized in order" is a reasonable assumption to make, and that the fact that this assumption is wrong should be documented. 2013-07-25 15:11:36 gfredericks for the record I don't think we should write code like this; but I think it's reasonable that he had different expectations and that this will happen to others 2013-07-25 15:11:52 bbloom i agree with that gfredericks 2013-07-25 15:12:01 gfredericks ToxicFrog: they _are_ realized in order, just some of them in parallel 2013-07-25 15:12:21 ToxicFrog Yeah, I would also be ok with the answer to "how do I do mutual recursion in clojure" being "don't", even if that is a really aggravating restriction in some cases 2013-07-25 15:12:29 ToxicFrog As long as that was actually documented somewhere. 2013-07-25 15:12:30 bbloom gfredericks: parallel == "observably simultaneously" ? 2013-07-25 15:12:41 gfredericks bbloom: I think so yes 2013-07-25 15:12:51 gfredericks bbloom: certainly I didn't mean wrt threads and such ... 2013-07-25 15:12:55 amalloy ToxicFrog: that's not really true, though; the thing that's discouraged is self-recursive data structures 2013-07-25 15:13:20 amalloy mutually-recursive functions are fine, although because we lack TCO you have to be careful 2013-07-25 15:13:54 ToxicFrog gfredericks: that doesn't really count as "in order" to me; "in order" implies that, at the moment the n'th element of the sequence is realized, all prior elements have already been realized. 2013-07-25 15:14:53 gfredericks ToxicFrog: okay; definitions I guess 2013-07-25 15:16:20 ToxicFrog gfredericks: basically the assumption of mine that was violated was that s[n] will always be realized after realization of s[n-1] is complete (and thus, by implication, that a definition of s[n] that depends on s[m] where m