Planet F#

F# Discoveries This Week 11/09/2009

Mon, 09 Nov 2009 08:24:59 GMT

As momentum builds for the F# release with Visual Studio 2010, so too does the number of people blogging about the language. This week we have a spec update, clarified comparisons, decision trees, porting gotchas and in depth explorations of the debug IL generated by F#. Please do enjoy.

Speaking on F# at the Connecticut .NET Developer’s Group

Tomorrow (Tuesday November 10th, 2009) I’ll be speaking on F# at the Connecticut .NET Developer’s group. For more information check out the ClickToAttend event.

From Don Syme’s Blog - F# Spec Updated for the 1.9.7 Release

Many thanks to all those who sent so much helpful feedback on the specification during Beta1. And for those using 1.9.7 already, thanks for your patience in the last couple of weeks - it took us a little longer to get this out the door than we had planned, since a development deadline for Visual Studio 2010 intervened.

Don Syme’s Equality and Comparison Constraints in F#

F# 1.9.7 introduces two new constraints to the F# language to help uncover issues in your code when using equality and comparison operators. In this blog entry we'll take a look at these constraints in a bit more detail.

The F# team has inherited quite a mess in terms of the lack of any kind of concrete definition of equality in the .NET framework. It seems that they’ve been able to do much with it though.

Chris Smith’s Decision Trees Part 1 and Part 2

Now that we got all that painful math out of the way, let’s write some code! Here is an implementation of the algorithm in F#.

I’m just dying to see this extended to Bayesian network. Perhaps I’ll try and extend it myself.

Bart De Smet’s Stack-Friendly Recursion

Recursion is a widely known technique to decompose a problem in smaller “instances” of the same problem. For example, performing tree operations (e.g. in the context of data structures, user interfaces, hierarchical stores, XML, etc) can be expressed in terms of a navigation strategy over the tree where one performs the same operation to subtrees.

A detailed look at tail recursion optimization in F# and how to achieve something similar in C#.

On StackOverflow, is a program F# any more efficient (execution-wise) than C#?

I'm guessing that it is not because they both boil down to the same IL.

It turns out that F# is in fact much faster in some cases. For more on F# performance see this roundup post.

Steve Gilham’s F# under the covers parts 1, 2, 3, 4, 5, 6, and 8

I'm in the tidying up stages for the little project I've been working on lately, a set of FxCop rules, mainly aimed at providing some complementary features for nCover-style code coverage, including static analysis for trivial methods -- or compiler generated ones.

In this series Steve takes a very careful approach to exploring the IL generated by the F# compiler in debug mode.

Matt Moloney’s Lessons Learned in Porting [from] C# to F# (WPF)

I encountered a ton of difficulties while porting code from C# to F#. Fortunately / unfortunately, so have many other people. Thankfully they took the time to write about these problems so my solutions were often only a quick search away. Here is a collection of some of the finds that were able to help me in my endeavors.

An excellent post well worth reading for anyone getting ready to port to F#.

Lessons learned in porting C# to F# (WPF)

Sun, 08 Nov 2009 23:29:57 GMT

I encountered a ton of difficulties while porting code from C# to F#. Fortunately / unfortunately, so have many other people. Thankfully they took the time to write about these problems so my solutions were often only a quick search away. Here is a collection of some of the finds that were able to help me in my endeavors.

I have done my best to attribute sources, and as always feedback is very much appreciated. Also, I will be updating my code viewer as soon as possible to stop it from embedding html smiley faces.

1. Data Templates

Unfortunately the only way to build Data Templates in code is being deprecated, which means we have to resort to writing Data Templates in XAML as a string. This string is then loaded using XamlReader as per the following code.

let loadFromString xaml = use sr = new StringReader(xaml) use xr = XmlReader.Create(sr) XamlReader.Load xr

Steve Horsfeild has a good write up on this here

2. Attached Dependency Properties

For ages I tried to figure out why my attached properties were not showing up in the XAML intellisense. It turns out that I was missing the Get and Set functions for the property, as per below;

 static let useHoverProperty = DependencyProperty.RegisterAttached( "UseHover", typeof<bool>, typeof<HoverInteractor>) static member public SetUseHover(d:DependencyObject, _use:bool) = d.SetValue(useHoverProperty, _use) static member public GetUseHover(d:DependencyObject) = d.GetValue(useHoverProperty)  > bool

3. Using options instead of Null

I use this when a attribute is begin set at runtime and I know that no function will call the attribute until after it has been set. (from here)

“Nullable” member

 static let mutable draggedElt = None static member private DraggedElt with get() = match draggedElt with | Some(v) -> v | _ -> failwith "initialization fail" and set(x:UIElement) = draggedElt <- Some(x)

Check for “null”:

match scrollOwner with
| Some(v) -> v.InvalidateScrollInfo()
| None -> ()

From here

4. Removing event handlers

let rec eventHandler = EventHandler(fun o e -> // Hide the Viewport this.viewport.Visibility <- Visibility.Hidden Panel.SetZIndex(this.backChildContainer, 0) // Show the FrontChild this.frontChildContainer.Visibility <- Visibility.Visible dockAnim.Completed.RemoveHandler(eventHandler) )

However, sometimes you can’t keep a reference to the delegate instance. Fortunately you don’t have to. The following code works as the object passed into Remove() must match the associated signature, but not necessarily the actual delegate instance you wish to remove. (Apress: Pro C# 2008 and the .Net 3.5 Platform)

 override this.StartListening(source:obj) = let evtSource = source  > DataSource evtSource.DataChanged.AddHandler(Handler<EventArgs>(this.PrivateOnDataChanged)) override this.StopListening(source:obj) = let evtSource = source  > DataSource evtSource.DataChanged.RemoveHandler(Handler<EventArgs>(this.PrivateOnDataChanged))

4. Property changed events

This is pretty straight forward (from here)

let propertyChanged = Event<_,_>()
let notify obj s = propertyChanged.Trigger(obj, PropertyChangedEventArgs(s)) interface INotifyPropertyChanged with [<CLIEvent>] member this.PropertyChanged = propertyChanged.Publish

6. Runtime casting:

The following is the equivilent for using as (C# keyword), and then checking for Null. (from here)

 match b1 with |  Derived1 as derived1 -> derived1.F() | _ -> ()

Other bits and pieces;

Accessing members in interfaces. It is a little odd but you have to cast the object to the interface type before you can call on the interface member: “(mark :> CouchDBDocument).DocType” (from here)

Pass ‘by ref’ into a function can be done by using the prefix ‘&” operator on a mutable (from here)

let mutable x = 1
if d.TryGetValue("foo", &amp;x) then...

PropertyPath wouldn’t work with a string, it requires the actual property “PropertyPath(UIElement.OpacityProperty)” (from here)

Motivating F# equality and comparison constraints

Sun, 08 Nov 2009 15:30:30 GMT

(I will return to the RSS Dashboard series soon; I needed to do this aside now to be timely.)

Don has just posted a great blog entry describing the details of the equality and comparison constraints in the latest release of F#. I would like to take a moment to describe the higher-level view to motivate the feature. By reading this blog entry, the reader should learn

what structural equality and comparison are
what is the problem that F# equality/comparison constraints solve
why this problem cannot be solved without a specific language feature
when does a programmer need to care about this

If you want to know the details of the F# language feature and how to exercise fine control and specification of equality/comparison on your user-defined types, then you should go read Don’s post. On the other hand, if you want an overview and more examples about the ‘why’, hopefully this blog entry will give you what you need. Some readers might find this blog entry is a useful ‘prequel’ to Don’s.

So let’s get started!

What are structural equality and comparison?

Consider this short code example:

let il1 : int list = [ 1; 2; 3 ]
let il2 : int list = [ 2; 3; 1 ]
printfn "%A" (il1 = il2) 
printfn "%A" (il1 < il2)

What would this print? If you said “false” and “true”, then you already have a good sense of structural equality and comparison. But let’s go through it in more detail.

Structural equality means that for F# structural types (e.g. tuples, arrays, lists, options, records, and unions), we can get a default behavior for ‘equals’ that compares each individual element of the structure for equality. That is, one ‘int list’ is equal to another ‘int list’ if both lists have the same length and each of their individual elements are equal. (Contrast this to the default behavior of the .Equals() method of a class type, which defaults to reference equality.) Structural equality is commonly the semantic the author of a type would want anyway, and in F#, you can get semantic “for free” on any structural type. In my experience, most people have a good intuition for what structural equality means and see its utility. (Technical aside: “structural equality” applies to both the .Equals() and the .GetHashCode() methods of a type, as well as the F# (=) operator and “hash” function.)

Structural comparison is analogous to structural equality, except that it applies to the comparison operators (<, <=, >, >=, whose behavior involves calls to System.IComparable.CompareTo()). For some people, the behavior here is less intuitive – what does it mean to compare two integer lists with the less-than operator? To explain this, I appeal to a more familiar domain: dictionary order on strings. If I ask you what order the words “bad”, “ace”, “ad”, and “a” appear in the dictionary, I bet you could tell me. Thus you are probably not too surprised by the behavior of this F# code:

let words = [| "bad"; "ace"; "ad"; "a" |]
printfn "%A" (Array.sort words)
// [|"a"; "ace"; "ad"; "bad"|]

Dictionary order, sometimes called lexicographical order, is a useful semantic for structural types. (Aside: you may recall that I relied on structural comparison in a previous blog entry to get an automatic ordering of poker HandValuations.) With the previous code example in mind, I hope it is now less surprising how this F# code behaves:

let intLists = [| [2;1;4]; [1;3;5]; [1;4]; [1] |]
printfn "%A" (Array.sort intLists)
// [|[1]; [1; 3; 5]; [1; 4]; [2; 1; 4]|]

All I did was change from strings, which ‘structurally’ are just lists of characters, to lists of integers (in this example, substituting a=1, b=2, …).

So for example [1;2]<[2;1] because we can compare the first element and immediately see a difference, whereas [1;2]<[1;3] because we compare the first element and they are equal, so we move on to the next element until we find a difference. This same logic applies to other structural types, like tuples: (1,”bbb”)<(2,”aaa”) and (1,”aaa”)<(1,”bbb”); records: {field1=1;field2=”aaa”}<{field1=1;field2=”bbb”}; etc.

To sum up then, structural equality and comparison define the most natural semantic for operations like (=) and (<) on structural types. In F#, you can get these semantic “for free” by default on structural types. (You can also opt out of these defaults, or choose to define your own equality/comparison behavior; for details see Don’s post.)

Now that we know what “structural equality” and “structural comparison” mean, we can move on to…

What problem do F# equality/comparison constraints solve?

In the previous section, we learned about this behavior for lists of integers:

let il1 : int list = [ 1; 2; 3 ]
let il2 : int list = [ 2; 3; 1 ]
printfn "%A" (il1 = il2) // false
printfn "%A" (il1 < il2) // true

Now consider a couple more cases for lists of various types. What is the ideal behavior of equality/comparison on (Windows Forms) Controls?

open System.Windows.Forms let cl1 : Control list = [ new TextBox(); new Button(); new CheckBox() ]
let cl2 : Control list = [ new Button(); new CheckBox(); new TextBox() ]
printfn "%A" (cl1 = cl2) 
printfn "%A" (cl1 < cl2)

Or how about on F# function types?

let fl1 : (int -> int) list = [ id; (+) 1; (fun x -> 2*x) ]
let fl2 : (int -> int) list = [ (+) 1; (fun x -> 2*x); id ]
printfn "%A" (fl1 = fl2) 
printfn "%A" (fl1 < fl2)

Let’s consider each case in turn. For Controls, there is a useful equality semantic: reference equality. As a scenario example, you might hook up the same “click” event handler to a bunch of buttons, and then inside the handler test “if (sender=button1) then…” Indeed, the behavior of .Equals() on these .Net Framework types is reference equality. So an equality test on a list of Controls should return true if and only if each element of the first list .Equals() the corresponding element of the second list.

What about comparison of Controls with the (<) operator? Here there is nothing reasonable to do. (Is a button less than a textbox? Is this button less than that one?) None of these type implement IComparable. Ideally we want this program not to compile; trying to compare a list of Controls with (<) is nonsense.

How about the function types? Those few humans who have studied the F# spec in detail may recall that the result of calling System.Object.ReferenceEquals() on two F# function types is underspecified (see 6.10.22: Types with Under-specified Object and Type Identity). Trying to compare two “function values” for (=) equality is bad news! Similarly, there is no reasonable “comparison” semantic for (<). So ideally, we would not like either of the function examples to compile.

Happily, F# equality/comparison constraints give us exactly the behavior we want, as suggested by the comments:

let il1 : int list = [ 1; 2; 3 ]
let il2 : int list = [ 2; 3; 1 ]
printfn "%A" (il1 = il2) // false
printfn "%A" (il1 < il2) // true open System.Windows.Forms let cl1 : Control list = [ new TextBox(); new Button(); new CheckBox() ]
let cl2 : Control list = [ new Button(); new CheckBox(); new TextBox() ]
printfn "%A" (cl1 = cl2) // false
printfn "%A" (cl1 < cl2) // does not compile let fl1 : (int -> int) list = [ id; (+) 1; (fun x -> 2*x) ]
let fl2 : (int -> int) list = [ (+) 1; (fun x -> 2*x); id ]
printfn "%A" (fl1 = fl2) // does not compile
printfn "%A" (fl1 < fl2) // does not compile

If the operation is reasonable, the code compiles and gives the expected behavior. If the operation if unreasonable, the code fails to compile and you get a helpful diagnostic from the compiler.

To sum up this section, hopefully I’ve provided a convincing argument that the behaviors described above are the ideal defaults. However this may leave you asking…

Does this really need a language feature?

As you may know, the CLI and languages like C# support a rich variety of ways to constraint class/method signatures so that the static type system can enforce that only sensible combinations of generics/object-hierarchies will typecheck. Surely we could use those existing mechanisms to get the ideal behavior described in the previous section?

It turns out you cannot. (Some readers may wish to take a few minutes to try this themselves – try to author your own ‘list’ type (and possibly (=) and (<) operators) that give the same compile-time and run-time behavior as in the previous code example.) The static type system of the CLI or languages like C# are not powerful enough to express this behavior.

To see why, consider just the comparison (<) aspect for a moment, and the ‘int’ versus ‘Control’ list example. I want to define a type List<T>. When I instantiate it with a comparable type like ‘int’, I want the resulting type “List<int>” to be an IComparable. But when I instantiate with a non-comparable type like ‘Control’ I want the resulting type “List<Control>” to not be an IComparable. This amounts to needing a generic type to be able to conditionally implement an interface, based on the generic argument. And you can’t do that. The nearest things you might try are C# code like

class ListA<T> : IComparable ...

class ListB<T> : IComparable where T : IComparable ...

but neither does what we want. ListA allows lists of Controls, but also allows those lists to be comparable. ListB disallows comparing lists of Controls, but does so by throwing out the baby with the bathwater, you cannot even create a list of Controls with ListB! What you really need is something like this imaginary syntax:

if T : IComparable class List<T> : IComparable {...}
else class List<T> {...}

But this feature does not exist in C# or the CLI.

The design methodology of F# here is to have features in the F# type system that are erased when the code is compiled. The same thing happens with units of measure; units are a feature that exist in the F# type system to enable a very useful kind of static type checking in F#, but this information is erased when compiled down to assemblies referenced by other .Net languages. So for instance, when F# looks at a particular F# assembly, it may see a method that returns “double<kg>”, but when C# looks at the same method, it will just see the return type as “double”. Similarly, F# equality & comparison constraints allow F# code to see what are effectively these ‘conditional interfaces’, whereas C# code would just see these interfaces unconditionally. The result is that the F# type system will catch some kinds of semantic errors at compile-time (like trying to add kilograms to meters, or trying to compare two functions values for equality), whereas the corresponding C# cannot (resulting in various unintended runtime semantics).

Without this feature, F# would have to choose between either (1) disallowing equality and comparison on structural types like lists (meaning e.g. you could not compare two lists for equality), or (2) allowing equality and comparison on all structural types, even when it does not make sense (this is roughly where F# was prior to the release of Beta2). (In fact there are more points in the design space, but this paragraph summarizes the central choice.) These constraints enable equality/comparison only when it makes sense.

To sum up this section: in order to get the desired behavior described in the previous section, we really do need a language feature. For details about the feature itself, see Don’s blog.

Now that you hopefully understand why the feature is necessary, you may say, ok, so…

When do I need to worry about any of this?

The good news is, amazingly, you almost never need to care about any of this. Almost all F# code that compiled and worked before continues to compile and work now the same way. The main difference is that the type system is providing an extra safety net to prevent you from doing meaningless things on certain types (such as trying to compare function values for equality). For the most part you get extra safety for free.

The F# library has constraints mentioned on a few common types (like Set<T>, which requires “T : comparison”) and functions (like Seq.groupBy, which requires “Key : equality” (note: at time of this writing, there’s a doc bug on the groupBy web page that says “unknown constraint”)). So knowing these constraints is occasionally useful when reading documentation, to know for example that Set<T> only works for types T that support (<), and that groupBy can only group on keys that can be tested with (=).

When you write code that uses equality/comparison constraints, it often gets inferred for you on your behalf. Consider this somewhat contrived example that finds the first element in a list ‘l’ that equals a certain value ‘e’:

let rec tryFindFirst e l = match l with | [] -> None | x::xs when x = e -> Some(x) | x::xs -> tryFindFirst e xs

Since (=) is used on the generic element type in the body of the function, the equality constraint is automatically inferred. Thus the behavior of this function for a few different calls is as seen here:

tryFindFirst 3 [1;2;3;4] // Some(3)
tryFindFirst 5 [1;2;3;4] // None
tryFindFirst id [id;fun x -> x+1] // does not compile

Notice that we get the ‘safety check’ for free. Our function only works on lists of elements for which the element types can be compared with (=), and we didn’t have to explicitly specify any constraint, it was automatically inferred.

You will occasionally need to be explicit about equality/comparison constraints, if authoring algorithms with explicit type annotations that depend on these constraints, or authoring generic data types that depend on these constraints in non-obvious ways. For examples, see Don’s blog.

To sum up: so long as you are aware of the existence of the “equality” and “comparison” constraints, and have some basic idea of what they mean (so as to grok them when seen in documentation or F# hover-tooltips in Visual Studio), you’re fine. You don’t need to understand the nitty-gritty details of the language mechanisms unless you are going to author types with ‘custom’ equality/comparison semantics, and those cases are relatively rare.

F# under the covers VIII

Steve — Sun, 08 Nov 2009 14:53:00 GMT

I'm in the tidying up stages for the little project I've been working on lately, a set of FxCop rules, mainly aimed at providing some complementary features for nCover-style code coverage, including static analysis for trivial methods -- or compiler generated ones. I've done the red -- add a set of methods that should give expected static analysis results -- and green -- write the simplest implementation that works when given the code base to analyse as a post-build activity. And now I'm on the refactor leg, abstracting out the common activities, taming sprawling methods into tighter ones, and reducing the level of imperative features (perhaps also making the code more idiomatic), even at times managing to delete whole methods.

And while I'm doing so, I'm running various tools over the code; FxCop and nCover over a small nUnit run every build, of course, but in turns Reflector and NDepend -- the results of which have been the inspiration for this series of posts.

And as we have seen, the code emitted by the F# compiler in its various iterations is unlike that coming from the more traditional .net langauges, in a way that doesn't always play nice with tools developed against C# or VB.net (and perhaps C++/CLI).

NDepend will deserve an essay of its own in due course -- part of the quid pro quo for the copy that Patrick Smacchia has generously donated -- but today's point of interest is that some IL code generated from F# cannot (at least with current Reflector builds) be easily folded back into C# source.

Take this active pattern used to match a property getter method that just returns a backing field with a name related to the property name, which is at a current intermediate stage of refactoring

 let (|SimpleGetter|_|) (fn:Method) = if (not fn.IsAccessor) || (not (fn.Name.ToString() @ "get_")) then None else match MapToTypes fn.Body.Statements with | [NodeType.Block; NodeType.Block] -> match (fn.Body.Statements.[0], fn.Body.Statements.[1], fn) with | CSharpGetterInterior -> Some () | _ -> None | [NodeType.Block] -> match (fn.Body.Statements.[0], fn) with | SimpleGetterInterior -> Some() | _ -> None | _ -> None

where MapToTypes turns an FxCop StatementCollection into a list of their corresponding NodeTypes, and @ wraps String.StartsWith with ordinal comparison.

Confronted with a request to decompile into C#, Reflector 5.1.6.0 asks me to file a bug report (which I have done) for an exception "Invalid branching statement for condition expression with target offset 002A."

Now, as far as I can tell from the IL, this is part of line 2 where it is balking

 L_0000: nop L_0001: ldarg.0 L_0002: call instance bool [Microsoft.Cci]Microsoft.FxCop.Sdk.Method::get_IsAccessor() L_0007: brtrue.s L_000b L_0009: br.s L_000d L_000b: br.s L_0011 L_000d: ldc.i4.1 L_000e: nop L_000f: br.s L_002a L_0011: ldarg.0 L_0012: call instance class [Microsoft.Cci]Microsoft.FxCop.Sdk.Identifier [Microsoft.Cci]Microsoft.FxCop.Sdk.Member::get_Name() L_0017: callvirt instance string [mscorlib]System.Object::ToString() L_001c: ldstr "get_" L_0021: call bool Tinesware.Rules.Assist.Local::op_Append(string, string) L_0026: ldc.i4.0 L_0027: ceq L_0029: nop L_002a: brfalse.s L_002e L_002c: br.s L_0030 L_002e: br.s L_0032 L_0030: ldnull L_0031: ret ...

Presumably -- I would have to build some equivalent C# code to validate -- the brfalse.s is not one that C# (or any of the other languages Reflector knows of) would actually emit. Certainly it seems that the new F# CTP compiler is fond of emitting it, and it breaks Reflector every time it does.

Another good reason for avoiding too many imperative constructs in your F# code, it would seem.

Later: this C# code that approximates the above F#

 public static int? SimpleGetter(System.Reflection.MethodInfo fn) { if (!fn.IsSpecialName || !(fn.Name.StartsWith("get_"))) return null; return fn.Name.Length; }

compiles to

 L_0000: nop L_0001: ldarg.0 L_0002: callvirt instance bool [mscorlib]System.Reflection.MethodBase::get_IsSpecialName() L_0007: brfalse.s L_001b L_0009: ldarg.0 L_000a: callvirt instance string [mscorlib]System.Reflection.MemberInfo::get_Name() L_000f: ldstr "get_" L_0014: callvirt instance bool [mscorlib]System.String::StartsWith(string) L_0019: br.s L_001c L_001b: ldc.i4.0 L_001c: stloc.1 L_001d: ldloc.1 L_001e: brtrue.s L_002c L_0020: ldloca.s CS$0$0002 L_0022: initobj [mscorlib]System.Nullable`1 L_0028: ldloc.2 L_0029: stloc.0 L_002a: br.s L_003f L_002c: ldarg.0 L_002d: callvirt instance string [mscorlib]System.Reflection.MemberInfo::get_Name() L_0032: callvirt instance int32 [mscorlib]System.String::get_Length() L_0037: newobj instance void [mscorlib]System.Nullable`1 ::.ctor(!0) L_003c: stloc.0 L_003d: br.s L_003f L_003f: ldloc.0 L_0040: ret

which indeed, as I suspected, uses a brtrue.s for the final branch out of the if statement (though there is a brfalse.s to perform the short-circuiting.

Technical analysis indicators in F# – Part II

Sun, 08 Nov 2009 14:10:14 GMT

This is the second part of a series of technical analysis indicators in F#. We define some internal helper functions, and some basic indicators (math and statistics-related, moving averages etc.) Quick disclaimer : many of these indicators are not verified. And the code may very well be slower than in TA-Lib. The point was only to see [...]

A Great Blog Series on Algorithmic Programming in F#

dsyme — Sun, 08 Nov 2009 10:19:00 GMT

I've just discovered Julien's amazingblog series on algorithmic programming in F#. This is a fantastic resource! And if that doesn't whet your appetite, he also has a series on food :-)

Here are some of his recent posts:

Technical analysis indicators in F#

This is the first part of a series on technical analysis indicators in F#. We will define the basic object holding the data series which will be used to compute the indicators. We will also describe some functions to check the integrity of the said data (and which will be useful when defining the indicators).

An immutable range library in F#

An immutable range library in F# where a range is only defined by a minimum and a maximum value (hence, there is no step).

An immutable queue in F#

An immutable queue library in F#. The queue is divided into two lists : one for dequeueing, and one for enqueueing. All operations are based on the List module.

A bitset library in F#

ReadWrite Requests for groups of files

In this post, we shall use read/write requests from a group of files considered as a single entity. We will also look at verifying the data. In our model, the group of files is defined by the files, and pieces. A piece is a chunk of data with a standardized size so that read/write requests are consistent. Of course, the last piece of the files stream could see its size differ from others since if the cumulative size of the files is not a multiple of the piece length.

Implementing Two-way TCP Traffic Control in F#

This post describes how to implement two-way (TCP for instance) traffic control in F# by modifying slightly a Trolltech article available at http://doc.trolltech.com/qq/qq17-ratecontrol.html.

And the list goes on!

F# brush for Gorbatchev’s SyntaxHighlighter

Dual quicksort in F#

F# brush for Geshi

Batch image resizer

Tries and Anagrams with F#

Crème pâtissière – Pierre Hermé, “Larousse des desserts”

Pâte à choux

Le chocolat

Pâte sucrée – Pierre Hermé, “Larousse des desserts”

Equality and Comparison Constraints in F#

dsyme — Sun, 08 Nov 2009 09:42:00 GMT

F# 1.9.7 introduces two new constraints to the F# language to help uncover issues in your code when using equality and comparison operators. In this blog entry we'll take a look at these constraints in a bit more detail. The topics in this blog post are

Tuples, Lists and other Structural Types

The Basic Equality and Comparison Operations in F#

What do the equality and comparison constraints mean?

Defining New Structural Types

Customizing Equality and Comparison

Safer Code: Suppressing Equality and Comparison on a Type

Safer Code: Safer Sets and Maps

Safer Code: Declaring Conditions for Equality over Container Types

Getting IEqualityComparer<’T> and IComparer<’T> Implementations which use F# Generic Equality

Using unchecked equality and comparison

Design Alternatives. Could interface constraints suffice? User defined constraints?

Summary

You can also find the details in the draft F# Language Specification, where similar material is covered. First, as usual, some background.

Tuples, Lists and other Structural Types

Functional programming in F# frequently involves the use of structural equality, hashing and comparison. For example:

(1,1+1) = (1,2)

will return true, because tuple types support "structural" equality. Likewise these two function calls return identical values:

hash (1,1+1)

hash (1,2)

Likewise an ordering on parts of a tuple induces an ordering on tuples themselves, so all the following evaluate to true:

(1,2) < (1,3)

(1,2) < (2,3)

(1,2) < (2,1)

(1,2) > (1,0)

The same applies to lists, options, arrays and user-defined record, union and struct types whose constituent field types permit structural equality, hashing and comparison.

Equality and comparison are a surprisingly important part of the experience of “programming with functional data” – it is difficult to imagine F# being F# if you can’t compare tuples for equality, or lists for equality, and likewise for other user-defined structural types. In each case, the behaviour of these operations depends on the equality properties of the constituent components.

This in turn means that the “idea” of equality, hashing and comparison (including structural versions of these) is built in quite deeply into the F# language and core library – for example, several pages of the F# specification are devoted to defining what happens when you use equality with user-defined structural types.

The Basic Equality and Comparison Operations in F#

Let’s take a look at the signatures of the equality, comparison and hashing operations in the F# library:

(=) : 'T -> 'T -> bool when 'T : equality

(<>) : 'T -> 'T -> bool when 'T : equality

hash : 'T -> int when 'T : equality

(<) : 'T -> 'T -> bool when 'T : comparison

(<=) : 'T -> 'T -> bool when 'T : comparison

(>) : 'T -> 'T -> bool when 'T : comparison

(>=) : 'T -> 'T -> bool when 'T : comparison

compare : 'T -> 'T -> int when 'T : comparison

min : 'T -> 'T -> 'T when 'T : comparison

max : 'T -> 'T -> 'T when 'T : comparison

First note that these are generic operations – they can be used on objects of many different types. This can be seen by the use of 'T in the signatures of these operations. These operations take one or two parameters of the same type. For example, you can apply the “=” operator to two Form objects, or two System.DateTime objects, or two System.Type objects, and something reasonable will happen. Some other important derived generic types such as the immutable (persistent) Set<_> and Map<_,_> types in the F# library also use generic comparison on their key type:

type Set<'T when 'T : comparison> = ...

type Map<'Key, 'Value when 'Key : comparison> = ...

In common with many other basic generic operators in the F# library, the above operations are constrained, in this case by the 'T : equality and 'T : comparison constraints. The purpose of constraints on type parameters is to make sure the operations are only used on a reasonable set of types. For example, consider using equality and comparison on a System.Windows.Forms.Form object. Equality is permitted, because the default for nearly all .NET object types is reference equality:

let form1 = new System.Windows.Forms.Form()

let form2 = new System.Windows.Forms.Form()

form1 = form1 // true

form1 = form2 // false

However comparison is not permitted:

let form1 = new System.Windows.Forms.Form()

let form2 = new System.Windows.Forms.Form()

form1 <= form2

// Error: The type 'System.Windows.Forms.Form' does not support the 'comparison' constraint.

// For example, it does not support the 'System.IComparable' interface

That’s good! There is no natural ordering for these object - you could define one, on a derived type, by implementing IComparable, but there is not natural ordering provided by the .NET libraries.

Now, unlike other operations in the F# core library, equality and comparison are conditional on the structure of types. For example, you can only use the above equality and comparison operators on a tuple if the constituent parts of the tuple also support equality and comparison. For example, using equality on a tuple of forms is permitted:

let form1 = new System.Windows.Forms.Form()

let form2 = new System.Windows.Forms.Form()

(form1, form2) = (form1, form2) // true

(form1, form2) = (form2, form1) // false

But attempting to order a tuple involving forms is not:

(form1, "Data for Form1") <= (form2, " Data for Form2")

// Error: The type 'System.Windows.Forms.Form' does not support the 'comparison' constraint.

Again, that’s good – this ordering would be a bug in your code.

Many types in the .NET libraries come with custom equality and comparison implementations. For example, System.DateTime has custom implementations of both equality and comparison. F# also allows you to define custom comparison and equality for new type definitions. We’ll be looking at how to customize equality and comparison implementations later in this blog post.

What do the equality and comparison constraints mean?

Let’s summarize where we are so far:

- For some types, equality is structural. For example, lists, options, tuples and user-defined structural types.

- For some types, equality is reference based. These types do not tend to support comparison. For example, System.Windows.Forms.Form.

- For some types, equality is customized, for example System.DateTime.

- For some types, there is no sensible notion of equality and/or comparison. You can think of these types as being labelled no equality and no comparison. This case is only important for finding bugs in your code earlier rather than later.

The combination of these points underlies the decision to include equality and comparison constraints as first-class new, primary constraints in the F# language. Later on in this blog post we consider other options in this design space. Now, let’s take a closer look at when equality and comparison constraints are satisfied in F#.

The essence of the rules is very simple:

The constraint type : equality holds if:

- the type definition for type doesn't have the NoEquality attribute,

- any “equality dependencies” of the type also satisfy ty : equality

The constraint type : comparison holds if:

- if the type is a named type, then the type definition doesn't have the NoComparison attribute; and

- the type definition implements System.IComparable; and

- any “comparison dependencies” of the type also satisfy ty_i : comparison

These rules mean that an equality constraint is a relatively weak constraint, since nearly all CLI types satisfy this constraint. Reference equality is pervasive in other CLI languages such as C# and this shows through in CLI libraries. Note that the an equality constraint also implies the ability to use the F# hash function on an object.

A comparison constraint is a stronger constraint, since it usually implies that a type must implement System.IComparable.

We’ve discussed the notion of “dependencies” above, e.g. (int * string) is comparable because both int and string are comparable. Here, int and string are dependencies of the tuple type. We’ll look at declaring new dependencies for a type further below.

Defining New Structural Types

Structural type definitions are easy in F#:

type MyBox<'T> = MyBox of 'T

In this case, the type is given structural equality and comparison implementations, and F# infers that there is an equality and comparison dependency on ‘T. All done!

Sometimes you may want to assert that a structural type really MUST support structural equality, and you want an error at the definition of the type if it does not. You do this by adding the StructuralEquality or StructuralComparison attribute to the type

[<StructuralEquality;StructuralComparison>]

type MyIntBox = MyIntBox of int

This simply adds extra checking. In the example below, the code gives an error at compile time, because the type can’t logically support automatic structural comparison, because one of the element types does not support structural comparison:

[<StructuralEquality;StructuralComparison>]

type MyData = MyBox of int * string * string * System.Windows.Forms.Form

More commonly, you may notice that F# function types do not support equality:

[<StructuralEquality;StructuralComparison>]

type MyData = MyBox of int * string * string * (int -> int)

Again this will give an error, because function values are considered to be “no equality”

You can also declare that a structural type should use reference equality.

[<ReferenceEquality>]

type MyFormWrapper = MyFormWrapper of System.Windows.Forms.Form * (int -> int)

In summary, the following attributes control the comparison and equality semantics of types in the cases outlined earlier in this blog post

- StructuralEquality,StructuralComparison – indicates a structural type MUST support equality and comaprison

- ReferenceEquality – indicates a structural type supports only reference equality

- NoComparison, NoEquality – indicates a type doesn’t support equality or comparison at all

- CustomEquality, CustomComparison – indicates a structural type supports custom equality and comparison

Note there is no such thing as “reference comparison” (the object pointers used by .NET move around, so the ordering would change). You might implement that by using a unique tag and custom comparison.

Customizing Equality and Comparison

For some types it is often necessary to define your own comparison, equality and hashing semantics. For example, values of a type may carry a unique integer tag which can be used for this purpose.

In this case our recommendation is to take full control of your destiny and define custom comparison and equality operations on your type. For example, here is how you might compare based on a “stamp” integer value:

/// A type abbreviation indicating we’re using integers for unique stamps on objects

type stamp = int

/// A type containing a function that can’t be compared for equality

[<CustomEquality; CustomComparison>]

type MyThing =

{ Stamp: stamp;

Behaviour: (int -> int) }

override x.Equals(yobj) =

match yobj with

| :? MyThing as y -> (x.Stamp = y.Stamp)

| _ -> false

override x.GetHashCode() = hash x.Stamp

interface System.IComparable with

member x.CompareTo yobj =

match yobj with

| :? MyThing as y -> compare x.Stamp y.Stamp

| _ -> invalidArg "yobj" "cannot compare values of different types"

You might also find these helpful to add to your library of F# helpers:

let equalsOn f x (yobj:obj) =

match yobj with

| :? 'T as y -> (f x = f y)

| _ -> false

let hashOn f x = hash (f x)

let compareOn f x (yobj: obj) =

match yobj with

| :? 'T as y -> compare (f x) (f y)

| _ -> invalidArg "yobj" "cannot compare values of different types"

This can then make your custom implementations more uniform. For example, here is a custom implementation for a union type:

type stamp = int

[<CustomEquality; CustomComparison>]

type MyUnionType =

| MyUnionType of stamp * (int -> int)

static member Stamp (MyUnionType (s,_)) = s

override x.Equals y = equalsOn MyUnionType.Stamp x y

override x.GetHashCode() = hashOn MyUnionType.Stamp x

interface System.IComparable with

member x.CompareTo y = compareOn MyUnionType.Stamp x y

You can also define custom equality and comparison implementations on other types.

Note: A bug in an error message in the 1.9.7 release of F# says “A type with CustomEquality must override Equals or implement IEquatable or IStructuralEquatable”. This is not the case: a type with CustomEquality must override Equals.

Safer Code: Suppressing Equality and Comparison on a Type

You can suppress equality on an F# defined type by using [<NoEquality>] attribute on the definition of the type. This simply means that the type will not be considered to satisfy the equality constraint. Likewise, you can suppress comparison on an F# defined type by using [<NoComparison>] attribute on the definition of the type. This simply means that the type will not be considered to satisfy the comparison constraint.

[<NoEquality; NoComparison>]

type MyProjections =

| MyProjections of (int * string) * (string -> int)

Adding these attributes to your library types makes client code safer, as it is less likely to inadvertently rely on equality and comparison over types where these operations make no sense.

Safer Code: Safer Sets and Maps

All previous versions of F# did not check equality and comparison constraints. We always planned to address this, but the details were only finalized in 1.9.7.

One main motivation for checking these constraints is to make sure the F# Set and Map types, and other future F# immutable collections, are not misused. For example, consider the following:

let x1 = set [ (fun x -> x + 1); id ; (fun x -> x + 2) ] // static error

let x2 = set [ obj(); obj(); obj() ] // static error

let x3 = set [ typeof<int>; typeof<string> ] // static error

In early versions of F# these gave runtime errors. As another example, consider trying to compare functions for equality:

id = id // static error

This returned “false” in early versions of F#, because two different closures were allocated for “id” on each side of the equation – this is valid, according to the F# specification, which says that the results of equality comparison on function values was undefined. This now gives a static error. These cases alone indicate the importance of addressing this issue.

Safer Code: Declaring Conditions for Equality over Container Types

Programmers love defining new generic container types. This is done less often in .NET and F# programming than in other languages, but it's still important!

Equality and comparison play a role here. For example, it is common to have collections where some of the values can be indexed using hashing, or compared for equality when searching, or compared using an ordering. For example, seeing a constraint on this signature on a library type would come as no surprise:

type Graph<'Node when 'Node : equality>() = ...

Indeed the presence of the constraint is somewhat reassuring here, as the requirement on node types is made clearer.

Now, sometimes it is also desirable to be able to compare “entire containers”, e.g. compare one set with another, or one map with another, or one graph with another. This is a lot like comparing tuples or lists. At a first approximation this is done by customizing equality and/or comparison for the container.

type Graph<'Node when 'Node : equality>() =

override x.Equals(yobj) = ...

override x.GetHashCode() = ...

In this case, the node type already supports equality/hashing (for indexing inside the collection ) so the implementation of “Equals” is simple enough, following the pattern laid out in the section “Customizing Equality and Comparison” above.

Sometimes, however, it is necessary to declare that equality (and comparison) over generic container values themselves is “dependent” on the type parameters of the container type. Just like F# list and tuple types. This is done by adding the EqualityConditionalOn and ComparisonConditionalOn attributes to the type parameters of a generic type.

As our example, we will use that beguilingly simple beast – a single-cell container that also supports equality and comparison over the container. You can define this easily in F# as follows:

type MyBox<'T> = MyBox of 'T

In this case, this is a structural type definition, and F# infers that there is an equality and comparison dependency on ‘T. All done! You will be able to use MyBox<_> with values of any type, and you will only be able to do equality and comparison on MyBox values if the element type also supports equality and comparison – perfect!

However, what if MyBox is, for some reason, implemented as a class type, or with customized comparison and equality logic for the type? In this case you need to be more explicit, starting with the EqualityConditionalOn and ComparisonConditionalOn attributes on the type parameter:

type MyBox<[<EqualityConditionalOn; ComparisonConditionalOn >]'T> = ...

With these attributes, MyBox<A> will only satisfy the equality and comparison constraints if A satisfies these constraints. You will still be able to use MyBox<_> with any type.

Now, let’s look at the custom implementations for Equals, GetHashCode and System.IComparable. Here’s a full example of a container type that also supports conditional equality and comparison over the containers themselves:

type MyBox<[<EqualityConditionalOn; ComparisonConditionalOn >]'T>(value : 'T) =

member x.Value = value

override x.Equals(yobj) =

match yobj with

| :? MyBox<'T> as y -> Unchecked.equals x.Value y.Value

| _ -> false

override x.GetHashCode() = Unchecked.hash x.Value

interface System.IComparable with

member x.CompareTo yobj =

match yobj with

| :? MyBox<'T> as y -> Unchecked.compare x.Value y.Value

| _ -> invalidArg "yobj" "cannot compare values of different types"

Note that the implementation of the interfaces and overrides uses “unchecked equality and comparison”, something we’ll get to below. The need for unchecked equality here ultimately stems from the dual facts that

(a) F# asks you to specify custom equality at the level of .NET overrides and interface implementations; and

(b) .NET does not support conditional interface and override implementations (see discussion below).

There are great advantages to (a) – it simplifies F# and means you don’t have to look up the F# manual to see what behaviour your objects will have when handed over to C#.

Fortunately, the use of unchecked equality is isolated and localized, and actually surprisingly hard to get wrong. In any case, you should unit test to check that your type really does support equality and comparison correctly.

Getting IEqualityComparer<’T> and IComparer<’T> Implementations which use F# Generic Equality

When using .NET libraries, it is very common to need an implementation of IEqualityComparer<'T> or IComparer<'T>. Two F# core library functions are very useful for getting objects which implement these interfaces in a way that is consistent with F# equality and comparison:

HashIdentity.Structural<'T> : IEqualityComparer<'T> when 'T : equality

ComparisonIdentity.Structural<'T> : IComparer<'T> when 'T : comparable

These are most useful when instantiating .NET hash table and comparison operations. For example:

open System.Collections.Generic

let hashTable = new Dictionary<string,int>(HashIdentity.Structural<string>)

let hashSet = new HashSet<string>(HashIdentity.Structural<string>)

You can also omit some of the type annotations here and let inference do its work:

open System.Collections.Generic

let hashTable = Dictionary(HashIdentity.Structural)

let hashSet = HashSet(HashIdentity.Structural)

hashTable.Add("three", 3)

hashSet.Add("three")

The great advantage of giving an explicit HashIdentity.* or ComparisonIdentity.* argument is that your code is more rigidly checked: the F# compiler checks if your inferred key type actually admits F# equality. For example, F# function types are considered to be “no equality” (i.e. hashing on an F# function values is not a good idea):

open System.Collections.Generic

let concatOne (s:string) = s + "1"

let hashTable = new Dictionary<_,_>(HashIdentity.Structural)

hashTable.Add(concatOne, 10) // error: the type “string -> string” doesn’t support equality

Here the intended code was something like this:

hashTable.Add(concatOne "ten", 10) // ok: the type “string” supports equality

Using unchecked equality and comparison

As we saw above, it can occasionally it can be necessary to resort to “unchecked” equality and comparison on values. This doesn’t do any static checking, just like in earlier versions of F#.

Unchecked.equals: 'T -> 'T -> bool

Unchecked.hash: 'T -> int

Unchecked.compare: 'T -> 'T -> int

These are unconstrained operations, and work just the same way as the constrained operations – for example, they will also by optimized by the F# compiler if used on basic integer types. For Unchecked.equals and Unchecked.hash, they are semantically similar to converting to the type “obj” and doing equality over that static type.

Design Alternatives. Could interface constraints suffice? What about type classes?

Readers familiar with C# may ask “Does F# really need a new kind of constraint here? How about using an interface constraint?”. For example, could we use this signature for comparison?

compare : 'T -> 'T -> bool when 'T : System.IComparable

Or this one?

compare : 'T -> 'T -> bool when 'T : System.IComparable<'T>

The problem with both is that they are too permissive: for example, if F# lists implement IComparable or IComparable<'T>, then the above signatures would let you use comparison on any two F# lists, regardless of whether the element type supports comparison.

The underlying (and well known) problem is that interface implementation in .NET is unconditional – a type either supports an interface or it doesn’t. This is a fundamental limitation of .NET generics. In F#, it is part of our design methodology to add additional, erased constraints to work around such limitations.

Equally it is also not possible to use a parameter constraint on the F# list type. For example, consider this option:

type FSharpList<'T when 'T : IComparable<'T>>() = ... // this leads the type to be over-constrained.

With this signature, lists become much less useful: you couldn’t create lists of objects that don’t support comparison!

As a result, .NET interface constraints are not sufficient to allow us to tackle equality and comparison constraints in F#. This underlies the decision to include equality and comparison constraints as new, erased constraints in the F# language.

Readers familiar with Haskell and other functional languages will be well informed of all the issues relating to equality and comparison, since the issues are fundamental to equality and comparison in any typed language, but particularly functional languages. The mechanisms used to address these points in F# are reminiscent of a weak form of type classes, particularly in the way equality and comparison are dependent on the structure of types, and the way these dependencies can be declared for any type. Haskell also lets users define their own constraints, in a very rich (and sometimes fairly complicated!) way.

Now, equality and comparison are the only operations in the F# Core Library that are statically conditional on the structure of types. This raises the question as to why F# doesn’t allow user-defined constraints (beyond interface constraints), and why other constraints can’t be declared conditional. After all, it is well known that it can be useful to make other operations conditional on structure too, e.g. printing and serialization.

The answer is two-fold. Firstly, in future versions of F# we may consider extending the mechanisms used to implement equality and comparison constraints to include user-defined constraints.

Secondly, however, for many common used constraints (such as formatting and serializability), there are other ways to achieve the same thing in F# that are not particularly amenable to using constraints. Also, in each case there are serious interactions with .NET libraries and existing design practice to consider. Finally, some conditional constraints would require a “dictionary passing” implementation. This brings added difficulties. Equality and comparison constraints are not dictionary passing – they are ultimately implemented via interfaces and overrides. As a result, for F# in Visual Studio 2010, we concentrated on resolving the interactions with .NET for the critical cases of equality and comparison, rather than adding a completely general mechanism.

Summary

F# equality and comparison constraints tighten up a key part of the F# language, they make user code safer and simpler.

On the whole, F# code is surprisingly unaffected by these constraints – in our test trees we have a very large collection of sample F# code, and only a very small amount of that code needed to have equality or comparison constraints added. These constraints catch problems, but do not intrude. For example, we use structural and equality constraints throughout the F# compiler codebase and, in a couple of cases, it helped to identify lingering potential bugs.

In 1.9.7 we also simplified some of the attributes used to control equality and comparison, notably removing the “true” and “false” arguments from StructuralEquality etc., and adding CustomEquality to help users declare exactly what is intended. If you need additional help to adjust your code for these changes, please let us know.

We wish you many happy days of safer and more productive coding!

"Getting started" with NaturalSpec – (Updated 08.11.2009)

Sun, 08 Nov 2009 01:48:00 GMT

In my last article (Introducing NaturalSpec – A Domain-specific language (DSL) for testing) I used NaturalSpec in two small samples. This time I will show how we can set up a NaturalSpec environment to write our first automatically testable scenarios.

1. Choosing an IDE

The first step is to choose an integrated development environment for NaturalSpec. At the current project status you should be able to use NaturalSpec with Visual Studio 2008, Visual Studio 2010 beta 2, the freely available Visual Studio 2008 Shell or the free IDE SharpDevelop 3.0.

2. Installing the testing framework

As NaturalSpec uses NUnit as the underlying testing framework we have to install NUnit 2.5. I also recommend installing TestDriven.Net in order to get a Unit Test runner within Visual Studio.

3. Installing F#

NaturalSpec is completely written in F# and all specs will also be written in F#. This doesn’t imply you have to learn programming in F# but we need the F# compiler to get things working. You can download the F# October 2009 CTP from the Microsoft F# Developer Center.

4. Downloading the latest version of NaturalSpec

You can download a .zip with the latest NaturalSpec libraries from GoogleCode.

5. Creating a spec

This part is written for using Visual Studio 2008. If you use SharpDevelop or Visual Studio 2008 Shell this might differ in some detail.

Start Visual Studio 2008 and create a new F# class library.

Rename Module1.fs in ListSpec.fs and delete script.fsx from the project:

Create a folder “Lib” and unzip the NaturalSpec libraries into it.

Add NaturalSpec.dll and nunit.framework.dll as references to your project:

Copy the following code into ListSpec.fs:

module ListSpec

open NaturalSpec [<Scenario>]
let When_removing_an_3_from_a_small_list_it_should_not_contain_3() = Given [1;2;3;4;5] |> When removing 3 |> It shouldn't contain 3 |> Verify

If you have TestDriven.Net installed you can run your spec via right click in the solution explorer:

If you don’t like the TestDriven.Net test runner you might want to use the NUnit GUI runner. The output should look like:

In addition the test runner should produce a Spec output file with the name “Spec.txt” within the same folder.

Summary

In a minimal environment you need SharpDevelop, the F# compiler, NUnit and the NaturalSpec libraries for using NaturalSpec.

In the next post I will show how you can use NaturalSpec to create a spec for C# projects.

Observing global hotkeys in C# / F#

Fri, 06 Nov 2009 02:08:05 GMT

I recently had the problem to register a global hotkey, but my “old” Win32-API calls didn’t work with WPF. I looked around the web and found the “Managed Windows API”, but I didn’t want to add another external dependency to my project, so I extracted the core functions for registering hotkeys and condensed the code to a new version.

As the original “Managed Windows API” is licensed by the GNU Lesser General Public License (LGPL) I want to provide my modifications here.

First we need a Window which can dispatch the window messages to our event handlers:

/// <summary>
/// A Win32 native window that delegates window messages to 
/// handlers. So several
/// components can use the same native window to save 
/// "USER resources". This class
/// is useful when writing your own components.
/// </summary>
public sealed class EventDispatchingNativeWindow : NativeWindow
{
    private static readonly Object MyLock = new Object();
    private static EventDispatchingNativeWindow _instance;
 
    /// <summary>
    /// Create your own event dispatching window.
    /// </summary>
    public EventDispatchingNativeWindow()
    {
        CreateHandle(new CreateParams());
    }
 
    /// <summary>
    /// A global instance which can be used by components 
    /// that do not need their own window.
    /// </summary>
    public static EventDispatchingNativeWindow Instance
    {
        get
        {
            lock (MyLock)
            {
                return 
                  _instance ?? 
                     (_instance = 
                       new EventDispatchingNativeWindow());
            }
        }
    }
 
    /// <summary>
    /// Attach your event handlers here.
    /// </summary>
    public event WndProcEventHandler EventHandler;
 
    /// <summary>
    /// Parse messages passed to this window and send 
    /// them to the event handlers.
    /// </summary>
    /// <param name="m">A System.Windows.Forms.Message 
    /// that is associated with the 
    /// current Windows message.</param>
    protected override void WndProc(ref Message m)
    {
        bool handled = false;
        if (EventHandler != null)
            EventHandler(ref m, ref handled);
        if (!handled)
            base.WndProc(ref m);
    }
}

Now we can write our global hotkey handler class:

/// <summary>
/// Specifies a class that creates a global keyboard hotkey.
/// </summary>
public class GlobalHotkey
{
    private static readonly Object MyStaticLock = new Object();
    private static int _hotkeyCounter = 0xA000;
 
    private readonly int _hotkeyIndex;
    private readonly IntPtr _hWnd;
 
    /// <summary>
    /// Initializes a new instance of this class.
    /// </summary>
    /// <param name="keys">The keys.</param>
    /// <param name="ctrl">if <c>true</c> [CTRL].</param>
    /// <param name="alt">if <c>true</c> [alt].</param>
    /// <param name="shift">if <c>true</c> [shift].</param>
    /// <param name="winKey">if <c>true</c> [win key].</param>
    public GlobalHotkey(Keys keys, bool ctrl, 
               bool alt, bool shift, bool winKey)
    {
        KeyCode = keys;
        Ctrl = ctrl;
        Alt = alt;
        Shift = shift;
        WindowsKey = winKey;
        EventDispatchingNativeWindow.Instance.EventHandler 
                += NwEventHandler;
        lock (MyStaticLock)
        {
            _hotkeyIndex = ++_hotkeyCounter;
        }
        _hWnd = EventDispatchingNativeWindow.Instance.Handle;
        Enable();
    }
 
    /// <summary>
    /// The key code of the hotkey.
    /// </summary>
    public Keys KeyCode { get; private set; }
 
    /// <summary>
    /// Whether the shortcut includes the Control modifier.
    /// </summary>
    public bool Ctrl { get; private set; }
 
    /// <summary>
    /// Whether this shortcut includes the Alt modifier.
    /// </summary>
    public bool Alt { get; private set; }
 
    /// <summary>
    /// Whether this shortcut includes the shift modifier.
    /// </summary>
    public bool Shift { get; private set; }
 
    /// <summary>
    /// Whether this shortcut includes the Windows key modifier.

      /// </summary>
    public bool WindowsKey { get; private set; }
 
    ~GlobalHotkey()
    {
        Disable();
        EventDispatchingNativeWindow.Instance.EventHandler 
            -= NwEventHandler;
    }
 
    /// <summary>
    /// Enables the hotkey. When the hotkey is enabled, 
    /// pressing it causes a
    /// <c>HotkeyPressed</c> event instead of being 
    /// handled by the active application.
    /// </summary>
    private void Enable()
    {
        // register hotkey
        int fsModifiers = 0;
        if (Shift) fsModifiers += ModShift;
        if (Ctrl) fsModifiers += ModControl;
        if (Alt) fsModifiers += ModAlt;
        if (WindowsKey) fsModifiers += ModWin;
        bool success = 
           RegisterHotKey(_hWnd, _hotkeyIndex, 
                fsModifiers, (int) KeyCode);
 
        if (!success)
            throw new 
              Exception(
                "Could not register hotkey (already in use).");
    }
 
    /// <summary>
    /// Disables this instance.
    /// </summary>
    private void Disable()
    {
        // unregister hotkey
        UnregisterHotKey(_hWnd, _hotkeyIndex);
    }
 
    /// <summary>
    /// Occurs when the hotkey is pressed.
    /// </summary>
    public event EventHandler HotkeyPressed;
 
    private void NwEventHandler(ref Message m, ref bool handled)
    {
        if (handled) return;
        if (m.Msg != WmHotkey || 
                m.WParam.ToInt32() != _hotkeyIndex)
            return;
        if (HotkeyPressed != null)
            HotkeyPressed(this, EventArgs.Empty);
        handled = true;
    }
 
    #region PInvoke Declarations
 
    private const int ModAlt = 0×0001;
    private const int ModControl = 0×0002;
    private const int ModShift = 0×0004;
    private const int ModWin = 0×0008;
    private const int WmHotkey = 0×0312;
 
    [DllImport("user32.dll", SetLastError = true)]
    private static extern bool RegisterHotKey(IntPtr hWnd, 
          int id, int fsModifiers, int vlc);
 
    [DllImport("user32.dll", SetLastError = true)]
    private static extern bool UnregisterHotKey(IntPtr hWnd, 
          int id);
 
    #endregion
}

Now we can easily register a global hotkey or use it as an observable in F#:

/// system-wide keyboard hook
let hotkey = new GlobalHotkey(Keys.Q,true,false,false,false)
let hookObserver =
  hotkey.HotkeyPressed  
    |> Observable.subscribe (fun _ -> printfn "Hotkey pressed")

Technical analysis indicators in F# – Part I

Thu, 05 Nov 2009 20:47:01 GMT

This is the first part of a series on technical analysis indicators in F#. We will define the basic object holding the data series which will be used to compute the indicators. We will also describe some functions to check the integrity of the said data (and which will be useful when defining the indicators). Quick disclaimer [...]

F# for Visualization 0.4.0.2 released

Thu, 05 Nov 2009 18:55:00 GMT

A new release of our F# for Visualization library is now available to beta release subscribers. This release is designed to work with the new October 2009 CTP release of F#.

Custom WPF Controls in F#

Thu, 05 Nov 2009 17:14:57 GMT

*Update: Custom WPF Controls in F# is now available on Codeplex at http://wpffsharp.codeplex.com. You can still download the source from my site here. (Works best withVSTS2010 Beta1)

Screen Shot

It is a translation of SAMS WPF Control Development Unleashed: Building Advanced User Interfaces written by Pavan Podila, and Kevin Hoffman to F#. I picked this book for translation as it covers many advanced topics that other books shy away from. I have been a reader of Pavan Podila’s blog Pixel in Gene for some time, and I have also been waiting for a book dedicated advanced UIs, so when I heard that he was coming out with such a book I knew it was going to be exactly what I needed.

WPF Control Development

The aim behind this project is to serve as an extensive collection non trivial examples of WPF/F# UI. As I introduce people to F#, one thing I am constantly asked is; can it do GUI. Now I can say yes, … well sort of. So far I have only translated 3,500 lines of F# code, and I am still not finished.

I’m doing this primarily as a learning experience and as a forcing function. I have already learned a lot about WPF and F#, and I plan on continuously improving the code as I learn more. Other contributions to the project would be very welcome, and if you spot mistakes or know of any better implementations please don’t hesitate to let me know.

I hope that you find this code to be useful to your WPF and F# projects , and happy coding.

-Matt

Read on for a list of known bugs;

A recent upgrade from VSTS 2010 Beta 1 to VSTS 2010 Beta 2 has unfortunately caused a whole lot of new bugs (on top of the ones that were already there).

List of known bugs:

Chapter 2 – Media element doesn’t play

Chapter 9 - TransitionContainer (delegate blocked off from TransitionTester_Loaded)

Chapter 10 – ComponentResourceKey ?? Not sure what is happening here

Chapter 10 – Custom Chrome Window, no skin on window

Chapter 11 – GardenViewPanel3D and Interactive GardenViewPanel3D both register the same names (they work individually)

Chapter 12 – Issues with enums for 3D mesh

Chapter 13 – Dependency properties for SqueezeEffect and DisplacementEffect overlap? “Input’ property was already registered by ‘DisplacementEffect’”

Chapter 14 – WeekEvent / Command Source (Property SpikeControl.Command not found)

Chapter 15 – Media element doesn’t play

Chapter 17 – Cannot find the static member ‘WatermakrTextProperty’ on the type ‘TextBoxWatermarkHelper’

Chapter 18 – ComputedStartOffsetProperty on type RangeSelector

Chapter 2 – Media element doesn’t play
Chapter 9 - TransitionContainer (delegate blocked off from TransitionTester_Loaded)
Chapter 10 – ComponentResourceKey ?? Not sure what is happening here
Chapter 10 – Custom Chrome Window, no skin on window
Chapter 11 – GardenViewPanel3D and Interactive GardenViewPanel3D both register the same names (they work individually)
Chapter 12 – Issues with enums for 3D mesh
Chapter 13 – Dependency properties for SqueezeEffect and DisplacementEffect overlap? “Input’ property was already registered by ‘DisplacementEffect’”
Chapter 14 – WeekEvent / Command Source (Property SpikeControl.Command not found)
Chapter 15 – Media element doesn’t play
Chapter 17 – Cannot find the static member ‘WatermakrTextProperty’ on the type ‘TextBoxWatermarkHelper’
Chapter 18 – ComputedStartOffsetProperty on type RangeSelector

F# 1.9.7 Language Specification Now Available

dsyme — Wed, 04 Nov 2009 09:46:00 GMT

The F# 1.9.7 Language Specification is now available, in PDF and HTML, matching the recent release of F# in Visual Studio 2010 Beta2, with matching CTP udpate for Mono and Visual Studio 2008. The latest language specification can also always be found via www.fsharp.net

Many thanks to all those who sent so much helpful feedback on the specification during Beta1. And for those using 1.9.7 already, thanks for your patience in the last couple of weeks - it took us a little longer to get this out the door than we had planned, since a development deadline for Visual Studio 2010 intervened.

We plan on making a second update to the 1.9.7 spec to polish some areas of the text in the next few weeks.

thanks,

don

F# under the covers VII

Steve — Tue, 03 Nov 2009 13:34:00 GMT

Working with nCover to examine the number of code-points represented by any given method, the October CTP made a large number of changes -- some up, some down -- to the code generated by the compiler.

Most interesting is the change to attribute setters, which used to be NOP;assign;return and are now just assign;return. Also the name of the implicit backing field has changed to be the property name with an appended '@', rather than being a case-mangled version of the property name.

(As always, talking about Debug builds).

Discriminated Unions in F#

Tue, 03 Nov 2009 09:20:00 GMT

In this video, programming writer, Gordon Hogenson explains and gives examples of discriminated unions in F#.

You can also learn more in the topic Discriminated Unions (F#)

Kathleen McGrath
Visual Studio User Education
http://blogs.msdn.com/kathleen
Visual Studio and .NET Framework Content Survey

An RSS Dashboard in F#, part one

Mon, 02 Nov 2009 23:48:02 GMT

As you may know, I am quite active answering questions on forums like StackOverflow and hubfs. I want F# users to get prompt and useful answers to their questions (and yes, I also wanted to be the first person to earn the F# badge on SO). But of course I cannot afford to spend all my time hitting the refresh button in my web browser, just waiting to pounce on new questions. So I need a tool to make it easy for me to keep abreast of forum topics. while still getting my other work done. I’ve created such a tool for myself, which I’ll describe in this blog series.

Setting goal for the app

Any reasonable web forum will be publishing an RSS feed (or Atom feed) of its posts, so it’s easy to get the data I wanted. The only thing I needed to do was figure out an effective way to present the information. The requirements I set up for myself were

I wanted a “dashboard”-style app. That is, I wanted to be able to view a summary of all the forum topics I care about on a single screen.
Of course I needed to be able to control the set of forum feeds/topics the app listens to.
I wanted the ability to get audio notification for new posts on interesting topics. This way I can leave the app running in the background during the day while I’m doing other work, but still be able to react quickly to new questions.
I wanted to easily visualize the “diff” over longer periods of time. For example, when I get in on Monday morning, I want to quickly be able to see “what’s new and different” since the last time I looked at the forums from the weekend.

Now, perhaps there is already a great tool out there which I could download that already meets all those requirements. But like many developers, I personally set a few more (selfish) requirements, namely

I wanted to built it myself in F#,
so I could experiment with some new-to-me technologies I don’t typically use in my day job,
and so I could blog about it.

So without further ado, I present…

Brian’s RSS Dashboard

Here’s a screenshot of the app, which tells half the story by itself (sometimes a picture really is worth a thousand words):

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

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

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

The audio is great for when I’m at my desk working on something else. If I’m in “flow” with whatever I’m working on, I just ignore the audio (my brain seems to tune it out automatically), but otherwise if I can take a break or afford a distraction, I’ll go have a look. This helps me provide quick replies to questions, which makes for happy customers and good StackOverflow reputation points. I only have the “audio” option turned on for a select few feeds (to minimize distraction).

The yellow highlight is great for when I return after being away from my desk for a while. When I log on in the morning, first thing I’ll do is glance at the dashboard to see what’s new (yellow). I click on any threads I’m interested in reading (and perhaps responding to) to go visit them in my browser. And then when I’m caught up, I click the big button at the top labeled “Mark all as seen”, which just erases all the yellow highlights.

That’s pretty much it! It’s a simple app, nothing fancy, but I’m very pleased with it, because it makes it super-easy for me to keep track of a number of different forums on different web sites.

Technology overview

In subsequent blog entries I’ll walk through all the F# code. Today I’ll just give an overview of the breakdown of the app and the various technologies/APIs that underlie each portion. The app conceptually has four main pieces:

Observable Feeds. I already know plenty about RSS/Atom feeds, seeing as I was part of the team that created the SyndicationFeed class in .Net Framework 3.5. IObservable<T> (the push-vs.-pull dual of IEnumerable<T>) is, on the other hand, new technology that I wanted an excuse to play around with. For this app, an important piece of the code is about making feeds be IObservables.
Speech. Though the .Net speech synthesis APIs are dirt-simple to use, there’s still a bit of futzing around to do here if, for example, you want your computer to pronounce “GUI” like “gooey”.
Getting link-coloring info from Internet Explorer. I really wanted the links in my app to be the same color as the links in my browser. But I also wanted my entire UI to be hand-coded WPF (I didn’t want to create HTML and host that in browser, that is not fun/interesting to me). So I needed a way to get IE to tell me what color each link should be. Perhaps there is a simple(r) way to do this, but I did find a way that involved hosting an invisible IE control that browses some HTML-and-Javascript my app serves to get the info it needs. It’s one of those hacks that you know is awful, but you nevertheless grin about, because it works. (I’d never written a line of Javascript before this – more unexpected new technology. Score!)
The WPF UI. This is undoubtedly the most complex UI I’ve ever created on my own. Since the app is basically a grid of text and a single button, you would be correct to infer that my prior UI experience is practically zero. :) When you have no UI experience, it is easy to be tickled pink when you first get your pretty icons or yellow highlights to appear on the screen. I enjoyed this bit.

And of course for any UI app, even though there is various background work going on (speech/audio, polling feeds, …) we want to ensure the UI stays up-to-date and responsive. Of course my code never mentions “Thread” or “BackgroundWorker”; instead it’s F# async, MailboxProcessor, and .Net SynchronizationContext FTW! I was very pleased how easy that part was.

For next time…

If you’re not yet familiar with IObservable, might I suggest that you watch a video or three? It’s cool stuff; a simple set of interfaces for a powerful reactive eventing model.

Hopefully you’re aware of RSS feeds (and you’re subscribed to my blog’s feed :), right?), but if not, at least read the paragraph summary on wikipedia.

Next time we’ll jump into the code for observable feeds. Fun stuff ahead!

Awesome F# - Decision Trees – Part II

Mon, 02 Nov 2009 18:56:00 GMT

In my previous post I went over the theory behind the ID3 algorithm. Now that we got all that painful math out of the way, let’s write some code! Here is an implementation of the algorithm in F#. (It is also attached to this blog post, download it via the link at the bottom.)

open System type Record = { Outlook : string Temperature : string Humidity : string Wind : string PlayTennis : bool } /// Given an attribute name return its value member this.GetAttributeValue(attrName) = match attrName with | "Outlook" -> this.Outlook | "Temperature" -> this.Temperature | "Humidity" -> this.Humidity | "Wind" -> this.Wind | _ -> failwithf "Invalid attribute name '%s'" attrName /// Make the %o format specifier look all pretty like override this.ToString() = sprintf "{Outlook = %s, Temp = %s, Humidity = %s, Wind = %s, PlayTennis = %b}" this.Outlook this.Temperature this.Humidity this.Wind this.PlayTennis type DecisionTreeNode = // Attribute name and value / child node list | DecisionNode of string * (string * DecisionTreeNode) seq // Decision and corresponding evidence | Leaf of bool * Record seq // ---------------------------------------------------------------------------- /// Return the total true, total false, and total count for a set of Records
let countClassifications data = Seq.fold (fun (t,f,c) item -> match item.PlayTennis with | true -> (t + 1, f, c + 1) | false -> (t, f + 1, c + 1)) (0, 0, 0) data // ---------------------------------------------------------------------------- /// Return the theoretical number of bits required to classify the information.
/// If a 50/50 mix, returns 1, if 100% true or false returns 0.
let entropy data = let (trueValues, falseValues, totalCount) = countClassifications data let probTrue = (float trueValues) / (float totalCount) let probFalse = (float falseValues) / (float totalCount) // Log2(1.0) = infinity, short circuiting this part if trueValues = totalCount || falseValues = totalCount then 0.0 else -probTrue * Math.Log(probTrue, 2.0) + -probFalse * Math.Log(probFalse, 2.0) /// Given a set of data, how many bits do you save if you know the provided attribute.
let informationGain (data : Record seq) attr = // Partition the data into new sets based on each unique value of the given attribute // e.g. [ where Outlook = rainy ], [ where Outlook = overcast], [ ... ] let divisionsByAttribute = data |> Seq.groupBy(fun item -> item.GetAttributeValue(attr)) let totalEntropy = entropy data let entropyBasedOnSplit = divisionsByAttribute |> Seq.map(fun (attributeValue, rowsWithThatValue) -> let ent = entropy rowsWithThatValue let percentageOfTotalRows = (float <| Seq.length rowsWithThatValue) / (float <| Seq.length data) -1.0 * percentageOfTotalRows * ent) |> Seq.sum totalEntropy + entropyBasedOnSplit // ---------------------------------------------------------------------------- /// Give a list of attributes left to branch on and training data,
/// construct a decision tree node.
let rec createTreeNode data attributesLeft = let (totalTrue, totalFalse, totalCount) = countClassifications data // If we have tested all attributes, then label this node with the // most often occuring instance; likewise if everything has the same value. if List.length attributesLeft = 0 || totalTrue = 0 || totalFalse = 0 then let mostOftenOccuring = if totalTrue > totalFalse then true else false Leaf(mostOftenOccuring, data) // Otherwise, create a proper decision tree node and branch accordingly else let attributeWithMostInformationGain = attributesLeft |> List.map(fun attrName -> attrName, (informationGain data attrName)) |> List.maxBy(fun (attrName, infoGain) -> infoGain) |> fst let remainingAttributes = attributesLeft |> List.filter ((<>) attributeWithMostInformationGain) // Partition that data base on the attribute's values let partitionedData = Seq.groupBy (fun (r : Record) -> r.GetAttributeValue(attributeWithMostInformationGain)) data // Create child nodes let childNodes = partitionedData |> Seq.map (fun (attrValue, subData) -> attrValue, (createTreeNode subData remainingAttributes)) DecisionNode(attributeWithMostInformationGain, childNodes)

The entropy and informationGain functions were covered in my last post, so let’s walk through how the actual decision tree gets constructed. There’s a little work to calculating the optimal decision tree split, but with F# you can express it quite beautifully.

let attributeWithMostInformationGain = attributesLeft |> List.map(fun attrName -> attrName, (informationGain data attrName)) |> List.maxBy(fun (attrName, infoGain) -> infoGain) |> fst

First, it takes all the potential attributes left to split on…

attributesLeft

… and then maps that attribute name to a new attribute name / information gain tuple …

|> List.map(fun attrName -> attrName, (informationGain data attrName))

… then from the newly generated list, pick out the tuple with the highest information gain …

|> List.maxBy(fun (attrName, infoGain) -> infoGain)

…finally returning the first element of that tuple, which is the attribute with the highest information gain.

|> fst

Once you can construct a decision tree in memory, how do get it out? The simplest way is to print it to the console.

The code is very straight forward. Note the use of ‘padding parameter’, so that recursive calls get indented more and more. This is a very helpful technique when printing tree-like data structures to the console.

/// Print the decision tree to the console
let rec printID3Result indent node = let padding = new System.String(' ', indent) match node with | Leaf(classification, data) -> printfn "\tClassification = %b" classification // data |> Seq.iter (fun item -> printfn "%s->%s" padding <| item.ToString()) | DecisionNode(attribute, childNodes) -> printfn "" // Finish previous line printfn "%sBranching on attribute [%s]" padding attribute childNodes |> Seq.iter (fun (attrValue, childNode) -> printf "%s->With value [%s]..." padding attrValue printID3Result (indent + 4) childNode)

However, it’s almost the year 2010. So in lieu of flying cars perhaps we can at least do better than printing data to the console. Ideally, we want to generate some sexy image like this:

You could painstakingly construct the decision tree using Microsoft Visio but fortunately there are tools to do this for you. AT&T Research has produced a great tool called GraphViz. While the end result doesn’t quite have sizzle, it’s very easy enough to get going.

The following function dumps the decision tree into a format that GraphViz can plot. (Just copy the printed text into the tool and plot it using the default settings.)

/// Prints the tree in a format amenable to GraphViz
/// See http://www.graphviz.org/ for more format
let printInGraphVizFormat node = let rec printNode parentName name node = match node with | DecisionNode(attribute, childNodes) -> // Print the decision node printfn "\"%s\" [ label = \"%s\" ];" (parentName + name) attribute // Print link from parent to this node (unless it's the root) if parentName <> "" then printfn "\"%s\" -> \"%s\" [ label = \"%s\" ];" parentName (parentName + name) name childNodes |> Seq.iter(fun (attrValue, childNode) -> printNode (parentName + name) attrValue childNode) | Leaf(classification, _) -> let label = match classification with | true -> "Yes" | false -> "No" // Print the decision node printfn "\"%s\" [ label = \"%s\" ];" (parentName + name) label // Print link from parent to this node printfn "\"%s\" -> \"%s\" [ label = \"%s\" ];" parentName (parentName + name) name printfn "digraph g {" printNode "" "root" node printfn "}"

So there you have it, ID3 in F#. With a little bit of mathematics and some clever output you can construct decision trees for all your machine learning needs. Think of the ID3 algorithm in the future the next time you want to mine customer transactions, analyze server logs, or program your killer robot to find Sarah Conner.

<TotallyShamelessPlug> If you would like to learn more about F#, check out Programming F# by O’Reilly. Available on Amazon and at other fine retailers. </TotallyShamelessPlug>

F# Discoveries This Week 11/02/2009

Mon, 02 Nov 2009 07:05:22 GMT

F# events are popping up all over the place and so I’ve included a separate section for them today. As far as posts go I’ve stumbled across immutable queue and range libraries, a post on the underlying implementation of discriminated unions, using the reactive framework and finally, a Microsoft research project: F7 Refinement Types.

-- Events --

Talbott Crowell is Presenting at the New England Visual Basic Professionals, November 5th

Introducing F# at 6:15pm

I am Presenting at Fairfield / Westchester Code Camp 2009 on November 7th

Why F# at 11:15am in Track 2
F# for Testing and Analysis at 2:40pm in Track 4

NashDotNet - F# Firestarter in Franklin, TN on November 14th

Come with an open mind and a laptop. Be prepared to learn, share, and chat. No prior knowledge or experience with F# is expected.

-- Posts --

Julien’s An Immutable Range Library in F#

An immutable range library in F# where a range is only defined by a minimum and a maximum value (hence, there is no step).

and Julien’s An immutable Queue Library in F#

An immutable queue library in F#. The queue is divided into two lists : one for dequeueing, and one for enqueueing. All operations are based on the List module.

I hope that Julien considers contributing these gems to the F# Power Pack.

F7: Refinement Types for F#

F7 is an enhanced type checker for the F# programming language. F7 supports static checking of properties expressed with refinement types. Our motivation is to check various security properties of F# implementation code by typing.

I took a peek at the included samples and found myself quite lost. It would be great if a walkthrough on how to use F7 were to pop up.

Using F# Discriminated Unions in C# (VS2010 Beta 2)

While updating my VsVim editor extensions for Beta2 [1] I got hit by a change in the way F# exposed discriminated unions in metadata.

A quick romp through how discriminated unions work under the hood and how you use them from C#.

IObservable/IObserver – Using the Reactive Framework with F#

One of the nice new features in .NET 4.0 beta 2 is the IObservable<T>/IObserver<T> support from the Reactive Framework (“Rx Framework” or sometimes “LinqToEvents”). It is a really powerful way to use reactive programming in .NET and especially in F# developed by Erik Meijer and his team.

Turning AutoCAD into a Spirograph using F#

Kean Walmsley — Mon, 02 Nov 2009 06:42:40 GMT

Thinking about ECNs, WF, Oslo State Machine, F# and Task

Mon, 02 Nov 2009 00:30:57 GMT

I’m not sure how many times people can blog about design patterns, anyway here is another with a Silverlight spin. You better watch these video’s as well if your new to this old world.
WF 4.0 Scheduler – under the hood details
Reflection Shader
The impact of regulatory changes on ECNs/MTFs
Oslo: State Machine Editor in Silverlight – interesting article, and probably a good foundation if your thinking about RFQ’s.
Task the new thread?
Awesome F#

An immutable range library in F#

Sun, 01 Nov 2009 21:35:29 GMT

An immutable range library in F# where a range is only defined by a minimum and a maximum value (hence, there is no step). Source type Range<'a when 'a:comparison> = { Min : 'a Max : 'a } override x.ToString() = sprintf "Range [...]

Some quick F# notes…

Sun, 01 Nov 2009 15:53:45 GMT

I am lining up a blog series, but in the meantime, here are a few quick notes and links to keep you occupied. :)

First, I forgot to mention that the documentation for the F# runtime (FSharp.Core.dll) is now online on MSDN. Previously these docs were only available from the F# website on research.microsoft.com. The F# docs keep getting better and better, as well as more fleshed out (and I really like the new look and improved usability of the MSDN site overall). So: don’t forget the docs, they’re a valuable resource.

For those of you just getting started with F#, here’s a summary of my most useful introductory/reference links:

Brian's favorite online content for learning F# – a summary of good links to docs/videos/etc
A three-part overview of the syntax of the language:

What does this C# code look like in F#? – a comparative “here is some C#, here is the corresponding F#” reference
F# function types: fun with tuples and currying – overview of tuples, curried functions, and partial application
Pipelining in F# – a discussion on the pipeline operator (|>)

Teaser: Regarding what’s coming up, I intend to do a blog series about a little app I wrote that I find useful. It is a nice example that emphasizes the connectedness of F# with the rest of the .Net platform, in that the app uses F# (including some advanced features like async and MailboxProcessors) along with a variety of other technologies: WPF, IObservables, SyndicationFeeds, Speech APIs, SynchronizationContexts, and COM interop. To do something useful! (This is not just another “calculate factorials” example!) All in just 500 lines of code. So that will be fun to discuss; I’m looking forward to writing it up.

Please keep sending your feedback to the F# team! Since the Beta2 release we’ve received lots of useful feedback and bug reports. Keep it coming! We’re glad to hear from you at fsbugs@microsoft.com.

Until next time…

Awesome F# - Decision Trees – Part I

Sat, 31 Oct 2009 15:01:20 GMT

Programming F# is out! Meaning you can, and should, go to the store and pick up a copy today.

With Programming F# serving as a solid guide for the F# Language, I’d like to start posting less about language features and more about applications. That is, what can you do with this awesome language.

This is the first blog post in a series titled Awesome F#. These posts will provide advanced, real-world applications of the F# language to do awesome things. This post is about Decision Trees and the ID3 algorithm, motivated by this question on StackOverflow.com.

If you want to learn more about data mining and machine learning THE BOOK you need to get is Machine Learning by Tom Mitchell. I’ll give a warning however, it is the most academically rigorous and dense book I’ve ever read. Seriously, not for the faint of heart!

Defining the Problem

So what does the ID3 algorithm do? It is a technique for creating decision trees much like the following used for determining whether or not to play tennis. Starting at the topmost node, if the outlook is overcast then you should play tennis. If it is rainy however, you should play tennis only if the wind is weak.

In addition to helping plan your sports activities, decision trees are an easy way to gather business intelligence. Imagine you run mid-sized paper company in Scranton, Pennsylvania. You have a database filled with IP addresses of people who have visited your site, special deals you’ve offered them on your products, and whether or not they ended up purchasing some paper.

This is a situation where you want to apply data mining to extract meaning from the data. In this case, how to optimize your sales.

There are many different data mining algorithms based on the type of data you have and what you are looking for. In this blog post I will be covering decision trees, which is a machine learning technique for predicting a concept based on data. (For example, given a browser session predict if the user will purchase something.)

More formally: given a set of instances represented as name/value pairs - where the values are discrete - create a decision tree to most accurately classify any new instances. In the example above the name value pairs were Outlook : {Sunny, Rainy, Overcast} and the classification was ‘should you plan tennis’.

The Approach

The simplest way to do this is to generate tree branches greedily. Given your training data, find the best branch first and then moving on with more specific subsets of rules on reduced data sets. For example, if trying to determine if someone will purchase a product from your website whether or not they are a returning customer is probably the most significant piece of information.

To find the ‘best split’ we will use an approach known as information again. But first, let’s look at a concept from information theory called entropy. Imagine you want to create a decision tree to determine if someone is an evil genius. Each datum may contain information such as gender and whether or not they had a Ph.D.

Entropy and information gain are metrics for calculating how much you learned from taking a given branch. If exactly 50% of evil geniuses are men, then you have learned nothing by branching on gender. (Since the same number of evil geniuses will be on the left side of the tree as the right side of the tree.) However, for determining evil geniuses education is likely very important – since we can assume the majority of evil geniuses have a Ph.D. in malevolence. In that case the decision tree branch is very effective at whittling down the data into a homogenous group: evil genius or not.

Enter the Mathematics

While information gain and entropy are simple concepts, the math is a bit intimidating. Let’s carry on with the ‘is an evil genius’ predictor using the following data:

Gender	Education	Is Evil Genius?
Female	No Ph.D.	No
Male	No Ph.D.	No
Male	No Ph.D.	No
Female	No Ph.D.	No
Female	No Ph.D.	No
Male	No Ph.D.	No
Male	No Ph.D.	No
Female	No Ph.D.	No
Female	No Ph.D.	No
Male	No Ph.D.	Yes
Male	No Ph.D.	Yes
Female	No Ph.D.	No
Female	No Ph.D.	No
Male	No Ph.D.	No
Male	No Ph.D.	No
Female	No Ph.D.	No
Female	No Ph.D.	No
Male	No Ph.D.	No
Male	No Ph.D.	No
Female	No Ph.D.	No
Female	No Ph.D.	No
Male	No Ph.D.	No
Male	No Ph.D.	No
Female	No Ph.D.	No
Female	No Ph.D.	No
Male	Ph.D.	Yes
Male	Ph.D.	Yes
Female	Ph.D.	Yes
Female	Ph.D.	Yes
Male	Ph.D.	No

Entropy

Given a set of data, S, which can be divided c ways with the probability of each division being p the entropy of that set is given by:

For example, if out of a set of six evil geniuses only four are men what is the entropy of that set?

Or 0.9182. Now, if out of that set of five people with Ph.D.s, four were evil geniuses. What is the entropy there?

Or 0.6883. That lower number means that it requires less information to encode that the evil geniuses of the log have a Ph.D. If you run the math for entropy, it will be zero when everything in a set has the same type and exactly 1 when its a 50/50 split. Looking something like this:

(Image generated from Wolfram Alpha.)

So the entropy for a homogenous set is lower than that of a mixed set. This is important because in our decision tree we want to narrow the data into more specific values – so we can make predictions more accurately.

Information Gain

Now that we know how to measure how homogenous a set of data is, how do we go about deciding the best attribute to branch on? That is, do we branch on gender, has a Ph.D., or some other attribute? To calculate this we can use the information gain function defined as:

Given a set of values, S, and an attribute of each datum in that set, A, determine how much information has been gained by branching on that attribute. Note that Sv is the subset of values S where each element has attribute value v.

So what is the information gained by putting our root branch at ‘has a Ph.D'.’ or not?

Or 0.2002. If we calculated the information gain from branching on gender, the result is –0.0513. So the math backs up our assertion that Ph.D. is a more significant factor in determining evil genius than gender. (Which makes sense since 4/5ths of the Ph.D.s are evil, whereas only 2/25ths of the non Ph.D.s are evil.)

Putting it Together

In Part II we’ll implement the ID3 algorithm in F#, which generally goes through the following process:

Find the attribute that leads to the most information gain.
Add a branch for that attribute.
For each child node, repeat until all the data have the same classification.

The Visual Studio 2010 and .NET Framework 4 Training resources

Sat, 31 Oct 2009 12:12:33 GMT

NET Framework 4 Training Course includes videos and hands-on-labs designed to help you learn how to utilize the Visual Studio 2010 features and a variety of framework technologies including: C# 4.0, Visual Basic 10, F#, ...

Planet F#

F# Discoveries This Week 11/09/2009

Chris Smith’s Decision Trees Part 1 and Part 2

Steve Gilham’s F# under the covers parts 1, 2, 3, 4, 5, 6, and 8

Lessons learned in porting C# to F# (WPF)

Motivating F# equality and comparison constraints

What are structural equality and comparison?

What problem do F# equality/comparison constraints solve?

Does this really need a language feature?

When do I need to worry about any of this?

F# under the covers VIII

Technical analysis indicators in F# – Part II

And also …

A Great Blog Series on Algorithmic Programming in F#

Equality and Comparison Constraints in F#

"Getting started" with NaturalSpec – (Updated 08.11.2009)

1. Choosing an IDE

2. Installing the testing framework

3. Installing F#

4. Downloading the latest version of NaturalSpec

5. Creating a spec

Summary

Observing global hotkeys in C# / F#

Technical analysis indicators in F# – Part I

And also …

F# for Visualization 0.4.0.2 released

Custom WPF Controls in F#

F# 1.9.7 Language Specification Now Available

F# under the covers VII

Discriminated Unions in F#

An RSS Dashboard in F#, part one

Setting goal for the app

Brian’s RSS Dashboard

Technology overview

For next time…

Awesome F# - Decision Trees – Part II

F# Discoveries This Week 11/02/2009

-- Events --

-- Posts --

and Julien’s An immutable Queue Library in F#

Turning AutoCAD into a Spirograph using F#

Thinking about ECNs, WF, Oslo State Machine, F# and Task

An immutable range library in F#

And also …

Some quick F# notes…

Awesome F# - Decision Trees – Part I

Defining the Problem

The Approach

Enter the Mathematics

Entropy

Information Gain

The Visual Studio 2010 and .NET Framework 4 Training resources