SlideGuitarist

I just gave money to Wikipedia

2011-11-18T23:44:00.001-05:00

XSLT to Produce Multiple Results from a Single Input

2011-10-01T13:36:00.001-04:00

I was recently confronted with some XML structured in this way: a <person> at the top, followed by 0 or more entities to whom the person has a certain sort of relationship. These may include other persons, and the same persons may appear in several input documents. I’d like to split up all these documents, and apply additional XSLTs to them. Moreover, I can only decide on where the output XML is going to go based on information not available to the XSLT processor, i.e. I can’t simply calculate a URI in <xsl:result-document> and let the processor open the file for me. This is the first time I’ve used the Saxon processor’s setOutputURIResolver() method; in fact, I didn’t know it existed until I did some hunting in Eclipse.

Here’s what the input looks like, more or less:

<?xml version="1.0"?>
<person-with-relationships>
 <person id="1">
  <name>Anthony Albert Nassar</name>
  <phone-number>800-555-1212</phone-number>
 </person>
 <relationships>
  <relationship>
   <employment>
    <start-date/>
   </employment>
   <organization id="2">
    <organization-name>Palantir Technologies, Inc.</organization-name>
    <url>palantir.com</url>
   </organization>
  </relationship>
  <relationship>
   <marriage>
    <start-date/>
   </marriage>
   <person id="3">
    <name>Donavan Arizmendi</name>
   </person>
  </relationship>
 </relationships>
</person-with-relationships>

The XSLT looks like this:

<?xml version="1.0"?>
<xsl:stylesheet version="2.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xpath-default-namespace="">
 <xsl:import href="identity.xslt"/>

 <xsl:template match="relationship/*[2]">
  <xsl:message>Opening document for <xsl:value-of select="local-name()"/> with ID <xsl:value-of select="@id"/></xsl:message>
  <xsl:result-document href="{@id}.xml">
   <xsl:apply-imports/>
  </xsl:result-document>
 </xsl:template>

  <xsl:template match="/person-with-relationships/person">
  <xsl:message>Opening document for person with ID <xsl:value-of select="@id"/></xsl:message>
  <xsl:result-document href="{@id}.xml">
   <!-- Invoke the identity template, i.e. just copy this subtree to the output. -->
   <!-- If you have some local template with lower priority that you'd like to 
    invoke, use <xsl:next-match/>
   -->
   <xsl:apply-imports/>
  </xsl:result-document>
 </xsl:template>


</xsl:stylesheet>

Let’s say that I want to turn each output in a DOM, or a dom4j Document, before I do anything else with it, i.e. I can’t just write the output to files. Moreover, I want to avoid overwriting files I’ve already created, and I may need to aggregate information from all the inputs in a way not suited to XSLT (I could do some of this in XQuery…but I digress). The Java for this purpose might look like the following. I’m using dom4j to set the output subtrees aside. I could have used DOM (quel horreur), or, probably, something in Saxon, but I actually wanted to stay closer to JAXP. So:

package com.demo.xml;

import java.io.File;
import java.io.IOException;
import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.ConcurrentMap;

import javax.xml.transform.Result;
import javax.xml.transform.Templates;
import javax.xml.transform.Transformer;
import javax.xml.transform.TransformerException;
import javax.xml.transform.sax.TransformerHandler;
import javax.xml.transform.stream.StreamResult;
import javax.xml.transform.stream.StreamSource;

import net.sf.saxon.Controller;
import net.sf.saxon.FeatureKeys;
import net.sf.saxon.OutputURIResolver;
import net.sf.saxon.TransformerFactoryImpl;
import net.sf.saxon.event.SequenceWriter;
import net.sf.saxon.om.Item;
import net.sf.saxon.trans.XPathException;

import org.apache.commons.io.FileUtils;
import org.dom4j.Document;
import org.dom4j.io.DocumentResult;
import org.dom4j.io.DocumentSource;

import com.google.common.io.NullOutputStream;

public class InputSplitter {
       private final Templates splitterTemplates;

       // http://dhruba.name/2009/08/05/concurrent-set-implementations-in-java-6/
       private final ConcurrentMap<String,DocumentResult> urisProcessed = new ConcurrentHashMap<String,DocumentResult>();

       private final TransformerFactoryImpl factory;

       public InputSplitter() throws TransformerException {
              factory = new TransformerFactoryImpl();
              // I also have the requirement of removing elements with only 
              // whitespace nodes among their descendants. This attribute
              // lets the parser throw away such whitespace nodes. The 
              // XPath expression to discard elements with no content 
              // then becomes trivial.
              factory.setAttribute(FeatureKeys.STRIP_WHITESPACE, "all");
              File splitterXlstFile = new File("resources/splitter.xsl");
              // Calling newTemplates(), rather than newTransformer(), gives me 
              // on thread-safe object that I can use repeatedly. Each time I 
              // want to transform an input, I have to create a new Transformer.
              this.splitterTemplates = factory.newTemplates(new StreamSource(splitterXlstFile));
       }

       public void splitFile(File xmlFile) throws TransformerException {
              final StreamSource xmlSource = new StreamSource(xmlFile);

              TransformerHandler handler = factory.newTransformerHandler(splitterTemplates);
              Transformer transformer = handler.getTransformer();
              Controller controller = (Controller) transformer;
              // You might not want an anonymous implementation of OutputURIResolver,
              // but that's irrelevant to the example. In any case, this is Saxon's
              // back door to <xsl:result-document>.
              controller.setOutputURIResolver(new OutputURIResolver() {
                     @Override
                     public void close(Result result) throws TransformerException {
                           // If you opened a Stream in resolve(), you'd want to close it
                           // here.

                     @Override
                     public Result resolve(String href, String base) throws TransformerException {
                           DocumentResult result = new DocumentResult();
                           DocumentResult existingResult = urisProcessed.putIfAbsent(href, result);

                           if (existingResult == null) {

                                  return result;
                           } else {
                                  // Throw the results away. There might be a way to implement 
                                  // a null SAXResult, but I'll leave that as an exercise for the 
                                  // reader.
                                  return new StreamResult(new NullOutputStream());
                           }
                          
                     }});

              
              controller.setMessageEmitter(new SequenceWriter() {

                     @Override
                     public void write(Item item) throws XPathException {
                           System.out.println(item.getStringValue())

                    }});
              // Discard the output from the entire document.
              transformer.transform(xmlSource, new StreamResult(new NullOutputStream()));
       }

       public void transformFolder(File folder) throws TransformerException {
              for (File xmlFile : folder.listFiles()) {
                     splitFile(xmlFile);
              }
       }

       static public void main(String[] args) throws TransformerException, IOException {
              InputSplitter splitter = new InputSplitter();
              
              assert args.length == 2;
              File inputXml = new File(args[0]);
              splitter.splitFile(inputXml);
              
              final File outputDirectory = new File(args[1]);

              if (!outputDirectory.mkdirs())
                     FileUtils.cleanDirectory(outputDirectory);

              for (String entry : splitter.urisProcessed.keySet()) {
                     File outputFile = new File(outputDirectory, entry);
                     // Use the identity transform to turn the dom4j tree into a file.
                     Transformer newTransformer = splitter.factory.newTransformer();
                     newTransformer.setOutputProperty("indent", "yes");
                     Document document = splitter.urisProcessed.get(entry).getDocument();
                     newTransformer.transform(new DocumentSource(document), new StreamResult(outputFile));
              }
        }
}

Tokenizing a String with Oracle SQL

2011-09-08T11:53:00.003-04:00

This problem actually comes up pretty frequently for me. Audit log records at my place of employment are written to the DB. I often get requests to pull out and aggregate the objects IDs in a set of rows. The IDs are space-separated within a VARCHAR2 column. The details aren't that interesting, though.

The first trick to know is the by-now conventional way of generating a sequence of integers in Oracle SQL:


SELECT ROWNUM i FROM DUAL CONNECT BY LEVEL <= 10;

The 10 above is a necessary but arbitrary cutoff. My sample data happens to have < 10 tokens per row; if there were more, I'd boost the cutoff. Anyway, the next trick to know concerns Oracle's REGEXP_SUBSTR() function, namely that it has an optional argument for the match. You can see where this is going, right? If I JOIN each row of the audit log to the sequence of integers, then I can use the latter integers as match indexes.

Since Oracle's regex implementation doesn't include look-ahead operators, the token separator will be part of the match, and I'll have to remove it, hence TRIM(). If your data is comma-separated, your SQL will look a little different. But enough:


SELECT * FROM (
  SELECT s, i, TRIM(REGEXP_SUBSTR(s, '\d+( |$)', 1, i)) token FROM (
    SELECT '123 456' FROM DUAL
    UNION
    SELECT '789 101112' FROM DUAL
), (
  SELECT ROWNUM i FROM DUAL CONNECT BY LEVEL <= 10
  )
) WHERE token IS NOT NULL;

Refactoring Groovy to Generate XML

2011-09-07T22:31:00.001-04:00

There are tons of examples out there about how to generate XML using Groovy’s builders. The usual pattern is use StreamingMarkupBuilder, then create a massive nested closure resembling almost exactly the XML you want as output, then passing that to StreamingMarkupBuilder#bind(). This does create problems, though. The first is that even when the closure represents the structure of a single object with a data source and a few properties, it's already pretty big. The second is that it quickly gets cluttered with programmatic logic: checks for invalid property values, calls to some external function to translate or normalize some input, base-64-encoding of raw text or the content of external binary files, etc. I finally found out how to avoid these problems, after hours of trial and error. I might have saved myself that time if I’d just looked at the code for StreamingMarkupBuilder, but that’s life. In the following:


import groovy.xml.*

// Note that this function has no dependency on the instance of StreamingMarkupBuilder, below.
def createPersonMarkup(builder, name, occupation, age) {
    // Putting this check inside a function means I can just return, without
    // generating *anything*, yet not add a nesting level to my code.
        if (!value)
         return
    assert name // This assertion will fire only when the closure is bound!
    // Note the use of the "Elvis operator" to avoid a null attribute value.
    builder.person(occupation: (occupation ?: ‘Unemployed’)) {
         builder.name(name)
         if (occupation)
           builder.occupation(occupation)
    }
}

builder = new StreamingMarkupBuilder()

xml = builder.bind { 
    // This is the strange part: the builder actually gets passed into each closure,
    // but you have to declare a closure argument to get at it. You can't rely on the
    // variable declaration for "builder," above, because that binding is no longer available
    // when the Builder actually constructs the XML, and you'll get some hellacious error 
    // meaning, basically, "unbound variable name 'builder'".
    persons { builder -> 
        createPersonMarkup builder, 'Anthony Albert Nassar', null, 49
        createPersonMarkup builder, ‘Donavan Arizmendi’, ‘Teacher’, 40
    }
}

XmlUtil.serialize(xml, System.out)

If you don't name the single closure argument, it must already be available as "it," and so it is in this case. This code works:


xml = builder.bind {
    palantir {
       createPropertyAsRawValue it, 'com.palantir.property.Name', 'Anthony Nassar', null
    }
}

XmlUtil.serialize(xml, System.out)

So that's how the StreamingMarkupBuilder works: it interprets the strings that you intend as element names, as method invocations, and tries to invoke them on itself. The builder itself is always the first argument to any of these methods, and it passes itself into whatever methods (i.e. nested elements) are invoked in turn. When you call bind(), it intercepts all these method calls to generate XML.

Exporting Word Documents to HTML

2011-03-27T09:56:00.001-04:00

I mean real HTML. Here's what I get if I save this blog entry (which I'm editing in Word 2007) as HTML:

<html xmlns:v="urn:schemas-microsoft-com:vml" xmlns:o="urn:schemas-microsoft-com:office:office" xmlns:w="urn:schemas-microsoft-com:office:word" 
        xmlns:m=http://schemas.microsoft.com/office/2004/12/omml
        xmlns="http://www.w3.org/TR/REC-html40">
    <head>
        <meta http-equiv=Content-Type content="text/html; charset=windows-1252">
        <meta name=ProgId content=Word.Document>

If I save as "filtered HTML," I get something similar:

<html>
    <head>
        <meta http-equiv=Content-Type content="text/html; charset=windows-1252">
        <meta name=Generator content="Microsoft Word 12 (filtered)">

In the first case, I get a namespace declaration that I don't want. What I want is legitimate XHTML (http://www.w3.org/1999/xhtml). C'mon, people, it's 2011! I don't care who's using browsers or authoring tools that can't handle it; they should upgrade. What I really, really, really want, however, is not to export with the Windows-1252 character encoding. However, there seems to be no way to prevent that if it's the default encoding on your Windows machine. If you export to plain text, you can specify an encoding, but not if you export to HTML (as far as I can tell). Weird. What I also really, really, really want is attribute values enclosed in quotation marks, as has been the standard for, oh, about 12 years. If I attempted (I did attempt it, actually) to further process this HTML as XML, any proper XML parser would choke on it.

There are parsers, however, that will read this garbage and turn it into legitimate XHTML. I prefer TagSoup for this purpose. John Cowan, the author, recommends that you not use the JAXP interface, but that's exactly what I want. I'll demonstrate below.

Let me backtrack for a minute. A good part of my job at Palantir requires me to deal with unfriendly input and output formats. A lot of these formats are XML, and usually not very nice XML (if there's a schema, it's almost certain to be misleading). So I've gotten used to dealing with character encodings, and I've gravitated toward Groovy for a lot of my work, as I can often whip something up in minutes without needing an IDE. A colleague recently asked me, quite reasonably, if it would be "easy" to convert Word documents automatically to wiki markup. "Sure!" I said. It was not easy, as it turned out.

The first step was to convert every Word document on hand to HTML. I use Groovy+Scriptom to do this:

import org.codehaus.groovy.scriptom.ActiveXObject
import org.codehaus.groovy.scriptom.Scriptom
import org.codehaus.groovy.scriptom.tlb.office.word.WdSaveFormat
import org.codehaus.groovy.scriptom.tlb.office.MsoEncoding

userHome = new File(System.properties.'user.home')
myDocuments = new File(userHome, 'My Documents')
output = new File(userHome, "Desktop/Tony's Output")

def word = new ActiveXObject('Word.Application')
Scriptom.inApartment {
    try {
        word.Visible = false // ('Visible', new Variant(false))
        word.DisplayAlerts = false // ', new Variant(false))
        def documents = word.Documents // ').toDispatch()
        myDocuments.eachFileMatch ~/.*\.docx/, { doc ->    
            println "Opening $doc"
            documents.Open doc.absolutePath
            def activeDocument = word.ActiveDocument
            assert activeDocument
            try {
                activeDocument.AcceptAllRevisions()
                def html = new File(output, doc.name - ~/\.docx$/ + '.html')
                // 7 is the magic number for Unicode text. See MSFT's docs for WdSaveFormatEnumeration. 
                // http://msdn.microsoft.com/en-us/library/bb238158%28office.12%29.aspx
                // 17 is PDF; 16 is "default," thus Office 2007. 
                // wdFormatHTML = 8
                def n = Scriptom.MISSING
                activeDocument.SaveAs html.absolutePath, WdSaveFormat.wdFormatFilteredHTML, false, n, n, n, n, n, n, n, n, MsoEncoding.msoEncodingUTF8
            } finally {
                activeDocument.Close()
            }
        } // each
    } finally {
        // This is the Office automation API call, which Scriptom resolves for you.
        word.Quit()    
        // Apparently it now works: winword.exe disappears from my Task Manager, which is what I want.
    }
} // Close apartment.

I'm not going to explain Scriptom here. Suffice it to say that the code above does roughly what VBA would do. Scriptom can use the constants defined at http://msdn.microsoft.com/en-US/library/microsoft.office.interop.word.wdsaveformat.aspx because someone was thoughtful enough to copy them to http://groovy.codehaus.org/modules/scriptom/1.6.0/scriptom-office-2K3-tlb/apidocs/org/codehaus/groovy/scriptom/tlb/office/word/WdSaveFormat.html. Unfortunately, my attempt to specify the encoding for the output file failed, and I could have left off all the arguments to SaveAs() after the first two.

Now, unfortunately, I've got a folder of bad HTML. How do I turn that into XHTML (actually, I wanted to run that through a further XSLT, to produce wiki markup)? Like this:

import org.ccil.cowan.tagsoup.Parser
import org.xml.sax.*
import javax.xml.transform.*
import javax.xml.transform.sax.SAXSource
import javax.xml.transform.stream.StreamResult
import javax.xml.transform.stream.StreamSource

output.eachFileMatch ~/.*\.html/, { html ->
        def transformer = TransformerFactory.newInstance().newTransformer()
        new File(html.parentFile, html.name - ~/html$/ + 'xhtml').withWriter 'UTF-8', { writer ->
            html.withReader 'Windows-1252', { reader ->
                transformer.transform(new SAXSource(new Parser(), new InputSource(reader)), new StreamResult(writer));
            }
        }
}

TransformerFactory#newInstance() simply returns the "identity transform," which is what I want: I don't want to change the structure of the XML at all.

Interval Coalesce with XSLT

2011-03-26T15:00:00.001-04:00

I was intrigued by Vadim Tropashko's SQL Design Patterns. I'm not a SQL guy, so like lots of developers, I think of databases as places to put data, from which to retrieve it, and which occasionally need tuning. I don't think of the execution engine as something that virtually can create additional information for me. I've written maybe two pivot queries in my life, for example. Someone who's adept with Mathematica, or Excel for that matter, can do things in a minute that would take a Java developer days, since a SQL rowset is a very impoverished data structure in Java.

Anyway, I saw an immediate use for Tropashko's "interval coalesce" algorithm. The problem is, given a collection of intervals, to coalesce those that overlap, and thus produce a small collection of non-overlapping intervals. Well, "immediate" is misleading; I waited a year to do this. Anyway, I fired up Oracle XE and made up some data. Then I entered the query on p. 37…only to find out that there's a typo in it. Several hours later, I figured out where it was:

SELECT fst.x, lst.y -- Find two endpoints.

FROM intervals fst, intervals lst WHERE fst.x < lst.y

AND NOT EXISTS ( -- There's no interval beginning between these endpoints...

  SELECT * FROM intervals i

  WHERE i.x > fst.x AND i.x < lst.y

  AND NOT EXISTS ( -- ...for which there's no covering interval.

    SELECT * FROM intervals cov

    WHERE i.x > cov.x AND i.x <= cov.y

) AND NOT EXISTS (

  SELECT * FROM intervals cov

  WHERE cov.x < fst.x AND fst.x <= cov.y

  OR cov.x <= lst.y AND lst.y < cov.y

You might notice a discrepancy from the query in the book...and I've reported the erratum!

Tropashko goes on to show a more elegant and efficient way to produce this result, but at this point I wanted to get back to my own practical problem, which was to coalesce intervals defined in an XML document. Since the query above involves three self-joins, I could expect n^4 performance if I simply turned Tropashko's SQL into XPath. However, an XML document is inherently ordered (there's no ANSI SQL equivalent to following-sibling::*[1]). If I sorted the intervals according to their left end, i.e. wrote an XSLT to preprocess the input, then I could simply iterate through the intervals one time, gradually coalescing them where possible. The code falls into a pattern familiar to functional programmers. In other words, I apply a template to the first interval in the document, and that template calls a second template that uses "accumulators" for the current coalesced interval. This pattern is also used in Jeni Tennison's (http://www.jenitennison.com/xslt/index.html) <span style="font-style: italic;">XSLT on the Edge</span> as a way of grouping adjacent elements. I wanted to avoid XPath stunts like Tropashko's SQL, because I will have to apply this transform to documents with 10s of 1000s of data points. I very deliberate select only following-sibling::*[1].

Since blogger's editor widget hacks up my XSLT in horrifying ways, and I can't attach text files, I had to format this XSTL with non-breaking spaces and whatnot. Let me know if you want the real thing. Let's say the input looks like this (it must be sorted, perhaps by another XSLT, by starting time only):

<?xml version='1.0' ?>
<intervals>

<interval x="10" y="14.1155607415243584888223696987094362306"/>

<interval x="10" y="27.2574271976039591982711142331954001295"/>

<interval x="30" y="33.7147910106524433624672477551503835313"/>

<interval x="40" y="46.844920420920822280815378491005656766"/>

<interval x="50" y="61.30421963829719394371538034317434986025"/>

…

Then the XSLT to coalesce these intervals will look about like this:

<?xml version="1.0"?>
<xsl:stylesheet version="2.0"

xmlns:xsl="http://www.w3.org/1999/XSL/Transform"

xmlns:xs="http://www.w3.org/2001/XMLSchema">

<xsl:output indent="yes"/>



<xsl:template match="interval">

<xsl:call-template name="coalesce-intervals">

<xsl:with-param name="next-interval" select="."/>

<xsl:with-param name="from" select="number(@x)" tunnel="yes"/>

<xsl:with-param name="to" select="number(@y)" tunnel="yes"/>

</xsl:call-template>

</xsl:template>

<xsl:template name="coalesce-intervals">

<xsl:param name="next-interval" as="element(interval)?"/>

<xsl:param name="from" as="xs:double" tunnel="yes"/>

<xsl:param name="to" as="xs:double" tunnel="yes"/>

<xsl:choose>



<xsl:when test="not($next-interval)">

<interval x="{$from}" y="{$to}"/>

</xsl:when>



<xsl:when test="$to gt number($next-interval/@x)">

<xsl:call-template name="coalesce-intervals">

<xsl:with-param name="next-interval" select="$next-interval/following-sibling::interval[1]"/>



<xsl:with-param name="to" select="max((number($next-interval/@y), $to))" tunnel="yes"/>

</xsl:call-template>

</xsl:when>

<xsl:otherwise>



<interval x="{$from}" y="{$to}"/>

<xsl:apply-templates select="$next-interval"/>

</xsl:otherwise>

</xsl:choose>

</xsl:template>

<xsl:template match="/intervals">

<intervals>

<xsl:apply-templates select="interval[1]"/>

</intervals>

</xsl:template>
</xsl:stylesheet>

Converting Oracle TIMESTAMP WITH TIME ZONE to Current TZ

2009-08-21T08:50:00.002-04:00

I see answers to this question all over the Web, usually involving some arithmetic with abbreviations such as "EDT", the use of hacky Oracle extension functions such as NEW_TIME, etc. Forget about that. Here's how you do it: use CAST(). If this seems pedantic, it's not. I recently had to deal with an Oracle database in which times were stored as epoch times, i.e. milliseconds since January 1, 1970 UTC (e.g. new java.util.Date().getTime()). So you can get the beginning of the epoch in Oracle SQL like so:

SELECT TIMESTAMP '1970-01-01 00:00:00 +00:00' FROM DUAL;

That'll get you a timestamp in terms of Greenwich Mean Time (GMT or UTC):

SELECT TO_CHAR(TIMESTAMP '1970-01-01 00:00:00 +00:00', 'TZR') FROM DUAL;

If I've got "epoch time" in ms, I can easily convert it to a timestamp relative to UTC:

SELECT TIMESTAMP '1970-01-01 00:00:00 +00:00' + NUMTODSINTERVAL(epoch_time / 1000, 'SECOND') FROM my_table;

How do I then display, and especially export these values relative to my current time zone? Casting to TIMESTAMP WITH LOCAL TIME ZONE doesn't quite work; by default, the time zone isn't displayed for this column, and the 'TZR' format doesn't work on it (I get an Oracle error, which confused me. So CAST() them to TIMESTAMP WITH LOCAL TIME ZONE, then CAST() to TIMESTAMP WITH TIME ZONE. Oracle does all the work, and I don't have to hard-code any information in the query about my time zone, or rely on EXTRACT(). So:

SELECT CAST(CAST(TIMESTAMP '1970-01-01 00:00:00 +00:00' AS TIMESTAMP WITH LOCAL TIME ZONE) AS TIMESTAMP WITH TIME ZONE) FROM DUAL;

An XSLT to Extract Text from Word

2009-07-22T00:36:00.005-04:00

Well, this turns out to be even easier. If you've got the text:

<?xml version="1.0" encoding="utf-8"?>
<xsl:stylesheet xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
       xmlns:w="http://schemas.openxmlformats.org/wordprocessingml/2006/main"
       version="1.0">

  <xsl:output method="text" encoding="UTF-8" />

  <xsl:template match="*">
    <!-- Simply recurse over the children. -->
    <xsl:apply-templates />
  </xsl:template>
 
  <!-- Any piece of text from the .docx is enclosed in a w:t element. -->
  <xsl:template match="w:t">
    <xsl:value-of select="."/>
    <!-- Look for the xml:space attribute. A namespace is not necessary. -->
    <!-- XPath 1.0 doesn't have the starts-with() and ends-with() functions, unfortunately. -->
    <xsl:if test="@space = 'preserve'">    
   <xsl:text> </xsl:text>
    </xsl:if>
  </xsl:template>
  
  <xsl:template match="w:p">
    <xsl:apply-templates />
    <xsl:text>&#xa;</xsl:text>
  </xsl:template>
  
 </xsl:stylesheet>

To get the text, here's some Groovy:


def createDocumentXml(f) {
    def zip = new ZipFile(f)
    def entry = zip.getEntry('word/document.xml')
    assert entry
    def xml =  new File(f.absolutePath - '.docx' + '.xml')
    // I want to copy the XML to a file, for purposes of visual inspection.
    // In production code I'd simply return the stream.
    zip.getInputStream(entry).withStream { i ->
        xml.withOutputStream { o ->
            o << i
        }
    }
    return xml
}

To apply the XSLT to the document, see the attachments.

Extracting the Text of an HTML Document

2009-05-02T14:14:00.007-04:00

This is something I often have to do within an XSLT: there's some base-64 encoded HTML in a text node, and I'd like to extract the body text. Saxon offers saxon:parse() and saxon:base64Binary-to-string() that might be useful here. If you use the TagSoup parser to turn possibly nasty HTML into XHTML, then you can extract the text from the "thing" element with


<xsl:variable name="html" select="saxon:parse(saxon:base64-to-string(xs:base64(thing)))"/>
<xsl:value-of select="$html/xhtml:body//xhtml:*[local-name() != 'script']/text()" separator=""/>

Saxon's parse() function will fail if you don't direct Saxon (from the command line, or programmatically) to use the TagSoup parser. OTOH, you could resort to Groovy. Put TagSoup on your CLASSPATH, and:


import org.ccil.cowan.tagsoup.*

parser = new Parser()
// TagSoup offers loads of interesting options...check 'em out!
f = new File('C:\\Documents and Settings\\tnassar\\Desktop\\Efficient.html')

As we're reminded here, we can probably do without the namespace declarations. I quote:

name or "*:name" matches an element named "name" irrespective of the namespace it's in (i.e. this is the default mode of operation)
":name" matches an element named "name" only id the element is not in a namespace
"prefix:name" matches an element names "name" only if it is in the namespace identified by the prefix "prefix" (and the prefix to namespace mapping was defined by a previous call to declareNamespace)

Anyway, force of habit:

html = new XmlSlurper(parser).parse(f).declareNamespace(xhtml: 'http://www.w3.org/1999/xhtml')

html.'xhtml:body'.depthFirst().findAll { it.name() != 'script' }*.text().join('\n')

Extracting the Text from a Word Document w/ Groovy

2009-05-02T13:44:00.005-04:00

As I'm doing a lot of data munging these days, and often have to talk to Java APIs. Since I'm not writing production code, don't have lots of RAM or lots of good tools at my disposal and therefore would just as soon use a text editor (SciTE's my current preference...no, I can't get the Win32 port of emacs!), Groovy is definitely my best choice. Notwithstanding my preference for XSLT (over GPath) to handle XML, I can't deny that you can do some slick stuff w/ GPath. At another munger's request, I cooked this up in 5 minutes, and was almost shocked at how easy it was to get the text out of an Office 2007 docx file:


import java.util.zip.*

docx = new File('C:\\Documents and Settings\\tnassar\\My Documents\\Efficient.docx')
zip = new ZipFile(docx)
entry = zip.getEntry('word/document.xml')
stream = zip.getInputStream(entry)

// The namespace was gleaned from the decompressed XML.
wordMl = new XmlSlurper().parse(stream).declareNamespace(w: 'http://schemas.openxmlformats.org/wordprocessingml/2006/main')

// The outermost XML element node is assigned to the variable wordMl, so
// GPath expressions will start after that. To print out the concatenated
// descendant text nodes of w:body, you use:

text = wordMl.'w:body'.children().collect { it.text() }.join('')

println text

It would be nice if Groovy offered "raw strings" like Python--r'C:\Documents and Settings\...'--or C#, which lets you prepend a '@' to have backslashes treated literally--esp. when it comes to Windows pathnames, but whatever.

This will not work well for complex document formats (I can imagine that tables and such would be a disaster), but for me it was just enough.

Efficient “Disjoint Sets” Implementation in XSLT

2008-10-25T14:01:00.001-04:00

I actually had to revisit this problem with slightly different input, and once again I struggled. If I represent an undirected graph like this:

<?xml version="1.0"?>
<graph>
    <nodes>
        <node id="1"/>
        <node id="2"/>
        <node id="3"/>
        <node id="4"/>
        <node id="5"/>
    </nodes>
    <links>
        <link end1="1" end2="2"/>
        <link end1="1" end2="3"/>
        <link end1="1" end2="4"/>
        <link end1="1" end2="5"/>
    </links>
</graph>

…then it's a little harder to go from one node to its connected nodes, because the information I need is elsewhere in the XML document (i.e. not in a child node of the <node> element) . To index any node element, I'd have to navigate up the tree, and back down to the links. What's worse, I'd have to scan all the links for every node. So the solution involves some indirection. First I declare these two mappings:

<xsl:key name="left" match="/graph/links/link" use="@end1"/>
<xsl:key name="right" match="/graph/links/link" use="@end2"/>

Now I map each node (its ID, actually; remember that the key has to be of an atomic type) to its connected nodes by going through these mappings (such a recursive definition is not possible in XSLT 1.0, I believe). Note that for links that were indexed by @end1, I'm interested in the value of @end2, and v.v.

<xsl:key name="connected" match="node" use="key('left', @id)/@end2, key('right', @id)/@end1"/>

Finally, I can use this mapping:

<xsl:template match="/">
        <connectivity>
            <xsl:for-each select="graph/nodes/node">
                <node id="{@id}">
                    <connected-to>
                        <xsl:value-of select="key('connected', @id)/@id"/>
                    </connected-to>
                </node>
            </xsl:for-each>
        </connectivity>
    </xsl:template>

I believe that these are all the data structures I need. Now I can implement the "strongly connected components" algorithm as I did below, but using set operators on the nodes.

Graph Algorithms in XSLT

2008-10-03T17:21:00.008-04:00

Notwithstanding that XSLT can be considered a functional programming language, you probably wouldn't choose to implement algorithms in it. Nonetheless, I recently had to split a very large XML document into smaller pieces (using xsl:result-document), and I wanted to redundancies between the outputs. So what I essentially wanted to do was separate elements in the input into "strongly-connected components." XSLT 2.0 provides lots of operators on sequences and sets, and allows you to define property functions, but what it does not lend itself to is the creation of new data structures. To be more precise, the data structures you'd need for depth-first search or Tarjan's disjoint sets would require you to copy elements into new structures. Easy, if you're working in a language that has pointer or reference equality; not possible in XLST. However, if you assume that the XSLT processor will use hash tables to represent sets, and you put that together with <xsl:key>, you can try a different approach.

Here's the input I want to process:

<?xml version="1.0"?>
  <data>
    <documents>
    <document id="a">
      <related-entities>1 2 3</related-entities>
    </document>
    <document id="b">
     <related-entities>2 3 4</related-entities>
    </document>
    <document id="c">
      <related-entities>5 6 7</related-entities>
    </document>
    <document id="d">
      <related-entities>7 8 9</related-entities>
    </document>
    <document id="e">
      <related-entities>10</related-entities>
    </document>
  </documents>
  <entities>
    <entity id="1"/>
    <entity id="2"/>
    <entity id="3"/>
    <entity id="4"/>
    <entity id="5"/>
    <entity id="6"/>
    <entity id="7"/>
    <entity id="8"/>
    <entity id="9"/>
    <entity id="10"/>
  </entities>
</data>

I'm going to create a hashmap (actually, a hashmultimap) from entity IDs to documents, and vice versa. Note that the keys have to be of an atomic value type, and the values have to be elements. You can't map, say, integers to strings. Alright: for any document I can get the list of entity IDs, and use them as keys pointing back to the document element. So if any two documents point to the same entity, those two documents (and, obviously, the entity as well) must belong in the same strongly-connected component. For a sequence of entity IDs I can create a set of document elements; I then have to determine if this set intersects with the set I've already accumulated. If yes, I union both sets and recurse; otherwise I spit out the subgraph, pop the stack, and resume with the next, as-yet-unselected document.

<?xml version="1.0"?>
<xsl:stylesheet version="2.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform" xmlns:xs="http://www.w3.org/2001/XMLSchema" xmlns:fn="subgraphs">
  <xsl:key name="linked-documents" match="/data/documents/document" use="tokenize(related-entities, ' ')"/>
  <xsl:key name="linked-entities" match="/data/entities/entity" use="key('linked-documents', @id)/@id"/>
  <xsl:template match="document">
    <document id="{@id}"/>
  </xsl:template>
  <xsl:template name="create-subgraph">
    <xsl:param name="subgraph" as="element(document)*"/>
    <xsl:param name="selection" as="element(document)*" />
    <xsl:message select="string-join($subgraph/@id, ',')" />
    <xsl:message select="string-join($selection/@id, ',')" />
    <xsl:choose>
      <!-- If there are no more elements to select from, the subgraph is complete (even if empty). -->
      <xsl:when test="not($selection)">
        <subgraph>
          <xsl:apply-templates select="$subgraph"/>
        </subgraph>
      </xsl:when>
      <xsl:otherwise>
        <xsl:variable name="linked-entities" as="element(entity)*" select="for $d in $subgraph return key('linked-entities', $d/@id)"/>
        <xsl:message select="string-join($linked-entities/@id, ',')" />
        <xsl:variable name="subselection" select="$selection[key('linked-entities', @id) intersect $linked-entities]"/>
        <xsl:message select="string-join($subselection/@id, ',')" />
        <xsl:choose>
          <xsl:when test="$subselection">
            <xsl:call-template name="create-subgraph">
              <xsl:with-param name="selection" select="$selection except $subselection"/>
              <xsl:with-param name="subgraph" select="$subgraph|$subselection"/>
            </xsl:call-template>
          </xsl:when>
          <xsl:otherwise>
            <subgraph>
              <xsl:apply-templates select="$subgraph"/>
            </subgraph>
            <xsl:variable name="new-selection" select="$selection except $subselection"/>
            <xsl:call-template name="create-subgraph">
              <xsl:with-param name="selection" select="$new-selection[position() gt 1]"/>
              <xsl:with-param name="subgraph" select="$new-selection[1]"/>
            </xsl:call-template>
          </xsl:otherwise>
        </xsl:choose>
      </xsl:otherwise>
    </xsl:choose>
  </xsl:template>

  <xsl:template match="/">
    <subgraphs>
      <xsl:call-template name="create-subgraph">
        <!-- Make the first document element an SCC. -->
          <xsl:with-param name="subgraph" select="/data/documents/document[1]"/>
          <xsl:with-param name="selection" select="/data/documents/document[position() gt 1]"/>
        </xsl:call-template>
      </subgraphs>
  </xsl:template>
</xsl:stylesheet>

In the end, sure enough, I get:

<subgraphs xmlns:fn="subgraphs" xmlns:xs="http://www.w3.org/2001/XMLSchema">
  <subgraph>
    <document id="a"/>
    <document id="b"/>
  </subgraph>
  <subgraph>
    <document id="c"/>
    <document id="d"/>
  </subgraph>
  <subgraph>
    <document id="e"/>
  </subgraph>
</subgraphs>

Yes, defining one mapping in terms of another is allowed in XSLT 2.0. The problem I had at work was actually more complicated: the entities were in entirely separate XML documents. The trick there, which cost me some sweat, was to define one mapping, which pointed from a document immediately to other documents. However, I'll put off that explanation until someone asks for it.

How to Convert Julian Dates to Gregorian

2008-07-18T21:48:00.010-04:00

I'm writing Java / Jython / Groovy these days, not F#, at a new job, and haven't had time to maintain this blog, but I did want to post one little snippet that I was surprised not to find elsewhere. I've had to ingest 10s of 1000s of records from a customer's Microsoft Access database, and the dates are represented in Julian format. Not relative to the Julian calendar; I mean the number of days since a particular Day 0. For Microsoft Access, Day 0 is December 30, 1899. If Microsoft Access interests you, read up on it here.

Anyway, there are quite a few Web pages out there describing how to do it in Excel or T-SQL, but none describing how to do it in Java. Actually, it's ridiculously easy, which doesn't say much for me. Here's the solution in Jython:


from java.util import *

def convertJulian(julian):
    calendar = Calendar.getInstance()
    # Why in God's name are months in Java 0-based?
    # This is December 30, 1899.
    calendar.set(1899, 11, 30)
    calendar.add(Calendar.DATE, julian)
    return calendar.time

D'oh! Set Day 0, add the days, and you're good to go. Now in Java:


private static Date convertJulian(final int julian) {
    Calendar calendar = Calendar.getInstance();
    calendar.set(1899, 11, 30);
    calendar.add(Calendar.DATE, julian);
    return calendar.getTime();
}

Finally, as XSLT (you'll need an XSLT 2.0-compliant processor for this):


 <xsl:function name="local:convert-access-date" as="xs:date">
  <xsl:param name="access-date" as="xs:integer"/>
  <xsl:variable name="days-since-zero" as="xs:dayTimeDuration"
    select="xs:dayTimeDuration(concat('P', $access-date, 'D'))"/>
  <xsl:sequence select="$zero + $days-since-zero"/>
 </xsl:function>

John Cage for Children

2008-05-24T14:23:00.011-04:00

Imagine my surprise when I came home from work a few days ago to find this album blasting from my Meadowlark speakers. I did buy them to listen to art music, not Wiggles DVDs, but I didn't expect my toddler to rummage through my CDs and pick this one to play. Kids today grow up so fast!

Here's the album I want him to listen to though, because I want to train him to be normal. Komar and Melamid, those jokesters, have assembled musical material that people say they like, result in "a musical work that will be unavoidably and uncontrollably 'liked' by 72 ± 12% of listeners ((standard deviation; Kolmogorov-Smirnov statistic)." I have to admit that I prefer the composition that only 200 people in the world are supposed to like; it sounds to me like John Cage sounds to those other people. You can listen to recordings of both here. The unpleasant recording had to be fun to make; the pleasant one sounds like a bored Alicia Keys cover band playing at an airport lounge.

Counting Change Again?

2008-05-04T20:08:00.009-04:00

Problem 76 at Project Euler is really just the "change counting" problem: how many ways can you count out 100 cents if you have coins in denominations from 1 to 99? However, when I plug those values into my previous implementations of the change counting algorithm, it runs forever...well, maybe not forever, but for hours and hours, while using 100% of my RAM. OK, so that's not going to work. At first I thought that the problem was simply that too many of the answers were in memory (i.e. sequences of coins), so I changed the implementation, simply to count possible answers:


let rec countChange =
    match coins, amount with
    ¦ _, 0 -> 1L
    ¦ [], _ -> 0L
    ¦ h::t, _ -> [ 0..h..amount ]
                 ¦> List.map (fun amt' -> countChange t (amount - amt'))
                 ¦> Seq.fold1 (+)

Let's review this. How many ways are there to make 0 in change, whatever the available coins? There's 1 way. How many ways are there to make some other quantity in change if you have no coins? 0. Finally, how many ways are there to make C in change if you have a a list of coins h::t? Partition the problem thus: use the coin h to pay out a partition of C (obviously you can use coin h up to C/h times), then make up the remaining partition of C with the rest of the list. If, to solve each subproblem, you're dividing C by the denomination of a coin, then the size of the problem space is exponential in the number of denominations: (C/denomination₁) * (C/denomination₂) * ... * (C/denomination_n) = O(Cⁿ). You can't exactly tell from this example, but the rate of growth here is clearly superpolynomial:


> countChange [ 4; 5 ] 20;;
val it : int64 = 2L
> countChange [ 3; 4; 5 ] 20;;
val it : int64 = 6L
> countChange [ 3; 4; 5; 6 ] 20;;
val it : int64 = 11L
> countChange [2;  3; 4; 5; 6 ] 20;;
val it : int64 = 47L
>

Anyway, it should be clear why there's no point in waiting for the solution to countChange [ 1..99 ] 100. However, I can memoize the change counting algorithm, since it's deterministic: for a given amount, and a given set of coins, the answer is always the same (commerce would be hopeless otherwise). This turns out to be fairly easy, notwithstanding the two arguments to the function. Here's my answer:


open System.Collections.Generic;;

let memoize f =
    let cache = Dictionary<_,>()
    fun x y ->
        if cache.ContainsKey((x, y)) then cache.[(x, y)]
        // Remember that f will always consult the memo
        // for subproblems.
        else let result = f x y
             cache.[(x, y)] <- result              
             result  

let rec countChange =   
  // Turn this into a function that returns a function.   
  // The *returned* function will be evaluated over the arguments.   
  let countChange' coins amount =      
    match coins, amount with     
    ¦ _, 0 -> 1L     
    ¦ [], _ -> 0L     
    ¦ h::t, _ -> [ 0..h..amount ]                   
                 ¦> List.map (fun amt' -> countChange t (amount - amt'))
                 ¦> Seq.fold1 (+)
  memoize countChange'

The answer shows up in a few seconds. Since F# lists are immutable, they can easily be compared for reference equality, rather than in O(n²) time. That is, the initial list [ 99..(-1)..1 ] is a 99 prepended to the list [ 98..(-1)..1 ], and so on. We partition the problem into subproblems corresponding to the head and tail of the list, but no additional lists are created beyond the argument to the function (there's only one list beginning with 50, ever, and it's the tail of the list beginning with 51). Microsoft.FSharp.Collections.List<_>.CompareTo() sees literally the same lists again and again when called from memoize(). Hence the lickety-split performance.

Perhaps this could all be done imperatively, though I don't how OOP is at all applicable to this sort of classic optimization problem (what could justify a Coin class here)? If you haven't read Daniel Friedman's "The Role of the Study of Programming Languages in the Education of a Programmer," here's your chance. As my buddy George Paci puts it, "The title is clearly written by a professor; a marketing guy would have called it something like, 'Holy Crap! It's Amazing What You Can Do with Program Transformations!'"

Agent Less Than Zero

2008-04-30T21:02:00.002-04:00

I just started a new job, and I'm writing a lot of Java all of a sudden. Hey, maybe I'll learn Scala and piss off my new colleagues just as I was pissing people off with F# a few weeks ago! Or maybe I'll put off blogging about F# for a few weeks until I get settled in. I have been using F# to solve Project Euler problems, but I feel guilty blogging about those, since I'd have to give away answers.

In the meantime, I have to agree with Charles Barkley, who said, "I think the Washington Wizards have got to be the dumbest team in the history of civilization." I think that Caron Butler is a smart player, mind you, and he *should* have had the ball in his hands at the end of tonight's game.

Memoization, etc.

2008-04-02T09:21:00.005-04:00

I've been sweating over some problems at Project Euler, and I've verified that I'm no mathematician. Some enterprising Haskell programmers got there way before I did, and if I were inclined to cheat, I'd simply translate their solutions into F#. However, in the effort or out of the necessity to remain pure, they don't use for-loops over arrays, or their own memoization, which I'd almost certainly do for any production code that had to calculate the Fibonacci series...well, actually, I don't do that kind of work. Anyway...

I did find the Haskell samples instructive, though I don't want to get sidetracked from my project of learning F#. To this end I've once again resorted to Don Syme's thoughts on memoization: here on the CAML list, and here more recently, where he avails himself of some popular .NET collections. So a memoized Fibonacci function in Dr. Syme's older formulation looks like this:


> #light;;

> let cache f =

-   let table = ref [] in

-   fun n ->

-      try

-        List.assoc n !table

-      with Not_found ->

-        let f_n = f n in

-           table := (n, f_n) :: !table;

-           f_n

-

-

- let rec fib_mem =

-    cache (function

-              // You'd better return a bigint, not an int!

-              ¦ 0 -> 0I

-              ¦ 1 -> 1I

-              ¦ n -> fib_mem (n - 1) + fib_mem (n - 2))

-

-

- ;;



val cache : ('a -> 'b) -> ('a -> 'b)

val fib_mem : (int -> bigint)


> fib_mem(1000);;

val it : bigint

= 434665576869374564356885276750406258025646605173717804024817290895365554179490

51890403879840079255169295922593080322634775209689623239873322471161642996440906

533187938298969649928516003704476137795166849228875I

val ns : seq

Several problems at Project Euler ask you to do something with the first 10 or last 10 digits of some big integer; for anyone who was wondering how to do that with a number such as the one above, here's one way:


> fib_mem(1000) |> Seq.unfold (fun n -> if n > 0I
-                                         then
-                                          let quotient,remainder = BigInt.divmod n 10I
-                                          Some (remainder, quotient)
-                                        else
-                                          None);;
val it : seq = seq [5I; 7I; 8I; 8I; ...]
>

You'll notice that the least significant digits appear first, which is of course by design, since dividing by 10 is probably cheap. The last thing I'd want to do is reverse this sequence, i.e.


-               |> List.of_seq
-               |> List.rev;;

I could clean this up further by applying BigInt.to_Int32 to the generated elements, etc. To sum the first 10 digits (note that this is *not* the Project Euler problem; I'm not about to give away any answers) I could go further, like so:


-               |> Seq.take 10
-               |> Seq.fold1 (+);;

You get the idea.

Munging with Active Patterns

2008-03-11T16:53:00.007-04:00

Have you checked out active patterns yet? C'mon! Here's what the code below might have looked like if I'd used them:


> open System;;

> open System.Text.RegularExpressions;;

> let re = new Regex("^(MON¦TUE¦WED¦THU¦FRI¦SAT¦SUN)", RegexOptions.Compiled);;

val re : Regex
> let (¦DataRow(¦_¦) (s : string) =
-     if re.IsMatch s
-         // Here I'd want to break the line down.
-     then Some(1, 2, "Hello!")
-     else None

val ( ¦DataRow¦_¦ ) : string -> (int * int * string) option

As I said earlier, Seq.choose will through out None, and I could then handle different kinds of data rows from the input:


> match "TUE" with
- ¦ DataRow(x, y, s) -> Console.WriteLine(s)
- // Additional cases here...
- ¦ _ -> Console.WriteLine("Got bupkes!");;
Hello!
val it : unit = ()

Munging Data in F#, Again

2008-03-10T09:54:00.015-04:00

I couldn't help myself. I was recently asked to take a coding test to prove my fitness for a potential new job, and I figured I could do it more quickly in F#, interactively. I wouldn't have to fire up Visual Studio, I wouldn't have to create an executable project with NUnit tests and debuggability and all that ceremony. But really, my dabblings in functional programming have taught me that decomposition into classes is not always the natural way to decompose a problem. Why do I need any classes at all to do this exercise?


> #light;;
> open System.Text.RegularExpressions;;
> let r = new Regex("^(MON¦TUE¦WED¦THU¦FRI¦SAT¦SUN)", RegexOptions.Compiled);;

The line must start with one of these abbreviations. Hey, Blogger keeps taking out the vertical bars between the abbreviations; if they're missing, don't get distracted. Then I want to turn the file into a sequence of strings, i.e. IEnumerable<string>. A "use" as opposed to a "let" binding ensures that the Close() or Dispose() is finally called. See Don Syme's blog for examples (this example, actually, which I simply copied). It's more or less like a C# function that returns IEnumerable<_> by means of "yield return."


> let reader =
- { use reader = new StreamReader(File.OpenRead(@"C:\...\input.txt"))
-   while not reader.EndOfStream do
-   yield reader.ReadLine() };;
// Filter out the lines that aren’t data rows.
> let filtered = reader ¦> Seq.filter (fun line -> r.IsMatch line);;
> open System;;

Now decompose the line into the parts we’re interested in, based on the (assumed) fixed format. If you want to get your mind blown by "active patterns," dig my man Don Syme.


> let (¦Record¦) (line : string) =
- let transientSold = Int32.Parse(line.Substring(67, 7))
- let definite = Int32.Parse(line.Substring(25, 3))
- let tentative = Int32.Parse(line.Substring(19, 3))
- let date = line.Substring(5, 11)
- // Return the tuple of interesting values.
- date, transientSold, definite, tentative;;
// This should really be embedded in a function!
> open System.Xml;;
> let xml = XmlWriter.Create("output.xml");;
> xml.WriteStartDocument();;
> xml.WriteStartElement("Sample");;

Now pass the filtered lines through a function that decomposes the line into fields we care about, and output an XML element per. Seq.iter applies a function with side-effects but no return value to every element in a sequence.


> filtered ¦> Seq.iter (fun line ->
- match line with
- ¦ Record(date, ts, d, t) -> xml.WriteStartElement("Thing")
-   xml.WriteElementString("Date", date)
-   xml.WriteElementString("TransientSold", XmlConvert.ToString(ts))
-   xml.WriteElementString("CommitmentsDefinite", XmlConvert.ToString(d))
-   xml.WriteElementString("CommitmentsTentative", XmlConvert.ToString(t))
-   xml.WriteEndElement()
- );;
val it : unit = ()
// Likewise, this should have been put into the function I inlined above.
> xml.WriteEndElement();;
val it : unit = ()
> xml.Close();;
val it : unit = ()

I could have made some different choices here. First of all, opening an XmlWriter in one function, or directly from the command line, then closing it the same way, is rather ugly. If a function is the unit of encapsulation in functional programming, then one function should really own the writer via a use-binding. So I could do something like this:

filtered ¦> (fun lines -> 
                                use xmlWriter = XmlWriter.Create("output.xml")
                                xmlWriter .WriteStartDocument()
                                xmlWriter .WriteStartElement("Sample")
                                // Yes, it's a loop!
                                for line in lines do
                                    // Create each element...
                            )

The following may be too cute:

filtered  ¦> Seq.fold (fun () -> let xmlWriter = ...
                                                 xmlWriter.WriteStartDocument()
                                                 // additional initialization
                                                 xmlWriter
                                      )
                                      (fun writer line -> 
                                                 // Add an element to the XmlWriter.
                                                 writer
                                      )
                  ¦> (fun writer -> writer.Close())

A significant change would have been to use an active pattern to both look for lines of interest and decompose them into interesting tuples. In this case I either keep the line or throw it out, but there might be several data row formats that I care about. In this event I could use active patterns to discriminate between them, and embed any regular expressions in the pattern function. Furthermore, I could use Seq.choose instead of Seq.filter, because the former passes over None. If I get a chance tonight, I'll write that code out.

Munging some XML with F# & Linq

2008-02-02T17:03:00.000-05:00

I recently wanted to change the format of a test script, and canonicalize a flattened listing of all the regression test models. So I set myself the goal of doing it in F#, which would force me to use some of the language features I'd only read about, and possibly prod me to use some LINQ as well. I could have done this transformation manually in about an hour, I admit. And I learned that if I really want to transform a lot of XML to XML, I'd rather do it via XML, i.e. XSLT. However, Microsoft doesn't offer XSLT 2.0 compliancy, so I have less to gain from learning to do it that way (meaning, I'm stuck with the .NET XsltCompiledTransform implementation at work). What I would have needed is the tokenize function (to split up pathnames on the '\\' character), XSLT functions that could return Boolean values, and the ability to select groups. Anyway, that's what I did below.


#light

open System
open System.Xml
open System.Linq
open System.Xml.Linq
open Microsoft.FSharp.Linq
open Microsoft.FSharp.Xml.Linq
open Microsoft.FSharp.Linq.SequenceOps
open Microsoft.FSharp.Xml.Linq.SequenceOps

let doc = XDocument.Load @"knownSolutions.xml"

// Simply tagged aliases for these various tuples. I want to create 
// a tree of these, then finally convert them back to XML.      
type Node =
| File of string * XElement
| Directory of string * Node list

// the temporary data structure: I'll create a list of these from
// the initial XML, then recursively group them into directories. 
type Path = string list * XElement

let make_path (e : XElement) =
   e.Element(xname "File") |> element_to_string |> String.split [ '\\' ], e

// I want to split up the path names, while carrying the original
// element around until I'm ready to use it. 
let paths = doc.Root.Elements(xname "Model")
               |> Seq.map make_path
               |> Seq.to_list // There's no Seq.partition, so...
              
let is_file (p, _) =
   (List.length p) = 1
  
let strip (p, e) =
   // Strip the next part of the path, and return this tuple.
   List.tl p, e

let separate (l : Path list) =
   List.partition is_file l  
  
let rec collect (l : Path list) =
   match l with
   | [] -> []
   | _ -> let files, directories = separate l
          let x = directories
                  |> Seq.groupBy (fun (l, _) -> List.hd l)
                  |> Seq.map make_directories
                  |> Seq.to_list
          (make_files files) @ x
and make_directories (l, r) =
   Directory ( l, r |> Seq.map strip |> Seq.to_list |> collect )
and make_files paths =
   paths |> List.map (fun (l, e) -> File (List.hd l, e))
  
let collected = paths |> collect

let make_xml l =
   // Yes, you need the "let rec" here, too. That took me a while to 
    // figure out. Otherwise these nested functions can't call each other.
   let rec make_file name (xml : XElement) =
       // If you want to mix XElement and XAttribute objects, you'll have 
        // to upcast them to XObject. F#'s type inference won't try to find the
        // lowest common denominator between two classes in a heterogeneous 
        // collection, as far as I can tell. 
       XElement(xname "File", xargs [XAttribute(xname "Name", name); XAttribute(xname "ObjectiveValue", xml.Element(xname "Solution") |> element_to_string)])
   and make_directory name nodes =
       let element = XElement(xname "Directory", xargs (nodes |> List.map make_xml'))
       element.SetAttributeValue(xname "Name", name)
       element
   and make_xml' e =
       match e with
       | File (name, element) -> make_file name element
       | Directory (name, element) -> make_directory name element
   match l with
   | [] -> []
   | _ -> List.map make_xml' l
  
let xml = XElement(xname "KnownSolutions", make_xml collected)
let s = xml.ToString()
Console.WriteLine(s)

What's an F# Tuple?

2008-02-02T12:26:00.000-05:00

It's hardly a difficult question, but it's taken me a while to arrive at an answer. Reflector has been invaluable to me, and I can't recommend it strongly enough to anyone who wants or needs to understand what the F# compiler does. One often hears that functional programming more readily lets one find the proper level of abstraction, but sometimes one has to look at the IL, perhaps as a bridge to C# (the "canonical"
.NET language), to improve.

Let's say I define these tuple types:

type StringInt = string * int
type StringDouble = string * double

If I disassemble the resulting DLL, I find...nothing at all! There's no trace in the IL of these tuple types, or anything else:

public static void main()
{
}

Let me add some functions that operate on this code:

let get_int (t : StringInt) =
    let _, n = t in n

let get_float (t : StringFloat) =
    let _, f = t in f

Something interesting now shows up in Reflector's tree view of the
assembly:

main() then looks like this (screenshots made using Cropper):

I can't claim that all of this is comprehensible to me, but one thing is obvious: the compiled IL has no trace of the named tuple types. They're like structs insofar as they're equal when they have equal structure. Tuple types with the same structure are really the same type. They are not implemented as structs (presumably to avoid having to copy them to the stack on every recursion), but they're implemented as classes. Sealed classes, mind you:

The disassembled get_int() function looks like this; I don't know why a new instance is being allocated from the heap:
Interestingly, if I change my code thus, I can no longer call get_int() and get_float() with the resulting values, because the "discrimated union" Tuples is implemented as a class, rather like a C-style union with type tag and some smarter operations (the disassembled IL is much too verbose to reproduce here, but I recommend trying it):

type Tuples =
| One of StringInt
| Two of StringFloat

let si = One ("Carlo", 6)
let sf = Two ("Leo", 1.5)

Console.WriteLine (si)
Console.WriteLine (sf)

Note that I don't have to specify the tuple type; the compiler infers if from the tag "One" or "Two". What I've learned from Don Syme's Expert F# is that the tag most recently put in scope is the one that the compiler tries to use. Then the disassembled code looks like this, meaning that you can no longer get at the tuple except through the tag:

Cute Techie Kids!

2008-01-29T09:48:00.000-05:00

I don't really have any excuse for posting this photo of Leo (19 mos. old) sleeping with a bottle dangling from his lips. You wanna make something of it?

I Couldn't Be Happier!

2008-01-29T08:40:00.000-05:00

From slate.com:

A study suggests extreme happiness may be bad for you. Findings: 1) "The highest levels of income, education and political participation were reported not by the most satisfied individuals, but by moderately satisfied individuals." 2) Extremely happy people "earned significantly less money" and earned lower school grades than moderately happy people. 3) They "may not live as long," either. Theories: 1) Happiness makes you complacent and kills your drive. 2) It makes you slow to adapt. 3) It makes you too optimistic and insufficiently vigilant about your health. 4) It may overstimulate your cardiovascular system. Researchers' conclusions: 1) "Happiness may need to be moderated for success." 2) "Extremely high levels of happiness might not be a desirable goal." Human Nature's conclusions: 1) Success may need to be moderated for happiness. 2) Extremely high levels of success might not be a desirable goal.

Huffman Coding in F#

2008-01-20T11:03:00.001-05:00

#light // I.e. lightweight syntax

namespace Nassar
// An F# module is a "static class." All the declarations
// that follow are static members of this class.
module Huffman

type Incidence = HashMultiMap<char, int>
type CharSet = Set<char>

let addToCount (d : Incidence) (c : char) =
   // For some reason, the "do" is necessary here.
   do match d.TryFind c with
       Some(n) -> d.Replace(c, n + 1)
       _ -> d.Add(c, 1)
   d // Return the dictionary.

let count (s : string) =
   // I only just noticed that System.String implements
   // IEnumerable. The F# compiler correctly inferred from
   // the type of Incidence that s has to be a sequence of
   // char.
   s |> Seq.fold addToCount (Incidence.Create())

type HuffmanNode =
  Leaf of HuffmanLeaf
  Tree of HuffmanTree
and HuffmanLeaf = {Count: int;
                  Char: char;}
and HuffmanTree = {Count: int;
                  Chars: CharSet;
                  Left: HuffmanNode;
                  Right: HuffmanNode;}
              
let get_count node =
   match node with
    Leaf l -> l.Count
    Tree t -> t.Count

let has_char node c =
   match node with
    Leaf l -> l.Char = c
    Tree t -> t.Chars.Contains c

let get_set node =
   match node with
    Leaf leaf -> CharSet.Singleton leaf.Char
    Tree tree -> tree.Chars
              
let merge_nodes left right =
   Tree { Count = get_count left + get_count right;
          Chars = (get_set left) + (get_set right);
          Left = left;
          Right = right }

let node_priority l r =
   get_count l - get_count r

let rec reduce_list l =
   // What I should really do is put all the new leaf nodes
   // into a priority queue, and pull off two at a time as
   // long as the length of the queue is > 1. Then
   // make_tree wouldn't have to convert the sequence
   // it creates from the dictionary into a list.
   match l with
    l::r::tail -> (merge_nodes l r)::tail
                   |> List.sort node_priority
                   // ...and recurse.
                   |> reduce_list
    [tree] -> tree
    [] -> failwith "Can't operate on empty list!"

let rec encode h s =
   // Encode a character by branching to the leaf node
   // with that character.
   let rec encode' node c =
       match node with
        Leaf l -> []
       // TODO Add an accumulator to make this tail-recursive,
       // rather than prepending the new element.
        Tree t -> if has_char t.Left c then 0::(encode' t.Left c) else 1::(encode' t.Right c)
   s > Seq.map (fun c -> encode' h c) > Seq.concat

// Decode the int list l using the tree h.
let rec decode h l =
   let rec decode' node l =
       match node, l with
        // If we've arrived at a leaf, this must be the character
       // we're looking for. Add it to the sequence, and resume
       // from the top of the tree.
       // TODO Add an accumulator to make this tail-recursive.
        Leaf leaf, _ -> leaf.Char :: (decode h l)
        // A 0 in the stream means a left branch during
       // the encoding, and v.v.
        Tree tree, n::tail -> if n = 0 then decode' tree.Left tail else decode' tree.Right tail
       // Something was wrong in the encoding.
        _, _ -> failwith "Something has gone very wrong."
   match l with
    [] -> []
   // Start navigating down the tree.
    _ -> decode' h l

let make_tree s =
   let d = count s
   // IDictionary<_, _> implements
   // ICollection<KeyValuePair<_,_>>, so enumerate the
   // pairs and convert each into a leaf node.
   let leaves = d |> Seq.map (fun pair ->
                                   Leaf { Count = pair.Value;
                                          Char = pair.Key }; )
                  |> Seq.to_list
                  |> List.sort node_priority
   reduce_list leaves

Huffman Coding, SICP Exercise 2.69

2008-01-16T15:29:00.001-05:00

As a convenience, I defined Incidence as System.Collections.Generic.Dictionary. F#'s Map type
is actually a functor, and each insertion or removal returns a new instance. What I'd really like is something like the FindOrAdd() method available in the C5 dictionary implementations, but I can live without it. Anyway, I intend to fold a sequence of characters into a dictionary, for which purpose I'll first define the function that will do the folding:


> let count (d : Incidence) (c : char) =
-     let n = ref 0
-     // I need a "ref" variable to serve as an "out" parameter.
-     if d.TryGetValue(c, n) then
-         // Assign to a mutable property...
-         d.[c] <- !n + 1 
-     else 
-         d.Add(c, 1) 
-     d;;  
val count : Incidence -> char -> Incidence

I'm getting good at this:


> let d = "Tony Nassar, Software Engineer" |> Seq.fold count (new Incidence());;

val d : Incidence

> d;;
val it : Incidence
= dict
    [('T', 1); ('o', 2); ('n', 3); ('y', 1); (' ', 3); ('N', 1); ('a', 3);
     ('s', 2); ('r', 3); (',', 1); ('S', 1); ('f', 1); ('t', 1); ('w', 1);
     ('e', 3); ('E', 1); ('g', 1); ('i', 1)]
>

I did not know until today that System.String implements IEnumerable! And, fortunately, F#'s type inference lets me pipe that sequence of characters into my count() function. There are two steps that I need to take now: I need to create a sequence sorted by frequency (actually, a mapping from frequency to character, where the frequencies don't have to be unique) and turn it into a tree. This took me a while. Unlike C#, F# only allows mutually recursive type definitions if they're linked with "and." Here I'm declaring HuffmanNode as a "discriminated union," where Leaf and Tree are implemented as tags (you can verify this by using Reflector to examine the compiled DLL), and a leaf consists of the character to be encoded and its frequency (the latter is necessary during the construction of the tree), and a tree (or any non-leaf node) is...well, it's kinda obvious. If this were C, and someone were using a union and a type code, I'd say "Yuck!" But since it's functional programming, and this is a very handy way to build up a tree, it's suddenly cool again.


> type HuffmanNode =
- | Leaf of HuffmanLeaf
- | Tree of HuffmanTree
- and HuffmanLeaf = { Count : int; Char : char }
- and HuffmanTree = { Count : int; Chars : CharSet; Left : HuffmanNode; Right : HuffmanNode };;

type HuffmanNode =
  | Leaf of HuffmanLeaf
  | Tree of HuffmanTree
and HuffmanLeaf = {Count: int;
                   Char: char;}
and HuffmanTree = {Count: int;
                   Chars: CharSet;
                   Left: HuffmanNode;
                   Right: HuffmanNode;}

>

Eight Queens: I couldn't let it go!

2008-01-15T22:57:00.000-05:00

If you're not used to functional programming, and I'm not, you may respond with irritation at an FPer's "How few lines of code can I use to solve this problem?" showpiece. A good example would be the textbook problem of transposing a matrix (for which the answer is posted on Jomo Fischer's blog). If you really need to transpose a lot of matrices, you're probably going to be working in an environment where such operations are optimized, e.g. Mathematica. In other words, you're not going to do it yourself. So if anyone is irritated with the following code, let me say that I had to ponder this (on and off, not continuously!) for a few months before I arrived at the "right" solution, and I do feel that it's right. However, trying to implement it in F# gave me some valuable insights into how it ought to be done in other languages. Here's my solution:

> let queens size =
-     let range = [1..size]
-     range |> Seq.fold (fun answers column ->
-         let positions = [for row in range -> (column, row)]
-         [for p in positions for a in answers when all_safe p a -> a@[p]]) [[]]
- ;;

val queens : int -> (int * int) list list

> queens 5;;
val it : (int * int) list list
= [[(1, 4); (2, 2); (3, 5); (4, 3); (5, 1)];
 [(1, 3); (2, 5); (3, 2); (4, 4); (5, 1)];
 [(1, 5); (2, 3); (3, 1); (4, 4); (5, 2)];
 [(1, 4); (2, 1); (3, 3); (4, 5); (5, 2)];
 [(1, 5); (2, 2); (3, 4); (4, 1); (5, 3)];
 [(1, 1); (2, 4); (3, 2); (4, 5); (5, 3)];
 [(1, 2); (2, 5); (3, 3); (4, 1); (5, 4)];
 [(1, 1); (2, 3); (3, 5); (4, 2); (5, 4)];
 [(1, 3); (2, 1); (3, 4); (4, 2); (5, 5)];
 [(1, 2); (2, 4); (3, 1); (4, 3); (5, 5)]]
> queens 4;;
val it : (int * int) list list
= [[(1, 3); (2, 1); (3, 4); (4, 2)]; [(1, 2); (2, 4); (3, 1); (4, 3)]]

First, I did not use a for loop. Not because that would just be too imperative, but because I realized that the range (e.g. from 1..8, for an 8 x 8 chessboard) was actually an (immutable) object that I needed to use in several ways. To generate all the positions on a chessboard, I would then use a "sequence comprehension" such as { for column_number in range for row_number in range -> (column_number, row_number) }. I've begun to see this as more natural than nested for loops. I'm not doing with side effects in a loop; I'm asking for a single object (a collection of board positions) to be created for me. So the comprehension, a declarative construct, is more natural: "Here's what I want; give it to me. I'm not interested in putting it together piece by piece; that's your job." In comparison, the idiom 1, create a list, 2, go through several loops, appending on each innermost iteration, 3, finally do something with the collection (which is probably mutable, even though it really shouldn't be), obscures the intention, and is error-prone.

Then I iterate over that range (now treating it as the sequence of column numbers), and for every column I take the sequence of answers so far (i.e., each such answer is a sequence of one position each from the columns I've seen so far) and extend each one with each position in the current column (i.e. the current element of the range) that's safe. Below, I defined the functions safe() and all_safe(). I can easily generate board positions for the current column by means of another comprehension (let positions = etc.). Then I take the Cartesian product of the answers so far and this new column, filter all these new candidates through all_safe, and pass this new collection on to the next iteration, via fold(). For obvious reasons, Seq.fold starts with the collection of known 0-length answers, which is of course [[]].

If I were (re)doing it in Scheme, I'd rip off Kent Dybvig's comprehension macro, first off. I'd also rip off an implementation of fold, if I didn't already have one. I'd generate a range 1..n just as I do above. Then, on every iteration (I believe it is an iteration, if I'm folding from the left) I create the Cartesian product of the answers so far and the current column (which I just generated), (filter) these pairs through (all-safe), and continue. Something like that.

Eight Queens, and an End

2008-01-15T21:58:00.000-05:00

Once again I was led astray by having done too much imperative programming. I hate nesting loops to create collections, but I didn't go all the way. If the columns and rows of the chessboard are represented as a range—the same range—then all the positions are produced by taking the Cartesian product of that range with itself. Then I can iterate across the columns, and, for each one, take the Cartesian product of the rows in that column and the answers so far, and fold the new answers into a collection that was empty to start with. Ah, fold, delight of all functional programmers. To wit:


> let queens size =
-     // the row numbers *and* the column numbers
-     let range = [1..size]
-     let queens' columns =
-         columns |> Seq.fold (fun answers column ->
-             let positions = [for row in range -> (column, row)]
-             [for p in positions for a in answers when all_safe p a -> a@[p]])
-             [[]]
-     queens' range;;

val queens : int -> (int * int) list list

> queens 4;;
val it : (int * int) list list
= [[(1, 3); (2, 1); (3, 4); (4, 2)]; [(1, 2); (2, 4); (3, 1); (4, 3)]]
>

Eight Queens in F#

2007-12-08T13:49:00.000-05:00

Man, I'm really going back to school here. The last time I did this problem was when I was learning Prolog. Let's say you're trying to place a queen in the first column. Prolog's select function will pick one of the rows, and create a branch to explore the remaining rows. If row 3 was selected, say, you don't have to write any code to concatenate [1..2] and [4..8], in order to pass that smaller set of unoccupied rows to the next iteration / recursion. Very handy! No loops, no list operations, etc.


> #light;;
> type Position = int * int;;

type Position = int * int

> let safe p q =
-     fst p <> fst q && snd p <> snd q && fst p + snd p <> fst q + snd q && fst p - snd p <> fst q - snd q;;

val safe : int * int -> int * int -> bool

> let all_safe p positions =
-     Seq.for_all (safe p) positions;;

val all_safe : int * int -> #seq -> bool

> all_safe (1, 2) [(1, 2)];;
val it : bool = false
> all_safe (1, 2) [(3, 3)];;
val it : bool = true

> let range = [1..8];;

val range : int list

> range;;
val it : int list = [1; 2; 3; 4; 5; 6; 7; 8]
> let queens size =
-     let range = [1..size]
-     let rec queens' columns answers =
-         match columns with
-         | [] -> answers
-         | column::tail -> queens' tail [for answer in answers for position in [for row in range -> (column, row)]  when all_safe position answer -> position::answer]
-     queens' range [[]];;

val queens : int -> (int * int) list list

> queens 4;;
val it : (int * int) list list
= [[(4, 3); (3, 1); (2, 4); (1, 2)]; [(4, 2); (3, 4); (2, 1); (1, 3)]]
>

Implemented recursively, it's:


> let queens size =
-     let range = [1..size]
-     let rec queens' columns =
-         match columns with
-         | column::tail -> [for answer in (queens' tail) for position in [for row in range -> (column, row)]  when all_safe position answer -> position::answer]
-         | _ -> [[]]
-     queens' range;;

val queens : int -> (int * int) list list

> queens 4
- ;;
val it : (int * int) list list
= [[(1, 3); (2, 1); (3, 4); (4, 2)]; [(1, 2); (2, 4); (3, 1); (4, 3)]]
>

F#, finally!

2007-12-07T20:17:00.001-05:00

I've been champing at the bit to actually write some F#, but haven't been willing to risk sneaking it into production at the office, and unable to put in extra time at home to learn it. I have read Robert Pickering's Foundations of F# while commuting, but that's not verifiable experience in functional programming. As to why I would care whether I learn functional programming or not, let me plug the FringeDC interest group, founded by the estimable Dr. Conrad Barski. Not only have I found the members to be charming and personable, but they also seem much more incisive about what programming is than most developers I meet. They're not, for the most part, doing enterprise-scale stuff, where decisions about programming languages, database vendors, and so on would probably be taken out of their hands. Unless they're Paul Graham, who got rich writing LISP. Good for him! Anyway, lots of smart people write Java, or even VB. Nonetheless, the kicks in the butt that I've gotten at FringeDC, as well as from graduate classes at George Mason U., have led me to feel that what would do me the most good, and what I would most enjoy, is something more fundamental, theoretical, than spending every weekend preparing for MCAD exams. Different strokes.

Alright, enough about that. Languages that offer a REPL seem really suited to scripting. Yes, my friends at FringeDC would probably do everything in Emacs Scheme, but...I just don't know how anymore. Which I'm not proud of. Visual Studio has actually spoiled me to the point where I wouldn't know how to run some XML through an XSLT from the command line. I would actually have to take time out to figure it out. OK, really enough. Here's my task: I've got some XML describing the expected return values from some linear programming models, and it's tacked on top of some older regression testing scripts that just list the files to be solved by particular solvers. The XML file is called knownSolutions.xml, and the scripts are called solveBatch.cplex.txt and solveBatch.lpSolve.txt. Here's what I want to do: load the XML file, and, when a particular solver is not supposed to solve a model, add a corresponding attribute to the element. I've changed the schema:

<xs:attribute name="SkipSolvers" type="solverTypeList" use="optional">
...
<xs:simpleType name="solverType">
<xs:restriction base="xs:string">
<xs:enumeration value="lpSolve" />
<xs:enumeration value="Cplex" />
</xs:restriction>
</xs:simpleType>
<xs:simpleType name="solverTypeList">
<xs:list itemType="solverType" />
</xs:simpleType>

So if we have the XML:

<KnownSolutions>
<Model skipsolvers="lpSolve">
 <File>TestModels\JasonCh3Net.xml</File>
 <ObjectiveValue>196200</ObjectiveValue>
</Model>
</KnownSolutions>

...then I'd like to add attributes like so:

<Model SkipSolvers="lpSolve" .../<

So I need to load the XML from the F# console:


> open System.Xml;; # Import the assembly and the corresponding namespace.
   # The F# console waits for two semicolons before it interprets
   # your statement.

> let document = new XmlDocument();; # Infer the variable's type.

val document : XmlDocument

> document.Load @"knownSolutions.xml";;
val it : unit = () # The Load() method returns void, in other words.

Now at this point I've got to make some decisions about, you know, algorithms and data structures. I've got a tree—XML—and I've got a list of files that I can't assume are sorted. So why don't I read them in, filter out the empty lines, sort them, and then iterate across the XML's elements looking for files that aren't in the list for Cplex. Since I'm going to be looking things up in the list, I'll make a set out of it first. I should point out that, in contrast to imperative programming, we do not want to open the file and loop over the lines. We want to treat the file as a sequence of lines, no different than IEnumerable<string>. I say "we," but I mean "I": I just don't want to write nested loops anymore. But how do I deal with the EOF? I use a "generator" that has a special way of "terminating" the sequence of lines it reads. This is the "pipes and filters" idiom familier to UNIX folks. F#'s Seq class provides a generate_using function that thoughtfully calls IDispose() on the object created at the beginning of the generation.

> let opener () = File.OpenText("something.txt");;

val opener : unit -> StreamReader
> > opener;;
val it : (unit -> StreamReader) = <fun:clo@0_3>

What that means is that opener is a function with no arguments (if I'd left off the parentheses before the equals sign, F# would assign the return value of OpenText() to opener, which is not what I want), that knows how to return a StreamReader. generate_using takes that residual value (I don't think it's called a return value, per se) and passes it repeatedly to the actual generator, ergo:


> let liner (reader : StreamReader) =
- if reader.EndOfStream then None
- else Some(reader.ReadLine());;

val liner : StreamReader -> string option

option means "either a string, or nothing." Don't think of it as null; F# doesn't really have null. None will mark the end of the generated sequence. generate_using keeps sending the stream as an argument to the "closure" liner, and liner decides whether it's got something worth returning; if not, it signals to the next thing in line, "I'm done." I don't need to point out how parallelizable this "pipes and filters" idiom is; whatever is waiting for a line of text only needs one line to do its job. Anyway, now I'll filter out the empty strings, and put all of them in a hashed set for fast lookup (I could also just remove the empty string from the hashed set after populating it). I'll create the filter separately, rather than inline:


> let filter s = (s <> "");;

val filter : string -> bool

The static Seq.filter method requires a function that takes a sequence element and returns a Boolean value, in this case false if the string is empty. In order to create a set that's initialized to include all the values in the generated sequence, I do:


> let lpSolveSet = HashSet<string>.Create(
- Seq.generate_using opener liner
- |> Seq.filter (fun s -> (s <> ""))
- );;

val lpSolveSet : HashSet<string>

Whew! I don't know if F#'s type inference would have let me leave out the <string>. Putting it together, as I suppose I could have done in 5 minutes if I were a PowerShell guru:


> Seq.generate_using (fun () -> File.OpenText @"solveBatch.lp_solve.txt")
- (fun reader -> if reader.EndOfStream then None else Some(reader.ReadLine()))
- |> Seq.filter (fun s -> (s <> ""))
- |> Seq.map (fun s -> lpSolveSet.Add(s));;
val it : seq<unit> = seq [null; null; null; null; ...]
> lpSolveSet;;
val it : HashSet<string>
= seq
["JasonCh3Net.xml"; "JohnCh4Net.xml"; "OffsetNet.xml";
"WithinClauseTestNet.xml"; ...]
>

In other words, generate a sequence of lines from a file , pass them through a filter that removes empty strings, and send the resulting sequence to the HashSet's constructor. I could also have piped the filtered sequence to a closure that would add each string to the set in turn. Whatever. Now...


> let models = document.SelectNodes "/KnownSolutions/Model";;

val models : XmlNodeList

> models;;
val it : XmlNodeList
= seq
[seq [seq [seq []]; seq [seq []]]; seq [seq [seq []]; seq [seq []]];
seq [seq [seq []]; seq [seq []]]; seq [seq [seq []]; seq [seq []]]; ...]
>

Oh, so it's a sequence! Now I'm rolling, so:


> Seq.hd models;;

  Seq.hd models;;
  -------^^^^^^^

stdin(131,7): error: FS0001: The type XmlNodeList is not compatible with the type seq<'a>
stopped due to error

Seq.hd ("head") is like LISP's car, btw. Hm, it's not a sequence. Embarrassing. I scratched my head for a few minutes, then realized that I should use a list comprehension:


> { for o in models -> o :?> XmlElement };;
val it : seq
= seq
[seq [seq [seq []]; seq [seq []]]; seq [seq [seq []]; seq [seq []]];
seq [seq [seq []]; seq [seq []]]; seq [seq [seq []]; seq [seq []]]; ...]
>

I apply the downcast operator to each element; now I have a strongly typed sequence, so F# can use type inference on the next element in the chain:


> let attrAdder (e : XmlElement) =
- if not (lpSolveSet.Contains(e.InnerText)) then begin
-   let attr = document.CreateAttribute("SkipSolvers") in begin
-     attr.Value <- "lpSolve";
-     e.Attributes.Append(attr)
-   end
- end;;

      e.Attributes.Append(attr)
  -----------------^^^^^^^^^^^^^

stdin(87,17): error: Type constraint mismatch. The type
        XmlAttribute
is not compatibile with type
        unit.
The type XmlAttribute is not compatible with the type unit
stopped due to error

What? I scratched my head over this one. In the end, the error message makes perfect sense: because there's no "alternative," the "consequent" is not allowed to return a value, and XmlAttributeCollection.Append() does. So we have to pipe it into oblivion, hence:


> let attrAdder (e : XmlElement) =
- if not (lpSolveSet.Contains(e.InnerText)) then begin
-   let attr = document.CreateAttribute("SkipSolvers") in begin
-     attr.Value &lt- "lpSolve";
-     e.Attributes.Append(attr) |> ignore
-   end
- end;;

val attrAdder : XmlElement -> unit

So this is the little function object that will add the required attribute to the element if the lpSolve solver is not supposed to solve it. Then:


> { for o in models -> o :?> XmlElement } |> Seq.iter adder;;
val it : unit = ()

And lo and behold, I get this:


> {for node in document.SelectNodes "/KnownSolutions/Model" -> node :?> XmlElement } |> Seq.iter adder;;
System.ArgumentException: The named node is from a different document context.
at System.Xml.XmlAttributeCollection.Append(XmlAttribute node)
at FSI_0014.adder(XmlElement e)
at FSI_0074.it@150.Invoke(XmlElement e@51_6)
at Microsoft.FSharp.Collections.Seq.iter@868.Invoke(IEnumerator`1 e@90_1)
at Microsoft.FSharp.Core.Operators.using[T,U](T ie, FastFunc`2 f)
at Microsoft.FSharp.Collections.Seq.iter[T,U](FastFunc`2 f, U ie)
at <StartupCode>.FSI_0074._main()
stopped due to error

After about an hour, I realized that the function object that's adding the attributes is a closure: that means that it encapsulates a reference to a previous value of document. That's what "closure" means, silly! I create a new closure that refers to the new XML document, rerun, and I'm done, almost:


> document.Save @"knownSolutionsImproved.xml"

Now it's Chinese music...

2007-11-30T16:38:00.000-05:00

Yep, I've listened to nothing but flamenco for several weeks. Then I wanted to see if YouTube had any clips of Sabicas, and saw that someone had posted a comment comparing him to Liu Fang. I don't quite see the comparison, except in terms of their virtuosity, but if you've been dying to hear a performance of "King Chu doffs his armor," here it is.

The FBI in Movies, the FBI in Reality

2007-11-17T16:54:00.000-05:00

In Broken, Richard Gid Powers suggests that the FBI has never actually had a mission, and many of it failures can be attributed to its flailing about in the effort to find one. J. Edgar Hoover's insistence on chasing a tiny number of radicals while completely ignoring the much more serious problem of organized crime was not simply due to his cynicism; it was also due to the confusion in the definition of a federal crime, and his unwillingness to embarrass himself trying and failig to solve an actually difficult problem. It was also the beginning of the FBI's self-promotion through popular entertainment ("The Untouchables" and all that).

Now, I'm a sucker for crime shows, but there is a powerful whiff of bullshit in the depiction of the profiling of serial killers in such movies as The Silence of the Lambs (not to mention something really repulsive, not to mention factually incorrect, in the depiction of them as evil geniuses in SotL, the contemptible Seven...I could go on), and that whiff emanates from John Douglas, the FBI's "eminent" profiler, the model for SotL's Jack Crawford. Malcolm Gladwell recently argued in The New Yorker that what these profilers do is not so different from the "cold readings" that psychics such as John Edward do, namely, spew enough predictions that some of them have to stick. Even about such simple, empirically verifiable aspects of a killer's identity as, oh, his age, his skin color, his intelligence...Douglas is usually wrong. Even if he were right, how would his colleagues go about looking for an unusually intelligent, unmarried white man whom no evidence links to the crime? Profiling's basis in research is rather weak; imprisoned serial killers are *not* reliable sources, and the more intelligent ones have ample opportunity to construct ex post facto justifications for details of the crime if that will keep some psychologist talking to them. Even if this were not so, "research" on imprisoned serial killers has not been conducted according to proper research protocols, and the findings would be impossible to replicate. Gladwell: "Not long ago, a group of psychologists at the University of Liverpool decided to test the FBI's assumptions [that a criminal typology can be deduced from crime-scene details]...When they looked at a sample of a hundred serial crimes, however, they couldn't find any support for the FBI's distinction [between 'organized' and 'disorganized' killings and therefore killers]. Crimes don't fall into one camp or the other. It turns out that they're almost always a mixture of a few key organized traits [emphasis mine—TN] and a random array of disorganized traits. Laurence Alison, one of the leaders of the Liverpool group and the author of The Forensic Psychologist's Casebook,'The whole business is a lot more complicated than the FBI imagines.'"

Unit-Testing XML, XSLT

2007-11-17T16:43:00.000-05:00

OK, I posted my suggested design for an XML fixture to the MbUnit user's group. I ought to use this blog for self-promotion sometimes.

MbUnit vs. NUnit, the cage match

2007-11-05T10:50:00.000-05:00

I've happily used NUnit for 4 years now, and never questioned the design. As you may know, NUnit diverges from the xUnit model by using metadata rather than inheritance to indicate test fixtures, their setup, and their tests: "With NUnit 2.0, we introduced the use of attributes to identify both fixtures and test cases. Use of attributes in this way was a natural outcome of their presence in .NET and gave us a way of identifying tests that was completely independent of both inheritance and naming conventions" (see here). There are times, however, when this new model doesn't quite serve. I have quite a few test fixtures that, as part of their setup, need to perform a similar set of operations: say, read a file, create some sort of data structures, run an expensive Solve() method, etc. I can do this by deriving my fixture classes from an abstract base class that spells out a "template pattern," namely the methods or properties that the real fixture classes must implement, which the base class, which actually has a public method with the [TestFixtureSetUp] or [SetUp], which in turn encapsulates the pattern. In this case, the derived class would implement public string ModelPath { get { return @"C:\Documents and Settings\...\model.xml" } }, and the abstract class's fixture set up would call this.Load(this.ModelPath). You get the idea. Anyway, I'm not totally happy with this. I don't like the coupling within a class hierarchy that the template pattern entails, I end up with too many, only slightly different ad hoc abstract base classes that no one else understands, and there are still things I can't do this way.

Now, I have to admit that I haven't yet explored NUnit's extensibility. My current task is to write a rather complex XSLT involving three different Muenchian groupings, and I really wanted to be able to do it incrementally, in TDD fashion. I do sort of like stepping through the transform in Visual Studio's debugger, as that's taught me a lot about XML, but I need repeatable tests. XsltUnit hasn't been updated in four years, nor has XmlUnit. The former might be suitable for a real XMLer, but I'm not one, and I don't want to displace my difficulties onto a tool. XmlUnit doesn't handle namespaces, anyway, whereas I can't avoid them. Poking around further, I stumbled on MbUnit,which does include XML diffing. That turned out not to be what I wanted, but I did learn some interesting things. MbUnit still provides the expected attributes, including the ever-handy [ExpectedException(...)], but the test pattern is really described in terms of attributes. A test runner finds a test fixture's attributes, and has the appropriate invoker create the tests. This allows test methods to accept parameters, for example; the invoker simply uses reflection to call the method with an argument described by method's attributes. You can find more information at Peli's Farm, and at the Advanced Unit Test project, but I wouldn't say that the documentation is stellar. Anyway, in order to begin to be more of a radical, and less of an early adopter, I downloaded the source code, went back and forth between it and my requirements, trying to figure out how to implement them.

So this is what I ended up with:


using System.Xml.XPath;
using MbUnit.Framework;
using Omega.NetworkModel.Tests;

namespace Omega.NetworkModel.Tests
{
/* A fixture factory should load this document:

 <?xml version="1.0" encoding="utf-8"?>
 <Root>
   <Element Integer="1"></Element>
 </Root>

 */
[MyXmlTestFixture("document.xml")]
public class TestXmlWithoutTransformFixture
{
 // A test invoker should somehow get its hands on the XPathNavigable,
 // compile this expression, and give me the strongly typed result.
 [MyXPathExpressionTest("/*")]
 public void DoSomething(XPathNodeIterator iterator)
 {
  Assert.AreEqual(1, iterator.Count);
 }

 // count() returns a double, it turns out. The invoker is invoking
 // this method via reflection, so if the XPath expression returns
 // something other than a double, there'll be an error.
 [MyXPathExpressionTest("count(//*)")]
 public void CountElements(double count)
 {
  Assert.AreEqual(2, count);
 }

 // I was surprised that the compiler does *not* expect XML-escaped stuff.
 [MyXPathExpressionTest("count(//*) > 0")]
 public void TryBoolean(bool hasElements)
 {
  Assert.IsTrue(hasElements);
 }
}

// The runner should load this document, and transform it. The
// transformed result is then the basis of the tests.
[MyXmlTestFixture("document.xml")]
/*
 <?xml version="1.0" encoding="UTF-8" ?>
    <xsl:stylesheet version="1.0" xmlns:xsl="http://www.w3.org/1999/XSL/Transform">

     <xsl:template match="node()|@*">
     <xsl:copy>
     <xsl:apply-templates select="@*"/>
      <!-- The default template simply copies the text value. -->
      <xsl:apply-templates/>
        </xsl:copy>
      </xsl:template>

      <xsl:template match="/">
       <xsl:apply-templates select="*|@*" />
     </xsl:template>
   </xsl:stylesheet>
 */
[MyXsltTransform("test.xslt")]
public class TestXmlAfterIdentityTransformFixture
{
 [MyXPathExpressionTest("/*")]
 public void DoSomething(XPathNodeIterator iterator)
 {
  Assert.AreEqual(iterator.Current.NodeType, XPathNodeType.Root);
 }
}

// Transform, and then establish an evaluation context (i.e., namespace mappings!).
[MyXmlTestFixture("document.xml")]
[MyXsltTransform("test.xslt")]
[MyXsltNamespaceMappingDecorator("tnt", "")]
public class TestXmlAfterIdentityTransformAndNamespaceFixture
{
 [MyXPathExpressionTest("/tnt:*")]
 public void DoSomething(XPathNodeIterator iterator)
 {
  Assert.AreEqual(iterator.Current.NodeType, XPathNodeType.Root);
 }
}
}

Open Spaces & Productivity

2007-11-01T09:13:00.000-04:00

I write from a position of utter ignorance here, as for the most of the last 5 years I've had quite unpleasant working situations. Nonetheless, I've often been very productive in my windowless basements, sometimes because of their unpleasantness: I had to work harder in order to eliminate them from my awareness. I wasn't always allowed an MP3 player and headphones, either, so it's not like I had any sort of private space. I worked for 15 months at the desk pictured at the right, and I was extremely productive. That doesn't mean that I didn't also hate it. The effort that I had to exert in order to shut out distractions eventually wore me out. Be all that as it may, I really just want to admit that I have no proper basis of comparison to the agile image of an open space of unimpeded communication. I'm not sure I want to share a keyboard with anyone for most of the day, but maybe my irritation will diminish now that I've moved out of the aforementioned dungeon.

At any rate, it is possible to study these things, and Michael Brill does just that. Brill is president of BOSTI Associates, "workplace planning and design consultant in Buffalo, N.Y., and founder of the School of Architecture at the University of Buffalo" (click here). This article contrasts his viewpoint to that of Franklin Becker, director of the International Workplace Studies Program at Cornell University. I don't have time to summarize right now (I just finished my coffee, so my "knife-sharpening" 20 minutes are over), but they both agree that cubicles are bad.

I'm a Libertarian Now!

2007-10-26T12:49:00.000-04:00

It was probably inevitable that I would become a libertarian. When I was in graduate school, I was a Gramscian Marxist and a Freudian, as was only proper. Now I write software. Now I'm linking to George Mason University economics professor Tyler Cowen's Marginal Revolution blog. Nice that the guy also writes about art: Markets and Cultural Voices: Liberty vs. Power in the Lives of Mexican Amate Painters. To be honest, most of the libertarians I knew before I got back into software were angry middle-aged engineers, and it was hard not to interpret their convictions as of a piece with their middle-aged guy anger.

Now that I'm rockin' the GMU CS department, maybe I'll meet Cowan.

Greeted as Liberators

2007-10-21T09:56:00.000-04:00

Rory Stewart, who served as governor of Maysan province under the CPA, reviews several biographies of one of his forebears, Gertrude Bell: "The Queen of the Quagmire". Both the review and his book The Prince of the Marshes show a kind of modesty that might be impossible for any American writing about our occupation of Iraq. For Americans, it seems to be all about us. This flaw doesn't invalidate the writing of George Packer, for example, whose essay on our contemptible neglect of Iraqis who've chosen to help the occupiers by serving as translators I highly recommend. Yet Packer was a liberal hawk only a few years ago, and it's very difficult for him, writing now, not to attribute the obvious failure of our occupation (and of his arguments at the time) to the people carrying it out, rather than to a more fundamental cause. In other words, if the CPA had not put the obtuse Paul Bremer in charge, it might have worked.

Gertrude Bell is one of the architects of modern Iraq, if that's something she'd really want to claim credit for at this point. In contrast to the liberal hawk's regret that we didn't put the smartest people in charge, not to mention Edward Said's imputation of a fundamental bad faith, Stewart credits Bell and her colleagues with quite impressive knowledge of Arabic, of tribal power structures, of how to ride a camel, etc.: "Some suggest that the US failure in Iraq is due simply to lack of planning...They should consider Bell and her colleagues, such as Colonel Leachman or Bertram Thomas, a political officer on the Euphrates. All three were fluent and highly experienced Arabists, won medals from the Royal Geographical Society for their Arabian journeys, and were greatly admired for their political work. Thomas was driven from his office in Shatra by a tribal mob. Colonel Leachman, who was famed for being able to kill a tribesman dead in his own tent without a hand lifted against him, was shot in the back in Fallujah." Bell herself has to take the blame for agreeing to tack the Kurdish areas onto this new entity, at subsequent great cost to the Kurds.

It's too easy to hate the smirking fatuity of Donald Rumsfeld. But it's entirely beside the point. There is no objective measure of the depth of our understanding of Iraq. Who's to say that their self-understanding is any better than our understanding of them? The obstacle to building a new Iraq for the Iraqis is not that we don't understand them. The obstacle is that they're just not that into us. That's what it's like to be an occupier.

Photo of cute toddler!

2007-10-13T13:27:00.000-04:00

There's this music called flamenco...

2007-10-12T19:32:00.000-04:00

...and on a whim I recently purchased a 12-volume set called The History of Flamenco. I had just read Fernanda Eberstadt's Little Money Street, and I felt I had to hear some. Or a lot. I've always loved the blues, and flamenco is like it in some ways: it's the music of a marginal group, much of its history is mysterious, purity of tone means little while emotional force means everything (in a wonderful phrase, a great flamenco singer is said to have "the voice that wounds"), and there's a violence in it that doesn't always seem metaphorical. On the other hand, flamenco has a much larger range of forms, and however much I may love Charlie Patton, I can't think of a blues guitar virtuoso who comes close to Sabicas. Anyway, I was just surfing for some information on La Paquera, one of whose tracks is included in the above anthology, and stumbled across this video clip of the same woman, now perhaps an abuela, attacking "Dolor de madre mia" with even more force than she had when she was young. I have no idea if this song is actually sad, although the title would suggest that. I was at work, but the hair on my arm stood up on hearing this, not just because of the emotion, which I can't identify, but because of the indomitable force of the music that bursts out of these old folks. Hunt around for some more clips from Carlos Saura's flamenco films. YouTube also has a lot of odd clips from old movies, in which some cantante in a suit strolls onto the set and lets loose (it doesn't hurt to have a young Paco de Lucia on guitar). For me it's like seeing Howlin' Wolf walk into a Doris Day movie and sing "Commit a Crime."

When I saw the first clip, I thought, "I could listen to this all day." Since then, a month ago, I have been. Here, I've done some of the work for you: Paco de Lucia with El Camaron de la Isla, Juanito Valderrama wandering into some weird dance routine, some younger singers and the great Tomatito tearing it up (also from Saura's film), and finally these two old men singing the slowest form, the martinete. Their intonation isn't perfect. Listen, Maria Callas's intonation wasn't perfect.

Ancient Technology

2007-10-12T19:07:00.000-04:00

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!

2007-10-12T18:15:00.000-04:00

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!

2007-10-10T08:12:00.000-04:00

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

2007-03-14T10:35:00.000-04:00

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

2007-03-09T09:48:00.000-05:00

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!

2007-02-05T17:08:00.000-05:00

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

2007-02-03T11:04:00.000-05:00

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

2007-01-19T17:39:00.000-05:00

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

2006-09-24T00:15:00.000-04:00

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

2006-09-22T13:36:00.000-04:00

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

2006-09-22T10:53:00.000-04:00

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

2006-09-05T11:08:00.000-04:00

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

2006-08-26T17:28:00.000-04:00

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

2006-08-23T20:08:00.000-04:00

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

2006-08-11T08:48:00.000-04:00

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

2006-08-07T15:11:00.000-04:00

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

2006-08-02T14:25:00.000-04:00

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

2006-07-18T15:16:00.000-04:00

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!

2006-07-04T14:40:00.000-04:00

Welcome, Leo!

2006-07-03T14:32:00.000-04:00

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

Generating C# from XML: A Mixed Blessing

2006-06-26T09:29:00.000-04:00

I was recently confronted with a considerable legacy application (I use "legacy" the way Michael Feathers does: a legacy application is any without tests) that at first seemed to have exploited .NET's lovely support for XML serialization: most of the classes from the domain model had the [Serializable] attribute. It turned out, however, that I could not simply instantiate an XmlSerializer for any of these classes, since they all had public properties of type System.Type (which already suggests that the developers who preceded me had some peculiar ideas about OO) or IDictionary. Now, of course, I could have changed the design only minimally in the following fashion:

[XmlSerializable]
public class LegacyClass {
  [NonSerialized]
  public Type ValueType { ... }

  public TypeEnum ValueTypeEnum {
    get { based on ValueType property }
    set { likewise }
  }
}

Similarly, events have to be marked thus:

  [field:NonSerialized]
  public event BlahHandler Blah;

The field qualifier causes the compiler to apply the attribute to the underlying multicast delegate field. An event is not serializable as such.

Still, after only half a day, I realized that my effort to leverage .NET's handy code generation for XML serialization of a class was adding more cruft to an already crufty code base, that any unit tests I tried to create as motivation for my new code were compromised by the low quality of the code I was adding to, that I would have to version these additions without knowing what effect they would have on the application as a whole...that I was driving blind, in other words. Our XML wizard advised me simply to write all my custom serialization code (via the ISerializable interface)...and at that point, I knew I was getting into pissing-match territory. I simply don't feel any need to prove myself by writing this code. I'm perfectly happy accepting the output from the VS2003 xsd.exe utility. The only obstacle was that I didn't have an XML schema to work from! All I had was the existing and very unorthodox custom serialization code that was already in place, which navigated a DOM, thus losing the performance advantages of custom serialization.

So I decided to use the memento pattern: treat XML as a persistence layer, generate a .cs file from a schema that I would have to create incrementally, based on what I could learn about the object graph and interpose a factory class that could populate the memento from the object graph or vice versa. Now all my serialization code is in one place, and testable as such, and I need never break the existing code. All I have to do is deserialize the XML, serialize, create a DOM, and determine what was lost during the round trip. Then I extend the XML schema, regenerate the .cs file for the memento, and repeat as necessary. I sidestep the existing deserialization code, and continue extending my factory until it creates an object graph that works, or seems to work. This latter step is obviously the difficult one, since I don't really know what the application requires in order to work properly! Ultimately, my factory has to reverse-engineer the existing code, but I can avoid destabilizing that code by virtue of having a completely discrete factory class in a separate file, and write unit tests in a strict A/B fashion (i.e., compare the object graph produced by my factory with that produced by the legacy code).

Then I dump the legacy code and open the champagne!

Running Fit via Visual Studio

2006-06-20T09:45:00.000-04:00

Robert C. Martin has written, "My attitude is that every time I must fire up a debugger, I have failed. Perhaps I have failed to make my code so clear that I don't need a debugger to understand it. Perhaps I have failed to work in cycles that are so small that I don't need a debugger to find out what went wrong. Whatever the reason, when I am forced to use a debugger it means that I need to adjust my practices so that I can avoid using a debugger next time." I agree with him whole-heartedly. The necessity of understanding legacy code (i.e., code not covered by tests) is often given as a counter-example, but the more time I spend debugging code I didn't write, the more I'm moved to bring it under test, for which I've found FitNesse indispensable. Ward Cunningham has likewise recommended writing exploratory tests when many developers would be inclined to single-step through code they haven't seen before.

Nonetheless, I've felt the need this week to single-step through some legacy code that is exercized by tests I wrote in FitNesse. I willingly concede that this feeling is evidence of some kind of failure, perhaps my own and not just the legacy coders'. The appropriate FitNesse documentation was not entirely clear to me, perhaps because I needed to better understand how FitNesse works in the first place. It seems obvious now that the test runner would have to get the HTML representing the tests from FitNesse, but I didn't quite grasp that. However, the application that needed to call my code is C:\FitNesse\dotnet\TestRunner.exe. In order to have TestRunner invoke my code (single-stepping through your own fixtures, let alone TestRunner or the Fit code, takes a little more work), I needed to open the Property Pages for the project and change the Debug Mode setting from "Project" to "Program," after which I could specify the Start Application. I then set the Command Line Arguments to -debug -nopaths -v localhost 8080 SerializationSuite.RoundTripSuite Validation.dll, though not all of that is required. My FitNesse server is listening on port 8080, so yes, those options are required. -debug and -v lead to more console output, though they might provide you with more insight into what, precisely, TestRunner is doing. FitNesse has to provide the tests, and in this case the tests that drive the problematic code are on the specified page (i.e., I normally see them at http://localhost:8080/SerializationSuite...). Validation.dll is the project output; in this case it contains custom fixtures. The Validation project references the code I want to bring under test; those DLLs are copied to the Validation project by default. If I set the Working Directory to the bin\Debug directory for the project, TestRunner should be able to find all the necessary DLLs. fit.dll and fitLibrary.dll should have been installed to the same directory as TestRunner.exe. I specified -nopaths in order to avoid any potential collisions with paths set in FitNesse. At this point, TestRunner can find all the DLLs it needs, so I can freely hit F5, just like in the old days, when I was looking for dangling pointers in C++.