<< Back to previous view

[CLJS-2258] Stack overflow regression for sequence xform applied to eduction Created: 18/Jul/17  Updated: 24/Jul/17  Resolved: 24/Jul/17

Status: Closed
Project: ClojureScript
Component/s: None
Affects Version/s: 1.9.562
Fix Version/s: None

Type: Defect Priority: Critical
Reporter: Mike Fikes Assignee: David Nolen
Resolution: Completed Votes: 0
Labels: regression, transducers

Attachments: Text File CLJS-2258.patch    
Patch: Code and Test
Approval: Accepted

 Description   

There is a regression in the ability to use sequence to apply transducers to eductions that was introduced with 1.9.562.

In 1.9.542 and earlier,

(sequence (map str) (eduction [1]))
produced ("1").

Minimal repro:

$ java -jar cljs.jar -m cljs.repl.node
ClojureScript Node.js REPL server listening on 50609
To quit, type: :cljs/quit
cljs.user=> (sequence (map str) (eduction [1]))
repl:13
throw e__5525__auto__;
^

RangeError: Maximum call stack size exceeded
    at Function.cljs.core.TransformerIterator.create (/Users/mfikes/Downloads/.cljs_node_repl/.cljs_node_repl/cljs/core.js:13959:50)
    at cljs.core.Eduction.cljs$core$IIterable$_iterator$arity$1 (/Users/mfikes/Downloads/.cljs_node_repl/.cljs_node_repl/cljs/core.js:33244:38)
    at Object.cljs$core$_iterator [as _iterator] (/Users/mfikes/Downloads/.cljs_node_repl/.cljs_node_repl/cljs/core.js:3158:13)
    at Object.cljs$core$iter [as iter] (/Users/mfikes/Downloads/.cljs_node_repl/.cljs_node_repl/cljs/core.js:13554:18)
    at Function.cljs.core.TransformerIterator.create (/Users/mfikes/Downloads/.cljs_node_repl/.cljs_node_repl/cljs/core.js:13960:55)
    at cljs.core.Eduction.cljs$core$IIterable$_iterator$arity$1 (/Users/mfikes/Downloads/.cljs_node_repl/.cljs_node_repl/cljs/core.js:33244:38)
    at Object.cljs$core$_iterator [as _iterator] (/Users/mfikes/Downloads/.cljs_node_repl/.cljs_node_repl/cljs/core.js:3158:13)
    at Object.cljs$core$iter [as iter] (/Users/mfikes/Downloads/.cljs_node_repl/.cljs_node_repl/cljs/core.js:13554:18)
    at Function.cljs.core.TransformerIterator.create (/Users/mfikes/Downloads/.cljs_node_repl/.cljs_node_repl/cljs/core.js:13960:55)
    at cljs.core.Eduction.cljs$core$IIterable$_iterator$arity$1 (/Users/mfikes/Downloads/.cljs_node_repl/.cljs_node_repl/cljs/core.js:33244:38)


 Comments   
Comment by Mike Fikes [ 18/Jul/17 7:36 AM ]

CLJS-2034:

d93c4356e7ab78743ae66d8cffe8df54869f0be3 is the first bad commit
commit d93c4356e7ab78743ae66d8cffe8df54869f0be3
Author: António Nuno Monteiro <anmonteiro@gmail.com>
Date:   Fri May 12 13:39:37 2017 -0700

    CLJS-2034: Sequence and Eduction produce infinite loop in transducer that appends to the reduction

    The implementation of transducers in ClojureScript tracked an old counterpart in
    the Clojure codebase. This patch addresses the change introduced in the
    following commit to Clojure, which replaced `LazyTransformer` with
    `TransformerIterator`, effectively making the transducer behavior akin to the
    one in Clojure.

    https://github.com/clojure/clojure/commit/c47e1bbcfa227723df28d1c9e0a6df2bcb0fecc1

:040000 040000 001a34e8f941a2e1697299be2632143e3e191587 5a508a3162eb9eb1023c0c0cd9ff7ee9cf2ad733 M	src
Comment by António Nuno Monteiro [ 18/Jul/17 12:08 PM ]

Attached patch with fix and test.

Comment by Mike Fikes [ 18/Jul/17 12:37 PM ]

I don't know if this is a bug or not, but with 1.9.542

cljs.user=> (iter (eduction [1 2 3]))
#object[cljs.core.SeqIter]

and after the patch:

cljs.user=> (iter (eduction [1 2 3]))
repl:13
throw e__8096__auto__;
^

Error: [object Object] is not ISeqable
    at Object.cljs$core$seq [as seq] (/Users/mfikes/Projects/clojurescript/.cljs_node_repl/.cljs_node_repl/cljs/core.js:4413:8)
    at Object.cljs$core$pr_sequential_writer [as pr_sequential_writer] (/Users/mfikes/Projects/clojurescript/.cljs_node_repl/.cljs_node_repl/cljs/core.js:31431:14)
    at cljs.core.TransformerIterator.cljs$core$IPrintWithWriter$_pr_writer$arity$3 (/Users/mfikes/Projects/clojurescript/.cljs_node_repl/.cljs_node_repl/cljs/core.js:32456:18)
    at Object.cljs$core$pr_writer_impl [as pr_writer_impl] (/Users/mfikes/Projects/clojurescript/.cljs_node_repl/.cljs_node_repl/cljs/core.js:31612:12)
    at Object.cljs$core$pr_writer [as pr_writer] (/Users/mfikes/Projects/clojurescript/.cljs_node_repl/.cljs_node_repl/cljs/core.js:31722:18)
    at Object.cljs$core$pr_seq_writer [as pr_seq_writer] (/Users/mfikes/Projects/clojurescript/.cljs_node_repl/.cljs_node_repl/cljs/core.js:31726:11)
    at Object.cljs$core$pr_sb_with_opts [as pr_sb_with_opts] (/Users/mfikes/Projects/clojurescript/.cljs_node_repl/.cljs_node_repl/cljs/core.js:31789:11)
    at Object.cljs$core$pr_str_with_opts [as pr_str_with_opts] (/Users/mfikes/Projects/clojurescript/.cljs_node_repl/.cljs_node_repl/cljs/core.js:31803:63)
    at Function.cljs.core.pr_str.cljs$core$IFn$_invoke$arity$variadic (/Users/mfikes/Projects/clojurescript/.cljs_node_repl/.cljs_node_repl/cljs/core.js:31886:18)
    at Object.cljs$core$pr_str [as pr_str] (/Users/mfikes/Projects/clojurescript/.cljs_node_repl/.cljs_node_repl/cljs/core.js:31882:25){

I wonder if there is some public code path where this would show up (as opposed to directly calling iter).

Comment by António Nuno Monteiro [ 18/Jul/17 12:57 PM ]

`(iter (eduction [1 2 3]))` is now a TransformerIterator, which doesn't have a print method.

For comparison with Clojure:

user=> (clojure.lang.RT/iter (eduction [1 2 3]))
#object[clojure.lang.TransformerIterator 0x28adf451 "clojure.lang.TransformerIterator@28adf451"]
Comment by David Nolen [ 24/Jul/17 12:12 AM ]

fixed https://github.com/clojure/clojurescript/commit/f6f4c0431b21fcc87b4de0fcb41f799083f98b9b





[CLJS-2034] Sequence and Eduction produce infinite loop in transducer that appends to the reduction Created: 12/May/17  Updated: 18/Jul/17  Resolved: 12/May/17

Status: Closed
Project: ClojureScript
Component/s: None
Affects Version/s: None
Fix Version/s: 1.9.655

Type: Defect Priority: Minor
Reporter: António Nuno Monteiro Assignee: David Nolen
Resolution: Completed Votes: 0
Labels: transducers

Attachments: Text File CLJS-2034.patch    
Patch: Code and Test

 Description   

Example: a transducer that appends :foo to the result of the reduction:

(defn xf []
  (fn [rf]
    (fn
      ([] (rf))
      ([result] (rf result :foo))
      ([result input]
       (rf result input)))))

(sequence (xf) [1 2 3])

In Clojure, the above code yields

'(1 2 3 :foo)
. In ClojureScript, it results in an infinite loop. The same happens with `eduction`.
However,
(into [] (xf) [1 2 3])
doesn't produce an error.



 Comments   
Comment by António Nuno Monteiro [ 12/May/17 2:13 PM ]

I'm looking into fixing this one.

Comment by António Nuno Monteiro [ 12/May/17 3:46 PM ]

The implementation of transducers in ClojureScript tracked an old counterpart in
the Clojure codebase. This patch addresses the change introduced in the
following commit to Clojure, which replaced `LazyTransformer` with
`TransformerIterator`, effectively making the transducer behavior akin to the
one in Clojure.

https://github.com/clojure/clojure/commit/c47e1bbcfa227723df28d1c9e0a6df2bcb0fecc1

Attached patch with fix and test.

Comment by David Nolen [ 12/May/17 3:53 PM ]

fixed https://github.com/clojure/clojurescript/commit/d93c4356e7ab78743ae66d8cffe8df54869f0be3

Comment by Mike Fikes [ 18/Jul/17 7:37 AM ]

See regression in CLJS-2258.





[CLJS-2028] `realized?` throws on LazyTransformer Created: 08/May/17  Updated: 08/May/17  Resolved: 08/May/17

Status: Closed
Project: ClojureScript
Component/s: None
Affects Version/s: None
Fix Version/s: 1.9.655

Type: Defect Priority: Minor
Reporter: António Nuno Monteiro Assignee: David Nolen
Resolution: Completed Votes: 0
Labels: transducers

Attachments: Text File CLJS-2028.patch    
Patch: Code and Test

 Description   

This is possible in Clojure



 Comments   
Comment by David Nolen [ 08/May/17 6:42 PM ]

fixed https://github.com/clojure/clojurescript/commit/8b409e08ddf7775299ec19c12e9421cc331838d8





[CLJS-1209] Reduce produces additional final nil when used w/ eduction Created: 16/Apr/15  Updated: 10/May/15  Resolved: 10/May/15

Status: Closed
Project: ClojureScript
Component/s: None
Affects Version/s: 0.0-3269
Fix Version/s: 0.0-3308

Type: Defect Priority: Major
Reporter: Karsten Schmidt Assignee: Unassigned
Resolution: Completed Votes: 0
Labels: transducers


 Description   
Unable to find source-code formatter for language: clojure. Available languages are: javascript, sql, xhtml, actionscript, none, html, xml, java
(defn my-conj
  [acc x]
  (prn acc x)
  (conj acc x))

(reduce my-conj [] (eduction (map identity) [1 2 3]))
;; [] 1
;; [1] 2
;; [1 2] 3
;; [1 2 3] nil
;; [1 2 3 nil]

This seems to be a CLJS specific issue - the above works fine in CLJ1.7.0-beta1. On the other hand, reductions too doesn't suffer this behavior (in CLJS):

Unable to find source-code formatter for language: clojure. Available languages are: javascript, sql, xhtml, actionscript, none, html, xml, java
(reductions my-conj [] (eduction (map identity) [1 2 3]))
;; [] 1
;; [1] 2
;; [1 2] 3
;; ([] [1] [1 2] [1 2 3])


 Comments   
Comment by David Nolen [ 10/May/15 2:30 PM ]

I cannot reproduce with 0.0-3269. Please feel free to reopen if more information can be supplied.

Comment by Karsten Schmidt [ 10/May/15 4:44 PM ]

I don't know, David - don't understand how this can be, since I just tried the same w/ 3269 and the extra `nil` still is happening (I first did use a clean setup as described in CLJS quickstart wiki). The below is from a figwheel REPL:

cljs.user=> *clojurescript-version*
"0.0-3269"

cljs.user=> (defn my-conj [acc x] (prn acc x) (conj acc x))
#<function cljs$user$my_conj(acc,x){
cljs.core.prn.call(null,acc,x);
return cljs.core.conj.call(null,acc,x);
}>

cljs.user=> (reduce my-conj [] (eduction (map identity) [1 2 3]))
[] 1
[1] 2
[1 2] 3
[1 2 3] nil
[1 2 3 nil]
Comment by Karsten Schmidt [ 10/May/15 4:47 PM ]

verified to still occur w/ 0.0-3269

Comment by Karsten Schmidt [ 10/May/15 4:49 PM ]

I you want, I can attach a zip of my test project...

Comment by David Nolen [ 10/May/15 5:10 PM ]

I wasn't quite careful enough when trying out your failing example. I see the problem, fix coming.

Comment by David Nolen [ 10/May/15 5:14 PM ]

fixed https://github.com/clojure/clojurescript/commit/ca19a521195eee3eb38f2946157c273679d64212





[CLJ-2312] Avoid using keywords as sentinel values in transducers Created: 12/Jan/18  Updated: 12/Jan/18

Status: Open
Project: Clojure
Component/s: None
Affects Version/s: Release 1.7, Release 1.8, Release 1.9
Fix Version/s: None

Type: Defect Priority: Minor
Reporter: Rick Moynihan Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: security, transducers
Environment:

All environments



 Description   

The use of keywords as sentinels in transducers could in rare circumstances expose some applications to bugs and potential security risks.

(sequence (partition-by keyword) ["1" "none" "2" "clojure.core/none" "3" "4"])
;(["1"] ["none"] ["2"] ["clojure.core/none" "3"] ["4"])

Ideally a private or local value that cannot be injected into the functions domain should be used instead, e.g. (Object.).



 Comments   
Comment by Rick Moynihan [ 12/Jan/18 6:24 AM ]

Apologies for messing up the formatting on the snippet, I also didn't mean to assign this as major. Though I can't seem to edit it, perhaps someone else can.

Comment by Rick Moynihan [ 12/Jan/18 6:39 AM ]

Also thanks to @reborg and @bronsa on #clojure-uk for sharing the above snippet.

Comment by Alex Miller [ 12/Jan/18 7:53 AM ]

Rick - I added you to the necessary groups for edit privileges.

How is this a security risk?

Comment by Rick Moynihan [ 12/Jan/18 7:49 PM ]

Thanks for upping my privileges Alex.

I didn't mean to over egg the pudding, but perhaps I ended up doing it all the same!

My reasoning was that if you're using a transducer to map/reduce over values taken from user input, then an attacker could cause a loop to abort earlier than expected; which might then have other consequences. I did't have a specific attack vector in mind, but I'd seen also the sentinel ::halt and had imagined that a user could inject "clojure.core/halt" into a HTTP header. If ring has a middleware to keywordize keys then you have the sentinel value for a transducer injected by a user, and that sentinel could then potentially be used to shortcut the validation/encoding/escaping etc of other fields.

However I've looked a bit more at the implementation of halt-when and other transducers and it seems the key isn't ever mixed with user data; and that ::none is used to indicate the first pass over by some transducer functions. So it looks like I was mistaken. I doubt now that this is worth resolving.





[CLJ-2146] partition-by and partition-all transducers should ensure visibility of state changes Created: 09/Apr/17  Updated: 17/Apr/17

Status: Open
Project: Clojure
Component/s: None
Affects Version/s: Release 1.7
Fix Version/s: None

Type: Defect Priority: Major
Reporter: Alex Miller Assignee: Unassigned
Resolution: Unresolved Votes: 1
Labels: transducers

Approval: Vetted

 Description   

The partition-by and partition-all transducers use state stored in an ArrayList. This state should be protected (for example, by volatile) to ensure visibility if used in a transducing process that moves computations across threads.



 Comments   
Comment by Léo NOEL [ 13/Apr/17 1:00 PM ]

Discussion here : https://groups.google.com/forum/m/#!topic/clojure/VQj0E9TJWYY

Comment by Léo NOEL [ 16/Apr/17 9:47 AM ]

Note that following this logic, transients are as much broken, as they make use of plain arrays.
This paragraph https://clojure.org/reference/transients#_concurrent_use makes me believe this very problem has already been tackled before. Is the discussion available somewhere ?
In my opinion, documentation should be more precise about what is meant by thread isolation, and explain why it is OK to use unsynchronized mutable objects when they're owned by something that enforces sequential processing (agents, go blocks, channels, single-threading, etc).

Comment by Alex Miller [ 17/Apr/17 9:24 AM ]

Transients originally enforced thread isolation by recording and validating the originating thread. This was weakened to allow for transients passed around go blocks in Clojure 1.7 and has been through some rounds of fixes (like CLJ-1580). If there is an issue with them now, please file a separate ticket.





[CLJ-2090] Improve clojure.core/distinct perf by using transient set Created: 23/Dec/16  Updated: 04/Jan/17

Status: Open
Project: Clojure
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Enhancement Priority: Major
Reporter: Nikita Prokopov Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: performance, transducers, transient

Attachments: Text File clj-2090-use-transient-set-in-distinct-2.patch    
Patch: Code
Approval: Triaged

 Description   

Current implementation of clojure.core/distinct uses persistent set. This patch improves performance of lazy arity by ~25%-30% and transducer by ~40%-50% by using transient set instead.

10 elements
(doall (distinct coll)) 	 5.773439 µs => 4.179092 µs (-27%)
(into [] (distinct) coll) 	 3.238236 µs => 1.943254 µs (-39%)

100 elements
(doall (distinct coll)) 	 67.725764 µs => 42.129993 µs (-37%)
(into [] (distinct) coll) 	 35.702741 µs => 16.495947 µs (-53%)

1000 elements
(doall (distinct coll)) 	 540.652739 µs => 399.053873 µs (-26%)
(into [] (distinct) coll) 	 301.423077 µs => 164.025500 µs (-45%)

10000 elements
(doall (distinct coll)) 	 3.439137 ms => 3.058872 ms (-11%)
(into [] (distinct) coll) 	 1.437390 ms => 848.277178 µs (-40%)

Benchmarking code: https://gist.github.com/tonsky/97dfe1f9c48eccafc983a49c7042fb21



 Comments   
Comment by Alex Miller [ 23/Dec/16 8:52 AM ]

You can't remove the volatile - you still need that for safe publication in multi threaded transducing contexts.

Comment by Nikita Prokopov [ 23/Dec/16 11:50 AM ]

Alex Miller How do you mean?

  • I don’t update seen link because transient set can be mutated in-place
  • Are transducers meant to be used from multiple threads? Because even existing implementation clearly has race condition. I imagine fixing that would be costly (we’ll need a synchronized section), so maybe it should be a specialized transducer that you use only when needed?
Comment by Alex Miller [ 23/Dec/16 12:26 PM ]

Transient sets can NOT be mutated in place - you must use the return value.

Yes, transducers are used from multiple threads in (for example) transducer chans in core.async go blocks.

Comment by Alex Miller [ 23/Dec/16 12:28 PM ]

I should also say transducers are not expected to be used from more than one thread at a time, so there are no race problems. But being used from multiple threads over time requires proper safe publication.

Comment by Nikita Prokopov [ 24/Dec/16 3:07 AM ]

But being used from multiple threads over time requires proper safe publication.

Does that imply that no transients could be used in transducers (because underlying arrays on which transient impl is based are mutated in place, so different threads could potentially see different states of transient object)?

Does that also mean that partition-by and partition-all should be fixed (they use java.util.ArrayList which, being array of references, has no safe publication semantics)?

Transient sets can NOT be mutated in place - you must use the return value.

I was thinking that clojure/core.clj and clojure.lang.ATransientSet.java are both part of Clojure internals, colocated, so can share a little bit of internal knowledge about each other. It seems safe to do that, because that knowledge does not leak outside, and, if at any point impl of ATransientSet would change, core.clj could be updated accordingly in the same release. I wouldn’t do that in any third-party library, of course.

Comment by Alex Miller [ 24/Dec/16 9:13 AM ]

Does that imply that no transients could be used in transducers (because underlying arrays on which transient impl is based are mutated in place, so different threads could potentially see different states of transient object)?

Transients require only that they are asked by no more than a single thread at a time and so are safe to use in a transducer. However, they should guarantee safe publication. core.async channels already do this as an artifact of their implementation, but other transducing contexts may not.

Transients should NEVER be used as "mutate in place", regardless of concurrency. While they will appear to "work" in some circumstances, this is never correct (eventually an update operation will return a new instance and if you are mutating in place, your data will then be missing). This is discussed and correct examples are shown at http://clojure.org/reference/transients.

Does that also mean that partition-by and partition-all should be fixed (they use java.util.ArrayList which, being array of references, has no safe publication semantics)?

That's something Rich and I are discussing but, probably.

Comment by Nikita Prokopov [ 24/Dec/16 12:56 PM ]

Alex Miller Here’s quick test that shows that changes to transient set (which is nothing more but a wrapper around transient map) made in one thread are not always visible from another thread.

https://gist.github.com/tonsky/62a7ec6d539fc013186bee2df0812cf6

That means that if we try to use transients for e.g. distinct it will miss duplicate items

Comment by Nikita Prokopov [ 24/Dec/16 1:02 PM ]

Removed transients from transducer arity of distincts because transducers might be accessed from multiple threads

Comment by Nikita Prokopov [ 24/Dec/16 1:12 PM ]

Maybe that doc http://clojure.org/reference/transients should be updated re: transients are not safe to use from multiple threads because changes made by one thread are not necessarily visible to another. Even if they don’t compete

Comment by Alex Miller [ 31/Dec/16 12:54 PM ]

I would say that test is demonstrating a bug in transient sets/maps and you should file a ticket for that as it's a lot more important than this enhancement.

distinct should be able to use transients in both the transducer and lazy seq impls. The issue with contains? not working on transients is actually a separate ticket - http://dev.clojure.org/jira/browse/CLJ-700 that will likely require some class hierarchy rearrangement. I don't think we would take this change until that is fixed (so that you can avoid relying on the class and Java method variants).

Comment by Nikita Prokopov [ 04/Jan/17 11:47 AM ]

I have to admit my test was demonstrating something else: there were no proper thread isolation. So it was a concurrency issue, not “safe publication” issue. My current understanding is this:

Transients require thread isolation. Use of a particular transient instance should be controlled either by using it in an single-threaded scope, or in a framework that enforces this.

That guarantee implicitly presumes that there’s happens-before relation between transient usage from multiple threads. There’s no other way to define “only one thread is in this section at a time”.

That, in turn, means that all writes that happened in thread 1 are visible in thread 2, regardless to volatility of the variables involved. In fact, we can remove all volatiles from transients implementation and probably make them faster, because, by asking “no more than one thread at a time” we enforce users to establish happens-before between sections, and that would give us all the safe publication guarantees we need.

Is my understanding correct? Am I missing something?

Comment by Nikita Prokopov [ 04/Jan/17 11:55 AM ]

Also, long-living transients (e.g. in a transducers associated with a queue, for example) will hold a reference to a thread that created them. Is that a bad thing? Should we switch to boolean flag instead?





[CLJ-1903] Provide a transducer for reductions Created: 17/Mar/16  Updated: 01/Oct/17

Status: Open
Project: Clojure
Component/s: None
Affects Version/s: Release 1.8
Fix Version/s: None

Type: Feature Priority: Major
Reporter: Pierre-Yves Ritschard Assignee: Unassigned
Resolution: Unresolved Votes: 6
Labels: transducers

Attachments: Text File 0001-clojure.core-add-reductions-stateful-transducer.patch     Text File 0002-clojure.core-add-reductions-with-for-init-passing-va.patch     Text File 0003-add-reductions-with.patch    
Approval: Prescreened

 Description   

Reductions does not currently provide a transducer when called with a 1-arity.

Proposed:

  • A reductions transducer with explicit initialization values: reductions-with
  • Do to arity conflicts, this is a separate function, not combined with reductions

A second patch proposes a variant which allows explicit initialization values: reductions-with

(assert (= (sequence (reductions-with + 0) [1 2 3 4 5]) [1 3 6 10 15])))

Patch: 0003-add-reductions-with.patch

Prescreened by: Alex Miller



 Comments   
Comment by Steve Miner [ 17/Mar/16 3:47 PM ]

The suggested patch gets the "init" value for the reductions by calling the function with no args. I would like a "reductions" transducer that took an explicit "init" rather than relying on a nullary (f).

If I remember correctly, Rich has expressed some regrets about supporting reduce without an init (ala Common Lisp). My understanding is that an explicit init is preferred for new Clojure code.

Unfortunately, an explicit init arg for the transducer would conflict with the standard "no-init" reductions [f coll]. In my own code, I've used the name "accumulations" for this transducer. Another possible name might be "reductions-with".

Comment by Pierre-Yves Ritschard [ 17/Mar/16 4:38 PM ]

Hi Steve,

I'd much prefer for init values to be explicit as well, unfortunately, short of testing the 2nd argument in the 2-arity variant - which would probably be even more confusing, there's no way to do that with plain "reductions".

I like the idea of providing a "reductions-with" variant that forced the init value and I'm happy to augment the patch with that if needed.

Comment by Pierre-Yves Ritschard [ 18/Mar/16 3:35 AM ]

@Steve Miner I added a variant with reductions-with.

Comment by Pierre-Yves Ritschard [ 24/May/16 6:40 AM ]

Is there anything I can help to move this forward?
@alexmiller any comments on the code itself?

Comment by Alex Miller [ 24/May/16 7:31 AM ]

Haven't had a chance to look at it yet, sorry.

Comment by Pierre-Yves Ritschard [ 24/May/16 7:36 AM ]

@alexmiller, if the upshot is getting clojure.spec, I'll take this taking a bit of time to review

Comment by Steve Miner [ 25/May/16 3:21 PM ]

For testing, I suggest you compare the output from the transducer version to the output from a simliar call to the sequence reductions. For example,

(is (= (reductions + 3 (range 20)) (sequence (reductions-with + 3) (range 20)))

I would like to see that equality hold. The 0002 patch doesn't handle the init the same way the current Clojure reductions does.

Comment by Pierre-Yves Ritschard [ 07/Sep/16 4:29 PM ]

@alexmiller I'm tempting one more nudge to at least get an idea on the patch and the reductions-with variant since 1.9 seems to be getting closer to a release.

Comment by Alex Miller [ 08/Sep/16 10:43 AM ]

Sorry, don't know that I'll get to it soon or that it will be considered for 1.9. I also don't know that it won't, just ... don't know.

Comment by Pierre-Yves Ritschard [ 08/Sep/16 10:48 AM ]

@alexmiller, Thanks for the prompt reply. I'm trying to make sure i'll be around when feedback comes to be able to act quickly on it. Cheers!

Comment by Pierre-Yves Ritschard [ 07/Jun/17 9:03 AM ]

@alexmiller, any additonal insight into wether this has a chance of going in or if I can adapt/perfect the code in any way?

Comment by Alex Miller [ 07/Jun/17 9:30 AM ]

I will try to prescreen it when I get a chance.

Comment by Alex Miller [ 03/Aug/17 3:02 PM ]

I think I prefer the reductions-with approach rather than overloading into reductions.

You have two derefs @state - this is not wrong given the assumptions we are making here, but I think it would be stylistically preferred to see a single deref of state in a let.

Comment by Pierre-Yves Ritschard [ 04/Aug/17 2:43 AM ]

Hi @alexmiller, It does make more sense to only have reductions-with, with a consistent behavior.
I've added a third patch which implements it according to your recommendations, avoiding the double deref.

Comment by Marcin Kulik [ 01/Oct/17 12:11 PM ]

FYI, I've used reductions-with from the 3rd patch by Pierre-Yves in my ClojureScript project and it worked out of the box without any adjustments.





[CLJ-1896] Support transducers in vec and set fns Created: 24/Feb/16  Updated: 15/May/17

Status: Open
Project: Clojure
Component/s: None
Affects Version/s: Release 1.8
Fix Version/s: None

Type: Feature Priority: Major
Reporter: Alex Miller Assignee: Unassigned
Resolution: Unresolved Votes: 2
Labels: transducers

Approval: Triaged

 Description   

Rather than

(into [] (map inc) [1 2 3])
vec (and set) could support the transducer directly:

(vec (map inc) [1 2 3])
(set (map inc) #{1 2 3})

Depending how far we wanted to take this, the implementation could be somewhat clever for vec in building the initial set of results in an array and then creating the vector with it directly as is already done in some other cases.






[CLJ-1858] Transducer for partition-all with step Created: 28/Nov/15  Updated: 15/May/17

Status: Open
Project: Clojure
Component/s: None
Affects Version/s: Release 1.7
Fix Version/s: None

Type: Feature Priority: Minor
Reporter: Jeremy Apthorp Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: transducers


 Description   

The docs for partition-all[1] mention that when a coll is not provided, it returns a transducer. This is true for the form (partition-all n), but not true for (partition-all n step). There's no clear way that I can see to combine transducers from core to produce this sort of "sliding window" transducer, i.e.

user=> (into [] (partition-all 2 1) [1 2 3 4 5])
((1 2) (2 3) (3 4) (4 5) (5))

Of course, there's an arity collision between the above hypothesized (partition-all n step) and the concrete, non-transducer-producing (partition-all n coll), which could be resolved by switching on the type of the second argument, or less hackily by providing the functionality in a separate function, e.g. (sliding window-size step-size), or perhaps by some other means.

I implemented this function with reference to the existing (partition-all n) transducer here: https://gist.github.com/nornagon/03b85fbc22b3613087f6

Would it make sense to work on getting something like this into core?

[1]: http://clojuredocs.org/clojure.core/partition-all






[CLJ-1806] group-by as reducer / reduction fn Created: 29/Aug/15  Updated: 15/May/17

Status: Open
Project: Clojure
Component/s: None
Affects Version/s: Release 1.8
Fix Version/s: None

Type: Feature Priority: Minor
Reporter: Karsten Schmidt Assignee: Unassigned
Resolution: Unresolved Votes: 1
Labels: reducers, transducers

Attachments: Text File clj-1806-1.patch    

 Description   

Whilst working on a query engine heavily based on transducers, I noticed that it'd be great to have group-by able to be used as reduction fn. The attached patch adds a single arity version to group-by which enables this use case and also includes a few tests.



 Comments   
Comment by Karsten Schmidt [ 29/Aug/15 8:08 PM ]

patch w/ described changes





[CLJ-1804] take transducer optimization Created: 25/Aug/15  Updated: 26/Aug/15

Status: Open
Project: Clojure
Component/s: None
Affects Version/s: Release 1.8
Fix Version/s: None

Type: Enhancement Priority: Minor
Reporter: Karsten Schmidt Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: performance, transducers

Attachments: Text File clj-1804-1.patch     Text File clj-1804-2.patch    
Patch: Code
Approval: Triaged

 Description   

A basic refactoring to remove the let form and only requires a single counter check for each iteration, yields an 25% performance increase. With the patch, 2 checks are only required for the last iteration (in case counter arg was <= 0)...

;; master
(quick-bench (into [] (take 1000) (range 2000)))
WARNING: Final GC required 34.82584189073624 % of runtime
Evaluation count : 13050 in 6 samples of 2175 calls.
             Execution time mean : 46.921254 µs
    Execution time std-deviation : 1.904733 µs
   Execution time lower quantile : 45.124921 µs ( 2.5%)
   Execution time upper quantile : 49.427201 µs (97.5%)
                   Overhead used : 2.367243 ns

;; w/ patch
(quick-bench (into [] (take 1000) (range 2000)))
WARNING: Final GC required 34.74448252054369 % of runtime
Evaluation count : 18102 in 6 samples of 3017 calls.
             Execution time mean : 34.301193 µs
    Execution time std-deviation : 1.714105 µs
   Execution time lower quantile : 32.341349 µs ( 2.5%)
   Execution time upper quantile : 37.046851 µs (97.5%)
                   Overhead used : 2.367243 ns


 Comments   
Comment by Karsten Schmidt [ 25/Aug/15 10:35 AM ]

Proposed patch, passes all existing tests

Comment by Alex Miller [ 25/Aug/15 11:28 AM ]

From a superficial skim, I see checks for pos? and then neg? which both exclude 0 and that gives me doubts about that branch. That may actually be ok but I will have to read it more closely.

Comment by Karsten Schmidt [ 25/Aug/15 11:58 AM ]

Hi Alex, try running the tests... AFAICT it's all still working as advertised: For (take 0) or (take -1) then the pos? check fails, but we must ensure to not call rf for that iteration. For all other (take n) cases only the pos? check is executed apart from the last iteration (which causes a single superfluous neg? call) The current path/impl always does 2 checks for all iterations and hence is (much) slower.

Comment by Alex Miller [ 25/Aug/15 7:22 PM ]

The only time that neg? case will be hit is if take is passed n <= 0, so I think this is correct. However, you might consider some different way to handle that particular case - for example, it could be pulled out of the transducer function entirely and be created as a separate transducer function entirely. I'm not sure that's worth doing, but it's an idea.

Comment by Karsten Schmidt [ 26/Aug/15 6:01 AM ]

Good idea, Alex! This 2nd patch removes the neg? check and adds a quick bail transducer for cases where n <= 0. It also made it slightly faster still:

(quick-bench (into [] (take 1000) (range 2000)))
Evaluation count : 20370 in 6 samples of 3395 calls.
             Execution time mean : 30.302673 µs

(now ~35% faster than original)





[CLJ-1723] NPE with eduction + cat on a collection containing nil Created: 04/May/15  Updated: 05/Jun/15  Resolved: 12/May/15

Status: Closed
Project: Clojure
Component/s: None
Affects Version/s: Release 1.7
Fix Version/s: Release 1.7

Type: Defect Priority: Critical
Reporter: Moritz Heidkamp Assignee: Alex Miller
Resolution: Completed Votes: 0
Labels: transducers

Attachments: Text File clj-1723.patch    
Patch: Code and Test
Approval: Ok

 Description   

Using the cat transducer with eduction leads to an NPE when the collection contains at least one collection with more than one item of which at least one is nil. The shortest reproduction case I could come up with is this:

(eduction cat [[nil nil]])

Cause: An expanding transducer (cat, mapcat) puts the expansion on an internal buffer, which is a ConcurrentLinkedQueue. Java Queue impls do not support adding or removing null b/c null is used as a special value in some of the Queue apis.

Approach: Switch from ConcurrentLinkedQueue to LinkedList. LinkedList supports both Queue and other semantics as well and does support nulls (with caveats that that is a bad thing to do if you're using the Queue apis and expecting those special semantics). However, the TransformerIterator usage does not rely on any of that. LinkedList is also obviously not concurrency friendly, but the buffer is only used by a single thread at a time and the volatile field guarantees visibility, so this is fine.

I re-ran some of the perf tests from CLJ-1669 and found the expanding transducer test there (into [] (eduction (map inc) (mapcat range) s50)) went from 27 us to 24 us, so there is a bit of a perf improvement as well.

Patch: clj-1723.patch



 Comments   
Comment by Alex Miller [ 04/May/15 12:03 PM ]

Gah, Java Queues don't allow null. I have some prior work on other impls for this so I'm working on a fix.

Comment by Fogus [ 08/May/15 9:49 AM ]

This is a very straight-forward solution that works and is easy to justify and grasp.

Comment by Nicola Mometto [ 05/Jun/15 9:53 AM ]

Patch committed and the ticket marked as resolved but not closed. I'm closing it.





[CLJ-1684] Transducer eduction test is wrong Created: 27/Mar/15  Updated: 31/Mar/15  Resolved: 31/Mar/15

Status: Closed
Project: Clojure
Component/s: None
Affects Version/s: Release 1.7
Fix Version/s: Release 1.7

Type: Defect Priority: Major
Reporter: Alex Miller Assignee: Unassigned
Resolution: Completed Votes: 0
Labels: regression, transducers

Attachments: Text File clj-1684.patch    
Patch: Code and Test
Approval: Ok

 Description   

Error in build:

[java] ERROR in (seq-and-transducer) (TransformerIterator.java:86)
         [java] Uncaught exception, not in assertion.
         [java] expected: nil
         [java]   actual: java.lang.NullPointerException: null
         [java]  at clojure.lang.TransformerIterator.step (TransformerIterator.java:86)
         [java]     clojure.lang.TransformerIterator.hasNext (TransformerIterator.java:97)
         [java]     clojure.lang.RT.chunkIteratorSeq (RT.java:489)
         [java]     clojure.lang.RT.seqFrom (RT.java:518)
         [java]     clojure.lang.RT.seq (RT.java:509)
         [java]     clojure.core/seq (core.clj:135)
         [java]     clojure.core$print_sequential.invoke (core_print.clj:47)
         [java]     clojure.core/fn (core.clj:7362)
         [java]     clojure.lang.MultiFn.invoke (MultiFn.java:233)
         [java]     clojure.core$pr_on.invoke (core.clj:3549)
         [java]     clojure.core$pr.invoke (core.clj:3561)
         [java]     clojure.pprint$pprint_simple_default.invoke (dispatch.clj:144)

There is an error in the generative transducer eduction test that was added in CLJ-1669. This code in transducers.clj:

(apply eduction (into actions [coll]))

is not invoking eduction with actions and a collection. Rather it is putting the actions inside the collection and effectively using no transformation at all as in {{(eduction [1 2])}}, which always passes. The error seen is due to a bad function being passed - if actions happens to be nil (which I think is happening while shrinking another failure), something like (eduction (constantly nil) []) is being called, which we would not expect to work in the first place.

After fixing the bad eduction handling, I was only able to trigger failures with a high number of iterations and a very large number of transformations. The errors reported under these conditions are difficult to understand, I believe because they are hitting StackOverflow errors and the stack traces are being removed by the JVM.

I did some more investigation into whether we are actually generating useful generative tests and found that due to the large stack of transformations, virtually all tests were just producing exceptions, rather than more interesting behavior. I capped the number of transformations to 5 and saw much more useful and interesting tests being generated. I've also doubled the number of transducer tests being run in the patch and ran it locally with a much higher number with no failures.

Patch: clj-1684.patch






[CLJ-1669] Move LazyTransformer to an iterator strategy, extend eduction capabilities Created: 04/Mar/15  Updated: 19/May/15  Resolved: 19/May/15

Status: Closed
Project: Clojure
Component/s: None
Affects Version/s: Release 1.7
Fix Version/s: Release 1.7

Type: Enhancement Priority: Major
Reporter: Alex Miller Assignee: Alex Miller
Resolution: Completed Votes: 0
Labels: transducers

Attachments: Text File clj-1669-2.patch     Text File clj-1669-3.patch     Text File clj-1669-4.patch     Text File clj-1669-5.patch     Text File clj-1669-6.patch     Text File clj-1669.patch    
Patch: Code and Test
Approval: Ok

 Description   
  • LazyTransformer does a lot of work to be a seq. Instead, switch to creating a transforming iterator.
  • Change sequence to wrap iterator-seq around the transforming iterator.
  • Change the iterator-seq implementation to be chunked. IteratorSeq will no longer be used but is left in case of regressions for now.
  • Change Eduction to provide iteration directly via the transforming iterator.
  • Extend eduction to support multiple xforms.

Performance:

Compared:

  • alpha5 == before any change
  • alpha6 == after clj-1669-6.patch was applied
  • beta3 == latest, includes range enhancement, expanding mapcat enhancement, etc

;; using java 1.8
(use 'criterium.core)
(def s (range 1000))
(def v (vec s))
(def s50 (range 50))
(def v50 (vec s50))

expr alpha5 s alpha5 v alpha6 s alpha6 v beta3 s beta3 v
non-chunking transform            
(into [] (->> s (interpose 5) (partition-all 2))) 432 us 437 us 413 us 411 us 353 us 414 us
(into [] (->> s (eduction (interpose 5) (partition-all 2)))) * 117 us 118 us 117 us 113 us 116 us 113 us
1 chunking transform            
(into [] (map inc s)) 43 us 45 us 35 us 31 us 32 us 36 us
(into [] (map inc) s) 19 us 19 us 18 us 18 us 18 us 16 us
(into [] (sequence (map inc) s)) 100 us 54 us 97 us 65 us 66 us 64 us
(into [] (eduction (map inc) s)) 24 us 19 us 24 us 20 us 20 us 19 us
(doall (map inc (eduction (map inc) s))) 219 us 203 us 98 us 78 us 93 us 89 us
2 chunking transforms        
(into [] (map inc (map inc s))) 53 us 56 us 53 us 54 us 61 us 58 us
(into [] (comp (map inc) (map inc)) s) 13 us 26 us 30 us 26 us 31 us 31 us
(into [] (sequence (comp (map inc) (map inc)) s)) 111 us 64 us 98 us 73 us 83 us 80 us
(into [] (eduction (map inc) (map inc) s)) * 58 us 31 us 58 us 31 us 30 us 31 us
(doall (map inc (eduction (map inc) (map inc) s))) * 240 us 212 us 114 us 93 us 105 us 102 us
expand transform            
(into [] (mapcat range (map inc s50))) 74 us 73 us 67 us 68 us 37 us 39 us
(into [] (sequence (comp (map inc) (mapcat range)) s50)) 111 us 102 us 166 us 159 us 99 us 98 us
(into [] (eduction (map inc) (mapcat range) s50)) * 65 us 64 us 57 us 56 us 27 us 27 us
materialized eduction            
(sort (eduction (map inc) s)) ERR ERR 99 us 77 us 77 us 77 us
(->> s (filter odd?) (map str) (sort-by last)) 1.10 ms 1.25 ms 1.15 ms 1.19 ms 1.14 ms 1.13 ms
(->> s (eduction (filter odd?) (map str)) (sort-by last)) ERR ERR 1.18 ms 1.15 ms 1.13 ms 1.13 ms
  • used comp to combine xforms as eduction only took one in the before case

Patch: clj-1669-6.patch

Screened by:



 Comments   
Comment by Michael Blume [ 05/Mar/15 3:52 PM ]

Nice, I like the direction on this.

CLJ-1515 currently breaks this patch (LongRange cannot be converted to Iterable), but I imagine that'll get better when it absorbs the changes from CLJ-1603

Comment by Alex Miller [ 06/Mar/15 8:11 AM ]

Yeah. colls should be mapped through RT.iter() to catch more cases.

Comment by Alex Miller [ 06/Mar/15 9:52 AM ]

To do:

  • remove Seqable from Eduction
  • support Iterable in RT.toArray()
  • more eduction pipeline tests that require realization at end
Comment by Alex Miller [ 06/Mar/15 1:00 PM ]

Perf numbers show pretty worse results from sequence, will dig in further.

Comment by Alex Miller [ 13/Mar/15 7:41 AM ]

For the s timings, we've actually introduced more steps into the stack:

OLD reduce with s:

LazyTransformer
   seq (range) - every transformation is another layer here

NEW reduce with s:

IteratorSeq 
  TransformingIterator (handles N transformations in 1 step)
    SeqIterator
      seq (range)
Comment by Alex Miller [ 20/Mar/15 10:08 AM ]

Look at perf for:

  • ->> eduction transformation
  • transformation comparison that doesn't support chunking
  • more into vector iteration case
Comment by Alex Miller [ 21/Mar/15 8:45 AM ]

The -5 patch is same -3 except all uses of IteratorSeq have been replaced with a ChunkedCons that is effectively a chunked version of the old IteratorSeq. While no one calls it, I left IteratorSeq in the code base in case of regression.

Generally, the chunked iterator seq reduces the cost in a number of the worst cases and also is a clear benefit in making seqs over a result of eduction or sequence faster to traverse (as they are now chunked).

I think the one potential issue is that seqs over iterators are now chunked when they were not before which could change programs that expect their stateful iterator to be traversed one at a time. This change could be isolated to just to sequence and seq-iterator and mitigated by not changing RT.seqFrom() and seq-iterator to use the new chunking behavior only in sequence and/or with a new chunked-iterator-seq to make it more explicit. The sequence over xf is new so no possible regression there, everything else would just be opt-in.

Comment by Rich Hickey [ 27/Mar/15 9:49 AM ]

push as is but leave unresolved, for perf tweaks

Comment by Alex Miller [ 27/Mar/15 10:15 AM ]

clj-1669-6 is identical to clj-1669-5 but removes two commented out debugging lines that were inadvertently included.

Comment by Alex Miller [ 18/May/15 9:47 AM ]

updated for beta3 numbers





[CLJ-1635] Make distinct/dedupe/interpose transducer tests play nicely with new reporting Created: 09/Jan/15  Updated: 20/Feb/15  Resolved: 20/Feb/15

Status: Closed
Project: Clojure
Component/s: None
Affects Version/s: None
Fix Version/s: Release 1.7

Type: Enhancement Priority: Minor
Reporter: Michael Blume Assignee: Unassigned
Resolution: Completed Votes: 0
Labels: test, transducers

Attachments: Text File clj-1635.patch    
Patch: Code and Test
Approval: Ok

 Description   

Fix interaction between CLJ-1601 (which introduced new transducers) and CLJ-1621 (which improved transducer tests) to improve test reporting for these new transducer arities as well.

Note from Alex M: I goofed these while rebasing CLJ-1601 after CLJ-1621 went in.

Patch: clj-1635.patch

Screened by: Alex Miller



 Comments   
Comment by Alex Miller [ 09/Jan/15 2:31 PM ]

My fault in the integration process! We'll try to get it fixed in 1.7. Thanks...





[CLJ-1621] Improve reporting in transducers generative test. Created: 21/Dec/14  Updated: 09/Jan/15  Resolved: 09/Jan/15

Status: Closed
Project: Clojure
Component/s: None
Affects Version/s: Release 1.7
Fix Version/s: Release 1.7

Type: Enhancement Priority: Minor
Reporter: Michael Blume Assignee: Unassigned
Resolution: Completed Votes: 0
Labels: transducers

Attachments: Text File transducer-reporting-v1.patch    
Patch: Code and Test
Approval: Ok

 Description   

If the transducers generative test breaks, you get output like this:

[java] {:test-var seq-and-transducer, :result #<ExceptionInfo clojure.lang.ExceptionInfo: Applied actions to coll as seq, sequence transducer, and into transducer and got different results. {:coll [-16 10 -8 8 -5], :actions map clojure.core$dec@782a4056,take 5,partition-by clojure.core$even_QMARK_@2200d281,partition-all 9,map clojure.core$inc@643b798d,drop 9,remove clojure.core$empty_QMARK_@4600f352,remove clojure.core$odd_QMARK_@32dd05af, :s #<ClassCastException java.lang.ClassCastException: clojure.lang.LazySeq cannot be cast to java.lang.Number>, :xs (), :xi [], :xt []}>, :seed 1419199634890, :failing-size 21, :num-tests 22, :fail [[-16 10 -8 8 -5] [{:desc map clojure.core$dec@782a4056, :xf #<core$map$fn__3669 clojure.core$map$fn__3669@28449652>, :seq #<core$partial$fn__3652 clojure.core$partial$fn__3652@506b8505>} {:desc take 5, :xf #<core$take$fn__3712 clojure.core$take$fn__3712@38934406>, :seq #<core$partial$fn__3652 clojure.core$partial$fn__3652@27ce0b6d>} {:desc partition-by clojure.core$even_QMARK_@2200d281, :xf #<core$partition_by$fn__5568 clojure.core$partition_by$fn__5568@5287c159>, :seq #<core$partial$fn__3652 clojure.core$partial$fn__3652@70961c7b>} {:desc partition-all 9, :xf #<core$partition_all$fn__5590 clojure.core$partition_all$fn__5590@3f869b0>, :seq #<core$partial$fn__3652 clojure.core$partial$fn__3652@6f99ed9f>} {:desc map clojure.core$inc@643b798d, :xf #<core$map$fn__3669 clojure.core$map$fn__3669@2f2c41d3>, :seq #<core$partial$fn__3652 clojure.core$partial$fn__3652@2fdbef8d>} {:desc drop 9, :xf #<core$drop$fn__3728 clojure.core$drop$fn__3728@4f7b4b50>, :seq #<core$partial$fn__3652 clojure.core$partial$fn__3652@214b9b5>} {:desc remove clojure.core$empty_QMARK_@4600f352, :xf #<core$filter$fn__3696 clojure.core$filter$fn__3696@6846d654>, :seq #<core$partial$fn__3652 clojure.core$partial$fn__3652@7df231c7>} {:desc remove clojure.core$odd_QMARK_@32dd05af, :xf #<core$filter$fn__3696 clojure.core$filter$fn__3696@5a8ce6dd>, :seq #<core$partial$fn__3652 clojure.core$partial$fn__3652@34ee9000>}]], :shrunk {:total-nodes-visited 32, :depth 12, :result #<ExceptionInfo clojure.lang.ExceptionInfo: Applied actions to coll as seq, sequence transducer, and into transducer and got different results. {:coll [0], :actions map clojure.core$inc@643b798d, :s (1), :xs (0), :xi [0], :xt [0]}>, :smallest [[0] [{:desc map clojure.core$inc@643b798d, :xf #<core$map$fn__3669 clojure.core$map$fn__3669@2f2c41d3>, :seq #<core$partial$fn__3652 clojure.core$partial$fn__3652@2fdbef8d>}]]}}
     [java]
     [java] ERROR in (seq-and-transducer) (core.clj:4566)
     [java] Uncaught exception, not in assertion.
     [java] expected: nil
     [java]   actual: clojure.lang.ExceptionInfo: Applied actions to coll as seq, sequence transducer, and into transducer and got different results.
     [java]  at clojure.core$ex_info.invoke (core.clj:4566)
     [java]     clojure.test_clojure.transducers$seq_and_transducer_same_result.invoke (transducers.clj:103)
     [java]     clojure.lang.AFn.applyToHelper (AFn.java:156)
...etc etc

This has a few problems:

  • when clojure functions are given as arguments, they're full object printouts, with classnames and memory addresses, this is kind of hard to read
  • the combination of the first problem found with the shrunk version means there's a lot of content to read
  • lack of pretty printing makes that content very hard to read
  • the traceback isn't actually that helpful – we know what failed already.

Approach: The attached patch encodes more descriptive info in the actions and does a better job of reporting the difference in an understandable manner:

[java] FAIL in (seq-and-transducer) (transducers.clj:135)
     [java] {:coll [0],
     [java]  :actions (->> coll (map inc)),
     [java]  :s (1),
     [java]  :xs (0),
     [java]  :xi [0],
     [java]  :xt [0]}

Patch: transducer-reporting-v1.patch

Screened by: Alex Miller






[CLJ-1606] Transducing an eduction finishes twice Created: 27/Nov/14  Updated: 09/Jan/15  Resolved: 09/Jan/15

Status: Closed
Project: Clojure
Component/s: None
Affects Version/s: Release 1.7
Fix Version/s: Release 1.7

Type: Defect Priority: Major
Reporter: Herwig Hochleitner Assignee: Unassigned
Resolution: Completed Votes: 0
Labels: transducers
Environment:

1.7.0-alpha4


Attachments: Text File CLJ-1606-2.patch     Text File CLJ-1606-3.patch     Text File CLJ-1606-4.patch     Text File CLJ-1606-5.patch     Text File CLJ-1606.patch    
Patch: Code and Test
Approval: Ok

 Description   
> (transduce (map identity)
             (fn
               ([s] (println "Finishing") s)
               ([s i] s))
             nil
             (eduction (map identity) []))
Finishing
Finishing
nil

Cause: transduce passes (xf f) into .reduce of Eduction, which calls transduce, causing completing xf to be called more than once.

Proposed: Eduction reduce should use (completing f) instead of f to isolate completion of inner xf from outer xf.

Patch: CLJ-1606-5.patch

Screened by: Alex Miller



 Comments   
Comment by Alex Miller [ 27/Nov/14 11:01 PM ]

identity is not a valid xf - changed to (map identity)

Comment by Ghadi Shayban [ 27/Nov/14 11:34 PM ]

identity is a valid though nonsensical transducer. fix & test added.

Comment by Ghadi Shayban [ 28/Nov/14 12:06 AM ]

Simple reproduction similar to into:

(transduce (map dec)
           (completing conj! persistent!)
           (transient [])
           (eduction (map inc) (range 6)))

;; ClassCastException clojure.lang.PersistentVector cannot be cast to clojure.lang.ITransientCollection

into doesn't use completing, and conj! has an arity that hides the problem.

Comment by Alex Miller [ 28/Nov/14 8:54 AM ]

I removed trailing whitespace in the patch so it applies cleanly.

Comment by Ghadi Shayban [ 14/Dec/14 11:16 PM ]

This patch is a little more subtle than I thought. Completion of the eduction's rfn needs to be handled separately from the "outer" transduce's xform. Patch coming.

Comment by Ghadi Shayban [ 14/Dec/14 11:32 PM ]

New patch with tests that completes the inner xform without completing the passed in rfn

Comment by Ghadi Shayban [ 15/Dec/14 1:19 AM ]

both -3 and -2 are equivalent. -3 is probably better stylistically.

Comment by Alex Miller [ 15/Dec/14 8:37 AM ]

Added CLJ-1606-4.patch - identical to -3, just fixed whitespace error.

Comment by Andy Fingerhut [ 08/Jan/15 6:09 PM ]

There are two identically named attachments here (containing -2). It looks like it isn't the one under consideration, but it might be nice to remove or rename to avoid the name conflict.

Comment by Ghadi Shayban [ 08/Jan/15 6:24 PM ]

Andy, not sure how to do that, but in any case I just added -5 clarifying language in the comment

Comment by Alex Miller [ 08/Jan/15 6:41 PM ]

Ghadi, that was super confusing. Did you just add a new -5 patch? The -4 patch has already been screened, and you have not removed the duplicate -2 patch so I don't get what the -5 is. Can we just delete the -5 and older -2 patches?

Comment by Andy Fingerhut [ 08/Jan/15 6:44 PM ]

Sorry for adding to the confusion. Ghadi, instructions for deleting patches are in the "Removing patches" section on this wiki page: http://dev.clojure.org/display/community/Developing+Patches

Comment by Ghadi Shayban [ 08/Jan/15 6:50 PM ]

Sorry. Fine by me, though permissions prevent me from deleting one of the patches.

As I read through the screened patch I just tried to clarify the wording. This:

;; NB (completing f) isolates completion of inner xfns from outer xfns
became:
;; NB (completing f) isolates completion of inner rf from outer rf

Feel free to nix that -5 patch if that's worthless

Comment by Alex Miller [ 08/Jan/15 7:12 PM ]

Gotcha. I will take care of the further changes later tonight.

In the future, please don't modify screened patches without letting me know.





[CLJ-1601] transducer arities for map-indexed, distinct, and interpose Created: 25/Nov/14  Updated: 09/Jan/15  Resolved: 09/Jan/15

Status: Closed
Project: Clojure
Component/s: None
Affects Version/s: None
Fix Version/s: Release 1.7

Type: Enhancement Priority: Major
Reporter: Stuart Halloway Assignee: Alex Miller
Resolution: Completed Votes: 0
Labels: transducers

Attachments: Text File clj-1601-2.patch     Text File clj-1601-3.patch     Text File clj-1601-4.patch     Text File clj-1601.patch     Text File clj-1601-transient-distinct.patch    
Patch: Code and Test
Approval: Ok

 Description   
  • with generative tests
  • with examples demonstrating performance

Performance: Details in comments, summary:

(def v (vec (concat (range 1000) (range 1000))))
(into [] (distinct v))            ;; 821.3 µs
(into [] (distinct) v)            ;; 388.2 µs
(into [] (interpose nil v))       ;; 316.0 µs
(into [] (interpose nil) v)       ;; 35.5 µs
(into [] (map-indexed vector v))  ;; 76.8 µs
(into [] (map-indexed vector) v)  ;; 49.4 µs

Patch: clj-1601-4.patch

Screening note: We could use transients to improve performance of the distinct impl, except checking containment in a transient set is broken per CLJ-700 (which is not currently in 1.7). I have a new patch and direction on CLJ-700 that could provide a way to solve that if we want to move it back and push this further. Or we could just wait and refactor when CLJ-700 does go in.

Screened by:



 Comments   
Comment by Alex Miller [ 25/Nov/14 11:54 AM ]

working on this

Comment by Alex Miller [ 25/Nov/14 4:22 PM ]

Initial patch with impls. Tests and perf still to do.

Comment by Alex Miller [ 27/Nov/14 7:09 AM ]

Perf tests, summarized in description:

user=> (use 'criterium.core)
nil
user=> (def v (vec (concat (range 1000) (range 1000))))
#'user/v
user=> (quick-bench (into [] (distinct v)))
WARNING: Final GC required 10.433088780213309 % of runtime
Evaluation count : 744 in 6 samples of 124 calls.
             Execution time mean : 821.339608 µs
    Execution time std-deviation : 11.351053 µs
   Execution time lower quantile : 811.901435 µs ( 2.5%)
   Execution time upper quantile : 837.972000 µs (97.5%)
                   Overhead used : 1.794010 ns
nil
user=> (quick-bench (into [] (distinct) v))
WARNING: Final GC required 10.78492057474076 % of runtime
Evaluation count : 14028 in 6 samples of 2338 calls.
             Execution time mean : 43.630656 µs
    Execution time std-deviation : 170.185825 ns
   Execution time lower quantile : 43.433193 µs ( 2.5%)
   Execution time upper quantile : 43.853959 µs (97.5%)
                   Overhead used : 1.794010 ns
				   
user=> (quick-bench (into [] (interpose nil v)))
WARNING: Final GC required 10.79555726490133 % of runtime
Evaluation count : 1914 in 6 samples of 319 calls.
             Execution time mean : 316.024853 µs
    Execution time std-deviation : 9.077484 µs
   Execution time lower quantile : 310.139273 µs ( 2.5%)
   Execution time upper quantile : 330.917486 µs (97.5%)
                   Overhead used : 1.794010 ns

Found 1 outliers in 6 samples (16.6667 %)
	low-severe	 1 (16.6667 %)
 Variance from outliers : 13.8889 % Variance is moderately inflated by outliers
nil
user=> (quick-bench (into [] (interpose nil) v))
WARNING: Final GC required 10.70401297525592 % of runtime
Evaluation count : 17022 in 6 samples of 2837 calls.
             Execution time mean : 35.592672 µs
    Execution time std-deviation : 560.066138 ns
   Execution time lower quantile : 35.252348 µs ( 2.5%)
   Execution time upper quantile : 36.553414 µs (97.5%)
                   Overhead used : 1.794010 ns

Found 1 outliers in 6 samples (16.6667 %)
	low-severe	 1 (16.6667 %)
 Variance from outliers : 13.8889 % Variance is moderately inflated by outliers
nil

user=> (quick-bench (into [] (map-indexed vector v)))
WARNING: Final GC required 12.45755646853723 % of runtime
Evaluation count : 7338 in 6 samples of 1223 calls.
             Execution time mean : 76.807691 µs
    Execution time std-deviation : 381.019170 ns
   Execution time lower quantile : 76.433202 µs ( 2.5%)
   Execution time upper quantile : 77.170733 µs (97.5%)
                   Overhead used : 1.794010 ns
nil
user=> (quick-bench (into [] (map-indexed vector) v))
WARNING: Final GC required 11.38700971837483 % of runtime
Evaluation count : 12474 in 6 samples of 2079 calls.
             Execution time mean : 49.458043 µs
    Execution time std-deviation : 620.716737 ns
   Execution time lower quantile : 48.995801 µs ( 2.5%)
   Execution time upper quantile : 50.229507 µs (97.5%)
                   Overhead used : 1.794010 ns
Comment by Alex Miller [ 17/Dec/14 1:50 PM ]

Updated based on comment from Christophe Grand that java.util.HashSet used in distinct impl had different hash/equality semantics than the set used with sequences.

Comment by Nikita Prokopov [ 21/Dec/14 6:13 AM ]

This can be further improved by using transient set instead of persistent one in distinct:

distinct with persistent set, w/o transducers:  904.932406 µs
distinct with transient set,  w/o transducers:  755.338598 µs
distinct with persistent set, with transducers: 452.170600 µs
distinct with transient set,  with transducers: 293.258473 µs

Only caveat is that transient sets do not support contains? for now (see CLJ-700). This can be solved by using (.contains ^clojure.lang.ITransientSet set key)

I’m not sure what’s the best way to attach patch to this, for now attaching a patch that can be applied on top of Alex changes (clj-1601-transient-distinct.patch).

Comment by Alex Miller [ 22/Dec/14 8:32 AM ]

Hey Nikita, I'd rather fix CLJ-700 and use the normal functions rather than what you've done in the patch, which is why I hadn't done this before. I'm waiting to check with Rich whether we'll do that in 1.7 or wait till next release.

Comment by Michael Blume [ 09/Jan/15 10:23 AM ]

1601-3 no longer applies cleanly to master, I've got a reroll that does, is it ok to attach it even though the ticket is marked 'screened'?

Comment by Alex Miller [ 09/Jan/15 10:27 AM ]

Updated tests to apply cleanly to current master in -4 patch.

Comment by Alex Miller [ 09/Jan/15 10:33 AM ]

Ha, didn't see your comment Michael! I was working on the same thing.





[CLJ-1600] calling hashCode on clojure.lang.LazyTransformer causes a StackOverflowError Created: 24/Nov/14  Updated: 09/Jan/15  Resolved: 09/Jan/15

Status: Closed
Project: Clojure
Component/s: None
Affects Version/s: Release 1.7
Fix Version/s: Release 1.7

Type: Defect Priority: Major
Reporter: Sam Ritchie Assignee: Unassigned
Resolution: Completed Votes: 0
Labels: transducers
Environment:

OS X 10.10.1, Macbook Pro,, Java 1.8.0_11, Clojure 1.7.0-alpha4


Attachments: Text File CLJ-1600-2.patch     Text File CLJ-1600.patch    
Patch: Code and Test
Approval: Ok

 Description   

Calling .hashCode on a an instance of clojure.lang.LazyTransformer causes a StackOverflowError:

user> (.hashCode (sequence (map identity) ["s"]))
StackOverflowError   clojure.lang.Util.hash (Util.java:161)

The trace is

Util.java:  161  clojure.lang.Util/hash
          LazyTransformer.java:  216  clojure.lang.LazyTransformer/hashCode
                     Util.java:  161  clojure.lang.Util/hash
          LazyTransformer.java:  216  clojure.lang.LazyTransformer/hashCode
                     Util.java:  161  clojure.lang.Util/hash
          LazyTransformer.java:  216  clojure.lang.LazyTransformer/hashCode
                     Util.java:  161  clojure.lang.Util/hash
          LazyTransformer.java:  216  clojure.lang.LazyTransformer/hashCode

Relevant lines:

https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/LazyTransformer.java#L212
https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/Util.java#L161

Cause: Looks like "seq" returns "this":

https://github.com/clojure/clojure/blob/master/src/jvm/clojure/lang/LazyTransformer.java#L55

This does NOT occur on an empty sequence, as clojure.core/sequence short-circuits.

Proposal: compute and cache hash and hasheq using same algorithm used in other seqs

Patch: CLJ-1600-2.patch

Screened by: Alex Miller



 Comments   
Comment by Ghadi Shayban [ 25/Nov/14 1:18 AM ]

Patch with hashcode calculation and caching similar to ASeq. Might be worthwhile hoisting that into its own hashSeq method.

Comment by Alex Miller [ 25/Nov/14 10:13 AM ]

What's here looks good. Can we hook into existing tests that verify equals/hashcode and equiv/hasheq equivalence?

Comment by Ghadi Shayban [ 25/Nov/14 1:24 PM ]

Test case added. Verified case was failing with SO prior to patch.





[CLJ-1572] into does not work with IReduceInit Created: 24/Oct/14  Updated: 10/Jan/15  Resolved: 10/Jan/15

Status: Closed
Project: Clojure
Component/s: None
Affects Version/s: Release 1.7
Fix Version/s: Release 1.7

Type: Defect Priority: Major
Reporter: Alex Miller Assignee: Unassigned
Resolution: Completed Votes: 0
Labels: transducers

Attachments: Text File clj-1572-2.patch     Text File clj-1572-3.patch     Text File clj-1572-4.patch     Text File CLJ-1572-alternative-POC.patch     Text File clj-1572.patch    
Patch: Code and Test
Approval: Ok

 Description   

This should work:

(into []
  (reify clojure.lang.IReduceInit
    (reduce [_ f start]
      (reduce f start (range 10)))))
IllegalArgumentException Don't know how to create ISeq from: user$eval5$reify__6
	clojure.lang.RT.seqFrom (RT.java:506)
	clojure.lang.RT.seq (RT.java:487)
	clojure.core/seq--seq--4091 (core.clj:135)
	clojure.core.protocols/seq-reduce (protocols.clj:30)
	clojure.core.protocols/fn--6422 (protocols.clj:42)
	clojure.core.protocols/fn--6369/f--6255--auto----G--6364--6382 (protocols.clj:13)
	clojure.core/reduce (core.clj:6469)
	clojure.core/into (core.clj:6550)

Cause: CollReduce only supports IReduce, not IReduceInit so when reduce calls into it, it falls back to trying to obtain a seq representation which fails.

Proposed: Extend CollReduce to IReduceInit and in the non-init arity, cast to IReduce. Also, now that CollReduce supports both IReduceInit and Iterable, a coll that implements both makes the path through CollReduce nondeterministic. transduce does an explicit check that prefers IReduceInit - the patch copies that approach to reduce as well.

Another consequence of this change is that since PersistentVector implements IReduce but throws on the non-init path, there are some test breakages. To address this, CLJ-1619 (which implements the non-init reduce) must be applied first.

Patch: clj-1572-4.patch
Depends on: CLJ-1619 being applied first



 Comments   
Comment by Alex Miller [ 24/Oct/14 10:40 AM ]

into calls reduce which calls into CollReduce. CollReduce extends to IReduce, but not to IReduceInit. If CollReduce were extended to IReduceInit for the arity it can support, into work as expected in the given example. Patch clj-1572.patch does this.

Comment by Ghadi Shayban [ 08/Nov/14 4:34 PM ]

It is also possible that core/reduce needs the same special casing of IReduceInit that transduce has to allow for a deterministic dispatch when transduce is called with (mapcat f), as mapcat calls reduce.

Comment by Stuart Halloway [ 10/Nov/14 11:02 AM ]

Can someone please expand on Ghadi's comment with an example of the problem?

Comment by Ghadi Shayban [ 10/Nov/14 11:14 AM ]

Example of something that is Iterable & ReduceInit:
https://github.com/ghadishayban/reducers/blob/master/src/ghadi/reducers.clj#L122-L128

Let's call that r/range in this example:
(transduce (mapcat r/range) + 0 [5 5 5 5 5])

The when the mapcat transducer encounters r/range, the inner reduce call will dispatch through CollReduce upon Iterable, rather than IReduceInit.

the inner call to reduce within cat:
https://github.com/clojure/clojure/blob/master/src/clj/clojure/core.clj#L7243

Comment by Alex Miller [ 12/Nov/14 12:55 PM ]

To restate the issue from Ghadi for my own sake:

The CollReduce protocol extends to IReduce, IReduceInit and Iterable. Because these are all interfaces, its possible for a custom coll to implement two or more of them. In that case, Clojure will arbitrarily pick which protocol impl is called - this can result in the Iterable version being called instead of IReduce/IReduceInit (which should be preferred).

transduce avoids this by explicitly checking for IReduceInit and preferring it over CollReduce.

Ghadi is suggesting that reduce should also make this preference (currently it does not).

Comment by Nicola Mometto [ 17/Nov/14 3:06 PM ]

If CollReduce could be direcly backed by the IReduce interface, this would remove the need for explicit IReduceInit checking at the callsite.

It's already possible to (defprotocol CollReduce :on-interface clojure.lang.IReduce ..), I'm proposing adding the ability to map the "reduce" method to the coll-reduce protocol-fn aswell and go with this solution

Comment by Alex Miller [ 17/Nov/14 3:21 PM ]

CollReduce extends to two interfaces (IReduceInit and Iterable) and for some impls this is ambiguous under the CollReduce protocol. The check in reduce and transduce is to force the choice of IReduceInit so it is not ambiguous. I think your suggestion re-introduces that issue? Or maybe I'm just not understanding what you mean.

Comment by Nicola Mometto [ 17/Nov/14 3:46 PM ]

Turns out defprotocol already has that capability via :on metadata field.

The attached patch is a proof of concept of my proposal, if there's interest in this approach I can fix the deftype/record/reify method parser to automatically pick the var name rather than having to specify the method name.

Comment by Nicola Mometto [ 17/Nov/14 3:52 PM ]

Ah, I see now the issue. Disregard my patch then.

Comment by Ghadi Shayban [ 14/Dec/14 11:58 AM ]

Note that unless this patch is applied, a plain reduce over an Eduction goes through the seq/iterator path of CollReduce, and not eduction's native IReduceInit path.

Comment by Ghadi Shayban [ 17/Dec/14 5:03 PM ]

with this patch + CLJ-1546

(reduce + [1 2 3]) doesn't work anymore, breaking a few tests.

Comment by Ghadi Shayban [ 17/Dec/14 5:16 PM ]

Should have left a bit more detail.
https://github.com/clojure/clojure/commit/ad7d9c46992cac0e812ce3dd47584c9bb2fda11f

This might not have anything to do with CLJ-1546, just happened to have them both applied. Seems like vectors are both IReduce+IReduceInit, but throw on the IReduce impl.

Vectors were made IReduce before IReduce was split into IReduceInit.

Comment by Nicola Mometto [ 17/Dec/14 5:19 PM ]

I've opened CLJ-1619 with a patch implementing the no-init arity of reduce for PersistentVector

Comment by Nicola Mometto [ 17/Dec/14 5:20 PM ]

An alternative fix would be to just make PersistentVectors IReduceInit rather than IReduce but I don't see the point in doing that since the implementation is trivial.

Comment by Ghadi Shayban [ 22/Dec/14 3:04 PM ]

Nicola, that is my impression, that Rich intended PersistentVector to be IReduceInit but not IReduce. But he changed it before that interface was split. Would still need some sort of way to handle the existing no-init case, which he mentioned was unfortunate at the conj.

Comment by Nicola Mometto [ 22/Dec/14 3:11 PM ]

Ghadi, what would the rationale be for PV not supporting the no-init arity? I'm not aware of any technical issues caused by my patch for CLJ-1619 but maybe you know about one?

Comment by Ghadi Shayban [ 22/Dec/14 10:58 PM ]

No I may just be confused.

Rubber-ducking aloud so that I can be corrected:

A call to init reduce with an 'init' supplied is unambiguous.

It's the responsibility of an IReduce to do what is appropriate with 'f', whereas with "improved" reduce and transduce (f) becomes the init. (c.c.reducers/reduce being the improved reduce)

IReduce implementations must preserve compatibility with core/reduce's docstring in the 0 and 1 arity cases.

If coll contains no
items, f must accept no arguments as well, and reduce returns the
result of calling f with no arguments. If coll has only 1 item, it
is returned and f is not called. If val is supplied, returns the
result of applying f to val and the first item in coll, then
applying f to that result and the 2nd item, etc. If coll contains no
items, returns val and f is not called.

A protocol's dispatch is non-deterministic when invoked upon things with multiple paths. One way to resolve the ambiguities in CollReduce is to extend CollReduce directly to any IReduce/IReduceInit impl and not rely upon friends like Iterable.

For example CLJ-1515 needs the same CollReduce extension as CLJ-1603's Iterable/Repeat/Cycle got.

(extend-protocol p/CollReduce
  clojure.lang.LongRange
  (coll-reduce [this f] (.reduce this f)
  ..

  clojure.lang.Cycle
  ...)
;; etc.
Comment by Nicola Mometto [ 23/Dec/14 4:36 AM ]

I feel like all those issues introduced by the non-deterministic dispatch of protocol functions in case of multiple available implementations, could (and should?) be solved by a prefer-method-like capability for protocols.
This way we could say have a bunch of hints like (prefer-dispatch CollReduce IReduce Iterable) and be done with it.





[CLJ-1571] Transducer of partition-by over take gives wrong answer Created: 20/Oct/14  Updated: 21/Oct/14  Resolved: 21/Oct/14

Status: Closed
Project: Clojure
Component/s: None
Affects Version/s: Release 1.7
Fix Version/s: Release 1.7

Type: Defect Priority: Critical
Reporter: Alex Miller Assignee: Rich Hickey
Resolution: Completed Votes: 1
Labels: transducers

Attachments: Text File 0001-CLJ-1571-fix-regression-introduced-by-43cc1854508d65.patch     Text File CLJ-1571.patch    
Approval: Ok

 Description   
(partition-by pos? (take 2 [-1 1]))
=> ((-1) (1))
(sequence (comp (take 2) (partition-by pos?)) [-1 1])
=> ([-1])


 Comments   
Comment by Nicola Mometto [ 21/Oct/14 7:49 AM ]

Given that it works fine when using transduce instead of sequence, the bug might be in LazyTransformer rather than in partition-by.

(into [] (comp (take 2) (partition-by pos?)) [-1 1])
=> [[-1] [1]]
Comment by Ghadi Shayban [ 21/Oct/14 9:21 AM ]

Patch fixes the test case, but needs eyes, I certainly may have broken something. This highlights the importance of CLJ-1554, something similar to the existing defequiv tests for reducers, but between #'into and #'sequence, also covering edge cases in reduced unwrapping.

Comment by Alex Miller [ 21/Oct/14 9:41 AM ]

Thanks Ghadi. This bug was found by the tests I wrote for CLJ-1554, so yes.

Comment by Nicola Mometto [ 21/Oct/14 9:53 AM ]

Applying this patch causes a regression in the lazyiness of sequence.
The lines that Ghadi removed for this patch were added by Rich in this commit https://github.com/clojure/clojure/commit/43cc1854508d655e58e377f84836ba128971f90c to address http://dev.clojure.org/jira/browse/CLJ-1497

Example of the regression:
current master:

user=>  (sequence (take 2) (map #(do (println (str "~" %)) %) (iterate inc 1)))
~1
~2
(1 2)

with this patch:

user=>  (sequence (take 2) (map #(do (println (str "~" %)) %) (iterate inc 1)))
~1
~2
~3
(1 2)
Comment by Nicola Mometto [ 21/Oct/14 10:03 AM ]

Patch 0001-CLJ-1571-fix-regression-introduced-by-43cc1854508d65.patch addresses this issue while preserving the current lazyness factor of `sequence`

Comment by Alex Miller [ 21/Oct/14 11:09 AM ]

Rich has a (different) patch for this on the way.

Comment by Alex Miller [ 21/Oct/14 1:16 PM ]

Fixed directly by Rich in commit https://github.com/clojure/clojure/commit/38d7572e4254afdd7f02b78095ccdb27065754d2





[CLJ-1569] transduce does not respect the init arity of transducers Created: 19/Oct/14  Updated: 07/Mar/16  Resolved: 20/Oct/14

Status: Closed
Project: Clojure
Component/s: None
Affects Version/s: Release 1.7
Fix Version/s: None

Type: Defect Priority: Minor
Reporter: Daniel James Assignee: Unassigned
Resolution: Declined Votes: 0
Labels: transducers


 Description   

Note: I initially raised this issue for discussion on the mailing list
https://groups.google.com/d/msg/clojure/uVKP4_0KMwQ/-oUJahvUarIJ

transduce and other transducible processes currently ignore the 'init' arity of transducers. The currently implementation of transduce takes the 'init' from the reducing function before being transformed by the transducer, rather the reducing function after being transformed.

The current implementation of transduce is equivalent to the following (simplified for exposition purposes):

Current implementation of transduce
(defn transduce
  ([xform f coll]
     (transduce xform f (f) coll))
  ([xform f init coll]
     (let [rf (xform f)]
       (rf (reduce rf init coll)))))

The arity 3 case uses (f) to construct the seed value of the reduction. The arity 4 case uses the explicitly provided seed, init.

I would like to propose an alternate implementation of transduce, one which makes use of the transducer when seeding the reduction.

Proposed implementation of transduce
(defn alt-transduce
  ([xform f coll]
     (let [rf (xform f)]
       (rf (reduce rf (rf) coll))))
  ([xform f init coll]
     (let [rf (xform
               (fn
                 ([] init)
                 ([result] (f result))
                 ([result input] (f result input))))]
       (rf (reduce rf (rf) coll)))))

Now, the arity 3 case uses (xform f) to construct the seed value of the reduction. The arity 4 case combines both f and init into a new reducing function that is given to xform. Both of these ensure that the init arity of the transducer is used.

As into is implemented in terms of transduce, it is also taken care of. However, sequence is separate, and would also have to be tweaked to respect the init arity.



 Comments   
Comment by Daniel James [ 19/Oct/14 1:24 PM ]

As a small addition, I just wanted to point out an example of where the current implementation raised curiosity:
https://groups.google.com/d/msg/clojure/M-13lRPfguc/IspgdpKDaGsJ

Comment by Alex Miller [ 20/Oct/14 9:12 AM ]

In transduce, the transducer is applied to the elements of the input and should not be entangled with the accumulation at all (either in initializing it or the act of accumulation). f is the final reducing function that deals with accumulation and initialization.

Comment by Daniel James [ 20/Oct/14 10:00 AM ]

Hi Alex,

I feel that you've misunderstood my proposal.

Could you explain how you consider

(defn init-with [x]
  (fn [rf]
    (fn
      ([] (rf (rf) x))
      ([result] (rf result))
      ([result input] (rf result input)))))

to be “entangled with the accumulation at all (either in initializing it or the act of accumulation).”

This seems like a completely legitimate transducer to me. It makes use of the init arity, while remaining oblivious to the accumulation.

Your explanation also seems to be at odds with

http://clojure.org/transducers

The inner function is defined with 3 arities used for different purposes:

  • Init (arity 0) - in most cases, this will just call the init arity on the nested transform xf, which will eventually call out to the transducing process to supply an initial value. It is also a place to establish the initial reducing state for the transducer.
Comment by Alex Miller [ 20/Oct/14 11:57 AM ]

By "entangling" I mean that in your alternate transduce you invoke the xform to obtain the initial value: ((xform f)) instead of (f). Transducers should not know about or be involved in the accumulating process.

The transducers page is in error and I will correct it (I wrote it; the error is mine).

Comment by Daniel James [ 20/Oct/14 3:25 PM ]

Ok, at the risk of belaboring the point (I have enough self-awareness to realized that I am probably about to do exactly that…) I feel that you are still missing something here.

Permit me to try one more time to explain my position.

Consider map

the map transducer
(defn map [f]
  (fn [rf]
    (fn
      ([] (rf))
      ([result] (rf result))
      ([result input] (rf result (f input))))))

It defines all three arities, init, step, and completion. It doesn’t have anything to do in init arity, and so the only thing it can do is “call the init arity on the nested transform rf, which will eventually call out to the transducing process.” (taken from your update to http://clojure.org/transducers)

Saying that transducers should not be involved in the accumulating process has the right spirit, but you are missing something. It is involved, but in a strictly constrained way. The transducer’s responsibility is to carefully thread the accumulator value around. Sure, it should not know what the value is, or what type it has, but it is still there. Every arity of map has access to it! In the init arity, map delegates to rf to construct it. In the completion arity, map has the result, but the only valid thing it can do with it is to pass it on to rf. Again, in the step arity, map has the result, and again the only legitimate thing it can do with it is to thread to through to rf.

Now consider the identity transducer:

the identity transducer
(def identity
  (fn [rf]
    ([] (rf))
    ([result] (rf result))
    ([result input] (rf result input))))

This is a transducer in its purest form. All it has to do is correctly thread the accumulation value around. It doesn’t and shouldn’t know any details of what that value is, nonetheless, it still has the responsibility of threading that value correctly.

In each arity the identity transducer does the ‘trivial’ thing. In my post to the mailing list, I illustrated three example of transducers that do something beyond the trivial thing in each of the three arities. (I’ll copy them here for completeness.)

non trivial threading of the accumulator in the init arity
(defn init-with
  [x]
  (fn [rf]
    (fn
      ([] (rf (rf) x))
      ([result] (rf result))
      ([result input]
         (rf result input)))))
non trivial threading of the accumulator in the completion arity
(defn complete-with
  [x]
  (fn [rf]
    (fn
      ([] (rf))
      ([result]
         (rf (rf result x)))
      ([result input]
         (rf result input)))))
non trivial threading of the accumulator in the step arity
(defn dupl
  []
  (fn [rf]
    (fn
      ([] (rf))
      ([result] (rf result))
      ([result input]
         (rf (rf result input)
             input)))))

I would consider all of these to be perfectly valid transducers. However, unless I’ve misunderstood, you appear to be taking issue with init-with. If so, I’m very curious as to why!

a closer look at the init arity of init-with
(defn init-with
  [x]
  (fn [rf]
    (fn
      ([] (rf (rf) x))
      ...

Rather than just delegating to (rf), it threads that value immediately into rf with (rf (rf) x). So I don’t agree at all that any of these, init-with, complete-with, or dupl, are “entangled” with the accumulation value or the accumulation process. They are completely oblivious to both its value and its type!

So, returning to transduce,

the first case of an alternate transduce
(defn alt-transduce
  ([xform f coll]
     (let [rf (xform f)]
       (rf (reduce rf (rf) coll))))
  ...

A valid transducer is one that threads the accumlation value correctly. Therefore, ((xform f)) is (f) threaded through xform. All the transducers in clojure.core have the trivial ([] (rf)), so ((xform f)) built from these core transducers degenerates into (identity (f)).
However, as transduce, into, and sequence never even invoke the init arity, it begs the question, why even require that transducers have that arity in the first place? Personally, I think that init arity is great as it enables a transducer such as init-with (while remaining stateless), but that requires transducible processes to actually make use of the init arity! Hence why I raised this issue.
It seems troubling to me that complete-with works perfectly fine in the current framework, yet init-with, its dual, does not.

I recognize that the various discussions around ‘typing transducers’ have made various approximations at elucidating the properties of transducers, but I feel strongly that the discussions around rank-2 polymorphism have some bearing on exactly this issue. In fact, it says rather a lot about correctly threading the accumulation value throught transducers without ever “entangling” it in the precise accumulation process of where a transducer is being used.

And on this, it appears that Rich Hickey agrees: “The rank-2 type in particular captures an important property.” (http://conscientiousprogrammer.com/blog/2014/08/07/understanding-cloure-transducers-through-types/#comment-1533318972) Maybe I’ve got him all wrong, but as of right now I’m pretty convinced I don’t. Still, I’m willing to be convinced otherwise

Comment by Alex Miller [ 20/Oct/14 10:03 PM ]

Rich asked me to decline the ticket because the init arity of the xform should not be involved in the reducing function accumulation.

Comment by Daniel James [ 20/Oct/14 10:34 PM ]

Ok, as you can guess I’m a little perplexed by that design choice, but I’ll accept it.

I’d appreciate any further insight you can offer on why this design choice has been taken.
Is the init arity simply a case of compatibility, despite it not being used? Is this a case of attempting to prevent the transducer writer from erroneously corrupting a transducible process? Is init-with actually actually considered to be an invalid transducer, and thus the only way to implement something equivalent would be as a stateful transducer?

Comment by Stephen Nelson [ 07/Mar/16 8:53 PM ]

I would appreciate a response to Daniel's question. Why is an init-arity required if it's never called?





[CLJ-1557] Nested reduced is broken Created: 09/Oct/14  Updated: 29/Jan/15  Resolved: 10/Oct/14

Status: Closed
Project: Clojure
Component/s: None
Affects Version/s: Release 1.7
Fix Version/s: Release 1.7

Type: Defect Priority: Critical
Reporter: Christophe Grand Assignee: Rich Hickey
Resolution: Completed Votes: 0
Labels: transducers

Attachments: File re-reduced.diff    
Patch: Code
Approval: Vetted

 Description   

Re-reduced from composed transformation functions:

  • re-wraps the Reduced when it should not (take)
  • forget to unwrap the Reduced (partition-by, partition-all)
; nested reduced
=> (transduce (comp (take 1)) conj [:a])
[:a]
=> (transduce (comp (take 1) (take 1)) conj [:a])
#<Reduced@65979031: [:a]>
=> (transduce (comp (take 1) (take 1) (take 1)) conj [:a])
#<Reduced@fcbc8d1: #<Reduced@60bea99a: [:a]>>
=> (transduce (comp (take 1) (take 1) (take 1) (take 1)) conj [:a])
#<Reduced@6e9915bb: #<Reduced@5c712302: #<Reduced@472b9f70: [:a]>>>
 
; problems not appearing in all contexts
; not ok with transduce
=> (transduce (comp (partition-by keyword?) (take 1)) conj [] [:a])
#<Reduced@5156c42e: [[:a]]>
; but ok with sequence
=> (sequence (comp (partition-by keyword?) (take 1)) [:a])
([:a])
; well, not always
=> (sequence (comp (partition-by keyword?) (take 1)  (partition-by keyword?) (take 1)) [:a])
ClassCastException clojure.lang.Reduced cannot be cast to clojure.lang.LazyTransformer  clojure.lang.LazyTransformer$Stepper$1.invoke (LazyTransformer.java:104)

See also: https://groups.google.com/d/msg/clojure-dev/cWzMS_qqgcM/7IAhzMKzVigJ



 Comments   
Comment by Ghadi Shayban [ 09/Oct/14 11:11 PM ]

Same with partition-all

(transduce (comp (take 1) (partition-all 3) (take 1)) conj [] (range 15))
 #<Reduced@84f8976: [[0]]>
Comment by Christophe Grand [ 10/Oct/14 5:50 AM ]

patch for take, partition-by and partition-all

Comment by Nicola Mometto [ 29/Jan/15 12:09 PM ]

ticket was marked resolved but not closed





[CLJ-1554] Need to expand tests to cover transducers Created: 07/Oct/14  Updated: 14/Nov/14  Resolved: 14/Nov/14

Status: Closed
Project: Clojure
Component/s: None
Affects Version/s: Release 1.7
Fix Version/s: Release 1.7

Type: Enhancement Priority: Critical
Reporter: Alex Miller Assignee: Alex Miller
Resolution: Completed Votes: 0
Labels: transducers

Attachments: Text File clj-1554-2.patch     Text File clj-1554-3.patch     Text File clj-1554-4.patch     Text File clj-1554-5.patch     Text File clj-1554.patch    
Patch: Code and Test
Approval: Ok

 Description   

Attached patch contains both some generative and example tests for transducers. The generative tests build a series of sequence functions (take 5, filter odd?, etc) and apply them to a random vector of numbers as seq transformations, sequence of transducer, into of transducer, and transduce of transducer. The results are compared.

Note: these tests depend on the patch in CLJ-1349 to run as tests.

Patch: clj-1554-5.patch



 Comments   
Comment by Fogus [ 24/Oct/14 1:44 PM ]

I downloaded and applied this patch and its dependent patch (1349) and ran the tests. The coverage is a good start and the approach of verifying results against results gathered from other approaches is important. One note of style is that the use of `doall` is inconsistent in the `apply-as-*` functions. i would recommend that at least one other person screen this patch as my grasp of test.check is tenuous.

Comment by Alex Miller [ 24/Oct/14 2:52 PM ]

Updated patch slightly to clean up the doall stuff.

Comment by Guangyu Zhang [ 01/Nov/14 2:55 PM ]

What is clojure.test.check? You require it but never use it. This namespace doesn't exist, so I can't do individual test by (require 'clojure.test-clojure.transducers).

The error message:
CompilerException java.io.FileNotFoundException: Could not locate clojure/test/check__init.class or clojure/test/check.clj on classpath., compiling:(clojure/test_clojure/transducers.clj:1:1)

The way I used to do individual test is described in http://dev.clojure.org/display/community/Developing+Patches.

But there is no error when I run 'mvn package'.

Comment by Alex Miller [ 01/Nov/14 3:13 PM ]

As noted in the description, this patch depends on CLJ-1349 to be applied first.

Comment by Alex Miller [ 01/Nov/14 3:23 PM ]

After you apply CLJ-1349 you will also need to rerun antsetup.sh as it adds new dependencies.

Comment by Guangyu Zhang [ 02/Nov/14 12:43 AM ]

I did what you say, but the error still exists.
I can pass this test via 'ant test-example', but I can not do individual test.

To reproduce this problem:
Apply CLJ-1349 and CLJ-1554
$ ./antsetup.sh
$ ant
$ java -cp test:clojure-1.7.0-master-SNAPSHOT.jar clojure.main
user=> (require 'clojure.test-clojure.transducers)
CompilerException java.io.FileNotFoundException: Could not locate clojure/test/check__init.class or clojure/test/check.clj on classpath., compiling:(clojure/test_clojure/transducers.clj:1:1)

This should work:
$ java -cp /Users/guangyu/.m2/repository/org/clojure/test.check/0.5.9/test.check-0.5.9.jar:/Users/guangyu/.m2/repository/org/clojure/test.generative/0.5.1/test.generative-0.5.1.jar:test:clojure.jar clojure.main
user=> (require 'clojure.test-clojure.transducers)
nil

Maybe the document (http://dev.clojure.org/display/community/Developing+Patches) needs to be updated.

Comment by Guangyu Zhang [ 02/Nov/14 12:46 AM ]

There is no need to require clojure.test.check . I remove it and nothing happens.

Comment by Alex Miller [ 03/Nov/14 10:46 AM ]

That page is out of date with respect to running tests with either test.generative or test.check (which doesn't actually exist yet until CLJ-1349).

More complete recipe:

1. Apply CLJ-1349 and CLJ-1554 patches
2. ./antsetup.sh
3. ant
4. java -cp `cat maven-classpath`:target/classes:src:test clojure.main
5. (require 'clojure.test-clojure.transducers)
6. (clojure.test/run-tests 'clojure.test-clojure.transducers)

Works for me.

Confusingly, the patch in this test uses test.check, which is a generative test but run in the build (post CLJ-1349) as an example-based test. Stu and I are still talking about the best way to address that. One issue is that test.generative tests are time-based for intensity while test.check is iteration-based.

I will update the patch to remove the require of test.check.

Comment by Alex Miller [ 03/Nov/14 11:14 AM ]

I updated that testing page to cover test.generative as well.

Comment by Stuart Halloway [ 10/Nov/14 12:15 PM ]

Alex, would like to discuss two possible changes

  • make fbind create a symbolic rep of the work to do, so that failure messages are easier to read
  • whitelist the exceptions we expect, and check with a predicate in seq-and-transducer-same-result
Comment by Alex Miller [ 12/Nov/14 12:08 PM ]

Added new patch that whitelists only IllegalArgumentException and ClassCastException as the possible allowed exceptions in the transducer tests (they may vary between the transducer and non-transducer form).

The fbind does build a semantic description already in the :desc key which is used on error. Here's an example error - see the :actions key. That will be a list of the transformations applied (although shrinking often minimizes that list):

[java] Testing clojure.test-clojure.transducers
     [java] {:test-var seq-and-transducer, :result #<ExceptionInfo clojure.lang.ExceptionInfo: Applied actions to coll as seq, sequence transducer, and into transducer and got different results. {:coll [3 5 5 5 -2], :actions take 6, :s (3 5 5 5 -2), :xs (3 5 5), :xi [3 5 5], :xt [3 5 5]}>, :seed 1415806766835, :failing-size 6, :num-tests 7, :fail [[3 5 5 5 -2] [{:desc take 6, :xf #<core$take$fn__4550 clojure.core$take$fn__4550@4d186c57>, :seq #<core$partial$fn__4490 clojure.core$partial$fn__4490@44709ca4>}]], :shrunk {:total-nodes-visited 46, :depth 10, :result #<ExceptionInfo clojure.lang.ExceptionInfo: Applied actions to coll as seq, sequence transducer, and into transducer and got different results. {:coll [0 0], :actions take 2, :s (0 0), :xs (0), :xi [0], :xt [0]}>, :smallest [[0 0] [{:desc take 2, :xf #<core$take$fn__4550 clojure.core$take$fn__4550@5b938615>, :seq #<core$partial$fn__4490 clojure.core$partial$fn__4490@556733e4>}]]}}




[CLJ-1553] Parallel transduce Created: 07/Oct/14  Updated: 15/May/17

Status: Open
Project: Clojure
Component/s: None
Affects Version/s: Release 1.7
Fix Version/s: None

Type: Feature Priority: Major
Reporter: Alex Miller Assignee: Unassigned
Resolution: Unresolved Votes: 11
Labels: transducers


 Description   

Consider how to create a parallel path for transducers, similar to reducers fold.






[CLJ-1552] Consider kv support for transducers (similar to reducers fold) Created: 07/Oct/14  Updated: 15/May/17

Status: Open
Project: Clojure
Component/s: None
Affects Version/s: Release 1.7
Fix Version/s: None

Type: Feature Priority: Major
Reporter: Alex Miller Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: transducers


 Description   

In reducers, fold over a map has special support for kv. Consider whether/how to add this for transducers.



 Comments   
Comment by Marshall T. Vandegrift [ 16/Dec/14 11:13 AM ]

We don't have a JIRA "unvote" feature, but I'd like to register my vote against this proposed enhancement. As a heavy user of clojure.core.reducers, I consider the switch to k-v semantics when reducing a map to be a significant mis-feature. As only an initial transformation function applied directly to a map is able to receive the k-v semantics (a limitation I can’t see how would not carry over to transducers), this behavior crops up most frequently when re-ordering operations and discovering that an intermediate map has now caused an airity error somewhere in the middle of a chain of threaded transformations. I’ve never found cause to invoke it intentionally.

Comment by Ghadi Shayban [ 21/Jan/16 9:17 PM ]

Marshall, there really isn't a proposed enhancement, yet. So there's nothing to be against! Your input is valuable. (Regarding c.c.reducers, that is a separate problem – yes that behavior is surprising)

Considering kv-support for transducers:
Is it useful to have some functions that transform reduce-kv style reducing functions (fn [result k v])?

Ignore naming:
map-key
map-val
map-keyval
filter-*

These could be mechanically generated. You wouldn't have to have a kv-version for every transducer currently in core. Some like map or filter could specifically apply to the key and ignore the val, or v.v.

Some things like map's transducer would be arity-incompatible (map's transducer has a varargs arity).





[CLJ-1551] Consider transducer support for primitives Created: 07/Oct/14  Updated: 28/Jun/17

Status: Open
Project: Clojure
Component/s: None
Affects Version/s: Release 1.7
Fix Version/s: Backlog

Type: Feature Priority: Major
Reporter: Alex Miller Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: transducers

Approval: Vetted

 Description   

Need to consider how we can support primitives for transducers. In particular it may be that IFn needs overloading for L/D in addition to O.






[CLJ-1512] Create volatile box for managing state Created: 25/Aug/14  Updated: 07/Oct/14  Resolved: 03/Sep/14

Status: Closed
Project: Clojure
Component/s: None
Affects Version/s: Release 1.7
Fix Version/s: Release 1.7

Type: Enhancement Priority: Major
Reporter: Rich Hickey Assignee: Rich Hickey
Resolution: Completed Votes: 0
Labels: transducers

Attachments: File volatile2.diff     File volatile3.diff    
Patch: Code and Test
Approval: Ok

 Description   

Motivation:

Clojure needs a faster variant of Atom for managing state inside transducers. That is, Atoms do the job, but they provide a little too much capability for the purposes of transducers. Specifically the compare and swap semantics of Atoms add too much overhead. Therefore, it was determined that a simple volatile ref type would work to ensure basic propagation of its value to other threads and reads of the latest write from any other thread. While updates are subject to race conditions, access is controlled by JVM guarantees.

Solution overview: Create a concrete type in Java, akin to clojure.lang.Box, but volatile inside supports IDeref, but not watches etc.

API:

(volatile! x) ;;ctor
(vreset! vol newval) ;;like reset
(vswap! vol f args) ;;same shape as swap!, but MACRO over vreset!

Patch: volatile3.diff

Screened by: fogus



 Comments   
Comment by Alex Miller [ 25/Aug/14 9:11 AM ]

Dumb benchmark before/after...

java -cp target/classes -Xmx512m -server clojure.main
(def t (take 1000000))
(def v (doall (range 1000000)))
(defn bench [t v]
  (time (into [] t v)))
(dotimes [_ 30] (bench t v))

before - 29-32 ms after warmup
after - 22-23 ms after warmup

Comment by Alex Miller [ 25/Aug/14 9:12 AM ]

From Stu H elsewhere:

Three questions:
1) Should we keep volatile? in the public API?
2) Should we work in terms of IVolatile interface (guessing no)
3) Do we need a CLJS version of these APIs?

Comment by Alex Miller [ 25/Aug/14 9:13 AM ]

1. We have many tickets requesting predicates over types that are "internal" and generally I find these to be helpful. They also can help in making core more portable to cljs (maybe those fns would fall back to atoms in cljs?).
2. We have tickets requesting the equivalent of this for IAtom (CLJ-803) etc. I don't think an interface adds any value to us here though. There seems to be some requests for this kind of passthrough interface from tooling as a decoupling point. Not putting my finger on those discussions but I know I've heard this, maybe on the mailing list.
3. I think yes if that allows us to be more efficient than whatever is being done now. Not obvious to me.

Comment by Nicola Mometto [ 25/Aug/14 9:40 AM ]

Why is vswap! a macro?

Comment by Ambrose Bonnaire-Sergeant [ 26/Aug/14 8:04 AM ]

An IAtom conversation: https://groups.google.com/forum/#!searchin/clojure-dev/iatom/clojure-dev/y5QoMqd44Lc/y4YmW09blk0J

Comment by Max Penet [ 26/Aug/14 10:28 AM ]

the vswap! macro is probably for performance reasons (the main motivation of this code to begin with), to avoid using apply or unrolling tons of arities

Comment by Nicola Mometto [ 26/Aug/14 1:07 PM ]

If that is the only reason, why can't it be a regular fn + :inline metadata?

Comment by Jozef Wagner [ 27/Aug/14 3:50 AM ]

why the bang in the name of volatile! function? If the reason is to warn users that this is an 'expert only' stuff, I suggest to use a verbose name instead, e.g. volatile-reference. (This will also be consistent with approach chosen in the names of volatile-mutable and unsynchronized-mutable hints.)

Comment by Rich Hickey [ 27/Aug/14 6:37 AM ]

Can you please lift the with-meta stuff out of the syntax-quote?
Actually, if volatile! ctor returned a type-hinted value that extra hinting might not even be needed. Let's do both for now.

Also the type hint on the volatile? arg makes no sense - it's a predicate asking if something is a volatile.

Comment by Alex Miller [ 28/Aug/14 9:05 AM ]

Made changes as requested.

Comment by Fogus [ 29/Aug/14 11:01 AM ]

I downloaded the patch and applied to latest master. I ran the isolated tests and the full test suite and also ensured that the patch didn't add any reflection warnings. I then modified the ticket description to add a little more context and motivation (for future readers). The code is straight-forward and clean.

Comment by Alex Miller [ 29/Aug/14 4:31 PM ]

Updated to volatile3.diff to address offline comment from Rich.





[CLJ-1511] stack overflow when comparing sequence results Created: 24/Aug/14  Updated: 07/Oct/14  Resolved: 27/Aug/14

Status: Closed
Project: Clojure
Component/s: None
Affects Version/s: Release 1.7
Fix Version/s: Release 1.7

Type: Defect Priority: Critical
Reporter: Chhi'mèd Künzang Assignee: Unassigned
Resolution: Completed Votes: 0
Labels: transducers
Environment:

OS X 10.9.4


Attachments: Text File 0001-provide-working-implementations-for-LazyTransform-eq.patch    
Patch: Code and Test
Approval: Ok

 Description   

Comparing sequences created with sequence causes a stack overflow when used as first argument to =.

Consider this transducer:

user=> (def map-inc (map inc))
#'user/map-inc

When creating a sequence and comparing with expected results, it works fine as the second argument to the comparison:

user=> (= (range 1 11) (sequence map-inc (range 10)))
true

But a stack overflow occurs when the order of arguments is reversed:

user=> (= (sequence map-inc (range 10)) (range 1 11))

StackOverflowError   clojure.lang.LazyTransformer.equals (LazyTransformer.java:202)
user=> (clojure.stacktrace/print-stack-trace *e 10)
java.lang.StackOverflowError: null
 at clojure.lang.LazyTransformer.equiv (LazyTransformer.java:185)
    clojure.lang.LazyTransformer.equals (LazyTransformer.java:202)
    clojure.lang.LazyTransformer.equiv (LazyTransformer.java:185)
    clojure.lang.LazyTransformer.equals (LazyTransformer.java:202)
    clojure.lang.LazyTransformer.equiv (LazyTransformer.java:185)
    clojure.lang.LazyTransformer.equals (LazyTransformer.java:202)
    clojure.lang.LazyTransformer.equiv (LazyTransformer.java:185)
    clojure.lang.LazyTransformer.equals (LazyTransformer.java:202)
    clojure.lang.LazyTransformer.equiv (LazyTransformer.java:185)
    clojure.lang.LazyTransformer.equals (LazyTransformer.java:202)
nil

The error persists, even if the sequence is forced with doall:

user=> (= (doall (sequence map-inc (range 10))) (doall (range 1 11)))

StackOverflowError   clojure.lang.LazyTransformer.equiv (LazyTransformer.java:185)

It does work as expected, however, if the sequence is converted to a vector:

user=> (= (vec (sequence map-inc (range 10))) (range 1 11))
true


 Comments   
Comment by Nicola Mometto [ 25/Aug/14 4:31 AM ]

Patch provides equiv/equals implementations for LazyTransform based on ASeq equiv/equals





[CLJ-1451] Add take-until Created: 20/Jun/14  Updated: 15/May/17

Status: Open
Project: Clojure
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Feature Priority: Major
Reporter: Alexander Taggart Assignee: Unassigned
Resolution: Unresolved Votes: 10
Labels: transducers

Attachments: Text File 0001-CLJ-1451-add-take-until.patch     Text File 0002-CLJ-1451-add-drop-until.patch     Text File 0003-let-take-until-and-drop-until-return-transducers.patch     Text File CLJ-1451-drop-until.patch     Text File clj-1451.patch     Text File CLJ-1451-take-until.patch    
Approval: Triaged

 Description   

Discussion: https://groups.google.com/d/topic/clojure-dev/NaAuBz6SpkY/discussion

It comes up when I would otherwise use (take-while pred coll), but I need to include the first item for which (pred item) is false.

(take-while pos? [1 2 0 3]) => (1 2)
(take-until zero? [1 2 0 3]) => (1 2 0)

Patch: clj-1451.patch

  • Includes transducer arity of take-until
  • Includes inclusion in transducer generative tests


 Comments   
Comment by Alex Miller [ 20/Jun/14 10:21 AM ]

Patch welcome (w/tests).

Comment by Alexander Taggart [ 20/Jun/14 2:00 PM ]

Impl and tests for take-until and drop-until, one patch for each.

Comment by Jozef Wagner [ 20/Jun/14 3:01 PM ]

Please change :added metadata to "1.7".

Comment by Alexander Taggart [ 20/Jun/14 3:12 PM ]

Updated to :added "1.7"

Comment by John Mastro [ 21/Jun/14 6:26 PM ]

I'd like to propose take-through and drop-through as alternative names. I think "through" communicates more clearly how these differ from take-while and drop-while.

Comment by Andy Fingerhut [ 06/Aug/14 2:27 PM ]

Both patches CLJ-1451-drop-until.patch and CLJ-1451-take-until.patch dated Jun 20 2014 no longer apply cleanly to latest Clojure master due to some changes committed earlier today. I haven't checked whether they are straightforward to update, but would guess that they merely require updating a few lines of diff context.

See the section "Updating stale patches" at http://dev.clojure.org/display/community/Developing+Patches for suggestions on how to update patches.

Comment by Ghadi Shayban [ 13/Nov/14 11:19 PM ]

Would be nice to cover the transducer case too.

Comment by Michael Blume [ 13/Nov/14 11:54 PM ]

rerolled patches

Comment by Michael Blume [ 14/Nov/14 12:11 AM ]

Covered transducer case =)

Comment by Michael Blume [ 14/Nov/14 12:12 AM ]

Actually I like take/drop-through as well

Comment by Ghadi Shayban [ 16/Nov/14 12:41 PM ]

Michael, no volatile/state is necessary in the transducer, like take-while. Just wrap in 'reduced to terminate

Comment by Michael Blume [ 17/Dec/14 6:47 PM ]

a) you're clearly right about take-until

b) seriously I don't know what I was thinking with my take-until implementation, I'm going to claim lack of sleep.

c) I'm confused about how to make drop-until work without a volatile

Comment by Michael Blume [ 18/Dec/14 1:52 AM ]

Ghadi and I discussed this and couldn't think of a use case for drop-until. Are there any?

Here's a new take-until patch, generative tests included.

Open questions:

Is take-until a good name? My biggest concern is that take-until makes it sound like a slight modification of take, but this function reverses the sense of the predicate relative to take.

Comment by Andy Fingerhut [ 08/Jan/15 6:06 PM ]

Michael, while JIRA can handle multiple attachments for the same ticket with the same name, it can get confusing for people trying to determine which one with the same name is meant. Could you remove or rename one of your identically-named attachments? Instructions for deleting patches are in the "Removing patches" section on this wiki page: http://dev.clojure.org/display/community/Developing+Patches

Comment by Alex Miller [ 11/Mar/16 2:49 PM ]

The patch was slightly stale so I updated to apply to master, but it's almost identical. Attribution retained.

Marked as prescreened.

Comment by Ghadi Shayban [ 29/Jun/16 9:01 PM ]

I feel like this is superceded by CLJ-1906

Comment by Ghadi Shayban [ 28/Oct/16 10:56 AM ]

And this is definitely superseded by `halt-when`

Comment by Alex Miller [ 28/Oct/16 2:11 PM ]

It's not lazy but this is one way to write take-until with halt-when:

(defn take-until [p s] (transduce (halt-when p (fn [r h] (conj r h))) conj [] s))
Comment by Steve Miner [ 28/Oct/16 3:00 PM ]

I wanted to suggest: `(sequence (halt-when p conj) s)` but sequence doesn't support stopping short on a reduced value so that won't work.

Comment by Alex Miller [ 28/Oct/16 3:02 PM ]

Yeah, halt-when is a little tricky to use in transducible contexts other than transduce.





[ASYNC-183] Completion arity of transducer is called twice Created: 20/Jan/17  Updated: 13/Feb/17

Status: Open
Project: core.async
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Major
Reporter: Jozef Wagner Assignee: Unassigned
Resolution: Unresolved Votes: 0
Labels: chan, transducers


 Description   

completion arity (1) of a transducer function is called twice in a channel

(let [xf (fn [rf]
           (fn
             ([] (println "INIT") (rf))
             ([result] (println "COMPLETING") (rf result))
             ([result input] (println "STEP") (rf result input))))
      c (chan 10 xf)]
  (close! c)
  (println "RESULT" (<!! c)))

will print

COMPLETING
COMPLETING
RESULT nil

According to https://clojure.org/reference/transducers, it is probably a bug:

> A completing process must call the completion operation on the final accumulated value exactly once

Looks like completing fn is called at there places in core.async: https://github.com/clojure/core.async/blob/master/src/main/clojure/cljs/core/async/impl/channels.cljs#L122 https://github.com/clojure/core.async/blob/master/src/main/clojure/cljs/core/async/impl/channels.cljs#L146






[ASYNC-129] Channels with transducer using reduced don't work as intended Created: 09/Jun/15  Updated: 13/Feb/17

Status: Open
Project: core.async
Component/s: None
Affects Version/s: None
Fix Version/s: None

Type: Defect Priority: Major
Reporter: Leon Grapenthin Assignee: Ghadi Shayban
Resolution: Unresolved Votes: 0
Labels: chan, transducers
Environment:

CLJ 1.7.0-RC1, (CLJS not tested)



 Description   
(def ch (chan 1 (take 2)))

(put! ch 1)
(put! ch 2)
(put! ch 3)

(take! ch identity)

ClassCastException clojure.lang.PersistentVector cannot be cast to java.util.concurrent.locks.Lock clojure.core.async.impl.channels.ManyToManyChannel (channels.clj:55)

This does not happen if a take is made before the first put so that the buffer size fits. The problem doesn't seem to be related only to the buffer size though.

(def ch (chan 1 (take-while true?)))

(put! ch true)
(put! ch false)
(put! ch false)

(take! ch identity)

ClassCastException clojure.lang.PersistentVector cannot be cast to java.util.concurrent.locks.Lock clojure.core.async.impl.channels.ManyToManyChannel (channels.clj:55)






Generated at Tue Oct 23 22:32:10 CDT 2018 using JIRA 4.4#649-r158309.