Oliver Steele

Have you ever written a function that looks like this?

function requestProductDetails(id, k) {
  var value = gProductDetailsCache[id];
  if (value)
    k(value)
  else
    ajax.get('/product/'+id, function(data) {
      gProductDetailsCache[id] = data;
      k(data);
    });
}

requestProductDetails calls its callback with the product details, which are stored in a cache. Since it might need to request this information from the server, it has to “return” it by passing it to a callback; in order to present a uniform API whether or not the product is cached, it “returns” the data this way whether it came from the cache or not.

requestProductDetails is intended to be used this way:

requestProductDetails(id, function(details) {
  infoPanel.setDetails(id, details);
});
infoPanel.setName(id, gProductNames[id]);

(I gave infoPanel a somewhat silly API in order to demonstrate a point. The general pattern is that there’s some computation in the callback, and some other computation after the call.)

There’s a subtle problem in this code, which is that two different code paths run through it. In the cached case, infoPanel.setDetails is called before infoPanel.setName. In the uncached case (the first time through), it’s the other way around. If there’s a bug that causes setDetails to work only after setName has been called, you may well miss it during casual testing, because it will only trigger the second time you trigger the code — and once it does trigger, it will appear intermittently (especially if you have a more sophisticated cache), and be darned difficult to find.

I recommend this implementation of requestProductDetails instead. It makes the inside of the function more complex — and the setTimeout looks gratuitous — but it makes its outside simpler : requestProductDetailss callers are much easier to debug.

function requestProductDetails(id, k) {
  var value = gProductDetailsCache[id];
  if (value)
    setTimeout(function() { k(value) }, 10);
  else
    ajax.get('/product/'+id, function(data) {
      gProductDetailsCache[id] = data;
      k(data);
    });
}

The general principle here is if a function sometimes has to call its callback asynchronously, always call it asynchronously, to minimize the number of possible code paths through the application.

Sometimes you need a totally opaque “constant” — a value that isn’t intended to be projected or modified, and whose only purpose is to be completely different from every other value¹. For example, Functional uses Functional._ as a placeholder; a comment on John Resig’s blog suggests defining something like Partial.PLACEHOLDER for something similar.

In JavaScript, these are easy to make. Here’s one: {}. And here’s another: {}. Note that these two values are different: the following code² will print true, then true, then false:

var L1 = {};
var L2 = {};
console.info(L1 == L1);
>>> true
console.info(L2 == L2);
>>> true
console.info(L1 == L2);
>>> false

The problem with these values is that they look the same when you print them. L1 and L2 both print as Object (in Firefox).

I’m going to print a value now:

console.info(isPrime(172942) ? L1 : L2);
>>> Object

Quick, which one did I print? Sure, you can figure it out in this case (assuming my implementation of isPrime isn’t buggy — probably not a safe bet, especially if you’re having to debug this in the first place), but in general this wreaks havoc with debugging.

Here’s an idiom for making opaque values that can be debugged. This has the further benefit that if the value is bound to a variable, you can use this to create a value that evaluates to itself when you type it back into the console (or into your source code). This works in Firebug and Rhino and OpenLaszlo, at least.

var L1 = {toString:function{return "L1"}};
var L2 = {toString:function{return "L2"}};
L1
>>> L1
L2
>>> L2

If you do use opaque constants often, you can use this makeLiteral utility routine to make them:

function makeLiteral(name) {return {toString:function(){return name}}}
var L1 = makeLiteral("L1");
var L2 = makeLiteral("L2");
L1
>>> L1
L2
>>> L2

Some real-world uses might be:

Functional._ = makeLiteral("Functional._");
Partial.PLACEHOLDER = makeLiteral("Partial.PLACEHOLDER");

In fact, you could go further and define a defining-form. I’m just including this for completeness; the version here doesn’t work unless target itself has a toString() method, and would need more work to be made robust.

function defineLiteral(target, name) {
  target[name] = return {toString:function(){return target+"."+name}}
}
defineLiteral(Functional, '_');

¹ Basically an enumerated type or a member of an algebraic data type, except that in meta-level programming these values are often compared to any other value, not just values of a specific type.

² This would work the same way with === instead of ==, but here it’s not necessary.

Don’t worry, this isn’t YAMT (Yet Another Monad Tutorial). This is a practical post about a code smell that afflicts everyday code, and about an idiom that eliminates that smell. It just so happens that this idiom corresponds to one of the uses for monads in Haskell, but that’s just theory behind the practice, and I’ve saved the theory for the end.

This post is about style: implementation choices at the level of the expression and the statement. Style doesn’t matter much in a small program, or a write-only program (one that nobody will read later). It isn’t necessary to make a program run: by definition, it doesn’t make a functional difference. Style makes a difference to how easy or pleasant a program is to read; this can make a difference to whether it gets worked on (by its author, or somebody else) later.

The Problem

The types are Product, Offering, Merchant, and Name. A Product might have an Offering; an Offering might have a Merchant; and a Merchant might have a Name.

The code displays the name of the merchant that is offering the selected product. The input is named product. This value might be an instance of Product, or it might be null. The specification is this: If product is a product that has an offering that has a merchant has a name, then display that name; else do nothing.

[This problem is adapted from an eCommerce application I'm writing.]

This code isn’t difficult to write. The challenge isn’t in make it run; it’s in making it readable.

The Obvious Implementation

Here’s a naive solution. This particular code is JavaScript, but the structure comes out the same in Python, or Ruby, or C++ or Java, or Lisp.

var product = ...;
if (product) {
  var offering = product.offering;
  if (offering) {
    var merchant = offering.merchant;
    if (merchant) {
      var merchantName = merchant.name;
      if (merchantName)
        displayMerchantName(merchantName);
    }
  }
}

Let’s stop for a moment and identify the smells. There are two of them: I call the first one Narrative Mismatch, and the second Baton Carriers.

The first smell has to do with those nested conditionals. There’s a narrative here, that flows from the beginning of the spec (”the input is named product“) to the end (”display that name”). The code that corresponds to this narrative starts with product=..., and ends displayMerchantName(...). However, the line of this narrative isn’t linear in this implementation; it’s a series of Russian dolls. The climax to the story is buried in a subplot, displayed as though it were some exceptional case. Narrative Mismatch is when the dramatic structure (the specification) of the program doesn’t match its control structure (in the implementation).

The other problem is the temporary variables. These are the variables such as offering and merchant. These variables are “bit players”: each variable enters the stage (the local scope) only to perform a trivial bit of business, and then hangs around as clutter. Or, to use a racing metaphor, this implementation turns what could be a sprint into a relay race, where a series of runners hands off the data baton.

Can we do better?

If the code did nothing but display the merchant name and then return, we could invert each of the conditionals, and bail out early. This changes the control structure to match the plot: the beginning and end of the narrative are both at the same (top) level of the control structure.

var product = ...;
if (!product) return;
var offering = product.offering;
if (!offering) return;
var merchant = offering.merchant;
if (!merchant) return;
var merchantName = merchant.name;
if (!merchantName) return;
displayMerchantName(merchantName);

This implementation retains two of the disadvantages from the first, and it introduces a third. First, that’s still an awful lot of control flow (four lines) obfuscating a tiny amount of data flow (four lines). Second, we’ve still got those baton variables, offering, merchant, etc. Finally, the new implementation works only if the fragment is an entire function: if displayMerchantName is the last statement in the function¹.

How about if we eliminate the batons altogether? Then we can combine all the tests into a single conditional:

var product = ...;
if (product
    && product.offering
    && product.offering.merchant
    && product.offering.merchant.name)
  displayMerchantName(product.offering.merchant.name);

This implementation has fewer lines, at least, but there’s still a lot of repetition² — the text product.offering occurs four times.

It’s also inefficient. The previous implementations computed the value of product.offering only once, but this one computes it four times, and contains a total of nine member accesses to the alternatives’ three. These multiple accesses may not matter for this particular example: the case where all nine of those accesses are executed is the same case that ends with a a function call to a display routine. But consider the case where the accessor is product.offering() instead; or, in Ruby or ECMAScript 4, the case where product.offering is a getter.

We can re-introduce the temporary variables, this time within the conditional, to keep the control flow simple:

var product = ...,
    offering, merchant, merchantName;
if (product
    && (offering = product.offering)
    && (merchant = offering.merchant)
    && (merchantName = merchant.name))
  displayMerchantName(merchantName);

…but now we’ve brought back the batons.

(You may also have a stylistic object to the assignments inside of conditionals in this latest attempt. I’m not completely against the construct, but I avoid it unless it makes the code clearer, and it’s not clear that it does that, here.)

Stepping Back

I’d like to be able to write something that matches the language of the specification:

var product = ...,
    merchantName = product.offering.merchant.merchantName;
if (merchantName)
  displayMerchantName(merchantName);

and have the system just know that product.offering evaluates to null if product is null; and that product.offering.merchant evaluates to null if product.offering is null, etc. Now, we might not like null.property to evaluate to null everywhere (that might move bug symptoms too far away from their defect sites), but we’d like it here.

This property — that member access to a property of null is itself null — could be called “null contagion”. Many languages have “float contagion”, where an arithmetic operation produces a float if either of its arguments is a float. (i.e. a+b is equivalent to float(a)+float(b) if either of a or b is a float.) “Null contagion” is similar to float contagion except that it only applies to the member access (.) operator, and only from left to right.

You may be used to null contagion from other contexts — for example, from the declarative languages such as CSS and XPath and SQL, that adjoin the mainstream languages. It’s just not present in any of the procedural languages that I listed at the top of this post. For example, if product were XML and we were using E4X, we could write this as product.offering.merchant.name as desired. Or if we could apply CSS to a JavaScript object, we might write something like $('offering > merchant > name', product). Or with XPath (and an Hpricot-like syntax, this time): product/'offering/merchant/name/text()'.

So one solution would be to write a function that applies CSS or XPath paths to JavaScript objects. This works and there’s even Java libraries that do this, but here I’m looking for something less heavyweight than a library, and something that doesn’t require parsing strings at runtime. I’m looking for an idiom that approximates null contagion within the language.

Without further ado, here’s how to write an expression that evaluates to object’s property property if object is not null, and to null otherwise³:

(object||{}).property

And this can be chained as follows:

((object||{}).property1||{}).property2

So let’s apply this, in two steps, to the problem above. First, get rid of all the intermediate conditionals, in order to match the control flow to the narrative:

var product = ...,
    offering = (product||{}).offering,
    merchant = (offering||{}).merchant,
    merchantName = (merchant||{}).name;
if (merchantName)
  displayMerchantName(merchantName);

And now that each intermediate variable is used only once, we can inline its value and eliminate its name:

var product = ...,
    merchantName = (((product||{}).offering||{}).merchant||{}).name;
if (merchantName)
  displayMerchantName(merchantName);

This isn’t as clean as the E4X example, but it’s relatively concise: no batons, and no non-narrative control flow.

It’s also, in the case where most products have offerings that have merchants that have names, potentially more performant. A || (which short circuits) is comparable to an if statement, and the number of conditionals of either form (|| or if) is conserved across all the implementations in this post. The “null contagion” version defines {} literals, but these are only interpreted to create objects when the property target is null — here, assumed to be the exceptional case. And since this attempt has fewer instances of variable name lookup than in the others, it should be more efficient than the others except when in the presence of more optimization that most of the scripting languages provide right now.

What about the case where most products don’t have offerings, or the offerings don’t have merchants, vel cetera? If this were a frequent case, and this were inner-loop code, I might introduce a global empty object in order to reduce the object instantiation overhead (which happens right away) and the GC load (which shows up over time). E.g. define var $N={}, and use:

var product = ...,
    merchantName = (((product||$N).offering||$N).merchant||$N).name;
if (merchantName)
  displayMerchantName(merchantName);

(The Ruby equivalent of {} is {} for a Hash, with array-style access; and OpenStruct.new for an Object, with property getter syntax. You definitely want a reusable singleton for the latter.)

On the minus side, even this version always performs all four tests and all three property accesses. That’s three extra tests (beyond the attempts at the top of this post) when product is null, and two extra when product.offering is null, and so on. So it might still slower be than the solutions that don’t use null contagion — but on the other hand, it still avoids the temporary variables of those solutions. In other words, there’s no substitute for actually measuring the difference, within the program and on each platform that you’re optimizing for. Oh well.

What Does this Have to Do With Monads?

An expression such as product.offering.merchant.name is a pipe. It can be read as “get the value of product; and then get that value’s offering; and then get that value’s merchant; and then get that value’s name“. The dot says two things: (1) evaluate the expression (product) to its left, and then (2) use that as target for the projection function (['offering']) immediately to its right.

We’ve made up a new construct, (object||{}).property, which is like object.property except that if you put a null in (as the value of object), you get null out (as the value of (object||{}).property). In effect, we’ve replaced dot’s interpretation of “and then”. The interpretation of object.property’s “and then” includes “and if object is null, then error”. The interpretation of the new “and then” adds “and if object is null, evaluate to null”.

This construct, (object||{}).property, isn’t a monad. It isn’t a monad because it isn’t associative; and it isn’t associative because the property accessor (dot) isn’t either [dot isn't the morphism of a category]. (A.b).c isn’t the same as A.(b.c) — in fact, the latter isn’t even well formed.

However, the class of property projection functions — just the .b part — does form a category. If you consider just the .b.c.d part of A.b.c.d, it doesn’t make any difference whether you read it as “apply the ‘b’ projection, and then apply the application of the ‘d’ projection to the ‘c’ projection, to that”; or “apply the ‘c’ projection to the ‘b’ projection, and then apply the ‘d’ projection to that”.

You won’t find “null contagion” proposed as an implementation technique on the web. What you’ll find is the Maybe Monad.

¹ It would be sad if this were an entire function. That would indicate that the function that contains displayMerchantName is just a wrapper for displayMerchantName, to protect it from being called when there isn’t a Product with an Offering with a Merchant. Having to define a new function to wrap each instance of a common pattern is like having to define a new word to name the reference of each noun phrase. It’s reminiscent of the boilerplate getters and setters in logorrheic enterprise code.

² “Repetition” is defined as “a host site for a defect infection”.

³ JavaScript has more than one null object. This code takes advantage of the fact that an Object (even one with no properties) is never null, while undefined — the value of an undefined property access — is null.

Computing the length of a Bezier curve is expensive, but the length of a given Bezier doesn’t change over time. In my JavaScript Bezier implementation, I wanted to compute the length only the first time it’s need, and save this result in order to return instantly thereafter.

This is a special case of memoization. There are well-known strategies for implementing memoization. But getLength is a nullary function, and there’s a trick for implementing memoization of nullary methods in a dynamic language such as JavaScript (or Python or Ruby). In these languages, you can memoize a nullary method by adding one line to it, without any support libraries. This line replaces the method by a constant function, that returns the computed value. This memoization strategy is also more efficient than the general-purpose solution that non-nullary methods require.

Memoizing by Hand

The naive way to implement memoization is to store the value in a property the first time it’s computed, and test for the presence of the property thereafter:

Bezier.prototype.getLength = function() {
  var length = this._length;
  if (length === undefined) {
    var length = ... // expensive computation
    this._length = length;
  }
  return length;
}

or:

Bezier.prototype.getLength = function() {
  if ('_length' in this) return this._length;
  var length = ... // expensive computation
  this._length = length;
  return length;
}

There are some problems with these solutions. First, they’re verbose. Worse, the domain logic (the line labelled “expensive computation”) and the memoization logic (the code that accesses length and this._length) are tangled up with each other.

These implementations also require a private property for each memoized method. And then there’s a (minor) performance hit too: it takes a few instructions, each time, just to discover that the return value has already been computed.

The Big Gun

The standard solution to the first two of the problems above (the length and structure of the implementation) is to write a higher-order-function, that creates a memoizing function from a non-memoizing one.

Function.prototype.memoize = function () {
  var fn = this;
  var cacheName = ... // create a unique property name
  return function() {
    var key = serialize(arguments);
    var cache = this[cacheName] || this[cacheName] = {};
    return key in cache ? cache[key] :
      cache[key] = fn.apply(this, arguments);
  }
}

(Keith Gaughan has a complete implementation here.) Then you can use it thus:

Bezier.prototype.getLength = function() {
  var length = ... // expensive compuation
  return length;
}.memoize();

This is the best general-purpose solution, and it’s good for a framework, or for a complete application. But in a small standalone code library such as this or this, I don’t want to include a copy of Function.prototype.memoize in each standalone file (and then worry about version skew); and I don’t want to make each file depend on a utility file (and then worry about file dependencies).

The One-Liner

A nullary function such as getLength is a special case of functions in general, and there’s a particular technique¹ for memoizing it, that fits on a single line.

Here’s the first variant.  This is less source code that the version above, and uses fewer instructions to retrieve a memoized value. (In fact, it uses the fewest possible number of instructions, if the API for retrieving a value requires a function call at all.) It’s an extra line (the assignment to this.getLength) that you can stick in a nullary method, that memoizes the method’s value on a per-instance basis.

Bezier.prototype.getLength = function() {
  var length = ... // expensive computation
  this.getLength = function(){return length};
  return length;
}

The second variant moves the return and the assignment to the same line. Think of this line as a “memoizing return statement”. It comes at the cost of more opaque code, and an extra function call. (The overhead of a function call is probably not a problem if the computation is expensive enough to be worth memoizing anyway.) And although it’s not a style I would use for general-purpose programming, I find it acceptable in an idiom².

Bezier.prototype.getLength = function() {
  var length = ... // expensive computation
  return (this.getLength = function(){return length})();
}

Another Use

You can use a similar technique to prevent a function from being called twice.  This is even simpler, since you don’t need to keep track of the value.  For example (from gradients.js):

OSGradients.initialize = {
  OSGradients.initialize = function() {};
  ... // initialization
}

Avoiding Memory Leaks

The inner function captures the variables from the outer function. In the method below, temp will never be deallocated, until the instance that getLength has been applied to (and that the constant version of getLength is therefore now attached to) has been deallocated.

Bezier.prototype.getLength = function() {
  var temp = new Array(10000);
  var length = ... // expensive computation
  // the following line captures length and temp:
  return (this.getLength = function(){return length})();
}

If there are large temporaries, or pointers to DOM elements that may be deleted later, you should either detach them before you exit the outer function body:

Bezier.prototype.getLength = function() {
  var temp = new Array(10000);
  var length = ... // expensive computation
  temp = null; // so the value won't be captured
  // the following line captures length and work:
  return (this.getLength = function(){return length})();
}

or use a helper function that closes over just the return value:

// Function.K(value) is a constant-valued function that returns
// value.
Function.K = function(value) {return function(){return value}};
Bezier.prototype.getLength = function() {
  var temp = ...
  var length = ...
  // the following line only captures length:
  return (this.getLength = Function.K(length))();
}

Thunks for the Memories

Although I didn’t realize it until later (when I was writing my Bezier library, coming at this more from the “how can I cache this value” perspective than from a “theory of memoization and programming language implementation” perspective), this is nothing more than an implementation of thunks for JavaScript.

In a lazy (or call-by-need) language such as Haskell, memoization comes for free. A variable with an initializer has the same syntax and semantics as a function; the initializer is evaluated once, the first time the variable is referenced, and then cached.

A referentially transparent nullary function has the syntax of a function, but the semantics of a value. (In Haskell, the syntax is the same too.) By memoizing it, we’re making this value call-by-need. One technique for implementing call-by-need (or “lazy”) values is to create a thunk that replaces its computation by its value the first time it’s evaluated. In JavaScript, we can implement these semantics but have to stick with the function-call syntax.

Beyond Thunks

There’s three directions to go from here, but all of them involve giving up the single-line solution.

First, it’s a bother that a method has to know its own name. This means you can’t paste the same line of code into each memoized function. This is the only way, however, that the method can replace itself with the constant function³. You can eliminate the need to type the name twice, if give up both the no-helpers requirement and the optimization that a memoized function doesn’t test any conditions the second time it is called. (The higher-order function in the section “The Big Gun” does this.)

Second, you can memoize non-nullary functions by getting out the big gun too. In this case the replace-yourself optimization is useless too, since each invocation needs to check whether the value has already been computed for these arguments, regardless of how many times the function has been invoked before.

A third extension lets you hang onto the optimization, but takes more than a line of code (and therefore, realistically, depends on a support function). It’s for the case where the return value depends upon the object state, and that state is mutable. In this case, you need a way to reset the memoized function to its initial state, so that it will perform the computation the next time it’s called. For example, setRadians below resets getDegrees so that the multiplication happens again upon the first call getDegrees after each time setRadians is called. (This example isn’t a realistic candidate for memoization, but pretend multiplication is really really really slow.)

function Angle(radians) {this.setRadians(radians)}
Angle.prototype.setRadians = function(radians) {
  this.radians = radians;
  this.getDegrees.reset();
};
Angle.prototype.getDegrees = function() {
  return this.radians * 180 / Math.PI;
}
memoizeConstantMethod(Angle.prototype, 'getDegrees');

Here’s a long but marginally readable implementation of memoizeConstantMethod:

function memoizeConstantMethod(object, property) {
  var f = object[property];
  var mf = function() {
    var value = f.call(this);
    var kf = function(){return value};
    kf.reset = reset;
    object[property] = kf;
    return value;
  }
  var reset = function() {
    object[property] = mf;
  }
  mf.reset = reset;
  reset();
}

And here’s a shorter version, that sacrifices the remaining readability for source code size⁴.

function memoizeConstantMethod(o, p) {
  var f = o[p], mf, value;
  var s = function(v) {return o[p]=v||mf};
  ((mf = function() {
    (s(function(){return value})).reset = mf.reset;
    return value = f.call(this);
  }).reset = s)();
}

Update: Peter Michaux has a nicely written description of a similar technique here.

¹ Memoization in general requires a finite map (or “hash”) from argument lists to result values. In the special case where the function is nullary, you don’t need a map, because the empty list is the only key.

² Just as I don’t need to understand what the tabs are in an English idiom such as “keep tabs on”, I don’t need to easily read a programming language idiom compositionally each time I see it.

³ You can’t search the object and its prototype chain for a function that’s === to the one being replaced, because the same function might be present at different property names.

⁴ This is written in might be called the “_why combinator” style of programming.

Today my office is an airplane. I’m visiting the home office in San Francisco for the week. I get to remind everyone that those of us in the Boston office are real people (insert your favorite joke here), and come back with enough to understand what’s behind the email and phone conferences for another month.

One of the geek games you can play on an airplane is stretching out the battery life of your computer. I have enough batteries to last me through a six-hour flight now, but old habits die hard.

Since I save my files every minute or two, spinning down the hard disk isn’t an option. (I tend to use programs that communicate use the file system to communicate. And I don’t want to be in a position to lose more than a few minutes of work anyway.) I don’t usually use a CD or DVD player, so I’m already optimizing there. The CPU that I’m using steps down to 800MHz when the plug is out, so that’s taken care of for me. That leaves screen brightness.

The problem with turning down the screen brightness is that this also turns down my reading speed. I’ve noticed that I read a lot faster when I’m reading higher-contrast text. Since I already use black text on a white background, the contrast is proportional to the screen brightness (as long as the overhead light is off).

This effect matters most when I’m reading English. When I’m reading math or code, or writing anything, my word recognition time, which is the part of the pipeline modulated by the contrast, isn’t the bottleneck anyway — in those cases I’m limited by comprehension time, or by other central abilities. So I used to turn the brightness up when I’m reading, and turn it down the rest of the time.

Let’s call this the contrast modulation strategy. It trades off reading speed against battery life, based on the current activity (reading versus other work). The contrast modulation strategy works if I’m spending long stretches of time reading, or not-reading. It’s a pain if I’m going back and forth — referring to one document while I’m writing another, for instance.

Here’s today’s discovery: my reading speed is also proportional to the text size. I just ran a few informal comparisons, and setting my document zoom to 200% at the lowest brightness works just as well as turning the brightness all the way up. (With a large font, it doesn’t seem to matter how bright the screen is, at least within the range that my screen adjusts to.)

With larger text (a larger font size, or a greater zoom), I have to scroll more, but when I’m reading English I don’t need to see more than a few paragraphs for continuity anyway. When I’m reading code I want to see as many lines as possible (this one reason I prefer concise programming languages, so I can see several different levels of structure without having commit as much to my mental buffers so that I can scroll) and technical documents always seem to refer to tables and figures a page away, which makes for a lot of scrolling, anyway. So I want big fonts for English that I’m reading, and small fonts for everything else. But font size, unlike screen brightness, is something you can associate with a specific document.

Let’s call this the text size modulation strategy. The text size modulation strategy trades reading speed off against the amount of the document that’s simultaneously visible. The text size modulation strategy takes decouples the trade-off between reading speed and battery life and, unlike the contrast modulation strategy, it’s automatic once you zoom your documents, no matter how many times you switch between them.