Skip to content

Latest commit

 

History

History
160 lines (122 loc) · 5.39 KB

glossary.md

File metadata and controls

160 lines (122 loc) · 5.39 KB
Raw

Glossary

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

[Reducing step function](@id glossary-rf)

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](@ref Transducers.next) is used instead of a "bare" callable. Furthermore, a reducing function in a loose sense also includes other interfaces such as [start(rf, ::X)](@ref Transducers.start) and [complete(rf, ::X)](@ref Transducers.complete).

[Transducer](@id glossary-transducer)

A transducer in Transducers.jl is a transformation xf that

  • transforms an iterator with [xf(itr)](@ref eduction) (iterator transformation)
  • transforms a reducing step function with [xf'(rf)](@ref adjoint) (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](@id glossary-ixf)

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](@id glossary-rfxf)

Transducers.jl 0.4.39 also exposes reducing function (RF) transformation with [xf'(rf)](@ref adjoint) (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](@id glossary-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](@ref man-executor) 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.