> On 31 May 2017, at 14:23, Steffen Märcker <merk...@web.de> wrote:
>
> Hi,
>
> I am the developer of the library 'Transducers' for VisualWorks. It
was
formerly known as 'Reducers', but this name was a poor choice. I'd like
to
port it to Pharo, if there is any interest on your side. I hope to learn
more about Pharo in this process, since I am mainly a VW guy. And most
likely, I will come up with a bunch of questions. :-)
>
> Meanwhile, I'll cross-post the introduction from VWnc below. I'd be
very
happy to hear your optinions, questions and I hope we can start a
fruitful
discussion - even if there is not Pharo port yet.
>
> Best, Steffen
Hi Steffen,
Looks like very interesting stuff. Would make an nice library/framework
for Pharo.
Sven
> Transducers are building blocks that encapsulate how to process
elements
> of a data sequence independently of the underlying input and output
source.
>
>
>
> # Overview
>
> ## Encapsulate
> Implementations of enumeration methods, such as #collect:, have the
logic
> how to process a single element in common.
> However, that logic is reimplemented each and every time. Transducers
make
> it explicit and facilitate re-use and coherent behavior.
> For example:
> - #collect: requires mapping: (aBlock1 map)
> - #select: requires filtering: (aBlock2 filter)
>
>
> ## Compose
> In practice, algorithms often require multiple processing steps, e.g.,
> mapping only a filtered set of elements.
> Transducers are inherently composable, and hereby, allow to make the
> combination of steps explicit.
> Since transducers do not build intermediate collections, their
composition
> is memory-efficient.
> For example:
> - (aBlock1 filter) * (aBlock2 map) "(1.) filter and (2.) map
elements"
>
>
> ## Re-Use
> Transducers are decoupled from the input and output sources, and
hence,
> they can be reused in different contexts.
> For example:
> - enumeration of collections
> - processing of streams
> - communicating via channels
>
>
>
> # Usage by Example
>
> We build a coin flipping experiment and count the occurrence of heads
and
> tails.
>
> First, we associate random numbers with the sides of a coin.
>
> scale := [:x | (x * 2 + 1) floor] map.
> sides := #(heads tails) replace.
>
> Scale is a transducer that maps numbers x between 0 and 1 to 1 and 2.
> Sides is a transducer that replaces the numbers with heads an tails by
> lookup in an array.
> Next, we choose a number of samples.
>
> count := 1000 take.
>
> Count is a transducer that takes 1000 elements from a source.
> We keep track of the occurrences of heads an tails using a bag.
>
> collect := [:bag :c | bag add: c; yourself].
>
> Collect is binary block (reducing function) that collects events in a
bag.
> We assemble the experiment by transforming the block using the
transducers.
>
> experiment := (scale * sides * count) transform: collect.
>
> From left to right we see the steps involved: scale, sides, count and
> collect.
> Transforming assembles these steps into a binary block (reducing
function)
> we can use to run the experiment.
>
> samples := Random new
> reduce: experiment
> init: Bag new.
>
> Here, we use #reduce:init:, which is mostly similar to #inject:into:.
> To execute a transformation and a reduction together, we can use
> #transduce:reduce:init:.
>
> samples := Random new
> transduce: scale * sides * count
> reduce: collect
> init: Bag new.
>
> We can also express the experiment as data-flow using #<~.
> This enables us to build objects that can be re-used in other
experiments.
>
> coin := sides <~ scale <~ Random new.
> flip := Bag <~ count.
>
> Coin is an eduction, i.e., it binds transducers to a source and
> understands #reduce:init: among others.
> Flip is a transformed reduction, i.e., it binds transducers to a
reducing
> function and an initial value.
> By sending #<~, we draw further samples from flipping the coin.
>
> samples := flip <~ coin.
>
> This yields a new Bag with another 1000 samples.
>
>
>
> # Basic Concepts
>
> ## Reducing Functions
>
> A reducing function represents a single step in processing a data
sequence.
> It takes an accumulated result and a value, and returns a new
accumulated
> result.
> For example:
>
> collect := [:col :e | col add: e; yourself].
> sum := #+.
>
> A reducing function can also be ternary, i.e., it takes an accumulated
> result, a key and a value.
> For example:
>
> collect := [:dic :k :v | dict at: k put: v; yourself].
>
> Reducing functions may be equipped with an optional completing action.
> After finishing processing, it is invoked exactly once, e.g., to free
> resources.
>
> stream := [:str :e | str nextPut: each; yourself] completing:
#close.
> absSum := #+ completing: #abs
>
> A reducing function can end processing early by signaling Reduced
with a
> result.
> This mechanism also enables the treatment of infinite sources.
>
> nonNil := [:res :e | e ifNil: [Reduced signalWith: res] ifFalse:
[res]].
>
> The primary approach to process a data sequence is the reducing
protocol
> with the messages #reduce:init: and #transduce:reduce:init: if
transducers
> are involved.
> The behavior is similar to #inject:into: but in addition it takes care
of:
> - handling binary and ternary reducing functions,
> - invoking the completing action after finishing, and
> - stopping the reduction if Reduced is signaled.
> The message #transduce:reduce:init: just combines the transformation
and
> the reducing step.
>
> However, as reducing functions are step-wise in nature, an application
may
> choose other means to process its data.
>
>
> ## Reducibles
>
> A data source is called reducible if it implements the reducing
protocol.
> Default implementations are provided for collections and streams.
> Additionally, blocks without an argument are reducible, too.
> This allows to adapt to custom data sources without additional effort.
> For example:
>
> "XStreams adaptor"
> xstream := filename reading.
> reducible := [[xstream get] on: Incomplete do: [Reduced signal]].
>
> "natural numbers"
> n := 0.
> reducible := [n := n+1].
>
>
> ## Transducers
>
> A transducer is an object that transforms a reducing function into
another.
> Transducers encapsulate common steps in processing data sequences,
such
as
> map, filter, concatenate, and flatten.
> A transducer transforms a reducing function into another via
#transform:
> in order to add those steps.
> They can be composed using #* which yields a new transducer that does
both
> transformations.
> Most transducers require an argument, typically blocks, symbols or
numbers:
>
> square := Map function: #squared.
> take := Take number: 1000.
>
> To facilitate compact notation, the argument types implement
corresponding
> methods:
>
> squareAndTake := #squared map * 1000 take.
>
> Transducers requiring no argument are singletons and can be accessed
by
> their class name.
>
> flattenAndDedupe := Flatten * Dedupe.
>
>
>
> # Advanced Concepts
>
> ## Data flows
>
> Processing a sequence of data can often be regarded as a data flow.
> The operator #<~ allows define a flow from a data source through
> processing steps to a drain.
> For example:
>
> squares := Set <~ 1000 take <~ #squared map <~ (1 to: 1000).
> fileOut writeStream <~ #isSeparator filter <~ fileIn readStream.
>
> In both examples #<~ is only used to set up the data flow using
reducing
> functions and transducers.
> In contrast to streams, transducers are completely independent from
input
> and output sources.
> Hence, we have a clear separation of reading data, writing data and
> processing elements.
> - Sources know how to iterate over data with a reducing function,
e.g.,
> via #reduce:init:.
> - Drains know how to collect data using a reducing function.
> - Transducers know how to process single elements.
>
>
> ## Reductions
>
> A reduction binds an initial value or a block yielding an initial
value
to
> a reducing function.
> The idea is to define a ready-to-use process that can be applied in
> different contexts.
> Reducibles handle reductions via #reduce: and #transduce:reduce:
> For example:
>
> sum := #+ init: 0.
> sum1 := #(1 1 1) reduce: sum.
> sum2 := (1 to: 1000) transduce: #odd filter reduce: sum.
>
> asSet := [:set :e | set add: e; yourself] initializer: [Set new].
> set1 := #(1 1 1) reduce: asSet.
> set2 := #(1 to: 1000) transduce: #odd filter reduce: asSet.
>
> By combining a transducer with a reduction, a process can be further
> modified.
>
> sumOdds := sum <~ #odd filter
> setOdds := asSet <~ #odd filter
>
>
> ## Eductions
>
> An eduction combines a reducible data sources with a transducer.
> The idea is to define a transformed (virtual) data source that needs
not
> to be stored in memory.
>
> odds1 := #odd filter <~ #(1 2 3) readStream.
> odds2 := #odd filter <~ (1 to 1000).
>
> Depending on the underlying source, eductions can be processed once
> (streams, e.g., odds1) or multiple times (collections, e.g., odds2).
> Since no intermediate data is stored, transducers actions are lazy,
i.e.,
> they are invoked each time the eduction is processed.
>
>
>
> # Origins
>
> Transducers is based on the same-named Clojure library and its ideas.
> Please see:
> http://clojure.org/transducers
>
