[ /js/lazy ]

On Laziness

It's Thanksgiving here in Canada this weekend. Thanksgiving is the time when we Canadians celebrate Colonialism by stuffing our faces with factory farmed livestock in a potluck style gathering appropriated from the native tribes whose ancestral home we are occupying.

The Turkey dinner that is customary on this occasion has a way of making you want to hibernate. I thought I'd explore this theme of 'sloth', and present a related computational model:

Lazy Execution

First, what is laziness? The term itself can refer to a few things:

Laziness in programmers

According to Larry Wall, the original author of the Perl programming language, there are three great virtues of a programmer; Laziness, Impatience and Hubris

  1. Laziness: The quality that makes you go to great effort to reduce overall energy expenditure. It makes you write labor-saving programs that other people will find useful and document what you wrote so you don't have to answer so many questions about it.
  2. Impatience: The anger you feel when the computer is being lazy. This makes you write programs that don't just react to your needs, but actually anticipate them. Or at least pretend to.
  3. Hubris: The quality that makes you write (and maintain) programs that other people won't want to say bad things about.

source

This sense of the word has gotten quite a bit of attention over the years.

Laziness in computer science

The relevant wiki

Languages like Haskell, Prolog are lazy by design. It's a foreign feature to Javascript, but it can be implemented with fairly little effort.

Explicit implementation in a function

The basic idea is pretty simple:

  1. We have some procedure that might need to be executed which is potentially an expensive computation
  2. We would like to avoid computing it unless we have to
  3. We would like the results, once computed, to be cached for subsequent retrieval

In order to accomplish that, the components we require are:

  1. A persistent cache where the result can be stored and accessed
  2. The function we would like to execute
  3. A check as to whether the cache has been populated
var result; // our cache
var lazyRandom = function(){
  if(!result){ // our check
    // I threw in a console statement to show when this block was executed  
    console.log("Computing a random number between one and 100");
    result=Math.floor(Math.random()*100)+1;
  }
  return result;
};

console.log(lazyRandom()); // result is initialized
  // First function invocation
console.log(lazyRandom()); // cache is fetched
  // Second function invocation

Let's generalize a bit

What mistakes are there in the example?

  1. We're using the global namespace for our cache
  2. Our inner procedure is explicitly coded using a block syntax

We can address both issues by using a closure that captures the cache, and passing a function to be generalized instead of using a block.

One indispensible piece of information to take note of is that we will use an object for our cache, because an object is passed by reference, and not by value.

Here's an example of what I mean:

var cache={}; // don't mind the global cache..

var fill = function(c){
  // our argument 'c' is to be a reference to the cache
  // as such, it behaves differently than most code you will have seen.
  c.d = "pew";
};

fill(cache);
console.log(cache.d); // pew

As you can see, this behaviour doesn't just apply in a usual closure, you can pass references to objects in any scope, and have a function act on them. This can be an essential feature for functions invoked purely for the sake of their side effects.

Having shown that the behaviour will satisfy our requirements, let's use it to implement our lazy behaviour.

/* First let's make our function */ 

var rand100 = function(){
  return Math.floor(Math.random()*100)+1;
};

/* Nest a function, to create a closure */

var lazyRand = (function(f){
  var cache={};
  return function(){
    if(!cache.result)
      cache.result=f();
    return cache.result;
  };
})(rand100); // invoke the outer function

console.log(lazyRand());
console.log(lazyRand());

// this returns a function which checks the outer cache
// and conditionally executes the passed functon

Back to the issue of functions which rely on side effects, we have a bug! If there is no return value, then the function will be executed every time, because 'cache.result' will always be 'undefined'. We can work around that behaviour by using the logical OR operator.

/* A void function with side effects */

var show = function(){
  console.log("pew");
};

var lazyShow = (function(f,A){
  var cache={};
  return function(){
    if(!cache.result)
      cache.result=f()||true;
    return cache.result;
  };
})(show); // invoke the outer function

lazyShow(); // pew
lazyShow(); //

This is one way to ensure that even if a function is called many times, it will only ever be executed once.

Finally, let's come up with a version of our anonymous parent function that we can rely on to create a wide variety of lazy functions.

/* Create our lazifier */

var laz={};

laz.ify = function(f){
  var cache = {};
  cache.args = Array.prototype.slice.call(arguments);
  return function(){
    if(!cache.result)
      cache.result=f(cache)||true;
    return cache.result;
  };
};

/* Just side effects */

laz.show = laz.ify(function(){
  console.log("pew");
});

laz.show(); // pew
laz.show(); //

/* Caching a generated constant */

laz.constantF = laz.ify(function(){
  console.log("I only work when the boss is looking");
  return "pewpew";
});

console.log(laz.constantF()); // I only work... , pewpew
console.log(laz.constantF()); // pewpew

/* Passing arguments */

laz.useArgs = laz.ify(function(c){
  console.log("doing it right, the first time");
  return "The following arguments were passed :: "+ c.args.slice(1);
},2,3,5,7);


console.log(laz.useArgs()); // doing it right... , 2,3,5,7
console.log(laz.useArgs()); // 2,3,5,7

That's enough to give you an idea of what laziness is, but it's not incredibly useful for most people's purposes. If you wanted a constant, you'd just assign a constant, and be done with it.

How about some real world use cases?

Caching varied results

We don't necessarily just want to run some function once, then remember it's result. We want to be able to call it with many different arguments, returning the precomputed result whenever it exists.

You can think of this as 'episodic' caching. It can occur in any order, and the result will be stored for future use.

There is another related technique in which the cache should be treated as being sequential in nature. This is commonly referred to as Memoization.

The canonical example is a lazy fibonacci generator.

source

var fibonacci = function(){
  var memo = [0,1];
  var fib = function(n){
    var result = memo[n];
    if(typeof result !== "number"){
      console.log("computing result of fib(%s)",n);
      result = fib(n-1)+fib(n-2);
      memo[n] = result;
    }
    return result;
  };
  return fib;
}();

console.log(fibonacci(3));  // computing result of "3,2" , 2
console.log(fibonacci(5));  // computing result of "5,4" , 5
console.log(fibonacci(11)); // computing result of "11,10,...,6", 89

And I'll just make up a quick proof of concept example for the 'episodic' style.

var LOC = function(f){ // Lookup Or Create
  var cache = {};
  return function(x){
    if(!cache[x]){
      console.log("creating entry for %s",x);
      cache[x] = f(x);
    }
    return cache[x];
  };
};

var square = LOC(function(x){
  return x*x;
});

console.log(  [1,2,3,4,5,6].map(square) );
  // creating entries... 1,2,3,4,5,6
  // 1,4,9,16,25,36

console.log(  [1,2,3,4,5,6].map(square) );
  // 1,4,9,16,25,36

Having written all this, I'm starting to feel fairly lazy myself. I'll leave it to you, the reader, to generalize these last two functions. Though, I suppose if no one else does it, I might add to this post.

--ansuz

2014/10/13


Additional reading:

lazy.js