making things cleaner, more transparent, more consistent: road to 1.0

[ExpandingMan]

I have been doing some work on the package lately and have some thoughts on what needs
improving.

Problems

Here are, as I see it, some problems with the package in its current state.

API Entropy

There are many different ways of doing the same thing which are in some cases distinct in arbitrary
and confusing ways, while in other cases are subtly but curcially different. For example, the
package exports transduce as well as foldxl and adds methods to foldl. transduce and
foldxl differ primarily in that transduce may return a Reduced, while foldxl and foldl are
largely equivalent (I don't think they have exactly the same methods but it's hard to even tell).

Opacity of Folds

Functions such as copy and collect arguably don't look like one would reasonably expect based on
the fundamentals such as foldxl. For example, it seems reasonable to expect something very much
like

collect(xf::Transducer, itr) = foldxl(append!!, xf, itr; init=Empty(Vector))

The truth is much more complicated than this, for good reason. I am not suggesting that we
compromise the convenience of functions such as collect, however I consider it a problem when
these functions rely on complicated opaque voodoo.

The catch here is that, for obvious performance reasons, one should not simply append!! separate
arrays, instead Transducers figures out that it can allocate an undef Vector and insert objects
into it. This situation is greatly complicated by the need to infer a container type prior to
executing the fold, which Julia itself doesn't provide an API for handling (more on this in a
moment).

In my view, this issue is of more than mere aesthetic interest. It leads to a lot of behavior which
reasonable users might not expect, for example, the following 3 lines all error on latest main:

copy(Map(x -> x=>(x+1))'(merge!!), Dict, 1:3)  # MethodError: copy lacks Reduction argument
copy(Map(x -> SingletonDict(x=>x+1)), Dict, 1:3)  # BoundsError, bet you didn't see that coming
copy(Map(x -> SingletonDict(x=>x+1))'(merge!!), Dict, 1:3)  # same MethodError as first one

Too Much Dependence on Complicated Type Inference Voodoo

I am worried code using Transducers.jl could easily become too difficult to optimize, and due to use
of undocumented Julia internals might degrade over time. The crux of this is a method of
transduce used in practically every invocation of Transducers.jl which one immediately runs into
when analyzing code with JET.jl, found
here.
In particular, there can be type instability arising from convert(realtype, ur_result). This is
an extremely difficult problem to address because it is more of a fundamental problem with Julia
than Transducers.jl in particular. The issue is of course that Julia does not expose its type
inference machinery, so calls to Core.Compiler.return_type may be unavoidable for the crucial use
case of inferring an appropriate container type before folding is executed.

Threaded Functions are Inflexible

Threaded functions, i.e. those based on foldxt, rely on being provided an associative reduction
step. This is reasonable as a default, but unfortunately there is no way to check whether a step is
associative a priori, which can lead to undefined behavior. From a user perspective, this can lead
to some rather confusing results when exchanging foldxl for foldxt. The associative requirement
comes from the need for foldxt to know how to combine results from each thread, but it currently
doesn't allow for any way of specifying non-associative operations in the thread-local case in
addition to a way to combine those results, meaning that users essentially need to write the
threading code "from scratch" if attempting this. Note that non-associative operations such as
push!! are quite common.

Possible Solutions

I propose that transduce be made private (this was suggested by TKF in the code) and that package
internals should be rewritten where appropriate, and users should be instructed to rely on

foldxl(step, xf, itr; init=Init(step))

(or something very similar) as a "fundamental" method. I'm not proposing that frequently used
convenience functions such as collect, copy and their threaded equivalents be discarded, but
they should be related to foldxl in a more transparent and understandable way.

One of the prerequisites for achieving this is a more accessible, transparent way of dealing with
cases where, instead of e.g. combining containers with an associative step such as append!!, one
instead needs to insert results into a pre-allocated container. To that end, I propose that the API
be expanded to allow for something like this

collect(xf::Transducer, itr) = foldxl(insertinto!!, xf, itr; init=Initialized(Vector))

Granted, I'm not yet entirely confident that such an interface is feasible, but if it is it seems
greatly preferrable to the current state of affairs in which the only equivalent to such a call
involves lots of rather inscrutible internals; surely highly undesirable for such a simple and
common use case. Achieving this would likely require a bit of reworking of BangBang.jl. Note that
that the concept of default initialization already exists to some extent, for example there is
Init(op), but it is not applied uniformly in Transducers.jl internals.

As for foldxt, I believe it should be based on a method something like

foldxt(local_step, step, xflocal::Transducer, xf::Transducer, itr; init, kw...)

or perhaps something even more fundamental. We could then create additional methods, more similar
to the current methods with reasonable defaults.

Lastly, while I don't know if it's possible to clean up the type inference problems in a consistent
way, I think we should at least try. For one, I believe the notorious transduce method with
Core.Compiler.return_type was written quite a few minor versions of Julia ago. We might also be
able to branch the behavior at compile time so that it does "normal stuff" by default and falls back
to Core.Compiler.return_type when there is no better option. It might also be worth describing
the issue to some of the core Julia people in detail in the hope of getting useful advice.

[jariji]

Is the overload of ' a pun or is there some math going on that I don't see?

  xf'


  xf'(rf₁) is a shortcut for calling reducingfunction(xf, rf₁).

  More precisely, adjoint xf′ of a transducer xf is a reducing function transform rf₁ -> rf₂. That is
  to say, xf' a function that maps a reducing function rf₁ to another reducing function rf₂.

  Examples
  ≡≡≡≡≡≡≡≡≡≡

  julia> using Transducers
  
  julia> y = Map(inv)'(+)(10, 2)
  10.5
  
  julia> y == +(10, inv(2))
  true

[MasonProtter]

@ExpandingMan I'm sorry for the over a month late reply, life has been kinda hectic lately. Yeah, I think you're raising some great points here and I'd like if we could start moving forward with these ideas.

Regarding the return type stuff, a lot of this was designed by Takafumi as an exploration into how one can design efficient and flexible algorithms like this without relying on compiler internals. I think he did an impressive job at that, but ultimately I think we should probably start taking advantage of the compiler's capabilities, since as you say it could simplify a lot of code, and make it more robust.

[MasonProtter]

@jariji yes, there is some (category theory) math going on there with ', it's discussed a bit here: JuliaFolds/Transducers.jl#67

The idea is that a transducer is a function which takes in an iterable sequence and spits out a transformed iterator sequence. An adjoint-transducer is a a function which takes in a reducing function and spits out a transformed reducing function. These follow an adjoint relationship in the sense that

fold(rf, xf(itr)) == fold(xf'(rf), itr)

which should be thought of in the same sense as how for vectors u and v, we have that

u' * v == v' * u

[ExpandingMan]

I haven't been playing with this lately, as I was hoping to hear some feedback before I put a lot of work into a big PR, however I remain heavily invested in this package and have continued to gradually use it more and more. Transducers + BangBang + (other important dependencies) has become quite big, so I'm thinking of trying out my ideas in an experimental "MiniTransducers" package where I can write stuff from scratch, evaluate whether I have any good ideas, and later port them to Transducers which is potentially a big job on its own.

Is the overload of ' a pun or is there some math going on that I don't see?

I didn't respond to this earlier because I didn't immediately want to get this thread way off track, but yes, this is related to the adjoint in a fairly straightforward way, category theory not necessarily required. The usual adjoint in linear algebra takes an operator on a vector space and makes it an operator on the dual space, which is a space of "reducing" functions (in that it maps $V\to\mathbb{R}$). Now, the reducing functions in this package needn't have the same properties as a vector dual space (though they could), so the usage here is arguably over-general, especially from a strictly linear algebra point of view, but, suffice it to say, my vote would not be to change this.

[MasonProtter]

One further thought I've had about this recently is that we should have better ways of handling / preserving the shape and type of input data. This is currently pretty ad-hoc and random in Transducers. For instance:

julia> collect([1 2 ; 3 4] |> Map(sqrt))
2×2 Matrix{Float64}:
 1.0      1.41421
 1.73205  2.0

versus

julia> collect(StructArray([1+im 2 ; 3 4-im]) |> Map(sqrt))
4-element Vector{ComplexF64}:
   1.09868411346781 + 0.45508986056222733im
 1.7320508075688772 + 0.0im
 1.4142135623730951 + 0.0im
  2.015329455153383 - 0.24809839340235612im

and also

julia> collect((1,2,3,4) |> Map(sqrt))
4-element Vector{Float64}:
 1.0
 1.4142135623730951
 1.7320508075688772
 2.0

We'll probably want some "data style" traits or something for informing Transducers about how it can handle input data.

[jariji]

This is currently pretty ad-hoc and random in Transducers.

What behavior do you expect here? collect is defined to return Array, so I'm not seeing what else it could do.

[MasonProtter]

That's true. Maybe a new function would be appropriate to replace the way currently use collect(::Transducer, itr).

Something that'd be kinda weird but almost makes sense would be map. e.g.

map(Map(f) ⨟ Filter(cond), itr)

could use the Transducers system. But that looks really weird, so maybe it's best to make our own name, e.g. each could word.

each(itr |> Map(f) |> Filter(cond))

(And also have keyword arguments for things like which backend, I.e. serial, multithreaded, distributed, etc)

[jariji]

collect is defined to return Array

Update/correction: JuliaLang/julia#50051 (comment)

---

almost makes sense would be map

map is supposed to apply the transformation to each element of the input collection. So map(Map(f), itr) works if itr is a nested collection like [collect(Map(f)(x)) for x in [[1,2], [3,4]], but if itr is a normal collection map has the wrong signature.

[ExpandingMan]

In regard to shape, I don't feel I know what the right answer is, but I do find it super annoying that there's basically no way to do a shape-preserving operation with transducers. Frankly I don't think Julia's Base API is that great where shape is concerned (I sometimes find the behavior of Base.map confusing) so maybe creative solutions are called for.

[jariji]

See also JuliaLang/julia#36537

[MasonProtter]

The other thing I want to focus on if we make a push for a 1.0 is trimming down the library of transducers a lot, or implementing some major fixes.

E.g. #26 and #29

I think if we do a major refactor we should basically just start out of Map, Filter and a few other highly useful and flexible transducers and then we can expand out from there.

[MasonProtter]

I've started a repo: https://github.com/JuliaFolds2/TransducersNext.jl where I'm playing with ideas for what's next.

This repo is much less featureful than the current transducers.jl but what is here I think works pretty well. Lets discuss individual design questions there