GitHub

Glossary

foldl(step, xf, input, init=...)
#  |   |    |     |
#  |   |    |     `-- reducible
#  |   |    |
#  |   |    `-- transducer
#  |   |
#  |   `-- "bottom" (inner most) reducing function
#  |
#  `-- transducible process

Reducing step function

Reducing function or Reducing step (function): A reducing function combines result-so-far with the input. It in a narrow sense is a "callable" op of the signature op(::X, ::Y) :: X (or op(::X, ::X) :: X in case for foldxt) or schematically:

\[(\text{result-so-far}, \text{input}) \mapsto \text{result-so-far}\]

It is the function that can be passed to the classic (non-Transducers.jl) Base.foldl or Base.reduce. It is sometimes referred to as a step or op. In Transducers.jl, next(rf, ::X, ::Y) :: X is used instead of a "bare" callable. Furthermore, a reducing function in a loose sense also includes other interfaces such as start(rf, ::X) and complete(rf, ::X).

Transducer

A transducer in Transducers.jl is a transformation xf that

  • transforms an iterator with xf(itr) (iterator transformation)
  • transforms a reducing step function with xf'(rf) (reducing function transformation)

Common variable names for transducers are xf and xform.

The idea of generalizing the transducer as two kinds of transformation is due to Jan Weidner @jw3126. See the discussion in JuliaFolds/Transducers.jl#67.

Iterator transformation

As of Transducers.jl 0.4.39, the call overload of Transducer is interpreted as an iterator transformation. That is to say, the iterator transformation using Base.Iterators

julia> ixf₁ = itr -> Iterators.filter(isodd, itr);

and the iterator transformation in Transducers.jl

julia> ixf₂ = Filter(isodd);

behaves identically:

julia> collect(ixf₁(1:10)) == collect(ixf₂(1:10))
true

Filter(isodd)(1:10) is an eduction.

Reducing function transformation

Transducers.jl 0.4.39 also exposes reducing function (RF) transformation with xf'(rf) (adjoint):

julia> rf = Filter(isodd)'(+);  # equivalent to (acc, x) -> isodd(x) ? acc + x : acc;

julia> rf(0, 2)  # `2` filtered out
0

julia> rf(0, 1)  # `1` not filtered out
1

Transducer in the narrow sense (Clojure)

The transducer as originally introduced by Rich Hickey is a transformation of reducing step function. Thus, what is referred to as a transducer $\mathrm{xf}$ in Clojure and many other languages is the reducing function transformation xf' in Transducer.jl.

Since a transducer in the narrow sense maps a reducing function to a reducing function, it can be composed with simple function composition $∘$. When a composite transducer $\mathrm{xf} = \mathrm{xf}_1 \circ \mathrm{xf}_2 \circ ... \circ \mathrm{xf}_n$ to a "bottom" reducing function $\mathrm{rf}_0$, it is processed from right to left just like normal functions:

\[\mathrm{rf} = \mathrm{xf}_1(\mathrm{xf}_2(...(\mathrm{xf}_{n}(\mathrm{rf}_0))))\]

which is equivalent to the following forms in Transducers.jl

rf = xf₁'(xf₂'(...(xfₙ'(rf₀))))
rf = (xf₁' ∘ xf₂' ∘ ... ∘ xfₙ')(rf₀)
rf = (xfₙ ∘ ... ∘ xf₂ ∘ xf₁)'(rf₀)
rf = (xf₁ ⨟ xf₂ ⨟ ... ⨟ xfₙ)(rf₀)

Inner transducer

Given a composition xf₁' ∘ xf₂', transducer xf₂ is said to be the inner transducer of xf₁' ∘ xf₂'. Likewise, xf₂'(rf₀) is an inner reducing function of xf₁'(xf₂'(rf₀)).

Reducible collection

Reducible collection (or just Reducible): Any object that can be passed to foldl and alike is reducible. A reducible collection knows how to apply reducing function to its elements. Iterators are automatically reducible as this is the canonical fallback implementation.

Transducible process

A function that can foldxt reducible collections using transducers is a transducible process. Examples are foldl and foldxt. Find more in Transducible processes.

Executor

An executor such as SequentialEx, ThreadedEx and DistributedEx specifies the execution mechanism of a fold. These executors provide a unified mechanism for choosing underlying execution mechanism for Transducers.jl and its related packages such as Folds.jl and FLoops.jl. Typically, the API functions take an executor as the last optional argument. In addition to the executors provided by Transducers.jl (see Executors section in the manual), additional executors are provided from external packages such as FoldsThreads.jl (various thread-based executors) and FoldsCUDA.jl (a CUDA-based executor).

Transducers.jl's executor is a concept similar to KernelAbstractions.jl' device.