Support Iterable in for-each

Support Iterable in for-each

[Matthieu Vachon]

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

Re: Support Iterable in for-each

[Per Bothner]

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/

Re: Support Iterable in for-each

[Jamison Hope]

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

Re: Support Iterable in for-each

[Per Bothner]

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/

Re: Support Iterable in for-each

[Jamison Hope]

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

Re: Support Iterable in for-each

[Per Bothner]

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/

Re: Support Iterable in for-each

[Jamison Hope]

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

Re: Support Iterable in for-each

[Per Bothner]

[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/

Re: Support Iterable in for-each

[Jamison Hope]

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

Re: Support Iterable in for-each

[Matthieu Vachon]

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
>
>
>

Re: Support Iterable in for-each

[Per Bothner]

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/