Asp Forum - library for fast map/filter/reduce

glathoud

2/17/2016 6:25:00 AM

Hello,

I'd like to share a library that permits to write map/filter/reduce code that runs much faster than the corresponding native Array methods. It works by generating fast JS code automatically, with a single for loop whenever possible, and also includes logical functions and object/array conversions functions.

http://glat.info...

Best regards,
Guillaume

8 Answers

Scott Sauyet

2/19/2016 4:01:00 AM

glathoud wrote:
> I'd like to share a library that permits to write map/filter/reduce code
> that runs much faster than the corresponding native Array methods. It
> works by generating fast JS code automatically, with a single for loop
> whenever possible, and also includes logical functions and object/array
> conversions functions.
>
> http://glat.info...

Please, when posting to USENET, give more information than a sound-bite
and a link. The link is fine, but it should be backed up by further
discussion, code, questions, debate, flame-wars, pedantry, ... in short,
by *content*. You certainly do not need to replicate all the content to
which your link makes reference, but there should be enough that people
here can discuss it without chasing down the link, and only visit that
page if it still seems interesting to them.

-----

Now, as to your library, congratulations! It's very interesting. It
seems to combine aspects of two ideas that I haven't seen put together
before. First, it uses a syntax very similar to Oliver Steele's
Functional JavaScript [1], the first fairly comprehensive library for
doing functional programming in Javascript. The similarity here is
in the string-based lambda expressions, such as `'.p'` for the
equivalent of `obj => obj.p` or `function(obj) {return obj.p;}`, and
`'+'` for `(a, b) => a + b`.

Second, you implement the relatively new notion of *transducers*
[2], which, at their core, replace a sequence of iterations of
transformations with an iteration of a sequence of transformations.
This prevents the creation of intermediate containers and can gain
some serious efficiency.

There are two reasons that this API does not appeal to me. First,
although I appreciate the _tour de force_ that was Oliver Steele's
original library, I don't at all care for the string lambdas. They
feel entirely wrong, as though all the lessons we've learned over
the years about problems with `eval` are to be discarded. Second,
I absolutely prefer to work by building composing more sophisticated
functions out of simpler ones. Chaining methods together holds
absolutely no appeal.

So this example from transfun:

var appfun = tfun.map( '.p' ).filter( '!=null' ).reduce( '+' );

I would write using Ramda as

const appfun = pipe(map(prop('p')), filter(complement(isNil)), sum);

The main difference is that I can pass ANY function through a pipeline
like this. It does not have to be a fixed method of some object or
set of objects. So for instance, if I wanted to reuse the ability to
filter out the null values, I would simply name that function:

const removeNulls = filter(complement(isNil));
const appfun = pipe(map(prop('p')), removeNulls, sum);

I don't see a way to do this with a chained set of method calls. But
I have only looked at your documentation and haven't dug into the code
so I may be missing something interesting.

But regardless of whether it's something that appeals to me personally,
kudos on putting this together. There's definitely some interesting
ideas here!

[1]: The original documentation page seems to be offline, but the code
is on GitHub at <https://github.com/osteele/functional-java...
and an initial announcement is at
<https://github.com/osteele/functional-java...

[2]: First discussed in the Clojure community, e.g.:
<http://blog.cognitect.com/blog/2014/8/6/transducers-are-....
There are several well-known Javascript versions, including
<https://github.com/jlongster/transduc... and
<https://github.com/cognitect-labs/transduc.... They're also
partially folded into some more general-purpose libraries like
Ramda: <http://ramda... (disclosure: I'm one of the authors.)

-- Scott

glathoud

2/19/2016 10:11:00 AM

Scott, thank you very much for taking the time to write such a detailed response. Below is an attempt to address several points you made.

.

Concerning O'Steele functional JavaScript: if I remember correctly, he was the one behind most of dojox.lang.functional back then. My article pointed to this already:

http://glat.info/transfun/#interlude-pers...

I should probably add the link you provided.

.

Concerning the string lambdas: transfun.js permits both string lambdas and usual functions:

http://glat.info/transfun/#with...

I am personally happy with both:

http://glat.info/transfun/#person...

It is probably a matter of context.

.

Concerning transducers, the term may be relatively new, but I am not sure whether the underlying mechanisms are that new. See for example this discussion:

http://forum.dlang.org/post/mailman.166.1409468422.5783.digitalmars-d@pur...

.

Thanks for mentionning Ramda. My impression after a brief glance: that's a lot of functionalities! Certainly something to look at.

.

Side note: transfun.js offers a few selected transformations (especially the ones I often need), but anyone can write his own:

http://glat.info/transfun...

.

Thanks again and best regards,
Guillaume

Scott Sauyet

2/19/2016 4:44:00 PM

glathoud wrote:
> Scott, thank you very much for taking the time to write such a detailed
> response.

I was glad to. It's a very interesting library. And please do take the
criticism in the positive spirit in which it was intended. This is the
most interesting new library I've seen since Trine [1]. That it doesn't
appeal directly to my personal sensibilities doesn't mean I think it
won't appeal to others'.

> Concerning O'Steele functional JavaScript: if I remember correctly, he was
> the one behind most of dojox.lang.functional back then.

Oh, was he? I always edged my way around Dojo, using it when I was on
projects that already had it, but never introducing it. It always seemed
overblown, a designed-by-committee monstrosity.

> Concerning the string lambdas: transfun.js permits both string lambdas and
> usual functions:
>
> http://glat.info/transfun/#with...
>
> I am personally happy with both:
>
> http://glat.info/transfun/#person...
>
> It is probably a matter of context.

Perhaps. I did see that both were available. To me, though, the string
lambdas are uncomfortable. They make me wonder about the overall design.
If I were to use the library, though, I do understand that I could simply
choose not to use them.

These days, ES6 fat arrow syntax helps reduce the verbose nature of lambdas
in JS anyway, so some of the reason for these may not be so important. I
may be missing some of your motivation, though.

> Concerning transducers, the term may be relatively new, but I am not sure
> whether the underlying mechanisms are that new. See for example this
> discussion:
>
> http://forum.dlang.org/post/mailman.166.1409468422.5783.digitalmars-d@pur...

Interesting. I've not worked with D, only read a few articles about it.

I've always thought of it as a mostly imperative language, and didn't
even realize that it had functional APIs included. I can't tell from
their documentation if the claims from that post are justified or not.
It would be interesting to know.

Clearly this cannot be the first time someone has wanted to address this
problem. Transducers is the first time I saw a generic approach at a
solution, but it would not be surprising to find that others had already
solved it.

> Thanks for mentionning Ramda. My impression after a brief glance: that's
> a lot of functionalities! Certainly something to look at.

If nothing else, it's been a fun project.

> Side note: transfun.js offers a few selected transformations (especially
> the ones I often need), but anyone can write his own:
>
> http://glat.info/transfun...

That does improve the situation, but still doesn't give the expressiveness
that I like in pipelines. It doesn't allow me to use functions on the
fly, partially applying functions, using lambdas, etc.

Again, though, I do find this very interesting, and I look forward to
having the time to dig more deeply into the implementation.

Kudos!

[1]: Trine came on very strong, but peaked quickly and didn't seem to
last. I wasn't really interested in using it either, but it also
presented an interesting alternative approach that I hadn't seen
elsewhere: <https://github.com/jussi-kalliokoski...

-- Scott

glathoud

2/20/2016 12:04:00 PM

On Friday, February 19, 2016 at 5:44:31 PM UTC+1, Scott Sauyet wrote:

> [...] please do take the
criticism in the positive spirit in which it was intended. [...]

No worries ! That's the way I understood your comments. And thanks for the compliments.

> [...] I always edged my way around Dojo, using it when I was on
> projects that already had it, but never introducing it. It always seemed
> overblown, a designed-by-committee monstrosity.

Yes... I once removed dojo from a production codebase, thus putting an end to recurring "daytime nightmares". I found comp.lang.javascript particularly useful in that context.

>
>
> > Concerning the string lambdas: transfun.js permits both string lambdas and
> > usual functions [...] It is probably a matter of context.
>
> Perhaps. I did see that both were available. To me, though, the string
> lambdas are uncomfortable. They make me wonder about the overall design.
> If I were to use the library, though, I do understand that I could simply
> choose not to use them.
>
> These days, ES6 fat arrow syntax helps reduce the verbose nature of lambdas
> in JS anyway, so some of the reason for these may not be so important. I
> may be missing some of your motivation, though.

One possible motivation is the extra speed - although the speed gain is not as important as the speed gain obtained from eliminating intermediate arrays.

Another possible motivation is to generate flat code without resorting to function decompilation.

A third motivation is that I just like to generate code :) More seriously it is nice to be able to look at one piece of generated code, hopefully still somewhat readable.

Side note about lambdas: it would be nice to be able to write some without variables at all. OCaml has an interesting notation where one can wrap an operator + into a function (+)

>
> [...]
>
> Interesting. I've not worked with D, only read a few articles about it.
>
> I've always thought of it as a mostly imperative language, and didn't
> even realize that it had functional APIs included. I can't tell from
> their documentation if the claims from that post are justified or not.
> It would be interesting to know.

I had the same reaction and asked. The answer is yes:

http://forum.dlang.org/thread/pbcwqhfgjghxezpsiblo@forum...

>
> [...]
>
> > Side note: transfun.js offers a few selected transformations (especially
> > the ones I often need), but anyone can write his own:
> >
> > http://glat.info/transfun...
>
> That does improve the situation, but still doesn't give the expressiveness
> that I like in pipelines. It doesn't allow me to use functions on the
> fly, partially applying functions, using lambdas, etc.

Ok. At this point of time I can only say that transfun's transformations support automatic currying - not documented, sorry. I have to look at the other topics you mentionned.

Thanks for mentionning Trine.

Best regards,
Guillaume

Ben Bacarisse

2/20/2016 2:00:00 PM

glathoud <glathoud@yahoo.fr> writes:
<snip>
> Side note about lambdas: it would be nice to be able to write some
> without variables at all. OCaml has an interesting notation where one
> can wrap an operator + into a function (+)

Haskell has that too, and it came (at least in the case of Haskell),
from Miranda designed by David Turner. He may have got it from a 1973
dissertation by Wile and (like so many such things) it probably has even
older roots in mathematical logic.

Haskell (and Miranda) can go both ways. (+) is a function make from an
operator, but given a function like mod, you can make an operator from
it using `...`:

95 `mod` 10

is 5. And you can combine the two. Since operators permit sections
using either operand it can be handy to write (`mod` 10) for the "modulo
10" function.

<snip>
--
Ben.

Michael Haufe (\"TNO\")

2/24/2016 3:23:00 AM

On Wednesday, February 17, 2016 at 12:24:58 AM UTC-6, glathoud wrote:
> Hello,
>
> I'd like to share a library that permits to write map/filter/reduce code that runs much faster than the corresponding native Array methods.

This of course depends on the implementation. A sufficiently intelligent one can accomplish comparable speed. For example, take a look at the newer implementations of Firefox [1]

> It works by generating fast JS code automatically, with a single for loop whenever possible, and also includes logical functions and object/array conversions functions.
>
> http://glat.info...

It seems like you've rediscovered something similar to the fold-fusion laws [2][3]. It's good to see someone play with this in JavaScript again, though I'm not a fan of your syntactic approach of using string literals... When I played with similar in the past (LINQ implementation on top of iterators/generators), I was using the following to represent the expressions:

function sum(a,b){ return a + b; }

var query = xs.select('p').where({ne:null}).reduce(sum)
....
query() //call the query

If I was to revisit this again, I think I would look at the recent efforts of Asen Bozhilov on ES-Iter [4] combined with a re-read of a few of the fold-fusion papers.

Overall though, I have a positive opinion of your efforts.

[1] <http://jsperf.com/arr-map-filter-re...
[2] <http://www.cs.nott.ac.uk/~pszgmh/fo...
[3] <https://www.cs.ox.ac.uk/ralf.hinze/publications/IFL...
[4] <https://github.com/abozhilov/E...

glathoud

2/24/2016 5:53:00 AM

On Saturday, February 20, 2016 at 2:59:52 PM UTC+1, Ben Bacarisse wrote:
> glathoud <glathoud@yahoo.fr> writes:
> <snip>
> > Side note about lambdas: it would be nice to be able to write some
> > without variables at all. OCaml has an interesting notation where one
> > can wrap an operator + into a function (+)
>
> Haskell has that too, and it came (at least in the case of Haskell),
> from Miranda designed by David Turner. He may have got it from a 1973
> dissertation by Wile and (like so many such things) it probably has even
> older roots in mathematical logic.
>
> Haskell (and Miranda) can go both ways. (+) is a function make from an
> operator, but given a function like mod, you can make an operator from
> it using `...`:
>
> 95 `mod` 10
>
> is 5. And you can combine the two. Since operators permit sections
> using either operand it can be handy to write (`mod` 10) for the "modulo
> 10" function.
>
> <snip>
> --
> Ben.

Thanks for giving the big picture about this topic. I did not know all that!

Best regards,
Guillaume

glathoud

2/24/2016 6:11:00 AM

On Wednesday, February 24, 2016 at 4:22:55 AM UTC+1, Michael Haufe (TNO) wrote:
> On Wednesday, February 17, 2016 at 12:24:58 AM UTC-6, glathoud wrote:
> > Hello,
> >
> > I'd like to share a library that permits to write map/filter/reduce code that runs much faster than the corresponding native Array methods.
>
> This of course depends on the implementation. A sufficiently intelligent one can accomplish comparable speed. For example, take a look at the newer implementations of Firefox [1]

Well I'd be cautious with the interpretation of that result. One can also say that the optimization of the single loop is deficient in Firefox, especially when one compares with other browsers. For example, Chrome is running it more than one order of magnitude faster! (and if I recall correctly, Internet Explorer, too).

In practice, if transfun leads to a comparable or slightly higher speed in some browsers, and a much higher speed in other browsers, that's good enough for me - especially in the mobile context for performance-critical parts of an application. In my experience, without such tools like transfun, profiling leads invariably to write loops by hand, which is a bit boring after a while.

>
> > It works by generating fast JS code automatically, with a single for loop whenever possible, and also includes logical functions and object/array conversions functions.
> >
> > http://glat.info...
>
> It seems like you've rediscovered something similar to the fold-fusion laws [2][3].

Yes. The second paragraph of the transfun article already says:

> transfun.js automatically merges consecutive loops into one loop, then
> generates fast code for that loop (similar to stream fusion in ? Haskell).

> It's good to see someone play with this in JavaScript again, though I'm not a fan of your syntactic approach of using string literals... When I played with similar in the past (LINQ implementation on top of iterators/generators), I was using the following to represent the expressions:
>
> function sum(a,b){ return a + b; }
>
> var query = xs.select('p').where({ne:null}).reduce(sum)
> ...
> query() //call the query
>
> If I was to revisit this again, I think I would look at the recent efforts of Asen Bozhilov on ES-Iter [4] combined with a re-read of a few of the fold-fusion papers.
>
> Overall though, I have a positive opinion of your efforts.
>
> [1] <http://jsperf.com/arr-map-filter-re...
> [2] <http://www.cs.nott.ac.uk/~pszgmh/fo...
> [3] <https://www.cs.ox.ac.uk/ralf.hinze/publications/IFL...
> [4] <https://github.com/abozhilov/E...

Thanks for [2][3][4]. Very interesting. [4] looks pretty good to me. I am not sure how complicate it is to debug such code in practice, though. This is also one of the possible reasons to "embrace the ugliness" of generated code - although of course within reasonable limits.

Best regards,
Guillaume

comp.lang.javascript

library for fast map/filter/reduce

glathoud

Scott Sauyet

glathoud

Scott Sauyet

glathoud

Ben Bacarisse

Michael Haufe (\"TNO\")

glathoud

glathoud

x Login to ForumsZone