Ancient Technology

I'm usually skeptical when I watch some History Channel cheapie about ancient trans-Atlantic journeys or whatever, but the evidence in this case is incontrovertible: the ancient Greeks knew how to build clocks, with gears and all. Only two examples exist, but they're too sophisticated to have been the only ones of their kind. How could this knowledge have been lost? John Seabrook suggests a number of reasons: not many people would have possessed such knowledge, and if social upheavals separated them from the opportunity to use the knowledge, the clocks would have ended up as scrap, and melted down; both Greek and Roman culture respected individual bravery too much to commit itself to technologizing warfare; technology may have provided delight rather than profit. Moreover, the knowledge almost surely ended up with the Arabs, whence it returned to Europe in the 14th century, when clocks with gears suddenly (re)appear. It's easy to suspect that the West refuses to admit just how advanced Muslim civilization was, but something more peculiar is going on here: even classicists showed little interest in the Antikythera Mechanism until recently. It's as though we think that only we are capable of technology per se. The Greeks had some impressive mechanisms, but didn't put them to uses we respect.

Country music is actually pretty good!

Merle Haggard, at http://archive.salon.com/people/bc/2000/11/14/haggard/index2.html: "Look at the past 25 years -- we went downhill, and if people don't realize it, they don't have their fucking eyes on," says Haggard. "In 1960, when I came out of prison as an ex-convict, I had more freedom under parolee supervision than there's available to an average citizen in America right now. I mean, there was nobody going to throw you down on the side of the road spread-eagled, and look up your butt for a fucking marijuana cigarette. God almighty, what have we done to each other?"

I give up!

I started this blog about a year ago because I thought it was necessary to my self-promotion. In addition to going to work every day, and doing a good job, and attending conferences, and reading books about CS generally, whatever language I'm using (XSLT, F#, whatever), whatever platform I'm on (.NET for most of the last 4 years), etc., I need to blog about the cool thing I'm doing, and get some C# MVP finally to add me to his blogroll. Real life got in the way, though, as it will, esp. in the form of a new baby. I've had just enough time to do what needed to be done, and none left over to describe to the recruiters at Google who, one imagines, are reading all these blogs, to explain how well I did it. So I'm going to start using this blog the way most people do, i.e. to quote big chunks of stuff I read elsewhere, give shout-outs to my friends, post cute toddler photos, etc.

Anyway, the big chunk that I want to regurgitate undigested is from The New Yorker, May 14, 2007. James Surowiecki, whose The Wisdom of Crowds might have appealed to the same folks I see reading Radicals for Capitalism on the bus, argues that it might be better for the whole if a certain part, namely companies who own patents, makes less money. I suppose that's an instance of the radicalism of capitalism; emergent capitalist economies might require a certain amount of theft, just as ours did. I'm not an ideologue of open-source software; I actually don't care about Linux one way or another, just as I don't care about Microsoft. Anyway, "History suggests that after a certain point tougher intellectual property rules yield diminishing returns. Josh Lerner, a professor at Harvard Business School, looked at a hundred and fifty years of patenting, and found that strengthening patent laws had little effect on the number of innovations within a country. And, in the US, stronger patent protections for things like software have had little or no effect on the amount of innovation in the field. The benefits of stronger IP protection are even less convincing when it comes to copyright law: there's little evidence that writers and artists are made more productive or creative by the prospect of earning profits for seventy years after they die, and the historical record suggests only a tenuous connection between stronger IP laws and creative output."

One would expect that at some point China will have to have strong laws to prevent Chinese entrepreneurs from stealing from each other. You're certainly not going to read some ponderous clash-of-civilizations crap on my blog. Maybe China is culturally incapable of respecting the rule of law, in the way that's bred into the Anglo-Saxon bone. Maybe not. "The great irony is that the US economy in its early years was built in large part on a lax attitude toward intellectual property rights and enforcement [ditto for the Dutch and English economies in the two centuries before that]. As the historian Doron Ben-Atar shows in his book Trade Secrets, the Founders believed that a strict attitude toward patents and copyright would limit domestic innovation and make it harder for the US to expand its industrial base. American law did not protect the rights of foreign investors or writers, and Secretary of the Treasury Alexander Hamilton, in his famous Report on the Manufactures, of 1791, actively advocated the theft of technology and the luring of skilled workers from foreign countries. Among the beneficiaries...was the American textile industry,which flourished thanks to pirated technology."

I really hate Wes Anderson

From James Wolcott's blog: "When I was watching Wes Anderson's beyond-precious and unjustifiably proud-of-itself The Life Aquatic, there was a scene where a three-legged dog is whimpering on deck and Jeff Goldblum, playing the suave villain, asks Bill Murray the dog's name. Murray tells him and (off camera) we hear a loud smack as Goldblum hits the dog to stop its whimpering. I can't recall if Murray changed expression or not, since that wasn't a high priority for him here. The minor cruelty doled out to an animal for a cheap laugh was compounded when the dog was left behind at the end splashing in the water as the cast of overpaid actors vying to outhip each other departs."

Wolcott puts it better than I could. Jason Schwartzmann gave Rushmore some real passion, and the film deserved the praise it got, but my jaw clenched while watching The Royal Tenenbaums. Not only was I both bored and irritated, Anjelica Huston looked bored and irritated, the usually ill-used Danny Glover looked bored and irritated, Gwyneth Paltrow looked bored and irritated (though that may just be Gwyneth)...only Gene Hackman didn't seem to be saying, "Dig how adorable I am in my ineffectuality." I know that Wes Anderson has already anticipated my belligerent response to his WASP privilege (check out the bowtie) by his irony, but that just makes me hate him more. Which, of course, lets him come out on top!

Would the aimless but amusing banter of his films be possible without the equally problematic Quentin Tarantino, who similarly dares you to disdain his shallowness? I saw Pulp Fiction on a college campus, surrounded by undergraduates (I was about 34 at the time), and I might have been the only person in the theater not to laugh when Marvin (the nigger, in case you've forgotten) gets his brains blown out! This gives Quentin the opportunity to appear in his own film and try to say the word "nigger" in good conscience, though he's so sweaty and uncomfortable doing it that ofay college students were not moved to emulate him, as far as I know. I realize that, having admitted that I was not enchanted by Pulp Fiction, I will never considered cool, but that's what his film is for: to separate the cool from the uncool (cf. this). What I'm getting at is that Wes Anderson is sort of the upper-class Tarantino, complex in an infuriatingly shallow if not selfish way, and deliberate in his provocation, which is intended to make you lose your cool and leave him on top.

NAnt's Filtered Trigger

I have to say that I found the documentation on this feature somewhat baffling, but that might just be me. We use Subversion here, and I'd like the build not to run if the only files committed since the last build are the ones that the last build created, e.g. the version.txt file, the generated CommonAssemblyInfo.cs into which the incremented build number is written, the backups of CruiseControl.NET's various .config and .xsl files, etc. Feel free to write me if my example doesn't help you out. The problem that cost me close to a day is that relative paths within the block don't seem to be resolved as I expected. See my comments...

<cruisecontrol>  
  <project name="Our Project 3.0">

    <workingDirectory>E:\Builds\Our Project 3.0</workingDirectory>
    <artifactDirectory>E:\Builds\Our Project 3.0\artifacts</artifactDirectory>
    <!-- 
         CruiseControl.NET doesn't handle spaces in paths consistently, so let's
         keep ourselves out of trouble. 
    -->
    <webURL>http://localhost/ccnet/OurProject3.0</webURL>

    <!-- Check every 10 minutes. -->
    <triggers>
        <intervalTrigger seconds="600" />
    </triggers>
    
    <sourcecontrol type="filtered">
      <sourceControlProvider type="svn">
        <trunkUrl>svn://aMachine/omega/trunk/OurProject</trunkUrl>
        <workingDirectory>E:\Builds\Our Project 3.0</workingDirectory>
        <username>tnassar</username>
        <password></password>
      </sourceControlProvider>
    <inclusionFilters>
      <pathFilter>
        <!-- Note that this is the full pathname, and apparently has to be. -->
       <pattern>/trunk/Our Project/**/*.*</pattern>
      </pathFilter>
    </inclusionFilters>
    <exclusionFilters>
      <!-- Changes to these files should *not* cause a new build. -->
      <pathFilter>
        <pattern>/trunk/Our Project/version.txt</pattern>
      </pathFilter>
      <pathFilter>
        <!-- These are serialization assemblies generated during the build process,
             using xsd.exe.
        -->
        <pattern>/trunk/Our Project/Serialization/Bin/*.dll</pattern>
      </pathFilter>
      <pathFilter>
        <!-- The build number is boosted by a NAnt task. -->
     <pattern>/trunk/Omega LP/Applications/CommonAssemblyInfo.cs</pattern>
      </pathFilter>
      <pathFilter>
        <pattern>/trunk/Our Project/Build/**/*</pattern>
      </pathFilter>
    </exclusionFilters>
    </sourcecontrol>
    <tasks>
       <!-- And so on... -->
    </tasks>

Generating LOC from NAnt, Part D'oh!

At some point I'd like to make all the code available, and perhaps even contribute it NAntContrib, but at the moment it's really butt-ugly. I'm glad that C# 2.0 has better support for sort-of-functional programming constructs, but this is unpleasantly verbose:

public static TreeSorter Sort(string[] paths)
{
 if (paths.Length == 0)
  return new TreeSorter("");
 List<string> pathsList = new List<string>(paths);
 pathsList.Sort();
 List<List<string>> splitPaths = pathsList.ConvertAll<List<string>>(delegate(string path)
                                                                     {
                                                                      return
                                                                       new List<string>(
                                                                        path.Split(
                                                                         System.IO.Path.DirectorySeparatorChar));
                                                                     });

 int index = 0;
 for (; index < splitPaths[0].Count; ++index)
 {
  if (!splitPaths.TrueForAll(delegate(List<string> input)
                              {
                               return index < input.Count && input[index] == splitPaths[0][index];
                              }))
   break;
 }

 IEnumerable<string> commonPath = splitPaths[0].GetRange(0, index);
 IList<IEnumerable<string>> truncatedPaths = splitPaths.ConvertAll<IEnumerable<string>>(delegate(List<string> input)
                                                                                         {
                                                                                          return
                                                                                           input.GetRange(index,
                                                                                                          input.Count -
                                                                                                          index);
                                                                                         });
 return new TreeSorter(commonPath, truncatedPaths);
}

Generating LOC from NAnt, Part 1

Last March I my team took over a failing project for our most important client. The domain to which the software applied is very interesting, and very difficult, and I can't deny that the previous contractor had employed some smart people...at some point in the project's history! The code was a mess. Simply passing FxCop over it revealed that about 5% of it was dead code. After a few months of working with it, we realized that another significant part of it would only be called if certain events fired, and they never did. This is often not so easy to prove, unfortunately. Since I use ReSharper, I found it easier simply to delete unused methods, but the overuse of dynamic binding (!) in the code base meant that I could not be sure, without regression tests (which of course didn't exist until I wrote them) that certain classes were never instantiated. And so on.

Anyway, we began by simply counting the lines of text in the entire code base. This measure decreased daily, and the project manager finally suggested that we do this more systematically so that the client could cite these figures when trying to justify his additional expenditures on this already "working" code to his superiors. I want to make clear that we are not somehow charging for KLOC. Notwithstanding that we're doing this work for a gov't agency, we're not working under some burdensome methodology. The distinction between physical and logical LOC is not so important to us. We are supposed to be making the code more maintainable; a steady decrease in the relative LOC counts as success. I imposed the requirement on myself that the LOC metric be generated from CruiseControl.NET via NAnt. None of the tools that I could use in this way were entirely satisfactory, however. NDepend measured the LOC in files that didn't interest me (e.g., MyForm.Designer.cs); GeroneSoft's Code Counter likewise. Both utilites allow me to create include and exclude lists, but none of them as neatly as NAnt! I would really like to be able to edit the .build file, quickly create another <fileset>, say for ".cs files generated by the Windows Forms Designer," measure the LOC in that set, and arrange for those results to be published by CruiseControl.NET.

NAntContrib does supply a <codestats> task, which accepts a fileset as input. Then, unfortunately, it outputs the statistics as a flat list, which is not what I wanted. What I need is to turn that list into a tree again. This turns out to be unspeakably difficult without XSLT 2.0. Don't recommend Muenchian groupings, please! My initial thought that it would be neat to write this transform cost me at least a day. Then I set about writing a custom NAnt task in C#, but once again I was sidetracked by C#'s relatively poor support for list comprehensions. Moreover, one is discouraged by "performance considerations" from repeatedly splitting and rejoining strings, slicing lists, etc. That's what happens to you when you write too much C, as opposed to learning LISP at a good school. After about two wasted days, on the bus going home, I pulled out a pad of paper and wrote out some Python. I tried it out when I got home, and it worked right out of the box. Then, I admit with some embarrassment, I retrofitted the unit tests, and implemented the special functions such as __len__(), for the sake of the tests.

import os
import itertools
import unittest

class Node:
 def __init__(self, path = [], children = []):
  assert isinstance(path, list)
  assert isinstance(children, list)
  self.path = path
  self.children = {}
  for child in children:
   self.add(child)
  
 def __len__(self):
  return 1 + sum([len(child) for child in self.children.values()])

 def __getitem__(self, key):
  return self.children.__getitem__(key)

 def __setitem__(self, key):
  return self.children.__setitem__(key)
 
 def __iter__(self):
  yield self.path
  for child in self.children.values():
   for i in child:
    yield self.path + i             
  
 def __repr__(self):
  return os.sep.join(self.path)

 def add(self, path):
  assert len(path), "Cannot add an empty path."
  if len(path) == 1:
   self.children[path[0]] = Node(path)
  elif self.children.has_key(path[0]):
   self.children[path[0]].add(path[1:])
  else:
   self.children[path[0]] = Node([path[0]], [path[1:]])
 
def allsame(seq):
 # An empty sequence is true because is has no mismatches. 
 # A 1-length sequence should always be true, i.e., imap(...) will
 # return an empty list, of which False is not a member (duh!).
 # Otherwise, compare all elements to the first. The iteration 
 # over the sequence should stop as soon as False becomes
 # a member of the output sequence.
 return not seq or False not in itertools.imap(lambda x: x == seq[0], itertools.islice(seq, 1, None))
 
def createNodeSorter(paths):
 assert paths, "Cannot create a base node for 0 paths"
 # Split the paths along the directory separator character.
 splitFiles = [f.split(os.sep) for f in paths]
 # Now "pivot" these lists in order to find out if they share a common
 # base path. Note that os.commonprefix() is character-based; it is 
 # not suitable.
 zipped = zip(*splitFiles)
 # How many sequences consist of identical elements?
 # Concatenate those, and you've got the common base path.
 common = [f[0] for f in itertools.takewhile(allsame, zipped)]
 print "Common base path: " + str(common)
 # Now strip the common base path.
 splitFiles = [f[len(common):] for f in splitFiles if f != common]
 print "\tchildren: " + str(splitFiles)
 return Node(common, splitFiles)
 
class AllSameTest(unittest.TestCase):
 def testEmptySequence(self):
  self.assertTrue(allsame([]))
  
 def testSingleElement(self):
  self.assertTrue(allsame([1]))
  self.assertTrue(allsame(['test']))
  
 def testTwoIntegers(self):
  self.assertTrue(allsame([1, 1]))
  self.assertFalse(allsame([0, 1]))
  
 def testTwoStrings(self):
  self.assertTrue(allsame(['test', 'test']))
  self.assertFalse(allsame(['test', 'fail']))
  
class CreatorTest(unittest.TestCase):
 def testEmptyFileSet(self):
  self.assertRaises(AssertionError, lambda: createNodeSorter([]))
  
 def testSinglePath(self):
  n = createNodeSorter([r'D:\trunk\Projects\Build\NAnt\LineCounter\LineCount.cs'])
  self.assertEqual(1, len(n))
  
 def testTwoPaths(self):
  files = [
   r'D:\trunk\Projects\Build\NAnt\LineCounter\LineCount.cs',
   r'D:\trunk\Projects\Build\NAnt\LineCounter\LineCountCollection.cs']
  n = createNodeSorter(files)
  self.assertEqual(3, len(n))
  self.assertEqual(['D:', 'trunk', 'Projects', 'Build', 'NAnt', 'LineCounter'], n.path)
  
 def testOverlappingPaths(self):
  files = [
   r'D:\trunk\Projects\Build\NAnt\LineCounter',
   r'D:\trunk\Projects\Build\NAnt\LineCounter\LineCountCollection.cs']
  n = createNodeSorter(files)
  self.assertEqual(2, len(n))
  self.assertEqual(['D:', 'trunk', 'Projects', 'Build', 'NAnt', 'LineCounter'], n.path)
 
class NodeSorterTest(unittest.TestCase):
 def testBlankNode(self):
  n = Node()
  self.assertEqual('', repr(n))
  self.assertEqual(1, len(n))
  
 def testSingleChild(self):
  n = Node(['base'], [['child1']])
  self.assertEqual(2, len(n))
  self.assertEqual('base', `n`)
  
 def testNoChildren(self):
  n = Node(['C:'])
  self.assertEqual(1, len(n))
  
 def testInvalidPath(self):
  self.assertRaises(AssertionError, lambda: Node('base'))
  
 def testIteratorBlankNode(self):
  n = Node()
  nodes = [node for node in n]
  self.assertEqual([[]], nodes)
  
 def testIteratorNodeWithPath(self):
  n = Node(['C:', 'Program Files'])
  nodes = [node for node in n]
  self.assertEqual([['C:', 'Program Files']], nodes)
  
 def testIteratorWithOneChild(self):
  n = Node(['C:'], [['Program Files']])
  nodes = [node for node in n]
  self.assertEqual(['C:'], nodes[0])
  self.assertEqual(['C:', 'Program Files'], nodes[1])
  
 def testThreeLevels(self):
  n = Node(['C:'], [['Program Files', 'Adobe', 'Acrobat 7.0'], ['Program Files', "CruiseControl.NET"]]) 
  self.assertEqual(5, len(n))
  
 def testNoCommonBase(self):
  n = Node([], [['C:', 'Program Files', 'Adobe', 'Acrobat 7.0'], ['D:', 'Program Files', "CruiseControl.NET"]])
  self.assertEquals(8, len(n))
 
if __name__ == '__main__':
 unittest.main()

Boosting Your Assembly.cs Revision Number from NAnt

I know that others have blogged about this, esp. Scott Hanselman did, somewhere...I'm digressing already. I wanted the simplest possible solution: I wanted to leverage already existing NAnt or NAntContrib tasks, rather than write my own; I did not want to use the CruiseControl.NET label, since a new CC.NET installation starts from zero, as I found out after I hosed my own, and in any case I would want CC.NET ultimately to do no more than call a bunch of NAnt tasks, pass all the artifacts through some XSLT, and create the Web pages. What I ended up with was 1, a file called version.txt, containing only (at the moment) the text 3.0.0.1401; 2, a file called CommonAssemblyInfo.cs, including assembly-level metadata common to the entire application, e.g. [assembly: AssemblyVersionAttribute("3.0.0.1412")]; 3, the following NAnt task:

<target name="createAsmInfo" description="Overwrite the rev. #" >
  <if test="${not property::exists('version.txt')}">
    <property name="version.txt" value="version.txt" />
  </if>
  <if test="${not property::exists('common.assembly.info')}">
    <property
      name="common.assembly.info"
      value="Applications/CommonAssemblyInfo.cs" />
  </if>
  <!-- I.e., increment the revision number and *not* the build number. -->
  <version path="${version.txt}"
    buildtype="NoIncrement"
    revisiontype="Increment" />
  <asminfo output="${common.assembly.info}" language="CSharp">
    <imports>
      <import namespace="System.Reflection" />
    </imports>
    <attributes>
      
      <attribute type="AssemblyVersionAttribute"
     
value="${buildnumber.major}.${buildnumber.minor}.${buildnumber.build}.${buildnumber.revision}" />
      <attribute type="AssemblyCopyrightAttribute" value="Copyright © 2006 MDi" />
      <attribute type="AssemblyCompanyAttribute" value="MegaDyne, Inc." />
      <attribute type="AssemblyProductAttribute" value="KillerApp" />
    </attributes>
  </asminfo>
  <!-- The svn task is inadequate. It doesn't handle commits! -->
  <exec program='${svn.exe}'
    commandline='commit --non-interactive --username=${svn.username} --password=${svn.password} -m "Updated by CruiseControl.NET" ' />
<exec program='${svn.exe}' commandline='update' />
</target>

The <asminfo> task should really not overwrite existing metadata unless so instructed, but I haven't tested that yet. Note that I immediately commit the changed files back into the repository; this might be the wrong thing to do, unless the build succeeds. If it does fail, then CruiseControl.NET will be unable to update the source code from the repository; i.e., there files I've changed will be in conflict. This suggests that I really do all my work from NAnt, but I haven't gotten around to that yet. A further problem is that version.txt and CommonAssemblyInfo.cs will look new to CC.NET the next time it checks, triggering another build. CC.NET offers a "filter trigger" for this sort of thing, but I found the documentation incomprehensible, so I haven't been able to use it yet.

The one additional step is to remove the common metadata from AssemblyInfo.cs files throughout the solution, and add CommonAssemblyInfo.cs as a link. This turned out to be somewhat tricky for me. I have an old habit of configuring Windows Explorer to open files with a single click; a more experienced developer once told me that he was "more productive" with this option; I fell for it, and now I'm stuck with this wierd tic. Anyway, I would select "Add existing item" from a project's context menu, navigate to CommonAssemblyInfo.cs, click on it...and of course a copy would be added to the project. You won't have this problem! Anyway, I had to right-click on the file from the File Open dialog, select "Select" from the context menu, and only then would the little triangle be enabled:

That's pretty much it. You have to remember to change every project this way, but that's about it. Some (Scott Hanselman) prefer to edit the .csproj files themselves; I am probably revealing myself as a non-guru by this admission, but I hate doing that.

Land of the Free

From a review of David Brion Davis's Inhuman Bondage in the London Telegraph: "The story Davis tells is strikingly at odds with traditional accounts. Those used to thinking of New World settlement in terms of a widening of horizons and a breaking free from European constraints will be surprised to learn that, before 1820, African slaves outnumbered European settlers by a ratio of more than five to one. This is not to deny that some Europeans did find the experience liberating, although it is worth remembering that many of them arrived themselves as indentured servants or transported criminals, and so were hardly in a position to feel liberated. The picture is certainly very different from that painted by those who like to think of early America either as a refuge for the oppressed or a gigantic adventure playground. If numbers are what count, the “typical” American settler was neither a swaggering conquistador nor a Bible-quoting Puritan but a miserable African slave toiling on a sugar plantation."

CEOs are Vile

I was cheerfully reading Tuesday Morning Quarterback while I snarfed my Thai fish cakes, and nearly spat when I came to the passage below. Perhaps I'm naive, but what "market forces" are operating on behalf of a CEO who's about to quit?

Much news and sports commentary focuses on the ever-larger paychecks of professional athletes. But even Peyton Manning is a day laborer compared to the modern Fortune 500 CEO. In May, Exxon Mobil shareholders passed the first resolution in company history to be enacted over opposition of the board of directors; at issue was shareholder fury regarding the $168 million retiring CEO Lee Raymond awarded himself in his final year. "There's some unhappiness about the way Raymond's compensation was handled," new Exxon Mobil CEO Rex Tillerson dryly told a news conference. During the summer Hank McKinnell was ousted as CEO of Pfizer. Over his last five years at the helm, he got $162 million, even as Pfizer earnings faltered. Carol Hymowitz of the Wall Street Journal reported that the head of Pfizer's "compensation committee" defended McKinnell's windfall on grounds of market forces in executive pay -- which in this context appears to mean, "CEOs at other companies are picking shareholders' pockets, too." There just wasn't anybody who would have taken the Pfizer job for less than $162 million? McKinnell's pay for his tenure atop Pfizer equates to $130,000 per work day.

African Pop

Ok-Oyot Project live at Iota in Arlington, VA: should be beautiful!

...and it wasn't. Why did the sound engineer insist on mixing them like some stupid rock band, with the thudding bass all the way up, obscuring the interlocking guitar figures?

xUnit for Scheme LISP

After a bit of pain, caused by my trying to install the SchemeUnit 2.0 download available on SourceForge, I managed to locate the 3.0 download here. I'm a novice when it comes to LISP, and to DrScheme, so the sparse installation instructions were inadequate for me. After some trial and error, which included messing up my DrScheme installation enough that I had to reinstall it, I found the happy path. First, I downloaded the .plt file and saved it an arbitary location (Firefox insists on showing the contents of the file as text, which is not what you want; I had to resort to IE).

Noel Welsh, the author of SchemeUnit, has dropped hints about how to install the .plt using planet, but my only goal is to learn a little more about LISP, and I don't want to be distracted by another utility. Noel's also turned out to be slightly inconsistent with the original documentation, as we'll see. In any case, Dr. Scheme's File menu has an Install .plt File... option, which seemed like the right method, so I clicked it and saw the dialog on the right. Which path to pick? After some trial and error, including a reinstallation of DrScheme, I noticed another dialog that had been concealed by the file selector. It turns out that I needed to navigate to C:\Program Files\PLT\collects, and make a new directory called schematics, after which I'd click OK and be happy forever. Oops! When I typed (require (lib "test.ss" "schemeunit")) at the DrScheme console, as SchemeUnit's Quick Start page says, it responded, "collection not found: "schemeunit" in any of [the paths displayed below]." D'oh! So, just to be one the safe side, I reinstalled DrScheme again, then followed the same steps as before to install the .plt file, but this time created a schemeunit directory within my PLT installation. It works! Now I actually have to write some LISP.

Voodoo in New Orleans

I recently read Ned Sublette's superb Cuba and Its Music: From the First Drums to the Mambo, and would certainly recommend it to anyone interested in one of the world's most musically brilliant cultures. Sublette cofounded the QubaDisc label and is coproducer of public radio's Afropop Worldwide. I don't know how well-founded is his account of musical commerce in the ancient world between Phoenicia, North Africa, and Cadiz, and the steady flow of African rhythmic innovation into Europe and the Western hemisphere over the last millenium. For example, a Kikongo etymology for sarabande seems rather fanciful when a very similiar Persian word for "song" is at hand. Nonetheless, a North American reader should be especially grateful to Sublette for his ambition to detail all the musical options available to Cuban musicians.

Many of these are really quite different from those available here. Spanish and even Moorish song forms are still typical of son, for example, and there really is no Cuban equivalent of the 12-bar blues (though Guillermo Portabales's "Hay Jaleo" in in AAB form). There are also significant differences in the African material that predominates here and there respectively. Dizzy Gillespie, whose musical understanding of the rumba (the additional 'h' was some strange marketing trick) was beyond reproach, thought that the differences between jazz and rumba were due to drums having been "taken from" North American slaves. However, the slave trade to Cuba and that to North America didn't work the same way. The trade to Cuba continued longer; in Cuba, Africans could much more readily maintain their particular traditions (or, more accurately, they could build on them within Cuba, a comparatively large place; they could also integrate the musical forms brought by refugees from Haiti, or shipments of slaves from different areas). On the other hand, there's really no Cuban music that has "blue notes."

Paul Oliver noticed decades ago (cf. Savannah Syncopators) that blues sounds more like Malian than Ghanaian music, i.e., solo string instruments figure much more heavily than percussion ensembles. Gerhard Kubik built on this idea in such works as Africa and the Blues (American-Made Music). Slaves brought to this country may have lost some of their percussive knowledge, may have had less to begin with, or may simply have selected from among their musical options those most useful: those of savannah herders. Hence the "field holler," etc.

I have one quibble with Sublette's book, and that is that the rather nasty cultic practices of palo (conjury with dead body parts, etc.) are treated rather too enthusiastically. For me, only the music justifies the religion. As for New Orleans voodoo, I'm rather skeptical about how profoundly anyone has ever believed it.

Agility in Gov't Contracting

In any large bureaucracy, one is often deprived of the requisite managerial power to carry out one's responsibilities, or even of the right to express and exercise one's better judgement. Yes, here's my gratuitous, parenthetical reference to the failed Trilogy project at the FBI. I'm happy not to work at SAIC, or any other big contractor. "Agile" has become a buzzword in gov't contracting, but I'm more than skeptical. There's too much money to be made in Northern Virginia by feeding gov't clients' hopes that the more that more requirements they state up front, the more they'll get. In case you don't have access to the Washington Post online, I'll quote:

Matthew Patton, a programmer who worked on the contract for SAIC, said the company seemed to make no attempts to control costs. It kept 200 programmers on staff doing "make work," he said, when a couple of dozen would have been enough. The company's attitude was that "it's other people's money, so they'll burn it every which way they want to," he said.

Patton, a specialist in IT security, became nervous at one point that the project did not have sufficient safeguards. But he said his bosses had little interest. "Would the product actually work? Would it help agents do their jobs? I don't think anyone on the SAIC side cared about that," said Patton, who was removed from the project after three months when he posted his concerns online.

To respond preemptively to any defenses of SAIC, let me say that if they knew that they couldn't deliver, they should have refused to take any more money, money that came, in the end, from taxpayers. This isn't a game, people; we're talking about national security here.

Developers Considered as Obstacle to Agility

A few days before I flew to Minneapolis to attend Agile2006, I underwent my performance review at work. My project manager and practice manager lauded my "passion" for my work, and suggested only that I could be even more valuable to the company if I could help them pass the CMMI Level 3 audit. I immediately thought that the work I'd already done to bring the legacy code base "under test," devise regression and acceptance tests in FIT, and automate builds via CruiseControl.NET could be extended by my entire team, under the aegis of the company's CMMI certification initiative, i.e., I could test-infect my coworkers and advance my employer's interests at the same time. Anyone who knows what a pessimist I am will know that I wouldn't be telling this story at all if it had turned out as I had hoped.

I must say that I like my job, and I like my coworkers. After working on government contracts for several years for employers and under project managers who could and did expressly forbid me the very use of testing and refactoring tools (Watir, Resharper, Eclipse, JMock, FitNesse, etc.), I ride the bus to Arlington in an enthusiastic mood. They are certainly the cleverest and most diligent team I've worked with in a good while.

Anyway, I'm not so much discouraged that my coworkers didn't rally to NUnit (some of them are familiar with JUnit; they seem to think it's just something you do in the Java world) and FitNesse after I brought the test coverage of a dismal yet significant code base up to 40% from 0% in a few months, as I am puzzled. I mused over this problem rather a lot during lulls in the action at Agile2006. At a status meeting at work last week, my jaw nearly dropped when the technical lead insisted that WinRunner was the appropriate tool for getting the application under test. I consider WinRunner to be a dead end, and in fact several teams near mine have attempted to make it part of their process and then given up. I don't want to review all the arguments against testing only through the GUI; I'll just say that if you test that way, you'll code that way, namely from the GUI on down, and your code will almost certainly be incoherent, just as if you code from the database schema on up. In one day, I managed to write tests in FitNesse that cover every single one of the use cases we were able to conceive for the application.

I should be pleased to have had the chance to create a fait accompli in FitNesse, yet it's somewhat tiring, always to have to carry out an alternative strategy before I can argue the case for it! My next goal is to configure CruiseControl.NET to pull the newest source from Subversion, rebuild it, run all the unit and acceptance tests, etc., and to make all this so easy that no one could think of doing things any other way. Until I've figured it out, everyone will continue to do manual testing. In fact, they'll continue even after I've created my next fait accompli.

Why? They're smart and diligent. Why do they not also realize how much time they waste every day? Perhaps the typical software developer's education provides him with an illusion that experience may never dispel, namely that if he simply throws himself at a problem the way he threw himself at assignments, he'll solve them. Then, of course, his professional progress becomes a matter of learning more about domains, or about platforms, but never about the resolute micrological analysis of one's own practices. Perhaps the most accomplished developer at my workplace, who participates in W3C's Binary XML Working Group, considers TDD to be unsuitable for "deep programming." It's not worth my time to debate him, here or to his face. The point I want to make is that the agile community's characterization of the resistance to agility as coming from "pointy-headed bosses" (yes, I heard this phrase more than once Agile2006), or from within "dysfunctional" organization, or from customers (!), is wrong. Competent developers are the source of this resistance, developers whose history of accomplishment deceives them that they don't need to think any harder about how they do things. Kent Beck, in Extreme Programming Explained, 2nd ed., has argued that overwork is, paradoxically, a retreat from professional responsibility. Yet overwork is strangely tempting to developers—I'm still tempted even now, when I have two small boys at home—so I can only conclude that on some level, we think that what our job is about is cranking out code, rather than exercising good judgment.

As evidence, I would present the odd attachment that my technical lead has to WinRunner, and to test plans written in Excel! As a software developer, in Northern VA and Silicon Valley, I have had 8 different technical leads, all of them entirely competent developers, and every single one, when he became a manager, suddenly developed a mania for Gantt charts, or documentation that immediately and obviously got out of sync with the application's functionality, Microsoft Word documents specifying variable naming conventions or coding standards, or, quel horreur, IEEE 830 requirements! Every one, in other words, was utterly incapable of analyzing his own and his subordinates' productivity, believing instead that imposing additional such adventitious requirements on the only sort of development they'd every practiced could be possible, desirable, and effective. In my experience, when my development process actually conformed to a prior Gantt chart, that was due to dumb luck, deliberate ass-dragging, or retrofitting the Gantt chart entries to the work I'd actually done with my manager's explicit approval. Is this poignant, or hilarious?

In short, the resistance to agility, to the continuous and deliberate analysis and refinement of one's modus operandi individually and as part of a team, conflicts with a profound motivation of many software developers: to do as much of it as they can without thinking about how they do it. The avoidance of self-reflection, let alone the kind of reflection that pair programming induces, becomes a professional prerogative. I think of TDD as a kind of carefully calibrated negative reinforcement, in which one purposefully causes only as many tests to fail as one can easily fix. In return, of course, one gets the positive reinforcement of the green bar. In contradiction to the frequent claim that TDD should be the most attractive practice to introduce first to a team, many developers resist precisely this practice, because it seems like the intrusion into their personal space of a less intelligent alter ego, one who purposefully writes code that he knows won't work! Even younger developers will say, "I know how to do this; why would I test it first?" If you begin with that attitude, it can take an extreme effort of will to let go of it when you really do know how to do things.

The Change-Counting Algorithm & TDD

I recently decided to make my way through Sussman & Abelson's classic CS textbook The Structure and Interpretation of Computer Programs, partly for reasons of professionalism, partly to clarify my thoughts on "test-driven development" and algorithmic programming. Every familiar example, and nearly every question I see on the Test-Driven Development newsgroup concerns object-oriented programming. The "bowling game" is simply too trivial a counterexample, in my opinion, but we can dispute this elsewhere.

At any rate, SICP poses this problem in Chapter 1: "How many different ways can we make change of $ 1.00, given half-dollars, quarters, dimes, nickels, and pennies? More generally, can we write a procedure to compute the number of ways to
change any given amount of money?" There is, it turns out, a fair amount of literature on this problem (cf. David Pearson's paper, or
What This Country Needs is an 18 Cent Piece). Despite having the solution right in front of me, an implementation eluded me until I really considered the structure of the problem, which is recursive. The authors provide unequivocal hints: "Consider this reduction rule carefully, and convince yourself that we can use it to describe an algorithm if we specify the following degenerate cases: 1, If a is exactly 0, we should count that as 1 way to make change; 2, If a is less than 0, we should count that as 0 ways to make change; 3, If n [the number of available denominations] is 0, we should count that as 0 ways to make change." These should be the starting points for the test-driven development of the algorithm, but I only understood their significance within the recursion after pondering the problem while riding the bus. Imagine you've got quarters and pennies, and are asked to make $.26 in change. You can try to use 1 quarter. Now you've got to make $.01 with quarters and pennies. If you use another quarter, you've then got to make - $.24, at which point condition 1 will obtain; if you use a penny, you'll then have to make $.00, at which point condition 2 will obtain (and the recursion will stop). Condition 3 will also stop the recursion, i.e., you've got no more denominations to try. Once I'd understood all this, I could eliminate some of the recursive calls by using integer division, i.e., the largest number of quarters that I can use to make a will be a / 25.

After that, I quickly wrote the following code in Python, and indeed this implementation evolved in order with precisely these tests:

import unittest

def countChange(amount, coins):
    if amount == 0:
        return 1
    if len(coins) == 0:
        return 0
    if len(coins) == 1 and amount % coins[0] == 0:
        return 1
    currentCoin = coins[0]
    remainingCoins = coins[1:]
    currentPossibilities = [currentCoin * i for i in range(0, amount / currentCoin + 1)]
    return sum([countChange(amount - p, remainingCoins) for p in currentPossibilities])

class TestCountChange(unittest.TestCase):
    def testAmountZeroWithNoCoins(self):
        self.assertEqual(1, countChange(0, []))
        
    def testAnyAmountWithNoCoins(self):
        self.assertEqual(0, countChange(100, []))
        
    def testAmountZeroWithAnyCoins(self):
        self.assertEqual(1, countChange(0, (1, 5, 10)))
        
    def testAmountsWithOneCoin(self):
        self.assertEqual(1, countChange(1, [1]))
        self.assertEqual(1, countChange(5, [5]))
        self.assertEqual(1, countChange(10, [10]))
        
    def testAnyAmountWithPennies(self):
        self.assertEqual(1, countChange(10, [1]))
        self.assertEqual(1, countChange(10000, [1]))
        
    def testMultiplesOfSingleCoin(self):
        self.assertEqual(1, countChange(100, [5]))
        self.assertEqual(1, countChange(100, [50]))
        
    def testTwoKindsOfCoins(self):
        self.assertEqual(2, countChange(10, [5, 10]))
        self.assertEqual(2, countChange(7, [5, 1]))
        self.assertEqual(0, countChange(7, [5, 10]))
        
    def testTextbookExample(self):
        self.assertEqual(292, countChange(100, [1, 5, 10, 25, 50]))

if __name__ == '__main__':
    unittest.main()

Generating A Regular Expression

A bioinformaticist recently posed an interesting problem to the RegexAdvice forum, where I like to lurk. Can a regular expression let me search for a pattern such as ATGGCACAGGTTATCCATTATCAGACCTTTACAAAAATCAGATAA, allowing exactly 1 mismatched character? Trust me, the patterns get a lot longer than this! Anyway, inexact matching algorithms would be too inefficient here: we know exactly how many mismatches we're allowed. On the other hand, I'm not sure that any solution could take advantage of optimized exact matching algorithms, whether those were part of a regex implementation or a custom implementation. At first, I considered how to write an expression that allowed a single mismatch somewhere in the pattern; then I realized that the general case, allowing m mismatches, is actually easier to write. I would like to present this work as part of a prospective talk on "test-driven development and recursive algorithms," or something like that, but to be honest, this provisional implementation was preceded by a lot of trial and error. At some point, however, I knew how the algorithm had to work, and how the expression had to look, and at that point, of course, it was easy to employ TDD.

OK, here it is, in Python:

import unittest

def expand(s, mismatches):
    assert mismatches <= len(s)
    # Only exact matching from this point on.
    if mismatches == 0:
        return s
    # All mismatches allowed.
    if mismatches == len(s):
        return '.' * mismatches
    # Branch: match the next character exactly, or mismatch.
    return [[s[0], expand(s[1:], mismatches)], 
           ['.', expand(s[1:], mismatches - 1)]]

def collapse(l):
    if type(l) == str:
        return l
    if type(l[0]) == str:
        # They're all strings, in this case.
        return ''.join(map(collapse, l))
    return '(' + '|'.join(map(collapse, l)) + ')'

class TestExpansion(unittest.TestCase):
    def testZeroMismatches(self):
        self.assertEquals('string', expand('string', 0))
        
    def testOneCharOneMismatch(self):
        self.assertEqual('.', expand('a', 1))
        
    def testMultipleCharsAllMismatches(self):
        self.assertEqual('..', expand('ab', 2))
        
    def testTwoCharsOneMismatch(self):
        self.assertEqual([['a', '.'], ['.', 'b']], expand('ab', 1))
        
    def testCollapseString(self):
        self.assertEqual('a', collapse('a'))
        
    def testCollapseTwoStrings(self):
        self.assertEqual('(a.|.b)', collapse([['a', '.'], ['.', 'b']]))
        
    def testThreeCharsOneMismatch(self):
        l = expand('abc', 1)
        self.assertEqual( [['a', [['b', '.'], ['.', 'c']]], ['.', 'bc']], l)
        r = collapse(l)
        self.assertEqual('(a(b.|.c)|.bc)', r)

if __name__ == '__main__':
    unittest.main()

And it seems to work, according to my understanding of what it should be able to do! I'd like to turn on "explicit capture only", to spare the expense caused by all those parentheses, but Python doesn't have that option:

>>> r.findall('tony bony tiny toby tonk toaa blah')
[('tony', 'ony', 'ny'), 
 ('bony', '', ''),
 ('tiny', 'iny', ''),
 ('toby', 'oby', 'by'),
 ('tonk', 'onk', 'nk')]
>>> 

Generating Column Fixtures for Collections Known at Runtime

I recently wanted to use FitNesse for regression testing of a set of data provided by the customer, namely, about 200 models for a rich client application with some very poorly written XML serialization code. I wanted to use the Visual Studio's XSD.EXE utility to generate the C# for all the classes, and then verify that serialization and deserialization worked as expected. I could not even be sure that the schema I inherited was complete, so I wanted to read each file using a validation XML parser, then reserialize the resulting object graph, read it in again and do some round-trip comparisons. Moreover, not all the models were still valid, so they might disappear from the directory, or new models might be dropped there, etc. To make a long story short, what I felt I needed was to be able to model a column fixture, with a "*" where the file name would appear, then generate the rows based on what was now in the directory. The markup would appear something like this:

!|Validation.BaseFileListingFixture|C:\FitNesse\dotnet|*.*|
|file name|do stuff?|
|*|0|

...and in this case the DoStuff() method would simply compare the file size to 0. Something like that.

The code works out differently in Java and C# (the former was easier; the latter required me to hack into Fit more than I would have liked). I can send you either one if you drop me a line. I had to eliminate the code from this posting because it ruined the format of the blog; can't have that!

Aww!

Welcome, Leo!

I have now been blessed with two lovely little boys: Carlo, age 4, and Leo, just a few days old!