hubFS: THE place for F#

Download F# in Visual Studio 2010 Beta2, or matching F# CTP Update for VS2008

dsyme — Mon, 19 Oct 2009 21:37:00 GMT

F# in Visual Studio 2010 Beta2, plus matching F# CTP Update for VS2008 The latest release of F# is now out! See the post on Don Syme's blog. ...(read more)

hubFS: Email Notifications

optionsScalper — Sat, 10 Oct 2009 14:22:00 GMT

Spammers are a constant issue when running a public site. I've taken normal precautions and the site seems relatively clean. Unfortunately, some of the spammers expect reply emails to undeliverable addresses. This has caused my hosting service some issues with email blacklisting.

I've disabled email notifications until I can find a more suitable approach to this problem. I'll be trying another provider for my SMTP services as a first attempt, but I will likely need a more general approach as to how to deal with email replies to illegitimate users.

In the meantime, please email me with concerns, suggestions, etc. I would especially like to hear from you if you feel this is critical to your usage of hubFS. Send to:

os #at# jjbresearch.org

with the subject line containing "HubFS EMAIL".

Thanks for your patience.

Introducing F# - Four part webcast series

tomasp — Tue, 16 Jun 2009 00:32:00 GMT

Now that Visual Studio 2010 Beta 1 is out, it is finally a good time to take a look at one of the (in my opinion) most interesting new features in the new release - the F# language. As all the regular hubFS readers know, F# existed for quite a long time now as Microsoft Research project, but is now becoming a real Microsoft product. Interestingly, F# is still available as a plugin for Visual Studio 2008, so if you want to try it you don't have to install the whole new beta of 2010.

There are already many resources for learning F# including my functional programming overview, which is a Manning Greenpaper for the book Functional Programming for the Real World that I'm writing with Jon Skeet and my four-part F# introduction. There are also some useful links on the official F# web site including some talk recordings. However, I haven't yet seen any good F# webcast focusing mainly on showing F# source code, starting from simple functional concepts to the real-world features like asynchronous workflows and object-oriented programming in F#, so I decided to create one.

(The whole webcast series is available in my other blog and I'm cross-posting the links and brief descriptions of each of the parts here)

The F# development process

The webcast starts by experimenting with F# and by introducing some of the essential functional concepts and then follows the usual F# development process. It starts by creataing an empty F# script (New File... - F# Script File in Visual Studio), which is the easiest way to start coding in F#. We'll just create an empty script, start writing the code and run it interactively to see how it works. This way, we'll develop a very simple F# snippet for downloading content of a RSS feed and for searching for feeds that contain the specified keyword.

Once we have a simple solution to the problem, we can start improving it and refactoring it in various ways. I believe that refactoring is a very important part of the usual F# development process. In particular, we'll see how to wrap the code into asynchronous workflows to make it run asynchronously (rather than using blocking calls) and also potentially in parallel (rather than downloading and processing all the feeds in sequence).

Finally, in the last part of the series, you'll see one more refactoring. We'll wrap the existing code into a simple object oriented library and we'll also finally turn it from a simple F# script file into a standard .NET DLL library that can be used from C#. As you'll see in the webcast, this is again a relatively simple refactoring that includes only a couple of minor changes in the source code. Once we'll compile the library, we'll also look how to use it from C# and in particular, from a simple ASP.NET web application.

Introducing F# webcast

The links to the individual parts of the webcast are available here. Each of the articles also contains link for downloading the video (in case you wanted to view it offline) and also full source code that I wrote during the presentation:

Part I. - Introducing functional concepts
The first part introduces functional programming principles such as immutability, recursion and functions that take other functions as parameter (higher order functions). This can all be demonstrated in C# 3.0, so we start with C# and then look how the same concepts look in F#. Finally, the first part also shows functions for working with lists in F#.
Part II. - Using standard .NET libraries
The second part demonstrates how we can use standard .NET libraries. It uses classes from System.Net and System.Xml to download content of a web page (RSS feed), load it into XML document and process it to find only posts that contain some specified keyword.
Part III. - Downloading web pages asynchronously
The third part shows how to make the code from the part II. better. It introduces F# asynchronous workflows that can be used for writing code that doesn't block a thread when waiting for the completion of some I/O request. This part also shows how to modify the code to download and process multiple feeds in parallel.
Part IV. - Developing standard .NET libraries
In the fourth part, we look how to encapsulate the functionality written in F# into classes. We'll create a project and we'll wrap the code we wrote into a .NET class. We'll also look how to compile the project into DLL and how to use it from a simple C# web application.

Visual Studio 2010 Beta1 with F# is now available, plus matching F# CTP Update for VS2008

dsyme — Wed, 20 May 2009 19:53:00 GMT

Cross posted from blogs.msdn.com

The F# team are thrilled to announce that Visual Studio 2010 Beta1 is now available , including the latest version of F#. Today we are also releasing a matching F# May 2009 CTP for use with Visual Studio 2008 (MSI, ZIP). Further below is a screen shot, more here.

If you’re new to F#, consider watching the PDC presentation on F# by Luca Bolognese, and the live demo of F# and other new language technologies at JAOO by Anders Hejlsberg, Where are Programming Languages Going, or else download, start playing and take the MSDN walkthrough of F# in Visual Studio 2010.

This release is a landmark in the process of making F# a language officially supported by Microsoft, being the first release where F# installs as part of Visual Studio 2010. Using Visual Studio 2010 you can build F# applications for .NET 4.0 Beta1, which has been released today. Likewise, using the F# CTP Update for Visual Studio 2008, you can build F# applications for .NET 2.0/3.0 and 3.5. The F# language itself is the same in both releases, with some additional library functions (e.g. Array.Parallel.map) available with .NET 4.0/Visual Studio 2010 Beta1 (see the detailed release notes).

As with our previous CTP release, one team focus of the last 6 months has been on refining the F# language and taking feedback from the wonderful and growing F# community. For example, we have now made the F# lightweight syntax option the default for the language (i.e. for .fs/.fsi/.fsx files). We have added support for custom numeric type literals, which allows F# to interoperate nicely with the BigInteger type on .NET 4.0, and have improved aspects of .NET interoperability such as smoother calling of .NET param array methods. You can also use F#'s support for units-of-measure with integer types, e.g. to qualify integer types by annotations such as <Pixels> or <Clicks>. Additionally, we have been focusing on the performance of F# language constructs in this release. In particular, we have made performance improvements to F# sequence expressions, using a state machine compilation for sequence expressions that provides substantial performance improvements for code that generates data using these constructs. Similarly, if you disassemble some F# code you will notice that F# classes have compact representations, and that some other constructs such as F# members taking arguments in curried form are compiled more efficiently. Taken together our aim has been to ensure a predictability in the performance characteristics of related language constructs. More detail in the detailed release notes.

One area we have done considerable work is the F# library, and existing users will notice this when they move their code to this release. The consistent feedback we've had is that the F# library support must be consistent , powerful and simple to use. As a result, we have completed an end-to-end review of the library and made some revisions to ensure standard naming conventions and standard, simpler operator names . The library also now uses uppercase type variable names. More details are available in the detailed release notes, including details of two small breaking changes and some simple ways to cope with these. The Visual Studio 2008 release also provides versions of FSharp.Core.dll to use when developing F# applications for Silverlight 2.0 and the .NET Compact Framework 2.0/3.5.

This release also sees major improvements in F# debugging. First, in Visual Studio 2010 F# benefits from amazing new technology such as time-travel debugging (ok, it’s officially called historical debugging, but I grew up in the eighties). This a product-quality realization of a long term dream of many language implementations. Next, in both Visual Studio 2008 and Visual Studio 2010 you will see major improvements in data visualization for F# language constructs such as records and discriminated unions and F# library types such as lists, maps and sets. Breakpoint and stepping have also greatly improved, and in Visual Studio 2010 breakpoints can be more accurately positioned inside lambda functions. Some library support also aids in adhoc debugging, e.g. the printf format "%+A" can now be used to print the private, internals of and F# structured object (when running code as full-trust), and a width parameter can be specified to fit the formatted text within a visual display, e.g. "%+128A".

We have not neglected the F# Language Service and F# Project System. For example, when you build from Visual Studio you will notice that the error list is now populated with errors from the build process. We have also made many performance and reactivity improvements to the F# language service, eliminating points where the Visual Studio user interface became less reactive due to background computations and increasing the number of cases where intellisense is made available. There are also nice additional touches for scripting with F#, such as hovering over a #r declaration now reveals the exact resolution of an assembly reference.

Next, we now have preliminary documentation for the F# language on the MSDN website (yippee!). These are preliminary, and yes there are glitches, so please have patience and send us your feedback J There is also a minor known bug in the walkthroughs where the code snippets all have extra leading whitespace. Since F# is whitespace-significant by default, be sure to delete this leading whitespace when copying snippets. These new docs are another good F# reference, as well as a resource for getting started with the language.

Finally, we have done considerable work towards aligning F# with .NET 4.0 additions , with the aim of ensuring a long, bright, compatible future for functional, reactive and parallel programming on the .NET platform. For example, you will see that when using .NET 4.0, F# record, tuple and union types now implement the .NET 4.0 standard types IStructuralEquatable and IStructuralComparable. Furthermore F# tuples are compiled using the standard .NET 4.0 type System.Tuple. We've also added some lovely operators to the F# library for .NET 4.0, in the Microsoft.FSharp.Collections.Array.Parallel module, building on the .NET Parallel Extensions library. For example Array.Parallel.map can be used to perform a parallel map of a function over a large data array. Finally, you'll notice the addition of Async.CreateAsTask and the extension property .AwaitTask as ways to create and wait for .NET 4.0 tasks, meaning you can program .NET tasks directly using the F# asynchronous programming support!

Details of all this and more is in the detailed release notes, and look for more blogging by the F# team and community about all this and more. As always we are very glad to hear your feedback on all aspects of F#, and the above updates especially. We trust you enjoy your F# programming!

Don Syme, for the F# team

hubFS: Downtime notification

optionsScalper — Fri, 10 Apr 2009 08:18:00 GMT

I've been informed by my hosting provider that the data centers where hubFS is hosted will be having scheduled maintenance, potentially causing downtime.

This maintenance will occur Friday evening (4/10/2009 after 5pm CDT) and Saturday Daytime (4/11/2009). While I don't have exact times, the outage is expected to be minimal and is unavoidable.

My apologies in advance for the short notification and any issues that arise. Leave comments on this post for any conditions that I can address if the downtime has affected posts.

My book: Real-world Functional Programming in .NET

tomasp — Wed, 05 Nov 2008 01:09:00 GMT

(This article is based on two articles about the book that I posted to my other blog).

If you’ve been reading my blog or seen some my articles, you know that I’m a big fan of the F# language and functional programming style. I’m also often trying to present a bit different view of C# and LINQ – for me it is interesting mainly because it brings many functional features to a main-stream language and allows using of many of the functional patterns in a real-world. Elegant way for working with data, which is the most commonly used feature of C# 3.0, is just one example of this functional approach. Talking about real-world applications of functional programming, there is also fantastic news about F#. It was announced last year that F# will become fully supported Visual Studio language and the first September CTP version of F# was released recently!

I always thought that the topics mentioned in the previous paragraph are really interesting and that functional programming will continue to become more and more important. That’s why I’m really excited that I have the privilege to write a book about these topics. The book is called Real-world Functional Programming in .NET [^] and it’ll be published by Manning Publications [^]. Even though there are some books about F# already (and more are probably comming soon), I believe that my book is unique in a way that it talks about both C# and F#. This is useful when understanding functional programming concepts, because you can see how would the same thing look in C#. Also, there are many functional techniques that can help you with daily C# programming and these are also discussed in the book. Here is a couple of reasons why you should have this book on your bookshelf:

Ideas behind C# 3.0 and LINQ - these main-stream technologies are inspired by functional programming and the new C# 3.0 features give us definitely much more than just a new way to query databases. The book explains the ideas behind these features and shows how to use them more efficiently in a wider range of scenarios.
Learning the F# language - F# is becoming a first-class citizen [^] in the Visual Studio family of languages, which alone would be a good reason for learning it! Even if you're not going to use it for your next large .NET project, you'll find it useful for quick prototyping of ideas and testing how .NET libraries work thanks to the great interactive tools.
Real world examples - the book includes a large set of real-world examples that show how to develop real .NET applications in a functional way - both in F# and C#. Among other things, the examples show how to utilize multi-core CPUs, how to better obtain and process data and how to implement animations and GUI applications in a functional way.

To summarize, the goal of the book is to explain the key ideas of functional programming to real world .NET developers in a way they can benefit from them. It actually very much follows my personal experience – I started seriously looking at functional programming in the F# language after using primarily C# for quite a long time.

What's new?

Here is a couple of links if you're interested in more information about the book. I started a companion web site for the book, so you'll find everything regarding the book, links to related articles and the source code here: www.functional-programming.net. There is a book page at Manning web site where you can find the direct links to the free content (Chapter 1 and the Greenpaper) and also the option to purchase the book via MEAP today:

First four chapters are already available via Manning Early Access program.
First chapter titled "Thinking differently about problems" is available for free.
Greenpaper showing what you can expect to find in the book is available for free.
www.functional-programming.net - My web site about the book.

The MEAP program allows you to get the book now and start reading chapters as they become available. Once the whole book is completed, you'll get the final version (either electronic or both electronic and printed). This means that you'll be among the first people to see the draft and you also have a chance to influence it. I've been receiving a large number of great suggestions as well as corrections from the MEAP program via book forum at Manning [^], so huge thanks to anyone who is reading the book and discussing it there!

The MEAP version is updated every couple of weeks, so things has changed since I posted the announcement to my blog and I had to rewrite this paragraph. Currently, you can get first 10 chapters and I'm working on chapter 11, so you can see that there is very small delay (when I see some of the errors in the draft that readers report in the forum, I sometimes think that it is almost too small - thanks again)!

About a month ago, the MEAP version of the book was first in the list of Manning bestsellers (even before books on topics like ASP.NET "MVC" and Silverlight, which was a very nice surprise for me)! Click on the image to see the full-size screenshot:

What’s inside?

The most interesting thing for me about writing the book is that I really had to shape my ideas very clearly and find a good way to organize all the topics. One point of view that I found particularly useful (and it reflects how I write code in F#) is that F# gives you a way to start with a very simple, easy to write and clear code and later turn it into a robust .NET code. At the beginning you can write your code just as a script for F# interactive using only the basic functional features. Thanks to the type inference the code is also very succinct. In the later phase you can use features like abstract interface types and object expressions to organize the code and make it easily accessible for example from C#. The nice thing is that the transition is very smooth, so you don't have to rewrite almost any code.

Since many of the functional features are now available in C# 3.0, it is possible to apply some of these ideas to C# too. In particular, we can simplify many object-oriented constructs (including some well known design patterns) and also use many effective functional techniques. This way of thinking is very suitable for a book, because we can start by looking at simple and clear ideas and then learn more sophisticated techniques and language features. The chapters that are currently written follow this organization. Here is a brief overview of the content of every chapter:

Part I. Introduction

To many of the readers, functional programming is a completely new idea. The basic principles of functional programming are also quite different to what you may be used to. The first part of the book (containing chapters 1 - 4) serves as an introduction and touches lightly some of the ideas that will later become essential.

Chapter 1: Thinking differently about problems starts with a little section about the long history of functional programming (By the way, would you believe that the first functional programming language celebrated its 50 years in 2008?). As a next thing, the chapter discusses some important reasons why functional concepts are important nowadays and shows successful real world applications of these concepts. The largest part is a tasting of what you'll find later in the book and finally, it contains a section showing the first example application in F#.
- The chapter is available for free from the Manning book page [^].
Chapter 2: Functional concepts and programming languages introduces the concepts behind functional programming. As I already mentioned many of the functional concepts are different then what you might be used to, so this chapter gives a brief overview (without any details) showing how functional concepts relate and what they mean for the program structure.
Chapter 3: Meet tuples, lists and functions in F# and C# finally shows some real functional code. In this chapter, we use both C# and F# when writing any code, which makes it easier to understand what the functional program does. It demonstrates some basic data types used in F# (such as tuples and lists) and also shows how they can be implemented in C#. This chapter also introduces the idea of using functions as values, which is one of the key functional concepts.
Chapter 4: Exploring F# and .NET libraries by example presents the first real world application implemented in F# and shows how to use various .NET and F# libraries from the F# language. We look at an application that loads data from a file and presents them in a graphical form using a pie chart. This chapter finishes the introductory part by presenting the F# language by example, using only basic features from Chapter 3.

Part II. Core functional techniques

The second part starts describing the "iterative development style" enabled by functional programming in F#. It discusses elementary ways used to construct functional programs. These give us a very clear and concise way to think about problems. Finally, in the later chapters it talks about functional applications from a higher perspective focusing more on architectural acpects.

Chapter 5: Creating and using common functional values - in functional programming, applications are described more like calculations that take some values as arguments and return a value as a result. This chapter explains what values actually are and talks about usual ways to construct them. This includes representing multiple values, alternative values and also functions (which are values too).
Chapter 6: Working with values using high-order functions introduces better way for working with basic values from Chapter 5. Instead of manipulating with them directly, we can factor out the changing part of some common operation and then use the single function for many varying tasks. This talks mainly about using functions as arguments, which is also very important for C# 3.0, which supports lambda functions.
Chapter 7: Designing data-centric programs - when designing an application in the functional style, we start by thinking about the data that it works with. This principle is very useful and clear independently of the language that you're actually using. In this chapter, we demonstrate this principle and also show how it relates to some well-known structural design patterns.
Chapter 8: Designing behavior-centric programs - not all applications are primarily focused at working with data as described in Chapter 7. Here we talk about the second types of applications. Using functional terminology, this chapter talks about functions in detail. In the object oriented terminology, we look at some behavioral design patterns like Strategy or Command.

Part III.

This section focuses on more advanced concepts that are used later in the "iterative development style". Once the application or a library grows larger, we want to use various .NET facilities to organize it intuitively, expose it to other .NET languages and document it. If the library is intended only for F# then we can leverage of some advanced F# features. Finally, we also want to make the code more efficient by using general functional and F# specific optimization techniques.

Chapter 9: Turning values into F# object types with members shows how to mix object-oriented and functional style of programming in F#. It shows how the functional concepts (like immutability) can be used well together with object oriented features like encapsulation and how the conceptually simple ideas from Chapter 7 and 8 can be wrapped into real-world .NET code.
Chapter 10: Efficiency of data structures, tail-recursion and continuations - in the earlier chapters we talked about recursion and data structures such as lists or trees. In this chapter, we look how to use them efficiently. This means how to avoid stack overflow errors when writing functional code and how to write fast code that processes lists and other collections.
Chapter 11: Refactoring functional programs and using lazy values Refactoring is a phase of development where we try to improve our code without doing any changes in its behavior. This is a very important step and functional programming gives us great tools to do it. Function values are useful when removing code duplication and thanks to immutablity it is much easier to ensure that a change will not affect the behavior. Finally, lazy values allow us to delay some computations until their results are actually needed, which is a topic very close to refactoring.

These are all the chapters that I wrote already (Chapter 11 is not available yet, but I already know quite well what will be inside). I'll definitely blog about more chapters as I'll write them, so stay tuned for another update!

Looking for your feedback!

The book is still "work in progress", so I'm very glad to receive any feedback. I already got many useful comments and suggestions via the book forum at Manning [^], from the reviewers of the first third of the book and also from my colleagues and friends. However, this is probably the first book about functional programming that aims to a very wide audience of .NET programmers, requiring only advanced C# background, so any comments are more than welcome! You can post them to the forum mentioned above as well as directly to me at tomas@tomasp.net.

More information

Real-world Functional Programming in .NET [^] - book homepage
Manning: Real-world Functional Programming in .NET [^] - book page at Manning.Com
Forum dedicated to the book [^] - at Manning.Com

Amanda and Some Guy discuss F# on .NET Rocks!

optionsScalper — Tue, 16 Sep 2008 21:30:00 GMT

Amanda Laucher and Ted Neward talk about F# on a recently released .NET Rocks! podcast (episode 377). Richard and Carl pose a lot of tough questions. Amanda and Ted are up to the task and provide a great perspective on functional languages, OO, F#, .NET and many other things. While I don't really know Ted, I can only help to perpetuate the "Some Guy" reference in the podcast. Evidently Amanda and Ted are also working on a book "F# in a Nutshell".

Amanda can be found at Pandamonial.

Ted can be found at The Blog Ride.

Podcast is here.

Good stuff.

F# September 2008 CTP Released

optionsScalper — Fri, 05 Sep 2008 05:55:00 GMT

The F# Team has released the F# September 2008 CTP. Seeing F# followed by "CTP" is outstanding. Congratulations to Don Syme and his team for steady and consistent work to move F# to another milestone.

Read about it here.

Download it here.

"F# for Scientists" now available

dsyme — Thu, 28 Aug 2008 22:05:00 GMT

[ Cross posted from http://blogs.msdn.com/dsyme/archive/2008/08/28/f-for-scientists-now-available.aspx ]

I can't believe I missed posting about this - F# for Scientists is now out!

I haven't got my hardcopy just yet, but I read a draft of this book, and was impressed. The 3D visualization chapter is stunning in its simplicity and power, the parallel programming techniques presented are simple and powerful, and the examples of interoperating with Mathematica, MATLAB and using web databases opened gateways to the crucial information sources and tools that form a significant part of modern computational science.

Here's a snippet from an Amazon review attributed to Jamie Bernadin, who I understand is CTO of Data Synapse:

All round outstanding. I wish more books were written at this level of quality. While this book can be used by anybody that wants to get up to speed with F#, it's also well suited for use as a text book for an undergraduate course in applied math or computer science (or reference for a graduate course). It's well organized, well written, and draws from classic examples in mathematical computing. ...If you enjoy this type of stuff, it's an absolutely pleasure to read - logical in flow and well articulated. ... a must-have book if you're doing anything with F# - or just considering it.

The soon-to-be-released F# CTP will have some ground-breaking features for added power and correctness in programming in these domains - watch this space for more :-)

Don Syme

Concurrency on a single thread

gneverov — Sun, 03 Aug 2008 09:40:00 GMT

Introduction

F# has the async computation expression for writing parallel programs. Async achieves concurrency by using the CLR ThreadPool to queue work items for each logical thread created in an async expression (e.g., through Async.spawn or Async.parallel). Using the thread pool is good because it reuses existing threads instead of creating and destroying new threads. However the thread pool has limitations when a large number of threads are created that may result in deadlock (if queued work items don't execute because of blocked threads), increased memory usage, and poorer performance due to excessive context switching.

Suppose we want to write a parallel application that creates a large number of concurrently executing threads. Threads are good because they present a sequential control flow model that is easy to understand and reason about, and having a large number of threads facilitates better resource utilization. To do this we would like to implement our own scalable concurrent threading system for our application that uses virtual threads not backed by the CLR thread pool or OS threads. To enable scalability, the creation of virtual threads in the system will be cheap (about the cost of a newobj instruction) and not consume OS-level resources (and similarly for synchronization primitives also).

The implementation of this system will be based on the standard F# async: it will be a computation expression based on the continuation monad and the users' code will look similar and be functionally the same. However operationally it will be different from the standard async because it will use a fixed number of threads instead of the thread pool. (For version 1 in this post it will use only 1 thread, but a version 2 might extend that to 1 thread per CPU.)

You can download the F# code for this post here.

Scheduler

At the core of this new async monad is the thread scheduler. The scheduler makes multiple threads of execution and multiplexes them together to give the illusion of concurrency. The scheduler is entirely managed code and uses continuations to manipulate control flow. The state of the scheduler consists of three parts:

type Scheduler () =
val ready : LinkedList<unit -> unit>;
val pending : int ref

The ready queue is a list of continuations that represent threads ready to run. It is a LinkedList from the BCL to allow fast insertion/removal from the beginning and end of the list. The basic operation of the one real OS thread in the system is this loop below.

let rec loop () =
if ready.Count > 0 then
    let k = ready.Dequeue ()
    k ()
    loop ()

It checks to see if the ready queue is non-empty. If so, it removes the first continuation, executes it (which may modify the ready queue) and repeats. However asynchronous I/O operations complicate this simple algorithm.

Asynchronous I/O

An I/O operation (like reading or writing to a disk or network) can take a long time and during this time the CPU is idle. If we performed a blocking I/O operation on our one real thread then all virtual threads would be suspended – not good. Therefore it is imperative that the programmer using this async monad never uses blocking operations and always uses non-blocking I/O. Win32 supports non-blocking I/O called 'overlapped' I/O. The basic principle is that a thread makes a system call to start an I/O operation. The system call returns immediately before the operation is completed. The operation is performed by the OS and not on the process's thread. When the operation is complete, a callback is executed on one of the threads in the process. The key point here is that the non-blocking I/O operation didn't create or consume an OS thread, thereby by using this we can stick to our one-thread budget. Non-blocking I/O is exposed in the BCL through Begin/End methods on various I/O objects (FileStream, etc.) and on Windows these methods are probably implemented using Win32 overlapped I/O.

The pending field in the state of the scheduler contains the number of logical threads currently in an asynchronous I/O operation. So when ready.Count = 0 and !pending = 0 the computation has terminated.

The Monad

So let's get started looking at the code. Additionally this will also serve as a guide to writing (not-necessarily-concurrency-related) computation expression builders in F#. The monad used in this code is based on the papers by Classen and Li and Zdancewic.

The type of the monad used here is

type Async<'a> = Async of (Scheduler * ('a -> unit) * (exn -> unit) -> unit)

In general all F# monad types need to be function types to achieve the delayed evaluation implicit in a computation expression block. Furthermore you'd typically want to wrap this type in a discriminated union tag to aid type inference. Hence making the general form of a monad type

type M<'a> = M of (… -> …)

In the Async type the left of the function arrow takes three arguments: the state of the scheduler of type Scheduler, a success continuation of type ('a -> unit) and an exception continuation of type (exn -> unit).

The Scheduler type was mentioned above. The Scheduler state supports the following operations.

member QueueFirst : (unit -> unit) -> Lock<unit>
member QueueLast : (unit -> unit) -> Lock<unit>
member Dequeue : unit -> Lock<(unit -> unit) option>
member IncrPending : unit -> Lock<unit>
member DecrPending : unit -> Lock<unit>
member Run : Lock<'a> -> 'a

Since the Scheduler state will be accessed by two threads: the single application thread and the CLR IO completion thread, access to the data structure needs to be synchronized. This is done using the lock monad from my previous blog post.

Return & Bind

We now implement the standard return and bind operations for a continuation monad.

let mreturn x = Async (fun (sched, sk, ek) -> sk x)

let apply (Async m) (sched, sk, ek) = m (sched, sk, ek)

let bind m f =
Async (fun (sched, sk, ek) ->
apply m (sched, (fun x -> apply (f x) (sched, sk, ek)), ek))

The implementation of return is fine; however there is a problem with the implementation of bind because it does not take into account the possibility of exceptions. If the function f throws and exception then this must be caught somewhere and execution diverted to the exception continuation.

type Result<'a> = Success of 'a | Error of exn

let tryApply f x = try Success (f x) with e -> Error e

let apply2 f x (sched, sk, ek) =
match tryApply f x with
    | Success m -> apply m (sched, sk, ek)
    | Error e -> ek e

let bind m f =
Async (fun (sched, sk, ek) ->
    apply m (sched, (fun x -> apply2 f x (sched, sk, ek)), ek))

The tryApply function will always be used whenever applying an "outside" function (a function defined outside the async library) so that any exceptions thrown by this function can be reified as values and control flow handled appropriately.

Mzero & Mplus

Two primitive operations for the async monad are stop and fork. The stop operation terminates the current thread. The fork operation duplicates the current thread and returns different values on each. For example, if there is a thread executing the expression "bind (fork m1 m2) f" then after the evaluation of fork there will be two threads executing: one executing the expression "bind m1 f" and the other executing "bind m2 f". Fork is the primitive method for creating new threads in the async monad. The implementation for stop and fork are as follows.

let stop =
Async (fun (sched, sk, ek) -> ())

let fork m1 m2 =
Async (fun (sched, sk, ek) ->
sched.QueueLast (fun () -> apply m2 (sched, sk, ek)) |> sched.Run
apply m1 (sched, sk, ek))

Unfortunately calling stop stops the current thread without running any finally handlers that are in scope. Ideally there should be a third continuation (called the finally continuation) that is executed by stop, but we'll ignore this issue for now. The fork operation works by queuing the second branch of the fork at the end of the scheduler's ready queue and executing the first branch immediately. Stop and fork form the mzero and mplus operations of a MonadPlus type class instance for the async monad.

Yield

The yield operation forces the thread to give up its execution and re-queues itself at the end of the ready queue.

let myield =
Async (fun (sched, sk, ek) ->
sched.QueueLast sk |> sched.Run)

Callback

The callback operation is used to invoke asynchronous IO operations. In the CLR base class library, asynchronous IO operations are defined by two methods: a Begin method and an End method (e.g. for reading from a stream BeginRead and EndRead). These two methods are passed to the callback function below. This function first increments the schedulers pending count to mark the start of a new asynchronous IO operation. It then calls the Begin method passing the function cb as the callback. If the Begin method was successful then this thread yields, otherwise the pending count is decremented and the exception continuation invoked. When the system has performed the IO operation it calls cb on some special thread (not the scheduler's thread). Therefore cb cannot continue execution of the continuation monad; instead it must marshal a continuation back onto the scheduler's ready queue. So it first calls the End method to get the result of the IO operation. If the IO operation failed for some reason then can exception will be thrown in this call. Depending on the success of End, either the success or exception continuation is chosen and queued at the front of the ready queue. The pending count is decremented and the lock is pulsed to wake up the scheduler thread which may be blocking waiting for new continuations to execute.

val callback : (AsyncCallback -> IAsyncResult) -> (IAsyncResult -> 'a) -> Async<'a>
let callback (beginFunc : _ -> IAsyncResult) endFunc =
Async (fun (sched, sk, ek) ->
    let cb (ar : IAsyncResult) =
      let k =
        match tryApply endFunc ar with
        | Success x -> fun () -> sk x
        | Error e -> fun () -> ek e
      lock { do! sched.QueueFirst k
             do! sched.DecrPending ()
             return! Lock.pulseAll } |> sched.Run
    sched.IncrPending () |> sched.Run
    match tryApply beginFunc (AsyncCallback(cb)) with
      | Success ar -> ()
      | Error e -> sched.DecrPending () |> sched.Run
                   ek e)

Run

Finally, we need to run function to execute the async monad. The run function creates a new scheduler and a place to store results. When executing, an async computation may create multiple threads that terminate successfully (viz. without calling stop) and thereby producing multiple results (and exceptions). Therefore the result of executing an async computation is a list of Result values. An initial continuation is added to the ready queue that runs the target monad with success and exception continuations that add respectively to the result list. Continuations are then dequeued and run iteratively until there is no more work to do.

let run m =
let sched = new Scheduler()
let result = ref []
let init () = apply m (sched, (fun x -> result := Success x :: !result), (fun e -> result := Error e :: !result))
sched.QueueFirst init |> sched.Run
let f () = sched.Dequeue () |> sched.Run
for k in Seq.unfold0 f do k ()
!result

Many applications however will expect a single result from an async computation, so the runOne function is also created to only return the first result.

let runOne m =
match run m with
    | [] -> failwith "no value"
    | Success x::_ -> x
    | Error e::_ -> raise e

Synchronization

There needs to be some way for threads within an async computation to synchronize with each other. We can't use the CLR's synchronization primitives because they will block the scheduler thread; therefore we need to create our own. So we will create a manual reset event (and leave an auto reset event as an exercise for the reader).

A manual reset event will be represented as an optional list of continuations. A value of None means that the event is in the signalled state. A value of Some ws means that the event is in the non-signalled state and the list ws contains the continuations waiting for the event to become signalled. Hence a value of Some [] means that the event is not signalled but no one is waiting on it. The type of a manual reset event is

type MRE = MRE of (unit -> unit) list option ref

To create a new MRE in the specified state

let newMRE state = if state then MRE (ref None) else MRE (ref (Some []))

Waiting on a MRE causes its state to be analysed. Access to the MRE's internal mutable state does not need to be synchronized because there is only one real thread in the system. If it is signalled then the success continuation can be invoke immediately. If it is not signalled then the success continuation is added to the wait list and the thread yields.

let waitMRE (MRE mre) =
Async (fun (sched, sk, ek) ->
    match !mre with
      | None -> sk ()
      | Some wait -> mre := Some (sk :: wait))

When setting an MRE, its state is again analysed. If it is already signalled then do nothing. Otherwise set the state to signalled and add each of the continuations in the wait list to the ready queue. Finally, regardless of the initial state, the success continuations in executed since setting an MRE is a non-blocking operation.

let setMRE (MRE mre) =
Async (fun (sched, sk, ek) ->
    match !mre with
      | None -> ()
      | Some wait -> mre := None
                     Lock.iter (sched.QueueFirst) wait |> sched.Run
    sk ())

As well as auto reset events, other synchronization primitives can also be defined, such as MVars.

Creating threads

In many applications fork is not a particularly intuitive operation. A spawn operation that takes an async computation executes it on a new thread and then ends that thread is more intuitive in many scenarios. We can write a spawn operation in terms of the primitives we have already defined.

let spawn m =
async { let join = newMRE false
          return! fork (mreturn join)
                       (async { do! tryWith m (fun _ -> mreturn ())
                                do! setMRE join
                                return! stop }) }

spawn starts by creating a new MRE that will be used signal the end of the spawned thread. It then forks. To one thread it returns the MRE so the caller can synchronize on the completion of the spawned computation. The other thread executes the target computation expression, ignoring any exceptions raised, signals the MRE and terminates.

One of the most useful async operations is parallel which takes a list of computations, executes them all in parallel and returns a list of their results.

let parallel ms =
async { let results = Array.zero_create (List.length ms)
          let task = fun i m ->
            async { let! x = m
                    return results.[ i ] <- x } |> spawn
          let! joins = mapi task ms
          do! iter waitMRE joins
          return results |> Array.to_list }

parallel first finds the length of the list and allocates an array to hold all the results. It then creates a task for each element in the list that executes the async computation and stores its result in the corresponding position in the results array. Spawning all these tasks produces a list of MREs which are used to wait for all the tasks to complete. When all the MREs have been signalled the function returns the list of results.

Another useful control flow operation is first that evaluates a target computation (which may fork) but continues only with the first thread that completes. It creates a new ARE in the signalled state. The first thread that completes the computation will reset the ARE and return the result. Other threads will see the non-signalled ARE and terminate.

let first m =
async { let once = newARE true
          let! x = m
          let! b = tryWaitARE once
          if b then return x
          else return! stop }

Conclusion

This blog post is already long enough so I'll stop it here before covering applications. In the code download you can find examples of a web crawler, image resizer and the concurrency example from this paper by Haller and Odersky. Two natural extensions to the system presented here are making the scheduler (1) multi-threaded and (2) distributed. Using .NET binary serialization it should be possible to serialize the continuations as delegates and send them to a different process/host. Additionally the STM monad could be built-in under the continuation monad as the primitive means for blocking, synchronization and inter-process communication.

Investing in F# - Making the tools and language better still

dsyme — Sat, 26 Jul 2008 16:50:00 GMT

The F# team at Microsoft Research and Microsoft are currently working hard towards our planned CTP release of F#. This is a follow up to the 1.9.4 release of F# as a research language.

When it comes, this release will be the first release that includes signficant improvements in the Visual Studio tools. Brian McNamara has been posting a few sneak screen shots of the project system in Visual Studio. Watch Brian's blog for more!

The project system isn't the only thing we're doing: we've done an end-to-end design review, some results of which appeared in 1.9.4, we've got improvements to F# Interactive in Visual Studio, and there are other improvements across the board, as well as some great new productivity features. We look forward to your feedback when we role this release out, and we know it will make your use of F# more productive still.

F# Support for ASP.NET and Notes on Samples

tomasp — Sat, 08 Mar 2008 22:36:00 GMT

(This article is cross-posted from http://tomasp.net/articles/aspnet-in-fsharp.aspx)

As I mentioned earlier, I spent three months as an intern in Microsoft Research in Cambridge last year and I was working with Don Syme and James Margetson from the F# team. Most of the time I was working on the F# Web Toolkit, which I introduced on the blog some time ago [1], but I also worked on a few additions that are now part of the F# release. Probably the most useful addition is a new implementation of the CodeDOM provider for the F# language which makes it possible to use ASP.NET smoothly from F# (but it can be used in some other scenarios as well) together with two ASP.NET sample applications that you can explore and use as a basis for your web sites. This was actually a part of the distribution for a few months now (I of course wanted to write this article much earlier...), so you may have already noticed, but anyway, I'd still like to write down a short description of these ASP.NET samples and also a few tips for those who're interested in writing web applications in F#.

F# and ASP.NET

Let's start by looking at the ASP.NET examples. You can find them in the samples directory in your F# installation under the Web/ASP.NET path. The directory also contains html files with description of the projects and a guide to configuring them, but I'll describe both of these topics in this post. The distribution contains two sample projects:

AspNetIntro - this project is (almost) the simples possible F# web site, so it can be used as a template for your web sites. It shows how to configure the CodeDOM provider, how to write a simple page with code-behind and how to use the App_Code directory and data-binding.
PersonalWebSite - this is a more complex web site ported from the C# sample called Personal Web Site Starter Kit [2]. It demonstrates many of the standard ASP.NET 2.0 techniques including data access controls, master pages, membership and custom HTTP handlers.

ASP.NET Introduction using F#

To start playing with ASP.NET you'll need to open the project (I recommend copying it to your working directory first). If you're using Visual Studio, you can select File - Open - Web Site... in the menu and select the directory with your project as demonstrated at Figure 1 below. The organization of ASP.NET projects is different than organization of ordinary F# projects - in ASP.NET the project is just a directory and it contains all the files in the directory (this is also the reason why you have to open it using a different command). The Figure 2 shows how the files of the ASP.NET Introduction project are organized in the Solution Explorer:

Figure 1: Open Web Site

Figure 2: Solution Explorer

As you can see, there are 6 files in the project. The Default.aspx.fs and Default.aspx together form one web page and the DataBinding.aspx.fs with DataBinding.aspx form the second web page. The App_Code directory contains application logic that can be used from other pages in the project and in our sample project it contains only one file (logic.fs). Finally, the web.config file contains configuration of the whole application.

Before we look at the pages you may want to check the web.config file, because it needs to contain the correct reference to the CodeDOM provider implementation including a version of the current F# installation. At the time of writing this article, the latest version is 1.9.3.14, but if you're not sure what version you are using, you can just start the fsi.exe from the F# installation which prints the version number. The web.config file is an xml file and it should contain the following content (with the right version number). The samples in the distribution should contain the correct version number, but the incorrect configuration is a common issue when working with ASP.NET in F#, so it is useful to know what the configuration should look like:

<?xml version="1.0"?>
<configuration><system.web>
<compilation debug="true">  
  <compilers>
    <compiler 
      language="F#;f#;fs;fsharp" extension=".fs" 
      type="Microsoft.FSharp.Compiler.CodeDom.FSharpAspNetCodeProvider, 
            FSharp.Compiler.CodeDom, Version=<strong style="color:red;">1.9.3.14</strong>, 
            Culture=neutral, PublicKeyToken=a19089b1c74d0809"/>
  </compilers>
</compilation></system.web>
</configuration>

Now, let's look at the Default.aspx and Default.aspx.fs files that together represent a simple page. The page contains one button and one label (a control that can display some text) and when the user clicks on the button, the result of some calculation is displayed in the label (the calculation is executed on the server-side). The following code is a (slightly simplified) content of the Default.aspx file, which defines the HTML markup together with the ASP.NET controls that are on the page:

<%@ Page Language="F#" 
  CodeFile="Default.aspx.fs" Inherits="FSharpWeb.Default" %>
<html>
<body><form runat="server">
  <asp:Button 
    ID="btnTest" RunAt="server" Text="Click me!" 
    OnClick="ButtonClicked" /><br />
  <asp:Label ID="lblResult" RunAt="server" />
</form></body>
</html>

You can easily identify two server-side controls, because these are written using prefix asp and also contain the RunAt="server" attribute, which means that the control is processed on the server-side. You can use standard HTML notation for setting attributes of the controls. We set the ID attribute to both of the controls, which is important because it allows us to use them in the code-behind code. The OnClick attribute of the button sets an event handler - a member of the FSharpWeb.Default type from the code-behind file that will be called on the server-side, when a user clicks on the button (which submits the HTML form and causes a page reload, so the event can be processed on the server). The file also contains the first special line, which tells the ASP.NET engine that the page is written in F# and it also tells what source file contains the code-behind code and what is the name of type declared in that file. The code-behind file (Default.aspx.fs) has the following content:

#light
namespace FSharpWeb
open System
open System.Web
open System.Web.UI.WebControls

type Default() =
  inherit Page()
  
  [<DefaultValue>]
  val mutable btnTest : Button

  [<DefaultValue>]
  val mutable lblResult : Label

  member this.ButtonClicked(sender, e) =
    this.lblResult.Text <- 
      (sprintf "Factorial of 5 is: %d" 
               (FSharpWeb.Logic.factorial 5))

As we can see, the file contains an F# object type (named Default), inherited from the base ASP.NET Page type. Thanks to the recent improvements in F# it is possible to write the type using the new implicit class syntax (note the parentheses after the type name), which means that you can place additional initialization code to the type declaration directly (following the inherit clause and F# will treat this as a constructor.

The class contains a mutable field for every control declared in the declarative markup with the name same as the ID attribute in the markup file (btnTest and lblResult). The ASP.NET initializes these controls automatically when it creates the page (that's why the fields are marked using mutable), so we don't need to initialize these fields in our code - F# doesn't usually allow uninitialized fields, but if you place the DefaultValue before the field declaration, it will be initialized to the default value (null), which is correct, because the field will be later initialized by the ASP.NET runtime. Finally, the type contains a member called ButtonClicked, which is a same name we used in the markup for the OnClick attribute of the button control. This is an event handler that will be called when user clicks on the button, it performs some calculation (the factorial function is declared in the logic.fs file) and sets a property of the other control that we have on the page.

Personal Web Site in F#

Figure 3: Personal Web Site

The second sample ASP.NET project is a port of quite a complex ASP.NET web site which also uses MS SQL database. The database can be created manually as described in Welcome.html in the PersonalWebSite directory, but I also uploaded the database to my web, so you can just download it and attach it in the SQL server (this is described below and the files for download can be found at the end of the article). The PWS_AspNetDb is a database managed by ASP.NET that contains user information - the database below already contains the required role (called Administrators) and one user (admin with password admin123!). The second database file (PWS_WebPersonal) contains the application data, mainly information about photos and galleries (as you can see from the screenshot in Figure 3).

The application uses many advanced ASP.NET features including the following:

Master Pages - the overall structure of the web site is stored in a master page (Default.master) and the other pages use the asp:Content control to fill the place holders in the master page.
Site Maps - the map of the web site is defined in the web.sitemap file and is used for generating the menu in the Default.master file.
Themes - the design of the page including CSS files and images are managed using ASP.NET Themes - there are two standard themes in the App_Themes directory.
Membership - the web uses standard ASP.NET technology for managing user accounts including the controls for manipulating with users (e.g. asp:CreateUserWizard control is used in Register.aspx file).
Data Controls - ASP.NET data-access controls are used for reading the data from the application logic layer (implemented as a module in F#)

Configuring the databases

To configure the databases required by the demo, you can either follow the steps described in the Welcome.html file (which is part of the sample project), or if you already have some version of SQL Server installed on your machine, you can download the sample databases below (a bunch of MDF and LDF files) and attach them to the SQL Server. I'll explain how to do this using full version of SQL Server, but the steps needed with Express edition are very similar.

Once you downloaded the files, you'll need to launch SQL Server Management Studio and connect to the server instance. After doing that you should see an "Object Explorer" window, where you can right click on the "Databases" group and select "Attach..." from the pop-up menu. In the opened dialog window, you can add the databases (by selecting the MDF file) and click the "OK" button to attach the databases. Finally, you'll need to modify the web.config file in the Personal WebSite sample to include the following section:

<connectionStrings>
 <add name="Personal" providerName="System.Data.SqlClient" connectionString=
      "Data Source=.;Integrated Security=True;Database=PWS_WebPersonal" />
 <remove name="LocalSqlServer"/>
 <add name="LocalSqlServer" connectionString=
      "Data Source=.;Integrated Security=True;Database=PWS_AspNetDb" />
</connectionStrings>

The Data Source parameter in the connection string specifies the instance of the SQL Server, where the databases are attached. By default this is the name of your computer (which can be written shortly using dot "."). When using the SQL Express the default instance name is ".\SQLExpress". The Database parameter specifies the name of the database, which you can see in the "Object Explorer" in the SQL Server Management Studio. After following these steps, you should be able to run the demo application.

Data-access in F#

Most of the ASP.NET technologies used in the web site are used in almost the same way as in C#, so I will not discuss them in larger details, but the last item in the list - the use of ASP.NET data controls together with F# is I believe quite interesting, so I'll write a few notes about it. Let's look for example at the Photos.aspx file, which displays a list of photos in a gallery. The most important parts of the file related to data access are shown in the following code snippet:

<asp:DataList RunAt="server" DataSourceID="photoSource" EnableViewState="false">
<ItemTemplate>
  <!-- ... -->
  <a href='Details.aspx?AlbumID=<%# base.Eval("PhotoAlbumID") %>'>
    <img src="Handler.ashx?PhotoID=<%# base.Eval("PhotoID") %>&Size=S" 
      class="photo_198" style="border:4px solid white" 
      alt='Thumbnail of Photo Number <%# base.Eval("PhotoID") %>' />
  </a>
  <!-- ... -->
</ItemTemplate>
</asp:DataList>

<asp:ObjectDataSource ID="photoSource" RunAt="server" 
  TypeName="PersonalWebSite.PhotoManager" 
  SelectMethod="GetPhotos">
  <SelectParameters>
    <asp:QueryStringParameter Name="AlbumID" Type="Int32" 
      QueryStringField="albumID" DefaultValue="0"/>
  </SelectParameters>
</asp:ObjectDataSource>

The first ASP.NET control used in the code is asp:DataList, which is a control that simply displays a collection of some items and uses a specified ItemTemplate for displaying every single item. In our case we're working with collection of records and the record has several members (including PhotoID and PhotoAlbumID). To display a value of a record member in the ASP.NET page we have to use ASP.NET Eval method as you can see in the sample. The Eval method reads the specified member of the item in collection and writing the code in <%# ... %> tells ASP.NET that we want to render the result of the expression as a part of the item template. The record that we're using in this example is very simple and has the following structure:

type Photo = 
  { PhotoID:int; 
    PhotoAlbumID:int; 
    PhotoCaption:string; }

This is actually one of the places where the F# version is shorter, because in C# version you have to write this as a class with properties, which makes the code quite longer.

The second server-side control (asp:ObjectDataSource) in the first code snippet isn't visual, which means that it will not produce any HTML output. It serves just as a declarative data-source for the data list and the properties of this control specify how the content for the data list should be loaded. There are various other data-source controls in ASP.NET (e.g. asp:SqlDataSource which loads data directly from the database), but the one that we're using in the example uses a specified .NET/F# type and calls a method of the given object when it needs to retrieve the data. In F# this is even easier, because we can use a name of the module and the code that retrieves the data can be a function in the module.

As you can see the property TypeName is set to PersonalWebSite.PhotoManager, which can be treated as a module called PhotoManager in a namespace PersonalWebSite and the SelectMethod property, which specifies a name of the function that will be called when loading the data is set to GetPhotos. Finally, the SelectParameters specifies that the function expects one argument called AlbumID and that the value of this argument should be retrieved from the query string (that is from the URL of form photo.aspx?albumIdD=42).

Now it is pretty easy to implement the module that matches this specifications and can be used as a data source (we could of course use FLinq for loading the data, but I wanted to keep things simple for now, so we're using standard SqlDataReader object from .NET):

namespace PersonalWebSite
// ...

module PhotoManager = 
  // Function will be called by ASP.NET when loading data
  // for the asp:DataList control in the 'Photos.aspx' page
  let GetPhotos (albumID:int) =
    // Open connection & create command
    use conn = new SqlConnection(" ... ")
    use cmd  = new SqlCommand("GetPhotos", conn)
    
    // Can the user see 'private' photos?
    let usr = HttpContext.Current.User
    let filter = not (usr.IsInRole("Friends") || usr.IsInRole("Administrators"))
    cmd.CommandType <- CommandType.StoredProcedure)
    cmd.Parameters.Add(SqlParameter("@AlbumID", albumID)) |> ignore
    command.Parameters.Add(SqlParameter("@IsPublic", filter)) |> ignore
    conn.Open()
    
    // Read all photos into a .NET ResizeArray type
    let list = new ResizeArray<_>()
    use reader = command.ExecuteReader()
    while (reader.Read()) do
      list.Add({ PhotoID = unbox (reader.get_Item("PhotoID")) 
                 PhotoAlbumID = unbox (reader.get_Item("AlbumID")) 
                 PhotoCaption = unbox (reader.get_Item("Caption")) }) 
                 
    // Return the created collection
    list

I hope this article explained some of the interesting things that you may find in the ASP.NET samples provided with the F# distribution and I think that the Personal WebSite Sample shows that F# can be used for writing quite complicated web applications as well. Of course, my initial motivation for writing web applications in F# is the possibility of using meta-programming to develop client-side code (the code that runs on the client as a JavaScript) in F# too, which makes development of modern "Ajax"-style applications easier, so if you're interested in this project you may want to look at F# Web Tools [1].

Downloads & References

Download PWS Database Files (9.65 MB)

[1] F# Web Toolkit: "Ajax" applications made simple [^] - Blog | TomasP.Net
[2] Visual Web Developer Express: Samples and Starter Kits [^] - Microsoft.Com

Using computation expressions to control monitor locks

gneverov — Sun, 17 Feb 2008 13:40:00 GMT

Using computation expressions to control monitor locks

C# has the lock statement to support the use of .NET monitor synchronization.

lock(this) { x--; }

This curly-brace delimited block of atomic statements is easily identified in code. However having to call Wait or Pulse inside the block is less appealing because this previously hidden Monitor class now comes to your attention and you have to make sure you wait/pulse on the same object that was locked.

lock(this) { x--; if(x==0) Monitor.Pulse(this); }

F# has the lock function which is basically a higher-order function version of C#'s lock statement. It has the same un-niceness with wait/pulse, plus you have to construct the body of the block into a function, and to me braces {…} look better than the verbose (fun () -> …).

lock this (fun () -> decr x; if x=0 then Monitor.Pulse(this))

We can solve all these issues and more with computation expressions in F#. We start by defining the Lock monad, which is actually just an instance of the reader monad. A value of type Lock<'a> is a computation that will execute under the context of a lock and return a result of type 'a. The type of the Lock monad is a function that accepts the locked object and returns the result of the computation. The following return and bind functions are the standard implementation of the reader monad.

type Lock<'a> = Lock of (obj -> 'a)

let apply (Lock f) lock = f lock
let mreturn x = Lock (fun lock -> x)
let bind m f = Lock (fun lock -> apply (f (apply m lock)) lock)

Next we need a function to run a Lock computation. This function takes as arguments an object to lock and the computation to run. It acquires a lock on the object, runs the computation and then releases the lock.

(* val run : 'a -> Lock<'b> -> 'b *)
let run lock m =
let lock = box lock
Monitor.Enter(lock)
try apply m lock
finally Monitor.Exit(lock)

Next we'll define some monadic actions for wait and pulse.

(* val wait : Lock<unit> *)
let wait = Lock (fun lock -> Monitor.Wait(lock) |> ignore)

(* val tryWait : int -> Lock<bool> *)
let tryWait (timeout : int) = Lock (fun lock -> Monitor.Wait(lock, timeout))

(* val pulse : Lock<unit> *)
let pulse = Lock (fun lock -> Monitor.Pulse(lock))

(* val pulseAll : Lock<unit> *)
let pulseAll = Lock (fun lock -> Monitor.PulseAll(lock))

Finally we need a builder class to enable computation expression syntax on the Lock type. This code is omitted here but can be downloaded in the full example.

Now at last we can write lock code in F# with curly braces, without seeing the Monitor class, and without reproducing the locked object to call wait and pulse.

lock { do decr x
if x = 0 then return! pulse } |> run this

Or a more complex example
lock { while ready.Count = 0 && !pending > 0 do return! wait
       if ready.Count > 0
       then return Some (ready.Dequeue())
       else return None } |> run myLock

You can even have an alternate run function that takes a timeout on acquiring the lock.

(* val tryRun : 'a -> int -> Lock<'b> -> 'b option *)
let tryRun lock (timeout : int) m =
    let lock = box lock
    if Monitor.TryEnter(lock, timeout)
    then try Some (apply m lock)
         finally Monitor.Exit(lock)
    else None

Additionally the Lock monad can be used to make synchronized code more composable. Say you have method that always needs to execute under a lock but either you don't know which lock or the lock needs to be entered at an outer scope. You can write this method so that it returns a Lock computation, which can be composed with other Lock computations. Consider functions to synchronously access items in a System.Collections.Generic.Queue.

(* val enqueue : Queue<’a> -> ‘a -> Lock<unit> *)
let enqueue (q : Queue<_>) x =
lock { if q.Count = 0 then return! pulseAll
do q.Enqueue(x) }

(* val dequeue : Queue<’a> -> Lock<’a> *)
let dequeue (q : Queue<_>) =
lock { while q.Count = 0 do return! wait
return q.Dequeue() }

Because these functions return a Lock<_> value the caller can never forget to acquire the lock and this will be enforced by the type system (of course the programmer can still acquire the wrong lock). Secondly these functions can naturally call pulse and wait without knowing the object the lock is acquired on.

With these functions you can easily write code that atomically moves an item between queues and returns the item.

let move q1 q2 =
lock { let! x = dequeue q1
do! enqueue q2 x
return x } |> run myLock

So if you have to use locks because you don't like STM or its performance isn't good enough or for legacy reasons, the lock monad could improve readability and abstraction.

Software Transactional Memory for F#

gneverov — Tue, 15 Jan 2008 14:11:00 GMT

I have written a library for using software transactional memory in F#. The library exposes memory transactions as a monad using F#’s new computation expression feature. It can be downloaded here.

Software transactional memory (STM) is an approach to concurrent programming that avoids the use of traditional, error-prone locks to control access to shared memory. Instead of using locks a programmer specifies sections of code that will make atomic changes to shared memory.

The design and implementation of this F# library is blatantly copied from the paper Composable Memory Transactions. I am enormously grateful to the authors of this paper whose clear and precise explanation made the implementation of this complicated piece of software almost trivial.

The low-level STM machinery is implemented in the file stm.cs. It is written in C# mainly because I was working off existing code I’d written some time ago, but there’s no reason why it could not be written in F#. It is all managed code and internally uses monitors for synchronization. It currently uses a very coarse grained lock meaning that only one transaction can commit at once and every waiting thread is resumed when a transaction completes, but this can be improved with more work. The implementation follows the description in the paper.

The F# monadic interface is in the file stm.fs. It imports definitions from the C# assembly and defines the monad type Stm<'a> with corresponding builder class to enable computation expression syntax. An issue with the implementation of STM systems is how to access the transaction log to make reads and writes during a transaction. Two common approachs are to use thread-local storage which is slow, or implicitly pass the transaction log as an extra parameter to every function, which requires code generation. The advantage of using computation expressions (or monadic do notation) is that the transaction log is explicitly passed between functions by the programmer’s code, thereby avoiding compiler modification, but also avoiding the need for the programmer to manually manage the transaction log parameter passing scheme as well.

With these two layers in place one can write STM code in F#. Transacted memory locations have the type TVar<'a>. This is a reference cell like Ref<'a> in F# but its value can only be read and written from inside a transaction. A TVar is created using the newTVar function.

let x = newTVar 0

val x : TVar<int>

This code is similar to let x = ref 0, but being a TVar instead of a Ref, the location x can be safely shared between multiple threads.

A transaction is defined using a computation expression. A transaction is a value of type Stm<'a> which represents a computation that when executed will make an atomic change to the values of zero or more TVars and then return a value of type 'a. The type system ensures at compile-time that all reads and writes to a TVar only take place inside a transaction. The functions readTVar and writeTVar read and write a TVar respectively. They are analogous to let v = !x and x := v for regular reference cells.

val readTVar : TVar<'a> -> Stm<'a>
val writeTVar : TVar<'a> -> 'a -> Stm<unit>

Let’s define a function that increments the value stored in a TVar.

let incr x =
stm {
    let! v = readTVar x
    do! writeTVar x (v+1)
    return v }

val incr : TVar<int> -> Stm<int>

The syntax stm { … } is an F# computation expression using the 'stm' monad, which means that this is a memory transaction (as opposed to an async work unit or something). The value of the location is read and stored in v. The incremented value is then written back to the location and v is returned as the result of the computation. When executed the read and write happen as an atomic block which means logically that an interleaving thread won’t access the location between the read and write.

A transaction is executed by the atomically function.

val : atomically : Stm<'a> -> 'a

incr x |> atomically

val it : int = 0

incr x |> atomically

val it : int = 1

The composability of STM can be seen by the ability to compose incr into a larger transaction that increments a location twice.

let incr2 x =
stm {
    let! _ = incr x
    let! v = incr x
    return v }

val incr2 : TVar<int> -> Stm<int>

incr2 x |> atomically

val it : int = 3

Imagine that incr was part of the public interface of a module. If incr used a lock to perform the read and write atomically then it would be impossible for users of the library to write incr2 unless the module also exposed its locks through a public interface, which would make programming intricate for the user.

If you see any Haskell STM code, it is straightforward to translate this into F#. For example the paper gives the implementation of an MVar as a code example. The paper describes an MVar as

An MVar is a mutable location like a TVar, except that it may be either empty, or full with a value. The takeMVar function leaves a full MVar empty, and blocks on an empty MVar. A putMVar on an empty MVar leaves it full, and blocks on a full MVar. So MVars are, in effect, a one-place channel.

MVars can be implemented in F# STM like so.

type MVar<'a> = TVar<option<'a> >

let newEmptyMVar () = newTVar None
let newFullMVar v = newTVar (Some v)

let takeMVar mv =
stm { let! v = readTVar mv
        return! match v with
                | Some a ->
                    stm { do! writeTVar mv None
                          return a }
                | None -> retry () }

let putMVar mv a =
stm { let! v = readTVar mv
        return! match v with
                | None -> writeTVar mv (Some a)
                | Some _ -> retry () }

val newEmptyMVar : unit -> MVar<'a>
val newFullMVar : 'a -> MVar<'a>
val takeMVar : MVar<'a> -> Stm<'a>
val putMVar : MVar<'a> -> 'a -> Stm<unit>

The retry operation is used to re-execute a transaction from the beginning. There is no point re-executing the transaction immediately because no memory locations will have changed. So the retry operation blocks until some memory changes that might allow the transaction to make further progress. This is how blocking is implemented with STM.

Another feature of STM that makes it more composable than locks is how it handles blocking. The get/put MVar operations above are blocking operations. If an MVar library was written using locks and non-blocking versions of these operations were required then they would have to be implemented by the library developer and exposed as part of the library’s public interface. Not so with STM: if the MVar interface only exposes blocking get/put operations then it is possible for the user of the library to write the non-blocking versions, and vice-versa.

let tryTakeMVar mv =
orElse
    (stm { let! v = takeMVar mv
           return Some v })
    (stm { return None })

val tryTakeMVar mv : MVar<'a> -> Stm<'a option>

The function tryTakeMVar is the non-blocking version of takeMVar; it returns an option value depending on whether a value was available. The key here is the orElse operation. This function takes two transactions and tries to execute the first. If the first fails with a retry/block then it executes the second. So in this example if takeMVar retries/blocks then it will return None.

Also included in the code download is the Santa program, a singly-linked list queue, and a fixed-length array queue.

Of course all these great benefits of STM come at a price, and that price is performance. An STM program is probably always going to be slower than a lock-based program. This STM implementation was engineered for correctness and design of the monadic interface and so probably has really bad performance.

Some notes about using F# in ProjectEuler

LewisBruck — Tue, 15 Jan 2008 05:20:00 GMT

(After a long hiatus of just lurking and posting to the forums, I am trying to start blogging again.)

Like many people, I recently discovered http://projecteuler.net. The site contains a set of mathematically oriented programming problems that get progressively harder. I started solving them using F#. While doing so, I've come up with some comments on how F# is really good for these kinds of problems and some improvements that would be nice and probably applicable to more general kinds of programs.

BigInt rules! Since a lot of the problems are calculations on large integers, it is nice to have them available. It would be nice if there was a "bigint" equivalent to the "int" and "float" functions to simplify conversions. It would be really nice if there was a way to override the default numeric behavior of assuming that every number is an int; it would be nice to be able to switch to "float" or "bigint" mode and have the type checker make the appropriate assumptions.
A minor nit, but it would be nice to have a predefined identity function. I seem to have one in each program I write (even beyond ProjectEuler).
For most of the problems, I'd create a sequence expression with individual calculations and then aggregate the desired result after filtering. This demonstrated the convenience of sequence comprehensions, but we already knew that :-)
I tried to avoid "normal" imperative for and while loops and created new helper functions to work on sequences: seqUntil and seqWhile would process a sequence depending on a boolean function, seqAll would see if a function was true for all values in a sequence (the counterpart to Seq.exists), seqSkip would remove the first n entries in a sequence (really creative name, there :-), etc. I think that a lot of these functions, especially the ones that are in the Haskell Prelude for lists, would be good additions to the Seq module.
It would be nice to have some of the aggregation operations be representable in the comprehension language. This has been described Simon Peyton-Jones and Phil Wadler in Comprehensive Comprehensions for Haskell and should be applicable to F# as well.
I've noticed that I mix the sequence comprehension syntax with the "old-style" pipeline syntax a lot, even when the function could be done in a sequence comprehension. Looking back, it seems that if I am exploring (ok, guessing) a solution incrementally, it is easier to do that by adding new Seq.map, Seq.filter, or Seq.fold functions at the end with "|>" while running each step in fsi. Would it help if there was a way to run and augment sequence comprehensions incrementally in fsi? If I knew the path to the solution(or subsolution), I would choose to use the comprehension syntax first.
While there seems to have been an interest in having F# be an alternative to Matlab for some kinds of engineering computing, I think that it could give Mathematica a run for its money in the computational and presentation space. Adding full symbolic math support would be nice, but a harder challenge...

It has been a fun diversion to work on these problems, and interesting to see how concise the F# solutions are compared to the other languages represented. The solutions in J are always the smallest, but I haven't grokked the syntax to understand the solutions yet :-) The assembly language solutions are always interesting to read, but it is nice to see F# solutions that are as concise as the Ruby and Python solutions but running much faster...

F# 1.9.3 Release Candidate (1.9.3.7) is now available

optionsScalper — Sun, 02 Dec 2007 05:18:00 GMT

Dr. Don Syme and the F# team have provided a "stabilization" release of F#. It looks like they are starting a "cleanup" in preparation of becoming a product. Woo Hoo!

Dr. Syme's full post is here.

The release notes are here.

Download it as an MSI or ZIP.

Using F# with R

optionsScalper — Tue, 06 Nov 2007 08:02:00 GMT

On the F# list server over at Microsoft Research, there was a question posted by Lars Johnson about using F# with R. For whatever reason, I'm not able to post to that list server. I'm not very good with list servers, so I'll post up my usage here and hope that someone could post this back to the list server or notify Lars.

For those that don't know, R is an analytics tool with an emphasis on rich statistical toolboxes. It was first produced at the old AT&T Bell Labs and was later commercialized by Stat-Sci (later to become Insightful) as S-Plus. R remains free and in the public domain.

In the list server thread, Juergen Van Gael mentioned two approaches for possible integration - RSOAP and R(D)COM. This post is for usage of R with R(D)COM with F#. The RSOAP approach is a little more involved, so I chose the R(D)COM path here. As its name implies, R(D)COM is a wrapper for R for usage with COM and DCOM. It was written by Thomas Baier and Erich Neuwirth.

My environment for use of F# with R on a Windows platform:

1. Windows XP SP2
2. .NET 2.0 - 2.0.50727
3. Visual Studio 2005 with SP1 - 8.0.50727.762 (SP.050727-7600)
4. F# 1.9.2.9
5. R 2.6.0 - http://cran.us.r-project.org/
6. R(D)COM 2.50_pl1 - http://rcom.univie.ac.at/

Note that VS2005 is not necessary as this could be done with the .NET Framework and F#.

After the above installation, we need to make an R(D)COM .NET wrapper so that F# or any .NET application can see the R(D)COM server. For this, I opened a VS2005 command prompt (dos window with the VS2005 environment variables properly set up). In that window, perform the following two steps. After you complete these steps, the command window is no longer needed.

1. Change directory to the default installation for the R(D)COM binaries. "cd C:\Program Files\R\(D)COM Server\bin".
2. Create the .NET interop wrapper. "TlbImp STATCONNECTORSRV.exe /out:Interop.STATCONNECTORSRVLib.dll". Note that while this is a standard operation for .NET with COM, Robert Pickering's book "Foundations of F#" covers COM usage with F# (and other interoperability) in Chapter 13.

Next, open up a copy of fsi and interact with the following code.

//-----------------------------
#light
// attach a copy of the R(D)COM dll for statistics connections.
#r @"C:\Program Files\R\(D)COM Server\bin\Interop.STATCONNECTORSRVLib.dll"
// open the namespace
open Interop.STATCONNECTORSRVLib

// Create a connection instance
let SCCForR = new StatConnectorClass()
// Initialize that instance for usage with R
SCCForR.Init("R")
// Sample statements to modify the R environment.

// create an R variable named abc and assign it the value of 5
SCCForR.SetSymbol("abc", 5)

// Retrieve the value of the R variable named abc and assign that value to the F# value valueForabc
let valueForabc = SCCForR.GetSymbol("abc")

// Evaluate an expression in R and assign that value to an F# value aTestEvaluation
let aTestEvaluation = SCCForR.Evaluate("8 * sin(4)")

// Close the R connection
SCCForR.Close()
//-----------------------------

Note that the value for valueForabc should be 5. The value for aTestEvaluation should be -6.054419962. Also note that this sample does NOT clean up the COM object assigned to SCCForR. It only closes the connection to R.

This sample interop code was modified from the example given in the R(D)COM package. There are many other possibilities for R(D)COM, especially in the rich graphics libraries that R has to offer.

F# Overview - Introduction to the F# language

tomasp — Sat, 03 Nov 2007 01:36:00 GMT

In my bachelor thesis I included a short introduction that covered all of the important aspects of the F# programming language and I thought that it may be useful to extend it a little bit to cover also a topics that were not important for my thesis and post it as an article, so there is one and relatively short article that introduces all the interesting F# features. The article got however a bit longer than I expected, so I decided to split it into a three parts that would introduce three different paradigms that are supported by F#. Of course, this series won’t teach you everything about F#, but it tries to cover the main F# design goals and (hopefully) presents all the features that make F# interesting and worth learning. In this first part I will shortly introduce F# and the supported paradigms that will be discussed in the upcoming articles.

Introducing F#

In one of the papers about F#, the F# designers gave the following description: "F# is a multi-paradigm .NET language explicitly designed to be an ML suited to the .NET environment. It is rooted in the Core ML design and in particular has a core language largely compatible with OCaml". In other words this means that the syntax of the F# language is similar to ML or OCaml (don’t worry if you don’t know these languages, we’ll look at some examples shortly), but the F# language targets .NET Framework, which means that it can natively work with other .NET components and also that it contains several language extensions to allow smooth integration with the .NET object system.

Another important aspect mentioned in this description is that F# is multi-paradigm language. This means that it tries to take the best from many programming languages from very different worlds. The first paradigm is functional programming (the languages that largely influenced the design of F# in this area are ML, OCaml and other), which has a very long tradition and is becoming more important lately for some very appealing properties, including the fact that functional code tends to be easier to test and paralellize and is also extensible in a ways where object oriented code makes extending difficult.

The second paradigm is widely adopted object oriented programming, which enables interoperability with other .NET languages. In F# it is often used for implementing elementary data types (meaning that the operations on the type are well known and change very rarely), for grouping a set of elementary functions that are together used to perform some complicated operation (i.e. implementing an interface) and also when working with object oriented user interface frameworks.

Finally, the third paradigm supported by F# is language oriented programming (the design of F# in this area is largely influenced by ML, Haskell and also by LINQ). In general, language oriented programming is focused on developing executors for some code which has a structure of a language (be it a declarative language like XML, or a fully powerful language like some subset of F#). In this overview, I will focus on two techniques provided by F# that allow you to give a different meaning to a blocks of F# code. In a programming language theory, this is often called internal domain specific languages, because the code is written in the host language, but is specifically designed as a way for solving problems from some specific domain. An example of such language (and an associated executor) is a block of code that is written as a linear code, but is executed asynchronously (in F# this can be implemented using computation expressions), or a query that is written in F#, but is executed as a SQL code by some database server (this can be implemented using F# quotations).

F# Overview - Links

In the rest of this article series we will look at all these three paradigms supported by F# starting with functional programming and basic F# types used when writing code in a functional way, continuing with object oriented programming and the support for .NET interoperability which is closely related to the OOP in F#. Lastly, we will look at the language oriented programming paradigm including some of the most important .NET and F# library functions that make it possible. The rest of the articles from the series are available in my other blog:

F# Overview (I.) - Introduction (at TomasP.Net)
F# Overview (II.) - Functional Programming (at TomasP.Net)
F# Overview (III.) - Object Oriented and Imperative Programming (at TomasP.Net)
F# Overview (IV.) - Language Oriented Programming(at TomasP.Net)

You can also download the complete article as a single document (PDF).

Other F# Resources

There are many other places where you can find useful information about F#. First of all, there is an official F# web site [1] where you can find the language specification, documentation and other useful resources. There are also two books written about F# (one already published [2], second will be available soon [3]). Lastly, there are also a lot of community resources including an F# community web site with discussion board [4], wiki [5] and several blogs [6,7,8,9]. Finally, there are also some projects developed by the F# community that are available at CodePlex - the first one includes various F# code samples [9, 10] and the second is based on my thesis and tries to solve several web development problems [11].

[1] F# web site [^] - Official F# homepage
[2] Expert F# [^] - Book by by Don Syme, Adam Granicz and Antonio Cisternino
[3] Foundations of F# [^] - Book by Robert Pickering
[4] hubFS: THE place for F# [^] - The F# community web site with blogs, forums, etc..
[5] F# Wiki Homepage [^] - F# Wiki started by Robert Pickering
[6] Don Syme’s WebLog on F# and Other Research Projects [^] - Blog written by the F# language designer Don Syme
[7] Robert Pickering’s Strange Blog [^] - Blog of the "Foundations of F#" book author
[8] Granville Barnett [^] - Explorations in programming
[9] F# News [^] and F#.NET Tutorials [^] by Jon Harrop
[10] F# Samples [^] - Contains code that demonstrate various F# language features
[11] F# WebTools [^] - Project that allows writing client/server Ajax web applications entirely in F#

Software Development Engineer Positions on the F# team!

dsyme — Tue, 30 Oct 2007 22:51:00 GMT

The F# team is hiring! We have two positions open right now. The first is a software development engineer specializing in Visual Studio and libraries. The second is a software development engineer in test. Some extracts from the job description for the first:

We’re looking for an exceptional developer to work on integration with the Visual Studio editor and debugger, and with Technical Computing libraries. You will be a key designer/engineer on our team, responsible for significant architecture investments, implementing key features, and participating in language design. You will be working with very strong architects, engineers and researchers, often working across organizational boundaries and with the developer community.

To be successful on this team, you should possess rock solid design and development skills. You should have a strong track record of shipping secure, high quality software through all phases of the product cycle and have demonstrated successes in cross team partnerships. The ideal candidate will have 6 or more years of experience designing/shipping developer tools, strong functional (F#/Haskell/OCaml), C# and C++ coding skills, and a good understanding of Technical Computing. A MS or PhD degree in Computer Science or a related technical field is preferred.

The full details of the position are up on the Microsoft site, along with how to apply. (The job is listed as "C# team" because the F# team is a small team in the C# org). The location listed is "Redmond", but we'd be open to people looking to work in Cambridge UK for some of the time.

Juergen van Gael on Asynchronous Workflows

dsyme — Thu, 18 Oct 2007 21:55:00 GMT

[ During the summer the F# team at MSR Cambridge had the pleasure of having Juergen van Gael working with us, prior to his starting a PhD at the University of Cambridge. Juergen looked at three topics: probabilisitic modelling with F#, some machine learning algorithms with the APG team, and topics in math libary support for F#. Before he left Juergen wrote up his expereiences of using asynchronous workflows to parallelize some math algorithms. Here's his write up!

One caveat: asynchronous workflows can be used to do some simple CPU-intensive parallelizations, but have some overheads because at each step of the way we have to cater for the fact that tasks may be asynchronous, and this often means using operating system synchronization resources ("WaitHandles") along the way. Libraries like Parallel FX Futures will have great functionality for scheduling lots of synchronous tasks, like many of the ones used below. Juergen wrote this up before we could really make heavy us of Parallel FX so his write up doesn't mention them.

Basically, I'd say that as these technologies become widely used you should assess the characteristics of your tasks and use the right scheduling machinery for the job. Do your tasks need to perform non-blocking network or disk I/O? Then the .NET thread pool will likely have to be used in some way, because that's largely how .NET asynchronous I/O works, and F# asynchronous workflows are a reasonable way of doing this kind of programming. Are they simple synchronous computational tasks? Then Parallel FX Futures look like the right machinery there.

Anyway, over to Juergen! ]

I want to draw your attention to a feature of F# that I’ve become to like very much: asynchronous workflows. As a machine learning researcher, I often run into the scenario where I need to read in a lot of data, run a number of independent tasks (potentially in parallel) and later compute some aggregate information. A very recent example required me to compute optimal parameters for a classifier; unfortunately I could not compute gradient information and decided to brute force search over a parameter grid. Evaluating the classifier for every parameter is independent of all other evaluations though and could be done in parallel. Although asynchronous workflows are designed for other purposes, they allow you to do just this. Asynchronous workflows are a mechanism in F# to setup a computation by describing small tasks and how these tasks depend on each other. The feature that got me excited was that it is extremely simple to describe parallel tasks. Onto an example!

One way to picture an asynchronous workflows is as a directed acyclic graph where every node describes a simple computation: in F# this is represented as an Async<’a> task.

V1 = Z*Z  -----\
                \
V2 = sin(Z)    -----> R = V1 + V2 + V3
                /
V3 = log(Z) ---/

The graph above shows a simple numerical computation which could be described with asynchronous workflows. Assume Z has some value prior to executing the computation in the graph above. It should be clear that the computations of the three v’s are independent and can be done in parallel; only after all three are computed the computation can proceed by computing R. The code snippet below shows how to describe the workflow in F#:

#light

let evals =

let z = 4.0

[ async { do printf "Computing z*z\n"

return z * z };

async { do printf "Computing sin(z)\n"

return (sin z) };

async { do printf "Computing log(z)\n"

return (log z) } ]

let awr =

async { let! vs = Async.Parallel evals

do printf "Computing v1+v2+v3\n"

return (Array.fold_left (fun a b -> a + b) 0.0 vs) }

let R = Async.Run awr

printf "Result = %f\n" R

First we initialize a variable evals which references a list of asynchronous computation each describing the computation of one v. It is important to note that no numerical computation is done at this point: we are just setting up the computation. Next we build another computation (awr) as a workflow by using the Async.Parallel construct. This construct takes a sequence of asynchronous workflows, schedules all of them in parallel, waits for the results and returns those packaged in a list of Async types. In the awr expression, we bind variable vs to the contents of the Async type returned by the parallel computations. Again, I want to stress that at this point we have only setup the computation. Only when we execute Async.Run do we commit the runtime to evaluate the whole workflow and wait for its results. On my machine this results in the following output:

Computing z*z

Computing sin(z)

Computing log(z)

Computing v1+v2+v3

Result = 16.629492

Although the computation we setup and executed above is trivial I hope I conveyed to you that asynchronous workflows are an interesting way to describe a parallel computation. Here is a possible implementation of a parallel matrix multiplication using asynchronous workflows. Note that in this example we chose to parallelize the computation of rows, but different granularities are possible. (Do not consider this to be a high performance, parallel matrix multiplication but rather as a workflow example.)

open Microsoft.FSharp.Collections

let ParallelMultiply A B =

let n = Array2.length1 A

let C = Array2.create n n 0.0

let RowTask i =

async { do for j=0 to n-1 do

for k=0 to n-1 do

C.[i,j] <- C.[i,j] + A.[i,k] * B.[k,j]

do printf "Computing row %d\n" i

}

let p = Async.Parallel [ for i in [0..n-1] -> RowTask i ] |> Async.Ignore

Async.Run p

let n = 4

let rnd = System.Random()

let A = Array2.init n n (fun i j -> rnd.NextDouble())

let B = Array2.init n n (fun i j -> rnd.NextDouble())

printf "%A\n" A

printf "%A\n" B

let C = ParMult A B

printf "%A\n" C

Somasegar Announces Productization of F#

Robert — Wed, 17 Oct 2007 13:31:00 GMT

Somasegar, the head of the Developer Division at Microsoft, has announced the productization of F#. Read more about it here.

Building LINQ Queries in F# and C#

tomasp — Mon, 15 Oct 2007 19:49:00 GMT

My last post at the hubFS was an article that I wrote earlier to my personal blog and I wrote one more article some time ago that is related to F# and I wasn't posted here. The article is a part of a short series that discusses how the same LINQ-related problem can be solved in F# and in C# 3.0 (and in fact, my implementation of the C# version was largely motivated by the F# solution). Because I think that the articles are closely related, I'll write just a short summary here and add links to both articles available in my other blog.

The articles deal with a problem how can one build a LINQ (database) query at runtime. A typical example of a query that developers want to build at runtime is a query where the user can modify the filtering condition (where clause) - for example the application may want to allow combining several conditions, like c.Country == <entered value> with c.Name.StartsWith(<entered value>). In addition you may want to allow combining these single conditions using various operators (at least or and and).

The article about the F# version also shortly introduces the F# comprehensions and quotations that are used when writing LINQ queries using F#. Then it gives a few examples of using LINQ for database queries and finally, it fully describes the example that is shortly introduced below. In the article about the C# version, I described several extensions that are very useful when writing the queries in the F#-style as well as a solution that I use to allow a mechanism similar to F# holes (that are shortly introduced below). Finally, the F# article also contains a version of the FLINQ sample that is compatible with Visual Studio 2008 Beta 2.

Building LINQ Queries at Runtime in F# [^] - Complete article at TomasP.Net
Building LINQ Queries at Runtime in C# [^] - Complete article at TomasP.Net

Building LINQ Queries at Runtime in F#

In F#, the queries are represented using quotations which can be easily combined thanks to the support for holes (written as underscore). The following example first defines two basic conditions (one of them always returns true and the second returns false). Later, we define two combinators for combining conditions using || and && operators. Finally, we build a condition that is composed from several elementary conditions (stored in a dictionary called dict). To do this we can use the Fold function which takes an initial condition and combines it with all the conditions in the dictionary:

// Basic conditions that always return true/false
let falseCond = « fun (c:Customer) -> false »
let trueCond  = « fun (c:Customer) -> true  »

// Condition combinators
let (||*) f g = « fun (c:Customer) -> (_ c) || (_ c) » f g
let (&&*) f g = « fun (c:Customer) -> (_ c) && (_ c) » f g

// Which combinator will we use?
let (^^) = if generateOr then (||*) else (&&*)
  
// Build the expression by folding all items in a dictionary  
let expr = 
  dict.Fold(fun key propSelector e ->
      Console.Write("Enter value for '{0}':\n> ", key);
      let enteredVal = Console.ReadLine();
          
      let currentCond = 
        « fun (c:Customer) -> ((_ c):string).IndexOf(_:string) <> -1 » 
          propSelector « §enteredVal »
      (currentExpr ^^ e)) 
    (if generateOr then falseCond else trueCond)

Building LINQ Queries at Runtime in C#

In C# the representation of the lambda expression can be either a delegate (Func<...>) or an expression tree (Expression<Func<...>>) and the decision whether to generate a delegate or an expression tree depends on the expected type, which means that the code needs to define a type alias. This is possible thanks to the using statement (though this can be avoided by using helper functions, but in this example I'll instead use aliases). Primitive conditions are easy to define once we have a type alias CustomerCondition (which stands for an expression tree of a lambda expression taking a Customer as an argument and returning a bool). When defining a combinators, we need a way for calling an expression tree in another expression tree and this is done by the method Expand (which is not part of LINQ and is further discussed in the article). Finally, the code that generates the result uses similar technique as the previous F# version:

// Basic conditions that always return true/false
CustomerCondition trueCond  = (c) => true;
CustomerCondition falseCond = (c) => false;

// Condition combinators
CustomerConditionCombinator combineOr = 
  (f, g) => (c) => f.Expand(c) || g.Expand(c);
CustomerConditionCombinator combineAnd = 
  (f, g) => (c) => f.Expand(c) && g.Expand(c);

// Which combinator will we use?
CustomerConditionCombinator combinator = 
  generateOr ? combineOr : combineAnd;

// Build the expression by folding all items in a dictionary  
var expr = dict.Fold((e, item) => {
    Console.Write("Enter value for '{0}':\n> ", item.Key);
    string enteredVal = Console.ReadLine();
    CustomerPropSelector propSelector = item.Value;    
    
    CustomerCondition currentCond = (c) => 
      propSelector.Expand(c).IndexOf(enteredVal) != -1;
      
    return combinator(e, currentCond); 
  }, generateOr ? falseCond : trueCond);

F# Web Tools: "Ajax" applications made simple

tomasp — Sat, 13 Oct 2007 20:23:00 GMT

I started thinking about working on "Ajax" framework quite a long time ago - the key thing I really wanted from the beginning was using the same language for writing both client and server side code and the integration between these two sides, so you could write an event handler and specify if it should be executed on the client or on the server side. About a year ago I visited Cambridge (thanks to the MVP program) and I had a chance to talk with Don Syme [^]. Don showed me a few things in F# and suggested using F# for this project, so when I was later selected to do an internship at MSR, this was one of the projects that I wanted to work on. The original reason for using F# was its support for meta-programming ([8], which makes it extremely easy to translate part of the page code-behind code to JavaScript. During my internship, the F# team was also working on a feature called computational expressions, which proved to be extremely useful for the F# Web Tools as well - I bet you'll hear a lot about this from Don soon, so I'll describe only the aspects that are important for this project. Aside from these two key features that F# has, I also quite enjoyed programming in F# itself - I already used it for a few things during the last year, but I could finally work on a large project in F# (and discuss the solution with the real experts!) and I don't believe I would be able to finish the project of similar complexity during less than three months in any other language (but this is a different topic, which deserves separate blog post). ...(read more)

CUFP Workshop 2007 - Featuring F#

dsyme — Tue, 21 Aug 2007 17:09:00 GMT

The program for the 2007 Commercial Users of Functional Programming workshop is now published.

http://cufp.galois.com/

The workshop is co-located with ICFP, and will be held in Freiburg, Germany, on 4 October 2007. We had a terrific response to our call for talks, and there are twelve (!) speakers describing commercial applications, variously written in
        Caml
        Erlang
        F#
        Haskell
        ML
        Scheme

The talks are informal, and there are no proceedings. We'll just have fun learning about functional programming used to solve real problems. Do come!

Don Syme
Kathleen Fisher
Simon Peyton Jones

F# on Hansel Minutes

Robert — Fri, 10 Aug 2007 13:54:00 GMT

Listen to yours truely bang on about F# for 36 minutes and 22 seconds :)
http://hanselminutes.com/default.aspx?showID=94