Support Transducers


(Jason Jobe) #1

Okay,

I would like to propose that Transducers be considered for addition to the Swift core.

"Transducers are a powerful and composable way to build algorithmic transformations that you can reuse in many contexts…"

There are ways to build them w/out any language modification but they are not as efficient as alternative expressions.
Here are some example implementations to give you an idea.

  https://gist.github.com/rjchatfield/14e2869b0c572696ea3c
  https://github.com/mbrandonw/learn-transducers-playground/blob/master/transducers.md
  https://gist.github.com/hsavit1/0791bc9a54d11608ed6d

I look forward to your thoughts and comments.

-jason

Transducers are Coming — Cognitect Blog <http://blog.cognitect.com/blog/2014/8/6/transducers-are-coming>

A presentation by Rich Hickey
https://www.youtube.com/watch?v=6mTbuzafcII <https://www.youtube.com/watch?v=6mTbuzafcII>


(Dmitri Gribenko) #2

Hi Jason,

I was playing with a similar idea here:

https://github.com/apple/swift/blob/master/test/Prototypes/CollectionTransformers.swift

You wouldn't find the word 'transducer' there, but it is based on
similar principles, except it also allows you to optimize the AST of
the transformation, and it is structured in such a way that would
allow us to automatically parallelize the whole pipeline.

Dmitri

···

On Fri, Dec 25, 2015 at 9:07 AM, Jason Jobe via swift-evolution <swift-evolution@swift.org> wrote:

Okay,

I would like to propose that Transducers be considered for addition to the Swift core.

"Transducers are a powerful and composable way to build algorithmic transformations that you can reuse in many contexts…"

There are ways to build them w/out any language modification but they are not as efficient as alternative expressions.

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/


(Matthew Johnson) #3

Okay,

I would like to propose that Transducers be considered for addition to the Swift core.

"Transducers are a powerful and composable way to build algorithmic transformations that you can reuse in many contexts…"

There are ways to build them w/out any language modification but they are not as efficient as alternative expressions.

Hi Jason,

I was playing with a similar idea here:

https://github.com/apple/swift/blob/master/test/Prototypes/CollectionTransformers.swift

You wouldn't find the word 'transducer' there, but it is based on
similar principles, except it also allows you to optimize the AST of
the transformation, and it is structured in such a way that would
allow us to automatically parallelize the whole pipeline.

It's great to see you experimenting with this!

It's unrelated but one comment in there jumped out at me:
// As sad as it is, I think for practical performance reasons we should rewrite
// the inner parts of the fork-join framework in C++. In way too many cases
// than necessary Swift requires an extra allocation to pin objects in memory
// for safe multithreaded access. -Dmitri

I agree this is sad, but also hope it is only a temporary situation (as with other performance related concerns). Any thoughts on that?

···

Sent from my iPad

On Dec 25, 2015, at 11:53 AM, Dmitri Gribenko via swift-evolution <swift-evolution@swift.org> wrote:
On Fri, Dec 25, 2015 at 9:07 AM, Jason Jobe via swift-evolution > <swift-evolution@swift.org> wrote:

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution


(Árpád Goretity) #4

This is a nice idea that I would definitely support having in the stdlib.
By the way, are there any benchmarks supporting that transducers do indeed
result in a performance gain? Having to allocate/traverse fewer arrays sure
seems like a win, but other constant factors may be introduced by the
extensive use of closures.

···

On Fri, Dec 25, 2015 at 6:53 PM, Dmitri Gribenko via swift-evolution < swift-evolution@swift.org> wrote:

On Fri, Dec 25, 2015 at 9:07 AM, Jason Jobe via swift-evolution > <swift-evolution@swift.org> wrote:
>
> Okay,
>
> I would like to propose that Transducers be considered for addition to
the Swift core.
>
> "Transducers are a powerful and composable way to build algorithmic
transformations that you can reuse in many contexts…"
>
> There are ways to build them w/out any language modification but they
are not as efficient as alternative expressions.

Hi Jason,

I was playing with a similar idea here:

https://github.com/apple/swift/blob/master/test/Prototypes/CollectionTransformers.swift

You wouldn't find the word 'transducer' there, but it is based on
similar principles, except it also allows you to optimize the AST of
the transformation, and it is structured in such a way that would
allow us to automatically parallelize the whole pipeline.

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com>*/
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution

--
Author of the Sparkling language
http://h2co3.org/


(Joe Groff) #5

Sent from my iPad

Okay,

I would like to propose that Transducers be considered for addition to the Swift core.

"Transducers are a powerful and composable way to build algorithmic transformations that you can reuse in many contexts…"

There are ways to build them w/out any language modification but they are not as efficient as alternative expressions.

Hi Jason,

I was playing with a similar idea here:

https://github.com/apple/swift/blob/master/test/Prototypes/CollectionTransformers.swift

You wouldn't find the word 'transducer' there, but it is based on
similar principles, except it also allows you to optimize the AST of
the transformation, and it is structured in such a way that would
allow us to automatically parallelize the whole pipeline.

It's great to see you experimenting with this!

It's unrelated but one comment in there jumped out at me:
// As sad as it is, I think for practical performance reasons we should rewrite
// the inner parts of the fork-join framework in C++. In way too many cases
// than necessary Swift requires an extra allocation to pin objects in memory
// for safe multithreaded access. -Dmitri

I agree this is sad, but also hope it is only a temporary situation (as with other performance related concerns). Any thoughts on that?

There's the intermediate possibility of using SIL to write these, which will give exact control over when copies and retains happen without dropping down to C++ and dealing with the fragility of maintaining common ABIs between Swift/C++ functions and the loss of high-level optimization opportunity.

-Joe

···

On Dec 25, 2015, at 11:15 AM, Matthew Johnson via swift-evolution <swift-evolution@swift.org> wrote:
On Dec 25, 2015, at 11:53 AM, Dmitri Gribenko via swift-evolution <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

On Fri, Dec 25, 2015 at 9:07 AM, Jason Jobe via swift-evolution >> <swift-evolution@swift.org <mailto:swift-evolution@swift.org>> wrote:

Dmitri

--
main(i,j){for(i=2;;i++){for(j=2;j<i;j++){if(!(i%j)){j=0;break;}}if
(j){printf("%d\n",i);}}} /*Dmitri Gribenko <gribozavr@gmail.com <mailto:gribozavr@gmail.com>>*/
_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org <mailto:swift-evolution@swift.org>
https://lists.swift.org/mailman/listinfo/swift-evolution

_______________________________________________
swift-evolution mailing list
swift-evolution@swift.org
https://lists.swift.org/mailman/listinfo/swift-evolution