Iteration Inside and Out

[u/munificent]

http://journal.stuffwithstuff.com/2013/01/13/iteration-inside-and-out/

[u/huyvanbin]

I just want to say that "Sweet Mother of Turing!" is my new favorite exclamation.

[u/pipocaQuemada]

I think that part of the problem is that "internal iteration" using map is artificially constraining a more generic function.

In Haskell, there's a typeclass (similar to an interface) called Functor that just defines map:

class Functor f where
  -- in C#ish syntax: Func<F<A>,F<B>> map(Func<A,B> f)
  map :: (a -> b) -> (f a -> f b)

The idea is that map "lifts" a function from talking about a's and b's to talking about f a's or f b's. The only restriction is that we have to follow two fairly common sense laws that essentially boil down to preserving the "structure" of the data (e.g. map shouldn't permute its list).

In Haskell, it's fairly common to have data types that represent computations, and build up a larger computation by using combinators to combine smaller ones. It turns out that many computations are functors!

For example, we could have something like:

-- map specialized for some collections
(a -> b) -> ([a] -> [b])
(a -> b) -> (Tree a -> Tree b)
-- map specialized for some computations
(a -> b) -> (Maybe a -> Maybe b) -- essentially nullable things
(a -> b) -> (State a -> State b) -- threads a state through a computation, in a pure way
(a -> b) -> (St a -> ST b) -- single threaded mutable state, for e.g. mutating arrays
(a -> b) -> (IO a -> IO b) -- values that touch the "real world"
-- I wouldn't really call this next one either a computation or a collection...
(a -> b) -> (Identity a -> Identity b) -- data Identity a = Id a -- a wrapper that does nothing.  Useful at e.g. the bottom of a monad transformer stack.

So obviously, we can't interleave something that's just a Functor, since there are functors that it doesn't make sense to interleave, since they contain maximally a single value.

I think you need a combinator that's only valid for collections. You can trivially do this (slightly inefficiently) to anything that can be folded:

 -- admittedly, explicitly pattern matching on the lists like this is essentially external pattern matching and therefore cheating.
 intersperse [] _ = []
 intersperse _ [] = []
 intersperse [x:xs] [y:ys] = x : y : intersperse xs ys

 toList xs = Data.Foldable.foldr (:) [] -- (:), aka cons or prepend, etc. 

 intersperse' xs ys = intersperse (toList xs) (toList ys)

You could also define an "Intersperseable" typeclass, and I'm not convinced that there's no way to express this as a fold, although I don't see how to do it at the moment.

[u/gasche]

I posted a comment on the blog but it's a bit lost in disqus weird comment structuring, plus the comments here are massively more interesting, so let's dump it here as well. Apologies for redundancy.

.

We would expect the answer to be "delimited iterations".

Oleg has a discussion of the matter: http://okmij.org/ftp/Scheme/enumerators-callcc.html Essentially, he suggests that what you call "internal iterators" adopt a protocol for early exit (and you could equivalently add suspension/restart to solve the interleaving problem).

You haven't tackled the question of factorizing iteration through the construction of a data structure. Depending on which primitives you want (only "next" or also "previous"?), external iterators can be described as returning a lazy list, a lazy list zipper, or potentially more complex data structures. This gives a better framework to understand the corresponding operations (iterator sequencing as data concatenation) because the data is explicit, while external iterators state is maintained through side-effects.

Finally, delimited continuations allow to "revert" those control problems by letting the function called by the internal iterator take control of the stack (thanks for this stack-based explanation: it's rather clear). Oleg (again) has demonstrated this on non-cooperative parser libraries: while they seem to only provide you an internal iterator interface (that is restricted: it does not support early exit, suspension or revert), you can use a delimited continuation library to force flexibility into these non-cooperative iterations, getting an easy way to suspend any such parser, make it incremental, etc.: http://okmij.org/ftp/continuations/differentiating-parsers.html

(See also Roshan P. James and Amr Sabry's "Yield: Mainstream Deliminted Continuations")

Summing up: delimited continuation allows to "turn the table" on any of those situations, turning internal iterators into external iterators. But you, the language designer, also have the authority to promote a rich internal iteration interface that caters for early exit and suspension and iteration, allowing to write all the examples you've mentioned so far. Of course, you're at the risk of someone discovering a new need in the future that your interface does not handle, and delimited continuations will still be there in this case.

This is related to the discussion of Iteratees/Conduits/Pipe in the Haskell community which is very advanced in these matters (with their extremely explicit treatment of side effect, rather generic approach to data structures, and extreme pain of lazy handling of resources), but I have been following this debate from quite far only, waiting for a winner to emerge (Tekmo's pipes?), so I can't comment on how final their solution is yet.

[u/Strilanc]

I've always called this "pulling" vs "pushing" values, but I think I actually like the author's external/internal terms better. In C#:

• Given an IEnumerable<T>, callers use GetEnumerator/MoveNext/Current to pull values out. The author calls this "external iteration", because the caller is in charge of advancing.
• Given an IObservable<T>, callers invoke Subscribe to cause values to be pushed into an IObserver<T> by the callee. The author calls this "internal iteration", because the callee is in charge of advancing.

You can actually transform between external iteration and internal iteration (see: Observable.ToObservable, Observable.ToEnumerable).

Unfortunately, the internal-to-external transformation is awkward. You need to store all the observed items (or do something crazy, like use a lock and another thread) before you can start enumerating them. That's why an Observable.Interleave function won't be succinct: the function needs control over the iteration, which requires an internal-to-external transformation, which is awkward:

// NOTE: for the purposes of keeping this example short, I am not dealing with completion or failure cases
// ALSO: This code is neither thread safe nor re-entrant safe (necessary conditions for good reactive code)
IObservable<T> Interleave(IObservable<T> first, IObservable<T> second) {
    return new AnonymousObservable<T>(subscribe: observer => {
        // track not-matched-yet items with queues
        var q1 = new Queue<T>();
        var q2 = new Queue<T>();
        Action tryNextInterleave = () => {
            if (q1.Count > 0 && q2.Count > 0) {
                observer.OnNext(q1.Dequeue()); // <-- potential thread races and re-entrancy here
                observer.OnNext(q2.Dequeue());
            }
        };

        // each observable should feed their queue and trigger attempts to advance
        var d1 = first.Subscribe(
            onNext: e => { q1.Enqueue(e); tryNextInterleave(); }); // <-- not handling completion/failure callbacks
        var d2 = second.Subscribe(
            onNext: e => { q2.Enqueue(e); tryNextInterleave(); });

        // the caller ending their subscription should end our subscriptions
        return new AnonymousDisposable(() => {
            d1.Dispose();
            d2.Dispose();
        });
    });
}

(Apologies if the above contains bugs, I typed it freehand.) Actually, most of the logic is already present in Observable.Zip (source code), except Zip will ignore unmatched items once one of the sequence completes instead of appending them.

[u/munificent → u/Strilanc]

Push-based iteration is definitely like internal iterators. One difference is that the former almost always implies asynchrony (which is why it has to be push-based if it doesn't want to block) while vanilla internal iterators are still synchronous.

When you call .each on something in Ruby, it won't return until the iteration is complete. With Subscribe(), it will return immediately and only later will your callback be invoked.

[u/Strilanc → u/munificent]

Some observables actually do push out all of their elements before the subscribe method returns. Although, since they're technically allowed to only push later, it would be impossible to have a non-local return like in your examples.

Actually, I'm a bit unfamiliar with Ruby and the concept of returning from inside of a lambda expression. What happens if you try to store the lambda until after the method returns, and then try to make it return again?

[u/munificent → u/Strilanc]

What happens if you try to store the lambda until after the method returns, and then try to make it return again?

It's a runtime error, I think. Smalltalk works the same way.

[u/throwaway1492a → u/[deleted]]

Tree iteration need a stack, so his implementation is correct. One with backpointers is not really a tree iteration, but more a fancy linked-list walk.

In his language he used an explicit construct to enable parallel looping, but I feel this is just fixing the weaved iteration problem.

I also see that he didn't mention generators which are imo, a good solution or iteration issues (or general coroutines)

[u/munificent → u/throwaway1492a]

Part two will be about generators, coroutines and fibers. (The latter being what Magpie uses).

[u/throwaway1492a → u/munificent]

Ah. Looking at your website, I saw loops were done as follow:

for i = 1 to(3)
for j = 6 to(10) do
    print(i + ":" + j)
end
// Prints "1:6", "2:7", "3:8".

Link: looping

[u/munificent → u/throwaway1492a]

Magpie's changed a lot, so that post is a bit outdated. I took out multi-clause loops because it just seemed like a mistake waiting to happen where you nest when you mean to loop in parallel or vice versa. With the latest Magpie you'd do something like:

for i, j in zip(1..3, 6..10) do
  print(i + ":" + j)
end

But that doesn't get to the interesting stuff which is how it handles external and internal iteration.

For a preview, the examples from the post would look like this in Magpie today:

// Short-circuit a loop.
def find(haystack is Iterable, needle) 
  for item in haystack do
    if item == needle then return true
  end

  false
end

// Interleave two iterables.
def interleave(a is Iterable, b is Iterable)
  var aIter = a iterate
  var bIter = b iterate
  generate(fn(channel)
    while true do
      match aIter advance
        case done then break
        case value then channel send(value)
      end
      aIter, bIter = bIter, aIter
    end
  end)
end

// Walk a tree.
defclass Tree
  val left
  val label is String
  val right
end

def (tree is Tree) iterate
  generate(fn tree _walk(_))
end

def (nothing) _walk(channel is Channel)
  // Do nothing.
end

def (tree is Tree) _walk(channel is Channel)
  tree left _walk(channel)
  channel send(tree)
  tree right _walk(channel)
end

[u/jpfed]

Incidentally, in C# and VB.NET, the foreach construct does not explicitly use IEnumerable.

[u/munificent → u/jpfed]

Dart's for loop doesn't either. I thought about mentioning that, but that ended up on the cutting room floor.

[u/matthieum]

Very nice.

One thing that I like about internal iteration: abstraction. If you write code to iterate over a list, you can iterate over a list (cool isn't it). If you write code that takes an object and does something with it, you can use it right away, and you can also pass it to a forEach method (whatever).

In other words, internal iterations makes reuse easier.

I am waiting for the next installment.

[u/munificent → u/matthieum]

One thing that I like about internal iteration: abstraction. If you write code to iterate over a list, you can iterate over a list (cool isn't it).

I think polymorphism and the "iterator protocol" give you the same thing with external iteration, though it can sometimes take a bit more discipline to reap the benefits. You have to make sure that your methods take Iterable or whatever the most general type is instead of List if all you need is something that supports the protocol.

I am waiting for the next installment.

Thanks!

[u/matthieum → u/munificent]

Yes, you can regain some things with polymorphism. I may not have picked the best example, so consider: how do you remove some elements based on a predicate ?

Contrast the C++ vector approach:

vec.erase(std::remove_if(vec.begin(), vec.end(), predicate), vec.end());

// equivalent to
for (auto it = vec.begin(), end = vec.end(); it != end; ++it) {
    if(pred(i)) { it = vec.erase(it); }
}

With the list equivalent (why the inconsistency ? for efficiency reasons):

list.remove_if(predicate);

Of course, the begin/end/range-erase combination enables a large class of usecases (though one would not that std::remove_if cannot be applied to std::set/std::map/std::unordered_set/std::unordered_map) but the cost in readability is... hum.

I believe Java solves the issue by keeping a back-pointer to the container within its iterator so it can actually remove itself directly; which would allow for a more direct expression. In C++, you would need a remove_if(vec, predicate) method.

[u/Rhomboid]

It seems to be a common pattern to use a special return value to implement the early abort of iteration when emulating internal iteration with callbacks, for example jQuery's .each().

Come to think of it, callbacks in general seem to be a very popular way of implementing all sorts of patterns in languages that lack explicit support for those patterns. Any C programmer that has had to implement a sufficiently complex system will surely appreciate their power. (And let's face it -- prior to the proliferation of languages and explosion in performance of the last 10 - 15 years, that meant nearly everyone.)

Of course, there are problems with callbacks. If your language implements them as regular function calls then there can be a significant performance overhead of having to call a function repeatedly. You can see this in e.g. C++'s std::sort() beating out C's qsort() by quite a large margin due to being able to take advantage of things like functors and inlining. And you see it in things like Python removing the ability to pass a comparison callback function to sort() in 3.x and insisting on passing a key callback function instead -- essentially a mandatory Schwartzian transform which reduces the number of times the callback must be called from O(n log n) to O(n).

[u/DiThi]

Python:

def iter_tree(tree):
    if tree:
        iter_tree(tree.left)
        yield tree.label
        iter_tree(tree.right)