Oliver Steele

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.

I first heard of Ruby at the second Lightweight Languages Workshop 2, where Matz and I were both speakers. This was first public disclosure of the then-proprietary Laszlo platform language. I’m afraid I was more worried about preparing my talk then listening to Matz at the time!

Since then, a number of different people have expressed interest in both Laszlo and Ruby. I figured I had finally better take a look at it.

I understand what the fuss is about. Ruby is one of the rare languages with a readable embedded syntax for metaprogramming, it’s well designed, and it has a mature library for web programming. What this translates to in practice is that you can program in a language with “keywords” (really just functions) suitable to the task at hand.

Compare the two class definitions below:

class Person < Object
  attr_reader :name
  attr :location
end

class Person < ActiveRecord::Base
  has_one :name
  has_many :address
end

The first definition uses the core language syntax to define a Person class that contains a getter for name, and both getters and setters for location. The second uses Rails to define a Person Active Record that has one name record and many address records. (It uses the Foreign Key and Association Table patterns, respectively.) The cool thing is that attr and has_one look the same to the library user. Ruby allows the library developer to grow a language. This lets the library user write in a concise domain-specific language that embeds Ruby.

What does this mean in practice? During my last vacation it took about five lazy vacation days with Ruby on Rails to implement a fairly sophisticated 40-page web application with five models, two metamodels, CRUD, cookies, image upload, and login. (I’ll write more about the application itself, if I find a few free weekends to harden it for public use.) For comparison, it took me about the same amount of time during my previous vacation to write a much simpler ten-page PHP web application that had only one model. And I already knew a little bit of PHP, whereas I was learning Ruby and Rails from scratch.

Now, what does this have to do with Laszlo? Laszlo certainly doesn’t have any metaprogramming facilities. It has states, constraints, and data binding, which extend the reach of declarative programming beyond static layouts. (Yeah, yeah, I should write about this too; in the meantime there’s docs and examples here and here.) I suspect that some of the people who “get” how to use metaprogramming in Ruby also get how to do declarative programming with the Laszlo features. But I also think a large part of what Laszlo brings to the table is simply that it allows you to use conventional OO techniques in client-side browser programming. For example,

<canvas layout="axis: y">
  <view width="10" height="10" bgcolor="red">
    <view x="1" y="1" width="8" height="8"/>
  </view>
  <view width="20" height="20" bgcolor="red">
    <view x="1" y="1" width="18" height="18"/>
  </view>
  <view width="30" height="30" bgcolor="red">
    <view x="1" y="1" width="28" height="28"/>
  </view>
</canvas>

DRYs out to:

<canvas layout="axis: y">
  <class name="box" width="${this.size}" height="${this.size}" bgcolor="red">
    <attribute name="size" value="10"/>
    <view x="1" y="1" width="${parent.width-2}" height="${parent.height-2}"/>
  </view>
  <box/>
  <box size="20"/>
  <box size="30"/>
</canvas>

This (OOP) is old hat in the server-side world — just like MOP is old hat to Smalltalk and Common Lisp developers — but it’s relatively new in the world of zero-install client-side platforms. So I think the analogy between Ruby on the server, and Laszlo on the (much more resource-constrained) client, is that each of them advances advances the reach of non-academic programming:

Update: Now that I’ve done more Ruby and DHTML programming, I can see that the diagram above gives OpenLaszlo short shrift. Although OpenLaszlo is lower level that Ruby with respect to code generation and a MOP, the use of databinding and constraints makes it higher level in a different set of ways.

Python really is becoming lisp. With the type/class unification, decorators, and generator expressions, it’s jumped from 80 percent of Common Lisp + CLOS to 90 percent¹, and for web tasks the web programming libraries often make up the difference.

I’ve listed below some of the functional and metaprogramming recipes and packages that have shown up in PyPI and the Python Cookbook over the past few weeks. [As of Memorial Day weekend, when I first wrote this. I didn't post it until a week later. My"real job":http://laszlosystems.com is heating up :-]

The point is not that these recipes exist. There’s plenty of clever Perl preprocessor hacks; there’s some pretty amazing C++ template metaprogramming libraries ; and I bet if you scoured the web you could find this many recipes for Java reflection. (Well, I don’t bet very much on the Java part. I’ll buy you an ice cream at Bart’s. First taker only.)

The point is that these are flowing in fast and furious, and that they don’t take much code. The recipes below are from just two weeks. There’s half a dozen functional programming recipes, and a dozen MOP recipes; many of them are one-pagers. There were some real wizards in the Lisp community, but I don’t recall anything like this pace of development on top of the CLOS MOP.

Two weeks of MOP and reflection recipes:
* Overriding new for attribute initialization
* Named tuple items: here and here
* Cacheable value objects
* Thread-safe caching
* “Simpler super syntax”:http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/286195
* Constants
* Prolog syntax
* Named Singletons
* Handler design pattern
* Monostate design pattern
* Simplified Mutable Instances

Two weeks of functional programming recipes:
* izip inverse
* Batched iterables
* Windowed iterables
* Grouped iterables
* Coroutines
* Cartesian product

Web programming in August:
* The Whole Web in a Dictionary
* Webcleaner, a filtering HTTP proxy
* rxrdf, an RDF application stack
* milter, interface to sendmail milter API
* itools, uri, resources, handlers, i18n, and workflow tools
* libgmail, a binding for Google’s Gmail service
* naja, a download manager and a website grabber
* IRC bots: pyfibot and supybot
* linkchecker, not sure what this does

And hotswap finally adds object evolution (what “live edit”).

¹ Percentage gains are subjective and are based on simulated exploratory programming conditions. Actual productivity will vary with hardware speed, workplace environment, develpment habits, and problem complexity. Results reported to SEI indicate that the majority of projects with these estimates will achieve between 71% and 123% of Lisp productivity in single-person projects and between 83% and 159% in team projects.

One of the things we’re building at Laszlo is LZX, a language for Rich Internet Applications. (Some of the other things we’re building are the client, server, and compiler pieces necessary to make applications written in that language actually do anything.)

Language design is a process, and there’s process-specific knowledge about how to do it. Much of the knowledge is the same that’s needed to design an architecture, or an API; some of it is language-specific. Here are some of the principles I’ve found helpful in designing LZX:
Continue reading…

A domain-specific language is a language for dealing with a specific problem domain, such as students at a university or entries in a blog. DSL implementation has become so easy, and some of the domains have become so deep, that there’s now a market for subdomain-specific languages (SDSLs).
Continue reading…