Munging with Active Patterns

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

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

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?

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!

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!

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#

#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

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!

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

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#

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!

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...

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

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

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

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

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!

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

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!