Oliver Steele

Here are some of the weekend projects that I didn’t finish this year. These aren’t good enough to put on my project list or my sources page. Some of these aren’t even working, and some of them I might not finish at all (most of my weekends are spoken for). And some of them I can’t bear to look at (I’m not proud of the code, and don’t want to be judged by it…), but I’m making myself put them out there anyway. I feel bad for the neglected little things, trapped on my hard drive, and I’d like to let them see the sun, even if just briefly before they flicker out and die.

Libraries:
* LzOSUtils — jQuery-compatible ajax function, Flash->JS bridge with callbacks, declarative Flash 8 filter effects, console that reports to Firebug, dashed lines, Prototype-compatible string and collection methods, etc. Completely undocumented and fairly disorganized.
* LzTestKit — mocks and asynchronous and automated testing for OpenLaszlo; still pretty raw.
* HopKit — a “higher order programming kit”, for constructed chained APIs such as in LzTestKit’s mocks and expectations; still somewhat buggy and undocumented.
* MVars — a port of Haskell MVar’s to JavaScript. I realized that what I actually needed for real-world applications was an implementation of the join calculus (a la JoCaml). I haven’t written the join calculus version.
* Protodoc — I wrote this to extract the docs from the source files and to implement the live examples in Functional and Sequentially; it includes a version of the wonderful doctest, for JavaScript. I got part way through refactoring it into something that isn’t quite put together again. I haven’t decided whether to finish it or whether there’s an existing project that’s close enough.
* [No link yet] Updates to OpenLaszlo JSON and ropenlaszlo, from using them over the past year. (No, those links go to the old versions — I haven’t uploaded the updates
* Implementations in Ruby and JavaScript of the awesome CFDG. I wrote these a couple of years ago, and really want to update and clean them up to point where I can donate them to Hackety Hack, or someone else who might use them.

Applets:
* Tiles — HTML port of my mid-nineties Java version (which was a port of my mid-eighties C version), uses the Canvas tag; probably doesn’t work in MSIE
* IFS — a few minutes of pair programming with my son to show him some stuff about matrices; probably doesn’t work in MSIE
* On this day — iPhone applet; the feed is down right now
* Force-directed layout for my home page — this was my experiment using HTML instead of Flash; I got discouraged when I saw how bad the frame rate for full-page animation is was even in Firefox, let alone MSIE (Safari rocks now, though!)

Plus a couple dozen essays that are half or three-quarters written (programming, software development, math education), a couple of AJAX presentations, and two workbooks for teaching abstract math at the elementary level. It takes me longer to write an essay than a program, though!

More weekends, please.

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.

amichail on reddit asks about understanding monads in one minute. My thoughts ran longer than a comment and more than a minute, so I’ve placed them here.

The main message of this posting is that you already use monads, just without the labels. The complexity in most explanations comes from factoring out the different pieces of what you already know, and from the mathematical exposition in terms of category theory and monad laws. (I like the math, but you won’t find any of it here.) This posting trades away accuracy for ease; I hope it’s a helpful start.

A monad, as used in Haskell, is a rule that defines how to get from one statement in a program to the next. For example, there’s an implicit monad in the (JavaScript) sequence var x = 1; var y = x+1. It describes how to get from var x = 1 to var y = x+1.

A monad describes the flow of control, and the flow of data. Typically, the flow of control is something like “execute the first statement once, and then execute the next statement once”, and the flow of data is something like “the first statement computes a value, and makes it available to the next statement” (through a variable binding, say).

Sometimes the rules are more complicated. For example, if one statement is throw or raise, the statements that follow it are skipped. If one statement sets a global variable, the statements that follow it can get additional data by reading that variable. And if one statement changes the world outside the program (say, that statement creates a file), this will affect what happens when the following statements peek at the world, maybe even in other ways (say, by reading the free space on that volume).

Also, “following statements” is a dynamic notion, not a static one. If function f calls g, then all the statements in f that follow f’s call to g, follow all the statements in g (at least, up until g’s return).

You’ve used monads. You’ve used the State monad (which manages global variables), the Error monad (which enables exceptions), and the IO monad (which handles interactions with the file system, and other resources outside the program). You may not have thought much about these properties, because they come “for free”: in most languages, you don’t need to do anything special to get them.

In Haskell, you do need to do something special. All you get by default is the “typical” case from above: one statement computes a value; the next statement can read it. If you want additional behavior (State, or Error, or IO), you have to say so. You can say so by declaring the type of your statement block. Just like every variable in a statically-typed language such as C or Java has a compile-time type (int if its values are integers, or String if its values are strings), every statement in Haskell has a compile-time type too: Error Int if it might raise an exception; IO Int it it might interact with the world.

Why introduce this complexity into statement sequencing? The complexity comes with two benefits: a check on dynamism, and the ability to extend it.

The first benefit is that, if the only statements that might change the world have IO in their type, you can assert to the compiler that some compound statement or function not only doesn’t change the world within its body, but doesn’t call any functions that contain statements that do. And so on for other properties (“raises an exception”, “accesses global data”). This turns out to be useful.

The other benefit is that you can define your own sequencing rule. Remember that part about “execute the first statement once, and then execute the next statement”, and “the first statement computes a value, which the next statement can use”? You can replace these with “execute the first statement, but only execute the next statement if the value so far isn’t null”. This is the Maybe monad; it turns out to be useful too.

Or, you could replace the rule with “the first statement computes a list of values, and the second statement runs once using each of them“. This is the List monad; it’s — yes, you’re ahead of me here — it’s useful too.

I made an analogy between statements and variables, above. Java and C++ have typed variables, while Haskell adds typed statements. Let’s extend that analogy. Operators, such as plus and times, combine values. Some languages let you overload operators: Integer+Integer does one thing; you can define String+String to do another (hopefully string concatenation), and Vector+Vector to do a third (hopefully vector addition).

You can think of the semicolon as an operator that combines two statements. A definition for the semicolon operator is a monad: it defines the meaning of a compound statement composed of two simpler ones. Haskell lets you overload semicolon.

I hope this helps. If it did, now go read a monad tutorial and see how it works for real. If didn’t, go read a monad tutorial to see if it’s easier with actual examples, and the details and syntax filled in.

Some Lies

Here’s some of what I said above, that just isn’t true:

A monad isn’t just a rule. It’s a structure that includes a rule. Its data are a set (or type) of statements, and an operation that combines them — the “rule” above. (There’s more accurate and technical definitions, but that gets into the heavy math.)

Furthermore, the rule part of the monad isn’t just any rule. It has to have certain properties: the monad laws. However, you can perfectly well understand how to use a monad without being able to enumerate the monad laws¹, just like you can use numbers without being able to enumerate the properties of a field or ring.

The descriptions of the State and IO monads above are particularly oversimplified. I think they’re useful for coming from procedural programming, but you’ll want to refine them in order to get to functional programming. Again, follow any monad tutorial.

In Haskell, you don’t even get statements by default. (I said above that you did.) Everything is an expression. As soon as you start using statements (which are just monad-valued expressions), you’re in monad land (even if it’s just the identity monad). The step from expressions to statements is the big one, and the differences between different monads aren’t as big a (syntactic) deal.

In Java, you do have to declare the types of some collections of statements. The collections are functions, and the type that you have to declare is the type of a statement that throws a checked exception. This fact about Java is widely despised, but it does give you a taste of Haskell.

Finally, thinking about monads as defining (or overloading) semicolon is a start, but sequencing is more general than that. Even in a language where every two lexical statements are separated by a semicolon, one statement can dynamically follow another without any particular relation between their sources, such as when one is in a function, that is called by the other.

¹ The monad laws just say that (1) there’s a way to turn any expression (that computes a value) into a monad (that passes that value on); and (2) a sequence of statements acts the way you think it should.