Re: Gee Functional iterators - call for consensus

[Quikee <quikee gmail com>]

On Wed, Jun 29, 2011 at 15:04, Maciej Piechotka <uzytkownik2 gmail com> wrote:
> Well - possibly due to different background I like virtual method in
> interfaces (i.e. like classes in Haskell). They allow to change
> interface w/out breaking API (breaking ABI however).
I acknowledge it is the difference in the background but still for the
sake of consistency you either get rid of AbstractCollection and co.
or change the interface. Still I prefer to keep interfaces clean of
implementation - this helps to separate how from what (How it works is
something a user of the interface is not interested in and does not
need to know, what does it do is the only thing he is interested in.)
and if I use an interface it does not assume anything (no default
implementation).

> The stream function was written for performance reason. The Vala does
> not optimize the virtual calls at all so they perform slowly as Java or
> C# would do. Vala have no static or dynamic type analysis and therefore
> each call to interface goes through 1-2 jumps by function pointers.
>
> For exact numbers see:
>
> https://bugzilla.gnome.org/show_bug.cgi?id=645850#c4
>
> It is written mostly for implemantators as it:
>
>  - Allows to reuse of code across functions (like map etc.) therefore
> making life of people implementing new combinators easier (i.e. Jurg,
> Dider, mine, ...). I agree that it is small benefit and therefore it was
> not in original spec.
>  - As a side effect it allows to implement all functional methods to be
> implemented efficiently by just reimplementing forall and stream. As it
> generally have huge impact (virtual calls are heavy in Vala, virtual
> calls to interfaces via abstract classes are even more).
>
> As shown in the data I've linked it have the  some constant overhead
> (which quickly outperform other methods except .get for array).
>
> In short - it is implementation detail but important one from
> performance POV (yes, I was surprised by benefits of forall).

If it is a performance regression in Vala or in GObject it should be
fixed there not worked around in libgee. To make this clear - I don't
care if the workaround is in the implementation that can be easily
changed without anybody noticing but don't workaround things (or
design with such problems in mind) on interface level.

Also I have nothing against stream besides that it should be part of
implementation - hidden away from the user as he does not need to know
it exists. There is a reason that libgee exists.. it is because GLib's
collections are horrible. They expose implementation details which
means you can not mix them easily by just changing the type like for
example you can do with libgee (change from LinkedList to ArrayList
and semantic doesn't change). With stream that is a implementation
detail you do the same. For example map can be implemented in various
ways - even non-lazy and parallel evaluated but when you assume stream
this is not possible or let's say it is not elegant.

> Hmm. +1?
>
> What about something like Stream interface from which both Collection
> and Iterator inherit?
>
> Edit: it seems you call it Functional. I'm not particulary happy with
> either of names.
I am not sure about the name either. Interfaces define behaviour of a
particular Class - I thought in the line that a certain Class is
functional or has functional behaviour if it implements the Functional
interface. The same as a Class is iterable if it implements Iterable
interface. Still functional behaviour sound very awkward and
misleading.

Stream is also a bad name for the interface - it's just one kind of
implementation for functional operators.

> Ok. There was take and skip operators in spec which get lost.
>
> it would be something like:
>
> iterator().skip(3).map(func)

This was not the point. Point was what kind of behaviour can I expect
when I do iterator().next().next().next().map(func). Does map work
through the whole collection or only the rest of collection? Because
there is no reset it obviously can not go from the beginning. Still I
don't like that I (or every other user) have to even ask such
questions - I want that the behaviour is obvious on the interface
level.

I like skip(..) but even nicer would be limit(3,10) or maybe
slice(3,10) also things like slice(3, -2) would be nice. There is
slice already but that slice copies the collection which is not really
cool.

> They produces elements as they go. So say there is iterator returning:
>
> iter = [1, 2, 3, 4, ....]
>
> iter.map((x) => {return x + 1;}) returns
>
> [2, 3, 4, 5, ...]
>
> iter.scan((x, y) => {return x + y}, 0) returns
>
> [0, 1, 3, 6, 10, ...]

... and fold and foreach? Because the method is implemented on the
interface the user doesn't even know that it has a problem. In case an
interface only prescribes that you need to implement an method the
user will go "hmmm..." immediately in such situation. :)

> To be honest I don't like the separation of FunctionalIterator and
> Iterator. Every iterator is, conceptually, functional iterator. There is
> no iterator for which you cannot define meaningfully map function.

Arguably you can kill a man with almost every knife but still this
does not mean that a kitchen knife should be designated as a weapon.
Also here the iterator purpose is to iterate elements, a special
iterator can do other things besides this but it is not only an
iterator anymore - it is something more than a iterator. In this case
it is a functional iterator - iterator that besides all also supports
functional operations.

> Sorry for double-posting. Also - your implementation uses foreach by
> default which is a bad idea from performance POV as mentioned before.
> (Namely 20x performance degradation for 1023 element array).

I did not know foreach has performance regressions.. still as I said -
there is no reason foreach should have regressions. If it has it is a
bug elsewhere.

And.. another thing I remembered that is currently missing and would
be nice to have is an ability to create a new collection from the
iterator. With all the power that can be done now with functional
operations it would be nice to have a add_all_from_iterator (not a
good name) method on collection interface or change the signature of
add_all to

>No. It would be... well stupid if I sent RFC/call for consensus
>expecting only positive feedback. Well - ok, I do hope everything is
>fine with my original design ;) but from my experience negative, but
>constructive, feedback is the most valuable one.
It is sometimes hard to give constructive feedback. Sometimes I know
that something is not good and we might run against the wall in the
future (or not) but it is hard to explain and persuade that I might be
right. As in this case I have a bad feeling about stream on interface
as I would always design the interface correct, extensible, friendly
first and never for performance in mind. I just hope we find something
that will be acceptable by both.

Regards, Tomaž