Software is a tree

Maybe software is like a tree.

The applications, websites, games that people use are the leaves. They’re the important part of the tree, because they’re useful. They solve real problems and improve lives, they make money, they entertain.

The leaves are built upon the wood of the tree, branches and trunk: all the libraries and languages and operating systems and network infrastructure. Technologies upon technologies, upon which we build applications. They’re the important part of the tree because dozens to thousands of leaves depend on each piece of wood.

Which part of the software tree do you work on? Is it a leaf? Leaves need polished according to their purpose, monitored according to their criticality, grown according to users’ real needs. Is it the wood? The wood needs to be strong, very well-tested because it will be used in ways its authors did not imagine.

Ever find yourself in between, changing an internal library that isn’t tested and documented like a strong open-source library, but isn’t specific to one application either? I’ve struggled with code like this; we want to re-use it but when we write it we’re trying to serve a purpose – grow the leaf – so we don’t stop to write property tests, handle edge cases, make the API clear and flexible. This code falls in the uncanny valley between wood and leaf. I don’t like it.

Code that is reusable but not core to the business function is best shared. Use another library, publish your own, or else stagnate in the uncanny valley. Follow the mainstream, form a new main
stream, or get stuck in a backwater.

With a few days set aside to focus on it, we could move that shared code into the wood, and release it as open source. Make it public, then document, test, and design with care. When we graft our twig into the larger tree, it can take nourishment from the contributing community, and maybe help more leaves sprout.

If the code isn’t useful enough to release as even a tiny open-source library, then it isn’t worth re-using. Build it right into multiple leaves if multiple leaves need it. App code is open for modification, instead of the closed-for-modification-but-needs-modification of the shared internal library.

With care, ours can be a healthy tree: millions of shiny custom leaves attached to strong shared branches.

Property tests don’t have to be generative

Now and then, a property test can be easier than an example test. Today, Tanya and I benefited.

There’s this web service. It returns a whole tree of information, some of it useful and some of it is not.

{ “category”: “food”,
  “children: [ { “category” : “fruit”,
                  “children” : […LOTS MORE…],
                  “updatedAt” : “2014-06-30T16:22:36.440Z”,
                  “createdAt” : “2014-06-30T16:22:36.440Z”},
                 {“category” : “vegetables”,
                  “children” : […EVEN MORE…],
                  “updatedAt” : “2014-06-25T18:32:36.436Z”,
                  “createdAt” : “2014-06-25T18:32:36.436Z”}],
  “updatedAt” : “2014-06-15T16:32:36.550Z”,
  “createdAt” : “2014-03-05T08:12:46.440Z” }

The service is taking a while, mostly because it’s returning half a meg of data. Removing the useless fields will cut that in half.

Being good developers, we want to start with a failing test. An example test might start with inserting data in the database, perhaps after clearing the table out, so we can know what the service should return. That’s a lot of work, when I don’t really care what’s returned, as long as it doesn’t include those updatedAt and createdAt fields.

Currently when we test the function implementing this service, there’s some sample data lying around. If we write a property test instead of an example test, that data is good enough. As long as the service returns some data, and it’s something with children so we can check nested values, it’s good enough. I can test that: (actual code)

(deftest streamline-returned-tree
  (testing “boring fields are not returned”
    (let [result (method-under-test)]
      (is (seq (:children result))))))

This is not a generative test, because it doesn’t generate its own data, and it doesn’t run repeatedly. Yet it is a property test, because it’s asserting a property of the result. The test doesn’t say “expected equals actual.” Instead, it says “The result has children.”

This test passes, and now we can add the property of interest: that the map returned by method-under-test has no :createdAt or :updatedAt keys, at any level. We could find or write a recursive function to dig around in the maps and nested vectors of maps, but that same function would also be useful in the implementation. Duplicating that code in the test is no good.

One of the classic challenges of property testing is finding two different ways to do the same thing. Then we can make assertions without knowing the input. But… nobody said they have to be two smart ways of doing the same thing! I want to be sure there’s no “createdAt blah blah” in the output, so how about we write that nested map to a string and look for “createdAt” in that?

(deftest streamline-returned-tree
  (testing “boring fields are not returned”
    (let [result (method-under-test)
          result-string (pr-str result)]
      (is (seq (:children result)))
      (is (not (.contains result-string:createdAt“))))))

This gives us a failing test, and it was a heck of a lot easier to implement than an example test which hard-codes expected results. This test is specific about its purpose. As a bonus, it doesn’t use any strategy we’d ever consider using in the implementation. The print-it-to-a-string idea, which sounded stupid at first, expresses the intention of “we don’t want this stuff included.”

Property tests don’t have to be generative, and they don’t have to be clever. Sometimes it’s the dumb tests that work the best.

Bonus material:
the output of this failing test is

expected: (not (.contains result-string:createdAt“))
  actual: (not (not true))

This “not not true” actual result… yeah, not super useful. clojure-test’s “is” macro responds better to a comparison function than to nested calls. If I define a function not-contains, then I can get:

expected: (not-contains result-string “:createdAt“)
  actual: (not (not-contains 
                “{:children [{:createdAt \”yesterday\”, :category \”fruit\”}], :createdAt \”last week\”, :category \”food\”}” 

That’s a little more useful, since it shows what it’s comparing.

Repeating commands in bash: per line, per word, and xargs

In bash (the default shell on Mac), today we wanted to execute a command over each line of some output, separately. We wanted to grep (aka search) for some text in a file, then count the characters in each matching line. For future reference…

Perform a command repeatedly, once per line of input:

grep “themain.log | while read line; do echo $line | wc -c ; done

Here, grep searches the file for lines containing the search phrase, and each line is piped into the while loop, stored each time in variable line. Inside the loop, I used echo to print each line, in order to pipe it as input to word-count. The -c option says “print the number of characters in the input.” Processing each line separately like this prints a series of numbers; each is a count of characters in a line. (here’s my input file in case you want to try it)

      41      22      38      24      39      25      23      46      25

That’s good for a histogram, otherwise very boring. Bonus: print the number of characters and then the line, for added context:

grep “the” main.log | while read line; do echo $(echo $line | wc -c) $line ; done

Here, the $(…) construct says “execute this stuff in here and make its output be part of the command line.” My command line starts with another echo, and ends with $line, so that the number of characters becomes just part of the output. 

41 All the breath and the bloom of the year
22 In the bag of one bee
38 All the wonder and wealth of the mine
24 In the heart of one gem
39 In the core of one pearl all the shade
25 And the shine of the sea
23 And how far above them
46 Brightest truth, purest trust in the universe
25 In the kiss of one girl.

This while loop strategy contrasts with other ways of repeating a command at a bash prompt. If I wanted to count the characters in every word, I’d use for.

Perform a command repeatedly, once per whitespace-separated word of input:

for word in $(grep “the” main.log); do echo -n $word | wc -c; done

Here, I named the loop variable word. The $(…) construct executes the grep, and all the lines in main.log containing “the” become input to the for loop. This gets broken up at every whitespace character, so the loop variable is populated with each word. Then each word is printed by echo , and the -n option says “don’t put a newline at the end” (because echo does that by default); the output of echo  gets piped into word-count.
This prints a lot of numbers, which are character counts of each word. I can ask, what’s the longest word in the file?

for word in $(grep “the” main.log); do echo $(echo -n $word | wc -c) $word; done | sort -n | tail -1

Here, I’ve used the echo-within-echo trick again to print both the character count and the word. Then I took all the output of the for loop and sent it to sort. This puts it in numeric order, not alphabetical, because I passed it the -n flag. Finally, tail -1 suppresses everything but the 1 last line, which is last in numeric order, where the number is the character count, so I see only the longest word.

9 Brightest

If that’s scary, well, take a moment to appreciate the care modern programming language authors put into usability. Then reflect that this one line integrates six completely separate programs.

These loops, which provide one line of input to each command execution, contrast with executing a command repeatedly with different arguments. For that, it’s xargs.

Perform a command repeatedly, once per line, as an argument

Previously I’ve counted characters in piped input. Word-count can also take a filename as an argument, and then it counts the contents of the file. If what I have are filenames, I can pass them to word-count one at a time.

Count the characters in each of the three smallest files in the current directory, one at a time:

ls –Srp | grep -v ‘/$‘ | head -3 | xargs -I WORD wc -c WORD

Here,  ls gives me filenames, all the ones in my current directory — including directories, which word-count won’t like. The -p option says “print a / at the end of the name of each directory.” Then grep eliminates the directories from the list, because I told it to exclude (that’s the -v flag) lines that end in slash: in the regular expression ‘/$, the slash is itself (no special meaning) and $ means “end of the line.” Meanwhile, ls sorts the directories by size because I passed it S. Normally it sorts them biggest-first, but -r says “reverse that order.” Now the smallest files are first. That’s useful because head -3 lets only the first three of those lines through. In my world, the three smallest files are main.log, carrot2.txt, and carrot.txt.
Take those three names, and pipe them to xargs. The purpose of xargs is to take input and stick it on the end of a command line. But -I tells it to repeat the command for each line in the input, separately. And -I also gives xargs (essentially) a loop variable; -I WORD declares WORD as the loop variable, and its value gets substituted in the command.

In effect, this does:
wc -c main.log
wc -c carrot2.txt
wc -c carrot.txt

My output is:

      14 main.log      98 carrot2.txt     394 carrot.txt

This style contrasts with using xargs to execute a command once, with all of the piped input as arguments. Word-count can also accept a list of filenames in its arguments, and then it counts the characters in each. The previous task is then simpler:

ls –Srp | grep -v ‘/$‘ | head -3 | xargs wc -c

      14 main.log      98 carrot2.txt     394 carrot.txt     506 total

As a bonus, word-count gives us the total characters in all counted files. This is the same as typing
wc -c main.log carrot2.txt carrot.txt

Remember that xargs likes to execute a command once, but you can make it run the thing repeatedly using -I.

This ends today’s edition of Random Unix Tricks. Tonight you can dream about the differences between iterating over lines of input vs words of input vs arguments. And you can wake up knowing that long long ago, in a galaxy still within reach, integration of many small components was fun (iand cryptic).

A monadically built generator

Today, I wanted to write a post about code that sorts a vector of maps. But I can’t write that without a test, now can I? And not just any test — a property-based test! I want to be sure my function works all the time, for all valid input. Also, I don’t want to come up with representative examples – that’s too much work.[1]

The function under test is a custom-sort function, which accepts a bunch of rows (represented as a sequence of hashmaps) and a sequence of instructions: “sort by the value of A, descending; then the value of B, ascending.”

To test with all valid input, I must write code to generate all valid input. I need a vector of maps. The maps should have all the same keys. Some of those keys will be sort instructions. The values in the map can be anything Comparable: strings and ints for instance. Each instructions also includes a direction, ascending or descending. That’s a lot to put together.

For property-based (or “generative”) tests in Clojure, I’ll use test.check. To test a property, I must write a generator that produces input. How do I even start to create a generator this complicated?

Bit by bit! Start with the keys for the maps. Test.check has a generator for them:

(require ‘[clojure.test.check.generators :as gen])
gen/keyword ;; any valid clojure keyword.

The zeroth secret: I dug around in the source to find useful generators. If it seems like I’m pulling these out of my butt, well, this is what I ate.

Next I need multiple keywords, so add in gen/vector. It’s a function that takes a generator as an argument, and uses that repeatedly to create each element, producing a vector.

(gen/vector gen/keyword) ;; between 0 and some keywords

The first secret: generator composition. Put two together, get a better one out.

Since I want a set of keys, not a vector, it’s time for gen/fmap (“functor map,” as opposed to hashmap). That takes a function to run on each produced value before giving it to me, and its source generator.

(gen/fmap set (gen/vector gen/keyword)) ;; set of 0 or more keywords

It wouldn’t do for that set to be empty; my function requires at least 1 instruction, which means at least one keyword. gen/such-that narrows the possible output of the generator. It takes a predicate and a source generator:

(gen/such-that seq (gen/fmap set (gen/vector gen/keyword)))

If you’re not a seasoned Clojure dev: seq is idiomatic for “not empty.” Historical reasons.

This is enough to give me a set of keys, but it’s confusing, so I’m going to pull some of it out into a named function.

(defn non-empty-set [elem-g
  (gen/such-that seq (gen/fmap set (gen/vector elem-g))))

Here’s the generator so far:
(def maps-and-sort-instructions
  (let [set-of-keys  (non-empty-set gen/keyword)]

See what it gives me:
=> (gen/sample maps-and-sort-instructions
   ;; sample makes the generator produce ten values
(#{:Os} #{:? :f_Q_:_kpY:+:518} #{:? :-kZ:9_:_?Ok:JS?F} ….)

Ew. Nasty keywords I never would have come up with. But hey, they’re sets and they’re not empty.

To get maps, I need gen/hash-map. It wants keys, plus generators that produce values; from these it produces maps with a consistent structure, just like I want. It looks like:

(gen/hash-map :one-key gen-of-value :two-key gen-of-this-other-value …)

The value for each key could be anything Comparable really; I’ll settle for strings or ints. Later I can add more to this list. There’s gen/string and gen/int for those; I can choose among them with gen/elements.

(gen/elements [gen/string gen/int]) ;; one of the values in the input vector

I have now created a generator of generators. gen/elements is good for selecting randomly among a known sequence of values. I need a quantity of these value generators, the same quantity as I have keys.

(gen/vector (gen/elements [gen/string gen/int]) (count #??#)) 
  ;; gen/vector accepts an optional length

Well, crap. Now I have a dependency on what I already generated. Test.check alone doesn’t make this easy – you can do it, with some ugly use of gen/bind. Monads to the rescue! With a little plumbing, I can bring in algo.monad, and make the value produced from each generator available to the ones declared after it.

The second secret: monads let generators depend on each others’ output.

(require ‘[clojure.algo.monads :as m])
(m/defmonad gen-m
    [m-bind gen/bind
     m-result gen/return])

(def maps-and-sort-instructions
 (m/domonad gen-m
   [set-of-keys (non-empty-set gen/keyword)
    set-of-value-gens (gen/vector  
                       (gen/elements [gen/string gen/int]) 
                       (count set-of-keys))]
    [set-of-keys, set-of-value-gens])

I don’t recommend sampling this; generators don’t have nice toStrings. It’s time to put those keys and value-generators together, and pass them to gen/hash-map:

(apply gen/hash-map (mapcat vector set-of-keys set-of-value-generators))
  ;; intersperse keys and value-gens, then pass them to gen/hash-map

That’s a generator of maps. We need 0 or more maps, so here comes gen/vector again:

(def maps-and-sort-instructions
 (m/domonad gen-m
  [set-of-keys (non-empty-set gen/keyword)
   set-of-value-gens (gen/vector  
                      (gen/elements [gen/string gen/int]) 
                      (count set-of-keys))
   some-maps (gen/vector 
              (apply gen/hash-map 
               (mapcat vector set-of-keys 

This is worth sampling a few times:
=> (gen/sample maps-and-sort-instructions 3) ;; produce 3 values
([] [] [{:!6!:t4 “à$”, :*B 2, :K0:R*Hw:g:4!? “”}])

It randomly produced two empty vectors first, which is fine. It’s valid to sort 0 maps. If I run that sample more, I’ll see vectors with more maps in them.
Halfway there! Now for the instructions. Start with a subset of the map keys – there’s no subset generator, but I can build one using the non-empty-set defined earlier. I want a non-empty-set of elements from my set-of-keys.

(non-empty-set (gen/elements set-of-keys)) 
  ;; some-keys: 1 or more keys. 

To pair these instruction keys with directions, I’ll generate the right number of directions. Generating a direction means choosing between :ascending or :descending. This is a smaller generator that I can define outside:

(def mygen-direction-of-sort 
      (gen/elements [:ascending :descending])) 

and then to get a specific-length vector of these:

(gen/vector mygen-direction-of-sort (count some-keys)) 
   ;; some-directions

I’ll put the instruction keys with the directions together after the generation is all complete, and assemble the output:

(def maps-and-sort-instructions
 (m/domonad gen-m
  [set-of-keys (non-empty-set gen/keyword)
   set-of-value-gens (gen/vector  
                      (gen/elements [gen/string gen/int]) 
                      (count set-of-keys))
   some-maps (gen/vector 
              (apply gen/hash-map 
               (mapcat vector set-of-keys 
   some-keys (non-empty-set (gen/elements set-of-keys)) 
   some-directions (gen/vector mygen-direction-of-sort 
                               (count some-keys))]
   (let [instructions (map vector some-keys some-directions)] 
                           ;; pair keys with directions
    [some-maps instructions]))) ;; return maps and instructions

There it is, one giant generator, built of at least 11 small ones. That’s a lot of Clojure code… way too much to trust without a test. I need a property for my generator!
What is important about the output of this generator? Every instruction is a pair, every direction is either :ascending or :descending, and every key in the sort instructions is present in every map. I could also specify that the values for each key are all Comparable with each other, but I haven’t yet. This is close enough:

(def sort-instructions-are-compatible-with-maps
    [[rows instructions] maps-and-sort-instructions]
    (every? identity (for [[k direction] instructions
                          ;; break instructions into parts
              (and (#{:ascending :descending} direction
                    ;; Clojure looks so weird
                   (every? k rows)))))) 
                          ;; will be false if the key is absent

(require ‘[clojure.test.check :as tc])
(tc/quick-check 50 sort-instructions-are-compatible-with-maps)
;; {:result true, :num-tests 50, :seed 1412659276160}

Hurray, my property is true. My generator works. Now I can write a test… then maybe the code… then someday the post that I wanted to write tonight.

You might roll your eyes at me for going to these lengths to test code that’s only going to be used in a blog post. But I want code that works, not just two or three times but all the time. (Write enough concurrent code, and you notice the a difference between “I saw it work” and “it works.”) Since I’m working in Clojure, I can’t lean on the compiler to test the skeleton of my program. It’s all on me. And “I saw it work once in the REPL” isn’t satisfying.

Blake Meike points out on Twitter, “Nearly the entire Internet revolution… is based on works-so-far code.” So true! It’s that way at work. Maybe my free-time coding is the only coding I get to do right. Maybe that’s why open-source software has the potential to be more correct than commercial software. Maybe it’s the late-night principles of a few hungry-for-correctness programmers that move technology forward.


But it does feel good to write a solid property-based test.

[1] Coming up with examples is “work,” as opposed to “programming.”

Code for this post: