Inside F#

Brian's thoughts on F# and .NET

Archive for February, 2010

DAWG-Gone!

Posted by Brian on February 21, 2010

A week ago today, on this very same stage, Chris got served.  Well, the poor fool danced back.  So you know what happens now.  It’s on!

The overview

(If you haven’t been keeping up, then go glance at the prior posts before starting here.)

My implementation of the Bookworm trie took less code, less memory, and less time to run than Chris’.  So of course Chris, in a desperate bid to restore his tarnished image, had to try to one-up me somehow.  He chose to focus on memory: the original trie implementation used about 400,000 nodes to represent the dictionary. By starting with my superior implementation, and then adding about 100 lines of his own code, Chris reduced the trie to about 55,000 nodes by sharing common suffixes.  In the process, though, he manages to write code that takes about four minutes to initialize the data structure.  Can you imagine if your favorite Flash/iPhone game took four minutes to load?  Good luck selling that at the app store, bro.

So today I’ll walk you through what Chris did right (shortest… subsection… ever!), as well as what he did wrong (get comfy in your chair), and then show my own implementation.  Like Chris’, my added code also tallies about 100 lines.  In contrast, my implementation uses less than a quarter of the memory of his.  And it runs in four seconds.  (Some refer to me as “Dr. McNamara”, but you can just call me ”Mac”.)

What Chris did right

Chris used a DAWG, and this is a good data structure.

What Chris did wrong

Sigh.  Where to start.

Let’s start small, then work our way up.

Idioms.  At one point in his code, Chris writes “ignore(expr)” rather than “expr |> ignore”.  The latter is the preferred idiom in F#; the former just looks funny.  (In two other places, Chris does this “right”.)  Also, Chris calls Option.isNone and Option.get, which is completely non-idiomatic.  Hello!  It’s called “pattern-matching” – look into it.

Equality. Chris does a lot of comparing object references for equality using the builtin ‘=’ and ’<>’ operators.  If you just want to do reference equality, it is faster to call obj.ReferenceEquals than to dynamically dispatch through the virtual .Equals() method.  This is a somewhat subtle point, but the mark of a true evil genius is attention to such detail.  In my implementation, I experimented using the wrong Equals call, and it resulted in about a factor-of-two slowdown (there are a lot of comparisons to do, as we’ll see).

Creating needless garbage.  Chris seems to enjoy making sure the GC always has plenty of work to do.  For example, he creates a Dictionary that uses a tuple type (“int*int”) as a key.  Tuple is a reference type, which means every time he looks something up in the Dictionary, he allocates a fresh tuple, which then immediately becomes garbage.  The tuple was at least somewhat well-motivated; Chris is trying to create a decent ‘hash’ function to minimize collisions and speed lookup, and is using “height*numChildren”.  Since the height it at most 16–

And, by the way, Chris’ blog and code just magically pull the number ‘16’ out of the air with no explanation.  So I’ll be the one to step up and explain it.  It just so happens that the longest word in our particular dictionary has 15 letters.  And this means the tree ends up being at most 16 tall (one extra node at the end representing “end of word”).  Of course, with a different word dictionary, Chris’ code may silently fail, since he’s hardcoded this number in–not one–but three places.  Argh!  Anyway, enough digressing…

–like I was saying, since the height is at most 16, and the number of children is at most 26, there’s plenty of bits in a single ‘int’ to store all these combinations.  But Chris just sloppily goes allocating tuples all over the place.  That might be fine for an everyday blog post or app, but if the whole point of your blog post is to out-do me on the “memory” front…  Sheesh!  I know the final goal is to optimize only the trie structure, but come on, try not to look like a complete chump along the way.

Choosing a good hash code. Speaking of that Dictionary, since we’re doing a lot of lookups to find equivalent trees, we really want the best hash code to minimize collisions.  Rather than just count the number of children a node has (and fail to distinguish e.g. a node with ‘ABC’ children from a node with ‘XYZ’ children), why not incorporate ‘which children’ into the hash?  Guess what, with 26 letters in the alphabet, we only need 26 bits to store whether there’s a child for each letter, which leaves us 6 more bits (plenty) to also store the height (in a 32-bit hash code).  We’ll see that in my implementation; it only takes 10 lines of code to do the job; some jobs are worth doing well.

Recomputing state. Chris defines some new properties on the TrieNode class, namely IsLeafNode and NumChildren.  Since they are ‘getter’ properties, their bodies are run every time they are called.  There is not a ton of work happening in these properties (just traversing the 26-wide array), but it is still wasteful to recompute every time; better to cache the result.  I presume Chris was trying to avoid putting new fields in the class (to keep the memory low), but as we’ll see in a moment, that’s being penny-wise but pound-foolish.

Choosing the right data structure.  Wait, what?  Earlier I said the DAWG was right!  Yes, a directed acyclic word graph is a great structure to be able to efficiently do prefix word searches through a big English dictionary.  But just because the thing is called a “graph” doesn’t mean you have to realize it as an actual object graphObjects are expensive! If the whole goal is to reduce memory, then one should not choose a CLR runtime representation that includes more than a hundred thousand separate objects (55K nodes, and each node also has an array field, which is its own separate object).  Why waste all that, when just one object will do?

(Yes.  That’s right… wait for it…)

If you want to represent this directed graph, there’s a good data structure for this.  It’s not rocket science.  You’ve heard of this data structure before.  They even have it in C.  It’s called a 2-D array.  Check it out!

(Pat yourself on the back if you saw it coming.)

Ok, enough of the blow-by-blow, Chris looks like he’s had enough.  Let’s move on to my version.

Doing it right – the strategy

Any directed graph of nodes-pointing-to-nodes can be realized with an array of integers.  After all, when we get close to the hardware level, that’s what the computer is doing anyway.  Memory is just a big array of bytes, and a pointer or object reference is just an index into that array of bytes.  The ‘problem’ is that runtimes like CLR inject a lot of overhead in that model (as suggested here; these are the costs associated with the benefits of having a GC, managed code, …), but this means there’s an opportunity to save memory by avoiding using the runtime to implicitly encode a graph as an array, and instead explicitly do it yourself.

So I’ll do just that.  I’ll build the original trie nodes as before (not caring too much about size, we’ll throw these objects away once we know final structure), combine common suffixes (create the DAWG), and then re-encode the DAWG structure as an array.  Along the way I’ll be sure to avoid all the pitfalls Chris fell victim to.

Before I do this, though, I ask myself, is it worth it?  I did some back-of-the-envelope math, and worked out that Chris’ structure occupies almost 15 megs of memory on a 64-bit machine, whereas the array structure I’m going to implement will only take up a little more that 3 megs.  So that’s more than a four-fold savings, which is a big enough win that I want to do it to ensure a FLAWLESS VICTORY in this grudge match.

If it weren’t for my desire to crush Chris’s soul, would it still be worth it?  My gut reaction is ‘probably not’ – if the goal is just to cheat at Bookworm, then even Chris’ (original, first) bloated solution is probably sufficient.  But if I imagine I’m the author of the Bookworm app, I can see wanting to do this kind of optimization to ensure that my app can run in a constrained memory environment.  And a smaller memory footprint means more spatial locality, which may also reap dividends regarding how fast the app runs.  (If you want a program to run faster, using less memory can be one way to make it happen.)  So I do think this is useful to explore, as this is the kind of thing you will occasionally want to do in the real world.  So let’s hop to it.

Doing it right – the implementation

I’ll just walk through the code that’s different since last time.  First, I define

let (===) x y = obj.ReferenceEquals(x,y)

I’ve defined this operator before; “obj.ReferenceEquals” is a mouthful, and I like choosing triple-equals-sign as the operator to compare whether two things are really, really equal (the same object).  I’ll be using it a fair bit.

Next I tweak the TrieNode class a few ways.  First,

[<NoEquality; NoComparison; AllowNullLiteral>]
type TrieNode() =

I added the NoEquality and NoComparison attributes; these will prevent me from accidentally calling the slower ‘=’ operator on two TrieNodes (the code would not compile – F# is great at detecting various errors at compile-time).

Next, in the body of the class, I add a couple more fields, and publicly expose the 26-wide array:

    let mutable height = -1
    let mutable fastHash = 0
    member this.NextChar = nextChar

What are the two new fields for?  I’m so glad you asked.  It’s probably obvious what “height” will be: it will store the height of the current subtree.  And “fastHash” will store a great hash code for this TrieNode.  Until the whole trie is built, however, I can’t assign these guys the right values, so I made them mutable and initialized them as above.  After the tree is built, then I can populate and access those values, thanks to these new members:

    // don't call this until the entire tree is built; it caches its results
    member this.Height =
        if -1 = height then
            height <- 1 + (nextChar |> Array.map (fun t -> if t===null then 0 else t.Height) |> Array.max)
            fastHash <- this.ComputeFastHash()
        height
    member private this.ComputeFastHash() =
        // An especially good hash function we can use after we've finished building the whole tree.
        // The first 26 bits will be set if the corresponding NextChar is non-null, and
        // the remaining 6 bits will be the Height.
        assert(this.Height > 0 && this.Height < 64)   // 64 is 2^6, we have 6 bits, which is plenty
        let mutable r = 0
        for i in 0..25 do
            if not(null === nextChar.[i]) then
                r <- r + 1
            r <- r <<< 1
        r <- r <<< 6
        r + this.Height 
    member this.FastHash = fastHash

The act of asking for the Height property the first time causes the entire tree to initialize the “height” and “fastHash” fields.  Height is easy – one plus the maximum height of any of your children.  As for the hash code, it’s an integer, where the first 26 bits encode which alphabet letters have children, and the last 6 bits are the height.  (If we end up with an English dictionary containing any sixty-five-letter words, an assert will fire to let us know that our clever scheme to cram all this information into the hash code is not working out exactly as planned, though it would do no great harm.)  Note the use of the bitwise left shift operator (<<<) – I think perhaps this is the first time I’ve had a reason to use it in a blog entry.  Fun stuff.

Ok, so with those minor additions to the TrieNode class, we can load up the word files and build the trie just as we did before.  (The full source code appears at the end of this blog entry; I’m skipping stuff that’s the same as last time.)  Once we have a trie, we need to convert it to a DAWG by finding common suffixes and sharing structure among semantically equal nodes.  Starting from the leaves, I’ll keep a Dictionary<TrieNode,TrieNode> where the keys represent semantically distinct nodes, and the values are “the canonical object reference” for that node.  We can walk the whole tree height-wise; if we encounter a node we’ve already seen, we replace it with the canonical one, otherwise we add it to our growing table of distinct nodes.  The code is almost easier than the prose:

open System.Collections.Generic 

let canonicalNodes = 
    new Dictionary<_,_>( { new IEqualityComparer<TrieNode> with
                            member this.Equals(x,y) = 
                                x.Height = y.Height 
                                && x.IsEndOfWord = y.IsEndOfWord 
                                && Array.forall2 (===) x.NextChar y.NextChar 
                            member this.GetHashCode x = x.FastHash } )

let rec Canonicalize (t:TrieNode, height) =
    if not(null===t) then
        if t.Height > height then
            for i in 0..25 do
                Canonicalize(t.NextChar.[i], height)
        elif t.Height = height then
            for i in 0..25 do
                let n = t.NextChar.[i]
                if not(null===n) then
                    match canonicalNodes.TryGetValue(n) with
                    | true,canon -> t.NextChar.[i] <- canon
                    | _ -> canonicalNodes.Add(n,n)

for i in 1..trie.Height do
    Canonicalize(trie, i)

Note that I provide a custom IEqualityComparer to the Dictionary, whose Equals() method tests semantic distinctness (under the invariant that all nodes of lesser height have already been canonicalized), and whose GetHashCode is our FastHash.  The Canonicalize() function then walks the tree heightwise: if we’re too high, we recurse deeper until we reach the height we’re canonicalizing, but once we reach the right height, we look up each of the object references in the 26-wide array and either replace each with the canonical value if we’ve already seen it, or else add that object to our growing table of distinct ones.  Calling Canonicalize for every height will ensure that every node in the trie (viz. every suffix tree) has a canonical object.  Well, almost every node – since we’re just replacing references in the inner arrays, we missed the root:

canonicalNodes.Add(trie,trie)  // need to add the root

Ok, now every node is represented in the canonicalNodes table.

In case you missed it, in those 25 lines of code, I basically just did what Chris did in his blog entry.  Well almost.  Rather than 4 minutes, mine runs in about 3 seconds, so I guess it’s a little different.  But it accomplishes the same goal.  Rather than 400,000 nodes, we’re now down to about 55,000.  (In the full program, you’ll see that I print out the node count.)

I’ve equaled Chris’ node-compression (with less code, that runs like 60x faster) – now it’s time to get the memory footprint smaller still.  Now that we have a DAWG represented as an object graph, we’ll re-encode it as a 2D-array.  Each ‘node’ will be a row of the array, and each ‘field’ within a node will be a column.  The only fields that matter are the 26-wide array (pointers to the child nodes) and the IsEndOfWord boolean – the other fields of the TrieNode type were just temporary artifice to help us efficiently get us to where we are now (DAWG-in-hand).  To simplify, we’ll just say each row is a 27-wide array, where the first 26 elements are the A-Z pointers, and the 27th element represents the IsEndOfWord boolean.  What kind of element is stored in this array?  Integers, of course.  Since each TrieNode now corresponds to a row of the array, we can just encode each object reference as a row index.  And, since there are conveniently only about 55,000 nodes – convenient because it’s a little less than 65,536 – we can use the two-byte “uint16” type in preference to “int”, to save half the storage.  So we begin:

assert(canonicalNodes.Count < int System.UInt16.MaxValue)
let arrayTrie = Array2D.create (canonicalNodes.Count+1) 27 0us

First I assert, so that if I do ever use a bigger dictionary that requires more than 65,536 nodes, I’ll know I have to switch to a bigger data type.  Then I create a 2D-array that has “canonicalNodes.Count+1” rows, 27 columns, and has each element initialized to (the uint16 version of) zero (I had to look up the suffix “us” in this table).  Why “canonicalNodes.Count+1”, you ask?  Well, we represented every TrieNode in “canonicalNodes”, but there is one other value to account for.  Not every entry in each 26-wide table of pointers to TrieNodes points to another TrieNode.  Many of those references were “null”.  And we need to represent that, too.  So row 0 of the table will mean “null”.  As it turns out, that row is already perfectly initialized.  The first 26 entries all contain the value 0us, which is the row number they are “pointing to” – in this case, the “null” row.  And the 27th entry, representing IsEndOfWord, is 0us (which I’m using to represent “false” – I’ll use 1us to represent “true”).  So this row is already great; in the TrieNodes, if we encounter ‘null’, we know there are no more words here, we’ve “fallen off the edge”.  And in the array, if we get to the 0-row “node” then no matter what extra letters we try to tack on, we just keep circling back around to this row, whose IsEndOfWord is always false.

So now we just need to initialize rows 1-through-Count so that they each correspond exactly with a canonical TrieNode. To do this, we need both a way to convert a row index into a canonical TrieNode reference, and a way to convert a canonical TrieNode into a row number.  So I write:

let numToNode = seq { yield null; yield! canonicalNodes.Keys } |> Seq.toArray
let nodeToNum =
    let d = new Dictionary<_,_>( { new IEqualityComparer<TrieNode> with
                                        member this.Equals(x,y) = x===y
                                        member this.GetHashCode x = x.FastHash } )
    for i in 1..numToNode.Length-1 do  // 0th is null
        d.Add(numToNode.[i], uint16 i)
    d

“numToNode” is an array of TrieNodes.  I pass in a number, and I get back a TrieNode.  And note that numToNode.[0] will be null, the way I’ve coded it.  Spiffy.

“nodeToNum” is a Dictionary<TrieNode,uint16>.  I pass in a TrieNode, and I get back an integer.  The .NET Dictionary type does not accept ‘null’ as a key, so I have to leave that entry out; we’ll account for it later.  Note that since I am working with canonical nodes, I use (===) as the equality test in my comparer.  So now I can say nodeToNum.[someNode] and I get back the row number in the array that will correspond to someNode.

Time to fill out the rows of the array with real data:

let mutable nextIndex = 1
let rec Fill (t:TrieNode) =
    if not(null===t) then
        for i in 0..25 do
            Fill(t.NextChar.[i])
        let num = int nodeToNum.[t]
        for i in 0..25 do
            arrayTrie.[num,i] <- match t.NextChar.[i] with |null -> 0us | n -> nodeToNum.[n]
        if t.IsEndOfWord then
            arrayTrie.[num,26] <- 1us
Fill(trie)

I just recursively walk through every node in the trie.  For each TrieNode reference in the 26-wide NextChar array, I convert each reference to its corresponding number, and store that in correct slot of the 2D-array.  Note also the special-casing of “null->0us” here (as I earlier forewarned).  And for each TrieNode, if IsEndOfWord is true, I set the 27th element of the row to 1us.  This initialization step only takes about one second of wall-clock time to run.

Now my 2D-array contains all the same information as my TrieNode object graph, only in much less memory space.  I can drop all the other objects on the floor for the GC to sweep up; I need only a single object in hand (the 2D-array) to solve Bookworm.

I’ll need to make some very minor adjustments to my “Find” algorithm – it used to talk to TrieNodes, but now it needs to talk to the array instead.  The previous algorithm just needed to know (1) which node it was ‘currently at’, (2) how to ‘move forward a letter’, and (3) how to check if it’s at the end of a word.  Previously (1) was handled by storing a local reference to a TrieNode, now instead I’ll store a uint16 instead.  As for (2) and (3), I can write those functions thusly:

let NextChar(node,c) = arrayTrie.[int node, int c - int 'A']
let IsEndOfWord(node) = arrayTrie.[int node, 26] = 1us

Thus my Find() code is almost unchanged; the only changes are on the lines marked HERE:

let rec Find(col, row, n:uint16) = seq {  // HERE - was t:TrieNode
    assert((col+row)%2 = 1) // we should only be searching LETTER positions
    let c = board.[col,row]
    if c <> ' ' then
        board.[col,row] <- ' '
        match NextChar(n,c) with  // HERE - was t.[c]
        | 0us -> ()  // HERE - was null
        | node -> 
            if IsEndOfWord(node) then  // HERE - was node.IsEndOfWord
                yield [c]
            for suf in Find(col-1, row-1, node) do yield c::suf
            for suf in Find(col-1, row+1, node) do yield c::suf        
            for suf in Find(col  , row-2, node) do yield c::suf        
            for suf in Find(col  , row+2, node) do yield c::suf        
            for suf in Find(col+1, row-1, node) do yield c::suf
            for suf in Find(col+1, row+1, node) do yield c::suf        
        board.[col,row] <- c }

I changed the argument type of the function from “TrieNode” to “uint16”.  I changed “t.[c]” to a NextChar() call.  “null” became “0us”.  And “IsEndOfWord” is no longer a member function.  Four tiny changes, due to the fundamental representation change I made to save on memory.

The full source code appears at the end of this blog entry.

Summing up

Here’s the TL;DR:

  • Chris posts a Bookworm solver
  • Brian posts his own solver that’s shorter, faster, smaller
  • Chris builds on Brian’s solution and reduces memory further, but makes the program much slower
  • Brian improves on that by more than 4x memory-wise and more than 60x speed-wise

Victory is mine!

The Source Code

All told, still fewer than 200 lines.

let IsLetter(c)   =    c>='A' && c<='Z'
let (===) x y = obj.ReferenceEquals(x,y)

[<NoEquality; NoComparison; AllowNullLiteral>]
type TrieNode() =
    let nextChar = Array.create 26 null
    let mutable isEndOfWord = false
    let mutable height = -1
    let mutable fastHash = 0
    member this.NextChar = nextChar
    member this.IsEndOfWord = isEndOfWord
    member this.Item with get(c:char) = nextChar.[int c - int 'A']
                     and private set(c:char) v = nextChar.[int c - int 'A'] <- v
    member this.Add(word) = 
        assert(word |> Seq.forall IsLetter)
        this.Add(word,0)
    member private this.Add(word:string,i) =
        if i = word.Length then
            isEndOfWord <- true
        else 
            match this.[word.[i]] with
            | null -> let newNode = new TrieNode()
                      newNode.Add(word,i+1)
                      this.[word.[i]] <- newNode
            | node -> node.Add(word,i+1)
    // don't call this until the entire tree is built; it caches its results
    member this.Height =
        if -1 = height then
            height <- 1 + (nextChar |> Array.map (fun t -> if t===null then 0 else t.Height) |> Array.max)
            fastHash <- this.ComputeFastHash()
        height
    member private this.ComputeFastHash() =
        // An especially good hash function we can use after we've finished building the whole tree.
        // The first 26 bits will be set if the corresponding NextChar is non-null, and
        // the remaining 6 bits will be the Height.
        assert(this.Height > 0 && this.Height < 64)   // 64 is 2^6, we have 6 bits, which is plenty
        let mutable r = 0
        for i in 0..25 do
            if not(null === nextChar.[i]) then
                r <- r + 1
            r <- r <<< 1
        r <- r <<< 6
        r + this.Height 
    member this.FastHash = fastHash

let words = seq {
    let toIgnore = System.IO.File.ReadAllLines("IgnoredWords.txt") |> Set.ofArray
    for word in System.IO.File.ReadAllLines("TWL06.txt") do
        assert(word |> Seq.forall IsLetter)
        if not (toIgnore.Contains word) && word.Length >= 3 then
            yield word }

let trie = new TrieNode()
for w in words do
    trie.Add(w)

let rec IsWord(s:string, t:TrieNode) =
    if t===null then false
    elif s.Length=0 then t.IsEndOfWord
    else IsWord(s.Substring(1), t.[ s.[0] ])
    
assert(IsWord("ABSTRACTIONISMS", trie))
assert(IsWord("MONSOON", trie))
assert(not(IsWord("TAPL", trie)))

/////////////////////////////////////////////////////////

let rec CountNodes (t:TrieNode) =
    if null===t then 0 else
    1 + (t.NextChar |> Array.map CountNodes |> Array.sum)
printfn "Original has %d nodes" (CountNodes trie)     

open System.Collections.Generic 

let canonicalNodes = 
    new Dictionary<_,_>( { new IEqualityComparer<TrieNode> with
                            member this.Equals(x,y) = 
                                x.Height = y.Height 
                                && x.IsEndOfWord = y.IsEndOfWord 
                                && Array.forall2 (===) x.NextChar y.NextChar 
                            member this.GetHashCode x = x.FastHash } )

let rec Canonicalize (t:TrieNode, height) =
    if not(null===t) then
        if t.Height > height then
            for i in 0..25 do
                Canonicalize(t.NextChar.[i], height)
        elif t.Height = height then
            for i in 0..25 do
                let n = t.NextChar.[i]
                if not(null===n) then
                    match canonicalNodes.TryGetValue(n) with
                    | true,canon -> t.NextChar.[i] <- canon
                    | _ -> canonicalNodes.Add(n,n)

for i in 1..trie.Height do
    Canonicalize(trie, i)
canonicalNodes.Add(trie,trie)  // need to add the root

printfn "Now has %d nodes" canonicalNodes.Count     

/////////////////////////////////////////////////////////

assert(canonicalNodes.Count < int System.UInt16.MaxValue)

let numToNode = seq { yield null; yield! canonicalNodes.Keys } |> Seq.toArray
let nodeToNum =
    let d = new Dictionary<_,_>( { new IEqualityComparer<TrieNode> with
                                        member this.Equals(x,y) = x===y
                                        member this.GetHashCode x = x.FastHash } )
    for i in 1..numToNode.Length-1 do  // 0th is null
        d.Add(numToNode.[i], uint16 i)
    d

let arrayTrie = Array2D.create (canonicalNodes.Count+1) 27 0us
let mutable nextIndex = 1
let rec Fill (t:TrieNode) =
    if not(null===t) then
        for i in 0..25 do
            Fill(t.NextChar.[i])
        let num = int nodeToNum.[t]
        for i in 0..25 do
            arrayTrie.[num,i] <- match t.NextChar.[i] with |null -> 0us | n -> nodeToNum.[n]
        if t.IsEndOfWord then
            arrayTrie.[num,26] <- 1us
Fill(trie)

let NextChar(node,c) = arrayTrie.[int node, int c - int 'A']
let IsEndOfWord(node) = arrayTrie.[int node, 26] = 1us
let rootNode = nodeToNum.[trie]

/////////////////////////////////////////////////////////

let COLS = 7
let ROWS = 8
let data = [|  // columns
        "  K M E M T O O "
        " E F K I M C A D"
        "  A A E R E A F "
        " T D A I B N D J"
        "  V F F A T E E "
        " O J T R F I R R"
        "  I R D R E E O "
    |]    
    
// surround entire grid with border of spaces (one extra column, two extra rows)
let BOARDCOLS = COLS + 2
let BOARDROWS = 2*ROWS + 4
let MakeBoard(columns:string[]) =
    assert(columns<>null)
    assert(columns.Length = COLS)
    assert(columns |> Seq.forall (fun s -> s.Length = ROWS*2))
    for i in 0..COLS-1 do
        for j in 0..ROWS*2-1 do
            let c = columns.[i].[j]
            if (i+j)%2 = 0 then assert(c=' ' || IsLetter c)
            else                assert(c=' ')
    Array2D.init BOARDCOLS BOARDROWS (fun c r ->
        if c=0 || c=BOARDCOLS-1 || 
           r=0 || r=1 || r=BOARDROWS-2 || r=BOARDROWS-1 then ' '
        else columns.[c-1].[r-2])

let board = MakeBoard(data)    

let rec Find(col, row, n:uint16) = seq {  // HERE - was t:TrieNode
    assert((col+row)%2 = 1) // we should only be searching LETTER positions
    let c = board.[col,row]
    if c <> ' ' then
        board.[col,row] <- ' '
        match NextChar(n,c) with  // HERE - was t.[c]
        | 0us -> ()  // HERE - was null
        | node -> 
            if IsEndOfWord(node) then  // HERE - was node.IsEndOfWord
                yield [c]
            for suf in Find(col-1, row-1, node) do yield c::suf
            for suf in Find(col-1, row+1, node) do yield c::suf        
            for suf in Find(col  , row-2, node) do yield c::suf        
            for suf in Find(col  , row+2, node) do yield c::suf        
            for suf in Find(col+1, row-1, node) do yield c::suf
            for suf in Find(col+1, row+1, node) do yield c::suf        
        board.[col,row] <- c }

let allWordsSorted = 
    seq {    
        for col in 0..BOARDCOLS-1 do
            for row in 0..BOARDROWS-1 do
                if board.[col,row] <> ' ' then
                    yield! Find(col, row, rootNode)  // HERE
    } 
    |> Seq.map (fun w -> new string(w |> Seq.toArray))
    |> Set.ofSeq    // remove duplicates
    |> Seq.toArray 
    |> Array.sortWith (fun a b -> match compare a.Length b.Length with 
                                  | 0 -> compare a b
                                  | x -> x)
printfn ""
for w in allWordsSorted do
    printfn "%s" w
printfn "%d words" allWordsSorted.Length 
Advertisements

Posted in Uncategorized | 3 Comments »

An RSS Dashboard in F#, part six (putting it all together with a WPF GUI)

Posted by Brian on February 18, 2010

Previous posts in this series:

In the previous blog posts, we’ve created all the components we need for the RSS Dashboard app.  Today we just need to assemble all these pieces into an application with a WPF GUI. 

There’s a fair bit of code for today (about 220 lines), but each section is small and understandable on its own, so I’ll walk through it piece by piece.  Recall that the final goal is an app with a UI that looks like

Dashboard

To quote myself from part one:

The window is divided up into a grid where each cell is a different topic/forum.  Within each cell are the six threads with the most recent activity, sorted in order of recency.  Each thread displays its title (long titles are truncated with an ellipsis) and how long ago the thread began.  The threads are hyperlinks, so if I click one it opens the corresponding thread in my web browser.

The app polls the various RSS feeds periodically for new activity.  When new activity is detected, a few things happen:

  • a new entry appears in the listing for the corresponding topic (or, if the thread was already displayed in the list, it gets moved to the top)
  • the thread gets a yellow highlight so that it visually stands out as new
  • (optionally) the title is read aloud over the speakers using the text-to-speech built in to Windows

So let’s get to it!

Easy preliminaries

To start things off, I open a bunch of namespaces I’ll need.

open System
open System.Diagnostics 
open System.Windows.Media
open System.Windows.Media.Imaging
open System.Windows 
open System.Windows.Controls 
open System.Windows.Documents 
open System.ServiceModel.Syndication 

Speech.EventuallySpeak("Starting dashboard")

let NumItemsPerFeed = 6
let FeedUpdateFrequency = TimeSpan.FromMinutes(15.0)

I also announce the start of the program, and define a couple constants used throughout the rest of the app.

Quickly load some icons

I need to get the StackOverflow and hubfs “favicons”.  It turns out that fetching each of these from the web takes on the order of three seconds, so I fetch them in parallel to shorten the application’s startup time. 

let GetIcon (uri:string) =
    let iconDecoder = new IconBitmapDecoder(new Uri(uri), BitmapCreateOptions.None, BitmapCacheOption.Default)
    iconDecoder.Frames.[0]
let [| soIcon; hubfsIcon |] = 
    [| async { return GetIcon "http://sstatic.net/so/favicon.ico" } 
       async { return GetIcon "http://cs.hubfs.net/favicon.ico" } |]
    |> Async.Parallel |> Async.RunSynchronously

That’s a simple use of F# ‘async’ for fork-join parallelism – create an array of async computations and run then in parallel.

Details about the feeds

Now for the feeds I want to appear in the grid.  I have some feeds from StackOverflow as well as the hubfs feed.

It turns out that whereas StackOverflow publishes “LastUpdated” information (e.g. the most recent answer/edit of a question) in its RSS feeds, hubfs does not (it only has the original publishing date – e.g. the date a question was first asked).  Thus I need to use a different comparator for sorting items from each of these feeds.  I define a couple functions to project out the field I want to use for comparing items for new-ness.

let PublishDate (item:SyndicationItem) = item.PublishDate 
let LastUpdate (item:SyndicationItem) = item.LastUpdatedTime 

let feeds = [|
    "http://stackoverflow.com/feeds/tag/f%23",                   "F#",                     LastUpdate, soIcon, true
    "http://stackoverflow.com/feeds/tag/functional-programming", "Functional Programming", LastUpdate, soIcon, true
    "http://stackoverflow.com/feeds/tag/recursion",              "Recursion",              LastUpdate, soIcon, true
    "http://cs.hubfs.net/forums/aggregaterss.aspx?Mode=2",       "HubFS",                  PublishDate, hubfsIcon, true 
    "http://stackoverflow.com/feeds/tag/c%23",                   "C#",                     LastUpdate, soIcon, false            
    "http://stackoverflow.com/feeds/tag/lambda",                 "lambda",                 LastUpdate, soIcon, true
    |]

Then I have a big array of all the feeds, where each item is a tuple of the URL, the title to appear in the UI, the comparison-projection function (just described), the icon to appear in the UI, and a boolean that says whether to speak question titles aloud.

Some WPF helpers

My user interface is basically a Grid of Grids of Grids.  :)  So of course I define a helper function and extension method for creating and positioning grids and their elements.

// WPF helpers
let MakeGrid(cols, rows) =
    let auto = GridLength(1.0, GridUnitType.Auto)  // 1.0 * desired content height/width
    let grid = new Grid()
    for i in 1..rows do
        grid.RowDefinitions.Add(new RowDefinition(Height = auto))
    for i in 1..cols do
        grid.ColumnDefinitions.Add(new ColumnDefinition(Width = auto))
    grid
type System.Windows.Controls.Grid with
    member this.AddAt(col, row, element) =
        Grid.SetRow(element, row)
        Grid.SetColumn(element, col)
        this.Children.Add(element) |> ignore

type System.Windows.UIElement with
    member this.WrappedInBorderWithThickness(borderThickness) =
        new Border(BorderThickness = Thickness(borderThickness), Child = this)
    member this.WrappedInBorderWithThicknessAndColor(borderThickness, brush) =
        new Border(BorderThickness = Thickness(borderThickness), BorderBrush = brush, Child = this)

My UI also uses borders, so I define a couple useful extension methods for that.

How long ago?

In order to have pretty “ago” information, like “1 hour ago” or “6 minutes ago” or whatever, we need to code it up:

// other helpers
let Ago(date : DateTimeOffset) = 
    let diff = DateTimeOffset.Now - date
    if diff < TimeSpan.FromHours(1.0) then
        match diff.Minutes with
        | 1 -> "1 minute ago"
        | x -> sprintf "%d minutes ago" x
    elif diff < TimeSpan.FromDays(1.0) then
        match diff.Hours with
        | 1 -> "1 hour ago"
        | x -> sprintf "%d hours ago" x
    else
        match diff.Days with
        | 1 -> "1 day ago"
        | x -> sprintf "%d days ago" x

So now I can pass in e.g. a LastUpdatedTime and get back a pretty “ago” string.

Link coloring

The all-important hyperlink coloring:

let visitedLinkDiscoverer = new DiscoverIEVisitedLinks.IEVisitedLinksDiscoverer()

let LinkColor(uri) = 
    if visitedLinkDiscoverer.IsUriVisited(uri) 
    then Brushes.Purple 
    else Brushes.Blue

Opening a browser

This is the scariest part of the app.  I want to open a new tab in my existing IE browser instance, so that I will have all my cookies and login credentials and such.  There’s any easy way to do this: Process.Start().  But that’s scary, because it basically says “run this string”.  And the string is data I just got from some random location on the web!  Your security spidey-sense ought to be tingling; mine is.  In the end, I just try very hard to ensure the string looks very much like a simple URL, so that I feel good that calling Process.Start on the string will just open a browser tab.  But I am interested to hear if people know a better/safer way to do this!

let OpenInBrowser (uri:string) =
    // Check belows is my attempt to validate input (link from rss feed) from accidentally running arbitrary code on 
    // this box (Process.Start).  Would be great to think more about security implications.
    if not(uri.StartsWith("http://")) then
        Debug.Assert(false, sprintf "Uri '%s' does not start with http://, so not trying to open it" uri)
    else
        try
            let parsedUri = (new Uri(uri)).AbsoluteUri // ensure legal Uri, else will throw
            // Process.Start uses my existing browser window (opens a new tab), rather than starting new window, 
            // which is good because existing browser window has my cookies/login/credentials.
            Process.Start(parsedUri) |> ignore  
        with e ->
            Debug.Assert(false, sprintf "Uri '%s' did not parse, or Process.Start failed" uri)

When new items arrive

This code has the main bit of ‘update logic’.  I have some old items (along with data about whether they’re yellow-highlight-new and whether they need to be announced), and some new data from a recent poll of the RSS feed, and now I have to compute what are the newest items that should be displayed.  The comparison-projection function (as described above) is passed in as a parameter to correctly sort new items by new-ness.

// Item update logic
let ComputeNextItems(compProjection, oldItems:seq<SyndicationItem*bool*bool>, newItems:seq<SyndicationItem>) =
    // 1st bool represents whether item is new to the user (highlight), 2nd whether needs to be announced (new to speech)
    let newItems = newItems |> Seq.toArray 
    // sort by newness
    newItems |> Array.sortInPlaceWith (fun x y -> compare (compProjection y) (compProjection x))
    // remove duplicate ids (e.g. may have two items with same Id but different LastUpdatedTimes, keep most recent)
    let newItems = newItems |> Seq.distinctBy (fun x -> x.Id) |> Seq.toArray 
    // remove any old items that have since been updated
    let nonUpdatedOldItems = 
        oldItems |> (newItems |> Seq.fold (fun f item -> f << Seq.filter (fun (x,_,_) -> x.Id <> item.Id)) id)
    // remove enough more olds (the oldest ones, at the end of the list) to have room for all the new ones
    let numOldToKeep = max 0 (NumItemsPerFeed - newItems.Length)
    let oldKeepers = Seq.take numOldToKeep nonUpdatedOldItems
    let newKeepers = Seq.take (NumItemsPerFeed - numOldToKeep) newItems
    Seq.append (newKeepers |> Seq.map (fun x -> x,true,true)) oldKeepers |> Seq.toArray 

Note the interesting use of Seq.fold to build up a filtering function that filters out any oldItems that match any of the newItems’ Ids.

Little text helpers

Sometimes the titles have these escaped bits of HTML, so I unescape them…

let WashText (text:string) =
    text.Replace("&quot;", "\"")
        .Replace("&amp;", "&")
        .Replace("&lt;", "<")
        .Replace("&gt;", ">")

let ShortenTitle(title:string) =
    match title.LastIndexOf(' ') with
    | -1 -> title
    | i -> title.Substring(0,i)+"..."

…and some titles are too long to display, so I find word boundaries to (progressively) shorten long titles with an ellipsis (see below).

Filling a grid with the most recent items

Ok, now we’re getting to the meat.  I have an array of item data, and I need to draw the data portion of the grid:

GridData

and possibly also announce some titles.  Here’s the code:

let rec PopulateGridItems(items : array<SyndicationItem*bool*bool>, grid:Grid, shouldSpeak) =
    for i in 0..items.Length-1 do
        let item,isNewForHighlight,isNewForSpeech = items.[i]
        let uri = item.Links.[0].Uri
        let MakeRow(title) = 
            let link = new Hyperlink(new Run(title), NavigateUri = uri, Foreground = LinkColor(uri.AbsoluteUri))
            link.Click.Add(fun _ -> Async.StartImmediate( async {
                    OpenInBrowser uri.AbsoluteUri
                    do! Async.Sleep(2000) // give browser a chance to open the link, so will be purple on redraw
                    grid.Children.Clear()
                    PopulateGridItems(items, grid, shouldSpeak)    }))
            let row = new TextBlock(FontSize = 16.0)
            if isNewForHighlight then
                row.Background <- Brushes.Yellow 
            row.Inlines.Add(link)
            row.Inlines.Add(new Run("  " + Ago(item.PublishDate)))
            row
        let rec FitTitleToReasonableWidth(curTitle) =
            let row = MakeRow(curTitle)
            grid.AddAt(0, i, row) |> ignore
            row.UpdateLayout()
            if row.ActualWidth > 650.0 then
                let newTitle = ShortenTitle(curTitle)
                if newTitle <> curTitle then
                    grid.Children.Remove(row)
                    FitTitleToReasonableWidth(newTitle)
        let title = item.Title.Text |> WashText
        if isNewForSpeech && shouldSpeak then
            Speech.EventuallySpeak(title)
            items.[i] <- item,isNewForHighlight,false
        FitTitleToReasonableWidth(title)

I loop over all the items.  I grab the link uri.  The MakeRow() function makes a single row, with a given title.  The row has a Hyperlink followed by a Run of text, and this all may get a yellow highlight.  When you click the link, the Click handler will open the uri in a browser, wait a couple seconds, and then redraw this portion of the UI (so as to update the purple-ness of the link that was just clicked).  Note the nifty use of ‘async’ here – I use Async.StartImmediate, which means all the code runs on the UI thread (where the Click handler starts), but I can still do non-blocking sleeps that don’t jam up the UI.  This is one way that F# async just blows the doors off everything else.

FitTitleToReasonableWidth(): I don’t know an easy way to predict how wide the rendered text will look; it depends on the exact text of the title, the font, kerning, etc.  So I just create the row with a given title, lay it out, and then see what its actual width would be.  If it’s too wide, I shorten the title and try again.  Simple enough.

I “wash” the title text, announce it if necessary, and then make an appropriate-sized row for it.

Main window, part one

I haven’t written many UI apps, but the ones I’ve written seem to have a curious feature in common: they don’t have any methods; they just do all the work in the constructor (which typically includes code to set up various event-handlers, which are just inline lambdas).  I’m not quite sure what to make of this, but thought I’d call it out.  Anyway, this UI app is no different.  I create my own window type, and its constructor is effectively two lines long.  I set the title, and then I add a handler for the Initialized event.  The handler just happens to be a 50-line lambda.  :)  Here’s the start:

// Main UI        
type MyWindow() as this =
    inherit Window() 
    do
        this.Title <- "RSS Dashboard"
        this.Initialized.Add(fun _ ->
        let wholeWindow = MakeGrid(1,2)
        this.Content <- wholeWindow
        let grid = MakeGrid(2,3)
        wholeWindow.AddAt(0, 1, grid.WrappedInBorderWithThicknessAndColor(1.0, Brushes.Black))
        let markAllAsSeenButton = new Button(Content = new TextBlock(Text="Mark all as seen"))
        wholeWindow.AddAt(0, 0, markAllAsSeenButton)
        // We don't have the SynchronizationContext in the constructor, which is why the whole rest 
        // of the method waits for the Initialized event to run
        let syncContext = System.Threading.SynchronizationContext.Current 

The window content is a grid with two rows – the button at the top, and the rest, which is itself another 2×3 grid of each feed.  I grab the SynchronizationContext, which is basically a handle that allows you to ‘get on the UI thread’ – we’ll see why in a moment.

Main window, part two

We’re going to make 6 feed grids, and so I define a function to make a grid for a single feed.  It takes as parameters the five pieces of data about each feed (from the array-of-feed-info we defined at the top of the program):

        let MakeFeedGrid(feedUrl:string, topicName, compProjection, topicIcon, shouldSpeak) =
            // upper is 'title bar' of grid
            let upper = MakeGrid(2,1)
            upper.AddAt(0, 0, new Image(Source = topicIcon, Height = 16.0, Width = 16.0))
            let title = new TextBlock(FontSize = 20.0)
            title.Inlines.Add(new Underline(new Run(topicName)))
            upper.AddAt(1, 0, title.WrappedInBorderWithThickness(3.0))
            // lower is 'content portion' of grid
            let lower = MakeGrid(1,NumItemsPerFeed)
            let items = ref [||]  // the main mutable state - only read/update this on the UI thread
            let Redraw() = lower.Children.Clear(); PopulateGridItems(!items, lower, shouldSpeak)
            let feedSrc = new ObservableFeed.FeedSource(feedUrl, FeedUpdateFrequency)
            let obs = feedSrc.AllUpdates |> ObservableFeed.Batch 
            obs.Subscribe(fun newItems -> syncContext.Post(fun _ ->
                let firstTime = (!items).Length = 0
                items := ComputeNextItems(compProjection, !items, newItems)
                if firstTime then
                    // first time, mark nothing as new to user (no highlights, nothing to announce)
                    items := !items |> Array.map (fun (i,_,_) -> i,false,false)
                // TODO what if fewer than desired number of items?  indeed this fails sometimes
                Debug.Assert((!items).Length = NumItemsPerFeed, "TODO fix this")
                Redraw()
            , null)) |> ignore
            markAllAsSeenButton.Click.Add(fun _ -> 
                items := !items |> Array.map (fun (i,_,b) -> i,false,b)
                Redraw())
            async { 
                while true do
                    do! Async.Sleep(60000)  // every minute...
                    Redraw()  // ... redraw, so as to recompute e.g. '3 minutes ago' to be current in the display
            } |> Async.StartImmediate 
            feedSrc.Start()
            // combine upper and lower
            let grid = MakeGrid(1,2)
            grid.AddAt(0, 0, upper.WrappedInBorderWithThickness(5.0))
            grid.AddAt(0, 1, lower.WrappedInBorderWithThickness(5.0))
            grid.WrappedInBorderWithThickness(5.0).WrappedInBorderWithThicknessAndColor(1.0, Brushes.Black)

The grid for each feed has two parts – an ‘upper’ part which is the title bar (itself a 2×1 grid containing an icon and the title), and a ‘lower’ part which contains the ‘grid items’ we saw in PopulateGridItems().  The ‘backing store’ for the items is a mutable reference to an array.  (All the code runs on the UI thread, so we don’t need to worry about locking the mutable data.)  For each feed grid, we create a FeedSource object for this URL that will poll with the FeedUpdateFrequency we defined in the constants at the top.  We grab the AllUpdates observable, Batch those up, and Subscribe with a handler for newItems.  The FeedSource runs and fires events from an arbitrary background thread, so this is the one place in the main program where we’re off the UI thread.  We get back on the UI thread by calling SynchronizationContext.Post.  The very first time we visit each feed, everything will appear ‘new’, so we go flip the newness booleans to false the first time around (to avoid having everything get a yellow highlight and having every title announced when the app first starts up).  Otherwise, each time the FeedSource fires new data at us, we use it to compute the next set of items to display and redraw this portion of the display.  (Once upon a time there was a bug here; I may have fixed it, but I left the assert I was using to catch it.)

I attach a handler to the “mark all as seen” button.  If you click the button, I flip all the ‘yellow highlight’ booleans for this feed back to false, and then redraw.

Our “ago” information (“3 minutes ago”) will quickly get stale if we don’t refresh it, so we start a loop that redraws every minute.  Once again, F# async kicks butt, as I can just write this as though it were a synchronous loop running on the UI thread, but the non-blocking sleep call ensures that the UI stays live.  Awesome.

Since we have already done all the subscribing to the IObservable and wiring things up, we can go ahead and tell the FeedSource to Start().

I finish by putting the upper and lower portions of the UI together into a grid that gets returned.

Main window, part three

Now that I have the MakeFeedGrid function, I just call it for each feed:

        grid.AddAt(0, 0, MakeFeedGrid(feeds.[0]))
        grid.AddAt(0, 1, MakeFeedGrid(feeds.[1]))
        grid.AddAt(0, 2, MakeFeedGrid(feeds.[2]))
        grid.AddAt(1, 0, MakeFeedGrid(feeds.[3]))
        grid.AddAt(1, 1, MakeFeedGrid(feeds.[4]))
        grid.AddAt(1, 2, MakeFeedGrid(feeds.[5]))
        )
    
[<STAThread>] 
do  
    let app =  new Application() 
    app.Run(new MyWindow()) |> ignore 

(The close-paren ends the Initialized handler.)  Now I kick off the WPF app.  That’s it, we’re done!

Summary

In less than 500 lines of code, we’ve created a useful little app for keeping up with RSS feeds.  Along the way we leveraged a variety of different technologies, including WCF (both for SyndicationFeeds and for a mini-web-server), IObservables (for a background feed-polling eventing model), speech synthesis (to announce question titles as new data arrives), COM interop and some crazy Javascript (to get link coloring info from IE), and WPF (to draw the user interface).  Despite the fact that work happens on a variety of different threads, we didn’t have to use low-level APIs like Thread or BackgroundWorker.  Rather, we used a MailboxProcessor to create an agent to queue up messages to the speech synthesizer, and used F# asyncs both for writing apparently-single-threaded code with non-blocking calls and sleeps, as well as for simple fork-join parallelism.

I really enjoyed putting together a small-but-non-trivial, useful app that spanned so many concepts and technologies.  I hope you enjoyed reading about it.

Full Source Code

In addition to enjoying reading the blog series, you’ll enjoy playing with the code yourself, so here it all is.

Posted in Uncategorized | Leave a Comment »

An RSS Dashboard in F#, part five (Javascript, COM interop, and WCF services – oh my!)

Posted by Brian on February 15, 2010

Previous posts in this series:

Last time I covered using an F# agent, along with the .Net speech synthesis libraries, to provide an easy API to communicate via the computer speakers without having to worry about threading issues.  Today I’m switching gears again, with the oh-so-lofty goal of finding out whether URL links should be colored blue or purple in my UI.  The implementation will use COM interop and Javascript (two technologies I had almost zero previous experience with), as well as a WCF service (which I know well).  Fortunately, my tools will make this easy on me; F#+.Net is a winning combination to get most any job done.

The goal

Let me quote myself from the introductory entry of this blog series:

I really wanted the links in my app to be the same color as the links in my browser.  But I also wanted my entire UI to be hand-coded WPF (I didn’t want to create HTML and host that in a browser, that is not fun/interesting to me).  So I needed a way to get IE to tell me what color each link should be.  Perhaps there is a simple(r) way to do this, but I did find a way that involved hosting an invisible IE control that browses some HTML-and-Javascript my app serves to get the info it needs.  It’s one of those hacks that you know is awful, but you nevertheless grin about, because it works.  (I’d never written a line of Javascript before this – more unexpected new technology.  Score!)

That about sums it up.  You can see from the colors in the screenshot from part one what I desired, but this requires knowing which links are ‘visited’ and which are not, so I can color each link appropriately.  It turns out, this information can be had via unusual means…

The strategy

I recalled a while back seeing a trick that made the rounds as a brief internet meme, where you’d visit a web site and the site would tell you information about your own browsing history.  You can find a good description of the underlying technique here.  The idea is you have some Javascript on your page that runs in the client browser and discovers whether the browser thinks a link is visited or not.  I don’t know any Javascript, but I have friends who do, who helped me hack together just enough to do what I needed.  In the end I had a Javascript function that takes a URL as a parameter and returns true or false depending on if the link is ‘visited’.  (I don’t know if the Javascript is portable, but it works on my machine at work in IE8.  Which is sufficient, this was all about hacking a useful app for my own selfish interests.)

I originally tried just saving the HTML-with-Javascript as a local “file:///blah…” URI, but for whatever reason (internet security options? I never spent enough effort trying to diagnose it) that didn’t work.  Fortunately, as a veteran developer from the WCF team, I can write a quickie HTTP server in 10 lines of code, and sure enough, serving my page as “http://localhost…” worked.  So I took the path of least resistance, even though it’s total overkill.

Finally, I needed a way to run the Javascript programmatically from my app (rather than in an actual instance of a browser).  Once again, the platform has APIs for all of this; I had to poke around a bit, but found that adding COM References (in Visual Studio, “Add Reference”, then go to the “COM” tab) to “Microsoft Internet Controls” and “Microsoft HTML Object Library” gave me access to some ugly COM objects going by names like “SHDocVw.InternetExplorerClass” and “mshtml.IHTMLDocument”, which had the APIs to create a browser control, navigate to my document, get the Javascript running in the context of the browser, and call it from my app.

The code

Here’s all the code for today, followed by some commentary.

open System
open System.Reflection 
open System.Runtime.InteropServices 
open System.ServiceModel
open System.ServiceModel.Web
open System.IO 

[<ServiceContract>]
type MyContract() =
    // Javascript that can be used in IE8 to determine if a Uri is visited
    let magicHtml = @"
    <!DOCTYPE HTML PUBLIC ""-//W3C//DTD HTML 4.0 Transitional//EN"">
    <html><head><script type=""text/javascript"" language=""javascript"">
            function IsUriVisited(uri) {
                var iframe = document.createElement(""iframe"");
                iframe.style.visibility = ""hidden"";
                document.body.appendChild(iframe);
                iframe.doc = iframe.contentWindow.document;
                iframe.doc.open();
                iframe.doc.write('<style>');
                iframe.doc.write(""a{color: #000000; display:none;}"");
                iframe.doc.write(""a:visited {color: #0000FF; display:inline;}"");
                iframe.doc.write('</style>');
                iframe.doc.close();
                var a = iframe.doc.createElement(""a"");
                a.href = uri;
                a.innerHTML = ""blah"";
                iframe.doc.body.appendChild(a);
                var didVisit = a.currentStyle[""display""] != ""none"";
                iframe.parentNode.removeChild(iframe);
                return didVisit;
            }
        </script></head><body></body></html>"
    [<OperationContract>]
    [<WebGet(UriTemplate="*")>]
    member this.Get() : Stream =
        upcast new MemoryStream(System.Text.Encoding.UTF8.GetBytes(magicHtml))

type IEVisitedLinksDiscoverer() =
    let mutable resultType = null
    let mutable htmlDoc = null
    let mutable script = null
    let mutable host = null
    do
        // We need to serve that Javascript HTML on a web page (rather than local file) 
        // to get the script to run.  So host a local web service to serve the HTML.
        let javascriptHtmlLocation = "http://localhost:64385/"  // TODO ideally this would pick an open port or let user configure it
        host <- new WebServiceHost(typeof<MyContract>, new Uri(javascriptHtmlLocation))
        host.AddServiceEndpoint(typeof<MyContract>, new WebHttpBinding(), "") |> ignore
        host.Open()
        // COM Reference: Microsoft Internet Controls
        let ie = new SHDocVw.InternetExplorerClass()
        ie.Navigate(javascriptHtmlLocation)
        while (ie.Busy) do
            System.Threading.Thread.Sleep(500);
        // COM Reference: Microsoft HTML Object Library
        htmlDoc <- ie.Document :?> mshtml.IHTMLDocument
        script <- htmlDoc.Script
        resultType <- script.GetType()
    // must be called on STAThread
    member this.IsUriVisited(uri:string) =
        resultType.InvokeMember("IsUriVisited", BindingFlags.InvokeMethod, null, script, [| box uri |]) :?> bool
    interface IDisposable with
        member this.Dispose() =
            Marshal.ReleaseComObject(script) |> ignore
            Marshal.ReleaseComObject(htmlDoc) |> ignore
            try host.Close() with e -> ()

The big red string constant is the HTML document I need to serve.  It’s just a document skeleton with a Javascript function in it.  The Javascript does some black magic to compute if a particular URL is a visited link or not.

I can serve this document over HTTP GET on localhost with a tiny WCF web service.  To describe what I want to serve, I created a tiny MyContract class, with a single Get() method that returns the document as a Stream.  I mark up the class with the appropriate WCF attributes.  That’s just 6 lines of code in addition to my giant string constant.

Now for the API I want clients to use.  I create a class called IEVisitedLinksDiscoverer.  It just exposes one method, IsUriVisited().  When you construct an instance of this class, it starts a WCF server (3 more lines of code – the ones starting with “host”) on a crazy (likely-to-be-unused) port number.  Then it news up an instance of the IE control, navigates to the page, grabs the document, and gets the script out of the document.  Now we have a handle by which we can call the Javascript via reflection.  (To figure out these few lines of code, I did a web search, found some code that looked promising, and then tweaked it until it worked.  I was wearing my Mort hat.)

The IsUriVisited() function uses the .Net reflection APIs to call the Javascript function stored inside the script object.  I don’t know exactly what magic is happening under the covers here, but it works.  Hurray.

The ‘discoverer’ object implements IDisposable so we can be good citizens and clean up when we’re done.  This includes releasing the COM objects we created and shutting down the WCF service.  I’m ignoring any error code or exceptions that happen here (since I’m only going to Dispose() when the app finishes running).

Here’s some tiny client code that demonstrates how this can be used to find out which links are visited:

let Main() =
    use disc = new IEVisitedLinksDiscoverer()
    printfn "%A" (disc.IsUriVisited("http://stackoverflow.com/questions/tagged/f%23"))
    printfn "%A" (disc.IsUriVisited("http://www.google.com/"))

[<System.STAThread>]
do
Main()

which, of course, prints “true” and “false”.  I hereby pronounce this code “good enough”!

Summing up

There are times when you want to do thing “the right way”, “elegantly”, etc… and then there are times when you are happy to be quick-and-dirty, and just get something working.  F# is a good tool in both of these roles.  Today’s topic was all about quick-and-dirty; I knew what I wanted done, I envisioned one way to achieve that goal, and I just plowed through, combining three technologies in just one screenful of code.  I used Javascript to do a little browser-magic, COM interop to talk to some browser controls, and a WCF service to serve up my document over HTTP.

A great thing about F# is that the .Net platform integration makes it so easy to combine all these various technologies to knock up some code that gets the job done.

Next time

We’re almost done!  At this point in the blog series, we’ve walked through all the ‘guts’ of the application.  The only remaining thing to do is assemble all the pieces and slap a dazzling WPF UI on top of it.  App ahoy!

Posted in Uncategorized | Leave a Comment »

How to _really_ be an evil genius (with F#)

Posted by Brian on February 14, 2010

(Starting aside: There’s a new F# release out, check it out.)

My coworker Chris claims to be an evil genius.  He recently posted a blog about how to automatically solve the Bookworm word search.  I was looking at his code, and thought, “There’s no way he’s ever going to take over the world with that implementation…” 

So I wrote my own version.  Which is three times shorter.  And uses less memory.  And is much simpler to read.  Oh, and it runs way faster too.  Which begs the question…

Who’s the evil genius now?

All trash talk and no code makes for a bad blog entry, so let’s get to it.

The Problem

There’s a game called Bookworm you can play on the web (or also on some crazy pocket-gadget you might have heard of).  You have a grid of letter tiles and you’re trying to find words like “BREAK”:

bookworm

There’s a dictionary of all the legal words you can use (details below).  The goal is, given as input one of these letter grids, find all the words.  You can only move to hexagonally adjacent tiles, and you can’t use the same letter tile more than once in a word. 

Simple, right?  Classic search problem.  I immediately started thinking of the optimal data structures to use to make this simple and efficient to code. 

The Strategy – the dictionary

There is a data structure that’s especially well-suited to representing a word dictionary for this type of problem.  It’s called a “prefix tree” or “trie”, and it is a very useful data structure to have in your back pocket.

(Chris also chose a trie for his implementation – awwww, snap! – Chris actually did something right!  Of course, his implementation is memory-heavy, creating a lot of garbage along the way.)

So let’s explain this trie thing.  It’s simple.  We represent a dictionary of words as a bunch of TrieNodes.  Each TrieNode contains two things.  First, an array of 26 references to other TrieNodes (26 letters in the alphabet – get it?).  Second, a boolean, which repesents if a word just ended here.  A picture is worth a thousand words.  Rather than just copy a diagram off wikipedia like some people (*cough*), I’ll draw my own to show off my mad skillz with MS Paint:

TrieDiagram

In the diagram, each big rectangle is a TrieNode, and each node has got a 26-wide array of “pointers” to other nodes, and a boolean (represented by a red or green box – I’ll let you guess which color means ‘true’).  If you don’t see a squiggle-line coming out of the bottom of one of the little boxes in the array, it means that array cell is null, dig?  So to find out of “BET” is a word in the trie, we start at the root node and look at cell.[1] in the array (A=0, B=1, C=2, … and we want the “B”, the first letter of “BET”).  It’s got a pointer to another TrieNode, so we follow that pointer and then look up the next letter in cell.[4] (because? … E=4, right), and that’s a pointer to another TrieNode, so we go there and look up cell.[19] (T=19), and that’s a pointer to another node, so we go that that node, but now we have no more letters, and thus we have traversed “B-E-T” and check the boolean in the final TrieNode we landed at to see if a word ends here.  Yes, the boolean is true (green), so we determine that “BET” was in this trie.  You can follow similar logic for “BE” or “A”.

What if we try to look up “BAT”?  We follow cell.[1] down to the ‘B’ node, but then when we look there in cell.[0] for the ‘A’, we see it’s null (no squiggly line coming out of there).  That means we stop searching, “BAT” is not stored in this trie; “BA” is not the prefix of any word in the trie.

Is just “B” a word in this trie?  Again we start by following cell.[1] down to the ‘B’ node.  But now there are no more letters in the word we are trying to look up, so we check the boolean here.  It’s false (red), which means “B” is not in the trie.

If you want to add a word to an existing trie, you just have to walk down each letter of the word you’re adding (creating fresh TrieNodes along the way if you encounter nulls), and then once you’ve finished all the letters of the word you’re adding, flip the boolean in the final TrieNode to true, to mark it as a word-ender.

Great, you now know everything there is to know about how tries work.  Let’s code the sucker up.

Trie implementation

Simple is good.  Let’s keep things simple.  All the Bookworm words contain only UPPERCASE LETTERS.  Pipe down, I’m not shouting at you, I’m illustrating.  So here’s a useful function we’ll be calling from a few places:

let IsLetter(c)   =    c>='A' && c<='Z'

Get it? Good, because if you don’t, you may want to quit reading right now.  You might prefer IsUppercaseLetter or IsLegalBookwormLetter or some such name for this function.  But I like this name.  The whole program is about Bookworm, and as far as Bookworm is concerned, there are only 26 “letters”, and these are they.  End of story.  Moving on!

(In point of fact, Bookworm treats “Qu” as one letter, but Chris ignores this, and so will I.  (But at least I’m explicitly pointing it out.))

What’s the ideal public API for a TrieNode?  Well, think back to our diagram.  At any given node, we want to know if it’s an “end of word”, so we need to surface that boolean as a property, like “node.IsEndOfWord”.  At a given node, we want to be able to “move forward” to some letter, e.g. go to ‘E’ from here.  So we would like an indexer that lets us do node.[‘E’] to get a reference to the next node down.  And finally we need a way to populate the tree, so let’s have a method that lets us say rootNode.Add(“BET”) to add that word to the trie.  (Yes, this means the trie is mutable.  It is much simpler to build the trie using mutation.  Just because you’re an F# programmer and all into “functional” doesn’t mean you can’t use arrays and mutation when they’re the simplest tool for the job!  Be pragmatic.) 

Hmm, is that everything?  Let’s try to write the client code we’ll need to build a trie and do some ad-hoc testing, in order to test drive the API we’re picturing.  Assume we have a list of words already and we want to make a trie of all those words:

let trie = new TrieNode()
for w in words do
    trie.Add(w)

Yeah, that looks good.  And now let’s hack a quick function to check if words are in the trie:

let rec IsWord(s:string, t:TrieNode) =
    if t=null then false
    elif s.Length=0 then t.IsEndOfWord
    else IsWord(s.Substring(1), t.[ s.[0] ])

We’ll be walking down the trie, and if we “fall off the end” (reach null), then there’s no word with that prefix, else if we walked all the way to the end of the word we’re looking up, when we just check the boolean in the current TrieNode to see if it’s a word, else if we still have more letters, we recurse.  The Substring() call at each step is inefficient (allocating a new string each time), but that’s ok, because I’m only using this function for this quickie test suite:

assert(IsWord("ABSTRACTIONISMS", trie))
assert(IsWord("MONSOON", trie))
assert(not(IsWord("QZXWWK", trie)))

to verify that things appear to maybe be ok.  Great.  We have a public API design that seems ok, and a tiny set of tests, let’s try to write our TrieNode class.  In four tiny steps:

[<AllowNullLiteral>]
type TrieNode() =
    let nextChar = Array.create 26 null
    let mutable isEndOfWord = false

We define a TrieNode class.  By default, instances of classes in F# can’t be null, but we want to use nulls to signify non-entries in the trie, so we add an attribute to allow it.  The class has two fields – the array of size 26, which we initialize to nulls, and the boolean, which we start as false.

We want the boolean exposed as a public property, so, shazam:

    member this.IsEndOfWord = isEndOfWord

We want to be able to use a character to index the next node down, so we write that indexer property.  Only the getter needs to be public in the API, but as we’ll see in a moment, we’ll want a private setter too (to use in the Add() implementation).  We need to convert ‘A’ to 0, ‘B’ to 1, etc., so we write

    member this.Item with get(c:char) = nextChar.[int c - int 'A']
                     and private set(c:char) v = nextChar.[int c - int 'A'] <- v

(Note that in F#, if you write an indexer property named “Item”, then you can use the object with array syntax, e.g. node.[‘E’].) 

Finally we write our Add() method, the only bit of code with any meat:

    member this.Add(word) = 
        assert(word |> Seq.forall IsLetter)
        this.Add(word,0)
    member private this.Add(word:string,i) =
        if i = word.Length then
            isEndOfWord <- true
        else 
            match this.[word.[i]] with
            | null -> let newNode = new TrieNode()
                      newNode.Add(word,i+1)
                      this.[word.[i]] <- newNode
            | node -> node.Add(word,i+1)

Add asserts that the word contains nothing but LETTERS and then calls a little recursive helper method, which takes as arguments the word we’re adding, and which character index we’re at (equivalently, how deep into the trie we’ve gone).  If we have traversed all the way down to the end of the word, we’re at the right node in the trie to just flip the ‘end of word’ bit to true to mark that there’s a word that ends here.  Otherwise, we still need to go deeper, so we look in this node’s array at the current character.  If it’s null, we need to create a fresh new node at this letter, and add the rest of the word to that.  Otherwise if there’s already a node there, then just recurse on down.

Feel free to trace through this on a sheet of paper with a fresh trie and add “A”, “BE”, and “BET” and see if you get a pretty picture like my earlier diagram.

Ok, that’s it.  The whole TrieNode class is less than 20 lines of code.

Now we need our dictionary of English words.  It turns out there’s some huge dictionary file full of

WORDS
LIKE
THIS

one per line, as well as a small file of words that aren’t allowed.  I dunno, I just did basically what Chris did:

let words = seq {
    let toIgnore = System.IO.File.ReadAllLines("IgnoredWords.txt") |> Set.ofArray
    for word in System.IO.File.ReadAllLines("TWL06.txt") do
        assert(word |> Seq.forall IsLetter)
        if not (toIgnore.Contains word) && word.Length >= 3 then
            yield word }

(I’ve linked the text files containing the words at the end of this blog entry, right above the full source code.)  Oh yeah, Bookworm only allows words that are at least three letters long, hence that “Length>=3” check.

Ok, I hit F5 to run my code so far in VS, and before you can say “blueberry pie” the thing is done, no asserts.  We have a big English dictionary stored in a trie, now we are go for search!

The Strategy – word search

One of the thing that makes Bookworm interesting is the hexagonal grid.  (This ain’t your run-of-the-mill square-grid game like Boggle!)  So we need a good board representation that enables easy hexagonal search.

Chris, predictably, goes nuts here, with some crazy “ITile” interface with a Neighbors property and Locations and all kinds of garbage like that.  Classic overengineering.  Hey Chris, it’s no wonder your volcano lair got foreclosed on!  Sure, blame the economy, I’m sure it wasn’t because of all the wasteful–

<deep breath>

Ok, I’m digressing.  Back on task.

If you want hexagonal search, there’s a good data structure for this.  It’s not rocket science.  You’ve heard of this data structure before.  They even have it in C.  It’s called a 2-D array.  Check it out:

        O U B N O V S 
         J A P A L O M
        G T E J T S H 
         U A E O F S A
        N O A E L E P 
         O S O U G N P
        A T F G A I I 

It’s a 2-D array of characters, where every other character is a space (kinda like a checkerboard, with letters as black squares and spaces as red ones, or whatnot).  We can index every cell with a pair of (x,y) coordinates.  And if, say, the green ‘A’ above happens to be at coordinate (x,y), then its six neighbors are like (x-1,y-1), (x+1,y-1), (x-2,y), (x+2,y), (x+1,y-1), (x+1,y+1).  See?  Simple.  It even looks like the board, once you tilt your head to the left (each ‘row’ is actually a ‘column’).

Of course, say we were at the ‘O’ in the upper left corner at coordinate (0,0).  If we try to get the neighbor at (x-1,y-1), we’ll look into cell [-1,-1] of the array and get an IndexOutOfRangeException.  Now we could be like Chris, and have an elaborate ‘validIndex’ checking function at every array lookup, to ensure we don’t go off the side of the board.  Or we can play it smart and simple, and just surround the array with some extra padding of spaces, so it won’t matter if we look outside the word grid.  Yeah, let’s do that.

Let’s also be flexible and allow any number of columns and rows. 

Board&search implementation

Consider the screenshot again:

bookworm

We can type up this input easily as

let COLS = 7
let ROWS = 8
let data = [|  // columns
        "  K M E M T O O "
        " E F K I M C A D"
        "  A A E R E A F "
        " T D A I B N D J"
        "  V F F A T E E "
        " O J T R F I R R"
        "  I R D R E E O "
    |]    

where we say there are 7 columns (COLS), each with at most 8 letters (ROWS), and an array of strings makes it easy to lay out the data like the screenshot (don’t forget to tilt your head to the left when looking at the code – this is your exercise for the day).  Ok, let’s convert this to a 2-D array with extra space-padding around the outside.  I’ll call this structure a “board”:

// surround entire grid with border of spaces (one extra column, two extra rows)
let BOARDCOLS = COLS + 2
let BOARDROWS = 2*ROWS + 4
let MakeBoard(columns:string[]) =
    assert(columns<>null)
    assert(columns.Length = COLS)
    assert(columns |> Seq.forall (fun s -> s.Length = ROWS*2))
    for i in 0..COLS-1 do
        for j in 0..ROWS*2-1 do
            let c = columns.[i].[j]
            if (i+j)%2 = 0 then assert(c=' ' || IsLetter c)
            else                assert(c=' ')
    Array2D.init BOARDCOLS BOARDROWS (fun c r ->
        if c=0 || c=BOARDCOLS-1 || 
           r=0 || r=1 || r=BOARDROWS-2 || r=BOARDROWS-1 then ' '
        else columns.[c-1].[r-2])

The first 8 lines of the MakeBoard function are just assertions to help ensure you didn’t screw up when you typed in the data.  All the real work is in the last 4 lines, which convert the array of strings into a 2-D array of characters with extra space padding around the edge.  The first and last columns are all space characters, and the first two and last two rows are all space characters, and the interior is populated with data from our string array.  Now we have a nice 2-D array where we can easily do hexagonal-neighbor-indexing from any letter without falling off the edge of the data structure.  We’re ready to rock.  No, wait:

let board = MakeBoard(data)    

Ok, now we’re ready to rock.

It’s time to search.  I want to write a function along the lines of “ok, I have a dictionary of English words encoded in a trie, and I have this 2-D array, and I want to find, say, all the words starting with the letter ‘M’ located at [5,2]” or something.  Think recursively.  At any given point, we’re at some TrieNode inside the trie, and at some [col,row] in the array.  Maybe we have gone off the edge of the letters into the ‘space’ border – no more words here!  But if we are on a letter, we can look it up in the trie.  If we get to a TrieNode where node.IsEndOfWord is true, then great, we’re at the last letter of a word, score one for the good guys.  Regardless, we need to recursively keep searching all the nearby neighbors with our new position in the tree.  And to ensure we don’t use the same letter tile twice in one word, we can “blot it out” by overwriting it with a space when we use it (and then “write it back” as we backtrack out of the recursive search). 

If you’ve written recursive searches before, that may all seem old hat; if not, welcome to the party.  It’s simpler just to show the code before talking about it any more:

let rec Find(col, row, t:TrieNode) = seq {
    assert((col+row)%2 = 1) // we should only be searching LETTER positions
    let c = board.[col,row]
    if c <> ' ' then
        board.[col,row] <- ' '
        match t.[c] with
        | null -> ()
        | node -> 
            if node.IsEndOfWord then
                yield [c]
            for suf in Find(col-1, row-1, node) do yield c::suf
            for suf in Find(col-1, row+1, node) do yield c::suf        
            for suf in Find(col  , row-2, node) do yield c::suf        
            for suf in Find(col  , row+2, node) do yield c::suf        
            for suf in Find(col+1, row-1, node) do yield c::suf
            for suf in Find(col+1, row+1, node) do yield c::suf        
        board.[col,row] <- c }

Just 17 lines of code.  I assert to ensure I’m correctly only looking at the “letter” portion of the checkerboard.  Grab the current character.  If it’s not a space, then it’s a letter we’ll try to use.  Temporarily blot it out with a space so we don’t use it again within “this word”.  (Yeah, that’s right, it’s our pragmatic pal, “mutation”.)  Now look up that letter in the trie.  If null, we’re out of luck, no words with this prefix.  Otherwise we got a trie node.  If this is the end of a word, yield a list containing this character (the last letter of the word).  Recursively search in all 6 neighbor directions for all word suffixes; for each one we find, cons this character onto the front to yield the longer suffix including the character from this recursive step.  That’s all, we’re done with the search on this character, so undo the “blotting out” before we exit, stage left.

That’s it.  With this search function in hand, it’s easy to generate a sorted list of all the words in the whole grid:

let allWordsSorted = 
    seq {    
        for col in 0..BOARDCOLS-1 do
            for row in 0..BOARDROWS-1 do
                if board.[col,row] <> ' ' then
                    yield! Find(col, row, trie) 
    } 
    |> Seq.map (fun w -> new string(w |> Seq.toArray))
    |> Set.ofSeq    // remove duplicates
    |> Seq.toArray 
    |> Array.sortWith (fun a b -> match compare a.Length b.Length with 
                                  | 0 -> compare a b
                                  | x -> x)

We loop over the whole grid and call Find() on every starting letter, resulting in one big sequence of all the words starting from every position.  The “words” yielded from our Find function have type “list<char>”, so we convert these to strings.  Then we remove any duplicate words by making a Set of the whole sequence.  We then convert this to an array, and sort it, first by word length, then by the string itself (alphabetically). 

We can print out the results

for w in allWordsSorted do
    printfn "%s" w
printfn "%d words" allWordsSorted.Length 

and verify we have the same output as Chris.  Except of course that our program is way faster.  (By about a factor of 6 on my box, to create the trie and find all the words.  But who’s counting?  Oh, right, the guys at the bank with the deed to the volcano lair.)

Here’s a data set that’s more fun:

let COLS = 21
let ROWS = 7
let data = [|  // columns
        "O U B N O V S "
        " J A P A L O M"
        "G T E J T S H "
        " U A E O F S A"
        "N O A E L E P "
        " O S O U G N P"
        "A T F G A I I "
        " W U B N O V S"
        "J E P A L O M "
        " G S E J T Y C"
        "U A O O F Y R "
        " N O M E L U T"
        "O S O E G E I "
        " H T F N A I Y"
        "O U B N E V S "
        " J A P A S O M"
        "G T E J T S C "
        " U A E O F Y R"
        "N O A E L U T "
        " O S O U G E I"
        "H T F G A I Y "
    |]

The output for that guy ends with


HAPPINESS
LANGUAGES
AWESOMENESS
732 words

Awesomeness indeed.

The Smackdown

Let’s face it: Chris may have wrote the book on F#, but as far as the F# blogosphere goes… this is my house.  Some may think Chris deserves to be on the receiving end of trash talk like “Yo’ momma’s so fat, she sat on a binary tree and turned it into a linked list in constant time”.  But not me; I’ll stay classy, and let my code do the trash-talking for me.

Chris Smith – Evil genius?  Riiiiight… half right, to be exact.  It’s left as an exercise to the reader to figure out which half.  (BOOM!  “Oh no he didn’t!”)

(Yeah, Chris, I know just how you’re feeling right now.)

The Challenge

Think you can do better?  I’d like to see you try!  Word up, bookworm!

The Source Code

Unlike Chris, who had to link to his code because it was too long to all fit on his blog, my code fits nicely right below.  And you can find links to the TWL06 and IgnoredWords text files here.

let IsLetter(c)   =    c>='A' && c<='Z'

[<AllowNullLiteral>]
type TrieNode() =
    let nextChar = Array.create 26 null
    let mutable isEndOfWord = false
    member this.IsEndOfWord = isEndOfWord
    member this.Item with get(c:char) = nextChar.[int c - int 'A']
                     and private set(c:char) v = nextChar.[int c - int 'A'] <- v
    member this.Add(word) = 
        assert(word |> Seq.forall IsLetter)
        this.Add(word,0)
    member private this.Add(word:string,i) =
        if i = word.Length then
            isEndOfWord <- true
        else 
            match this.[word.[i]] with
            | null -> let newNode = new TrieNode()
                      newNode.Add(word,i+1)
                      this.[word.[i]] <- newNode
            | node -> node.Add(word,i+1)

let words = seq {
    let toIgnore = System.IO.File.ReadAllLines("IgnoredWords.txt") |> Set.ofArray
    for word in System.IO.File.ReadAllLines("TWL06.txt") do
        assert(word |> Seq.forall IsLetter)
        if not (toIgnore.Contains word) && word.Length >= 3 then
            yield word }

let trie = new TrieNode()
for w in words do
    trie.Add(w)

let rec IsWord(s:string, t:TrieNode) =
    if t=null then false
    elif s.Length=0 then t.IsEndOfWord
    else IsWord(s.Substring(1), t.[ s.[0] ])
    
assert(IsWord("ABSTRACTIONISMS", trie))
assert(IsWord("MONSOON", trie))
assert(not(IsWord("QZXWWK", trie)))

/////////////////////////////////////////////////////////

let COLS = 7
let ROWS = 8
let data = [|  // columns
        "  K M E M T O O "
        " E F K I M C A D"
        "  A A E R E A F "
        " T D A I B N D J"
        "  V F F A T E E "
        " O J T R F I R R"
        "  I R D R E E O "
    |]    
    
// surround entire grid with border of spaces (one extra column, two extra rows)
let BOARDCOLS = COLS + 2
let BOARDROWS = 2*ROWS + 4
let MakeBoard(columns:string[]) =
    assert(columns<>null)
    assert(columns.Length = COLS)
    assert(columns |> Seq.forall (fun s -> s.Length = ROWS*2))
    for i in 0..COLS-1 do
        for j in 0..ROWS*2-1 do
            let c = columns.[i].[j]
            if (i+j)%2 = 0 then assert(c=' ' || IsLetter c)
            else                assert(c=' ')
    Array2D.init BOARDCOLS BOARDROWS (fun c r ->
        if c=0 || c=BOARDCOLS-1 || 
           r=0 || r=1 || r=BOARDROWS-2 || r=BOARDROWS-1 then ' '
        else columns.[c-1].[r-2])

let board = MakeBoard(data)    

let rec Find(col, row, t:TrieNode) = seq {
    assert((col+row)%2 = 1) // we should only be searching LETTER positions
    let c = board.[col,row]
    if c <> ' ' then
        board.[col,row] <- ' '
        match t.[c] with
        | null -> ()
        | node -> 
            if node.IsEndOfWord then
                yield [c]
            for suf in Find(col-1, row-1, node) do yield c::suf
            for suf in Find(col-1, row+1, node) do yield c::suf        
            for suf in Find(col  , row-2, node) do yield c::suf        
            for suf in Find(col  , row+2, node) do yield c::suf        
            for suf in Find(col+1, row-1, node) do yield c::suf
            for suf in Find(col+1, row+1, node) do yield c::suf        
        board.[col,row] <- c }

let allWordsSorted = 
    seq {    
        for col in 0..BOARDCOLS-1 do
            for row in 0..BOARDROWS-1 do
                if board.[col,row] <> ' ' then
                    yield! Find(col, row, trie) 
    } 
    |> Seq.map (fun w -> new string(w |> Seq.toArray))
    |> Set.ofSeq    // remove duplicates
    |> Seq.toArray 
    |> Array.sortWith (fun a b -> match compare a.Length b.Length with 
                                  | 0 -> compare a b
                                  | x -> x)

printfn ""
for w in allWordsSorted do
    printfn "%s" w
printfn "%d words" allWordsSorted.Length 

P.S. You may have noted that the tenor of this blog post is markedly different from others I’ve posted.  No, I haven’t lost my mind (at least, not recently).  Rather, Chris and I are friends, and we had discussed different implementation strategies before any of the blogging started, and decided that, rather than a dry, boring comparison of different techniques, it would be fun to do it this way with… “Drama!” (Or as Chris calls it, “drama-lama-ding-dong”.  Seriously.  I’m not making this up.)  Hence this post; hope you enjoyed it.  By the way, regarding “The Challenge”, if you have a simpler/faster/better algorithm for this problem, we’ll be interested to see it!  Feel free to post it on your own blog and call us out!  After all, that’s how we do it in the FP.  Word.

Posted in Uncategorized | Leave a Comment »

An RSS Dashboard in F#, part four (speech agents)

Posted by Brian on February 9, 2010

Previous posts in this series:

Last time I covered exposing RSS feeds as IObservables, and we created the basic infrastructure for getting new information from the web published as an IObservable event stream.  Today we’ll switch gears entirely to cover the next technology piece of the app: synthesizing speech so that titles can be read allowed over the speakers.  We’ll encounter one important design consideration which is neatly handled using asynchronous agents.

Making your computer talk

One of the terrific things about .Net is that it seems like no matter what you want to do, there’s a library for that.  :)  When I was originally designing what I wanted my RSS Dashboard to do, I was apprehensive about the speech part, because I had no idea what it entailed.  I was thrilled and relieved to discover that I could simply add a reference to System.Speech, and then write just two lines of code:

let ss = new System.Speech.Synthesis.SpeechSynthesizer()
ss.Speak("Hello world!")

and get my machine to speak to me.  Hurray!

Of course, it’s not perfect; try things like

ss.Speak("How do I make a GUI in F# using WPF and XAML?")

and discover it sounds like “How do I make a gweh in eff number sign using WPF and ex-ay-em-el”.  So after experience listening to a bunch of question titles from StackOverflow, I authored a function to “wash” the text before I hand to the speech synthesizer.  For example

let SpeechWash (text:string) = 
    text.Replace("GUI", "gooey")
        .Replace("#", " sharp")
        .Replace("XAML", "zah-mull")

cleans up the previous sentence pretty nicely so that

ss.Speak("How do I make a GUI in F# using WPF and XAML?" |> SpeechWash)

is understandable.  We’ll return to this at the end of today’s blog entry.

A blocking operation

Of course if things were just that simple, this would be a really short blog post.  There’s one important consideration for using this API in the context of my dashboard app.  I’m going to be receiving events about new items on the RSS feed, and need to draw updates to the UI and speak some titles aloud.  But the Speak() call is a blocking operation – if I call it from the UI thread, the UI thread will be blocked while it is speaking.  We can demonstrate this in a simple console application:

let ss = new System.Speech.Synthesis.SpeechSynthesizer()
ss.Speak("Until I finish saying this, I will not print what's below")
printfn "Done, press a key to quit"
System.Console.ReadKey() |> ignore

Until the computer finishes speaking, it does not reach the “printfn” line.  So if we call Speak() on the UI thread, we will end up blocking the UI for many seconds, which is a big no-no.  So we need to speak from a background thread, so that we can keep the UI ‘live’ at all times.

A first try at avoiding blocking the UI

There are various ways to do work on background threads, however a number of them will solve one problem by creating another.  For example, Threadpool.QueueUserWorkItem (QUWI) is an API to schedule work on a background thread, and we could use it like this:

let ss = new System.Speech.Synthesis.SpeechSynthesizer()
System.Threading.ThreadPool.QueueUserWorkItem(fun _ -> 
    ss.Speak("Now I can talk and continue on")
    ) |> ignore
printfn "Done, press a key to quit"
System.Console.ReadKey() |> ignore

If you run that code, the computer starts to speak the sentence, but the QUWI call does not block and so the console UI thread continues on and prints the message while the voice is just starting to speak.

Problem solved?  Apparently… until you consider that the dashboard app will be seeing lots of new feed items, and if it uses this strategy to speak each item title as it arrives, we’ll run into the issue that the app is ‘talking over’ itself.  For example, if I do the same code as above but with two QUWI calls to speak multiple sentences:

let ss = new System.Speech.Synthesis.SpeechSynthesizer()
System.Threading.ThreadPool.QueueUserWorkItem(fun _ -> 
    ss.Speak("Now I can talk and continue on")
    ) |> ignore
System.Threading.ThreadPool.QueueUserWorkItem(fun _ -> 
    ss.Speak("But saying multiple things at once is a problem")
    ) |> ignore
printfn "Done, press a key to quit"
System.Console.ReadKey() |> ignore

Now the computer is talking over itself, speaking two different sentences at the same time from two different background threads.

What we really need is a way to have a non-blocking call where we can pass a string to speak, but if there is already something else being spoken, the strings get queued up so they are spoken one by one.  That is, I want an API with a function like EventuallySpeak(someString), where calling the function returns immediately (non-blocking), and the string is either spoken right now (if the voice is not saying anything else), or else queued up to be spoken once the current voice work is finished.

It just so happens this is a perfect job for an asynchronous agent.

Let your agent do the talking

An agent-based architecture models a system as a set of independent autonomous processes (called “agents” or “actors”) that communicate via asynchronous message-passing.  Erlang is perhaps the archetypal programming language and runtime here.  Rather than digress into a long discussion of this style of programming and what its strengths are, I’ll stick to just describing how agents in F# work and what they can do for you.

Here’s an approximate mental model for an F# agent.  Imagine you have some background thread in your app that’s entirely devoted to a particular agent.  What an agent does is this: it runs a continual loop where it waits for a message to arrive in its in-box, and when a message arrives, it carries out some action based on that message.  Then it waits for the next message.  That’s it.  Agents just sit in a loop: wait for a message, do something with it.  The message can be any piece of data, that is, agents are generic in the type of data they accept as messages; a particular agent instance expects a particular data type for a message.

For my app, I need an agent that accepts a string as a message, and speaks the string.  Then my posited EventuallySpeak(someString) function can be implemented by just sending an asynchronous message to that agent.

To create an agent in F#, we use the MailboxProcessor type.  Agent boilerplate code looks like this:

let agent = new MailboxProcessor<T>(fun inbox -> 
    let rec Loop() = async {
        let! msg = inbox.Receive() 
        // do something based on the message
        do! Loop()}        
    Loop())
agent.Start()    

That is, we new up a MailboxProcessor<T>, where T is the type of message this agent can receive.  The MailboxProcessor constructor is passed a lambda that takes the ‘inbox’ (conceptually, the message queue managed by the MailboxProcessor, from which we can Receive() messages; in fact, just a reference to the MailboxProcessor object itself), and returns an arbitrary async computation that defines what the agent will do.  As I just described, a typical agent sits in a loop: “get a message, do something with it” – and so that’s what the code template above does.

For my “speech agent” for the RSS Dashboard app, I need an agent that accept strings and speaks them:

let ss = new System.Speech.Synthesis.SpeechSynthesizer()
let speechAgent = new MailboxProcessor<string>(fun inbox -> 
    let rec Loop() = async {
        let! text = inbox.Receive() 
        ss.Speak(text)
        do! Loop()}        
    Loop())
speechAgent.Start()    

Simple, right?  Now I can define my EventuallySpeak function thusly:

let EventuallySpeak(text) =
    speechAgent.Post(text)

Calling Post to a MailboxProcessor just asynchronously sends the message (fire-and-forget), which the agent will eventually receive and process.

This means I can now write

EventuallySpeak("Now I can talk and continue on")
EventuallySpeak("and saying multiple things is no longer a problem")
printfn "Done, press a key to quit"
System.Console.ReadKey() |> ignore

and achieve success.  I can call the EventuallySpeak function whenever I like, it doesn’t block the thread I’m calling from, and it queues up items to speak so the voice doesn’t talk over itself.

Some technical details

Earlier I described an approximate mental model for an agent: a background thread entirely devoted to spinning in the little loop that defines your agent code.  This makes for a simple mental model, but if that were the actual implementation it would be quite wasteful.  Threads in .Net are expensive (they take up a lot of memory, and you’ll typically use at most tens of threads in an app), and so you don’t want to create a thread for every agent you need, for a couple reasons.  First, most agents spend a lot of time sitting idle: in my RSS Dashboard app, if I only poll the RSS feeds every hour, then my speechAgent will probably spend 59 minutes idle, followed by 1 minute of activity reading new item titles, each hour.  Second, an agent-based architecture may involve thousands of agents (e.g. in an ant colony simulation, you could have an agent to model each and every individual ant).  So the one-thread-per-agent model is a non-starter in many cases.

Fortunately, F# async comes to the rescue here.  A MailboxProcessor runs an async loop in the .Net threadpool.  Async means that when an agent is idle (waiting to receive a message), it is not consuming a thread.  There’s just a callback saved (costing just a handful of bytes of memory), so that when a message arrives that callback will wake up and start running.  And when it does start running, it will grab an arbitrary thread from the threadpool.  Thus many agents can share just a handful of threadpool threads.

The implications are that agents provide immense scalability, but at the same time have the conceptual simplicity of being logically-single-threaded entities.  You can reason about agent code as though it were single-threaded, a constantly running loop which at any point in time has a single ‘program counter’ pointing at a next line of code to run, that may periodically ‘block’ while waiting for external events.  But the implementation is much more efficient.  That’s what makes the F# async programming model so powerful.

Summing up

Here’s all the code for today:

// Based on experience listening to the speech synthesizer trying to speak titles of StackOverflow questions
let SpeechWash (text:string) = 
    text.Replace(".", "dot ")
        .Replace("SO", "stack overflow")
        .Replace("IDE", "i-dee,eee")
        .Replace("GUI", "gooey")
        .Replace(" vs", " versus")  // before lowercasing, avoid e.g. VS2008
        .ToLowerInvariant()
        .Replace("#", " sharp")
        .Replace(" api", " ay pee i")
        .Replace("sql", "see-quill")
        .Replace("msbuild", "MS build")
        .Replace("utf", "u-t-f")
        .Replace("xaml", "zah-mull")
        .Replace("()", "")

let ss = new System.Speech.Synthesis.SpeechSynthesizer()

// A mailbox processor is perfect for the speech task
//  - we want to queue up things to speak without blocking the UI
//  - we want it to be logically-single-threaded (so it doesn't 'talk over itself')
let speechAgent = new MailboxProcessor<string>(fun inbox -> 
    let rec Loop() = async {
        let! text = inbox.Receive() 
        ss.Speak(text |> SpeechWash)
        do! Loop()}        
    Loop())
speechAgent.Start()    

let EventuallySpeak(text) =
    speechAgent.Post(text)

The biggest portion is just dealing with properly pronouncing the myriad acronyms and idiosyncratic words we developers constantly use.  After that, the speech agent is just 10 lines of code that neatly solves the problems of not blocking the UI thread while speaking, as well as not speaking multiple things at once.  An agent is a useful implementation strategy to provide a simple programming model over a singleton fixed resource (like your computer speakers) to ensure that you use it properly.

Next time

For the next entry in the series, I need to get information about what links I’ve visited in my browser.  COM interop and Javascript code ahead!

Posted in Uncategorized | Leave a Comment »

Upcoming release and the “F# 2.0” language

Posted by Brian on February 8, 2010

If you’re very tuned in to the interwebs, you may be aware of hints that the public VS2010 release candidate (RC) will arrive soon.  As usual, the F# team plans to publish a new MSI/ZIP for VS2008 and Mono at the same time as the VS2010 release.  That’s very exciting and I’m looking forward to getting our newest bits out to developers.  (EDIT, Feb 2010: The release is now available – start here.)

What’s even more exciting for me is the ongoing stability of the language and core library since Beta2.  Over the past few years the F# language and core library have been continually improved and refined, thanks in large part to our terrific community, who have provided excellent feedback and bug reports with each release.  Now we’ve finally reached the point where we can say goodbye to the 1.9.x revision numbers and update the major version number of the F# language.  With the VS2010 RC and matching CTP soon arriving, there will finally be an F# compiler that announces itself as the

Microsoft (R) F# 2.0 Compiler

in the banner output of fsc.exe.  This release will be source-code compatible with the prior release (1.9.7.8). The F# compilers in the VS2008 and VS2010 installations will both be for the F# 2.0 language, with source and binary-compatibility. The only substantive language or library changes from Beta2 to RC have been final removals of deprecated functionality and bug fixes to a handful of corner cases that affected binary compatibility.

The upside of all this for me is that I no longer need to worry about confusing folks with ‘old code’ from my blog.  I’ve had a number of questions along the lines of “hey, I found this code on your blog from a year ago, but it calls ‘Enum.to_int’ and that function doesn’t seem to exist any more…”  In honor of the stability of the F# 2.0 language, I’ve gone and updated all my old blog entries to F# 2.0 code.  Of course the F# team will also be updating sites like the F# Samples concurrently with the new release.  We’ll also be contacting various folks in the community who have published popular F# content to ask them to consider ensuring that their F# code is up to date.  There is a ton of great sample code in the F# blogosphere, and I often hear “yeah, I found this great sample to do XYZ… I had to change ‘Array.fold_left’ to ‘Array.fold’ to make it compile, but after that it just works and is exactly what I need!”  I’d love to remove those final speedbumps so that everyone has a smooth time trying out F# sample code, and can straightaway get on with enjoying programming with F# :)

So if you’re a reader of my blog, and find any code on my blog that does not compile with the latest F#, please let me know, and I’ll fix it.  And if you have published your own F# code/blog, please grab the VS2010 RC or February 2010 F# CTP after they arrive, and consider any final updates you may need to your most popular code samples.

Thanks again to everyone who has helped contribute to F# to get to where we are today!

Posted in Uncategorized | 2 Comments »

An RSS Dashboard in F#, part three (RSS feeds)

Posted by Brian on February 6, 2010

Previous posts in this series:

Last time I covered IObservables and we created a useful ObservableSource class.  Today I’ll cover the next technology piece of the app: reading RSS feeds.  I’ll discuss the design considerations regarding how to poll feed for updates and publish feed items as IObservables, and walk through one implementation.

RSS feeds

Many web sites with continually updating content will post RSS feeds (or Atom feeds).  These syndication feeds are just XML documents that are easy to read/parse and contain a list of recent items.  The .Net SyndicationFeed class makes it trivial to load a feed and access its data through a convenient object model.  In terms of the noteworthy data I need for the dashboard application, each SyndicationItem in the feed may contain a Title (e.g. the question title of a StackOverflow question), an Id (that uniquely identifies this question), a LastUpdatedTime (which says when the data of this item was most recently modified), and some Links (e.g. to the Uri of the question itself). This provides the key data to be displayed in the UI, as well as what items are new (never-before seen Ids) or updated (fresher LastUpdatedTime).

Given the Uri (web address) of a feed, it’s trivial to get a feed object:

let feed = SyndicationFeed.Load(XmlReader.Create(uri))

so the only challenge comes from how to present this information as an IObservable.

Some design considerations for presenting feeds as IObservables

When designing a reusable component to present feeds as IObservables, a number of considerations come into play.  For starters, syndication feeds are a pull technology, whereas IObservables are a push technology, so polling (pumping) must be used.  Various feed readers may poll the feed daily or hourly; a general-purpose component should make it easy to configure the frequency that the feed is rechecked.

Polling creates a bursty event channel.  Suppose for example we are polling hourly.  If there are many new items in the past hour, this means the IObservable will go for an hour with no activity, followed by a flurry of OnNext calls, followed by an hour of silence, then another flurry, … the events will be very bursty.  When you start receiving these events, it can be useful to know when the burst will end (perhaps you want to collect all the data and then update the UI once, rather than have the UI flicker as it updates each item individually).  Alternatively, some clients may prefer to have the items “batched” and just get one (relatively predictable) event each polling cycle that contains a list of all the items.

Also, some clients may only be interested in finding about new items (e.g. new questions posted to a specific StackOverflow tag), whereas other client may be interested in updates to existing items as well (e.g. a new answer posted to an existing question).

Finally, since the feeds are probably being read over the internet, there are issues of reliability.  Networks and web sites periodically go down.  Some clients may want notification that the feed could not be read (e.g. to present that information or diagnostics in a UI), whereas others may be happy to just ignore a failure to poll (treating it as though there were no new data this polling cycle) and just retry again after the next polling time period passes.

An implementation of a feed source

In light of the design considerations of the previous section, I elected to create two components.  First there is a FeedSource class that provides IObservables for various FeedEvents in a very granular and flexible fashion.  And then there is a transformer that batches up the granular/verbose events from that source into an IObservable that’s more tailored to my dashboard application.

(The design space here is large, and I don’t know that this design is optimal.  But it does create a nice opportunity to demonstrate using a ‘transform’ function that turns one IObservable into another, as I’ll show shortly.)

To start things off, there are three kinds of events that I want to surface that can happen over time.  I define a discriminated union:

type FeedEvent =
    | Item of SyndicationItem
    | EndPoll
    | RetryError of exn

“Item” is an event that carries data about a new or updated item in the feed.  “EndPoll” is simply a notification that this polling cycle has ended, and so there will be no more items coming until the next time it’s time to download the feed again.  The “RetryError” can be sent when there was an error downloading or parsing the feed; it carries data about the exception that happened (recall that “exn” is just an F# type alias for System.Exception).  This data type enables me to create an IObservable<FeedEvent> that deals with a number of the considerations of the previous subsection.

The next thing to do is to implement the actual machinery to poll the feed and publish these events.  Since some clients may be interested in only new items whereas others may also be interested in updates, I decided to expose two different IObservables on the FeedSource class.  The key data that must be maintained here is which feed items have already been seen and when they were last updated.  For this I use a simple Map<string,DateTimeOffset>, where the (string) key represents the Id of an item, and the (DateTimeOffset) value represents the LastUpdated time.  Thus subsequent reads of the feed can look through the dictionary to determine if an item is new (the key is not in the Map), or if an existing item has been updated (the key is already in the Map, but the time value is newer).

So here’s the class broken up into a few chunks, with explanation of each portion.  To start:

type FeedSource(uri : string, 
                pollingFrequency : TimeSpan, 
                itemState : IDictionary<string,DateTimeOffset>  // item.Id, item.LastUpdatedTime
                ) =
    let mutable seenItems = 
        let mutable m = Map.empty
        for KeyValue(k,v) in itemState do
            m <- Map.add k v m
        m
    let allUpdates = new ObservableSource<FeedEvent>()
    let justNew = new ObservableSource<FeedEvent>()

The FeedSource class constructor takes in three bits of information – the Uri of the RSS feed, how often we want to poll, and an initial state for the Map.  (This may be over-engineered; I can imagine a client that saves out the state of already-seen items to disk, so the next time the app starts it can read them back in and then pass them into the third parameter of this constructor, but my app doesn’t do that.)  “seenItems” is a Map of item Ids to LastUpdatedTimes, and it’s initialized with the data passed into the constructor.  There are two ObservableSource objects (instances of the class from last time), “allUpdates” for information about every change and “justNew” for only new items that appear in the feed (that is, items whose Ids we have not previously encountered).

Next here’s a function to run each polling cycle:

    let Update() =
        try
            let feed = SyndicationFeed.Load(XmlReader.Create(uri))
            for item in feed.Items do
                match Map.tryFind item.Id seenItems with
                | Some lup -> 
                    if item.LastUpdatedTime > lup then
                        seenItems <- seenItems.Add(item.Id, item.LastUpdatedTime)
                        allUpdates.Next(Item item)
                | None ->
                    seenItems <- seenItems.Add(item.Id, item.LastUpdatedTime)
                    allUpdates.Next(Item item)
                    justNew.Next(Item item)
            allUpdates.Next(EndPoll)
            justNew.Next(EndPoll)
        with e ->
            allUpdates.Next(RetryError e)
            justNew.Next(RetryError e)

It’s pretty straightforward.  We download the feed.  We iterate over all the items.  If the item already exists in the “seenItems” Map, but its LastUpdatedTime is newer, we publish an Item event with the item to “allUpdates”.  (If the time is not newer, then we can drop this data on the floor, there’s nothing more to do.)  Otherwise if it’s not in the Map, the item is totally new, and we publish it to both “allUpdates” and “justNew”.  Once we’ve processed all the items, we publish an EndPoll event to both sources.  If there was an exception during the processing, we publish a RetryError event with the exception.

Next we need to be able to run the polling cycle in a loop, sleeping for the appropriate TimeSpan in between polls.  I’ve chosen to expose an explicit Start() method so that client can subscribe before the events begin arriving.  (A Dispose() method, coming shortly, is the “stop”.)  We use an async loop to avoid blocking a thread while we sleep.  Async.Start will start this loop in the .Net threadpool, where it will run continually.

    let mutable started = false
    let mutable disposed = false
    // Start poll the feed and sending observations to subscribers.  
    // (The polling and OnXXX calls run in the thread pool.)
    // This method is distinct from the constructor so that clients can subscribe before calling Start, and thus
    // get the 'first' batch of data from the feed.
    member this.Start() = 
        if started then
            raise <| new InvalidOperationException("cannot start twice")
        started <- true
        let rec Loop() =
            async {
                Update()
                do! Async.Sleep(int pollingFrequency.TotalMilliseconds)
                if not disposed then
                    do! Loop()
            }
        Loop() |> Async.Start 

Finally, we expose the two IObservable properties, as well as the rest of the state of the class, and finally make it IDisposable to have a way to stop the polling.

    member this.AllUpdates = allUpdates.AsObservable 
    member this.JustNewItems = justNew.AsObservable
    member this.ItemState = Map.toSeq seenItems |> dict  // return a read-only snapshot
    member this.IsStarted = started
    member this.IsDisposed = disposed
    member this.Uri = uri
    member this.PollingFrequency = pollingFrequency
    interface IDisposable with
        member this.Dispose() = 
            if disposed then
                raise <| new InvalidOperationException("cannot dispose twice")
            disposed <- true
            allUpdates.Completed()
            justNew.Completed()

That’s it.  There’s little to this class other than running the Update() function in an async loop and exposing all the state/properties.

Here’s a short sample that demonstrates the FeedSource class being used.  This little program polls the StackOverflow feed of C# questions every minute:

let soCSharpFeed = "http://stackoverflow.com/feeds/tag?tagnames=c%23&sort=newest"

let Main() =
    use feedSrc = new FeedSource(soCSharpFeed, System.TimeSpan.FromMinutes(1.0), dict[])
    use au = feedSrc.AllUpdates.Subscribe(fun event ->
        match event with
        | Item i -> printfn "Update to '%s'" i.Title.Text 
        | _ -> ())
    use jn = feedSrc.JustNewItems.Subscribe(fun event ->
        match event with
        | Item i -> printfn "New item '%s'" i.Title.Text 
        | _ -> ())
    feedSrc.Start()
    System.Console.ReadKey() |> ignore

Main()    

When run it will immediately print all the recent messages as both JustNewItems and AllUpdates.  If you leave it running for a couple minutes during a busy period on StackOverflow, you’ll see some new items or updates-to-already-seen-items appear.  This code snippet demonstrates the way a typical client would use the API: new up a FeedSource, subscribe to the observations it cares about, ‘start’ the source, and then dispose everything when it’s all done.

Implementing batching

As mentioned previously, the FeedSource class provides fine-grained observations about all the information in an RSS feed.  Some clients may want something simpler – for instance, receiving at most one event each polling cycle that describes the changes since the last time.  I’ve built a batch-transform function that serves this purpose.  It takes as input an IObservable<FeedEvent> (thus listening for every individual event), and returns a new IObservable<seq<SyndicationItem>> that fires at most once per polling cycle with the information about all the item events that were seen.  Here’s the code:

// Given that most feed sources will poll, and thus be quiet for a period of time, followed by a burst
// of OnNext() activity, followed by another quiet period... this method "batches" together all the items
// between polling events (or failures) so that just a single OnNext() with a collection of items happens
// with each polling cycle.
// Note that this effectively swallows error diagnostics (RetryError).
let Batch (src : IObservable<FeedEvent>) : IObservable<seq<SyndicationItem>> =
    let curList = ref []
    let result = new ObservableSource<seq<SyndicationItem>>()
    let SendBatch() =
        if not (!curList).IsEmpty then
            result.Next(!curList)
            curList := []
    let disp = ref (null : IDisposable) 
    disp := src.Subscribe({new IObserver<_> with
        member this.OnNext(x) =
            match x with
            | Item x -> 
                curList := x :: !curList 
            | _ -> 
                SendBatch()
        member this.OnCompleted() = SendBatch(); result.Completed(); (!disp).Dispose()
        member this.OnError(e) = SendBatch(); result.Error(e); (!disp).Dispose() })
    result.AsObservable 

We store a mutable list in a reference cell (curList) that is used to accumulate items as we encounter them; each time we get an OnNext with an Item event, we add that item to the list.  (I don’t use ‘ref’ very often; if you need a refresher, see this blog entry.)  Once the polling cycle ends, the original source will send an EndPoll (or possibly a RetryError) message, which will go to the second branch of the ‘match’, which calls SendBatch().  SendBatch() looks to see if we’ve accumulated any new items in the list; if so, we send them all in a single OnNext() call and empty the list.  If there are no new items, we do nothing (don’t publish any new observations to the resulting IObservable event stream).  This will just happen over and over again until we get an OnCompleted/OnError from the original source, at which point we send any as-yet-unsent items as a final batch, and then forward the completed/error event and dispose ourselves.

Once again, let’s see what some client code may look like that uses the Batch() function.

open System.ServiceModel.Syndication 
let soCSharpFeed = "http://stackoverflow.com/feeds/tag?tagnames=c%23&sort=newest"

let Main() =
    use feedSrc = new FeedSource(soCSharpFeed, System.TimeSpan.FromMinutes(1.0), dict[])
    use au = Batch(feedSrc.AllUpdates).Subscribe(fun updates ->
        printfn "Saw the following updates..." 
        for item:SyndicationItem in updates do
            printfn " - %s" item.Title.Text)
    use jn = Batch(feedSrc.JustNewItems).Subscribe(fun news ->
        printfn "Saw the following new items..." 
        for item:SyndicationItem in news do
            printfn " - %s" item.Title.Text)
    feedSrc.Start()
    System.Console.ReadKey() |> ignore

Main()    

This is very similar to the last example, but now we call Batch() on the IObservable before subscribing.  Thus now we get a single event that has data about all the items this polling cycle, which we can iterate over inside the handler.

Summing up so far

In the previous blog entry and this one, I’ve covered a bit of territory.  I’ve introduced the IObservable interface, which is conceptually an event stream that periodically fires OnNext() messages until finally potentially ending with an OnCompleted() or OnError() call.  I’ve implemented an ObservableSource class which provides a straightforward API for creating an IObservable that clients can subscribe to, and discussed the importance of threading contracts like ‘serializable’ (where, even if events come from arbitrary background threads, they never overlap).  I’ve built a polling RSS FeedSource class, which allows you to specify a feed Uri and a polling frequency, that publishes a couple granular IObservables: one with all updates, and another with only not-previously-seen items.  And I’ve implemented a transform function that converts a bursty granular FeedSource IObservable into a new IObservable that batches everything up to just send one event per polling cycle.

With these pieces in hand, we’re on our way towards implementing the dashboard app.

Next time

For the next entry in the series, we’ll look at speech synthesis.  Your computer will be speaking aloud to you in no time!  The .Net APIs here make this really, really easy, as you’ll soon see.

Posted in Uncategorized | Leave a Comment »