PragPub 2012-10: Issue #40

Table of Contents

Features

Thinking Functionally with Haskell

by Paul Callaghan

Paul has introduced some of the key concepts of the Haskell language in the past two issues, and now puts them to work in an interesting exercise.

Tales from the Ops Side

by Michael Nygard

Michael returns with one more tale of a system that went wrong, and a lesson in why.

It’s Not About the Unit Tests

by Jonathan Rasmusson

Jonathan brings his years of software development to iOS app creation, and finds out that some cherished assumptions no longer hold.

Threads

by Michael Swaine

The flamboyant entrepreneur behind a legendary software product find himself a beneficiary of Apple’s Map snafu.

Departments

Up Front

by Michael Swaine

Back in time to language develoment in 1984, forward to the functional language Haskell, unit tests vs. iOS development, and a tale of a Web site that was waiting for Godot.

Choice Bits

Which Pragmatic Bookshelf books are hot right now.

Calendar

Author sightings, upcoming conferences, and other events of note.

Shady Illuminations

by John Shade

A cockroach festival, zombie cybernetic cockroaches, the internet considered as a cockroach, and Apple’s Map app flap.

But Wait, There’s More...

Coming attractions and where to go from here.

Except where otherwise indicated, entire contents copyright © 2012 The Pragmatic Programmers.

Feel free to distribute this magazine (in whole, and for free) to anyone you want. However, you may not sell this magazine or its content, nor extract and use more than a paragraph of content in some other publication without our permission.

Published monthly in PDF, mobi, and epub formats by The Pragmatic Programmers, LLC, Dallas, TX, and Raleigh, NC. E-Mail support@pragprog.com, phone +1-800-699-7764. The editor is Michael Swaine (mailto:michael@pragprog.com). Visit us at http://pragprog.com

ISSN: 1948-3562

Up Front

From Turbo Pascal to Haskell

by Michael Swaine

The leaves on the liquid amber trees outside the door are starting to turn. We’ve had some corn on the cob that was so sweet it didn’t need butter. Soon we’ll be choosing our perfect pumpkin for the carving party toward the end of the month.

Autumn is a nostalgic time of year, and I found myself slipping into a sentimental mood as I wrote about the birth of Turbo Pascal in a little computer history article for this issue. The community for which the arrival of a new programming language implementation is an occasion of celebration is a special community, and Turbo Pascal was a special programming language implementation.

But magazine editors need to think a season ahead, so I’m also thinking about winter downtime and the article that you could write for me while your loved ones are frolicking on the beach or on the slopes. Pardon me if I inappropriately project my lifestyle onto you. But if I’m right and you have a little free time in the next couple of months, you might consider writing an article for PragPub. We pay in fame and gratitude, and the satisfaction of getting your words and code out there in front of the smartest technical audience I know.

But maybe you want some examples of what we’re looking for? You might start with this issue.

Over the past few issues, Paul Callaghan has been favoring us with a series on Haskell, a purely functional programming language. At the Functional Programming Languages and Computer Architecture ’87 conference, Haskell was chosen as an open standard for functional languages, and it now serves as a basis for research in functional-language design. But over the years Haskell has become a practical language for development. In this issue, Paul puts the key concepts developed in earlier columns to work in an interesting exercise to demonstrate its virtues.

Michael Nygard is back this month, too, wrapping up a series of horror stories from his days as a troubleshooter for “for a company that offered 24x7 operations for websites that we didn’t create.” In this installment, he reveals how he solved the problem of the system that was waiting for Godot.

Also: Jonathan Rasmusson shares some insights gained while working in iOS development. Your editor takes you back in time. And John Shade decides not to delve into Apple’s Map app flap and instead spends his whole column talking about cockroaches. You don’t want to miss that!

Choice Bits

What’s Hot

Which Pragmatic Bookshelf books are hot right now.

What’s Hot

Top-Ten lists are passé—ours goes to 11. These are the top titles that folks are interested in currently, along with their rank from last month. This is based solely on direct sales from our online store.

1^ | NEW | The Pragmatic Programmer
2^ | NEW | The Definitive ANTLR 4 Reference
3^ | 7 | Practical Vim
4^ | NEW | iOS SDK Development
5^ | NEW | Mac Kung Fu
6v | 4 | Agile Web Development with Rails
7v | 6 | Programming Ruby 1.9
8^ | NEW | Explore It!
9^ | NEW | Outsource It!
10v | 8 | The Cucumber Book
11 | 11 | The RSpec Book

Our usual panning of gold from the Twitter stream is still looking for a few good nuggets. Surely by next month some shiny things will show up.

Thinking Functionally with Haskell

Playing with Haskell

by Paul Callaghan

Paul has introduced some of the key concepts of the Haskell language in the past two issues, and now puts them to work in an interesting exercise.

The Word Chain Kata

It’s time to do some programming now, so let’s try a kata. We’re going to look at Dave Thomas’s Word Chain exercise. The objective is to find a series of steps from one word to another, where for each step a single letter is changed such that the resulting word is valid. For example, turning “lead” into “gold” with the path ["lead","load","goad","gold"]. For simplicity, I’ll assume four-letter words and lowercase throughout.

This problem is more “algorithmic” than “real world,” but it’s a useful step in our journey to larger use of Haskell or above—it is important to understand the core language and how to use it before we tackle anything more advanced. Plus, after last month, I think we all deserve a shorter article! [only marginally shorter!]

Where to start? This is often the hardest question. Personally, I like to start somewhere near the bottom and play around with ideas a bit, then start building upwards. (However: I must confess that I used a similar example in lectures for a few years so I know where it’s going. But I’ll try not to let this show too much....) As we go, we can reflect on what we’ve built and maybe refactor if or when we get some more insight about the problem.

Note that this isn’t a tutorial on programming in Haskell—we don’t have the time or space for that here, and there are several good references for this (as discussed below). Instead, I’m aiming to get you interested in some key ideas and give you something to think about.

Finally, remember the golden rule—it’s all about data, so the process will be all about identifying relevant data structures and transformations, and about decomposing big problems into smaller problems until we can solve them in a straightforward way. Remember the silver rule too—“trust your compiler,” so focus on clear code first before you worry too much about efficiency.

Development Tools and Language Version

I’m going to use the Glasgow Haskell Compiler (GHC) as the main development tool here. GHC is the most advanced implementation of Haskell, covering the standard language (Haskell-98) and many experimental extensions and libraries, including some based on cutting-edge research. As well as compiling Haskell to fast native code, it also provides a REPL-style tool called ghci.

Haskell-98 is a version of Haskell that was frozen around 1998, some 12 years after Haskell’s inception, to provide a stable version of the language and standard libraries that was suitable for education (including books and tutorials) and as a common target for all implementations of the language.

I won’t go into the history here, but recommend the paper "Being Lazy with Class" from 2007—by four of the main movers behind the language (Hudak, Hughes, Peyton Jones, Wadler)— as an excellent survey of Haskell’s genesis and development. For several of these articles, I will deliberately stick to Haskell-98 because of the standardization and because we won’t need any advanced features for a while.

For reference, the Haskell Platform provides an easy-to-install package of the main Haskell tools for standard platforms, including GHC and GHCi, Cabal (similar to Ruby’s Gem tool) and other build tools, plus many of the popular extra libraries (cf. Gems) already installed. Such additional libraries can be found on Hackage. Finally, there are some IDEs for Haskell, but I use vi.

Another option for Haskell-98 is the Hugs system: this is a smaller implementation and very useful for teaching: I used it in most of my classes, and still use it for basic programming.

The full code for this article is in a Github Gist. To play with the code, save it to a file with a .hs extension and run ghci on the file (or hugs, if you’re using that), then run various bits of code as you wish.

One Step at a Time

We’re looking to construct paths, and paths contain steps, so how about starting with the step operation? We want this to take a word and return all of the valid words that are reachable from the original word. For example, from “lead” we want to get the list

| ["bead","dead","head","mead","read","load","lend","lewd",
| "leaf","leak","leal","lean","leap","lear","leas"]

(the actual list depends on the dictionary you are using), but also to exclude non-words like “xead”.

Now, a key idea in functional programming is to split big problems into smaller ones, so how can we apply this here? We can guess that at some point we need to use the dictionary to filter out invalid words, but does the filtering need to be tied into the other parts of word generation? One common way to split problems is via the “generate and test” pattern, where one component suggests results and the other one discards invalid ones. (In my experience, undergrad programmers are experts in this pattern, although they tend to use it as a methodology—but that’s another story.) So, we can try having one component to generate a list of candidate words, and another to filter out the bad candidates.

A quick thought about types first: our basic step needs to have the type String -> [String], or from a word to a list of words. You might be itching to use more complex types after last month’s article (hurrah!) but let’s keep it simple for now. What do we have now? Let’s write it down.

| one_step :: String -> [String]
| one_step = filter is_valid_word . generate_candidates

Of course, this won’t compile because some code is missing (aka we have at least one failing test).

What does this code mean? The definition uses function composition (the dot), and says directly that the one_step operation is a composition (or combination) of generating candidates and filtering them. Recall that f . g is defined in the Haskell Prelude as \x -> f (g x), so the composition is a new function (the \x -> ... bit) that applies f to the result of g x. Programming-wise, we’re building a bigger transformation from two smaller ones.

You can read function compositions in any direction, whatever makes more sense to you. For example, right to left as a series of steps; i.e., generate the candidates then filter them; or left to right for a more “transformational” view: filtering the results from the candidate list. Notice that we don’t need to mention any parameters here: partly, we don’t need to (since the definition of function composition handles that for us), and partly we want to say that the big operation is a composition of two others and that’s all we need to say.

I’m going to leave word filtering for a bit, so I will just define the following and move on to the other missing code.

is_valid_word = error "Need to finish"

The Prelude function error :: String -> a takes a string and causes a run-time exception when the expression is evaluated. That is, if the program ever tried to use is_valid_word then there would be a run-time error whose message included the "Need to finish" string. This function is useful for stubbing out unfinished code, and for signalling serious problems at run time. (It is a bit like throw for exceptions, and indeed, some exception support is built into Haskell—though not often used because we have other, softer alternatives.)

Note the type of error: it takes a string and the result type is a but there’s absolutely no constraint on a, i.e. it really does mean anything. This is sensible, because it allows us to flag errors anywhere, for example we can use it where a list of Ints is expected because the type variable matches anything. Plus, if you think about it, there’s no sensible operation that could have this type so it kind of has to be this error functionality!

Telling It Like It Is

Before we move on, notice that I used the expression filter is_valid_word rather than some other single (yet to be defined) function name. There are some important points about language use here. Firstly, I’m making the positive choice that I want to use filtering on the candidate list, because I know what data structures are in play at the time, and have decided that filtering is going to be appropriate. So instead of a simple decomposition (into two stages) I’ve gone a bit further on the detail.

Secondly, I’m using the language to say this directly rather than making up a new function name and adding another definition of that name. Compare these expressions: map (\x -> 2 + x) [1..10] and map add_two [1..10]—which is clearer? My point here is that Haskell is flexible enough that quite often, the code itself is the clearest explanation of the programmer’s intent, and adding in extra definitions can make the code harder to follow; e.g., you would have to check elsewhere in the code to see what add_two actually does. Of course, there are cases where such new definitions can be justified—but Haskell gives you the choice. (You can be even more terse, like map (2+) [1..10] if that’s your thing.)

Thirdly, what does the expression filter is_valid_word actually mean? Conceptually, it’s taking the general idea of filtering a list with some predicate and then fixing the predicate to be a certain test: the result is an operation that picks out the valid words from a list. The important point here is that in Haskell, this kind of expression is meaningful and hence a key part of the coding style. Let’s consider a simpler example.

| foo = filter (\x -> reverse x == x)
| bar = foo ["ada", "fred", "bob"]

The first line above names a combination of filter and a test for a list being a palindrome. (Haskell Strings are a list of characters—though this test for palindromes will work with a list of anything that has an equality test.) The combination can then be used with a list of words, as in the second line.

What’s the type of foo? Well, filter :: (a -> Bool) -> [a] -> [a]; i.e., it takes a predicate (takes some a value, returns a Bool) and a list of such a values and returns a list of the same. For the type of \x -> reverse x == x we have to do some type inference, but it comes out as Eq a => [a] -> Bool, i.e. testing a list of a values as long as we can do equality tests on a values themselves. Putting these together— which means matching the first parameter of filter with the predicate—we get filter (\x -> reverse x == x) :: Eq a => [[a]] -> [[a]], hence converting a list of list of a values into a similar list (assuming equality is known). A nested list of something might be a bit abstract if you are new to it, but it’s fine to think concrete examples, so in the context of bar it is going to take and return a list of strings.

Some people like to use the word “currying” at this point. I don’t—I think it’s a bit of a misleading distraction that adds little. Conceptually (and theoretically; i.e., the lambda calculus), all functions in Haskell take one argument at a time, and either return a new function or a concrete value, and it’s important to understand this. How filter behaved above is a direct consequence of this.

Pragmatically, we often define and use multi-argument functions as if they were just like their equivalents in (say) Ruby, but underneath, Haskell is still using the above mechanism. The compilers will optimize such multi-argument functions so they behave efficiently, so it makes little difference to actual performance. The key point is: we really don’t have to worry about it. Enjoy the flexibility instead!

Generating Candidates

Next, the operation that generates potential words for later filtering. Type-wise, we want generate_candidates :: String -> [String], so from a word we get all possible next steps. Is there a sensible possibility to make it polymorphic? It is always worth asking this, or else keeping the question in mind while coding. (There’s also a chance that something like this already exists in a library, though this is a bit “niche” and so it is unlikely. The Hoogle tool provides specialized search facilities over many Haskell libraries and so can help you check this.)

You need to know a bit about Strings first. Haskell strings are simple: just lists of characters, and these are lists in the Lisp sense—a list is empty or it is an element cons’d onto the front of a list. This means we can use all of the list functionality on strings, including map, filter, and the sugared versions of these known as list comprehensions.

Where do we start? Always good to start with some concrete examples, especially if the operation doesn’t seem obvious. From generate_candidates "" we expect no candidates, since there’s no way to change a single character in an empty string. From generate_candidates "a" we expect ["b", "c", ... "z"] because we change the character to every other character except "a". From generate_candidates "ba" we expect ["aa", "ca", "da", ... "za", "bb", "bc", ... "bz" ]—which is the list from changing the first character plus the list from changing the second character. We can encode these as test cases and there are several ways to do this—but I won’t do this now (that’s another article).

There’s a bit of a pattern here (which we should look to exploit in the code), but it’s not obviously a map or a filter or a fold, so the functional programmer’s usual next tactic is to start thinking about the main cases of the input. This means thinking about (a) the empty list case and (b) the cons case.

One benefit of thinking via patterns is that we can think about the cases independently, and looking at our examples above, we’ve already done the first case (there are no candidates) so let’s fill it in. This leaves:

| generate_candidates []
| = []
| generate_candidates (c:cs)
| = error "don't know"

The cons case is highly likely to involve recursion somewhere, and the trick of writing recursive code is to think about possible recursive calls and what they give you, and from the results how to construct what you actually want. In this case, we can call generate_candidates on any other string, but it’s likely to be the tail of the input (or maybe a substring of it). Let’s guess a call to generate_candidates cs (to produce all candidates from the tail string) and see where it gets us, specifically thinking about how we can use c, cs and the result from generate_candidates cs to build the result.

Let’s also think about the concrete examples for "ba" and "a" from above. The latter will be the result from the recursive call when processing "ba", so can we do something to ["b", "c", ... "z"] to get (part of) the overall result? Well, if we put character b at the front of each of the strings, we get the last part of the result list. Let’s fill this in.

| generate_candidates []
| = []
| generate_candidates (c:cs)
| = error "don't know"
| ++ [ c : xs | xs <- generate_candidates cs ]

Syntax [ expr | pattern <- list ] indicates a “list comprehension”, also seen in CoffeeScript, Python, certain branches of set theory.... It is a very convenient shorthand for combinations of maps and filters on lists and translates to a combination of map, filter and list concatenation. The code above produces a new list by looping through the elements produced by the recursive call and sticking head character c on the front of each—it’s a map in other words.

The first part of the result is not too hard either: it’s the result of putting any letter except for c at the front of the list tail cs. We can use a list comprehension here too, with a filtering step that skips the original character.

| generate_candidates []
| = []
| generate_candidates (c:cs)
| = [ x : cs | x <- ['a'..'z'], x /= c ] -- new at front
| ++ [ c : xs | xs <- generate_candidates cs ] -- old at front

Observe that when we’re dealing with the a one-character string, the recursive call will return an empty list, and mapping over it also produces an empty list—which is safe to append to the rest of the result. In short, we don’t have to handle this situation explicitly, it just naturally slots into place.

Is This Code OK?

We can test generate_candidates on the concrete examples and confirm that we get the expected outcome. Question for you: do we also need to test some more? It’s up for debate, and I don’t really have a definitive answer. You could nail it with dependent types, but pragmatically, is that overkill?

Also pause a while to consider whether the code makes sense, and whether it gives a clear enough view of how this part of the program works. We’ve reached this version of the code by a few careful steps of reasoning, filling in pieces at a time, and we did understand each step. Are we therefore confident that the code is correct, with or without testing? Is confidence alone enough? On the other hand, how can we be confident that our tests are sufficient?

What about alternative coding approaches though? Specifically, what would an imperative or OO programmer do? Would we be happier with these versions? One possibility is an outer loop on the string position and an inner loop on the replacement letters, generating a new candidate word on each iteration. Here’s a version of the code that works along similar principles.

| generate_v2 w = [ before ++ d : tail after
| | (before, after) <- all_splits_of w
| , not (null after)
| , d <- ['a' .. 'z']
| , d /= head after ]

| all_splits_of :: [a] -> [([a], [a])]
| all_splits_of w = zip (inits w) (tails w)

The all_splits_of function returns all ways of splitting a list into two while keeping the original element order; e.g., all_splits_of "lead" will give [("","lead"),("l","ead"),("le","ad"),("lea","d"),("lead","")]. We then loop over this list, replacing the head of the second part with a different character and rebuilding the string (except when the second part is empty). Is this clearer? Or can you find another version that does make more sense? TMTOWTDI.

It’s worth noting that this version touches on recent FP research on views: the idea is that we choose a view of the data that simplifies the code, rather than always working with a particular physical representation. (It has some relationship with the concept of views in databases.) So, we view a list as the join of two lists, and then loop through the various ways of splitting the list to get our answer. The FP work in views started with Wadler, and has been expanded significantly by McBride in the context of dependently typed programming (e.g. in Epigram).

There’s a strong flavor of using types to provide almost a DSL that makes the problem easier to solve. It’s an important idea—we’ll come back to it in later articles.

Dictionary Filtering

We’ll do this bit by loading a list of words into a hash-like structure and then testing whether a word is present. Here’s the code. It’s not a key detail here so I won’t explain it much.

| -- import lines should go at the top
| import Data.Set(Set, fromDistinctAscList, member)
| import System.IO.Unsafe(unsafePerformIO)
| dict = fromDistinctAscList
| $ lines
| $ unsafePerformIO (readFile "fours.txt")
| is_valid_word w = member w dict

The above loads a list of words from a file (which contains just four-letter words), splits the file into lines and then builds a lookup table from it. I’m using Haskell’s Set library, which uses efficient binary trees. The implementation isn’t important, as long as it gives reasonable performance. We can always switch to hash-based tables later if performance here ever becomes an issue. The key detail is that we can test word validity by testing membership of the set, as shown in the new definition of is_valid_word.

Syntactic detail: the $ operator is a neat trick to save writing too many right-nested parentheses, i.e. instead of f (g (h x)) one can write f $ g $ h x. You can think of $ as a kind of pipeline symbol, similar to how function composition is sometimes used, though it’s not building new functions or anything freaky. Its definition is f $ x = f x (boring) and the magic works entirely through the symbol being declared as a right associative operator. In contrast, division is declared as left associative; e.g., 1.0 / 2.0 / 3.0 is equivalent to (1.0 / 2.0) / 3.0 rather than 1.0 / (2.0 / 3.0). So this $ is just a useful bit of shorthand.

What’s that unsafe doing? It’s a Haskell programmer cutting a corner, basically doing some unofficial IO (the file read) at an arbitrary point in the code and turning the dictionary into a global variable. (What’s that sound? A fairy dying? No.) Normally, we should be careful about ordering IO actions so we don’t try to read before writing, etc., but this idiom is kind of excusable since the dictionary is used as a constant. (We’ll talk monads and IO at a later date. Bet you can’t wait.)

Breadth-first Searching

We can call one_step "lead" to get a list of next steps, and call one_step on any of the new words and so on. But, we’re after the shortest path between two words, and so we need a controlled way of exploring how steps are related in order to find such a path. The obvious thing is to try all one-step paths, then all two-step paths, then three, etc.

This kind of process is called a “breadth-first search” (BFS). I’ll show you a version of BFS that is phrased in terms of exploring a “state space.” This framework also makes it easier to experiment with other kinds of searching, like best-first search. The parent-to-list-of-children relationship suggests a tree, so let’s program it this way. (More generally, it could be a graph too, but let’s keep it simple for now.) Firstly, we need a type. Haskell’s standard library contains a module Data.Tree that provides a suitable type and some useful related functionality.

| -- contained in the Data.Tree module
| data Tree a
| = Node { rootLabel :: a, -- label value
| subForest :: Forest a -- zero or more child trees
| }
| type Forest a = [Tree a]

So this is a tree with only one kind of node, and the node holds a value or label plus a list of zero or more child trees. The line type Forest a = [Tree a] defines a type synonym, providing a possibly more meaningful name for some type expression; i.e., a forest is a list of trees. The tree is (parametrically) polymorphic, of course. Concrete values look like this:

| eg1 = Node "foo" [Node "bar" []]
| eg2 = Node True [Node False [Node True []], Node True []]

The library contains drawTree :: Tree String -> String, which shows a simple text picture of the tree, so we can run putStr $ drawTree eg1 right away. How do we convert eg2? Well, we want to convert all of the Boolean values to strings, without changing the tree structure, and this sounds like a mapping operation. To cut a long story short, the Tree library implements the Functor interface too, which allows use of the overloaded fmap function for mapping over container types (like lists or trees), hence we can call putStr $ drawTree $ fmap show eg2.

Next, we’ll create the state space as a tree, where each node contains a state plus the trees that are reachable from that state. Notice the type first and what it describes: from a state-generating function and an initial state, we can produce the tree. It’s polymorphic too, because the tree-building process doesn’t care what’s in the tree. The implementation is straightforward: start a new tree at the current state and then collect the state space trees produced by all of the children. When a state has no children, there’s nothing to recurse on, hence no subtrees—just an empty list in the node.

| import Data.Tree -- put at top of file
| state_tree :: (s -> [s]) -> s -> Tree s
| state_tree children_of state
| = Node state [ state_tree children_of s | s <- children_of state ]

Now, you wouldn’t run this code directly in a conventional setting, but it’s fine in a lazy language because we’ll only need to generate enough of the tree to satisfy what the caller code requires—even if the tree’s depth was not finite. (If a state generated huge numbers of children, that would be an issue—but it’s an issue for other approaches too....)

Still, if we tried drawTree on an infinite tree, it would just keep on going or maybe run out of memory eventually. Let’s define another function to help us get sensible output: prune n t returns the structure from t down to a depth of n. There are two main cases, a depth of zero (or below) and a positive depth. When we hit zero, then truncate the tree by dropping its children. Otherwise, build a new tree based on the pruned child trees.

| prune :: Int -> Tree a -> Tree a
| prune d (Node x cs)
| | d <= 0 = Node x []
| | otherwise = Node x [ prune (d - 1) c | c <- cs ]

With this, code like putStr $ drawTree $ fmap show $ prune 3 $ state_tree (\s -> [s+1, s+1]) 0 now generates something useful. (Nothing significant here—it’s just a test value. The state generator here just says, from each state—which happens to be a number—it has two child states of that number with one added, hence it generates a tree that shows the depth at each level and has a fan-out of two children at each step.)

Now for BFS, we need to go through the state tree in breadth-first order. To keep things general, i.e., free from any application-specific details, we’re going to write a traversal function (to visit all of the states in order) and later filter the resulting state list for goal states. The traversal function will have the type bft :: Tree a -> [a]. It’s a bit trickier, but the technique here is to get a second function (here called bft_) to handle a list of trees at a time, then the main function calls it with the original tree in a singleton list.

| bft :: Tree a -> [a]
| bft t = bft_ [t]
| bft_ :: [Tree a] -> [a]
| bft_ trees = [ x | Node x _ <- trees ]
| ++ bft_ (concat $ map subForest trees)

You can think of bft_ as taking the next list of trees, skimming off the root values of the trees, and adding on the result of traversing the various child trees. The child traversal works by taking all of the children, flattening the lists of children to a flat list, and then running bft_ on this new list. If it helps, draw the picture and check how the code mirrors an informal level-by-level sweep.

The last step is to identify when we have found “goal” states—states that solve the required problem. We can do this by passing in a predicate of type a -> Bool and using it when filtering the output of bft. Putting this all together, we get the following.

| breadth_first_search :: (s -> Bool) -- goal test
| -> (s -> [s]) -- state generator
| -> s -- initial state
| -> [s] -- solutions out
| breadth_first_search is_goal children_of
| = filter is_goal
| . bft
| . state_tree children_of

To recap: we build the state tree, then do a breadth-first traversal of it to get a list of states to try, then return the ones that correspond to solved goals. Now compare this to implementations in your favorite language. More modular, no? And more reusable?

Exercise for the reader: write the code to do depth-first traversal, then generalize the search function to allow the search strategy to be supplied as a new argument.

Using the Search

Let’s plug the word chain code into the above and see what happens, e.g., defining the following and running word_chain "lead" "gold". You should see the word “gold” popping out every few seconds, which corresponds to each successful path being found. (There might be a short delay while the dictionary is loaded into memory on the first run.)

word_chain a b = breadth_first_search (\w -> w == b) one_step a

This confirms that paths exist, but we want to know the intermediate steps. The way to do this is to change the state type from a String to something that keeps track of where it’s been, i.e., a list of previous words. The following code lightly wraps up the basic code to maintain this list, testing against the head word in the list, and creating child states by expanding the head word and pre-pending the new child words to the previous path.

type Path = [String]

| goal_path :: String -> Path -> Bool
| goal_path target ws = target == head ws

| child_paths :: Path -> [Path]
| child_paths (w:ws)
| = [ s : w : ws | s <- one_step w, s `notElem` ws ]

| init_path :: String -> Path
| init_path w = [w]

| word_chain_path a b
| = breadth_first_search (goal_path b) child_paths
| $ init_path a

Running word_chain_path "ruby" "code" gets us a list of results, each a valid path, and the paths increase in length as the search enters deeper levels.

Note that it’s fairly usual to wrap such code up in a better abstraction. For example, the combination of goal test, state generator, and initial state do effectively define a search problem so it seems sensible to hold them in a record. It’s easy to adjust the search code to expect this as input. From this, we can recast the move to paths as converting a simple search problem object into a more complex one, e.g., convert_to_path_search :: SearchProblem s -> SearchProblem [s]. We could also encapsulate the path inside a new type so it’s not just a bare list any more.

Performance and Optimization

Is this code fast enough? Using the Hugs interpreter, it takes around a second or two to do the lead-gold example (both directions), and a few seconds more for the ruby-code example (also both directions). With the GHC compiler, this reduces to a fraction of a second—even without turning on the optimization options of the compiler. It’s probably fast enough.

GHC provides some good profiling tools to help diagnose and track performance issues. The following snippet is part of the standard time and space profile produced by running the ruby-to-code search 1000 times (taking around 10 seconds, so 0.01 seconds per search). This is without any compiler optimizations.

The profiler result indicates that 78% of the time was spent looking up words, and 14% of the time calculating the candidates. For memory, 84% of the total allocation was spent on the generated words. A similar pattern is seen when searching the reverse direction, albeit some 20 times slower(!)— though this could be a quirk of these words (we’d have to see this pattern on a bigger test set before concluding it was really a code problem).

| CALLS time space TIME SPACE
| state_tree 655000 0.8 4.3 95.9 93.7
| child_paths 58000 0.5 3.1 95.2 89.4
| one_step 0 2.3 1.7 94.6 86.3
| is_valid_word 5703000 77.9 0.0 77.9 0.0
| generate_candidates 286000 14.4 84.6 14.4 84.6

Now that we know this, if time or memory really were an issue then we could start analyzing the offending operations, maybe even fusing them together in some way to reduce overheads, or adding in cheaper word validity tests (like: reject words with no vowels). Until then, we can stick with the clear code.

Summing Up

We’ve not used many complex types, but types have still been useful in the process to describe what data we’re manipulating, and as a guide for how certain operations should behave. There’s room for a bit more type use in this Haskell-98 code, maybe wrapping up search problems as bundles, or perhaps wrapping valid words inside a new type to distinguish them from unchecked words.

What about dependent types? What details are we worried about, that we’d like the extra confidence for? I’ll let you think about this, but you might like to think about confirming that all candidate words are the same length, or conditions on the state generation to ensure that the states don’t inadvertently cause infinite loops or repeat work, or that the state space is finite (which would confirm that a tree-based approach is adequate rather than needing the full graph-based approach).

I’ve not said much about testing either. We can certainly add tests to double-check that code is doing what we expect, but we’ve also managed to split various concerns apart so it’s clear how each part works—indeed reflecting Hoare’s comment on “obviously no deficiencies” vs “no obvious deficiencies.”

When we code like this, it’s less of a “black box” situation—in the sense that testing does not say much about the code itself, just about its inputs and outputs, so it doesn’t really address code quality. So, what extra tests do we need?

Finally, I hope you have some appreciation of how we can use the language to keep the details simple and modular, and what a difference it makes to the final program. This isn’t just a happy coincidence—many functional programs do develop like this, and it really does help us work with much more complex programs. Even if you decide not to try Haskell, still be aware when you are programming of what is possible in the language, how to articulate your solutions, and think about the wider picture. Oh yeah, and keep practicing and having fun!

A Few Comments on Haskell Resources

We’re getting into more technical detail with Haskell here, but I’m not planning to write a tutorial on Haskell or repeat much of the good material already available. How do I expect you to fill in the gaps? Here are my suggestions and thoughts on relevant references:

My favorite introductory book is Graham Hutton’s Programming in Haskell. It’s a clear and crisp overview of Haskell-98 in around 180 pages, together with some significant examples (such as programming and optimizing the Countdown arithmetic problem). In my view, it is the K&R of Haskell—all the key details with little unnecessary filler. Experienced programmers from other languages should definitely take a look at it. (You can also find online videos of lectures by Erik Meijer—of LINQ fame amongst other things— based on Hutton’s book.)

A useful backup reference is A Gentle Introduction to Haskell by Hudak, Peterson, and Fasel. It’s available in a variety of formats online, and is a readable companion to the full Haskell Report. The language report itself defines the full technical details of the language, should you need it.

Real World Haskell by O’Sullivan, Stewart, and Goerzen from 2008 is a good overview of the language and some practical libraries, together with several significant programming examples. The content is available free online but also published in book form by O’Reilly. This book is notable for the way it mobilized the Haskell community to help: people were invited to comment on working drafts, via a web site allowing comments at the paragraph level, and the final book took many of these comments into account.

The book is pretty comprehensive in its coverage and contains many good programming examples, so is definitely worth a read when you are ready, but beware that some libraries have developed significantly since 2008 so many better alternatives exist now. A particular case is programming for web applications: there are now several strong Haskell-based frameworks such as Yesod, Snap, and HAppStack.

My main criticism is that it tries to be too many things to too many people, and doesn’t always pull this off. (It would be interesting if the next edition could separate the original book into two or three smaller books. This could make library updates easier to manage too.) For example, there’s around 100 pages of introductory material before the real programming starts—not the most exciting start, and Hutton’s 2007 book already covers most of this. Plus (for me), it doesn’t really say enough about the pragmatic aspects and wider picture.

Some people may like Learn You a Haskell. This book (with a free Html version online) has been likened in style to Why the Lucky Stiff's Ruby Guide. Some of the explanations are good, especially for a different perspective from the standard, though the author’s approach can be wearing after a while.

Finally, the main Haskell web site has many links to other useful resources.

So, many good references—but as I mentioned in an earlier article, I think there’s still a gap in the market for a more pragmatic approach, hence my reason for attempting something in these articles. I’d be very grateful for suggestions of what else to cover, and for any feedback, so please join in the conversation in the PragPub forums!

Dr. Paul Callaghan rides a big, fast motorbike, but his motorbike has no chain—it has a drive shaft. So, no messy cleaning, oiling, weekly checks, regular maintenance, and no worn sprockets. Neither will his chain fall off. He prefers his programming languages to be similarly hassle-free.

Bits of his bio can be seen on earlier articles. Paul also flies big traction kites and can often be seen being dragged around inelegantly on the beaches of North-east England, much to the amusement of his kids. He blogs at free-variable.org.

Send the author your feedback or discuss the article in the magazine forum.

Tales from the Ops Side

Synchronized Drowning

by Michael Nygard

No one designed this failure mode in, but no one designed it out either.

Several years ago, I worked for a company that offered 24x7 operations for websites that we didn’t create. As crazy as it sounds, we would not only support applications and systems that our clients built but also offer uptime and performance guarantees. During that time, I got what you could call a “crash course” in operations and in what it meant to build resilient systems. These systems taught me how well our typical applications were prepared to survive the harsh rigors of production. The answer was, “Not well at all.”

In this series, I relate some incidents from that time. Names have been changed to protect the parties involved, but the essential details and interactions are all accurate. You may find these vignettes entertaining or enlightening, or you may shake your head at how unprepared we all were. As you read, please bear Kerth’s Prime Directive in mind. “Regardless of what we discover, we understand and truly believe that everyone did the best job they could, given what they knew at the time, their skills and abilities, the resources available, and the situation at hand.” Also, it’s no fun to tell stories about times when everything went right!

Spot the Blocking Call

Can you find the blocking call in the following code?

| String key = (String)request.getParameter(PARAM_ITEM_SKU);
| Availability avl = globalObjectCache.get(key);

You might suspect that globalObjectCache is a likely place to find some synchronization. You would be correct, but the point is that nothing in the calling code tells you that one of these calls is blocking and the other is not. In fact, the interface that globalObjectCache implemented didn’t say anything about synchronization either.

In Java, it is possible for a subclass to declare a method synchronized that is unsynchronized in its superclass or interface definition. Object-oriented purists will tell you that this violates the Liskov Substitution Principle. They are correct. (For more on the Liskov Substitution Principle, see the end of this article.)

You cannot transparently replace an instance of the superclass with the synchronized subclass. This might seem like nit-picking, but it can be vitally important.

The basic implementation of the GlobalObjectCache interface is a relatively straightforward object registry:

| public synchronized Object get(String id) {
| Object obj = items.get(id);
| if(obj == null) {
| obj = create(id);
| items.put(id, obj); }
| return obj; }

You should hear mental alarm bells when you see the synchronized keyword on a method. While one thread is executing this method, any other callers of the method will be blocked. In this case, synchronizing the method is the right thing to do.

(Some of you Java programmers might have seen an idiom called the double-checked lock that is meant to avoid synchronizing the whole method. Unfortunately, it just doesn’t work. See this article for a complete rundown on why it doesn’t work and why all the attempts to fix the pattern also don’t work.)

This method executes quickly, and even if there is some contention between threads trying to get into the method, they should all be served fairly promptly. (A word of caution, however. GlobalObjectCache could easily become a capacity constraint if every transaction uses it heavily. See Antipattern 9.1, Resource Pool Contention, on page 176 of my book Release It!: Design and Deploy Production-Ready Software for an example of the effect that blocked requests have on throughput.)

Part of the system had to check the in-store availability of items by making expensive inventory-availability queries to a remote system. These external calls took a few seconds to execute. The results were known to be valid for at least fifteen minutes because of the way the inventory system worked. Since nearly 25% of the inventory lookups were on the week’s “hot items” and there could be as many as 4,000 (worst case) concurrent requests against the undersized, overworking inventory system, the developer decided to cache the resulting Availability object.

The developer decided that the right metaphor was a read-through cache. On a hit, it would return the cached object. On a miss, it would do the query, cache the result, and then return it. Following good object orientation principles, the developer decided to create an extension of GlobalObjectCache, overriding the create( ) method to make the remote call. It was a textbook design. The new RemoteAvailabilityCache was a cache proxy, as described on pages 111–112 of Pattern Languages of Program Design 2. It even had a time stamp on the cached entries so they could be expired when the data became too stale. This was an elegant design, but it wasn’t enough.

The problem with this design had nothing to do with the functional behavior. Functionally, RemoteAvailabilityCache was a nice piece of work. In times of stress, however, it had a nasty failure mode. The inventory system was undersized (see Antipattern 4.8, Unbalanced Capacities, on page 96 of Release It!), so when the front end got busy, the back end would be flooded with requests. Eventually, it crashed. At that point, any thread calling RemoteAvailabilityCache.get() would block, because one single thread was inside the create() call, waiting for a response that would never come. There they sit, Estragon and Vladimir, waiting endlessly for Godot.

This example shows how these antipatterns interact perniciously to accelerate the growth of cracks. The conditions for failure were created by the blocking threads and unbalanced capacities. The lack of timeouts in the integration points caused the failure in one layer to become a cascading failure. Ultimately, this combination of forces brought down the entire site.

Obviously, the business sponsors would laugh if you asked them, “Should the site crash if it can’t check availability for in-store pickup?”

If you asked the architects or developers, “Will the site crash if it can’t check availability?” they would assert that it would not. Even the developer of RemoteAvailabilityCache would not expect the site to hang if the inventory system stopped responding. No one designed this failure mode into the combined system, but no one designed it out either.

Synchronization and the Liskov Substitution Principle

I mentioned the Liskov Substitution Principle, so maybe I should explain what that is.

In object theory, the Liskov Substitution Principle (see “Family Values: A Behavioral Notion of Subtyping” states that any property that is true about objects of a type T should also be true for objects of any subtype of T. In other words, a method without side effects in a base class should also be free of side effects in derived classes. A method that throws the exception E in base classes should throw only exceptions of type E (or subtypes of E) in derived classes.

Java violates that principle in the case of allowing a subclass to declare a method synchronized that is unsynchronized in its superclass or interface definition. Java does not allow other declared violations of the substitution principle. It is not clear whether the ability to add synchronization in a subclass was a deliberate weakening of Liskov or whether it was just an oversight.

Michael is a veteran software developer and architect. His background is either “well-rounded” or “checkered” depending on how charitable you'd like to be. He has worked in Operations (including for a “Top Ten” internet retailer), sales engineering, and as a technology manager and executive.

In 2007, Michael wrote Release It! to bring awareness of operational concerns to the software development community. This early influence in the DevOps movement showed developers how to write systems that survive the real world after QA.

Send the authors your feedback or discuss the article in the magazine forum.

It’s Not About the Unit Tests

Learning from iOS Developers

by Jonathan Rasmusson

iOS developers generally don’t unit test. So why then do they as a community seem to enjoy a reputation for quality?

No unit tests. No continuous integration. No TDD.

That pretty much summarizes my last project. It was my first paying iOS gig, and not only did we not apply these cherished practices, we shipped a high quality product.

This really bugged me.

I had always thought unit tests were essential. But this experience with iOS seemed to challenge some deeply cherished assumptions I had developed over the years about writing software, and led me to ask myself some very uncomfortable questions.

Was I regressing in my development practices?

Were unit tests not essential?

Was there something different about iOS development?

And how did the iOS community ship quality products without unit tests at their core?

These questions kept me up at night, and led to the soul-searching I’m sharing in this article.

Ten years ago I used to debate people on the merits of unit testing. Not any more. Unit testing has become such a common practice that you’d struggle to find a modern development platform that doesn’t have some sort of automated testing framework.

And why not? The benefits are obvious. You can release, change, and refactor your code with confidence. You save a ton on regression testing. And the feeling of security that comes from knowing you have a suite of automated unit tests backing your every change is undeniable.

So imagine my surprise when I entered a community responsible for some of the world’s most loved mobile applications, only to discover that they don’t unit test. Even more deeply disturbing, they seem to be getting away with it!

What’s Different about iOS?

While I won’t say developing apps on iOS is easier, there are definitely a few things that iOS developers have going for them.

1. Smaller screen size.

You can’t fit a lot on a mobile phone screen—there just isn’t a lot of room. The apps also tend to be smaller (many don’t even have a backend). This, when combined with a culture of minimalism, dramatically simplifies things in terms of code and data. There is simply less of both.

2. No legacy.

Mobile apps are so new, iOS developers typically aren’t burdened with 100,000 lines of legacy code the way enterprise developers sometimes are. This lets them start from scratch unencumbered.

3. One language.

You can build an iOS application knowing only one language: Objective-C. The typical web developers needs no fewer than four or five languages to do anything other than static HTML.

4. A mature platform.

A lot of the heavy lifting is done for you in iOS. If you need to do something with photos, music, or Facebook, it’s there. You just plug in.

5. Very visual.

This was probably the biggest difference for me coming from the enterprise. Instead of spending days wading through layers of architecture (mocking and unit testing every step of the way), iOS developers have almost no layers of architecture. They spend almost all their time at the UI layer.

That means the nature of the code they write is often visual. The only way to see if it works is to fire up the simulator and try it out.

As interesting as these differences are, however, they still don’t tell the whole story. If they did, every mobile platform would enjoy this higher level of quality. Nope, there’s something else going on. Something bigger.

Who Cares?

When you do something for a long time, it’s easy to forget what people in your field once did without.

Architects used to work with slide rules.

Seafarers used to navigate by the stars.

Artists used to work solely with their bare hands.

Programmers used to program without unit tests (often at a much higher quality they you see today).

And yet in all these fields, practitioners were able to achieve what we today, with all our modern tools, would admit was a high level of quality in their work. So how did they do it? What was their secret?

They cared.

These people simply cared more about their craft, and what they were doing, than their contemporaries. They “out cared” the competition. And that is what I see in the iOS community.

They care more about the art.

They care a lot about the exact wording and spacing of text on buttons.

They care a lot about speed and performance.

And they care a ton about affordances (like remembering where in the scroll list a user was when they put the application in the background).

Apple works very hard to make sure every developer in their ecosystem cares, and they give them the tools so they have no excuse not to.

They walk them painstakingly through the importance of creating beautiful art.

They share (and enforce) human interface guidelines for mobile application development.

They curate and block apps that don’t meet certain quality standards.

And their former CEO was known for calling people up in the middle of the night to tweak a color or a logo.

It’s in the community’s DNA.

These guys care. They care like artists care. And—I’m just citing my own experience here—the same can’t be said for other platforms I have been a part of.

What Does This Have to Do with Unit Tests?

Absolutely nothing. And that’s my point.

unit tests != quality

What leads to quality is something much bigger—more than a collection of software engineering techniques or a collection of practices.

When I entered this community I was under the false impression that if you didn’t write software the way I did, you must be doing it wrong.

Instead I discovered a community that cared more about quality than I did, and I learned that I still had a lot to learn about crafting a quality experience.

That’s what this whole things has taught me. It’s not about the practices. It’s about the spirit and intent behind them, and how they are applied. Used when applicable. Quickly abandoned when not.

Are unit tests an invaluable tool for writing great software? Hell yes.

Am I going to produce a poor product if I can’t unit test? Hell no.

And that is what this experience taught me. I need to be more than a collection of practices.

To keep growing sometimes we need to challenge our most cherished assumptions. It doesn’t always feel good, but that’s how we grow, gain experience, and turn knowledge into wisdom.

The second you think you’ve got it all figured out, you are dead.

If you want to see how far down the rabbit hole this whole discussion on quality can go, I suggest picking up a copy of Zen and the Art of Motorcycle Maintenance. It’s not an easy read. But it may change your life.

Oh yeah, and keep unit testing.

Jonathan Rasmusson is the author of The Agile Samurai. As an experienced entrepreneur and former agile coach for ThoughtWorks, Jonathan has consulted internationally, helping others find better ways to work and play together. When not coaching his sons’ hockey teams or cycling to work in the throes of a Canadian winter, Jonathan can be found sharing his experiences with agile delivery methods at his blog, The Agile Warrior. For more information on the Agile Inception Deck check out The Agile Samurai.

Send the author your feedback or discuss the article in the magazine forum.

Threads

Philippe Kahn and Turbo Pascal

by Michael Swaine

The flamboyant entrepreneur behind a legendary software product find himself a beneficiary of Apple’s Map snafu.

Paul Freiberger and I are currently writing the third edition of Fire in the Valley, our history of the personal computer—to be published by The Pragmatic Bookshelf, naturally. As we go back over the material, we keep finding threads that run through the whole narrative. I am sharing some of these as brief history articles here in PragPub.

This time I want to recall the role of flamboyant entrepreneur Philippe Kahn and his company Borland International in the history of the personal computer.

The Crazy Frenchman

When I was hired as editor-in-chief of Dr. Dobb’s Journal, just about the first thing the editorial staff—Renny Wiggins and Randy Sutherland—did was to haul me down to Scotts Valley to see this crazy Frenchman who had just brought out a Pascal compiler that was being touted as the best thing since sliced bread. (That figure of speech was a lot fresher back then.)

This was early 1984. IBM had recently entered what had been largely a hobbyist market and “legitimized” the heck out of it. Personal computer makers who had been defining this young industry were scrambling to adapt to IBM’s presence. Language vendor Microsoft had become an operating system supplier, well on its way to supplanting CP/M on personal computers. A few months earlier Apple had told Superbowl viewers why 1984 wouldn’t be like 1984. There was a lot going on. But at DDJ we were obsessing on this Pascal compiler.

On that spring day we were interviewing the founder of the company that produced the compiler. A flamboyant Frenchman who played the saxophone and had majored in mathematics, Kahn had written software for Andre Truong’s pioneering Micral microcomputer and had worked under computer science legend Niklaus Wirth on a programming language Wirth had invented: Pascal. Coming to Silicon Valley on a tourist visa, Kahn soon found work making custom printer cables. That was a real job back then, and he was able to hire some employees and create a profitable business for himself making these cables for people. He also hung out his shingle as a consultant. When one of his clients went bankrupt, Kahn took the company’s name in payment, and that’s how he became President of Borland International.

Kahn’s new company had a product, something called MenuMaster, written by the brilliant Danish programmer Anders Heijlsberg for the CP/M operating system. It was a good product, but to be successful in the IBM-dominated market, MenuMaster needed to be ported to MS-DOS. And for that Kahn needed money, and to get money he needed a business plan. Tim Berry was working in the same office complex, and Kahn offered him a piece of Borland if he’d write a business plan.

Berry signed on and the company incorporated in May 1983, with Berry on the board of directors. He wrote the first ads and created the whimsical early image for the company, featuring a fictional grizzled prospector named Frank Borland.

What Kahn hadn’t included in the deal was a promise to actually follow the business plan. Berry was dismayed when he learned that no porting was getting done. Kahn told him the problem was a lack of software tools. What they needed, he said, was a Pascal compiler. So he had put Anders Heijlsberg to work writing one.

Turbo Pascal

Berry was horrified. While they were building their own tools, everyone in the world was bringing out products for the IBM PC. Borland would miss this huge window of opportunity. This strategy was crazy, Berry thought.

But in retrospect, it was brilliant. Heijlsberg finished the compiler in a few months, and here we were almost a year to the date after Borland incorporated, talking with Kahn about this new product. To us at DDJ, a compiler was a lot more interesting than something called MenuMaster.

It would turn out that this speed of development was due to the fact that Turbo Pascal was based on Heijlsberg’s own Blue Label Pascal compiler that he had written back in 1981 for the NasSys cassette-based operating system of the Nascom microcomputer. But the proof was in the review, and we anxiously awaited that. It was worth the wait. Words like “extraordinary” and “amazed” peppered the review. Turbo Pascal was a breakthrough product in many ways.

Turbo Pascal was astonishingly fast, and so compact that it easily ran in the limited memory of the PC. It was flat-out better than anything you could get on a mainframe or minicomputer. And it was exceptionally easy to use and well documented. The product, as it stood, was a tool anyone could learn programming with. It was a compiler, but felt like an interpreter. Compilation was lightning fast, and it produced reasonably fast code for the time. And the compiler took up 28k.

But Turbo Pascal’s importance extended beyond the product itself. Because Kahn broke all the rules in selling it. He priced it at $49.95 by mail order. At the time, Microsoft was selling a Pascal compiler for roughly ten times that price. And Kahn eliminated all the complexities of licensing then current in the market. Turbo Pascal had no copy protection and was sold under the famous “Book License”: “You must treat this software just like a book... [it] may be used by any number of people... may be freely moved from one computer location to another, so long as there is no possibility of it being used at one location while it’s being used at another.”

And, further terrifying Tim Berry, Kahn had scheduled ads to run in Byte magazine and elsewhere before even sharing with his board even the existence of the product. On an ad budget of zero, he bought $18,000 worth of advertising—take my word for it, that was substantial back then. He talked the ad salesperson from Byte into extending him credit mostly through the force of his personality, but also by calling friends in to sit in chairs and pretend to be employees in order to create the impression of a large, successful company.

Some perspective from Wikipedia: “In the early IBM PC market (1981–83) the major programming tool vendors all made compilers that worked in a similar fashion. For example, the Microsoft Pascal system consisted of two compiler passes and a final linking pass (which could take minutes on systems with only floppy disks for secondary storage). This process was the cumbersome product of the extremely limited resources of the early IBM PC models. Vendors of software development tools aimed their products at professional developers, and the price for these basic tools plus ancillary tools like profilers ran into the hundreds of dollars.”

In November, the ads appeared in Byte. That month, Borland brought in enough in sales to pay his advertising bill and buy twice as much advertising for the next month. Which is just what Kahn did. He kept putting all his chips back in the game, and in four months Borland was raking in a quarter million a month. It would go on to become one of the defining software tools companies of the young personal computer industry.

When it got big, Borland figured in a less appealing part of the industry’s development, too: litigation and patent fights. But by then Kahn had moved on to other challenges.

Philippe Kahn, Post-PC

And today?

It doesn’t surprise me at all that Kahn is still at it, and that he would instinctively gravitate to where the cool kids are: doing iOS development.

“As soon as Steve shared his vision for the iPhone we knew it was going to be be a success,” Kahn says, “because Steve got it. He realized that the iPhone was a [device] that everyone wanted to have in their hand and use to do most of what they do today.”

And one of the products Kahn’s current company makes may have just been given a golden opportunity. Lauren Goode at AllThingsD: “[W]hile Apple is improving Maps, there are other map apps available for iPhone users.... For the past several days, I’ve been finding my way with [alternatives, including] Fullpower’s MotionX GPS Drive.”

Yep, that’s his product. Talk about your window of opportunity.

Calendar

Author sightings, partner events, and other notable happenings.

Oct 3, StarWest, Anaheim, CA

Becoming a Kick-*** Test Manager

Johanna Rothman, author of Behind Closed Doors: Secrets of Great Management, Manage It! Your Guide to Modern, Pragmatic Project Management, and Manage Your Project Portfolio: Increase Your Capacity and Finish More Projects

Oct 5-7, NFJS, Minneapolis, MN

Talks on JVM languages, Concurrency, HTML5, JavaScript, and Testing

Venkat Subramaniam, the author of .NET Gotchas, the coauthor of 2007 Jolt Productivity Award winning Practices of an Agile Developer, the author of Programming Groovy, Programming Scala and Programming Concurrency on the JVM

Oct 6, School of Art and Design, University of Michigan, Ann Arbor, MI

Workshop: “Creative Coding for Mobile Devices”

Daniel Sauter

Oct 6, AgileEE, Kiev, Ukraine

Keynote

Henrik Kniberg, author of Lean from the Trenches

Oct 8, Design/Media Arts, University of California, Los Angeles, CA

Workshop: “Creative Coding for Mobile Devices”

Daniel Sauter

Oct 10, ChicagoAndroid.com and Google Technology User Group Meeting, Chicago, IL

“Wearable Android Computing”

Mike Riley, author of Programming Your Home

Oct 10-11, RiconSan Francisco, CA

TBA

Michael Bevilacqua-Linn

Oct 11, Boston Chapter IIBA, Wellesley, MA

“Agile Portfolio Planning: Managing Your Project Portfolio” and “Influence and Authority—Using Your Personal Power to Get Things Done”

Johanna Rothman, author of Behind Closed Doors: Secrets of Great Management, Manage It! Your Guide to Modern, Pragmatic Project Management, and Manage Your Project Portfolio: Increase Your Capacity and Finish More Projects

Oct 12, FabLab Shibuya, Tokyo, JP

Artist Talk and Workshop: “Creative Coding for Mobile Devices”

Daniel Sauter

Oct 14, Videotage New Media Art Collective, Hong Kong, HK

Artist Talk and Workshop: “Creative Coding for Mobile Devices”

Daniel Sauter

Oct 15-18, Spring2GX, Washington, D.C.

Talks on Groovy and JVM Languages Integration

Venkat Subramaniam, the author of .NET Gotchas, the coauthor of 2007 Jolt Productivity Award winning Practices of an Agile Developer, the author of Programming Groovy, Programming Scala and Programming Concurrency on the JVM

Oct 16, Nanyang Technological University, Singapore, SG

Artist Talk

Daniel Sauter

Oct 17–19, MacTech, Los Angeles, CA

“Less is More”

Daniel H Steinberg

Oct 18, Lasalle College, Singapore, SG

Artist Talk and Workshop: “Creative Coding for Mobile Devices”

Daniel Sauter

Oct 20, CAMP, Khar, Mumbai, IN

Artist Talk and Workshop: “Creative Coding for Mobile Devices”

Daniel Sauter

Oct 22, Heart of England Scrum User Group, Birmingham, UK

"Talk: Coaching Teams through Change"

Rachel Davies, co-author of Agile Coaching

Oct 23, AgileDCWashington, DC

“Test Abstraction: Keeping Your Test-Driven Tests Healthy”

Jeff Langr, co-author of Agile in a Flash

Oct 23, Digitale Klasse, University of the Arts, Berlin, DE

Artist Talk

Daniel Sauter

Oct 24, Lab for Electronic Arts and Performance, Berlin, DE

Artist Talk and Workshop: “Creative Coding for Mobile Devices”

Daniel Sauter

Oct 25–27, CocoaConf PDX, Portland, OR

“Modern Objective-C” and a second talk on iOS 6

Daniel H Steinberg

Oct. 25–27, QCon China, Hangzhou, China

Keynote and talk

Dave Thomas

Oct 25–27, CocoaConf,Portland, OR

“Core Audio in iOS 6,” “Mobile Movies with HTTP Live Streaming,” and “All-Day Core Audio Workshop”

Chris Adamson, co-author of iOS SDK Development

Nov 2-4, NFJS, Reston, VA

Talks on JVM languages, Concurrency, HTML5, JavaScript, and Testing

Venkat Subramaniam, the author of .NET Gotchas, the coauthor of 2007 Jolt Productivity Award winning Practices of an Agile Developer, the author of Programming Groovy, Programming Scala and Programming Concurrency on the JVM

Nov 3–4, Mobile Processing Conference, University of Illinois at Chicago, Chicago, IL

Artist Talk and Workshop: “Creative Coding for Mobile Devices” and Workshop: “Working with Android and Arduino”

Daniel Sauter

Nov 4–8, Amplifying Your Effectiveness Conference, Albuquerque, NM

Has Your Project Outgrown Its Training Wheels?, Replacing Management Myths, What's Your Number One Project?, Improve Your Social Networking Skills, Reinventing Yourself, Congruent Coaching, a full day workshop

Johanna Rothman, author of Behind Closed Doors: Secrets of Great Management, Manage It! Your Guide to Modern, Pragmatic Project Management, and Manage Your Project Portfolio: Increase Your Capacity and Finish More Projects

Nov 6, Øredev, Malmo, Sweden

Vim Masterclass

Drew Neil, author of Practical Vim

Nov 6–9, Pragmatic Studio, Denver, CO

“iOS Programming”

Daniel H Steinberg

Nov 6–9, Pragmatic Studio, Denver, CO

“iOS Programming”

Bill Dudney, author of Core Animation

Nov 7, Øredev, Malmo, Sweden

“Vim—precision editing at the speed of thought”

Drew Neil, author of Practical Vim

Nov 8–9, RubyWorld Conference, Matsue, Japan

Keynote

Dave Thomas

Nov 9-11, NFJS, Chicago, IL

Talks on JVM languages, Concurrency, HTML5, JavaScript, and Testing

Venkat Subramaniam, the author of .NET Gotchas, the coauthor of 2007 Jolt Productivity Award winning Practices of an Agile Developer, the author of Programming Groovy, Programming Scala and Programming Concurrency on the JVM

Nov 12, Devoxx, Antwerp, Belgium

“Intro to iOS 6 for Java Developers”

Daniel Steinberg

Nov 13, Bath Scrum User Group, Bath, UK

"Talk: Coaching teams through Change

Rachel Davies, co-author of Agile Coaching

Nov 16-18, NFJS, Denver, CO

Talks on JVM languages, Concurrency, HTML5, JavaScript, and Testing

Venkat Subramaniam, the author of .NET Gotchas, the coauthor of 2007 Jolt Productivity Award winning Practices of an Agile Developer, the author of Programming Groovy, Programming Scala and Programming Concurrency on the JVM

Nov 27-30, RichWeb Experience, Fort Lauderdale, FL

Talks and workshops on JavaScript, CoffeeScript, HTML5, Testing

Venkat Subramaniam, the author of .NET Gotchas, the coauthor of 2007 Jolt Productivity Award winning Practices of an Agile Developer, the author of Programming Groovy, Programming Scala and Programming Concurrency on the JVM

Nov 29–Dec 1, CocoaConf, Raleigh, NC

Keynote, “Less code, more fulfilling,” and “Storyboards—This time it’s personal”

Daniel Steinberg

Nov 29–Dec 1, Cocoa Conf, Raleigh NC

TBD

Bill Dudney, author of Core Animation

Nov 29–Dec 1, CocoaConf, Raleigh, NC

“Core Audio in iOS 6,” “Mobile Movies with HTTP Live Streaming,” and “All-Day Core Audio Workshop”

Chris Adamson, co-author of iOS SDK Development

O’Reilly Events

Upcoming events from our friends at O’Reilly.

Oct 1–2, Strata Conference, London, England

Strata Conference: “The O’Reilly Strata Conference in London will bring together the best minds in data to explore the opportunities made possible by the latest state-of-the-art big data tools and analytic approaches.”

Oct 2–4, Velocity Conference, London, England

Velocity Conference: “This October, hundreds of web ops and performance professionals will gather in London to share their ideas and expertise—and to discover the technical skills, tools, tips, tricks, and best practices they need to exceed the continually increasing expectations for a faster, stronger web.”

Oct 9, TOC Frankfurt, Frankfurt, Germany

TOC Frankfurt: “Tools of Change Frankfurt returns for a fourth year on Tuesday, 9 October 2012—the eve of the Frankfurt Book Fair (10–14 October)—gathering the best and brightest in our global publishing and technology community for a full day of intriguing keynotes, sessions, and networking.”

Oct 16–17, Strata Rx Conference, San Francisco, CA

Strata Rx Conference: “Strata Rx is the first conference to bring data science to the intractable and urgent issues confronting healthcare.”

Oct 20, Mini TOC Vancouver, Vancouver, B.C.

Mini TOC Vancouver: “While the focus at Mini TOC is on the intersection of technology and publishing—just like at the ‘big’ TOCs—at Mini TOC, the crowd is small, the atmosphere is intimate and informal, and all the emphasis is on attendees and presenters sharing the conversations.”

Oct 23–25, O’Reilly Strata Conference and Hadoop World, New York, NY

O’Reilly Strata Conference and Hadoop World: “Now in its second year in New York, the O’Reilly Strata Conference explores the changes brought to technology and business by big data, data science, and pervasive computing. This year, Strata has joined forces with Hadoop World to create the largest gathering of the Apache Hadoop community in the world.”

Nov 7, Mini TOC Charleston, Charleston, SC

Mini TOC Charleston is geared to librarians, large & small publishers, self-published authors, creative collectives, information hobbyists, journalists, historians, bloggers, and online experts seeking a better understanding of what ubiquitous content means for the future of commercial publishing.

Dec 4–5, Velocity China Conference, Beijing, China

Most dynamic website companies face the same challenge: pages must load fast, the infrastructure has to be able to expand, sites and services must be reliable, and you have to do it all in a timeframe the team can handle while keeping it within budget. Velocity is the best place for Web professionals to meet to exchange ideas and share best practices and lessons learned.

USENIX Events

What’s coming from our USENIX friends.

Oct 8–10, OSDI ’12, Hollywood, CA

10th USENIX Symposium on Operating Systems Design and Implementation: “The 10th OSDI seeks to present innovative, exciting research in computer systems. OSDI brings together professionals from academic and industrial backgrounds in what has become the premier forum for discussing the design, implementation, and implications of systems software.”

Dec 3–7, Middleware 2012, Montreal, Quebec, Canada

ACM/IFIP/USENIX 13th International Conference on Middleware: “a premier forum for the discussion of innovations and recent advances in the design, implementation, experimentation, deployment, and usage of middleware systems.”

Dec 9–14, LISA ’12, San Diego, CA

26th Large Installation System Administration Conference: “The annual LISA conference is the meeting place of choice for system and network administrators and engineers; it is the crossroads of Web operations, DevOps, enterprise computing, educational computing, and research computing.”

Other Happenings

Oct 4

The Free Software Foundation is 37.

Oct 4

Birthday of John Vincent Atanasoff, one of the inventors of the computer.

Oct 5

Linux is 21!

Oct 6

Adobe co-founder John Warnock is 72.

Oct 12

Birthday of Ole-Johan Dahl, co-creator of the Simula language and thus of object-oriented programming.

Oct 16

Mike Muuss, who invented Ping, was born on this date in 1958.

Oct 25

Peter Naur, the N in BNF, is 84.

Oct 28

Former software executive Bill Gates is 57.

Oct 29

On this date in 1969, ARPAnet first linked Doug Engelbart’s lab at SRI with Leonard Kleinrock’s at UCLA.

Oct 31

The traditional date for the leaking of confidential internal Microsoft documents outlining strategies for undermining open source software.

Nov 1

Mitch Kapor is 62.

Nov 8

Bill Joy is 58.

Nov 6

Jerry Yang is 44.

Nov 10

Bert Bos, co-creator of Cascading Style Sheets, is 49.

Nov 10

Richard Brodie, creator of Microsoft Word, is 52.

Nov 18

Pamela Kyle Crossley, historian and creator of SIMPLE, is 57.

Nov 19

Dries Buytaert, Drupal founder and lead developer, is 34.

Nov 22

Randall Schwartz is 51.

Nov 22

PHP creator Rasmus Lerdorf is 44.

Nov 22

And it’s Charles Simonyi’s wedding anniversary.

Dec 3

John Backus would have been 87.

Dec 4

Eric Raymond, aka ESR, is 43.

Dec 9

Grace Hopper’s 105th birthday.

Dec 10

Ada Lovelace’s 196th birthday.

Dec 10

Ada, the programming language, is 31 today.

Dec 16

John Bardeen and Walter Brattain created the first transistor on this day in 1947.

Dec 17

Ken Iverson, creator of APL, would have been 91 today.

Dec 17

Les Earnest, inventor of first spell checker and of the finger protocol, is 81.

Shady Illuminations

Cockaroaches

by John Shade

A cockroach festival, cybernetic cockroaches, the internet considered as a zombie cockroach, and Apple’s Map app flap.

The cockroaches are taking over.

I was going to write about Apple’s Map app flap this month. I was all set to rant about how replacing Google Maps with Apple’s Not Ready for Primetime substitute will bring about death and driver disorientation and Doonesbury derision. I think you can tell by the alliteration that it would have been a nifty column. I was going to tie in football refs and Mars Curiosity rover. Good stuff.

But then Tim Cook himself stepped up with the solution to the map mess and undercut my premise. Cook’s recipe is simple: Don’t use Apple Maps. It’s crap, we’re trying to fix it, and in the meantime, here are some workarounds so you can use Google Maps. Great. Thanks a lot, Tim. Problem solved. So I’m going to column plan B: cockroaches.

But first let me just say this: fanboy. There, I got that in. You’re not a serious journalist unless you use the word “fanboy” in every article that mentions Apple.

But back to the cockroaches. Or as Tony “Scarface” Montana prefers, cockaroaches.

They’re taking over. You knew it was going to happen eventually. And it is. Check Google Trends if you don’t believe me. Or try this search if you dare. They’re big in Nepal. And although Google Trends doesn’t know it yet, they’re really big in Madagascar.

A Kami-Kazi Flight to the Cockroach Festival

Cockroaches are survivors. They are the zombies of the creepy vermin set. They can survive nuclear war. They can survive decapitation. Cut off a cockroach’s head and it will go on functioning for days without a head. In fact, the head will go on living without the cockroach. It’s like you’ve created a second cockroach. But even though they’re almost impossible to kill, until now cockroaches have preferred to keep themselves hidden from humans. Staying out of the light. Waiting for their moment.

And it looks like their wait is over.

The first sign, for those of us manning the early warning system, was the Cockroach Festival in Santa Fe, Texas. Apparently October is Cockroach Month in Galveston County. I think they race the cockroaches. There was also mention of a barbecue. I’d skip that. For that matter, I’m not sure how you get to Santa Fe, Texas. There’s a heliport nearby named Kami-Kazi Airport, but I think I’d avoid that, too.

Anyway, I’m not on the Santa Fe, Texas Tourism Board. I couldn’t care less about their cockamamie festival. That story just happens to be the first one I spotted. But remember the lesson of Cockroach 101: There's never just one. When it comes to cockroaches, you’re either roach-free or you’re roach-infested.

So I flipped on the light. Oh. My. God.

Invasion of the Cybernetic Cockroaches

Researchers at North Carolina State University have worked out how to drive a cockroach by remote control. Sort of like a very slow, very low altitude drone. They’re using Madagascar hissing cockroaches because they are the very best cockroaches. Really big, measuring up to three inches long, exactly the length of an iPod Nano. Apple could use that in their advertising. Probably go over better than the Map app. More significantly, the Madagascar hissing cockroach is just a bit longer than an Arduino Diecimila microcontroller.

The researchers want to put these monster roaches to work as beasts of very small burden. Emergency first responder is their idea of a good job for their cybernetically controlled cockroaches. Strap audio equipment and a tiny camera to one’s back and it can be sent into earthquake rubble to locate survivors.

And to identify them. “Hold still and look into this cockroach,” would be the implicit message, “so your loved ones will know you’re alive.” Once the system’s in place it’ll be interesting for other academic researchers to study the effect on the mental health of someone pinned immobile under earthquake rubble who suddenly has a three-inch-long cockroach hissing in his face.

I’m sure the researchers are right and that these hideous cyborgs could be useful for that sort of thing. But what I see here is another cool techno-toy that everybody’s going to want. Aren’t you just itching to get your own cyber-roach? I’m sure they won’t be cheap, at least as cockroaches go, because of the add-ons. You’re going to want the motion control circuitry and video and audio at least, plus the Arduino board for cockroach programmability. And with that much investment in roach tech, you should probably plunk for a tracking chip and download the Tony Montana Where Is My Cockaroach? app.

Of course, as Tony Montana could tell us, these cybernetic cockaroaches will be easily adapted for crime. Now that burglars can use a Trojan designed by other helpful academic researchers to build a 3D map of the inside of your house, they can send a cyber-roach in to retrieve the front door key from your pants pocket. You can’t stop progress. Even if you cut off its head.

The Internet Considered as a Zombie Cockroach

You know why cockroaches can survive having their heads cut off? It’s because their brains aren’t all in their heads.

Cockroaches have distributed intelligence. They have ganglia running down the length of their bodies that are capable of managing a lot of the mental activities that cockroaches consider important. Or that North Carolina researchers want to control.

Cockroaches are not going to bleed to death from having their heads cut off, either. Their blood doesn’t circulate the way ours does. And they don’t breathe through their heads. All these functions are more distributed than in humans. Sound like anything? Right, it sounds like the internet. So the internet will probably survive the invasion of the zombie cybernetic cockroaches and the rise of the Jurassic cockroaches, even if we don’t. And since cockroaches and the internet have similar minds, they’ll probably link up eventually and become one disgusting and all-powerful being.

Oh, right. The Jurassic cockroaches. Another team of helpful academic researchers have reconstructed a prehistoric cockroach, a slippery step on the path to the Jurassication of the Roach. Technically, the Roach Nymph is an ancestor, sort of a proto-roach. But as we all know, prehistoric ancestors of any living creature are way bigger and scarier than their descendants. This was a structural revisiting of roach history, not a DNA reconstruction, but you know that’s only a matter of time.

Obviously, resistance is futile.

So if you, as I do, welcome our insect overlords and want to track their every thought and action, you’ll be happy to know that there’s an app for that.

John Shade was born under a cloud in Montreux, Switzerland, in 1962. Subsequent internment in a series of obscure institutions of ostensibly higher learning did nothing to brighten his outlook. Much like a cockroach, he has been hiding from the light ever since. Follow him on Twitter, send him your feedback, or discuss the article in the magazine forum.

But Wait, There’s More...

Coming Attractions

This may be the last page, but that doesn’t mean it’s the end of the conversation. Keep up with what’s going on in the Pragmatic universe by subscribing to our newsletter and drop by the Pub again next month for more Pragmatism. We’ll keep a seat warm and a mug chilled and a candle burning in the window.

Coming Soon in PragPub

Here’s what I want for Christmas: an article on Raspberry Pi. And I think I might just get it.

Recent Releases from the Bookshelf

Outsource It! is in beta, Practical Vim is in print. The iOS SDK Development beta has been updated to iOS 6, with print coming soon. The Definitive ANTLR 4 Reference is now in beta. And The Pragmatic Programmer is now available as a DRM-free ebook, all formats for one price.  

Right. But to really be in the know, you need to subscribe to our weekly newsletter. It’ll keep you in the loop, it’s a fun read, and it’s free. All you need to do is create an account on pragprog.com (email address and password is all it takes) and select the checkbox to receive newsletters.

While you’re waiting for the next issue of the newsletter or of PragPub to come out, you can follow us on twitter at @pragpub, @PragmaticAndy, or @pragdave. Or on Facebook at facebook.com/PragmaticBookshelf. Or email us at michael@pragprog.com.