hubFS: THE place for F#

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.