Seqs & Iterators 2: Transducer-oo

[lilactown]

This is a continuation of #22

Proposal

We implement sequence operators (map, filter, etc.) as lazy iterables, rather than eagerly returning arrays like we do today.

What we've learned

Since developing the IIterable protocol and the rest of the community doing some experiments, we have learned a couple things:

1. Iterables are very flexible and have great runtime support. It is easy for us to construct them in a Clojure-y protocol way. Most of the clava.core library "just works" with any iterable object at this point.
2. Using eager versions of sequence ops like map, filter, etc. breaks expectations when moving from Clojure to Clava
3. Transducers require a lot of code. Transducers #139 shows the amount of code required for just the core protocol and a few operators, it's over 130 lines. Transducers are also not the first thing that most people reach for when developing; in Clojure, they only are heavily getting used in performance sensitive contexts.

Iterators & iterables & generators, oh my

Generators are native JS constructs that allow one to create lazy iterators using the special function* and yield keywords.

function* genRange(n = Infinity) {
  for (let i = 0; i < n; i++) {
    yield i;
  }
}

// logs 0, 1, 2, 3, 4
for (const x of genRange(5)) {
  console.log(x);
}

Generator functions return iterators. Iterators work with for...of and destructuring. As pointed out in #22, iterators are mutable, so one has to be careful when passing them around

let xs = genRange(5);

// prints 0, 1, 2, 3, 4
for (const x of xs) {
  console.log(x);
}

// prints nothing
for (const x of xs) {
  console.log(x);
}

However, iterable objects implement #125 and return a new iterator every time they are used in a for...of or destructured.

class Range {
  constructor(n) {
    this.n = n;
  }
  [Symbol.iterator]() {
    return genRange(this.n);
  }
}

xs = new Range(5);

// prints 0, 1, 2, 3, 4
for (const x of xs) {
  console.log(x);
}

// prints 0, 1, 2, 3, 4
for (const x of xs) {
  console.log(x);
}

So you if you construct the object right, an iterable can act as the immutable version of the iterator. A generator can easily create a lazy iterator. Therefore you can have a generic immutable LazyIterable class (see #138), akin to LazySeq in Clojure, that all sequence ops like map, filter, for, etc. build on top of.

Transducers are a higher abstraction

Transducers are more general than lazy sequences or iterators. Transducers represent a trans-formation of a re-_ducer_ function, and it turns out reducer functions are used everywhere, including:

• Working with collections like arrays, objects, maps and sets
• Working with channels a la core.async
• Working with streams a la RxJS

Basically any time you are combining a "result" and a "next" element, you've got a reducer, which means you can use transducers.

Programming with highly general abstractions can allow one to wield a lot of power, however they can also place a greater toll on the user. Take the following code:

;; lazy seq
(->> (range) (filter even?) (map inc) (take 10) (vec))

;; transducers
(into [] (comp (filter even?) (map inc) (take 10)) (range))

Most developers find the former easier to read and modify.

Adding a reducing step in between operations is also easy to add to the lazy seq version while requiring a significant rewrite in the transducer version. Nested transducing steps also get even harder to read.

A lot of people coming to Clava are used to writing the former code, but in Clava it will break as filter and map are eager; they will attempt to realize the entire infinite range into an array and lead to a stack overflow.

Transducers also introduce a lot of code. I think it's worth weighing whether it's good to include it or not. I am still for it, but ensuring that we have lazy sequences too means that we don't need it to work with core things like (repeat 1) (range) etc.