* Support Iterable in for-each @ 2014-01-10 18:45 Matthieu Vachon 2014-01-10 19:24 ` Per Bothner 0 siblings, 1 reply; 11+ messages in thread From: Matthieu Vachon @ 2014-01-10 18:45 UTC (permalink / raw) To: kawa Hi Per, I was wondering if you think it would be possible for the `for-each` methods and friends to accept directly a Java `Iterable` object. That would greatly ease Java usage since it would not be necessary in a lot of cases to transform an `Iterable` to a native list. However, I fear that it would not be that easy because maybe a lot of stuff relies on car/cdr. But we could make them compatible with `Iterable` though, where `car` returns first element from `Iterable` object and `cdr` returns an `Iterable` representing the rest elements and for a single element list, returns maybe an empty `Iterable`. But this would implies some more logic changes on `null?` and maybe other methods so it's possibly far-fetched and potentially a BC break (I don't think so but it may be the case). Of course, I could have my specialized function of `for-each` and like to do the job, but I think having "native" support if possible is always better. Had you had some thoughts on this subject before? Regards, Matt ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Support Iterable in for-each 2014-01-10 18:45 Support Iterable in for-each Matthieu Vachon @ 2014-01-10 19:24 ` Per Bothner 2014-01-10 21:04 ` Jamison Hope 2015-02-27 2:25 ` Per Bothner 0 siblings, 2 replies; 11+ messages in thread From: Per Bothner @ 2014-01-10 19:24 UTC (permalink / raw) To: Matthieu Vachon, kawa On 01/10/2014 10:45 AM, Matthieu Vachon wrote: > Hi Per, > > I was wondering if you think it would be possible for the `for-each` > methods and friends to accept directly a Java `Iterable` object. > > That would greatly ease Java usage since it would not be necessary in > a lot of cases to transform an `Iterable` to a native list. However, I > fear that it would not be that easy because maybe a lot of stuff > relies on car/cdr. Some things to keep in mind: * map and for-each are inlined by Kawa. We don't want to gove this up. * Using an Iterable implies using an Iterator, which implies object allocation. So that would add overhead. Iterating over an Iterable is a standard idiom, so it is possible Hotspot can do some optimization in this case. Still, I wouldn't count on it. * It is possible to come up with some iteration protocol that at least avoids object allocation for Kawa lists and vectors, and perhaps falls back to Iterator in the generic case. However, I haven't figured out a way to do so without 3 method calls per iteration step. (The problem is for a list the "state" variable is an object (a pair); for a vector it is an index. To avoid heap allocation the state needs to be one or more local variables. Thus for each step you may need to update an object and/or an int, plus you need to extract the next value.) It's easy if we're willing to accept allocating an Iterator object in the case of lists. As an exampSee the "Iteration" section of: http://www.gnu.org/software/kawa/api/gnu/lists/package-summary.html * Scheme also has vector-for-each, string-for-each, etc. It would be weird to make for-each generic. I guess one could add list-for-each as the specialized version and for-each as the generic version. * As I may have mentioned, I have some idea for a new iteration facility. (It is related to pattern matching.) It's taking longer than I'd like to get to it (because it depends on pattern matching working first), but we may not want too many changes until that is ready. Though a "generic for-each" is somewhat orthogonal. > But we could make them compatible with `Iterable` though, where `car` > returns first element from `Iterable` object and `cdr` returns an > `Iterable` representing the rest elements and for a single element > list, returns maybe an empty `Iterable`. But this would implies some > more logic changes on `null?` and maybe other methods so it's possibly > far-fetched and potentially a BC break (I don't think so but it may be > the case). Plus it's tricky to do this efficiently. I really don't want cdr to do object allocation. (This is one of my concerns about SRFI-101.) > Of course, I could have my specialized function of `for-each` and like > to do the job, but I think having "native" support if possible is > always better. > > Had you had some thoughts on this subject before? Of course :-) -- --Per Bothner per@bothner.com http://per.bothner.com/ ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Support Iterable in for-each 2014-01-10 19:24 ` Per Bothner @ 2014-01-10 21:04 ` Jamison Hope 2014-01-10 21:20 ` Per Bothner 2014-01-10 21:27 ` Per Bothner 2015-02-27 2:25 ` Per Bothner 1 sibling, 2 replies; 11+ messages in thread From: Jamison Hope @ 2014-01-10 21:04 UTC (permalink / raw) To: kawa@sourceware.org list On Jan 10, 2014, at 2:24 PM, Per Bothner <per@bothner.com> wrote: > On 01/10/2014 10:45 AM, Matthieu Vachon wrote: >> Hi Per, >> >> I was wondering if you think it would be possible for the `for-each` >> methods and friends to accept directly a Java `Iterable` object. >> >> That would greatly ease Java usage since it would not be necessary in >> a lot of cases to transform an `Iterable` to a native list. However, I >> fear that it would not be that easy because maybe a lot of stuff >> relies on car/cdr. I've done this in the past by writing my own iterator-for-each, iterable-for-each, array-for-each, etc. They don't convert to lists, they just make the right calls for whatever type. For example, (define (enumeration-for-each f::procedure enum::java.util.Enumeration) (let loop () (when (enum:hasMoreElements) (f (enum:nextElement)) (loop)))) These functions are pretty straightforward to write, but I agree that it would be nice if they were Kawa built-ins. Deciding the best container type for *-map return values might tricky, though. > Some things to keep in mind: > > * map and for-each are inlined by Kawa. We don't want to gove this up. > > * Using an Iterable implies using an Iterator, which implies object > allocation. So that would add overhead. Iterating over an Iterable > is a standard idiom, so it is possible Hotspot can do some optimization > in this case. Still, I wouldn't count on it. This is more egregious for for-each than for map, since map is already allocating cons pairs to hold the result. > * It is possible to come up with some iteration protocol that > at least avoids object allocation for Kawa lists and vectors, and > perhaps falls back to Iterator in the generic case. However, I haven't > figured out a way to do so without 3 method calls per iteration step. > (The problem is for a list the "state" variable is an object (a pair); > for a vector it is an index. To avoid heap allocation the state > needs to be one or more local variables. Thus for each step you may need > to update an object and/or an int, plus you need to extract the next > value.) I count two: Iterator#hasNext() and Iterator#next(). What's the third method call? Just the invocation of the passed procedure? > It's easy if we're willing to accept allocating an Iterator object > in the case of lists. As an exampSee the "Iteration" section of: > http://www.gnu.org/software/kawa/api/gnu/lists/package-summary.html > > * Scheme also has vector-for-each, string-for-each, etc. It would be > weird to make for-each generic. I guess one could add list-for-each > as the specialized version and for-each as the generic version. For Scheme, my vote would be to add new functions to Kawa's standard library with similar (predictable) names, perhaps: (array-for-each f::procedure arr::object) ;; is there an array pseudo-type? (enumeration-for-each f::procedure enum::java.util.Enumeration) (iterable-for-each f::procedure it::java.lang.Iterable) (iterator-for-each f::procedure iter::java.util.Iterator) And then maybe a generic-for-each which dispatches to the correct function depending upon the type of the second argument. A user can then rename generic-for-each if desired using the standard library import/rename mechanism. > * As I may have mentioned, I have some idea for a new iteration > facility. (It is related to pattern matching.) It's taking > longer than I'd like to get to it (because it depends on pattern > matching working first), but we may not want too many changes > until that is ready. Though a "generic for-each" is somewhat > orthogonal. We've been getting hints about this pattern stuff for quite a while now, Per. :-) > >> But we could make them compatible with `Iterable` though, where `car` >> returns first element from `Iterable` object and `cdr` returns an >> `Iterable` representing the rest elements and for a single element >> list, returns maybe an empty `Iterable`. But this would implies some >> more logic changes on `null?` and maybe other methods so it's possibly >> far-fetched and potentially a BC break (I don't think so but it may be >> the case). > > Plus it's tricky to do this efficiently. I really don't want cdr > to do object allocation. (This is one of my concerns about SRFI-101.) > >> Of course, I could have my specialized function of `for-each` and like >> to do the job, but I think having "native" support if possible is >> always better. >> >> Had you had some thoughts on this subject before? > > Of course :-) It's probably shorter to come up with a list of topics you have NEVER considered, isn't it? -J -- Jamison Hope The PTR Group www.theptrgroup.com ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Support Iterable in for-each 2014-01-10 21:04 ` Jamison Hope @ 2014-01-10 21:20 ` Per Bothner 2014-01-10 21:27 ` Jamison Hope 2014-01-10 21:27 ` Per Bothner 1 sibling, 1 reply; 11+ messages in thread From: Per Bothner @ 2014-01-10 21:20 UTC (permalink / raw) To: Jamison Hope, kawa@sourceware.org list On 01/10/2014 01:04 PM, Jamison Hope wrote: > On Jan 10, 2014, at 2:24 PM, Per Bothner <per@bothner.com> wrote: >> * It is possible to come up with some iteration protocol that >> at least avoids object allocation for Kawa lists and vectors, and >> perhaps falls back to Iterator in the generic case. However, I haven't >> figured out a way to do so without 3 method calls per iteration step. >> (The problem is for a list the "state" variable is an object (a pair); >> for a vector it is an index. To avoid heap allocation the state >> needs to be one or more local variables. Thus for each step you may need >> to update an object and/or an int, plus you need to extract the next >> value.) > > I count two: Iterator#hasNext() and Iterator#next(). What's the third > method call? Just the invocation of the passed procedure? You missed the requirement "some iteration protocol that at least avoids object allocation for Kawa lists and vectors". Using Iterator#hasNext( and Iterator#next() implies that you have allocated an Iterator. It's not per-step, but it is per-iteration. Perhaps I should worry less about it. -- --Per Bothner per@bothner.com http://per.bothner.com/ ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Support Iterable in for-each 2014-01-10 21:20 ` Per Bothner @ 2014-01-10 21:27 ` Jamison Hope 0 siblings, 0 replies; 11+ messages in thread From: Jamison Hope @ 2014-01-10 21:27 UTC (permalink / raw) To: kawa@sourceware.org list On Jan 10, 2014, at 4:20 PM, Per Bothner <per@bothner.com> wrote: > On 01/10/2014 01:04 PM, Jamison Hope wrote: >> On Jan 10, 2014, at 2:24 PM, Per Bothner <per@bothner.com> wrote: > >>> * It is possible to come up with some iteration protocol that >>> at least avoids object allocation for Kawa lists and vectors, and >>> perhaps falls back to Iterator in the generic case. However, I haven't >>> figured out a way to do so without 3 method calls per iteration step. >>> (The problem is for a list the "state" variable is an object (a pair); >>> for a vector it is an index. To avoid heap allocation the state >>> needs to be one or more local variables. Thus for each step you may need >>> to update an object and/or an int, plus you need to extract the next >>> value.) >> >> I count two: Iterator#hasNext() and Iterator#next(). What's the third >> method call? Just the invocation of the passed procedure? > > You missed the requirement "some iteration protocol that at least avoids > object allocation for Kawa lists and vectors". Using Iterator#hasNext( > and Iterator#next() implies that you have allocated an Iterator. It's not > per-step, but it is per-iteration. Perhaps I should worry less about it. I was assuming that the existing for-each and vector-for-each would remain, so Kawa lists and vectors would avoid this entirely. The path that treats the sequence as an Iterable would be the last resort. -- Jamison Hope The PTR Group www.theptrgroup.com ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Support Iterable in for-each 2014-01-10 21:04 ` Jamison Hope 2014-01-10 21:20 ` Per Bothner @ 2014-01-10 21:27 ` Per Bothner 2014-01-10 21:29 ` Jamison Hope 1 sibling, 1 reply; 11+ messages in thread From: Per Bothner @ 2014-01-10 21:27 UTC (permalink / raw) To: Jamison Hope, kawa@sourceware.org list On 01/10/2014 01:04 PM, Jamison Hope wrote: > We've been getting hints about this pattern stuff for quite a while > now, Per. :-) I do get distracted easily, especially from big complex projects. (Adding pattern support means changing the calling convention, and so I got pulling to tweaking that, including making full-tailcall mode faster. Sigh.) Nobody has commented on what I think is an interesting recent distraction: shell-style scripting. -- --Per Bothner per@bothner.com http://per.bothner.com/ ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Support Iterable in for-each 2014-01-10 21:27 ` Per Bothner @ 2014-01-10 21:29 ` Jamison Hope 0 siblings, 0 replies; 11+ messages in thread From: Jamison Hope @ 2014-01-10 21:29 UTC (permalink / raw) To: Per Bothner; +Cc: kawa@sourceware.org list On Jan 10, 2014, at 4:27 PM, Per Bothner <per@bothner.com> wrote: > Nobody has commented on what I think is an interesting recent > distraction: shell-style scripting. I've been busily wearing my embedded systems programming hat lately, haven't had a chance to look at it yet. My checkout of Kawa is 100+ revisions out of date. :-/ -- Jamison Hope The PTR Group www.theptrgroup.com ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Support Iterable in for-each 2014-01-10 19:24 ` Per Bothner 2014-01-10 21:04 ` Jamison Hope @ 2015-02-27 2:25 ` Per Bothner 2015-02-27 17:35 ` Jamison Hope 1 sibling, 1 reply; 11+ messages in thread From: Per Bothner @ 2015-02-27 2:25 UTC (permalink / raw) To: kawa [This is a follow-up to a discussion from January 2014.] I've checked in code to generalize map, for-each, and vector-map so the sequence arguments can be "generalized sequences": * any java Iterable, which includes Scheme lists, vectors, uniform vectors, and any java.util.List; * any primitive array; * and any CharSequence, including java.lang.String and Scheme strings. vector-for-each is generalized to any java.util.List, using the get and size methods. (I.e it assumes the List is RandomAccess.) Thus it performs poorly on Scheme lists. (Perhaps we should compile in a cast to RandomAccess to guard against quadratic behavior on Scheme lists.) Note that a CharSequence is considered a sequence of Unicode scalar values (a surrogate pair is converted to a single character). OTOH a native Java char array is considered a sequence of 16-bit char values. I think it makes most sense this way. If the sequence type is known as compile-time then the Kawa compiler well generate custom code for that sequence type (see the scanner-for procedure and the ScanHelper class in compile_map.scm). Otherwise it will use an Iterator, selecting the Iterator kind at run-time (see the static getIterator method in gnu/lists/Sequences.java). Regardless, if the mapped-over procedure is a lambda it will get inlined. The splice operator @ now also handles strings: (string #\X @"abc" #\Y) ==> "XabcY" (However, this has not been optimized as well as I'd like yet.) -- --Per Bothner per@bothner.com http://per.bothner.com/ ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Support Iterable in for-each 2015-02-27 2:25 ` Per Bothner @ 2015-02-27 17:35 ` Jamison Hope 2015-02-27 18:22 ` Matthieu Vachon 2015-02-27 20:43 ` Per Bothner 0 siblings, 2 replies; 11+ messages in thread From: Jamison Hope @ 2015-02-27 17:35 UTC (permalink / raw) To: kawa On Feb 26, 2015, at 9:25 PM, Per Bothner <per@bothner.com> wrote: > [This is a follow-up to a discussion from January 2014.] > > I've checked in code to generalize map, for-each, and vector-map > so the sequence arguments can be "generalized sequences": > * any java Iterable, which includes Scheme lists, vectors, uniform > vectors, and any java.util.List; > * any primitive array; > * and any CharSequence, including java.lang.String and Scheme strings. Very cool. I see that map always returns a list, regardless of the type(s) of the sequence argument(s). So if I've got an ArrayList of numbers #|kawa:1|# (define arraylist (java.util.ArrayList 1 2 3 4 5)) and I want to produce another ArrayList containing the squares of those numbers, I can do.. #|kawa:2|# (java.util.ArrayList @(map square arraylist)) [1, 4, 9, 16, 25] or #|kawa:3|# (apply java.util.ArrayList (map square arraylist)) [1, 4, 9, 16, 25] That was too painless. :-) Which is more idiomatic, (apply type list) or (type @list) ? > vector-for-each is generalized to any java.util.List, using the > get and size methods. (I.e it assumes the List is RandomAccess.) > Thus it performs poorly on Scheme lists. (Perhaps we should compile > in a cast to RandomAccess to guard against quadratic behavior on Scheme lists.) > > Note that a CharSequence is considered a sequence of Unicode scalar values > (a surrogate pair is converted to a single character). OTOH a native > Java char array is considered a sequence of 16-bit char values. I think > it makes most sense this way. > > If the sequence type is known as compile-time then the Kawa compiler > well generate custom code for that sequence type (see the scanner-for > procedure and the ScanHelper class in compile_map.scm). Otherwise > it will use an Iterator, selecting the Iterator kind at run-time (see the > static getIterator method in gnu/lists/Sequences.java). > > Regardless, if the mapped-over procedure is a lambda it will > get inlined. > > The splice operator @ now also handles strings: > (string #\X @"abc" #\Y) ==> "XabcY" > (However, this has not been optimized as well as I'd like yet.) BTW, I had to define a remove() method for CharacterIterator in gnu/lists/Sequences.java to build with Java 1.7, which doesn't have these newfangled "default" methods. I also had to add <include name="kawa/Source*.java"/> to the java-classes target in build.xml. -- Jamison Hope The PTR Group www.theptrgroup.com ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Support Iterable in for-each 2015-02-27 17:35 ` Jamison Hope @ 2015-02-27 18:22 ` Matthieu Vachon 2015-02-27 20:43 ` Per Bothner 1 sibling, 0 replies; 11+ messages in thread From: Matthieu Vachon @ 2015-02-27 18:22 UTC (permalink / raw) To: Jamison Hope; +Cc: kawa Wow, this is a massive increase of Kawa and Java inter-operability in my opinion. It will be much more easier now to iterate through native Java Iterable types. We have a lot of functions and macro to deal with those in our codebase. Great enhancement :) On Fri, Feb 27, 2015 at 12:35 PM, Jamison Hope <jrh@theptrgroup.com> wrote: > On Feb 26, 2015, at 9:25 PM, Per Bothner <per@bothner.com> wrote: > >> [This is a follow-up to a discussion from January 2014.] >> >> I've checked in code to generalize map, for-each, and vector-map >> so the sequence arguments can be "generalized sequences": >> * any java Iterable, which includes Scheme lists, vectors, uniform >> vectors, and any java.util.List; >> * any primitive array; >> * and any CharSequence, including java.lang.String and Scheme strings. > > Very cool. I see that map always returns a list, regardless of the > type(s) of the sequence argument(s). > > So if I've got an ArrayList of numbers > > #|kawa:1|# (define arraylist (java.util.ArrayList 1 2 3 4 5)) > > and I want to produce another ArrayList containing the squares of > those numbers, I can do.. > > #|kawa:2|# (java.util.ArrayList @(map square arraylist)) > [1, 4, 9, 16, 25] > > or > > #|kawa:3|# (apply java.util.ArrayList (map square arraylist)) > [1, 4, 9, 16, 25] > > That was too painless. :-) > > Which is more idiomatic, (apply type list) or (type @list) ? > > >> vector-for-each is generalized to any java.util.List, using the >> get and size methods. (I.e it assumes the List is RandomAccess.) >> Thus it performs poorly on Scheme lists. (Perhaps we should compile >> in a cast to RandomAccess to guard against quadratic behavior on Scheme lists.) >> >> Note that a CharSequence is considered a sequence of Unicode scalar values >> (a surrogate pair is converted to a single character). OTOH a native >> Java char array is considered a sequence of 16-bit char values. I think >> it makes most sense this way. >> >> If the sequence type is known as compile-time then the Kawa compiler >> well generate custom code for that sequence type (see the scanner-for >> procedure and the ScanHelper class in compile_map.scm). Otherwise >> it will use an Iterator, selecting the Iterator kind at run-time (see the >> static getIterator method in gnu/lists/Sequences.java). >> >> Regardless, if the mapped-over procedure is a lambda it will >> get inlined. >> >> The splice operator @ now also handles strings: >> (string #\X @"abc" #\Y) ==> "XabcY" >> (However, this has not been optimized as well as I'd like yet.) > > > BTW, I had to define a remove() method for CharacterIterator in > gnu/lists/Sequences.java to build with Java 1.7, which doesn't have > these newfangled "default" methods. > > I also had to add > <include name="kawa/Source*.java"/> > to the java-classes target in build.xml. > > -- > Jamison Hope > The PTR Group > www.theptrgroup.com > > > ^ permalink raw reply [flat|nested] 11+ messages in thread
* Re: Support Iterable in for-each 2015-02-27 17:35 ` Jamison Hope 2015-02-27 18:22 ` Matthieu Vachon @ 2015-02-27 20:43 ` Per Bothner 1 sibling, 0 replies; 11+ messages in thread From: Per Bothner @ 2015-02-27 20:43 UTC (permalink / raw) To: kawa On 02/27/2015 09:35 AM, Jamison Hope wrote: > On Feb 26, 2015, at 9:25 PM, Per Bothner <per@bothner.com> wrote: >> I've checked in code to generalize map, for-each, and vector-map >> so the sequence arguments can be "generalized sequences": > Very cool. I see that map always returns a list, regardless of the > type(s) of the sequence argument(s). Yes - the alternative seems too complicated. Scala has a complicated framework for picking a result type based on the argument type, but it seems very complicated and fragile. What if you map sqrt over an int[]? Should the result be a double[]? What when there are multiple sequence arguments? Note the rules have to work sanely and consistently both with compile-time typing and run-time-typing. It's a lot easier when the compiler just knows the result type. And as you show there is an easy work-around with constructors and splices. > So if I've got an ArrayList of numbers > #|kawa:1|# (define arraylist (java.util.ArrayList 1 2 3 4 5)) > and I want to produce another ArrayList containing the squares of > those numbers, I can do. > #|kawa:2|# (java.util.ArrayList @(map square arraylist)) > [1, 4, 9, 16, 25] > Which is more idiomatic, (apply type list) or (type @list) ? I'd say the latter. Currently apply isn't well optimized, Though splicing isn't as well optimized as I'd like, it's better than apply. For example calling a varargs method with a splice is complied pretty well. My plan is to have the compiler rewrite: (apply f x y lst) to: (f x y @lst) When that is done they'll have the same performance, Further out, the plan is to allow this syntax: (java.util.ArrayList (square (each arraylist)) ...) This uses the same '...' as in syntax patterns, and 'each' is a magic function inside the context of a '...'. It would also work in patterns: (! [x ...] arraylist) ;; x is 'each' element of arraylist (java.util.ArrayList (* x x) ...) I expect this feature before the next release. > BTW, I had to define a remove() method for CharacterIterator in > gnu/lists/Sequences.java to build with Java 1.7, which doesn't have > these newfangled "default" methods. Oops - fixed. > I also had to add > <include name="kawa/Source*.java"/> > to the java-classes target in build.xml. It doesn't seem like it's strictly needed, but I fixed this too. -- --Per Bothner per@bothner.com http://per.bothner.com/ ^ permalink raw reply [flat|nested] 11+ messages in thread
end of thread, other threads:[~2015-02-27 20:43 UTC | newest] Thread overview: 11+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2014-01-10 18:45 Support Iterable in for-each Matthieu Vachon 2014-01-10 19:24 ` Per Bothner 2014-01-10 21:04 ` Jamison Hope 2014-01-10 21:20 ` Per Bothner 2014-01-10 21:27 ` Jamison Hope 2014-01-10 21:27 ` Per Bothner 2014-01-10 21:29 ` Jamison Hope 2015-02-27 2:25 ` Per Bothner 2015-02-27 17:35 ` Jamison Hope 2015-02-27 18:22 ` Matthieu Vachon 2015-02-27 20:43 ` Per Bothner
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).