Inside F#

Brian's thoughts on F# and .NET

Archive for November, 2009

Another quick aside…

Posted by Brian on November 9, 2009

If you haven’t seen the new Visual Studio branding, you should check it out!  I really like the new look.  Here’s F#:

VisualFSharpLogo

Of course, for a slightly different take on the logo, see Chris’ recent blog post.  :)

(There’s been quite a bit of F# blogging activity of late; as always, check out the F# dev center for links to lots of content!)

Advertisements

Posted in Uncategorized | Leave a Comment »

Motivating F# equality and comparison constraints

Posted by Brian on November 8, 2009

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

or

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.

Posted in Uncategorized | 2 Comments »

An RSS Dashboard in F#, part one

Posted by Brian on November 2, 2009

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 build 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):

RssDashboardScreenshot

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!

Posted in Uncategorized | 1 Comment »

Some quick F# notes…

Posted by Brian on November 1, 2009

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:

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…

Posted in Uncategorized | 1 Comment »