You are viewing a plain text version of this content. The canonical link for it is here.
Posted to dev@beam.apache.org by Wesley Tanaka <wt...@yahoo.com.INVALID> on 2017/04/18 02:29:59 UTC
Naming of Combine.Globally
As I start to understand Combine.Globally, it seems that it is, in spirit, Beam's implementation of the "fold" higher-order function
https://en.wikipedia.org/wiki/Fold_(higher-order_function)#Folds_in_various_languages
Was there a reason the word "combine" was picked instead of either "fold" or "reduce"? From the wikipedia list above, it seems as though "fold" and "reduce" are in much more common usage, so either of those might be easier for newcomers to understand.
---
Wesley Tanaka
http://wtanaka.com/
Re: Naming of Combine.Globally
Posted by Eugene Kirpichov <ki...@google.com.INVALID>.
...Curiously enough, ReduceFn is by far the closest of all these to a
sequential fold. It is also internal (runner-facing rather than
user-facing).
On Tue, Apr 18, 2017 at 8:27 AM Dan Halperin <dh...@google.com.invalid>
wrote:
> Great discussion! As Aljoscha says, Fold, Reduce, and Combine are all
> intertwined and not quite identical as we use them.
>
> Another simple but perhaps coy answer is that if you read the MapReduce
> paper by Dean and Ghemawat that started this all, they used "Map",
> "Reduce", and "Combine" (see section 4.3:
> https://research.google.com/archive/mapreduce.html)
>
> So then it's likely just the lineage of Beam as "evolving from MapReduce"
> :). [Looking around the source tree: we have MapElements, ReduceFn, and
> Combine. And the DataflowRunner has Shuffle inside of GroupByKey. ;)]
>
> Dan
>
> On Tue, Apr 18, 2017 at 3:16 AM, Aljoscha Krettek <al...@apache.org>
> wrote:
>
> > The definition of foldl in Haskell is the same as the description I gave
> > earlier:
> >
> > foldl :: (a -> b -> a) -> a -> [b] -> a
> >
> > The function (a -> b -> a) is what I described as (T, A) -> A and it’s
> > used to fold a list of b’s into an a (the accumulator type).
> >
> > You’re right that the mapping AccumT->OutputT is not important and could
> > be delegated to a separate method. The important part of the interface is
> > mergeAccumulators() since this makes the operation distributive: we can
> > “fold” a bunch of Ts into As in parallel (even on different machines) and
> > then merge them together. This is what is missing from a functional fold.
> >
> > Best,
> > Aljoscha
> >
> >
> > > On 18. Apr 2017, at 12:03, Wesley Tanaka <wt...@yahoo.com.INVALID>
> > wrote:
> > >
> > > I believe that foldl in Haskell https://www.haskell.org/
> > hoogle/?hoogle=foldl admits a separate accumulator type from the type of
> > the data structure being "folded"
> > > And, well, python lets you have your way with mixing types, but this
> > certainly works as another example:python -c "print(reduce(lambda ac,
> elem:
> > '%s%d' % (ac,elem), [1,2,3,4,5], ''))"
> > > Is there anything special about the AccumT->OutputT conversion that
> > extractOutput() needs to be in the same interface as createAccumulator(),
> > addInput() and mergeAccumulators()? If the interface were segregated
> such
> > that one interface managed the InputT->AccumT conversion, and the second
> > managed the AccumT->InputT conversion, it seems like maybe the
> > AccumT->OutputT conversion could even get replaced with MapElements? And
> > then the full current "Combine" functionality could be implemented as a
> > composition of the lower-level primitives?
> > > I haven't dug that deeply into Combine yet, so I may be missing
> > something obvious.
> > > ---
> > > Wesley Tanaka
> > > https://wtanaka.com/
> > >
> > > On Monday, April 17, 2017, 11:32:29 PM HST, Aljoscha Krettek <
> > aljoscha@apache.org> wrote:Hi,
> > > I think both fold and reduce fail to capture all the power or (what we
> > call) combine. Reduce requires a function of type (T, T) -> T. It
> requires
> > that the output type be the same as the input type. Fold takes a function
> > (T, A) -> A where T is the input type and A is the accumulation type.
> Here,
> > the output type can be different from the input type. However, there is
> no
> > way of combining these aggregators so the operation is not distributive,
> > i.e. we cannot hierarchically apply the operation.
> > >
> > > Combine is the generalisation of this: We have three types, T (input),
> A
> > (accumulator), O (output) and we require a function that can merge
> > accumulators. The operation is distributive, meaning we can efficiently
> > execute it and we can also have an output type that is different from the
> > input type.
> > >
> > > Quick FYI: in Flink the CombineFn is called AggregatingFunction and
> > CombiningState is AggregatingState.
> > >
> > > Best,
> > > Aljoscha
> > >> On 18. Apr 2017, at 04:29, Wesley Tanaka <wt...@yahoo.com.INVALID>
> > wrote:
> > >>
> > >> As I start to understand Combine.Globally, it seems that it is, in
> > spirit, Beam's implementation of the "fold" higher-order function
> > >> https://en.wikipedia.org/wiki/Fold_(higher-order_function)#
> > Folds_in_various_languages
> > >>
> > >> Was there a reason the word "combine" was picked instead of either
> > "fold" or "reduce"? From the wikipedia list above, it seems as though
> > "fold" and "reduce" are in much more common usage, so either of those
> might
> > be easier for newcomers to understand.
> > >> ---
> > >> Wesley Tanaka
> > >> http://wtanaka.com/
> >
> >
>
Re: Naming of Combine.Globally
Posted by Dan Halperin <dh...@google.com.INVALID>.
Great discussion! As Aljoscha says, Fold, Reduce, and Combine are all
intertwined and not quite identical as we use them.
Another simple but perhaps coy answer is that if you read the MapReduce
paper by Dean and Ghemawat that started this all, they used "Map",
"Reduce", and "Combine" (see section 4.3:
https://research.google.com/archive/mapreduce.html)
So then it's likely just the lineage of Beam as "evolving from MapReduce"
:). [Looking around the source tree: we have MapElements, ReduceFn, and
Combine. And the DataflowRunner has Shuffle inside of GroupByKey. ;)]
Dan
On Tue, Apr 18, 2017 at 3:16 AM, Aljoscha Krettek <al...@apache.org>
wrote:
> The definition of foldl in Haskell is the same as the description I gave
> earlier:
>
> foldl :: (a -> b -> a) -> a -> [b] -> a
>
> The function (a -> b -> a) is what I described as (T, A) -> A and it’s
> used to fold a list of b’s into an a (the accumulator type).
>
> You’re right that the mapping AccumT->OutputT is not important and could
> be delegated to a separate method. The important part of the interface is
> mergeAccumulators() since this makes the operation distributive: we can
> “fold” a bunch of Ts into As in parallel (even on different machines) and
> then merge them together. This is what is missing from a functional fold.
>
> Best,
> Aljoscha
>
>
> > On 18. Apr 2017, at 12:03, Wesley Tanaka <wt...@yahoo.com.INVALID>
> wrote:
> >
> > I believe that foldl in Haskell https://www.haskell.org/
> hoogle/?hoogle=foldl admits a separate accumulator type from the type of
> the data structure being "folded"
> > And, well, python lets you have your way with mixing types, but this
> certainly works as another example:python -c "print(reduce(lambda ac, elem:
> '%s%d' % (ac,elem), [1,2,3,4,5], ''))"
> > Is there anything special about the AccumT->OutputT conversion that
> extractOutput() needs to be in the same interface as createAccumulator(),
> addInput() and mergeAccumulators()? If the interface were segregated such
> that one interface managed the InputT->AccumT conversion, and the second
> managed the AccumT->InputT conversion, it seems like maybe the
> AccumT->OutputT conversion could even get replaced with MapElements? And
> then the full current "Combine" functionality could be implemented as a
> composition of the lower-level primitives?
> > I haven't dug that deeply into Combine yet, so I may be missing
> something obvious.
> > ---
> > Wesley Tanaka
> > https://wtanaka.com/
> >
> > On Monday, April 17, 2017, 11:32:29 PM HST, Aljoscha Krettek <
> aljoscha@apache.org> wrote:Hi,
> > I think both fold and reduce fail to capture all the power or (what we
> call) combine. Reduce requires a function of type (T, T) -> T. It requires
> that the output type be the same as the input type. Fold takes a function
> (T, A) -> A where T is the input type and A is the accumulation type. Here,
> the output type can be different from the input type. However, there is no
> way of combining these aggregators so the operation is not distributive,
> i.e. we cannot hierarchically apply the operation.
> >
> > Combine is the generalisation of this: We have three types, T (input), A
> (accumulator), O (output) and we require a function that can merge
> accumulators. The operation is distributive, meaning we can efficiently
> execute it and we can also have an output type that is different from the
> input type.
> >
> > Quick FYI: in Flink the CombineFn is called AggregatingFunction and
> CombiningState is AggregatingState.
> >
> > Best,
> > Aljoscha
> >> On 18. Apr 2017, at 04:29, Wesley Tanaka <wt...@yahoo.com.INVALID>
> wrote:
> >>
> >> As I start to understand Combine.Globally, it seems that it is, in
> spirit, Beam's implementation of the "fold" higher-order function
> >> https://en.wikipedia.org/wiki/Fold_(higher-order_function)#
> Folds_in_various_languages
> >>
> >> Was there a reason the word "combine" was picked instead of either
> "fold" or "reduce"? From the wikipedia list above, it seems as though
> "fold" and "reduce" are in much more common usage, so either of those might
> be easier for newcomers to understand.
> >> ---
> >> Wesley Tanaka
> >> http://wtanaka.com/
>
>
Re: Naming of Combine.Globally
Posted by Aljoscha Krettek <al...@apache.org>.
The definition of foldl in Haskell is the same as the description I gave earlier:
foldl :: (a -> b -> a) -> a -> [b] -> a
The function (a -> b -> a) is what I described as (T, A) -> A and it’s used to fold a list of b’s into an a (the accumulator type).
You’re right that the mapping AccumT->OutputT is not important and could be delegated to a separate method. The important part of the interface is mergeAccumulators() since this makes the operation distributive: we can “fold” a bunch of Ts into As in parallel (even on different machines) and then merge them together. This is what is missing from a functional fold.
Best,
Aljoscha
> On 18. Apr 2017, at 12:03, Wesley Tanaka <wt...@yahoo.com.INVALID> wrote:
>
> I believe that foldl in Haskell https://www.haskell.org/hoogle/?hoogle=foldl admits a separate accumulator type from the type of the data structure being "folded"
> And, well, python lets you have your way with mixing types, but this certainly works as another example:python -c "print(reduce(lambda ac, elem: '%s%d' % (ac,elem), [1,2,3,4,5], ''))"
> Is there anything special about the AccumT->OutputT conversion that extractOutput() needs to be in the same interface as createAccumulator(), addInput() and mergeAccumulators()? If the interface were segregated such that one interface managed the InputT->AccumT conversion, and the second managed the AccumT->InputT conversion, it seems like maybe the AccumT->OutputT conversion could even get replaced with MapElements? And then the full current "Combine" functionality could be implemented as a composition of the lower-level primitives?
> I haven't dug that deeply into Combine yet, so I may be missing something obvious.
> ---
> Wesley Tanaka
> https://wtanaka.com/
>
> On Monday, April 17, 2017, 11:32:29 PM HST, Aljoscha Krettek <al...@apache.org> wrote:Hi,
> I think both fold and reduce fail to capture all the power or (what we call) combine. Reduce requires a function of type (T, T) -> T. It requires that the output type be the same as the input type. Fold takes a function (T, A) -> A where T is the input type and A is the accumulation type. Here, the output type can be different from the input type. However, there is no way of combining these aggregators so the operation is not distributive, i.e. we cannot hierarchically apply the operation.
>
> Combine is the generalisation of this: We have three types, T (input), A (accumulator), O (output) and we require a function that can merge accumulators. The operation is distributive, meaning we can efficiently execute it and we can also have an output type that is different from the input type.
>
> Quick FYI: in Flink the CombineFn is called AggregatingFunction and CombiningState is AggregatingState.
>
> Best,
> Aljoscha
>> On 18. Apr 2017, at 04:29, Wesley Tanaka <wt...@yahoo.com.INVALID> wrote:
>>
>> As I start to understand Combine.Globally, it seems that it is, in spirit, Beam's implementation of the "fold" higher-order function
>> https://en.wikipedia.org/wiki/Fold_(higher-order_function)#Folds_in_various_languages
>>
>> Was there a reason the word "combine" was picked instead of either "fold" or "reduce"? From the wikipedia list above, it seems as though "fold" and "reduce" are in much more common usage, so either of those might be easier for newcomers to understand.
>> ---
>> Wesley Tanaka
>> http://wtanaka.com/
Re: Naming of Combine.Globally
Posted by Robert Bradshaw <ro...@google.com.INVALID>.
On Tue, Apr 18, 2017 at 3:03 AM, Wesley Tanaka
<wt...@yahoo.com.invalid> wrote:
> I believe that foldl in Haskell https://www.haskell.org/hoogle/?hoogle=foldl admits a separate accumulator type from the type of the data structure being "folded"
> And, well, python lets you have your way with mixing types, but this certainly works as another example:python -c "print(reduce(lambda ac, elem: '%s%d' % (ac,elem), [1,2,3,4,5], ''))"
> Is there anything special about the AccumT->OutputT conversion that extractOutput() needs to be in the same interface as createAccumulator(), addInput() and mergeAccumulators()? If the interface were segregated such that one interface managed the InputT->AccumT conversion, and the second managed the AccumT->InputT conversion, it seems like maybe the AccumT->OutputT conversion could even get replaced with MapElements? And then the full current "Combine" functionality could be implemented as a composition of the lower-level primitives?
It is correct that the AccumT->OutputT conversion could be implemented
as a subsequent MapElements operation. One reason that it's not is
that in practice it's tightly coupled with the other parts of the
Combine as a single semantic unit (e.g. one things of taking the
"mean" as a single operation). Once one moves beyond the simple
combiners (with identity extractOutput) there's often a 1:1
correspondence between the CombineFn and its output extraction that
reduces potential value of splitting them while placing further burden
on their user (e.g. there's little use for the Quantiles intermediate
accumulator without the mapping from that actual quantiles, and vice
versa).
Also, letting the extractOutput be part of the CombineFn itself rather
than simply providing a separate Map allows one to use the CombineFn
uniformly for global combine, per-key combine, and combined state. It
also makes it more compossible (e.g. the TupleCombineFns at
https://github.com/apache/beam/blob/release-0.6.0/sdks/python/apache_beam/transforms/combiners.py#L443
that create a single CombineFn (including the output extraction) from
a set of CombineFns applying each in parallel.
- Robert
Re: Naming of Combine.Globally
Posted by Wesley Tanaka <wt...@yahoo.com.INVALID>.
I believe that foldl in Haskell https://www.haskell.org/hoogle/?hoogle=foldl admits a separate accumulator type from the type of the data structure being "folded"
And, well, python lets you have your way with mixing types, but this certainly works as another example:python -c "print(reduce(lambda ac, elem: '%s%d' % (ac,elem), [1,2,3,4,5], ''))"
Is there anything special about the AccumT->OutputT conversion that extractOutput() needs to be in the same interface as createAccumulator(), addInput() and mergeAccumulators()? If the interface were segregated such that one interface managed the InputT->AccumT conversion, and the second managed the AccumT->InputT conversion, it seems like maybe the AccumT->OutputT conversion could even get replaced with MapElements? And then the full current "Combine" functionality could be implemented as a composition of the lower-level primitives?
I haven't dug that deeply into Combine yet, so I may be missing something obvious.
---
Wesley Tanaka
https://wtanaka.com/
On Monday, April 17, 2017, 11:32:29 PM HST, Aljoscha Krettek <al...@apache.org> wrote:Hi,
I think both fold and reduce fail to capture all the power or (what we call) combine. Reduce requires a function of type (T, T) -> T. It requires that the output type be the same as the input type. Fold takes a function (T, A) -> A where T is the input type and A is the accumulation type. Here, the output type can be different from the input type. However, there is no way of combining these aggregators so the operation is not distributive, i.e. we cannot hierarchically apply the operation.
Combine is the generalisation of this: We have three types, T (input), A (accumulator), O (output) and we require a function that can merge accumulators. The operation is distributive, meaning we can efficiently execute it and we can also have an output type that is different from the input type.
Quick FYI: in Flink the CombineFn is called AggregatingFunction and CombiningState is AggregatingState.
Best,
Aljoscha
> On 18. Apr 2017, at 04:29, Wesley Tanaka <wt...@yahoo.com.INVALID> wrote:
>
> As I start to understand Combine.Globally, it seems that it is, in spirit, Beam's implementation of the "fold" higher-order function
> https://en.wikipedia.org/wiki/Fold_(higher-order_function)#Folds_in_various_languages
>
> Was there a reason the word "combine" was picked instead of either "fold" or "reduce"? From the wikipedia list above, it seems as though "fold" and "reduce" are in much more common usage, so either of those might be easier for newcomers to understand.
> ---
> Wesley Tanaka
> http://wtanaka.com/
Re: Naming of Combine.Globally
Posted by Aljoscha Krettek <al...@apache.org>.
Hi,
I think both fold and reduce fail to capture all the power or (what we call) combine. Reduce requires a function of type (T, T) -> T. It requires that the output type be the same as the input type. Fold takes a function (T, A) -> A where T is the input type and A is the accumulation type. Here, the output type can be different from the input type. However, there is no way of combining these aggregators so the operation is not distributive, i.e. we cannot hierarchically apply the operation.
Combine is the generalisation of this: We have three types, T (input), A (accumulator), O (output) and we require a function that can merge accumulators. The operation is distributive, meaning we can efficiently execute it and we can also have an output type that is different from the input type.
Quick FYI: in Flink the CombineFn is called AggregatingFunction and CombiningState is AggregatingState.
Best,
Aljoscha
> On 18. Apr 2017, at 04:29, Wesley Tanaka <wt...@yahoo.com.INVALID> wrote:
>
> As I start to understand Combine.Globally, it seems that it is, in spirit, Beam's implementation of the "fold" higher-order function
> https://en.wikipedia.org/wiki/Fold_(higher-order_function)#Folds_in_various_languages
>
> Was there a reason the word "combine" was picked instead of either "fold" or "reduce"? From the wikipedia list above, it seems as though "fold" and "reduce" are in much more common usage, so either of those might be easier for newcomers to understand.
> ---
> Wesley Tanaka
> http://wtanaka.com/