Re: Support Iterable in for-each

[Jamison Hope <jrh at theptrgroup dot com>]

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