Streams in JavaScript

Time is but the stream I go a-fishing in.

-Henry David Thoreau

Recently I was rereading Structure and Interpretation of Computer Programs by Abelson and Sussman and was hooked by the section on streams. Streams allow one to reason about stateful phenomena while mitigating "some of the complexities of modeling state".

A stream is a data structure representing the history of values for a system across time. Imagine physics' world line concept applied to any system or phenomena. If one thinks about the life of an apple over time it ages. But if one considers the entire history of the apple through time that function is constant with respect to time. I decided it would be fun to implement this concept in JavaScript.

Implementation

To easily model a stream implement it as a delayed list. This means the head of the list will be the current value and the tail will be a promise to evaluate the next element in the stream. In SICP the authors use the delay method to convert a tail into a promise and then use the force method to evaluate the promise.

function Stream(head, tail) {  
    this.headValue = head;
    this.tailValue = this.delay(tail);
}

Stream.prototype = {  
  delay: function(tail) {
    return tail();
  },
  force: function(delayedTail){
    return delayedTail();
  }
}

Application

Because streams are sequences we can still use sequence methods like enumerating, filtering, accumulating, and mapping but because streams delay evaluation we can perform these manipulations on sequences that are large or infinite in size.

For example I can take a stream representing all integers beginning with the number 2 and run it through the Sieve of Eratosthenes to generate a stream of the prime numbers.

Stream.integersStartingFrom = function(num) {  
  return new Stream(num, function(){
    return integersStartingFrom(num += 1);
  });
};
Stream.prototype.sieve = function() {  
    var self = this;
    return new Stream(self.head(), function() {
      return self.tail().filter(function(num) {
        return !willDivide(self.head(), num);
        }).sieve();
    });
  }

var primes = Stream.integersStartingFrom(2).sieve();  
console.log(primes.item(50)); // 233  

Streams allow the developer to cleanly separate and intuitively reason about these types of tasks across data collections.

Improvements

One early improvement to make in a streams library is to memoize the delay method that generates the promise. Rather than reevaluating the tail everytime use a closure to store whether the tail has been evaluated in the past and if so return that result.

Stream.prototype = {

 delay: function(tail) {
    return this._memoTail(tail);
  },

  _memoTail: function(tail){
    var hasRun = false;
    var result;
    return function(){
      if(!hasRun) {
        result = tail();
        hasRun = true;
        return result;
      } else {
        return result;
      }
    };
  }
}

Practical use cases

Infinite streams of data can be found in many fields from physics, finance, and engineering. In physics as mentioned the world line is the concept of reasoning about an elements' entire history through spacetime. In finance there are many financial assets that exhibit stream like behavior such as perpetuities and stock market data. In engineering they can be found in the fourier series which has application in electrical engineering, optics, acoustics, and more.

Next steps

I would like to explore using the stream data structure to model some of the practical applications listed above namely the modeling of financial streams and fourier series.

The code

The full code used can be found on my github in the streams repository. I would also like to mention the streams.js library by dionyziz which helped jump start my implementation of streams in JavaScript.

Show Comments