August 21, 2009

Pimp My Code, Part 16: On Heuristics and Human Factors

First off, I should mention that I don't think I use the word "heuristic" correctly – although in computer science it's grown to replace the word "algorithm" as just a general term for a way to solve a problem, traditionally it has a more narrow definition:
Heuristic (/hjʊˈrɪs.tɪk/) is an adjective for experience-based techniques that help in problem solving, learning and discovery.
(Yay, it's fun to copy and paste from Wikipedia!)

When I use it, I usually am talking about an algorithm that won't always give the correct solution, but does so often enough that the algorithm is useful. This differs from a classic algorithm, where we struggle mightily to make it provably correct in every instance.

But classic computer programming has largely failed, because it failed to copy nature. Nothing in nature works 100% of the time, but it sure works well MOST of the time – and when it fails, well, you die and get replaced. A human being, for instance, is an absolutely amazing machine, and is provably NOT provably correct.

--

To talk about computer heuristics, we'll need to get concrete. Could I get a "for instance?" Heck, yes.

For instance: NSDateFormatter has the following method:

NSDateFormatter (NSDateFormatterCompatibility)
- (id)initWithDateFormat:(NSString *)format allowNaturalLanguage:(BOOL)flag;

Ignoring for a second that 'flag' should be really be renamed 'allowNaturalLanguage' (I mean, honestly, if your method body refers to a variable named 'flag' it's not at ALL obvious what you mean, is it? You'd have to look at the method definition every time you saw this 'flag' variable, and that's just poor coding.) uh I lost my train of thought.

Oh! Yes. 'allowNaturalLanguage.' It's really cool! In most places you can enter a textual date in Cocoa (but not those fiddly NSDatePicker widgets where each number is in its own field), you can enter dates like, "Next Tuesday at noon" or "yesterday at 5:23PM" and Cocoa will magically turn that into a valid NSDate.

Possibly more importantly, you can type "Oct 16, 1969" or "10/16/69" or "10.16.1969" and it'll figure out what you meant my birthday in each case. (You cannot just type "Wil Shipley's Birthday" but that would be a great extension of their existing heuristic, if you ask me.)

This frees users up from having to figure out what magic combination of digits, dashes, slashes, words, and/or abbreviations comprise a valid date. Without this flag the programmer specifies exactly what format dates must take, like, "mm/dd/yyyy", and if the user doesn't type exactly that information, she gets an ugly error panel. With the flag, the user doesn't have to learn what the computer wants: she can continue to do things the way she has done them and the computer will understand her.

The latter is the touchstone of great design: we must strive to make our programs require as little learning as possible on the user's part. Each little thing they have to learn about our program is another obstacle to them using it fully, another tiny chunk of enjoyment stripped from their experience.

Now, a few releases of OS X ago (I believe 10.4), 'allowNaturalLanguage' was marked as deprecated; soon to be removed from the APIs. "What what what‽" said I. I filed a bug: "Why?"

The response was, essentially, the current heuristic doesn't work perfectly even in English, and fails badly in foreign languages.

That may seem like a logical reason to remove a piece of API, if you are a programmer. If you're a user, you're probably thinking, as I did: this is the worst reasoning in the world.

Let's say 65% of Mac OS X users speak English primarily. They were all enjoying not having to type dates and times the way the computer wanted. 65% percent of the users were just a little bit more happy with their experience on Mac OS X. And, crucially, the other 35% who didn't speak English had no idea what they were missing. It didn't hurt them at all to not have this functionality, it just didn't help them, either.

--

Life isn't fair, and programming is even less fair. Programming is all about picking a certain class of users with a certain specific class of problems, and making their lives much MUCH better. Like, if I didn't listen to music, I wouldn't care about iTunes. If I didn't take photos of my girlfriends naked, iPhoto would add nothing to my life... but that would be OK by me. iTunes and iPhoto don't have to please everyone in order to be good. They just have to please some people, and should please those people a lot.

We talk a lot about the 80% solution, which can be summarized thusly: Will 80% of your users think this feature / heuristic / bug fix is good? Then do it.

That rule seems obvious, really; the value of this rule is in remembering its obverse: if a feature / heuristic / bug fix is only going to help, say, 20% of your customers, you need to prioritize it lower.

It's easy when programming to get seduced into doing something really super-duper-cool no matter how obscure, but we have to remember our time is finite: spend your time where your users are going to see it. Do a GREAT job on those areas. (Don't do a shitty job on the other areas - skip them entirely.)

--

In Leopard, '-[NSDateFormatter allowNaturalLanguage]' is no longer marked as deprecated – I won that battle. But there's also a new date widget that makes entering dates a much more graphical affair, which democratizes the happiness. Clear graphics trump heuristic input methods – I use the widget now in my programs, unless I'm parsing text files, in which case I use 'allowNaturalLanguage.'

Everyone wins, now.

--

So, we switch to another heuristic, which requires a bit of background:

Amazon recently started requiring that all requests to their product catalog API be digitally signed with the secret password of a registered Amazon associate – one might assume they discovered stealing other people's associate codes is rampant, and they want to crack down on programs and websites that are violating their rules and using their APIs with stolen identities. A reasonable thing.

I rewrote the lookup code for both Delicious Library 1.7 and Delicious Library 2.2 so they will digitally sign requests, so my customers could keep looking up books and DVDs and stuff. (I don't think there are a lot of 1.x users still out there, but even so I didn't want to force them to pay upgrade to 2.x just to keep using my program.)

Now, since I've changed how I look up items, immediately after the release of I asked my support team to immediately prioritize all bugs reporting lookup problems, since you modify some area of code you want to alert your support people to actively look for failures in that particular area, so you can fix them immediately instead of waiting until they become a huge issue.

It turns out there was a tiny issue (searching for a book by title fails if its title has an apostrophe in it - fixed in 2.2.1) but while looking at user's bugs I discovered something more interesting: a number of users were reporting lookup failures because they were typing in ISBNs the way they see them on the boxes, eg: 978-0-316-01876-0, and they were getting no results, because Amazon stores ISBNs without dashes, eg: 97803780316018760.

Hrm. Now, my first response to this problem (a year ago when I'd just finished 2.0 and was exhausted) was, "Dammit, just don't type the damn dashes. Who looks up things manually by ISBN anyways? There's like twenty easier input methods, including dragging URLs in from Amazon or scanning with the iSight or typing the author's name... Geez." There was actually a lot more cussing than that, actually, but luckily I have Terry as a buffer layer between me and the customers, so it comes out as, "I'm sorry, we don't accept dashes in ISBNs or EANs right now..."

But after seeing bug reported again, I realized I'm violating my cardinal rule: I'm making users learn some picky input method that only exists because of Amazon's particular database formatting. And, worse, there's no good way for them to learn this rule unless they write us.

I should mention that there's only one search field: the user can type in numbers, author names, titles, or even keywords, and we just hand that stuff off to Amazon and let it do a fuzzy search.

So, how do we solve the dashes issue? Let's run through the solutions we think of, until we hit the best one.

Possible Solution 1: Document it
Add text near the search field: "Omit dashesWhen entering ISBNs or EANS"

Advantages of this method: • It's easy for us to add a field to the NIB. • The user can actually learn from this without having to write us.

Disadvantages: • We're teaching the user something that's not generally useful, instead of learning from her. • There's another damn text box on or page, which is one more graphical thing calling for the user's attention, and we've learned from bitter experience that every widget you add to a window is like killing a kitten. • This field requires localization.

Possible Solution 2: Remove all dashes from input
- (IBAction)findMatchingItems:(id)sender;
{
self.keywordsString = [self.keywordsString stringByReplacingOccurrencesOfString:@"-"
withString:@""];
[...search...]
}

Advantages of this method: • One line of code, sweet. • User doesn't have to learn anything: ISBNs and EANs can be entered with or without dashes, work either way.

Disadvantages: • User has lost the ability to search for titles where dashes are meaningful. Eg, "The Mythical Man-Month" would be turned into "The Mythical Manmonth," and Amazon may fail to find THAT, now (actually it does in this instance, but let's not rely on THEIR heuristic working in all cases.).

Possible Solution 3: Remove all dashes from input if input is of only digits and dashes
- (IBAction)findMatchingItems:(id)sender;
{
NSString *noDashesString = [self.keywordsString
stringByReplacingOccurrencesOfString:@"-" withString:@""];

BOOL containsOnlyDigits = YES;
for (NSUInteger characterIndex = 0; characterIndex <
noDashesString.length; characterIndex++) {
containsOnlyDigits &= [[NSCharacterSet decimalDigitCharacterSet]
characterIsMember:[noDashesString characterAtIndex:characterIndex]];
if (!containsOnlyDigits)
break;
}
if (containsOnlyDigits)
self.keywordsString = noDashesString;

[...search...]
}

Advantages of this method: • User doesn't have to learn anything: ISBNs and EANs can be entered with or without dashes, work either way. • User can still search for titles with dashes in them.

Disadvantages: • User has lost the ability to search for titles that are ONLY digits and dashes, for example, if a user were searching for a book about the latest quack diet, "10-10-10," she'd end up searching for "101010," and maybe not finding it.

Possible Solution 4: Remove all dashes from input if input is of only digits and dashes, and the number of digits is right for EANs or ISBNs
- (IBAction)findMatchingItems:(id)sender;
{
NSString * noSpacesOrDashesString = [[self.keywordsString
stringByReplacingOccurrencesOfString:@"-" withString:@""]
stringByReplacingOccurrencesOfString:@" " withString:@""];

BOOL containsOnlyDigits = YES;
for (NSUInteger characterIndex = 0; characterIndex <
noSpacesOrDashesString.length; characterIndex++) {
containsOnlyDigits &= [[NSCharacterSet decimalDigitCharacterSet]
characterIsMember:[noSpacesOrDashesString characterAtIndex:characterIndex]];
if (!containsOnlyDigits)
break;
}
if (containsOnlyDigits) {
switch (noSpacesOrDashesString.length) {
case LIISBNDigitCount: case LIUPCDigitCount: case LIEANDigitCount:
self.keywordsString = noSpacesOrDashesString;
default:
break;
}
}

[...search...]
}

(While I was in there, I decided to remove extra spaces if I pass the tests to remove extra dashes, so users can now also type "978 0 316 01876 0" and that will work, as well. It seemed like it might be as common, and it cost me almost nothing to add.)

Advantages of this method: • User doesn't have to learn anything: ISBNs and EANs can be entered with or without dashes, work either way. • User can still search for titles with dashes in them. • User can still search for titles with only decimal digits and dashes in them, as long as the number of digits doesn't happen to form a valid EAN, UPC, or ISBN.

Disadvantages: • Kind of reveals that I am a crazy person.

[Update: several sharp-eyed readers have pointed out I neglect to check for "x" or "X", which is valid as the last digit (the check digit) in the older ISBN-10s. Thank you... I'm human, too!]

[Update update: Reader Ian Stoba wrote me a note and suggested a more clever (and actually less code for me) heuristic, which is to remove the dashes and check the checksum (last digit) to see if the number that remains is a valid ISBN-10, UPC, or EAN. Since I already have written the methods to do these checks, this is very simple, and pretty fail-proof.]

--

So, that is the algorithm I went with. Let's evaluate this in terms of our goals for any good heuristic (like the one from NSDateFormatter):

  • It has to help some class of users – it helps users who type the dashes in ISBNs, UPCs, and EANS, and it helps them a lot, because before they had no clues how to proceed when lookups failed.
  • It has to not harm other users – it almost never will, because it won't change the input at all unless the user happens to be searching for an author or title that is all numbers and dashes AND has exactly 10, 12, or 13 digits it.
  • It shows the user what it's doing, so if the heuristic does fail the user will understand why – in this case, we replace the contents of the text field in which the user just typed her number with our new (dashless) number, and so if she really WERE searching for a book whose title was, say, "1-2-3-4-5-6-7-8-9-10-11," she'd see that was replaced by "1234567891011" when she did the search, and at least have a clue why the search failed.
--

Heuristics are the key to designing programs that work well with humans, that make humans smile. In college computer science classes, we learn all about b*trees and linked lists and sorting algorithms and a ton of crap that I honestly have never, ever used, in 25 years of professional programming. (Except hash tables. Learn those. You'll use them!)

What I do write – every day, every hour – are heuristics that try to understand and intuit what the user is telling me, without her having to learn my language.

The field of computer interaction is still in its infancy. Computers are too hard to use, they require us to waste our brains learning too many things that aren't REAL knowledge, they're just stupid computer conventions.

It's up to us to fix this.

Labels: ,