Composable API for asserting algebraic properties and specifying execution strategy

[tkf]

Transducers.jl now has different kinds of fold that are usable with different algebraic properties of the reducing function:

• binary function: foldl / transduce
• monoid (semigroup): reduce / transduce_assoc
• commutative monoid: reduce_commutative / transduce_commutative! (related: foreach(ndreducible(...)); foldl-based API to implement GEMM https://tkf.github.io/NDReducibles.jl/dev/)

Some of those functions are not exposed, as it was hard to come up with a consistent and composable interface.

This is not the only way to categorize the folds. Another axis is based on the execution mechanism:

• sequential: foldl / collect / copy
• threaded divide-and-conquer: reduce / tcollect / tcopy
• distributed fork-join: dreduce / dcollect / dcopy

Problems

It is ugly that the execution strategies are encoded in one-letter prefixes like t and d. It is also hard to express other useful strategies:

• single-threaded version of reduce to get pair-wise summation even in single-thread
  • simd = true can be set by default in this case.
• single-threaded version of reduce_commutative when there is non-canonical iteration order (e.g., block matrix, ndreducible)

It is also impossible to let Transducers.jl choose the best strategy even though relevant information is already/can be encoded in the transducer/reducing function types.

Wants

• Orthogonalize the algebraic properties and execution mechanisms.
• An entry point that automatically chooses execution strategy.

Idea

Specifying strategy

One solution may be to introduce a new function fold (no l)

fold(rf, xf, coll; strategy = Auto(), ...)

where strategy can be something like

Auto()  # i.e. DWIM
Sequential()
Unordered()
ThreadedPairwise(basesize)  # ThreadedDivideAndConquer()? ThreadedDAC()?
ThreadedUnordered(basesize)
DistributedForkJoin(pool, basesize, inner_strategy)

s.t

foldl(rf, xf, coll) = fold(rf, xf, coll; strategy = Sequential())
reduce(rf, xf, coll; basesize) =
    fold(rf, xf, coll; strategy = ThreadedPairwise(basesize))
dreduce(rf, xf, coll; basesize, threads_basesize, pool) =
    fold(rf, xf, coll; strategy = Distributed(pool, basesize, ThreadedPairwise(threads_basesize)))

Asserting algebraic properties

Use some wrapper factory to declare the algebraic properties of reducing functions and transducers:

associative(op)
commutative(op)
stateless(xf)

For example:

op = (x, y) -> x + y
fold(op, Map(identity), coll)               # => foldl
fold(associative(op), Map(identity), coll)  # => reduce

[jtrakk]

Would it make sense to offer the strategy as an optional first positional argument like foldl([strategy,] rf, xf, coll) so the user can have more control over dispatch?