Lazy Iteration is being actively researched recently. There are two main strategies

Generators are widely implemented and their use cases are quite well understood. Mainstream languages just recently implemented lambda functions (Lisp had them since 1958!) which are required for iteration with callback. This article introduces Streams, which is the most basic way to do iteration with callback.

Lazy Iteration

An iterator is used to modularize your code. You first put all your values in a container. Then you have an iterator that iterates through the container, and finally a code that processes the values.

The goal of the lazy iteration is to merge the generation and iteration steps. This has several benefits:

  • No storage: values are generated, processed and then garbage collected.
  • Arbitrary number of values: Can represent asynchronous I/O.
  • Earlier Process: As soon as one value is generated, it can be processed. Better for user interactivity.

Generators

Lazy iteration is traditionally done with generators. A generator is a function that each time it is being called, returns the next value. Language makers allow to use yield to return multiple values. When you call the function again, it jumps back where it stopped.

function generator() {
  for (var x = 0; x < 10; ++x) {
    for (var y = 0; y < 10; ++y) {
      yield [x, y];
    }
  }
}
 
while (value in generator()) {
  // Do something with value
}

However, the implementation of generators is not trivial. There are several articles that explain how it works in C#: Behind the Scenes - Yield Keyword, What does Yield keyword generate.

To give you an idea of the complexity, this is a version of the same generator without yield.

var p = null;
function generator() {
  // First time
  if (p == null) {
    p = [0, 0];
    return p;
  }
 
  // Loop through the 2 dimensions (x, y)
  for (var dim = 2 - 1; dim >= 0; --dim) {
    p[dim] += 1;         // i++
    if (p[dim] == 10) {  // i < 10
      p[dim] = 0;        // i = 0
      continue;
    }
    return p;            // return [x, y]
  }
  // If we are here, we got through all the values.
}

Streams

All the functions of this article are available on this page. Just open-up your Javascript console and start using the streams :) (You can also embed streams.js).

Generators are not the only way to deal with to do lazy iteration. We can use continuations (or callbacks). We will call "Stream" a function that generates values, and will pass them to the continuation.

function stream(continuation) {
  for (var x = 0; x < 10; ++x) {
    for (var y = 0; y < 10; ++y) {
      continuation([x, y]); // We call the function that will process the value
    }
  }
}

As you can see, the code used to generate the values remains unchanged. Now we are going to use the stream: the most basic way to do that is to print the values.

stream(function (value) {
  console.log(value);
});
// [0, 0]
// [0, 1]
// [0, 2]
// ...
// [9, 9]

A stream is a function and we call it with another function. This is probably the first thing that will intrigue you. We just landed into the functional world! A stream is a high-order function. If you are not familiar with this concept, you can think a stream as a foreach function.

function print(stream) {
  stream(function (v) { // For each value of the stream
    console.log(v);     // Print it
  });
}

Rebuilding core functions

Now that we defined what a stream is, we want to see if we can express the basic functional operations that are map, filter and reduce.

function map(stream, f) {
  return function (continuation) { // We return a stream that
    stream(function (value) {      // For each value of the stream
      continuation(f(value));      // Continues with the application of f on the value
    });
  };
}
 
 
function filter(stream, f) {
  return function (continuation) { // We return a stream that
    stream(function (value) {      // For each value of the stream
      if (f(value)) {              // Tests if it matches the filter
        continuation(value);       // And continues it
      }
    });
  };
}
 
function reduce(stream, f, initial) {
  var ret = initial;               // Store the initial value
  stream(function (value) {        // For each value of the stream
    ret = f(value, ret);           // Reduce it with the current value
  });
  return ret;                      // and return the computed value
}

Example: Range

This was probably not clear how to use the object we just built. Let us take a simple example, we are going to play with the simplest thing we can generate: numbers from 0 to 10 :)

// The range function is a factory for a stream
function range(min, max) {
  return function (continuation) {
    for (var i = min; i < max; ++i) {
      // Once we have generated a value, we pass it to the continuation
      continuation(i);
    }
  };
  // The returned object is a function that takes a continuation
  // and calls it with the generated values,
  // therefore this is a stream
}
 
// We create a stream
stream = range(0, 10);
 
// A stream takes a continuation that will be executed on all the values it generates
print(stream);
// 0 1 2 3 4 5 6 7 8 9
 
// We can use the map, to change every value from v to 2 * v
stream = map(stream, function (v) { return 2 * v; });
print(stream);
// 0 2 4 6 8 10 12 14 16 18
 
// And filter only the multiples of 3
stream = filter(stream, function (v) { return v % 3 == 0; });
print(stream);
// 0 6 12 18
 
// In our case the number of generated values is finite
// We can therefore reduce them with the + operation
reduce(stream, function (a, b) { return a + b; }, 0);
// 36  (Note: This is a real value, not a stream)

Example: Message

A stream is a function that will call the continuation for all the values it generates. Therefore, any API that generates values with a callback can be used as a stream. As an example, we will use the window.postMessage API.

// We create the stream
events = function (continuation) {
  window.addEventListener("message", continuation);
}
 
// We only want events that are from a trusted origin
trusted_events = filter(events, function (e) { return e.origin == 'http://vjeux.com'; });
 
// We don't care about the event object, we just want the data
messages = map(trusted_events, function (e) { return e.data; });
 
// Now that we have the messages we wanted
// in the form we wanted, we can process them.
messages(function (m) {
  console.log('Message received!', m);
});

enumerate

We can easily reproduce the enumerate function of Python.

function enumerate(stream) {
  var i = 0;
  return map(stream, function (v) {
    return [i++, v];
  });
}
 
print(enumerate(range(5, 10)));
// [0, 5]
// [1, 6]
// [2, 7]
// [3, 8]
// [4, 9]

Stream Comprehension

It is quite painful to work with streams for basic operations (filtering and mapping). Languages like Python introduced a shorthand called List Comprehension. It is possible to do the same with streams.

function comprehension(f_map, stream, f_filter) {
  if (filter) {
    stream = filter(stream, f_filter);
  }
  return map(stream, f_map);
}
 
print(comprehension(#(v) { 2 * v }, range(0, 10), #(v) { v % 3 == 0 }));
// 0 6 12 18
 
// Python equivalent:
//   [2 * v for v in range(0, 10) if v % 3 == 0]

I make use of the Harmony # function proposal. It is still not really user-friendly. A modification of the language is probably required to make it enjoyable.

Recursive Stream

It took some time for C# to have recursive yield. Our stream proposal on the other hand works directly in a recursive fashion.

function traverse(tree) {
  return function (continuation) { // We return a stream that
    continuation(tree.value);      // Continues with the value
    for (var i = 0; i < tree.children.length; ++i) {
                                   // And traverse recursively on the children
      traverse(tree.children[i])(continuation);
    }
  };
}
 
var tree = {
  value: '1', children: [ {
    value: '1.1', children: [ {
      value: '1.1.1', children: [] } ] }, {
    value: '1.2', children: [] } ] };
 
print(traverse(tree));
// 1
// 1.1
// 1.1.1
// 1.2

List

Since we are building a stream using a functional approach, we want to build functional lists. We need two things, an empty list and a way to construct a new list by adding an element to an existing list.

function empty() {
  // An empty list is a stream that does not call the continuation
  return function (continuation) { };
}
 
function cons(head, tail) {
  return function (continuation) { // To construct a new list, we return a stream
    continuation(head);            // That first continues with the head
    tail(continuation);            // and continues the tail
  };
}
 
print(cons(1, cons(2, cons(3, empty()))));
// 1 2 3

I am not exactly sure how to write a head & tail function that returns two streams, one with the head and one with the tail.

zip

The zip function takes two streams and returns a single stream where each value is the combination of both streams.

function zip(stream_a, stream_b) {
  values_a = [];
  values_b = [];
  return function (continuation) {
    stream_a(function (v) {  // For each value of stream_a
      values_a.push(v);      // Store it
      if (values_b.length) { // If there is a value of stream_b awaiting
                             // Continue with both values
        continuation([values_a.shift(), values_b.shift()]);
      }
    });
 
    // Same for stream_b
    stream_b(function (v) {
      values_b.push(v);
      if (values_a.length) {
        continuation([values_a.shift(), values_b.shift()]);
      }
    });
  }
}
 
print(zip(range(0, 10), range(5, 10)));
// [0, 5]
// [1, 6]
// [2, 7]
// [3, 8]
// [4, 9]
// Note: All the values of the first range after 4 are being ignored
// because both streams do not have the same length.

Infinite zip

Here, the stream is generated by a for loop. Since the scheduler of Javascript is not pre-emptive, nothing can be executed while we are generating the values. Therefore we need to see all the values of one stream before we can return any value. It is problematic for infinite streams.

print(zip(range(1, Infinity), range(10, Infinity)));
// Freeze!

We are going to simulate a scheduler to solve this problem. We first need a generator. This is a function that will return the next value everytime it is being called. We can either use Firefox 2+ yield to build a generator or do it by hand.

We will construct a stream on top of this generator. The trick is to use window.setTimeout with a zero-delay between the generation of two values. Both streams will be able to generate values in parallel.

// With yield
function xrange(min, max) {
  for (var i = min; i < max; ++i) {
    yield i;
  }
}
 
// Without yield
function StopIteration() {}        // We first define the exception
function xrange(min, max) {
  var i = min;                     // We create the cursor
  return {                         // And return an object with a
    next: function () {            // next() that will be called to get the next value
      if (i == max) {              // If we reached the end,
        throw new StopIteration(); // We throw the StopIteration exception
      }                            // else
      return i++;                  // We return the value
    }
  };
}
 
// Then we make a function that converts a generator to a stream
function generator2stream(generator) {
  return function rec(continuation) { // We return a stream that
    try {
      continuation(generator.next()); // continues with the next value of the generator
      window.setTimeout(function () { // and gives the hand back.
        rec(continuation);            // It will provide the next value
      }, 0);                          // as soon as the scheduler calls it again.
 
    } catch (e) {
      // When the generator has finished, it throws a StopIteration exception
      // We want to ignore it.
      if (!(e instanceof StopIteration)) {
        throw e;
      }
    }
  };
}
 
a = generator2stream(xrange(1, Infinity));
b = generator2stream(xrange(10, Infinity));
print(zip(a, b));
// [1, 10]
// [2, 11]
// [3, 12]
// ...

But if the source of the stream releases the flow of execution between the generation of two values, this works well. This is the case of all async I/O. Let's take as example click and mousemove events. We want to synchronize the click and move events aka everytime both have happend, do something with them.

var click = function (continuation) { $('body').click(function (e) { continuation(e); }); };
var move = function (continuation) { $('body').click(function (e) { continuation(e); }); };
// The 2 lines before are best understood like this:
// var click = $('body').click;
// var move = $('body').mousemove;
// However it is not working because of the dynamic scoping of `this` :(
 
// Return only the type and enumerate for a better display
click = enumerate(map(click, function (e) { return e.type; }));
move = enumerate(map(move, function (e) { return e.type; }));
 
print(zip(click, move));
// move 0
// move 1
// click 0
// -> [click 0, move 0]
// click 1
// -> [click 1, move 1]
// click 2
// click 3
// move 2
// -> [click 2, move 2]

Conclusion

This article showed that Streams supports all the basic iteration techniques. Even better, the implementation of all them is straightforward. This looks all shiny, so why nobody uses it?

I think that it is because it relies heavily on functional programming. Lambda functions is a requirement and unfortunately they used to be only implemented on languages such as Lisp, Haskell, ML ... However, this trend is evolving. Languages with lambda such as Javascript, Python, Ruby are growing, and mainstream languages such as C# and C++ are getting lambdas. The next step is to educate people to functional programming.

If you want to know more about lazy iteration, here are some related links:

If you liked this article, you might be interested in my Twitter feed as well.
 
  • http://www.mrspeaker.net/ Mr Speaker

    Fantastic article. I was starting to write my own version of lazy streams - but they were getting pretty messy!

    I wish yield worked in webkit.

  • http://vjeux.com vjeux

    Thanks :)

    I did not think that anyone would be brave enough to read the article in its integrality :p

 

Related Posts

  • April 5, 2012 Climb – Property-based dispatch in functional languages (1)
    ELS Presentation | A Generic and Dynamic Approach to Image Processing | Chaining Operators & Component Trees | Property-based dispatch in functional languages This is the third (and last) presentation about my work on Climb at the LRDE. During the first one I tackled genericity on data s...
  • May 10, 2012 Generic Image Processing With Climb – 5th ELS (0)
    ELS Presentation | A Generic and Dynamic Approach to Image Processing | Chaining Operators & Component Trees | Property-based dispatch in functional languages Laurent Senta had the opportunity to go to the 5th European Lisp Symposium to present Climb, the project I've been working on dur...
  • August 29, 2011 Javascript: Improve Cache Performance: Reduce Lookups (2)
    In my Binary Decision Diagram Library, the performance bottleneck was the uniqueness cache. By reducing the number of cache lookup, it is possible to greatly improve the performances. Common pattern In order to test if the key is already in the cache, the usual pattern is to use key in cache....
  • October 5, 2011 Javascript Presentation (1)
    The talk is over. Check out the Slides & Video. For several months now I've been surveying my friends and teachers at EPITA and I came to the conclusion that they have absolutly no idea what Javascript really is. In order to help them discover a language that is getting a lot of traction n...
  • October 28, 2011 JSPP – Morph C++ Into Javascript (Paper) (0)
    6 months ago, I wrote the blog post "JSPP - Morph C++ into Javascript". My supervisor at the LRDE (R&D Lab of EPITA), Didier Verna, found it interesting and told me that it could be worth a publication. With his great help, I've written my first article. We have submitted it to two conferences (o...