Oliver Steele

More Monads on the Cheap: Inlined fromMaybe

Tuesday, February 26, 2008

This article is about how to deal with null values. It follows up on this one. It’s intended for code stylists: people who care a lot about the difference between one line of code and two, or keeping control statements and temporary variables to a minimum. (A code stylist is kind of like the dual of a software architect, although one person can be both.) It’s not about code golf — although you might learn some strokes to use on that — but about keeping the structure of your code, even at the expression level, close to the way you think about the problem, if you think like me.

If you’re not a code stylist — and I’m not saying that being a code stylist, any more than being a prose stylist, is either a good or a bad thing — you might find it baffling that someone would put so much time into such simple topic. I won’t try to convince you otherwise. In that case, you might want to check back next week, when I’ll move back up to the bigger picture. (Specifically, some fun stuff involving how to use meta-object programming to solve race conditions in client-server models.)

A nullable or optional, type is one that might have a value of a certain basis type, but might be null. For example, a nullable array is either an array or null. Even if you don’t use a language with type declarations, you probably use a language with types. If a variable or field (JavaScript property) is expected to hold only arrays, it has type array; if it sometimes ends up holding null as well, it has type nullable array instead.

Haskell has a function fromMaybe that turns a nullable type into a non-nullable type, but replacing it with a default value when it’s null. What would this look like in a more conventional language, and where would you use it?

I’m using JavaScript as an example language here, but the techniques here apply to Ruby and, to a lesser extent, Python as well.

The First Problem Set

Here’s your assignment. It has three parts. In all of them, products is a list of products . In JavaScript, this list is represented by an instance of Array.

First, if products is non-empty, display its first item; otherwise, do nothing. This is easy enough:

if (products.length) {display(products[0])}

Or, for a more Lisp- or Ruby-like style, with the advantage that it can be nested in an expression:

products.length && display(products[0])

Second, apply a preload() function to each item in products. This is easy too:¹

products.forEach(preload)

Finally, extract the id from each product, and pass the list of ids to a function preloadAll.²

preloadAll(products.pluck('id'))

Raising the Bar

Let’s make this problem harder. This time, products might be an array, but it might be null.

“Hey!” you (ought to) protest. “That’s a stupid design. You’re giving me poorly typed data, and this introduces complexity and its attendant costs (development time, code size, test cases) to deal with it.”

Well, yes. But this is the real world. Maybe you’re reading an attribute from a deserialized XML element. XML schemas allow for this kind of abbreviation, and using it makes documents more concise (and therefore both lower bandwidth and easier to inspect for debugging), so you’ll probably see this at some point. Maybe you’re reading or a property from a JSON object, where the server omits null lists (for the same reasons — message size and debuggability — as for XML). Or maybe you’re reading products from a library that represents empty lists by null — for performance reasons (to avoiding making empty lists), or for backwards compatibility, or just out of laziness. I’ve seen all of the cases, a number of times.

Or maybe you used the technique in Monads on the Cheap to write something like (order||{}).products. Now that you’ve propogated a null order into a null products — to avoid wrapping an if statement around the code that dealt with order — you’ve got to pay the piper. You followed my advice and I dug you into a hole; now I’d better toss you a rope ladder.

Solution 1: Fixing the input on entry

You could fix products before you use it: insert products = products || [] at the top of your function to change a nullable array into a non-null array, by replacing null by a default value. If products is a local variable (as opposed to a function parameter), you could even do this where it’s initialized: replace var products = order.products, say, by var products = order.products || [].³ So the three solutions above become simply:

// products may be null
products = products || [];
// products instanceof Array
if (products.length) {display(products[0])}
 
products = products || [];
products.forEach(preload)
 
products = products || [];
preloadAll(products.pluck('id'))

Raising the Bar Again

Where products is a local variable, “fixing the input” really is the best solution. However, it’s not the most general solution (for reasons I’ll get to). So I’ll move the bar again.

This time, instead of the variable products, it’s the expression offer.products that evaluates to the nullable array. What’s the smallest change required to adapt our code to null values, in this scenario?

Solution 2: Introducing a temporary variable

This one looks absurdly easy too. Changing a line of code to accommodate nullable arrays involves a simple program transformation. Replace offer.products by products, and insert var products = offer.products || [] on the line before. Here are the before cases, where offer.products is not allowed to be null:

// requires products instanceof Array
if (products.length) {display(offer.products[0])}
offer.products.forEach(preload)
preloadAll(offer.products.pluck('id'))

And here are the after cases, where offer.products is allowed to be null:

// accepts null products
var products = offer.products || [];
if (products.length) {display(products[0])}
 
var products = offer.products || [];
products.forEach(preload)
 
var products = offer.products || [];
preloadAll(products.pluck('id'))

Non-local Transformations

There’s something funny about the “temporary variable” program transformation. offer.products is an expression — you can nest it in another expression: as the argument to a function, before a property accessor, or as part of a conditional. var products = offer.products||[]; ...; ...(products)... is a statement sequence. In fact, it’s a statement sequence with a hole — it doesn’t strictly embed the original code, but it isn’t strictly embedded by it, either; instead, it’s woven in.

These differences — that this transformation changes the syntactic type of the code that you’re applying it to (from an expression to a statement), and that you have to weave it into the existing code — make it non-local.⁴ Here’s what I mean by this:

To apply this transformation — to change code that expects an array into code that accepts a null — we look for an occurrence of offer.products; we replace it by products; and then we travel up the syntax tree (we look at the expression that contains offer.products, and then the expression that contains that) until we find a statement. Finally we insert var products = offer.products||[] before that statement.

Admittedly, there hasn’t been much to this in the statements so far. We’ve simply replaced the first snippet below (with one line of code) by the second snippet (with two lines). And the lines are adjacent, so it’s easy enough to read them as a unit.

// requires products instanceof Array
preloadAll(offer.products.pluck('id'))

// accepts null products
var products = offer.products || [];
preloadAll(offer.products.pluck('id'))

It gets worse, though. Let’s make offer nullable too, and add some more computation. (I’m trying to get offer.products far enough inside of an expression that we can get a feel for where the problems arise.)

In the first block below (which doesn’t deal with nullable arrays), offer is either an object with a products property (which is always an Array), or null. If it’s not null, we load its products. We then set loaded to true if there was an offer, and if any of its products were already loaded. (preloadAll returns true in this case.) Simple enough:

// accepts null offer; requires products instanceof Array
var loaded = offer && preloadAll(products.pluck('id'));

Now, how do we change this if not only offer, but offer.products, are nullable? We apply the transformation above, inserting the statement var products = ... and changing offer.products to products. But where do we insert the statement? It has to go before the call to preloadAll, but after the test for whether offer is null.⁵ But in the listing above, there isn’t any such location!

To create one, we have to split the initialization expression in half, in order to get the test for offer and the use of offer.products into separate statements, so that there will be room for a statement (not added yet) between them:

// accepts null offer; requires products instanceof Array
var loaded = false;
if (offer)
  loaded = preloadAll(offer.products.pluck('id'));

And now we can hoist offer.products out of the second new statement, without moving it before the first:

// accepts null offer, offer.products
var loaded = false;
if (offer) {
  var products = offer.products || [];
  if (preloadAll(products.pluck('id'))
    loaded = true;
}

This is awful! Not only did it go from one line to five, but loaded changed from a non-mutable variable with an initializer into a mutable variable with two different assignments, such that its initialization is split across the inside and the outside of a conditional. This is the kind of code that, if I let it take over 5% of my program, takes up 50% or my debugging time.

You might think these problems are because of the distinction between statement and expression in Algol-style languages (C, C++, Java, JavaScript). This is partly right, but it’s only somewhat better in Lisp-style languages (Smalltalk, Lisp itself, Ruby). Here’s a straight translation of the JavaScript code into Ruby:

// before: accepts offer == nil; requires offer.products.is_an? Array
loaded = offer && preloadAll(products.map &:id));

# after: accepts offer == nil, offer.products == nil
loaded = false
if offer
  products = offer.products || []
  loaded = preloadAll(producs.map &:id)
end

Now let’s use the fact that Ruby statements are expressions to re-write the second case:

# also accepts offer == nil, offer.products == nil
loaded = offer && preloadAll(begin products = offer.products || []; products.map &:id));

Sure, this is back down to one line. And it avoids the cascading rewrite of the first transformation (where changing the innermost expression into a statement required changing the expression that contains it into a statement). However it’s far from idiomatic Ruby.

Worse, like the JavaScript snippet (and this is another problem with temporary variables), it introduces a products into the surrounding environment, or overwrites the existing value of products if there’s already a variable with that name there — a subtle source of bugs, especially when you apply this transformation more than once.

Solution 2: Ifs and Ands

You could use conditional statements to transform the original solutions from these:

// requires non-null product
if (offer.products.length) {display(offer.products[0])}
offer.products.forEach(preload)
preloadAll(offer.products.pluck('id'))

into these:

// accepts null product
if (offer.products && offer.products.length) {display(offer.products[0])}
if (offer.products) offer.products.forEach(preload)
if (offer.products) preloadAll(offer.products.pluck('id'))

The first line (if (products) {...}) already had a conditional, so we stuck the new test into the existing conditional. The other two lines didn’t, so we wrapped the original code in new conditionals to hold the new test.

Scalability

The “ifs and ands” solution works, but it doesn’t scale. (“Doesn’t scale” is Enterprise for “I don’t like it.” In this case, I’ll ~~rationalize~~ define “scale” as “grows linearly and compositionally with the number of variables and/or the complexity of the syntactic context”.)

First, like the “temporary variable” solution, it’s non-local — it involves changing an expression into a statement, and therefore the expression that contains that expression into a statement, and so on up the line.

It’s also non-linear (in the sense of linear logic⁶, not linear algebra). Where an expression occurs once in the original code, it occurs twice in the new code. It evaluates offer.products three times instead of twice in the first case, and twice instead of once in the other two.

To see why this is bad, imagine if instead of offer.products it were offer.getProducts, or customer.offer.products, or ((customer||{}).offer||{}).products. Or imagine if it were an expression that had side effects — then the first example wouldn’t have worked anyway, but we would have just broken the other two.

To get another taste of how the expressions replicate with this strategy, take a look at what happens when here’s more than one of them. What if there are two such properties, offer.products and offer.merchants, and we only want to execute our code if they’re both non-empty? Here’s the case for non-nullable arrays:

// offer.products and offer.merchants are non-null
if (offer.products.length && offer.merchants.length) {...}

This code transforms into this:

// offer.products and offer.merchants may each be null
if (offer.products && offer.products.length &&
    offer.merchants && offer.merchants.length) {...}

Or let’s say we wanted to sum the lengths of two properties, offer.ordered and offer.saved. The code for the non-nullary case is simply offer.ordered.length + offer.saved.length. The nullary case balloons into a statement sequence:

// offer.products and offer.merchants may each be null
var count = 0;
if (offer.ordered) count += offer.ordered.length;
if (offer.saved) count += offer.ordered.length;

Or we could use the ternary operator, but still at the cost of typing (and evaluating) each nullable subexpression twice:

// offer.ordered and offer.saved can each be null
(offer.ordered ? offer.ordered.length : 0) : (offer.saved ? offer.saved.length : 0)

The problem with all of these is that we’ve had to write out each variable name twice, inviting defects. In fact, I made a paste-o in one of the examples above. I could fix it, but I bet I’d make it again if I later changed the code to include offer.wishlist in the count.

Solution 3: Inlined fromMaybe

Here’s an alternative. To change code that expects a non-nullable array to a nullable array, change array to array||[]. This is a local transformation: it changes an expression into an expression (not a statement), so you don’t need to re-write the code that contains it. It’s also a linear transformation (again, in the sense of linear logic, not linear algebra): an expression that only occurs once before the transformation, only occurs once after it.

The original solutions transform thus:

// offer.products can be null
if ((offer.products||[]).length) {...}
(offer.products||[]).forEach(...)
if ((offer.products||[]).length || (offer.saved|[]).length) {...}

Note that each transformation is local: no new control structures are introduced, so there’s no cascade of expression -> statement transformations up the syntax tree. We can see that by the fact that the troublesome loaded case remains largely intact.

// offer and offer.products can each be null
var loaded = offer && preloadAll(offer.products||[]).length);

Here’s the summation code:

// offer.ordered and offer.saved can each be null
count = (offer.products||[]).length || (offer.saved||[]).length;

Beyond Arrays and JavaScript

This technique works in any language where arbitrary values can be used in a boolean context (that is, practically every language except Java) and where null is considered false, and for any type whose values test true. This includes Object and Array in JavaScript, additionally Number and String in Ruby (since 0 and “” are considered true in that language), and — well, the moral equivalent of Object types in Python, since Python collections implement nonzero() or len.

But actually we can go ahead and use the technique even with types that contain a false value, where we want to replace that false value by a default anyway (either the same false value, or a different value that tests as true). For example, even though JavaScript "" tests false, we can use inputString || "" to coerce a nullable string to a non-null string, since it will null and "" are the only two values that it will change to ""

Here are some examples that go beyond arrays. First, using the ternary operator. (Which isn’t so bad here, since the expression is in a variable already — bear with me and pretend the expressions are more complex):

var count = products ? products.length : 0; // the original example: an array
var value = inputString ? parseInt(inputString, 10) : 0; // string
var option = options ? options.key : 'default'; // Object used as dictionary
var result = fn ? fn(argument) : defaultValue; // Function
sprite.moveTo(x ? x : 0, y ? y : 0); // number

And now, using the inlined fromMaybe technique, in JavaScript, Ruby, and Python:

// JavaScript
var count = (products || []).length;
var value = parseInt(inputString || '0', 10);
var option = ({key:'default'}.key;
var result = (fn || Function.K(defaultValue))(argument);
sprite.moveTo(x || 0, y || 0);

# Ruby
count = (products || []).length
value = (inputString || '0').to_i
option = (options || {:key => 'default'})[:key]
sprite.move_to(x || 0, y || 0)

# Python
count = (products or []).length
value = int(inputString or '0')
option = (options or {'key': 'default'})['key']
sprite.moveTo(x or 0, y or 0)

The Real Thing

For reference, here’s how these examples look in Haskell.

let count = length (fromMaybe [] products)
let value = read (fromMaybe "0" inputString)
let option = lookup (fromMaybe [["key", "default"]] options) "key"
moveTo sprite (fromMaybe 0 x) (fromMaybe 0 y)

This is fairly unidiomatic Haskell. You can do a lot better, by modifying the functions instead of the values:

let count = maybe 0 length products

Scala also has a nullable type (Option), with a getOrElse method.

val count = (products getOrElse List()).length

Although, as with Haskell, you’d write this differently in idiomatic Scala:

val count = products.map(_.length) getOrElse 0

¹ forEach was added in JavaScript 1.6, and works in Firefox. You can get cross-browser implementations from Dean Edwards or the Mozilla Developer Center; or with frameworks such as the JQuery (in the jQuery collection plugin), Prototype (where it’s called each), or MochiKit (where it’s a top-level function).

² anArray.pluck is from Prototype. In pure JavaScript 1.6 (or another library that extends JavaScript with the 1.6 collection functions), this would be products.map(function(product) { return product.id }). Or in Functional, it’s map('_.id', products)

³ In conjunction with monads on the cheap, in the scenario where products might be null because order might be null, the code looks like this: var products = (order||{}).products || []. In fact, this is simply an extension of monads, where the default value is the empty array, instead of {}.

⁴ This disruption is in addition to the fact that now you’ve got to come up with a variable name (usually easy), and make sure that if you do this to two different pieces of code in the same scope you use two different variables (harder), and hold a larger set of variable names in your head when you’re reading this code a year later (hardest).

⁵ In this particular case, we could instead use the cheap monads idiom (offer||{}).products. But not every embedding expression is a test for nullity.

⁶ Linear logic is just a system where you can’t replace once occurrence of an expression by two. I didn’t link to the wikipedia page in the text because it’s written for logicians, not programmers, and makes it look scary-complicated, but here it is. Failing linearity is what goes wrong in C macros.

Filed in Essays, JavaScript | | Comments (8)

Self-Printing JavaScript Literals

Friday, February 15, 2008

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.

Filed in JavaScript, Tips | | Comments (5)

Supply/Demand Springs

Thursday, February 7, 2008

Full size (pdf, png).

Update: This is what I call an entry-level metaphor — it’s a rough sketch of the relation between the concepts, not a productive metaphor that can be used to reason about them beyond this. It doesn’t support analytic microeconomic analysis, and it’s not even consistent at the level of the supply chain. (For example, the unit cost needs to include the component cost, whereas the illustration shows these as complementary; this is because the metaphor leaves out profit.) Nonetheless, I find it a helpful starting point before going more analytic.

It popped into my head when I was answering my son’s question about what “supply and demand” meant. (He had run across it in a Newsweek article he’s reading in his history class.) It seemed to work for him, so I decided to write it down here. We’re both so used to talking about images in words that I didn’t realize until I made this that I’d never actually put it on paper!

Filed in Illustrations, Visualizations | | Comments (4)

Knowledge Per Unit Time

Tuesday, February 5, 2008

My friends have been asking me how important I consider experience (again in the context of the election), enough to write the answer down.

Experience can mean contact with facts and events; or, the knowledge and skill that this contact causes. One sense measures the past; the other, the present. It’s the fact that one word has both senses that can allow one to describe the same life history as either “thirty years experience”, or one year of experience thirty times.

But even in its second sense, “experience” is a proxy measure for an unknowable: knowledge and skills that will be useful in the future. To the extent that the future resembles the past, it’s a perfect proxy; where they diverge, the correlation drops.

As a hiring manager, if I were to hire someone to do a specific job and they had done that same job before (in the same kind of organization, with the same tools, and the same requirements and constraints), and I only needed it done the same way, I might look no further.

I’ve never hired for such a job, so what I’m usually more interested in is “experience per unit time”: the efficiency with which a candidate converts the first kind of experience (contact with the world) into the second (knowledge and skills). This is because I expect the candidate to encounter new facts and events, and to need to use these encounters to create new knowledge and skills.

Age is a factor here: not because of the merits of youth for its own sake, but because it shows up in the denominator. If the ability to process life into knowledge and skills were all that mattered, then someone who had seen twenty years of experience (in the first sense) would need show at least twice as much experience (in the second sense) as someone who had only seen ten. This isn’t an advantage of youth, unless you’re comparing candidates with equal experience.

In a democracy, selecting a leader is like hiring an employee: specifically, a manager, or a CEO. (Or in some ways like hiring a contractor, because you can get rid of one by letting the contract run out; it’s harder to get rid of a bad employee .) The same criteria — motivation, ability, character, ethics, knowledge, interpersonal skills, management skills, communication skills, ability to process information and make decisions — apply. Experience, and the ability to acquire it, are important parts of the picture.

Filed in General | | Comments (1)

Two Thoughts on Elections

Tuesday, February 5, 2008

What follow are some notes from talking about the elections and the presidential primaries with my children, and some metaphors that I found helpful in thinking about the topics. They’re not otherwise related to each other, except that they all came up over the last couple of days.

1. Votes are Agents

The wikipedia article about voting systems, and the Newsweek article When Math Warps Elections describe a number of different systems: in particular, the America plurality system where you casts only one vote (presumably for your favored candidate, unless you’re voting strategically); approval voting, where you vote for all the candidates your find acceptable (again, unless you’re voting strategically); and ranked-choice or instance-runoff voting, where you rank the candidates, and the candidate who was highest on the smallest number of ballots is removed from all of them until only one candidate remains.

It can be hard to compare these systems. The wikipedia lists some criteria, but it’s a few hours time to learn enough about the theory in this area to apply them.

So here’s a less formal way to think about this, using a metaphor that’s more familiar to most of us (including kids) than the language of the economic theories:

You’re building a robot. The job of the robot is to vote for a candidate, on your behalf. Your robot may need to vote several times: the real election may be built out of a number of micro-elections with different sets of candidates. The reason you’re delegating this to a robot instead of doing this yourself is that it’s logistically easier, and faster, to get each voter to build a robot¹ once than to get each voter to show up for each micro-election.

One way the voting systems differ is in how much you get to tell your robot; and, therefore, what your robot does in the elections where your first-choice candidate isn’t on the ballot². In a plurality system, you can only tell the robot your first-choice candidate; your robot has to sit out the micro-elections where your candidate isn’t on the ballot. In an approval system, where you’ve selected several unranked candidates, your robot doesn’t have enough information to vote in those elections where more than one of your candidates is on the ballot. In an instant-runoff system, your robot always knows how to vote the same way as you.

Kids seem to have a sense that there’s something a bit off about strategic voting; and, therefore, about systems that require it. (Among other problems, strategic voting is a bit like learning test-taking skills for the SAT: it provides an advantage for those who have thought of it, which may bias the election.) In the robot metaphor, strategic voting comes about only when your robot is too stupid to do what you want it to in every micro-election, so you have to decide what to tell it in order to get it to vote right in the micro-elections that you think are more likely to come up, or more likely to matter.

2. Primaries and Decision Theory

[This is unrelated to the first topic, except that they're both about elections.]

Let’s say you want to run for president. To do this effectively, you need a certain amount of manna (money, endorsements, and organizational backing); each bit of manna increases your chances of winning.

There’s a mana provider with a lot of huge amount of manna, who’s willing to make a deal with you: after you accept the terms of the deal (and only after), they’ll decide whether to anoint you (this is the process by which they give you all their manna); and if you don’t, you agree to drop out of the race.

This deal has a up side — that you’ve got more manna, and therefore you’ve increased your chances of winning the election if you’re anointed — and a huge down side — that if you accept the deal and the manna provider doesn’t anoint you, you’ve decreased your chances of winning the election to zero (because then you’ve promised not to run).

Let’s say you have a 20% chance of winning the election on your own, and that being anointed increases your chances by 20%. Then the payoff matrix looks like this:

	anointed	not anointed
reject deal	0.2	0.2
accept deal	0.4	0.0

Now let’s say you have only a 50% chance of being anointed. Then your chance of winning the election if you reject the deal is 20% (in this case it doesn’t matter whether you would have been anointed not), and your average chance of winning the election if you accept the deal is also 20%. It’s not obvious whether you should accept the deal or not; it depends on your risk tolerance.

But now let’s throw a couple of other factors into the mix. Both of these factors have the effect that your chance of being anointed is correlated with your chance of winning the election.

First, the manna provider could attempt to anoint you exactly when your chances of winning are greater anyway (by using some tool, such as polls or an interim election, to estimate these chances). If instead of having a 20% chance of winning the election without anointment, you either have a 30% chance or a 10% chance (you don’t know which when you make the deal), and you’ll be anointed if it turns out (after you make the deal) that it was closer to 30%, then the matrix looks like this:

	anointment-worthy	not anointment-worthy
reject deal	0.3	0.1
accept deal	0.5	0.0

The other factor that increases the correlation between being anointed and winning the election is that if you are not anointed, someone else is, and this decreases your chances of winning the election, say by 20% (but not to less than 1%).

Then the matrix looks like this:

	anointment-worthy	not anointment-worthy
reject deal	0.1	0.01
accept deal	0.5	0.0

The mana providers, of course, are political parties; and this is why candidates join parties.

What’s in it for the manna providers? This is just strategic nomination, to avoid splitting the vote in a plurality voting system. Interestingly, strategic nomination is analogous to strategic voting, only proactive, and aggregated at the level of the political party.

—

¹ These are really simple robots, and we can build them all by putting checkboxes or numbers on a paper ballot.

² The other ways they differ are in how they many micro-elections there are; how they determine who runs in each of those; and how the results of the micro-elections are aggregated to determine the winner of the overall election.

Filed in Math Education | | Comments (1)

Adding the Easy Piece; or, The Metaphor of the Rock

Saturday, February 2, 2008

The novice project manager cares about a program’s size. The experienced manager cares when it gets big.

Big programs are, from a developer’s perspective, slow. Slow not to run, but to develop: effortful to maintain, expensive to change. Half the job of a project manager is to keep programs small by keeping their requirements small (and half the job of an architect is to keep them small when the requirements are large); this is about the case when this isn’t enough.

Developing a program is like pushing a rock around a room. (The rock is called “code base”. The room is an irregular shape called “design space”, with “requirements” marked off along the wall.) Big programs are big, heavy rocks. They require more push, to get less far.

Sometimes you can get several people to push one rock. This works if the rock is the right shape – if it’s straight and wide, say, so that many people can push it the same direction, at the same time. Otherwise they will push at different angles, and the greater part of their efforts will cancel.

Sometimes, you can break the rock into smaller pieces – so that different people can push them, or so that you can push them separately, or so that you can abandon some pieces and use instead pieces that are sited where you’re going. (The advantage of a pre-sited piece’s location can outweigh the fact that it’s not quite the right shape.)

Sometimes you can polish the floor, or insert rollers, or employ a cart (use languages, platforms, practices, tools). Sometimes, though, you spend more time polishing the floor than you would have spent moving the rock; and sometimes the rollers end up aimed differently from where it turns out you need the rock. But even when these tricks work, they only increase the size of rock that’s counts as “big”. Some rocks are still big rocks.

This perspective – the size of the rock – is the static view of code size. It’s concerned with how to move rocks of a fixed size. The static> view is the right view for maintenance programming. It’s the right view for (most of) version three of a product, where most of the program is unchanged from version two. Often it’s the right view for version two as well.

For a greenfield project – a project where you’re (mostly) not modifying an existing system, but (mostly) starting from scratch – the static view is too limited. In a greenfield project, you’re not just moving the rock. You’re building it too.

(How do you build a rock? By fastening other rocks to it. Or sometimes by coating chicken wire with papier mâché, if you just need to know how it looks.)

Greenfield development sounds simpler. Instead of pushing the rock where it’s needed, you just build it there. There’s some work (pushing) that you don’t have to do.

But oh, did I mention that you won’t know where the rock needs to go until you’ve already built some of it? (Funny how often that isn’t mentioned.) In fact, you may have even less of an idea where to site the rock that hasn’t been built than one that has, because the shape of the rock helps determine the site, And if a rock takes long enough to build, the room may change too.

So, you’ve got to build the rock, and you’ve got to push it, and you could do these in any order (build some, push some, build some more, push some more), except that you won’t know where to push it until you’ve got some built. And just to make this harder – and more realistic – there’s some parts you can’t build where you start, but only where you push it to.

This is the dynamic view of code size: that code size changes over the course of a project. The fundamental question about dynamic code size is: Does it matter what order you build the rock? If you know you’ve got to add a piece, does it matter whether you add it at the beginning or end of the project?

And the answer is yes, it matters. Sometimes greatly. Sometimes enough to determine whether you can build, and push, your rock at all. The reason is because building the rock makes it harder to push.

Often, on a project, there’s a few pieces that you know at the outset need to be there. They’re standard parts, that need to be attached to every project. You know how to attach them. It will be comforting to do so.

(Sometimes these pieces have names like “localization”, “optimization”, and “scalability”; or “graphic design complete”; or “windows compatibility”; or “undo”.)

Some advantages of attaching these pieces early are: an easy sense of accomplishment, and a feature checked off. They simulate great and early progress. The disadvantage is that they increase project drag. Attaching them makes pushing the rock harder. Make it harder sooner, and you’ve made your trajectory like the orange line, and not the green one, below.

It’s not that you should never add these pieces first. Building and pushing rocks is engineering; and engineering is the art of the trade-off.

Here are some reasons to add a piece sooner. You don’t know if you’ll be able to add it later, or if you’ll have time if you wait, or how long it will take. (You want to front-load uncertainty and risk.) Or: you need to show the rock to somebody, and they can’t imagine what it will look like with the missing piece. Or: you can’t imagine this either. Or: knowing how to add a piece gnaws at you – it’s a distraction – and you can’t concentrate on harder work until you’ve added the easy piece. Or: the rock is useful only halfway built, and the piece is the useful one. Or: you’ll have to tear the rock apart to attach a piece later, and this is more work than pushing a bigger rock now.

Engineering is the art of the informed trade-off. These reasons to make a rock bigger sooner are (can be) good reasons. Weigh them against the cost of pushing a bigger rock.

Filed in Essays, Software Development | | Comments Off

Getting Lost

Thursday, January 24, 2008

I like to travel in style. Two different styles, in fact: exploratory, and direct.

When I’m late to an appointment, I take the most direct, familiar, route I know. I don’t try any tricks — roads that vaguely ring a bell, or look like they might connect — I stay with what I’ve known.

But when I’ve time to spare, I get lost. Given a choice between a 15 minute route I know, and one that might take twice as long, I’ll take the road less traveled (by me). I’m paying for knowledge, with time.

I discover a lot of good routes this way — not always to the place I was going at the time, but often to somewhere I want to go later, when I’m in a hurry and wouldn’t have time to look for them. And, when I am in a hurry and I do get lost — because I’m coming from or going somewhere unfamiliar, or have to detour — I’m more likely to come across a place I recognize, and place myself back onto my mental map.

So maybe it’s too simple to say that I’ve paid for my knowledge with time. I’ve made a deposit (of time), that I can withdraw later. Knowledge is the loan note.

The same holds in programming, and project management, and software development. (These are some areas that are open-ended but set against a virtual landscape, and with which I’ve some experience.)

Often, as developer and project managers, we’re up against deadlines. Crunch time is not the time to risk something new.

But the rest of the time, it helps to take the detour, so that the next time you’re in a hurry and need something (a library, a technique, a language, a framework), you can remember where you saw it.

It helps to stay a little lost.

¹ Neither is when you’re working on someone else’s dime, unless it’s your employer’s decision. (Doing this from time to time would often be a good decision, but it’s rare.) This is one reason I write libraries.

Filed in General | | Comments (1)

Why Write Open Source Libraries

Thursday, January 24, 2008

1. Exploration. I can sample platforms and sample stretch languages without sinking my stakeholders if I fail. Also, it’s easier to try something radical in a small, green field project than in a big one.

2. Altitude training (link TBD). I can make myself jump through hoops that I wouldn’t feel ethical asking someone to pay me to jump through. I did this recently with Sequentially; the next time I needed to simulate concurrent processes in a more serious context, it was a lot easier.

3. Encapsulating components. My answer to Steve Yegge’s problem is to refactor my code into libraries. When I write programs that run on Linux, or the JVM, or a browser, I get those features, but the code sizes of those libraries don’t really count against me. Why not do that with my own code, too.¹

This was the motivation for LzOsUtils and Fluently (both didn’t get to projects), most recently: they were part of other projects, but they were respectively large/tricky enough that I wanted to be able to compartmentalize them, and think about them separately.

5. The Golden Rule. I’ve benefitted hugely from open source projects; why not give back a little?

6. You can take it with you! I’ve written things that I want to use in more than one project; this is easier if they’re in library form. That was the motivation for LzTestKit (another didn’t get to project), most recently.

7. Fame and fortune! Just kidding. You get more fame from working on one project (if it’s the right one) for a long time. And there’s more fortune in straight consulting.

8. More days. I’m with Joel and Leo Babauta (ZenHabits): sometimes I can only work productively for four hours a day. The trick is to have more days. If I’ve got another project I can switch to when I burn out for the day on the first one, sometimes I can get another work day out of it. (Another trick for getting another day to move from the home to the office or vice versa, or to switch cafes.)

¹ Interestingly, the extra work to some code up so that I never need to look inside it again (docs, test cases, examples) and can remember how it works years later is exactly the same work that I need in order for someone else to use it. I use to think I could take a short cut on things I use myself, but with enough going on or enough years in between, it isn’t true.

Filed in Programming | | Comments Off