# Archive for May, 2008

## Catamorphisms, part five

Posted by Brian on May 31, 2008

Today’s blog entry highlights previous errata and demonstrates a new improvement/generalization.

I made a major error in my previous post: I said that

In real-world applications with large immutable data structures, it is imperative to do this right and "only recreate what you need to".  Otherwise, a single change to a huge tree will wind up using O(N) space, when in fact you only needed to use O(log N) space.

but then went on to show code that is still always O(N).  This was unintentional, and I’m glad that a friend of mine called me on it.  It makes the perfect segue into today’s blog entry.

### The trouble with Fold and XFold

Fold and XFold, as we have seen in previous blog entries in this series, are useful functions.  However these functions suffer an important limitation that I haven’t yet discussed.  The limitation is that they always traverse the entire structure.  Traversing the whole structure is often what you want to do – nearly all the example functions I’ve written in terms of folds so far on this blog need to visit the whole structure.  For example, if you want to sum all the nodes in a tree, or calculate a tree’s height, you have to visit every node.  But sometimes you don’t want to visit every node.  For example, when searching for a node in a binary search tree, the "search" property of the tree directs you down a certain path, so that you only need to visit the nodes that connect the root of the tree to the node you are looking for.  If the tree is balanced, then the search will only take O(log N) time.

Doing a binary search on a tree (or more generally, any kind of "selective" walk over an arbitrary recursively-defined data structure) cannot be done efficiently using Fold or XFold, because these functions always walk the entire structure (which takes O(N) time, as well as O(N) space due to the lambdas allocated at each node).  When we need to do "selective traversals", we need something different.  But what?

### KFold to the rescue

That "something different" is an entity I’ll call KFold.  Consider once again the binary tree structure we used last time:

type Tree<‘a> =
| Node of (*data*)‘a * (*left*)Tree<‘a> * (*right*)Tree<‘a>
| Leaf

//     4
//  2     6
// 1 3   5 7
let tree7 = Node(4, Node(2, Node(1, Leaf, Leaf), Node(3, Leaf, Leaf))
Node(6, Node(5, Leaf, Leaf), Node(7, Leaf, Leaf)))

We can define a KFold function over the tree like so:

let KFoldTree nodeF leafV tree =
let rec Loop t =
match t with
| Node(x,left,right) -> nodeF x (fun k -> k (Loop left)) (fun k -> k (Loop right)) t
| Leaf -> leafV t
Loop tree

A KFold is a fold where the recursive portions (e.g. the second and third parameters to "nodeF") use explicit continuations.  Continuation variables are sometimes conventionally named "k", and so I have adopted that convention here in the code body, and used the "K" prefix to differentiate this fold from the other folds we’ve already defined.

The use of continuations serves two purposes.  First, as we have seen before, continuations are used to help ensure that the function stays tail-recursive, so that regardless of the size and shape of the data structure, we won’t blow the call stack.  Second, and more importantly to today’s blog entry, we have shifted the continuation aspect back to the client of the KFold.  This puts the client in control of when and if we make a recursive call.

Consider the case where we want to find the ‘5’ node in a binary search tree and change its value.  We only want to recurse left or right (and not both ways) down the tree as we try to find the desired value.  Thus I can define:

// Change5to0bst : Tree<int> -> Tree<int>
let Change5to0bst tree =
KFoldTree (fun x kl kr t ->
let (Node(_,oldL,oldR)) = t
if x < 5 then
kr (fun newR ->
Node (x, oldL, newR))
elif x > 5 then
kl (fun newL ->
Node (x, newL, oldR))
else
Node(0,oldL,oldR)
) (fun t -> t) tree

The key bits are "kl" and "kr".  These are continuations which will produce the results of the recursive calls on the left and right subtrees, respectively.  The person calling KFoldTree can choose if and when to invoke these continuations.  So, for example, we only invoke "kl" if we need to go down the left branch.  In the code above, we do the usual binary-search-tree logic: if the value of the current node is too small, we recurse right, else if it’s too big, we recurse left, else if we found it, we modify the value.  I’m using the words "change" and "modify", but recall that the Tree structure is immutable, and we’re actually just returning a new tree with the 5 replaced by a 0.  (Yes, this make the result no longer a search tree; oh well, "Change5to0" is just contrived example function anyway.)  As in the previous blog entry, we only create new nodes when necessary, that is, we re-use as much of the original structure as possible.  (Compared to the XFold code, the "reuse" here is much more explicit, as we name the "old" subtrees which we explicitly connect into the new Node structures.)

By defining this function using a KFold, we get the desired performance characteristic: running the function on a balanced binary search tree will only consume O(log N) time and space.

### The KFold boilerplate – catamorphisms#

It turns out that XFoldTree can be defined in terms of KFoldTree:

// XFoldTree : (‘a -> ‘r -> ‘r -> Tree<‘a> -> ‘r) -> (Tree<‘a> -> ‘r) -> Tree<‘a> -> ‘r
let XFoldTree nodeF leafV tree =
KFoldTree (fun x l r -> l (fun lacc -> r (fun racc -> nodeF x lacc racc))) leafV tree

That is, XFoldTree is just KFoldTree where we always call the recursive continuations.  KFold is more general than XFold, so XFold can be defined in terms of it.

Furthermore, KFold is entirely boilerplate – given a discriminated union type definition, the definition of a KFold over that type is automatic.

### Revisiting an old problem

Back in part three, I made another minor error.  The Eval function I defined was not tail recursive, in that if you had a large expression whose "if" condition was another "if", whose condition was another "if", … and so on, then you’d use a stack frame for each "if".  Though it’s unlikely that anyone would ever run that version of "Eval" on a program containing 10000 nested "if"s, I would still sleep a little better at night knowing that I wrote the function tail-recursively, so that arbitrarily large data will not blow the stack.  So let’s rewrite it using a KFold.  This will also provide an opportunity to show what a KFold looks like on a differently-shaped type.

Here was the original data type from part three:

// types capable of representing a small integer expression language
type Op =
| Plus
| Minus
type Expr =
| Literal of int
| BinaryOp of Expr * Op * Expr     // left, op, right
| IfThenElse of Expr * Expr * Expr // cond, then, else; 0=false in cond
| Print of Expr                    // prints, then returns that value

The KFoldExpr function definition follows directly from the structure of the type:

let KFoldExpr litF binF ifF printF expr =
let rec Loop ex =
match ex with
| Literal(x) -> litF x ex
| BinaryOp(l,op,r) -> binF (fun k -> k (Loop l)) op (fun k -> k (Loop r)) ex
| IfThenElse(c,t,e) -> ifF (fun k -> k (Loop c)) (fun k -> k (Loop t)) (fun k -> k (Loop e)) ex
| Print(e) -> printF (fun k -> k (Loop e)) ex
Loop expr

Note that each recursive portion of the type becomes a "fun k -> …" bit.  With the KFold defined, we can write Eval thusly:

// Eval : Expr -> int
let Eval expr =
KFoldExpr (fun x _ -> x)
(fun kl op kr _ -> match op with
| Plus -> kl (fun l -> kr (fun r -> l+r))
| Minus -> kl (fun l -> kr (fun r -> l-r)))
(fun kc kt ke _ -> kc (fun c -> if c <> 0 then
kt (fun t -> t)
else
ke (fun e -> e)))
(fun ke _ -> ke (fun e -> printf "<%d>" e
e))
expr

The problem with the Eval function previously defined (back in part three) was the bit that said

... (fun c t e () -> if c() <> 0 then t() else e()) ...

In that code, "c()" could cause a recursive call, but it is not a tail call.  Today’s Eval function (defined as a KFold) has every function application as a tail call, so we are safe.

### The source code

Here’s the full source code from today.

open System

// handy operator
let (===) = fun x y -> Object.ReferenceEquals(x,y)

type Tree<‘a> =
| Node of (*data*)‘a * (*left*)Tree<‘a> * (*right*)Tree<‘a>
| Leaf

//     4
//  2     6
// 1 3   5 7
let tree7 = Node(4, Node(2, Node(1, Leaf, Leaf), Node(3, Leaf, Leaf))
Node(6, Node(5, Leaf, Leaf), Node(7, Leaf, Leaf)))

let KFoldTree nodeF leafV tree =
let rec Loop t =
match t with
| Node(x,left,right) -> nodeF x (fun k -> k (Loop left)) (fun k -> k (Loop right)) t
| Leaf -> leafV t
Loop tree

// Change5to0bst : Tree<int> -> Tree<int>
let Change5to0bst tree =
KFoldTree (fun x kl kr t ->
let (Node(_,oldL,oldR)) = t
if x < 5 then
kr (fun newR ->
Node (x, oldL, newR))
elif x > 5 then
kl (fun newL ->
Node (x, newL, oldR))
else
Node(0,oldL,oldR)
) (fun t -> t) tree
Change5to0bst tree7 // does ‘the right thing’, e.g. O(log N) space and time for a balanced search tree

// XFoldTree : (‘a -> ‘r -> ‘r -> Tree<‘a> -> ‘r) -> (Tree<‘a> -> ‘r) -> Tree<‘a> -> ‘r
let XFoldTree nodeF leafV tree =
KFoldTree (fun x l r -> l (fun lacc -> r (fun racc -> nodeF x lacc racc))) leafV tree

// Other useful Tree boilerplate from previous blogs
let XNode (x,l,r) (Node(xo,lo,ro) as orig) =
if xo = x && lo === l && ro === r then
orig
else
Node(x,l,r)
let XLeaf (Leaf as orig) =
orig
let FoldTree nodeF leafV tree =
XFoldTree (fun x l r _ -> nodeF x l r) (fun _ -> leafV) tree

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

// types capable of representing a small integer expression language
type Op =
| Plus
| Minus
type Expr =
| Literal of int
| BinaryOp of Expr * Op * Expr     // left, op, right
| IfThenElse of Expr * Expr * Expr // cond, then, else; 0=false in cond
| Print of Expr                    // prints, then returns that value

let exprs = [Literal(42)
BinaryOp(Literal(1), Plus, Literal(1))
IfThenElse(Literal(1), Print(Literal(42)), Print(Literal(0)))
]

let KFoldExpr litF binF ifF printF expr =
let rec Loop ex =
match ex with
| Literal(x) -> litF x ex
| BinaryOp(l,op,r) -> binF (fun k -> k (Loop l)) op (fun k -> k (Loop r)) ex
| IfThenElse(c,t,e) -> ifF (fun k -> k (Loop c)) (fun k -> k (Loop t)) (fun k -> k (Loop e)) ex
| Print(e) -> printF (fun k -> k (Loop e)) ex
Loop expr

// Eval : Expr -> int
let Eval expr =
KFoldExpr (fun x _ -> x)
(fun kl op kr _ -> match op with
| Plus -> kl (fun l -> kr (fun r -> l+r))
| Minus -> kl (fun l -> kr (fun r -> l-r)))
(fun kc kt ke _ -> kc (fun c -> if c <> 0 then
kt (fun t -> t)
else
ke (fun e -> e)))
(fun ke _ -> ke (fun e -> printf "<%d>" e
e))
expr

exprs |> List.iter (fun expr -> printfn "%d" (Eval expr))
// 42
// 2
// <42>42

## Catamorphisms, part four

Posted by Brian on May 24, 2008

I found something new to say about catamorphisms, so here we are again!  Back in part two, we created a "fold" function for a binary tree type, which made it easy to define most any function on the tree (e.g. Sum, InOrder, Height).  Today we’ll show a limitation of the "fold" function I previously showed, and demonstrate an easy way to overcome that limitation.  There will also be code to "diff" trees and render them prettily, using WPF.  Fun stuff ahead!

### Quick recap of Tree and FoldTree

Recall that we previously defined a data type for binary trees like this:

type Tree<‘a> =
| Node of (*data*)‘a * (*left*)Tree<‘a> * (*right*)Tree<‘a>
| Leaf

let tree7 = Node(4, Node(2, Node(1, Leaf, Leaf), Node(3, Leaf, Leaf))
Node(6, Node(5, Leaf, Leaf), Node(7, Leaf, Leaf)))

Each tree object is either an interior node (with data, a left child, and a right child) or a leaf.  In the example above, "tree7" is a tree that I might draw like this:

We also defined a "fold" function for this tree data type:

// FoldTree : (‘a -> ‘r -> ‘r -> ‘r) -> ‘r -> Tree<‘a> -> ‘r
let FoldTree nodeF leafV tree =
let rec Loop t cont =
match t with
| Node(x,left,right) -> Loop left  (fun lacc ->
Loop right (fun racc ->
cont (nodeF x lacc racc)))
| Leaf -> cont leafV
Loop tree (fun x -> x)

FoldTree is extremely general; we previously used it to easily define various tree functions (Sum, InOrder, and Height).  However, FoldTree is not quite general enough to solve one more tree problem…

### A new tree problem

Suppose I want to walk a given tree and replace every occurrence of a given number with a different number.  For example, here’s a function which walks a tree of integers, and returns a new tree with every 9 replaced by a 0:

// Change9to0 : Tree<int> -> Tree<int>
let Change9to0 tree =
FoldTree (fun x l r -> Node((if x=9 then 0 else x), l, r)) Leaf tree

As usual, we wrote this function as a simple application of FoldTree.  It works as advertised.

However, you might notice a peculiarity.  Suppose we apply "Change9to0" to our "tree7" tree.  The "tree7" tree contains no 9s.  As a result, we might expect to get the "same" tree back.  In fact, we get back a tree that contains all the same data, but the tree which is returned is an entirely new tree.  That is, Change9to0 allocated 7 new "Node" objects, filling them with the same data as the original Nodes in "tree7".  For a small tree, this is not a big deal, but if this were a huge data structure, it would be a real waste to recreate the entire structure if we’re not going to change anything!

Graphically, I might draw the returned tree like this:

where red nodes are nodes that are different objects (in terms of reference-equality) from those nodes in the original tree.  All the nodes are red, because Change9to0 allocated an entirely new set of nodes.

What we want is a function which will be smart, and only allocate new data structures when necessary.  Indeed, one of the main advantages of immutable data structures is the ability to "share" portions of structure.  Consider a slightly different function, that changes each 5 to a 0.  Ideally when we apply such a function to the original "tree7", we want the result to look like this:

Look carefully at the colors – do you see what’s happened here?  We changed the 5 to a 0, so of course that Node much now be a new object.  Its parent node (the node containing the 6) must now also be a new object, since it has a different left-child reference than the corresponding node in the original tree.  Similar, 6’s parent (the node with 4) is new because if now has a different right-child.  However, the rest of the nodes (the 7, and the entire 1-2-3 subtree) remain the same.  That is, these nodes are shared with the original data structure; for example, the new "4 node" points to the original "2 node" because there were no changes to that portion of the tree – everything from the 2 on down is unchanged.

In real-world applications with large immutable data structures, it is imperative to do this right and "only recreate what you need to".  Otherwise, a single change to a huge tree will wind up using O(N) space, when in fact you only needed to use O(log N) space.  A series of small changes would cause a plethora of extra allocations, creating tons of garbage, slowing down your program (due to the garbage collector) and spiking the memory usage.  So in the real world, you must do this right.

But it’s impossible to do this right with the FoldTree function!  (Try it!)  Does this mean FoldTree is worthless for tree-transform tasks?  We’ll find out in a moment.

### Doing it right

Let’s do a small example "by hand", both to make sure we understand what’s going on, and to help guide us towards a more general solution.  What we want is a function which has the same general behavior as this function:

let Change5to0 tree =
FoldTree (fun x l r -> Node((if x=5 then 0 else x), l, r)) Leaf tree

except that instead of yielding a tree like this one (with all new/red nodes)

when applied to "tree7", we want our enhanced function to result in

instead.  We can do this via careful checks for reference-equality as we build up the new tree.  Let’s first define a handy operator for checking reference-equality:

let (===) = fun x y -> Object.ReferenceEquals(x,y)

That is, "x===y" returns true if x and y are the same object in memory.  Now we can define:

let rec MyChange5to0 tree =
match tree with
| Leaf -> tree
| Node(x,l,r) ->
let newL = MyChange5to0 l
let newR = MyChange5to0 r
if x<>5 && newL === l && newR === r then
tree
else
Node((if x = 5 then 0 else x), newL, newR)

This preserves as much structure of the original tree as possible.  In the case of a Leaf, we can always return the same object.  In the case of an interior Node, there’s a bit of logic.  First we need to recurse on both children.  If we are not changing the data value in the current node (it’s not 5), and both recursive calls returned the original children (the same objects in memory as the originals), then this whole call can return the original tree object as-is.  Otherwise, we need to allocate a new Node, filled in with the right data.

The good news is, this works.  The bad news is "MyChange5to0" is 9 lines of code (subtle code, non-tail-recursive code), whereas "Change5to0" was just a single line of code.  In an ideal world, the function would be as simple to write as Change5to0, but also have the right reference-equality-preserving behavior.  Can we have our cake and eat it too?

### XFold to the rescue

We can!  Here again is the original function based on "FoldTree" that has bad behavior:

let Change5to0 tree =
FoldTree (fun x l r -> Node((if x=5 then 0 else x), l, r)) Leaf tree

It turns out we can write a slightly different function based on "XFoldTree" that has the desired behavior:

let XChange5to0 tree =
XFoldTree (fun x l r -> XNode((if x=5 then 0 else x), l, r)) XLeaf tree

The only differences are that "FoldTree", "Node", and "Leaf" have been replaced by "XFoldTree", "XNode", and "XLeaf".  What are these crazy X-entities?

The definition of XFoldTree is just like the definition of FoldTree, except that its "nodeF" and "leafV" are modified to take an extra tree parameter (note the extra ‘t’ at the call sites):

// XFoldTree : (‘a -> ‘r -> ‘r -> Tree<‘a> -> ‘r) -> (Tree<‘a> -> ‘r) -> Tree<‘a> -> ‘r
let XFoldTree nodeF leafV tree =
let rec Loop t cont =
match t with
| Node(x,left,right) -> Loop left  (fun lacc ->
Loop right (fun racc ->
cont (nodeF x lacc racc t))) // note ‘t’
| Leaf -> cont (leafV t) // note ‘t’
Loop tree (fun x -> x)

Passing in the original tree object to "nodeF" and "leafV" makes it possible to inspect the original object reference, in case you want to do reference-equality tests.

(Aside: It turns out that our original FoldTree function (which still has many utilities) can easily be defined in terms of XFoldTree:

let FoldTree nodeF leafV tree =
XFoldTree (fun x l r _ -> nodeF x l r) (fun _ -> leafV) tree

That is, FoldTree is just XFoldTree where we discard the extra tree parameter (the "_" is the original-tree parameter we are ignoring).  XFold is more general than Fold; so Fold can be defined in terms of it.)

Just as the XFoldTree arguments "take an extra tree parameter", the X-constructors (XNode and XLeaf) also take an extra tree parameter (but otherwise work similarly to the case labels of the discriminated union data type).  These X-constructors do the equality-comparsion, so as to not create new objects whenever we have an existing object nearby that we expect might be exactly the same:

let XNode (x,l,r) (Node(xo,lo,ro) as orig) =
if xo = x && lo === l && ro === r then
orig
else
Node(x,l,r)
let XLeaf (Leaf as orig) =
orig

It may help you understand these functions by thinking of them as "constructors that take a hint".  That is, for example, the expression "XNode (x,l,r) hint" means "I want to create ‘Node(x,l,r)’, but it just so happens that I have another Node named ‘hint’ right here, and it’s possible that ‘hint’ contains exactly the same data as the Node I am about to construct.  So please check if these are the same.  If they are, let’s not allocate anything new, and instead just reuse the hint.  Otherwise, give me a new Node with the data I want."

### A closer look

Look again now at the difference between

let Change5to0 tree =
FoldTree (fun x l r -> Node((if x=5 then 0 else x), l, r)) Leaf tree

and

let XChange5to0 tree =
XFoldTree (fun x l r -> XNode((if x=5 then 0 else x), l, r)) XLeaf tree

As is often the case, currying is hiding the plumbing, so as to make the code look simple on its face.  Currying is great, but it may help you understand how XFoldTree interacts with the X-constructors if I rewrite the code like this:

let UncurriedXChange5to0 tree =
XFoldTree (fun x l r hint -> XNode ((if x=5 then 0 else x), l, r) hint)
(fun hint -> XLeaf hint) tree

This is exactly the same code, except that I "uncurried" the "hint" argument.  Now things are more clear.  XFoldTree’s parameters each take an extra Tree parameter, which I’ve called "hint".  This "hint" is passed as the extra parameter to XNode and XLeaf.  Currying handily hides this extra plumbing, so that we preserve the structure of the original solution.  To change from Change5to0 to XChange5to0, all we have to do is swap out the non-X versions of FoldTree/Node/Leaf with the X versions.  That’s all.  A trivial change, and now you get reference-equality-preservation "for free".

### The XFold boilerplate – catamorphisms++

I just said "for free", but of course it’s not entirely free.  After all, we had to pay the price of defining these new X functions.  Just like the Fold functions I previously showed you, however, these functions are entirely boilerplate – given a discriminated union type definition, a (very-well-trained) monkey could author XFold, Fold, and the X-constructors.  (You might not be able to write them yet, but that’s because I haven’t trained you – I’ve simply asserted that there exists a mechanical algorithm from "data type" to "useful fold functions".  I haven’t yet tried to find a way to automagically create these functions using F# reflection, or F# quotations, or whatnot, but those might be interesting future pursuits.)

The moral is, if you have a recursive discriminated union type that you will be using a lot, you should spend a little time up-front and define these handy functions alongside the data type.  Then you can express practically every possible function over this data type as a simple application of Fold (or of XFold and the X-constructors).  Folds are a huge win – they are an omnipresent idiom in functional programming.  You should "wear them on your tool belt" (not just "keep them in your tool box" – Folds come up all the time, so you want the tool right at hand, at every moment) whenever you are writing F# code.

### The rest

The pictures in this blog entry are just screenshots from today’s program (code below).  There are two portions of the code below that I did not discuss in the blog entry.  "DiffTree" is a function that compares the interior nodes of two trees for reference-equality, returning a new tree with an extra boolean value at each interior node; check out the code itself for details.  Of course, DiffTree is implemented as an application of XFoldTree.  "Draw" is a function that renders a Tree on a graphics Canvas using WPF.  It recursively partitions the Canvas into portions for the current node, the left subtree, and the right subtree.  Of course, Draw is implemented as an application of FoldTree.  (Did I mention that you use folds all the time in F#?)  Check out the code; it’s short.

### The source code

Here’s today’s dose of F# goodness!

#I @"C:\Program Files\Reference Assemblies\Microsoft\Framework\v3.0"
#r @"WindowsBase.dll"
#r @"PresentationCore.dll"
#r @"PresentationFramework.dll"

open System

// handy operator
let (===) = fun x y -> Object.ReferenceEquals(x,y)

type Tree<‘a> =
| Node of (*data*)‘a * (*left*)Tree<‘a> * (*right*)Tree<‘a>
| Leaf

//     4
//  2     6
// 1 3   5 7
let tree7 = Node(4, Node(2, Node(1, Leaf, Leaf), Node(3, Leaf, Leaf))
Node(6, Node(5, Leaf, Leaf), Node(7, Leaf, Leaf)))

// XFoldTree : (‘a -> ‘r -> ‘r -> Tree<‘a> -> ‘r) -> (Tree<‘a> -> ‘r) -> Tree<‘a> -> ‘r
let XFoldTree nodeF leafV tree =
let rec Loop t cont =
match t with
| Node(x,left,right) -> Loop left  (fun lacc ->
Loop right (fun racc ->
cont (nodeF x lacc racc t))) // note ‘t’
| Leaf -> cont (leafV t) // note ‘t’
Loop tree (fun x -> x)
// Can express the usual Fold in terms of XFold:
// FoldTree : (‘a -> ‘r -> ‘r -> ‘r) -> ‘r -> Tree<‘a> -> ‘r
let FoldTree nodeF leafV tree =
XFoldTree (fun x l r _ -> nodeF x l r) (fun _ -> leafV) tree
// Since the "X" version takes an extra tree parameter (the ‘original’ tree),
// we can also define "X" versions of the constructors which preserve reference-equality:
let XNode (x,l,r) (Node(xo,lo,ro) as orig) =
if xo = x && lo === l && ro === r then
orig
else
Node(x,l,r)
let XLeaf (Leaf as orig) =
orig
// (Note that XFold, Fold, and the X-constructors are potentially useful boilerplate for
//  every recursive DU type.)

// original version recreates entire tree, yuck
let Change5to0 tree =
FoldTree (fun x l r -> Node((if x=5 then 0 else x), l, r)) Leaf tree
// here’s a "smart" one written by hand
let rec MyChange5to0 tree =
match tree with
| Leaf -> tree
| Node(x,l,r) ->
let newL = MyChange5to0 l
let newR = MyChange5to0 r
if x<>5 && newL === l && newR === r then
tree
else
Node((if x = 5 then 0 else x), newL, newR)
// here it is with XFold – same as original, only with Xs
let XChange5to0 tree =
XFoldTree (fun x l r -> XNode((if x=5 then 0 else x), l, r)) XLeaf tree

let Change9to0 tree =
FoldTree (fun x l r -> Node((if x=9 then 0 else x), l, r)) Leaf tree
let XChange9to0 tree =
XFoldTree (fun x l r -> XNode((if x=9 then 0 else x), l, r)) XLeaf tree

// DiffTree: Tree<‘a> * Tree<‘a> -> Tree<‘a * bool>
// return second tree with extra bool
// the bool signifies whether the Node "ReferenceEquals" the first tree
let rec DiffTree(tree,tree2) =
XFoldTree (fun x l r t t2 ->
let (Node(x2,l2,r2)) = t2
Node((x2,t===t2), l l2, r r2)) (fun _ _ -> Leaf) tree tree2

let ch9to0 = DiffTree(tree7, Change9to0 tree7)
let xch9to0 = DiffTree(tree7, XChange9to0 tree7)
let ch5to0 = DiffTree(tree7, Change5to0 tree7)
let mych5to0 = DiffTree(tree7, MyChange5to0 tree7)
let xch5to0 = DiffTree(tree7, XChange5to0 tree7)

open System.Windows
open System.Windows.Controls
open System.Windows.Input
open System.Windows.Media
open System.Windows.Shapes

// Handy functions to make multiple transforms be a more fluent interface
let IdentT() = new TransformGroup()
let ScaleT x y (tg : TransformGroup) = tg.Children.Add(new ScaleTransform(x, y)); tg
let TranslateT x y (tg : TransformGroup) = tg.Children.Add(new TranslateTransform(x, y)); tg

// Draw: Canvas -> Tree<int * bool> -> unit
let Draw (canvas : Canvas) tree =
// assumes canvas is normalized to 1.0 x 1.0
FoldTree (fun (x,b) l r trans ->
// current node in top half, centered left-to-right
let tb = new TextBox(Width=100.0, Height=100.0, FontSize=70.0, Text=sprintf "%d" x,
// the tree is a "diff tree" where the bool represents
// "ReferenceEquals" differences, so color diffs Red
Foreground=(if b then Brushes.Black else Brushes.Red)
HorizontalContentAlignment=HorizontalAlignment.Center,
VerticalContentAlignment=VerticalAlignment.Center)
tb.RenderTransform <- IdentT() |> ScaleT 0.005 0.005 |> TranslateT 0.25 0.0 |> AddT trans
// left child in bottom-left quadrant
l (IdentT() |> ScaleT 0.5 0.5 |> TranslateT 0.0 0.5 |> AddT trans)
// right child in bottom-right quadrant
r (IdentT() |> ScaleT 0.5 0.5 |> TranslateT 0.5 0.5 |> AddT trans)
) (fun _ -> ()) tree (IdentT())

type MyWPFWindow<‘a>(tree : Tree<‘a>, draw : Canvas -> Tree<‘a> -> unit) as this =
inherit Window()

let canvas = new Canvas(Width=1.0, Height=1.0, Background = Brushes.Blue,
LayoutTransform=new ScaleTransform(200.0, 200.0))
do
draw canvas tree
this.Content <- canvas
this.Title <- "MyWPFWindow"
this.SizeToContent <- SizeToContent.WidthAndHeight

do
let app =  new Application()
app.Run(new MyWPFWindow<_>(ch9to0, Draw)) |> ignore
//app.Run(new MyWPFWindow<_>(xch9to0, Draw)) |> ignore
//app.Run(new MyWPFWindow<_>(ch5to0, Draw)) |> ignore
//app.Run(new MyWPFWindow<_>(mych5to0, Draw)) |> ignore
//app.Run(new MyWPFWindow<_>(xch5to0, Draw)) |> ignore

Posted in Uncategorized | 2 Comments »

## DebuggerVisualizers in F#

Posted by Brian on May 17, 2008

One of my very favorite features of Visual Studio is debugger visualizers.  These let you pop up a custom display of values, like those values that appear in the "locals" window, for example.

The F# team has not yet invested much effort in the F# debugging experience.  (EDIT, Jan 2010: the out-of-the-box debugging experience is much improved now.  This entry is still useful to demonstrate custom visualizers, but you won’t need them for basic types.)  One thing that needs improvement is the appearance of values in the locals window.  For example, look at how these list variables ("lc" and "li") appear by default:

The "Value" in the locals window at the bottom just displays as "{Microsoft.FSharp.Collections.List<char>._Cons}", for instance.  That doesn’t help much when you’re debugging your program – typically you want to see the values in the list (e.g. "[‘a’; ‘b’; ‘c’]").

Though we’ll undoubtedly improve the out-of-the-box story here in a future release of F#, the current situation gives me a good excuse to talk about debugger visualizers.  When you install a visualizer, a little magnifying-glass icon appears next to values, along with a drop-down menu that lets you select among the visualizers.  In today’s blog entry, I’ll show how to install a "list visualizer" which can be selected in the debugger as suggested in the screenshot below (note the "FSharp List Visualizer" drop-down near the very bottom of the picture):

When selected, it will pop up a dialog box that displays the list contents:

### Installing the debugger visualizer

For those of you who just want the install instructions to try this out, I’ll summarize them:

From the Visual Studio "Tools\Options" menu, under "Debugging\General", uncheck "warn if no symbols on launch" (see screenshot below).

Build the F# code that appears at the end of this blog into an exe.  Then copy the exe into the VS debugger visualizers directory, using a command-line like:

copy MyDebugViz.exe "c:\Program Files\Microsoft Visual Studio 9.0\Common7\Packages\Debugger\Visualizers"

Close Visual Studio.  Re-open Visual Studio.

That’s it – now you’re ready to go.  Just put a breakpoint on the "printf" line as suggested by the screenshot below, and you should see the magnifying glass icon in the locals window next to list values, as in the previous screenshots.

### Authoring debugger visualizers

Though the documentation for visualizers is a little sparse, simple visualizers are pretty easy to write.  I won’t go into all the nitty gritty details, but I’ll give the high-level overview.  There are three main parts.

First, there is the "object source", which runs in the debuggee (the process being debugged).  It is used to serialize "some data about the object we want to debug" into a stream which we can send to the debugger.  Here’s an example, that uses <sprintf "%A"> as a way to pretty-print an F# value to a string, which is then written to a stream.

type FSharpObjectSource() =
inherit VisualizerObjectSource()
override this.GetData(target : Object, outgoingData : System.IO.Stream) =
let formatter = new BinaryFormatter()
formatter.Serialize(outgoingData, sprintf "%A" target)
()

Next, there is the "debugger visualizer", which runs in the debugger, and receives the data from the debuggee via an "object provider".  It can display the information it receives in a dialog box.  In the code below, we receive our string data, and then just create a Form with a RichTextBox to display the data.

type FSharpDebuggerVisualizer() =
inherit DialogDebuggerVisualizer()

override this.Show(windowService : IDialogVisualizerService,
objectProvider : IVisualizerObjectProvider) =
let data = objectProvider.GetObject()
use displayForm = new Form()
let text = new RichTextBox(Dock = DockStyle.Fill,
Text = data.ToString(),
Font = new Font("Lucida Console",10.0f,FontStyle.Bold),
ForeColor = Color.DarkBlue)
displayForm.Text <- "F# list visualizer"
windowService.ShowDialog(displayForm) |> ignore

Finally, there is an attribute which associates an object source and a visualizer with a specific data type and gives it a name:

[<assembly:DebuggerVisualizer(typeof<FSharpDebuggerVisualizer>,
typeof<FSharpObjectSource>,
Target = typedefof<Microsoft.FSharp.Collections.List<Object> >,
Description = "FSharp List Visualizer")>]

The "Target" here says that this visualizer will work on any variable with type list<‘a> (in the CLR, the type we want to target is called "List`1" – the uninstantiated-generic type for List, and this is what the F# "typedefof" operator yields).  The "Description" is the text that appears in the drop-down menu next to the magnifying glass icon (as in the second screenshot in today’s blog entry).  And the two "typeof" arguments just point to the classes that contain the code that should run in the debugger and debuggee when this visualizer is invoked.

That’s pretty much all there is to it.  If you find yourself often debugging some code that uses data that doesn’t display well naturally in the debugger, visualizers are a great way to extend the debugger to provide your own visualization of the data in your running program.

### The source code

Here’s the code:

namespace FSharpDebuggerVisualizers

#r "C:\Program Files\Microsoft Visual Studio 9.0\Common7\IDE\PublicAssemblies\Microsoft.VisualStudio.DebuggerVisualizers.dll"

open System
open System.Diagnostics
open System.Runtime.Serialization.Formatters.Binary
open System.Collections.Generic
open System.Windows.Forms
open System.Drawing
open Microsoft.VisualStudio.DebuggerVisualizers

type FSharpObjectSource() =
inherit VisualizerObjectSource()
override this.GetData(target : Object, outgoingData : System.IO.Stream) =
let formatter = new BinaryFormatter()
formatter.Serialize(outgoingData, sprintf "%A" target)
()

type FSharpDebuggerVisualizer() =
inherit DialogDebuggerVisualizer()

override this.Show(windowService : IDialogVisualizerService,
objectProvider : IVisualizerObjectProvider) =
let data = objectProvider.GetObject()
use displayForm = new Form()
let text = new RichTextBox(Dock = DockStyle.Fill,
Text = data.ToString(),
Font = new Font("Lucida Console",10.0f,FontStyle.Bold),
ForeColor = Color.DarkBlue)
displayForm.Text <- "F# list visualizer"
windowService.ShowDialog(displayForm) |> ignore

namespace Global

open System
open System.Diagnostics
open FSharpDebuggerVisualizers

module Main =

[<assembly:DebuggerVisualizer(typeof<FSharpDebuggerVisualizer>,
typeof<FSharpObjectSource>,
Target = typedefof<Microsoft.FSharp.Collections.List<Object> >,
Description = "FSharp List Visualizer")>]
do
let li = [1; 2; 3]
let lc = [‘a’; ‘b’; ‘c’]
printfn "%A %A" li lc

printfn "press a key to quit"

Posted in Uncategorized | 6 Comments »

## Connected component labeling in F#

Posted by Brian on May 12, 2008

Kirill recently posted a blog about connected component labeling in C#.  He also asked for solutions in other languages, so of course I had to code it in F#.

You can read his blog for more info, but the gist is, given a black and white grid, do a "flood fill" of each section with a different random color.  Here’s a sample before-and-after screenshot:

There are slider controls which let you control both the size of the initial black-and-white grid and the "white percentage".  So here’s a bigger example that starts off mostly white:

When you move the sliders you get a new black-and-white grid, and then when you click the button, it colors it.  Get the idea?  Cool and fun.

Anyway, I shamelessly stole all Kirill’s UI code, transliterated it to F#, and then implemented the Union-Find algorithm Kirill had mentioned, and it seems to be blazingly fast.  So I present for your enjoyment, without further commentary, the F# code:

```open System

// A partition is a mutable set of values, where one arbitrary value in the set
// is chosen as the canonical representative for that set.
type Partition<'a>(orig : 'a) as this =
[<DefaultValue(false)>] val mutable parent : Partition<'a>
[<DefaultValue(false)>] val mutable rank : int
let rec FindHelper(x : Partition<'a>) =
if Object.ReferenceEquals(x.parent, x) then
x
else
x.parent <- FindHelper(x.parent)
x.parent
do this.parent <- this
// The representative element in this partition
member this.Find() =
FindHelper(this)
// Merges two partitions
member this.Union(other : Partition<'a>) =
let thisRoot = this.Find()
let otherRoot = other.Find()
if thisRoot.rank < otherRoot.rank then
otherRoot.parent <- thisRoot
elif thisRoot.rank > otherRoot.rank then
thisRoot.parent <- otherRoot
elif not (Object.ReferenceEquals(thisRoot, otherRoot)) then
otherRoot.parent <- thisRoot
thisRoot.rank <- thisRoot.rank + 1
// The original value of this element
member this.Value = orig

open System.Diagnostics
open System.Windows.Forms
open System.Drawing

let random = new Random()
type Info() =
let mutable iMax = 1
let mutable jMax = 1
// The original grid (true = white)
let mutable grid = Array2D.create iMax jMax true
// Connected components
let mutable colorField = Array2D.create iMax jMax (new Partition<_>(Color.White))
// Initialize() resets the data and returns a white/black array
member this.Initialize pctWhite size =
iMax <- size
jMax <- size
grid <- Array2D.init iMax jMax (fun _ _ -> float (random.Next(100)) < 100.0 * pctWhite)
colorField <- Array2D.init iMax jMax (fun _ _ ->
new Partition<_>(Color.FromArgb(random.Next(256), random.Next(256), random.Next(256))))
Array2D.init iMax jMax (fun i j -> if grid.[i,j] then Color.White else Color.Black)
// Connect() connects components, and returns a tuple (numConnectedComponents, newColorArray)
member this.Connect() =
// connect components...
for i in 0 .. iMax-1 do
for j in 0 .. jMax-1 do
if i <> 0 then
if grid.[i-1,j] = grid.[i,j] then
colorField.[i-1,j].Union(colorField.[i,j])
if j <> 0 then
if grid.[i,j-1] = grid.[i,j] then
colorField.[i,j-1].Union(colorField.[i,j])
if i <> iMax-1 then
if grid.[i+1,j] = grid.[i,j] then
colorField.[i+1,j].Union(colorField.[i,j])
if j <> jMax-1 then
if grid.[i,j+1] = grid.[i,j] then
colorField.[i,j+1].Union(colorField.[i,j])
// ... count how many there are, and pick a color for each component
let h = new System.Collections.Generic.HashSet<_>()
let theField = Array2D.init iMax jMax (fun i j ->
let rep = colorField.[i,j].Find()
rep.Value  // color of representative element
)
(h.Count, theField)

// the UI
type Form1() as this =
inherit Form()
let Drawing = new PictureBox(Anchor = (AnchorStyles.Top ||| AnchorStyles.Bottom
||| AnchorStyles.Left ||| AnchorStyles.Right),
Location = new System.Drawing.Point(12, 12),
Name = "Drawing",
Size = new System.Drawing.Size(485, 405),
TabIndex = 0,
TabStop = false)
let FindComponents = new Button(Anchor = (AnchorStyles.Bottom ||| AnchorStyles.Right),
Location = new System.Drawing.Point(358, 538),
Name = "FindComponents",
Size = new System.Drawing.Size(139, 37),
TabIndex = 2,
Text = "Find components",
UseVisualStyleBackColor = true)
let PercentageSlider = new TrackBar(Anchor = (AnchorStyles.Bottom ||| AnchorStyles.Left
||| AnchorStyles.Right),
LargeChange = 2,
Location = new System.Drawing.Point(176, 423),
Maximum = 40,
Name = "PercentageSlider",
Size = new System.Drawing.Size(321, 53),
TabIndex = 3,
Value = 20)
let label1 = new Label(Anchor = (AnchorStyles.Bottom ||| AnchorStyles.Left),
AutoSize = true,
Location = new System.Drawing.Point(12, 434),
Name = "label1",
Size = new System.Drawing.Size(124, 17),
TabIndex = 4,
Text = "White percentage:")
let label2 = new Label(Anchor = (AnchorStyles.Bottom ||| AnchorStyles.Left),
AutoSize = true,
Location = new System.Drawing.Point(12, 470),
Name = "label2",
Size = new System.Drawing.Size(71, 17),
TabIndex = 6,
Text = "Field size:")
let FieldSizeSlider = new TrackBar(Anchor = (AnchorStyles.Bottom ||| AnchorStyles.Left
||| AnchorStyles.Right),
LargeChange = 2,
Location = new System.Drawing.Point(176, 470),
Maximum = 100,
Minimum = 1,
Name = "FieldSizeSlider",
Size = new System.Drawing.Size(321, 53),
TabIndex = 5,
Value = 5)
let Status = new Label(Anchor = (AnchorStyles.Bottom ||| AnchorStyles.Left),
AutoSize = true,
Location = new System.Drawing.Point(15, 538),
Name = "Status",
Size = new System.Drawing.Size(0, 17),
TabIndex = 7)

let mutable field = Array2D.create 1 1 Color.White  // the array we will Draw

let Draw (canvas : Control) (graphics : Graphics) =
let width  = float32 canvas.ClientSize.Width
let height = float32 canvas.ClientSize.Height
let iMax = Array2D.length1 field
let jMax = Array2D.length2 field
let iMaxFloat = float32 iMax
let jMaxFloat = float32 jMax
for i in 0 .. iMax-1 do
for j in 0 .. jMax-1 do
let w = width / iMaxFloat
let h = height / jMaxFloat
use brush = new SolidBrush(field.[i, j])
graphics.FillRectangle(brush, w * float32 i, h * float32 j, w, h)

let info = new Info()

do this.InitializeComponent()

member this.Repaint() = Drawing.Invalidate()

member private this.Form1_Resize sender e =
let maxFieldSize = Math.Max(5, Math.Min(Drawing.ClientSize.Width, Drawing.ClientSize.Height))
FieldSizeSlider.Maximum <- maxFieldSize
this.Repaint()

member private this.FindComponents_Click sender e =
let stopwatch = new Stopwatch()
stopwatch.Start()
let count, newField = info.Connect()
field <- newField
stopwatch.Stop()
Status.Text <- sprintf "Found %d connected components, took %dms" count stopwatch.ElapsedMilliseconds
this.Repaint()

member this.Regenerate() =
let size = FieldSizeSlider.Value
let pct = float PercentageSlider.Value / float PercentageSlider.Maximum
field <- info.Initialize pct size
Status.Text <- sprintf "%d x %d, White:%f" size size pct
this.Repaint()

member private this.InitializeComponent() =
(Drawing :> System.ComponentModel.ISupportInitialize).BeginInit()
(PercentageSlider :> System.ComponentModel.ISupportInitialize).BeginInit()
(FieldSizeSlider :> System.ComponentModel.ISupportInitialize).BeginInit()
this.SuspendLayout()
Drawing.Paint.AddHandler(fun s e -> Draw (Drawing :> Control) e.Graphics)
this.AcceptButton <- FindComponents
this.AutoScaleDimensions <- new System.Drawing.SizeF(float32 8, float32 16)
this.AutoScaleMode <- System.Windows.Forms.AutoScaleMode.Font
this.ClientSize <- new System.Drawing.Size(509, 587)
this.DoubleBuffered <- true
this.Name <- "Form1"
this.StartPosition <- System.Windows.Forms.FormStartPosition.CenterScreen
this.Text <- "Find connected components"
(Drawing :> System.ComponentModel.ISupportInitialize).EndInit()
(PercentageSlider :> System.ComponentModel.ISupportInitialize).EndInit()
(FieldSizeSlider :> System.ComponentModel.ISupportInitialize).EndInit()
this.ResumeLayout(false)
this.PerformLayout()
this.Regenerate()

do
Application.EnableVisualStyles()
Application.SetCompatibleTextRenderingDefault(false)
Application.Run(new Form1())
```

## “FSI is the new perl”

Posted by Brian on May 9, 2008

When I need a quick-and-dirty fifteen-line script for a one-off task involving text files, I often use perl.  The problem is, I use perl infrequently enough that each time I decide to use it, I usually need to give myself a five-minute refresher on the syntax and common functions before I can get the job done.

On the other hand, I use F# every day.

Thus today’s blog entry is just to call out how easy it is to write little handy scripts with F#.

### FSI

I haven’t talked about FSI much.  You can use F# Interactive from the command-line (fsi.exe), or as a Visual Studio Add-in (inside VS, select "Tools\Add-in Manager…" and click the check box next to F# interactive).  I like the VS add-in because it makes it easy to use the VS text editor as a "scratch pad" with syntax highlighting and intellisense.  When you have code you want to execute, just select it and press Alt-Enter and the code will be sent to the FSI window and executed.

### A sample script

Suppose I want to know what percentage of the sample .fs files in the F# distribution use the lightweight syntax option (#light).  (EDIT, Jan 2010: #light is now the default, so this script is no longer useful for this particular task, though it does show how to find what percentage of files contain an arbitrary substring.)  I can quickly hack together:

open System.IO

let Average l =
List.reduce (+) l / List.length l

let rec AllFiles dir =
seq { yield! Directory.GetFiles(dir)
for subdir in Directory.GetDirectories(dir) do yield! AllFiles subdir }

[ for file in AllFiles @"C:\Program Files\FSharp-1.9.4.15\samples" do
if file.EndsWith(".fs") then
yield 100
else
yield 0 ]
|> Average
|> printfn "%d%% of files use #light"

Highlight this code, press alt-enter, and FSI says

val Average : int list -> int
val AllFiles : string -> seq<string>
91% of files use #light

Cool.  I wonder which files don’t use #light?  I can just add a little code to the "else" branch:

else
do printfn "no #light: %s" file
yield 0 ]

and then highlight the last block of code (from "[for…" to the end of the file) and hit alt-enter again, and I see

no #light: C:\Program Files\FSharp-1.9.4.15\samples\fsharp\Differentiate\lex.fs
no #light: C:\Program Files\FSharp-1.9.4.15\samples\fsharp\Differentiate\pars.fs
no #light: C:\Program Files\FSharp-1.9.4.15\
samples\fsharp\FLinq\dumper.fs
no #light: C:\Program Files\FSharp-1.9.4.15\samples\fsharp\FLinq\program.fs
no #light: C:\Program Files\FSharp-1.9.4.15\samples\fsharp\Parsing\ast.fs
91% of files use #light
val it : unit = ()

in the FSI window.  Neat.

There might be shorter or more elegant ways to accomplish the same goal with F# (or perl, or what have you), but my focus today is on writability, demonstrating that it’s easy to hack little scripts like this in less than five minutes.

### Some F# details

The script above demos some F# bits that I don’t think I’ve talked about before.  The "seq { … }" code is an example of a sequence comprehension, another example of F#’s computation expression syntax.  Recall that "seq" (short for "sequence") just means "IEnumerable".  Inside a sequence comprehension, "yield" means the same thing as it does in a C# iterator block, and "yield!" means nearly the same thing, except that you pass it a sequence rather than a single item.  (In other words, "yield! s" is like "for i in s do yield i", where s is a seq<‘a> and i is an ‘a.)  So AllFiles returns a seq<string> that recursively enumerates all the file names under some directory.

The portion in square brackets is a list comprehension, which is pretty much just like a sequence comprehension, except the result is a list<‘a> rather than a seq<‘a>.  Thus we end up with a list of integers, with the value 100 for each file containing "#light", and 0 for the other files.  We average the values in the list, and we get the percentage of files that use #light.

That’s all for today – just some quickie fun I wanted to share!

Posted in Uncategorized | 1 Comment »

## “An Introduction to Async Workflows in F#”, or “how to utilize all those CPUs without writing lots of threading code”, part three

Posted by Brian on May 7, 2008

Last time I showed you how to use the F# Control library to easily parallelize a primes-computing program.  Today I’ll show you how to use the same library in C# to achieve the same end.  I’ll also talk more about one of the real strong suits of the library – making async programming more compositional – and this leads to all kinds of interesting discussions for C#, involving LINQ, as well as iterators and "yield".  Hold on tight – it’s a wild ride!

### Easy async from C#

As we saw last time, the F# solution involved calling library functions like Async.Parallel, but it also involved a tiny async workflow that looked like this:

async { return (x, IsPrime x) }

That is, this part of the F# solution leveraged the F# computation expression syntax.  We don’t have this syntax available in C#, so what are we to do?

As I hinted obliquely last time, C# has its own syntax sugar that will fit the bill: LINQ.  The key piece of the original C# code that we need to parallelize can be written this way:

var primeInfo = nums.Select((x) => new KeyValuePair<int, bool>(x, IsPrime(x))).ToArray();

That’s the bit that takes more than 12 seconds to run on my box.  We can parallelize just as in F#, using the F# library + LINQ thusly:

var computations = nums.Select((x) =>
from dummy in AsyncExtensions.StartWorkflow // enter async monad & protect rest of code in a lambda
select new KeyValuePair<int, bool>(x, IsPrime(x)));
var primeInfo = AsyncExtensions.Run(AsyncExtensions.Parallel(computations));

I’ll explain it in a minute, but the first thing to note is – we got the same big win as in F#.  If you look back at the original C# code from part one, you’ll see it was about 10 lines of mess involving ThreadPool.QueueUserWorkItem, ManualResetEvent, and Interlocked.Decrement.  The code above is much simpler – we just create a sequence of all the computations we want to do, parallelize them, and run.

AsyncExtensions is a small wrapper class I authored that just wraps up the F# Control library in a thin facade that makes it more C#-friendly.  You’ll get a chance to see the implementation shortly.  The Run() and Parallel() methods just forward calls to the corresponding Async calls in the F# Control library.

The interesting/unexpected part is the LINQ query.  Though you typically think of LINQ as just syntactic sugar for authoring queries over IEnumerables, the way LINQ is defined in the C# language specification is far more general, and enables the LINQ syntax (things like "from" and "select") to be used in an arbitrary monad.  (I demonstrated this a long while back, when I showed how to use LINQ in the definition of monadic parser combinators in C#.)  I’m continuing to defer the full discussion about monads (what they are, why they matter, what LINQ has to do with it) because at this point it would still be a needless distraction.  All you need to do right now is take it on faith that this C# code:

from dummy in AsyncExtensions.StartWorkflow
rest_of_linq_query

means the same thing as this F# code:

async { body_of_computation }

and that this C# inside a LINQ query:

select expr

means the same as this F# inside a computation expression:

return expr

and you’re good to go.  Actually, you don’t have to just take it on faith – you can try the code yourself.  Here’s the full C# code.  Just throw it in a C# project, reference FSharp.Core.dll, and try it out.  But then keep reading – there’s more blog after this code:

```//#define SYNC
using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.FSharp.Core;
using Microsoft.FSharp.Control;
using System.Diagnostics;

class Program
{
static Stopwatch stopWatch = new Stopwatch();
static void ResetStopWatch() { stopWatch.Reset(); stopWatch.Start(); }
static void ShowTime() { Console.WriteLine("took {0} ms", stopWatch.ElapsedMilliseconds); }

static bool IsPrime(int x)
{
for (int i = 2; i < x; ++i)
{
if (x % i == 0)
return false;
}
return true;
}
public static void Main()
{
var nums = new int;
for (int i = 0; i < nums.Length; ++i)
nums[i] = 10000000 + i;
ResetStopWatch();
#if SYNC
Console.WriteLine("Computing primes sequentially...");
var primeInfo = nums.Select((x) => new KeyValuePair<int, bool>(x, IsPrime(x))).ToArray();
#else
Console.WriteLine("Computing primes in parallel...");
var computations = nums.Select((x) =>
from dummy in AsyncExtensions.StartWorkflow
select new KeyValuePair<int, bool>(x, IsPrime(x)));
var primeInfo = AsyncExtensions.Run(AsyncExtensions.Parallel(computations));
#endif
ShowTime();
var primes = from x in primeInfo
where x.Value
select x.Key;
foreach (var x in primes)
Console.Write("{0},", x);
Console.WriteLine();
ShowTime();
Console.WriteLine("press a key");
}
}

// boilerplate code to wrap F# library in a nice C# facade
static class AsyncExtensions
{
static Microsoft.FSharp.Control.FSharpAsyncBuilder async = Microsoft.FSharp.Core.ExtraTopLevelOperators.DefaultAsyncBuilder;

// easily massage "Func" types into F# function types
public static FSharpFunc<A, B> ToFastFunc<A, B>(this Func<A, B> f)
{
return FuncConvert.ToFSharpFunc(new Converter<A, B>(f));
}
// LINQ syntax sugars
public static FSharpAsync<B> Select<A, B>(this FSharpAsync<A> x, Func<A, B> selector)
{
return async.Bind(x,
ToFastFunc<A, FSharpAsync<B>>((r) => async.Return(selector(r))));
}
public static FSharpAsync<V> SelectMany<T, U, V>(
this FSharpAsync<T> p, Func<T, FSharpAsync<U>> selector, Func<T, U, V> projector)
{
return async.Bind(p, FuncConvert.ToFSharpFunc<T, FSharpAsync<V>>(new System.Converter<T, FSharpAsync<V>>(r1 =>
async.Bind(selector(r1), FuncConvert.ToFSharpFunc<U, FSharpAsync<V>>(r2 =>
async.Return(projector(r1, r2)))))));
}
// Wrap F# Control library functions in simpler facade
public static FSharpAsync<R[]> Parallel<R>(IEnumerable<FSharpAsync<R>> computations)
{
return Microsoft.FSharp.Control.FSharpAsync.Parallel<R>(computations);
}
public static R Run<R>(FSharpAsync<R> computation)
{
return Microsoft.FSharp.Control.FSharpAsync.RunSynchronously(computation,
}
// convenience object to get in the Async monad
public static FSharpAsync<int> StartWorkflow = async.Return(0);
}
```

So there’s some fun C# code you can run with today.

### Compositional async code

We’ve seen how the F# Control library can be used to parallelize computations in both F# and C#.  But parallelization is just one aspect of the F# Control library.  An even more enticing value proposition is the ability to write async code that composes easily.  Let’s consider another example, from a networking domain, using WCF.

Suppose I have a web service that exposes an endpoint that can be used to compute squares of integers – for example, you pass 5 to the web service, and it does some extremely difficult computations and finally returns you the answer 25.  (As is often the case, my blog samples are very contrived, in order to stay simple.)  Given a particular object that represents the connection to this service, we might write some C# code like this:

static int SumSquares(IMyClientContract client)
{
((IClientChannel)client).Open();
var sq1 = client.Square(3);
var sq2 = client.Square(4);
((IClientChannel)client).Close();
return sq1 + sq2;
}

as a sample of what we can do with a "client" connection to the web service.

Now, each of the operations on the client (Open(), Square(), and Close()) can potentially involve a call out over the network.  In the code above, all the code executes synchronously, which means this function holds a CLR thread for the duration of the whole call to SumSquares().  Sometimes this is fine, but often (especially when writing servers or middle-tier components) we need to be more frugal when it comes to resources like threads, and ensure that we are only holding threads when necessary – not while we are blocked, waiting for some network call to return.  To this end, the .NET framework provides the Begin/End pattern and IAsyncResult type.  So for example, in addition to methods like Open(), frameworks also provide the corresponding async versions via BeginOpen() and EndOpen().  This API pattern makes it possible to get the job done – you can make a "Begin" call with a callback object, release the current thread, and then when the operation eventually finishes, your callback gets invoked with the result so you can pick up where you left off (probably with code now running on a different thread).

While the Begin/End pattern is somewhat workable for a single call, it fails miserably for composing a series of async calls.  Suppose we want to author BeginSumSquares() and EndSumSquares(), with the implementation making calls to the Begin/End versions of Open, Square, and Close.  This is a perfectly reasonable thing to want to do – in fact, if you work on framework code in this kind of domain, this may be something you need to do all the time.  Ideally it would be straightforward – SumSquares is a five-line method, and we just want to do the same thing, only async.  In practice, it’s a nightmare.  I won’t even attempt to write the code for Begin/End-SumSquares here, because I know I will get it wrong.  The Begin/End pattern forces you into a hideous mess of spaghetti code where each async call necessitates a new callback method and a new IAsyncResult object, and this simple SumSquares example will probably take on the order of 100 lines of code to implement async.  If you’ve never had to write this kind of code before, thank your lucky stars.

Again, the problem is that the Begin/End pattern does not compose.  If I have two synchronous methods I want to call in series, one after another, I just write "Method1(); Method2();".  But with two async methods, I have to write tons of code just to correctly string two calls together in series.  What we need is a pattern for writing async code that makes composing a series of async calls as easy as composing a series of sync calls.

In F# this is easy to do.  The F# synchronous code looks like this:

let SumSquares (client : IMyClientContract) =
(box client :?> IClientChannel).Open()
let sq1 = client.Square(3)
let sq2 = client.Square(4)
(box client :?> IClientChannel).Close()
sq1 + sq2

(The "box" and ":?>" bits are just how the cast to type IClientChannel is performed in F#.)  To make it async, rather than use the Begin/End pattern, we can use the F# Async pattern (which is easy to build on top of the Begin/End methods, using the Async.FromBeginEnd function in the library).  Then we can use F# async workflows like this:

let SumSquaresAsync (client : IMyClientContract) =
async { do! (box client :?> IClientChannel).OpenAsync()
let! sq1 = client.SquareAsync(3)
let! sq2 = client.SquareAsync(4)
do! (box client :?> IClientChannel).CloseAsync()
return sq1 + sq2 }

The "do!" keyword in an F# async workflow lets us call an async method when we don’t care about the result, and the "let!" keyword calls an async method and binds the result to a new variable name.  As a result, our original five-line synchronous method is still just five lines when we rewrite it to run asynchronously – the difference is that we write the code inside an async workflow.

It turns out that we can do the same thing for C#.  This sync C# code:

static int SumSquares(IMyClientContract client)
{
((IClientChannel)client).Open();
var sq1 = client.Square(3);
var sq2 = client.Square(4);
((IClientChannel)client).Close();
return sq1 + sq2;
}

can be rewritten as this async code:

static Async<int> SumSquaresAsync(IMyClientContract client)
{
return from _0  in AsyncExtensions.StartWorkflow
from _1  in ((IClientChannel)client).OpenAsync()
from sq1 in client.SquareAsync(3)
from sq2 in client.SquareAsync(4)
from _2  in ((IClientChannel)client).CloseAsync()
select sq1 + sq2;
}

using the F# Control library from C#.  Again, I am using LINQ.  Once we enter the async monad (the first line with "StartWorkflow"), each subsequent "from" in C# is like a "let!" in F#.  There is no LINQ syntax that corresponds to "do!", so we have to use "from" and bind the meaningless results to dummy variable names (I chose "_0", "_1", and "_2" as the names for my "don’t care" variables here).  The code looks a little weird, since we are "abusing" LINQ in order to achieve our goal.  But I am a pragmatic, and if I can save myself from having to write 100 lines of nightmare Begin/End/IAsyncResult/callback code in order to achieve composable async C# code, then I am willing to pay the price of having to use some awkward syntax (the "from", "select", and dummy variables).  The code looks a little weird, but it still feels like a big win.

### Shortcomings of the LINQ approach to async in C#, and an alternative approach

The async C# code I just showed is pretty nifty, but there are more problems with the "LINQ approach to async" other than just the awkward syntax.  The example I chose (SumSquaresAsync) was very simple – a method with straight-line code that made five async method calls.  What if we want to start with some more complicated synchronous code, that involves if-then-else, while loops, try-catch blocks, or arbitrary other C# constructs?  These constructs do not have an obvious/straightforward mapping into LINQ when we try to create the corresponding async code.  As a result, the async version of code using such constructs will probably have to look different from (and be more complicated than) the corresponding sync code.  That’s unfortunate, as it erodes the main benefit we were out to achieve in the first place (async code that’s as simple as the original sync code).

There is an alternative to the LINQ approach.  Another of the C# language’s "syntax sugars" fits the bill: "yield".  Iterator blocks that use the "yield" statement create a way to write C# code that will ‘exit and return later where we left off’, which is just the type of thing you need for writing async code.  As a result, it’s possible to build an async library atop the iterator metaphor, rather than atop an async monad (utilizing LINQ).  This is the approach taken, for example, by CCR in Robotics Studio, which you can read a little about here.  I haven’t yet studied this approach in depth, but it seems very interesting, as it doesn’t suffer the LINQ drawbacks I just mentioned in the previous paragraph.  It’s possible the two approaches might be complimentary (perhaps the same library can expose both the LINQ programming model and the "yield"/iterator programming model for composing async computations).

### What’s next?

There’s potentially a lot more to talk about, but this is a good place to wrap things up for today.

### Source code

Below is the full source code for the WCF example – first in F#, then in C#.

F# code

```open System
open System.Collections.Generic
open System.Diagnostics
open System.ServiceModel
open System.ServiceModel.Channels
open Microsoft.FSharp.Control

// define WCF service
[<ServiceContract>]
type IMyContract = interface
[<OperationContract>]
abstract Square: x:int -> int
end

[<ServiceContract(Name="IMyContract")>]
type IMyClientContract =
[<OperationContract>]
abstract Square: x:int -> int
[<OperationContract(AsyncPattern = true)>]
abstract BeginSquare: x:int * cb:AsyncCallback * o:obj -> IAsyncResult
abstract EndSquare: iar:IAsyncResult -> int

type MyService() = class
interface IMyContract with
member this.Square x = x * x
end

// set up a WCF service, and then run a client function against it
let DoWCFRun (clientFunc : IMyClientContract -> int) =
let host = new ServiceHost(typeof<MyService>, [|address|])
let reliableBinding = new WSHttpBinding(SecurityMode.None, true)
host.Open()

let client = cf.CreateChannel()
let ans = clientFunc client
printfn "done - answer is %d" ans
host.Close()

// a sample client function that runs synchronously
let SumSquares (client : IMyClientContract) =
(box client :?> IClientChannel).Open()
let sq1 = client.Square(3)
let sq2 = client.Square(4)
(box client :?> IClientChannel).Close()
sq1 + sq2

// run it
DoWCFRun SumSquares

// define Async versions of the key client methods
type IClientChannel with
member this.OpenAsync() =
Async.FromBeginEnd(this.BeginOpen, this.EndOpen)
member this.CloseAsync() =
Async.FromBeginEnd(this.BeginClose, this.EndClose)
module Extensions =
type IMyClientContract with
member this.SquareAsync x =
Async.FromBeginEnd(x, this.BeginSquare, this.EndSquare)
open Extensions

// async version of our sample client - does not hold threads while calling out to network
let SumSquaresAsync (client : IMyClientContract) =
async { do! (box client :?> IClientChannel).OpenAsync()
let! sq1 = client.SquareAsync(3)
let! sq2 = client.SquareAsync(4)
do! (box client :?> IClientChannel).CloseAsync()
return sq1 + sq2 }

DoWCFRun (SumSquaresAsync >> Async.RunSynchronously)  // ">>" is function composition operator

printfn "press a key"
```

C# code

```//#define SYNC
using System;
using System.Collections.Generic;
using System.Linq;
using Microsoft.FSharp.Core;
using Microsoft.FSharp.Control;
using System.Diagnostics;
using System.ServiceModel;
using System.ServiceModel.Channels;

// define WCF service
[ServiceContract]
interface IMyContract
{
[OperationContract]
int Square(int x);
}

[ServiceContract(Name = "IMyContract")]
interface IMyClientContract
{
[OperationContract]
int Square(int x);
[OperationContract(AsyncPattern = true)]
IAsyncResult BeginSquare(int x, AsyncCallback cb, object o);
int EndSquare(IAsyncResult iar);
}

class MyService : IMyContract
{
public int Square(int x)
{
return x * x;
}
}

class Program
{
// set up a WCF service, and then run a client against it
public static void Main()
{
ServiceHost host = new ServiceHost(typeof(MyService), address);
Binding reliableBinding = new WSHttpBinding(SecurityMode.None, true);
host.Open();

IMyClientContract client = cf.CreateChannel();
#if SYNC
var ans = SumSquares(client);
#else
var ans = AsyncExtensions.Run(SumSquaresAsync(client));
#endif
Console.WriteLine("done - answer is {0}", ans);
host.Close();
Console.WriteLine("press a key");
}
// a sample client function that runs synchronously
static int SumSquares(IMyClientContract client)
{
((IClientChannel)client).Open();
var sq1 = client.Square(3);
var sq2 = client.Square(4);
((IClientChannel)client).Close();
return sq1 + sq2;
}
// async version of our sample client - does not hold threads while calling out to network
static FSharpAsync<int> SumSquaresAsync(IMyClientContract client)
{
return from _0 in AsyncExtensions.StartWorkflow
from _1 in ((IClientChannel)client).OpenAsync()
from sq1 in client.SquareAsync(3)
from sq2 in client.SquareAsync(4)
from _2 in ((IClientChannel)client).CloseAsync()
select sq1 + sq2;
}
}

// define Async versions of the key client methods
static class ClientExtension
{
public static FSharpAsync<Unit> OpenAsync(this IClientChannel client)
{
return AsyncExtensions.FromBeginEnd(client.BeginOpen, client.EndOpen);
}
public static FSharpAsync<Unit> CloseAsync(this IClientChannel client)
{
return AsyncExtensions.FromBeginEnd(client.BeginClose, client.EndClose);
}
public static FSharpAsync<int> SquareAsync(this IMyClientContract client, int x)
{
return AsyncExtensions.FromBeginEnd<int, int>(x, client.BeginSquare, client.EndSquare);
}
}

// boilerplate code to wrap F# library in a nice C# facade
static class AsyncExtensions
{
static Microsoft.FSharp.Control.FSharpAsyncBuilder async = Microsoft.FSharp.Core.ExtraTopLevelOperators.DefaultAsyncBuilder;
// easily massage "Func" types into F# function types
public static FSharpFunc<A, Result> ToFSharpFunc<A, Result>(this Func<A, Result> f)
{
return FuncConvert.ToFSharpFunc(new Converter<A, Result>(f));
}
public static FSharpFunc<Tuple<A1, A2>, Result> ToTupledFSharpFunc<A1, A2, Result>(this Func<A1, A2, Result> f)
{
return FuncConvert.ToFSharpFunc(new Converter<Tuple<A1, A2>, Result>(t => f(t.Item1, t.Item2)));
}
public static FSharpFunc<Tuple<A1, A2, A3>, Result> ToTupledFSharpFunc<A1, A2, A3, Result>(this Func<A1, A2, A3, Result> f)
{
return FuncConvert.ToFSharpFunc(new Converter<Tuple<A1, A2, A3>, Result>(t => f(t.Item1, t.Item2, t.Item3)));
}
// LINQ syntax sugars
public static FSharpAsync<B> Select<A, B>(this FSharpAsync<A> x, Func<A, B> selector)
{
return async.Bind(x,
ToFSharpFunc<A, FSharpAsync<B>>((r) => async.Return(selector(r))));
}
public static FSharpAsync<V> SelectMany<T, U, V>(this FSharpAsync<T> p, Func<T, FSharpAsync<U>> selector, Func<T, U, V> projector)
{
return async.Bind(p, FuncConvert.ToFSharpFunc(new System.Converter<T, FSharpAsync<V>>(r1 =>
async.Bind(selector(r1), FuncConvert.ToFSharpFunc<U, FSharpAsync<V>>(r2 =>
async.Return(projector(r1, r2)))))));
}
// Wrap F# Control library functions in simpler facade
public static FSharpAsync<R[]> Parallel<R>(IEnumerable<FSharpAsync<R>> computations)
{
return Microsoft.FSharp.Control.FSharpAsync.Parallel<R>(computations);
}
public static R Run<R>(FSharpAsync<R> computation)
{
return Microsoft.FSharp.Control.FSharpAsync.RunSynchronously(computation,
}
public static FSharpAsync<R> FromBeginEnd<R>(Func<AsyncCallback, object, IAsyncResult> begin, Func<IAsyncResult, R> end)
{
return FSharpAsync.FromBeginEnd(begin.ToTupledFSharpFunc(), end.ToFSharpFunc(), null);
}
public static FSharpAsync<Unit> FromBeginEnd(Func<AsyncCallback, object, IAsyncResult> begin, Action<IAsyncResult> end)
{
return FSharpAsync.FromBeginEnd(begin.ToTupledFSharpFunc(), FuncConvert.ToFSharpFunc<IAsyncResult,Unit>(iar => { end(iar); return (Unit)null; }), null);
}
public static FSharpAsync<R> FromBeginEnd<Arg, R>(Arg a, Func<Arg, AsyncCallback, object, IAsyncResult> begin, Func<IAsyncResult, R> end)
{
return FSharpAsync.FromBeginEnd(a, begin.ToTupledFSharpFunc(), end.ToFSharpFunc(), null);
}
// convenience object to get in the Async monad
public static FSharpAsync<int> StartWorkflow = async.Return(0);
}```

## “An Introduction to Async Workflows in F#”, or “how to utilize all those CPUs without writing lots of threading code”, part two

Posted by Brian on May 5, 2008

Last time I showed a short example of a CPU-intensive task and demonstrated how to speed up the program by utilizing multiple CPUs.  The .NET ThreadPool APIs got the job done, but it was non-trivial to change our program to use these APIs.  Specifically, we had to change a portion of the original program from this:

let primeInfo = nums
|> Array.map (fun x -> (x,IsPrime x))

to this:

let mutable numRemainingComputations = nums.Length
let mre = new ManualResetEvent(false)
let primeInfo = Array.create nums.Length (0,false)
nums
|> Array.iteri (fun i x -> ignore (ThreadPool.QueueUserWorkItem(fun o ->
primeInfo.[i] <- (x, IsPrime x)
// if we’re the last one, signal that we’re done
if Interlocked.Decrement(&numRemainingComputations) = 0 then
mre.Set() |> ignore)))
// wait until all done
mre.WaitOne()

Yuck.  Today we’ll see how an F# library can accomplish the same goal much more simply.

### A better way – the F# Control library

There is a better way to use our CPUs, using the F# Control library.  In particular, we’ll use the Async<‘a> class type along with a couple of its static methods, as well as the F# async workflow syntax (which is just a specific instance of the general syntax for F# computation expressions).  Each little piece (which I’ve called out in bold in the paragraphs that follow) is small and easy to understand, and as we’ll see, the F# type system and type inference make it easy to ensure that we glue the pieces together correctly.

The Async<‘a> class is a data type for representing an asynchronous computation that will result in a value of type ‘a.  So, for example, an Async<int> object represents a computation that will produce an integer result.

In order to turn a computation into a result, we use the Async.RunSynchronously method.  It’s signature is

// Async.RunSynchronously : Async<‘a> -> ‘a

That is, you pass an async computation to this method, and it runs the computation and returns the result.  Simple enough?  (In point of fact, the Async.RunSynchronously method has other extra optional parameters, but we don’t need them for our example, and so I won’t distract you with those details.)

So, now we know about a data type to represent asynchronous computations, and we have a way to run a computation, but how do we actually create an async computation in the first place?  There are three common waysFirst, we might make a call to a library function that returns an async computation.  For example, if we have a Stream object, we may call

// asyncBytes : Async<byte[]>

AsyncRead() is an extension method on the System.IO.Stream class (from Microsoft.FSharp.Control.CommonExtensions).  The F# Control library contains a number of such extension methods for common operations that you may want to execute asynchronously (like disk IO and networking operations).  Second, we can create our own async versions of methods out of "Begin" and "End" methods by using the Async.FromBeginEnd static method.  An example explains things well.  Consider the WebRequest class in the System.Net library. It has BeginGetResponse and EndGetResponse methods for doing standard .NET-style async programming.  The F# Control library defines this extension method:

type System.Net.WebRequest with
// AsyncGetResponse : unit -> Async<WebResponse>
member x.AsyncGetResponse()
Async.FromBeginEnd(x.BeginGetResponse, x.EndGetResponse)

So with that defined, we can call "webRequest.AsyncGetResponse()" and the result is an Async<WebResponse> object that can be used in an F# async workflow computation.  Third, we can write code using the async workflow syntax using "async" followed by some code in curly braces, yielding a block of code that resolves to an Async value.  We’ll see an example of that shortly.

Finally, once we have a bunch of async computations we want to run in parallel, we can call Async.Parallel

// Async.Parallel : #seq<Async<‘a>> -> Async<array<‘a>>

Recall that seq<‘a> is just shorthand for IEnumerable<‘a> (a "sequence").  So you pass a sequence of computations to Async.Parallel, and it returns you a single computation that will yield and array of all the results.  The library will take care of scheduling each computation on the thread pool and doing the synchronization so as to block until all of the results are ready.

### Applying the F# Control library to our problem

Now that we have an overview of the library, let’s apply it to our prime-computing program.  I’ll once again rewrite the original code between the ResetStopWatch() and ShowTime() calls:

ResetStopWatch()
// info : array<Async<int * bool>>
let info = nums |> Array.map (fun x -> async { return (x, IsPrime x) } )
// par : Async<array<int * bool>>
let par = Async.Parallel info
// primeInfo : array<int * bool>
let primeInfo = Async.RunSynchronously par
ShowTime()

I’ve broken the code down into three steps so as to comment on the data type at each step.  First, we map the input array over an async workflow (an example of a computation expression) that computes an Async tuple.  (I’m not going to describe the "computation expression" syntax – the stuff with "async" and curly braces and "return" – in any detail here, as it deserves its own blog entry.  The curious reader can check out Don’s blog about computation expressions.  Briefly, this is F#’s general syntax for monadic comprehensions – you can think of it like "LINQ notation on steroids".)  The result is an array of async tuples.  Next, we call Async.Parallel on that array, yielding a single async computation which will yield an array of all the tuples when it is run.  Finally, we call Async.RunSynchronously to run this giant parallel computation and get back the desired output array of tuples.  The type system steers you in the right direction the entire time – if the types all work out, then you have glued the pieces together correctly.

I would actually write this code more idiomatically like this:

let primeInfo = nums
|> Array.map (fun x -> async { return (x, IsPrime x) } )
|> Async.Parallel
|> Async.RunSynchronously

That is, we take the input array, map it into an array of async computations that will yield tuples, parallelize all those computations, and then run it.  That’s it!  No queuing up work on the thread pool, no synchronizing mutable data, no blocking on an event to wait for the results to finish – the library does all that for us.  We just describe the essence of the computation (I have all these computations, run them in parallel, go!) and the library does the rest.  Now that is simple.

I wrote this, ran it, and it worked the first time.  100% CPU utilization, and the program finishes in just over 3 seconds.  Huzzah!

Compared to the original program, the only difference is we changed this:

let primeInfo = nums
|> Array.map (fun x -> (x,IsPrime x))

to this:

let primeInfo = nums
|> Array.map (fun x -> async { return (x, IsPrime x) } )
|> Async.Parallel
|> Async.RunSynchronously

That’s it!  That’s a trivial three-line change, and now our program runs four times faster.  And it worked the first time.

If you want to learn more about the F# Control library and async workflows, you should check out Don’s initial blog on async workflows, or Robert Pickering’s 4-part series on asynchronous programming in F# (part 1, part 2, part 3, part 4).  The code is slightly out of date (as some of the F# library namespaces & function names have changed slightly since the blogs were written), but these blogs are nevertheless a good place to read more about the F# Control library.

### Using the F# Control library from C#

F# definitely makes it much easier to write simple and correct async code that takes full advantage of your CPU resources.  Since a lot of the "work" is done by an F# library, you might ask: "Can I consume the F# Control library from C#?"  Great question!  We’ll find out how to utilize some of these great F# ideas from C# code… next time.

### Source code

Here’s the full F# code from today.

module AsyncControl =
open System
open System.Diagnostics

let stopWatch = new Stopwatch()
let ResetStopWatch() = stopWatch.Reset(); stopWatch.Start()
let ShowTime() = printfn "took %d ms" stopWatch.ElapsedMilliseconds

let IsPrime x =
let mutable i = 2
let mutable foundFactor = false
if x % i = 0 then
foundFactor <- true
i <- i + 1

let nums = [| for i in 10000000..10004000 -> i |]

ResetStopWatch()
let primeInfo = nums
|> Array.map (fun x -> async { return (x, IsPrime x) } )
|> Async.Parallel
|> Async.RunSynchronously
ShowTime()
primeInfo
|> Array.filter (fun (x,b) -> b)
|> Array.iter (fun (x,b) -> printf "%d," x)
printfn ""

printfn "press a key"

## “An Introduction to Async Workflows in F#”, or “how to utilize all those CPUs without writing lots of threading code”, part one

Posted by Brian on May 4, 2008

If I told you that I could make your program run four times faster, and all you had to do was make trivial changes to three lines of code, would you be interested?  If so, then read on.  :)

### The current tragedy of multi-core boxes

It’s often the case that you have to write a program that processes lots of data.  Here’s a quick real-world example: a friend of mine was recently writing some test automation for Intellisense, where the product parses a huge source code file and the test verifies that if you press "." at the end of the file you get the right Intellisense completion list.  Or something.  I don’t recall all the details, but they’re not important to our story.  What is important are two facts: first, the product being tested takes a couple seconds to parse the huge file, and second, there are about 100,000 variations to test.  And so at the end of the day, it was taking about 60 hours to complete that entire test run on a fast lab machine.  60 hours!  Bummer.

What’s even more of a bummer is that, if you fire up Task Manager on the lab machine while it’s running the tests, you’ll see that only 25% of the CPU is being used.  Why?  Because the machine has 4 CPUs, but the test was single-threaded, and so only one CPU was in use with the rest just sitting idle.  This has probably happened to all of us.  Nowadays, most new desktop machines are multi-core (my main development box at work is also a quad-core, for instance) and so every developer eventually has that awful experience of sitting at your desk waiting for some program you just wrote to run, and it’s taking forever (anything more than 10 seconds seems like forever),  and, what’s worse, you can see that it’s only using 25% of the CPU because the little program you just coded up is single-threaded.  Ugh, I hate that feeling.

So why don’t we always write code that uses threads, so as to utilize all the horsepower we have sitting on our desktops?  Because threads are complicated – you have to carefully synchronize data, maybe using locks or the Interlocked class, signal, wait, use weird ThreadPool APIs… it’s just too easy to screw up, and wind up with race conditions or other kinds of erroneous programs.

Which is too bad, because it would be handy to speed up programs by a factor of 4 on a 4-CPU box.  A test that runs in 60 hours takes the wind out of my sails – I have to wait days for the results.  But if it runs in 15 hours, I can start it before I leave the office this afternoon, and have the results by the time I return to the office tomorrow morning.  That’s a huge difference.

In this series of blog posts, I want to introduce you to an awesome F# library that enables you to write multi-threaded code so that it’s just too easy to get the code exactly right, the very first time.  :)

### A simple problem

If we want to demo this mysterious F# library, we need a sample problem to solve.  So let’s write a program to determine if various large numbers are prime.  Specifically, for each number between 10,000,000 and 10,004,000, I want to know if the number is prime or not.  The output of my program is an array of 4000 int-bool pairs – the int is the number in question, and the bool says whether than number is prime or not.

Yes, this is a very contrived problem.  Nevertheless, is it representative of any real-world problem where you’ve got a big array of input data where you need to run some computation on each piece of data.  For easy blog-exposition, I want to keep the particular computation task (computing primes) very simple, and as for the peculiar numbers I chose (why "ten million four thousand"?), well, you’ll see why I chose them shortly.

Anyway, this is a simple task, and so it can be solved with a simple program.  Here’s an F# program I wrote that computes my array of int-bool pairs.  It also measures how long it takes to compute this array, and, just for kicks, it prints out the prime number results.  It’s less than 30 lines of code – read it over:

open System
open System.Diagnostics

let stopWatch = new Stopwatch()
let ResetStopWatch() = stopWatch.Reset(); stopWatch.Start()
let ShowTime() = printfn "took %d ms" stopWatch.ElapsedMilliseconds

// IsPrime : int -> bool
let IsPrime x =
// extremely naive approach – good because we want it to be slow
let mutable i = 2
let mutable foundFactor = false
if x % i = 0 then
foundFactor <- true
i <- i + 1

let nums = [| for i in 10000000..10004000 -> i |]

ResetStopWatch()
// primeInfo = array<int * bool>
let primeInfo = nums
|> Array.map (fun x -> (x,IsPrime x))
ShowTime()
primeInfo
|> Array.filter (fun (x,b) -> b)
|> Array.iter (fun (x,b) -> printf "%d," x)
printfn ""

There are 4 main parts.  I use the Stopwatch class in System.Diagnostics to measure how long it takes to compute the prime-ness of the array of numbers.  I wrote an extremely naive "IsPrime" function to test if a number is prime.  (It’s slow, which bodes well for my storytelling example, as we’ll see in a moment.)  Then I compute the results I want ("primeInfo") by using Array.map to turn each number into a int*bool 2-tuple – the number itself, and a boolean of whether it’s prime.  (This is the major computation, and thus this step is the only portion being timed by the stopwatch.)  Finally I print the primes, by filtering out just those tuples whose boolean value is true and printing the corresponding numbers.

When I run this program (unoptimized, inside the VS debugger) on my box at work – tragedy!  It takes forever (about 12.5 seconds), and the CPU is pegged at 25% the whole time.  But at least now you know why I picked those numbers (ten million to ten million four thousand) – I did some quick trial-and-error ranges until I found a range where the program would take more than 10 seconds (a.k.a "forever").  :)  So let’s try to speed it up by bringing our idle CPUs to the party.

This program is just begging to be run with multiple threads.  We have an array of 4000 inputs and we run some computation on each individual input to yield an array of 4000 outputs.  If we had 4000 CPUs, we could run the whole thing in parallel in an instant.  Alas, my box only has 4 CPUs, but I would still love to speed this up by a factor of four.  But how?

As a result, a better strategy is to queue up each element of the array as a separate piece of work, and whenever there is a free CPU, have it grab the next element to process.  The .NET thread pool, specifically the QueueUserWorkItem method, makes this relatively straightforward to do.  Using this strategy, there are no worries that CPUs will sit idle while there are still unprocessed array elements.

### Coding against the thread pool APIs

Let’s look at some code that uses the thread pool APIs directly to utilize all our CPUs.  It is rather tricky to get right.  The only portion of the original program that changes is the bit between the ResetStopWatch() and ShowTime() calls, so that’s all I’m showing here (the rest of the program remains unchanged):

ResetStopWatch()
// we need to "join" at the end to know when we’re done, and these will help do that
let mutable numRemainingComputations = nums.Length
let mre = new ManualResetEvent(false)
// primeInfo = array<int * bool>
let primeInfo = Array.create nums.Length (0,false)
nums
|> Array.iteri (fun i x -> ignore (ThreadPool.QueueUserWorkItem(fun o ->
primeInfo.[i] <- (x, IsPrime x)
// if we’re the last one, signal that we’re done
if Interlocked.Decrement(&numRemainingComputations) = 0 then
mre.Set() |> ignore)))
// wait until all done
mre.WaitOne()
ShowTime()

The tricky bit is that after we queue up all the work, we need a way to find out when it’s all done.  So here I’ve created a mutable variable "numRemainingComputations" that "counts down" how many array elements of work we have left.  I also need a ManualResetEvent that I can "wait" on (when the final piece of work finishes, it will "signal" the event).  Each bit of work that I queue up will

• Do the actual work for this one array element (compute the int*bool tuple and stuff it in the output array "primeInfo")
• Decrement the numRemainingComputations counter (using Interlocked.Decrement, so I don’t need an explicit lock for this shared mutable data)
• If it just completed the final computation, signal that we are all done (by calling mre.Set())

The "ignore" calls just throw away useless booleans (both QueueUserWorkItem() and Set() returns boolean results that I don’t care about).

Sigh.  Well, the code works.  When I run it on my box, the CPU utilization goes to 100% and the program finishes in just over 3 seconds.  So we accomplished the goal of using our CPUs to make things run 4 times faster.  But…

That code is a mess.  It doesn’t make happy to read it or write it.  I originally wrote it in C# (see code at the end of this blog entry) and I made two different tragic errors along the way.  There are too many little details to keep track of and get right.  Surely there is a better way!

### A better way – the F# Control library

There is a better way, using the F# Control library.  We’ll see how to apply it to this problem… in the next blog entry.

### Source code

Here’s the code when I tried it in C#, both with and without multi-threading:

using System;
using System.Diagnostics;
using System.Collections.Generic;
using System.Linq;

class Program
{
static Stopwatch stopWatch = new Stopwatch();
static void ResetStopWatch() { stopWatch.Reset(); stopWatch.Start(); }
static void ShowTime() { Console.WriteLine("took {0} ms", stopWatch.ElapsedMilliseconds); }

static bool IsPrime(int x)
{
for (int i = 2; i < x; ++i)
{
if (x % i == 0)
return false;
}
return true;
}
static void Main(string[] args)
{
var nums = new int;
for (int i = 0; i < nums.Length; ++i)
nums[i] = 10000000 + i;
ResetStopWatch();
var primeInfo = new KeyValuePair<int, bool>[nums.Length];
// we need to "join" at the end to know when to stop, and these will help do that
int numRemainingComputations = nums.Length;
ManualResetEvent mre = new ManualResetEvent(false);
#endif
for (int i = 0; i < nums.Length; ++i)
{
// be sure to use a local variable inside the loop, else you’ll capture the mutable variable
// "i" inside the lambda and go nuts and get an ArrayIndexOutOfBoundsException
int j = i;
{
primeInfo[j] = new KeyValuePair<int, bool>(nums[j], IsPrime(nums[j]));
// if we’re the last one, signal that we’re done
if (Interlocked.Decrement(ref numRemainingComputations) == 0)
mre.Set();
}
);
#else
primeInfo[i] = new KeyValuePair<int, bool>(nums[i], IsPrime(nums[i]));
#endif
}
ShowTime();
// wait until all done
mre.WaitOne();
#endif
var primes = from x in primeInfo
where x.Value
select x.Key;
foreach (var x in primes)
Console.Write("{0},", x);
Console.WriteLine();
ShowTime();
Console.WriteLine("press a key");
}
}

And now here’s the code in F# – first single-threaded, then multi-threaded using the .NET threading APIs.

module Original =
open System
open System.Diagnostics

let stopWatch = new Stopwatch()
let ResetStopWatch() = stopWatch.Reset(); stopWatch.Start()
let ShowTime() = printfn "took %d ms" stopWatch.ElapsedMilliseconds

// IsPrime : int -> bool
let IsPrime x =
// extremely naive approach – good because we want it to be slow
let mutable i = 2
let mutable foundFactor = false
if x % i = 0 then
foundFactor <- true
i <- i + 1

let nums = [| for i in 10000000..10004000 -> i |]

ResetStopWatch()
// primeInfo = array<int * bool>
let primeInfo = nums
|> Array.map (fun x -> (x,IsPrime x))
ShowTime()
primeInfo
|> Array.filter (fun (x,b) -> b)
|> Array.iter (fun (x,b) -> printf "%d," x)
printfn ""

printfn "press a key"

open System
open System.Diagnostics

let stopWatch = new Stopwatch()
let ResetStopWatch() = stopWatch.Reset(); stopWatch.Start()
let ShowTime() = printfn "took %d ms" stopWatch.ElapsedMilliseconds

let IsPrime x =
let mutable i = 2
let mutable foundFactor = false
if x % i = 0 then
foundFactor <- true
i <- i + 1

let nums = [| for i in 10000000..10004000 -> i |]

ResetStopWatch()
// we need to "join" at the end to know when to stop, and these will help do that
let mutable numRemainingComputations = nums.Length
let mre = new ManualResetEvent(false)
let primeInfo = Array.create nums.Length (0,false)
nums
|> Array.iteri (fun i x -> ignore (ThreadPool.QueueUserWorkItem(fun o ->
primeInfo.[i] <- (x, IsPrime x)
// if we’re the last one, signal that we’re done
if Interlocked.Decrement(&numRemainingComputations) = 0 then
mre.Set() |> ignore)))
// wait until all done
mre.WaitOne()
ShowTime()
primeInfo
|> Array.filter (fun (x,b) -> b)
|> Array.iter (fun (x,b) -> printf "%d," x)
printfn ""

printfn "press a key"

## New F# users: some tips to help you become productive more quickly

Posted by Brian on May 3, 2008

(Quick note: we just had a new release – check it out!)

I have written a lot of blog entries about some of the coolest features and nicest aspects of programming with F#.  F# is pretty new to most people, though, and when learning a new programming language, there are bound to be some frustrating moments along the way as you learn the new syntax and reorganize some of your mental models for structuring code.  The F# team is always looking for ways to reduce the initial learning curve, so today I’ll mention a few issues that new users commonly encounter, and I’ll describe some useful things to know "up front" that will make it easier to ramp up on F#.

So without further ado, here are a handful of tips that will make it easier for you to hit the ground running with F#.

### The "tab" character is illegal in #light code

Almost all the F# code in the world you will find uses the lightweight syntax option – using the "#light" directive at the top of the file (which will probably become the default in a future release).  When using #light, layout matters (whitespace is significant), and the "tab" character is illegal.  Thus many users exploring F# in Visual Studio for the first time will try to define their first function, press ‘tab’ to indent the body, and all of a sudden there are error squiggles highlighting the whitespace just typed.  Yikes!  (EDIT: (Jan 2010) #light is now the default; you can quit putting #light at the top of your files.)

Fortunately, the solution is simple: in Visual Studio, go to "Tools\Options\Text Editor\F#\Tabs" and select "Insert spaces".  Do this once, and you’re forever good to go.  Others have blogged about this before, check the link for a screenshot.  (If you’re using an editor other than Visual Studio, make the corresponding change to convert tabs to spaces when editing F# source files in your editor-of-choice.)  (EDIT: (Jan 2010) Whether you have the CTP or VS2010, the defaults are now set up properly, you do not have to customize anything here to make it work.)

### There is a distinction between tupled functions versus curried functions

People new to F# need to learn about the two different ways that functions can be called.  I have talked about the difference between using tuples and using currying before.  Consider:

// fc : int -> int -> int
let fc x y   = x + y    // curried
// ft : int * int -> int
let ft(x, y) = x + y    // tupled

Since functions can be written in both styles, it’s important to call each function with the right syntax, e.g.:

fc 3 4
ft(3,4)

If you mix a curried function with a tupled call site, or vice-versa, you’ll end up with an error message like one of these:

fc(3,4)  // This expression has type ‘a * ‘b but is here used with type int
ft 3 4   // This value is not a function and cannot be applied

Though you don’t have to understand terms like "currying", "partial application", and "higher-order functions" to get started using F#, you do at least have to be aware of the curried-versus-tupled distinction in order to author programs that will typecheck.  Tupled functions have types where arguments are separated by "*", and they are defined and called with tuple syntax (parentheses and commas).  Curried functions have types where arguments are separated by "->", and they are defined and called using just whitespace to separate the arguments.  You must learn this distinction in order to survive your first week of programming in F#.  The good news is, if you’ve read this far in today’s blog, you already know enough that you’re likely to never again get blocked by the "curried/tupled" distinction.

### Don’t panic about various syntax errors for simple code

Another common experience for people writing F# code for the first time is getting tripped up by the interactive feedback Visual Studio provides while you are typing.  Suppose you intend to write a simple function like this:

let circumference r =
let pi = 3.14
let d = 2.0 * r
pi * d

That’s perfectly legal F# code.  However, while you are typing, you’ll get to points like

let circumference r =
let pi = 3.14
let d = 2.0 * r
// cursor here, haven’t finished typing yet

where you haven’t finished typing yet, and you might get surprised and hung up by error squiggles under the last "let" with messages like "syntax error" or "error in the return expression for this ‘let’".  What’s going on here?

The lightweight syntax option makes it easy to forget that these "let"s inside the body of the function are not statements, rather they are the beginning of an expression.  (F#, like most functional languages, emphasizes expressions rather than statements.)  The F# grammar rule for a let expression looks something like "let ident = expr in body-expr".  The key part is the "in body-expr" at the end.  A let expression must have a body!  Since the lightweight syntax allows us to omit the "in", the necessity of a body is especially easy to forget.  If I make the original code very, very explicit:

let circumference r =
begin  // don’t write code like this; just emphasizing how it parses
let pi = 3.14 in
begin
let d = 2.0 * r in
begin
pi * d
end
end
end

then the error makes more sense when you realize that, in the original function, if you haven’t typed the last line of code yet, it’s equivalent to

let circumference r =
begin  // don’t write code like this; just emphasizing how it parses
let pi = 3.14 in
begin
let d = 2.0 * r in
// cursor here, haven’t finished typing yet
end
end

Now the error message "error in the return expression for this let" (pointing at the "let" in "let d=…") makes more sense – the let expression at the cursor has no body!

The solution here is just to be aware of this aspect of the language and how it interacts with the tooling.  The F# language service in Visual Studio does more "online" parsing, typechecking, and semantic analysis than C#.  Whereas in C# you typically need to explicitly "build" in order to get typechecking errors, in F#, the language service continually running in the background is re-parsing and typechecking as you type, so as to provide interactive feedback (which is especially useful for type-inference).  However as a consequence of this, some of the error reporting and squiggles are a little "over-eager" when it comes to code you’re still in the middle of editing.  Though we’ll continue to improve the F# interactive editing experience inside Visual Studio, it is important to be aware of this aspect and not let it throw you for a loop.  (On a related note, we also have a bit of work ahead of us to improve the quality of the compiler error diagnostics.  A "syntax error" may tell you where the problem is, but it does not help you get un-stuck if you don’t know the correct syntax!)

### Summary

I’ve discussed a few simple issues that nearly every new F# programmer faces during their first week using the language.  Each issue is simple to get past, once and for all – provided you have the right little bit of understanding or tooling!  Don’t let little issues like these prevent you from learning, using, and enjoying the language.  If you find yourself getting stuck, let us know – the F# team would love to hear your feedback – both positive and negative.  What aspects of F# do you enjoy most?  Are there parts you find confusing or frustrating?  Do you have feedback about the F# language, libraries, tooling, or setup?  Just send us mail telling us about your experience!

The best time to send feedback is now!  F# is a real language you can use today, so go download the latest release and try it out!  As we transition from releasing F# out of Microsoft Research to releasing F# out of Microsoft Developer Division (another milestone on the long drive towards making F# a first-class language on the .NET platform), we’ll be tying down the remaining loose ends and driving the core language and libraries to stabilization.  Which is why now is the best time for user feedback; the suggestions you provide today could have a marked impact on the experience found on thousands of developer desktops just a few years down the road.  Let us know what you think of F#!

Posted in Uncategorized | 4 Comments »