Jomo Fisher -- Sharp Things

F# Performance Tweaking

Jomo Fisher—I’ve enjoyed reading the blog series on F# and game development here.  Joh had posted an example of F# of using RK4 and showed some performance numbers comparing F# to C++ and OCaml. Don Syme had been reading too and asked if anyone on the F# team wanted to take a stab to see if they could optimize Joh’s code any further. I thought it would be fun. It turns out there were a few small changes that make a significant performance improvement without sacrificing immutability or other nice functionalness.

The example code in this article was compiled with the 1.9.6.2 version of the F# compiler.

Joh probably already accounted for this, but it’s worth pointing out that there is a huge performance difference between Debug and Release builds for this example. On my machine I could measure a 3x performance difference between the two.

Considering just Release builds, I was able to get another 2-3x improvement by making several simple changes:

-          Change a few functions to return struct instead of tuple. For this, I created a ps (e.g. Position-Speed) struct and a sa (e.g. Speed-Acceleration) struct.

-          I manually lifted a few computations out of the outer similar loop. I made (euler_implicit_opt accel_opt) and (runge_kutta_4_opt (adapt_opt accel_opt))into values.

-          I changed the simulate function to use OptimizedClosures.FastFunc3.

This last part especially needs some explaining. Closure optimization can be used when a function will be called many times. It allows F# to do a bit of expensive work up front that will later be amortized across the many calls to the function. Below is the simulate function using optimized closures. I’ve bolded the affected lines.

let inline simulate_opt intg_func t0 t_fin delta pos0 speed0 =   

    let oc = OptimizedClosures.FastFunc3<_,_,_,_>.Adapt(intg_func)

    let rec repeat t0 pos0 speed0 =       

        if t0 > t_fin then (pos0, speed0)       

        else           

            let t1 = t0 + delta           

            let ps:ps<_> = oc.Invoke(pos0,speed0,delta)

            repeat t1 ps.pos ps.speed

    repeat t0 pos0 speed0 

Unfortunately, this is not something that you can stick everywhere and just get a benefit (otherwise, the compiler could just inject it for you).  You should definitely profile before and after. Here are my final performance numbers:

Optimized---

Euler single: 2.529253

Euler multi: 1.328133

RK4 single: 2.383238

RK4 multi: 1.241124

Baseline---

Euler single: 7.672767

Euler multi: 3.922392

RK4 single: 4.563456

RK4 multi: 2.450245

Here’s the entire code. The optimized functions end in _opt. Thanks Joh for an awesome diversion!

#light

open System

let run_time_func (func: unit -> 'a) =   

    let time0 = System.DateTime.Now   

    let res = func ()   

    let diff0 = System.DateTime.Now - time0   

    (diff0, res)

let map_parallel func items =   

    let tasks =       

        seq {           

             for i in items -> async {               

                    return (func i)           

                    }       

            }   

    Async.Run (Async.Parallel tasks)       

let gravity =

     -9.81

let inline spring pos =   

    let k = 100.0 in       

    -k * pos

let inline drag k pos speed = -k * speed   

type ps<'num> = struct

    val pos:'num

    val speed:'num

    new(pos,speed) = {pos=pos;speed=speed}

end

type sa<'num> = struct

    val speed:'num

    val accel:'num

    new(speed,accel) = {speed=speed;accel=accel}

end

let inline euler_implicit accel_func pos speed delta =   

    let speed2 = speed + delta * accel_func pos speed in       

        pos + delta * speed2, speed2

let inline euler_implicit_opt accel_func pos speed delta =   

    let speed2 = speed + delta * accel_func pos speed in       

        ps(pos + delta * speed2, speed2)

let inline adapt (f: 'num -> 'num -> 'num) =    

    fun pos speed ->        

        let accel = f pos speed in           

            speed, accel

let inline adapt_opt (f: 'num -> 'num -> 'num) =    

    fun pos speed ->        

        let accel = f pos speed in           

            sa(speed, accel)

let inline runge_kutta_4 deriv_func pos speed delta =   

    let half_delta = 0.5 * delta   

    let s1, a1 = deriv_func pos speed   

    let s2, a2 = deriv_func (pos + half_delta * s1) (speed + half_delta * a1)  

    let s3, a3 = deriv_func (pos + half_delta * s2) (speed + half_delta * a2)   

    let s4, a4 = deriv_func (pos + delta * s3) (speed + delta * a3)   

    let pos1 = pos + delta/6.0*(s1 + 2.0*s2 + 2.0*s3 + s4)   

    let speed1 = speed + delta/6.0*(a1 + 2.0*a2 + 2.0*a3 + a4) in       

        pos1, speed1

let inline runge_kutta_4_opt deriv_func pos speed delta =   

    let half_delta = 0.5 * delta   

    let sa1:sa<_> = deriv_func pos speed   

    let sa2 = deriv_func (pos + half_delta * sa1.speed) (speed + half_delta * sa1.accel)  

    let sa3 = deriv_func (pos + half_delta * sa2.speed) (speed + half_delta * sa2.accel)   

    let sa4 = deriv_func (pos + delta * sa3.speed) (speed + delta * sa3.speed)   

    let pos1 = pos + delta/6.0*(sa1.speed + 2.0*sa2.speed + 2.0*sa3.speed + sa4.speed)   

    let speed1 = speed + delta/6.0*(sa1.accel + 2.0*sa2.accel + 2.0*sa3.accel + sa4.accel) in       

        ps(pos1, speed1)       

let inline simulate intg_func t0 t_fin delta pos0 speed0 =   

    let rec repeat t0 pos0 speed0 =       

        if t0 > t_fin then (pos0, speed0)       

        else           

            let t1 = t0 + delta           

            let pos1, speed1 = intg_func pos0 speed0 delta            

            repeat t1 pos1 speed1   

    repeat t0 pos0 speed0

let inline simulate_opt intg_func t0 t_fin delta pos0 speed0 =   

    let oc = OptimizedClosures.FastFunc3<_,_,_,_>.Adapt(intg_func)

    let rec repeat t0 pos0 speed0 =       

        if t0 > t_fin then (pos0, speed0)       

        else           

            let t1 = t0 + delta           

            let ps:ps<_> = oc.Invoke(pos0,speed0,delta)

            repeat t1 ps.pos ps.speed

    repeat t0 pos0 speed0   

let initial_states = [ for s in 1..1000 -> (float s * 1.0, 0.0) ]   

let t0 = 0.0

let t_fin = 1000.0

let delta = 0.025

let accel pos speed = (drag 1.0) pos speed + spring pos + gravity in

let accel_opt pos speed = (drag 1.0) pos speed + spring pos + gravity in

let ef = (euler_implicit_opt accel_opt)

let rk4f = (runge_kutta_4_opt (adapt_opt accel_opt))

// Changes

// - Change euler_implicit_opt and runge_kutta_4_opt to return a struct (ps)

// - Manually lift (euler_implicit_opt accel) and (runge_kutta_4_opt (adapt accel)) out of loop

// - Change adapt_opt to return struct (sa)

// - Use optimized closure in simulate_opt

printfn "Optimized---"   

for i in 0..0 do   

    let (run_time, res) = run_time_func (fun () -> initial_states |> List.map(fun (x,y) -> simulate_opt ef t0 t_fin (0.25*delta) x y))

    printfn "Euler single: %f" run_time.TotalSeconds;   

    let (run_time, res) = run_time_func (fun () -> initial_states |> map_parallel(fun (x,y) -> simulate_opt ef t0 t_fin (0.25*delta) x y))

    printfn "Euler multi: %f" run_time.TotalSeconds;  

    let (run_time, res) = run_time_func (fun () -> initial_states |> List.map(fun (x,y) -> simulate_opt rk4f t0 t_fin delta x y))

    printfn "RK4 single: %f" run_time.TotalSeconds;   

    let (run_time, res) = run_time_func (fun () -> initial_states |> map_parallel(fun (x,y) -> simulate_opt rk4f t0 t_fin delta x y))

    printfn "RK4 multi: %f" run_time.TotalSeconds;

printfn "Baseline---"   

for i in 0..0 do   

    let (run_time, res) = run_time_func (fun () -> initial_states |> List.map(fun (x,y) -> simulate (euler_implicit accel) t0 t_fin (0.25*delta) x y))

    printfn "Euler single: %f" run_time.TotalSeconds;   

    let (run_time, res) = run_time_func (fun () -> initial_states |> map_parallel(fun (x,y) -> simulate (euler_implicit accel) t0 t_fin (0.25*delta) x y))

    printfn "Euler multi: %f" run_time.TotalSeconds;  

    let (run_time, res) = run_time_func (fun () -> initial_states |> List.map(fun (x,y) -> simulate (runge_kutta_4 (adapt accel)) t0 t_fin delta x y))

    printfn "RK4 single: %f" run_time.TotalSeconds;   

    let (run_time, res) = run_time_func (fun () -> initial_states |> map_parallel(fun (x,y) -> simulate (runge_kutta_4 (adapt accel)) t0 t_fin delta x y))

    printfn "RK4 multi: %f" run_time.TotalSeconds;

done;

T his posting is provided "AS IS" with no warranties, and confers no rights.

F# Scripts—Reference Nirvana

Jomo Fisher—Last time I wrote about getting started with F# scripts. They’re the fastest way to just write and run some F#.  It’s reasonable to ask whether you can use them to do real work. After all, I just showed a toy example: reversing a linked list. In the real world you need use other people’s code. This is what the #r directive is for. You use it like this:

#light

#r "c:\Program Files\Microsoft Visual Studio 9.0\Visual Studio Tools for Office\PIA\Office12\Microsoft.Office.Interop.Excel.dll"

open System.Reflection

open Microsoft.Office.Interop.Excel

let app = ApplicationClass(Visible=true)

let sheet = app.Workbooks

               .Add()

               .Worksheets.[1] :?> Worksheet

let range = sheet.Range("A1")

                 .Value(Missing.Value)

                 <- "Hello Excel"

One thing that is fragile about the script is that different people may have installed the needed assembly in different spots.

To help with this situation, we’ve done something that I think is pretty magical. F# will resolve the assemblies using the same industrial strength reference resolution engine that MSBuild uses. (I tipped our hand a bit on this here). So now, you can just reference the assembly like this:

#r "Microsoft.Office.Interop.Excel"

And F# will just find it. Now the script works in a lot more places.

You can even use it to reference a specific version of an assembly.

#r "Microsoft.Office.Interop.Excel, Version=11.0.0.0, Culture=neutral, PublicKeyToken=71e9bce111e9429c"

The MSBuild algorithm is open to anyone who wants to publish their assembly (search for AssemblyFoldersEx). For example, here’s a screenshot of me referencing the XCeed chart library:

You can pick up the latest CTP of F# here:  http://msdn.com/fsharp

This posting is provided "AS IS" with no warranties, and confers no rights.

F# Scripts--Zero to Execute in Ten Seconds

Jomo Fisher--F# is about conciseness. Consider the interview question that asks you to reverse a singly-linked-list. I’ve been asked this question twice in interviews and even the cleanest implementation in the interviewer’s chosen language was long and it was hard to show that I’d covered the corner cases. The F# answer is concise and self-evidently correct now that I’ve learned F# well enough:

// Take two lists, source and target, and append all the items from source

// to target in reverse order.

let rec AppendReverse source target =

    match source with

    | [] -> target

    | (head::tail) -> AppendReverse tail (head::target) 

// Call AppendReverse with the empty list for target.  

let Reverse list =

    AppendReverse list []

Once you have F# installed, you’re free to just start coding. These steps take about ten seconds:

-          Press Ctrl+N (new file) and select Script\F# Script File

-          In the opened .fsx file add:

System.Windows.Forms.MessageBox.Show("Hello")

-          One time only, press Ctrl+Alt+F to bring up the F# interactive window.

-          Press Ctrl+A (select everything) and then Alt+Enter (execute)

That’s it. We’ve tried to eliminate every piece of friction between you and the code you want to write.

We call these files scripts, but they’re not watered down in any way. They are actual F# which means they are compiled, statically typed and have access to .NET. There’s just not a project or even an explicit build step. In fact, this is one of the reasons F# needed a Visual Studio language service that can actively display errors and warnings as you type.

This posting is provided "AS IS" with no warranties, and confers no rights.

Update on Fast Switching with LINQ

Jomo Fisher—A while back I wrote about using LINQ to get close-to-the-metal performance in a particular string lookup case in C#. Here, Gustavo Guerra has expanded on the idea significantly with a class he calls StaticStringDicitionary. I haven’t tried it, but it looks like it should be nearly as fast as the original (and better tested :).

This posting is provided "AS IS" with no warranties, and confers no rights.

F# Community Technology Preview

Jomo Fisher—The F# team has been working furiously on the upcoming release of F# these last weeks. We’ll have some cool stuff to show you soon. Stay tuned.

This posting is provided "AS IS" with no warranties, and confers no rights.

Programmatically Resolve Assembly Name to Full Path the Same Way MSBuild Does

Jomo Fisher—Every once in a while I find I need to turn and assembly name like “System” or “System.Core, Version=3.5.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089, processorArchitecture=MSIL” into a path to the actual file for that assembly. This is a tricky problem considering the assembly name might be for a product install in Program Files or elsewhere. MSBuild already has rules for doing this resolution. Here’s how to call that code directly (written in F#):

#light

#r "c:\Windows\Microsoft.NET\Framework\v2.0.50727\Microsoft.Build.Tasks.dll"

#r "c:\Windows\Microsoft.NET\Framework\v2.0.50727\Microsoft.Build.Utilities.dll"

#r "c:\Windows\Microsoft.NET\Framework\v2.0.50727\Microsoft.Build.Framework.dll"

#r "c:\Windows\Microsoft.NET\Framework\v2.0.50727\Microsoft.Build.Engine.dll"

open Microsoft.Build.Tasks

open Microsoft.Build.Utilities

open Microsoft.Build.Framework

open Microsoft.Build.BuildEngine

/// Reference resolution results. All paths are fully qualified.

type ResolutionResults = {

    /// Paths to primary references

    referencePaths:string array

    /// Paths to dependencies

    referenceDependencyPaths:string array

    /// Paths to related files (like .xml and .pdb)

    relatedPaths:string array

    /// Paths to satellite assemblies used for localization.

    referenceSatellitePaths:string array

    /// Additional files required to support multi-file assemblies.

    referenceScatterPaths:string array

    /// Paths to files that reference resolution recommend be copied to the local directory

    referenceCopyLocalPaths:string array

    /// Binding redirects that reference resolution recommends for the app.config file.

    suggestedBindingRedirects:string array

    }

let Resolve(references:string array, outputDirectory:string) =

    let x = { new IBuildEngine with

                member be.BuildProjectFile(projectFileName, targetNames, globalProperties, argetOutputs) = true

                member be.LogCustomEvent(e) = ()

                member be.LogErrorEvent(e) = ()

                member be.LogMessageEvent(e) = ()

                member be.LogWarningEvent(e) = ()

                member be.ColumnNumberOfTaskNode with get() = 1

                member be.ContinueOnError with get() = true

                member be.LineNumberOfTaskNode with get() = 1

                member be.ProjectFileOfTaskNode with get() = "" }

    let rar = new ResolveAssemblyReference()

    rar.BuildEngine <- x

    rar.TargetFrameworkDirectories <- [|@"C:\Program Files\Reference Assemblies\Microsoft\Framework\v3.5\"|]

    rar.AllowedRelatedFileExtensions <- [| ".pdb"; ".xml"; ".optdata" |]

    rar.FindRelatedFiles <- true

    rar.Assemblies <- [|for r in references -> new Microsoft.Build.Utilities.TaskItem(r):>ITaskItem|]

    rar.SearchPaths <- [| "{CandidateAssemblyFiles}"

                          "{HintPathFromItem}"

                          "{TargetFrameworkDirectory}"

                          "{Registry:Software\Microsoft\.NetFramework,v3.5,AssemblyFoldersEx}"

                          "{AssemblyFolders}"

                          "{GAC}"

                          "{RawFileName}"

                          outputDirectory |]

    rar.AllowedAssemblyExtensions <- [| ".exe"; ".dll" |]    

    rar.TargetProcessorArchitecture <- "x86"                    

    if not (rar.Execute()) then

        failwith "Could not resolve"

    {

        referencePaths = [| for p in rar.ResolvedFiles -> p.ItemSpec |]

        referenceDependencyPaths = [| for p in rar.ResolvedDependencyFiles -> p.ItemSpec |]

        relatedPaths = [| for p in rar.RelatedFiles -> p.ItemSpec |]

        referenceSatellitePaths = [| for p in rar.SatelliteFiles -> p.ItemSpec |]

        referenceScatterPaths = [| for p in rar.ScatterFiles -> p.ItemSpec |]

        referenceCopyLocalPaths = [| for p in rar.CopyLocalFiles -> p.ItemSpec |]

        suggestedBindingRedirects = [| for p in rar.SuggestedRedirects -> p.ItemSpec |]

    }

try

    let s = Resolve([| "System"

                       "System.Core, Version=3.5.0.0, Culture=neutral, PublicKeyToken=b77a5c561934e089, processorArchitecture=MSIL"

                       "Microsoft.SqlServer.Replication"

                    |], "")

    printfn "%A" s

finally

    ignore (System.Console.ReadKey())

The result of running the code looks like this:

{referencePaths =

  [|"C:\\Program Files\\Microsoft SQL Server\\90\\SDK\\Assemblies\\Microsoft.SqlServer.Replication.dll";

    "C:\\Program Files\\Reference Assemblies\\Microsoft\\Framework\\v3.5\\System.Core.dll";

    "C:\\Windows\\assembly\\GAC_MSIL\\System\\2.0.0.0__b77a5c561934e089\\System.dll"|];

 referenceDependencyPaths =

  [|"C:\\Windows\\assembly\\GAC_MSIL\\System.DirectoryServices\\2.0.0.0__b03f5f7f11d50a3a\\System.DirectoryServices.dll";

    "C:\\Windows\\assembly\\GAC_MSIL\\System.Xml\\2.0.0.0__b77a5c561934e089\\System.Xml.dll";

    "C:\\Windows\\assembly\\GAC_32\\Microsoft.SqlServer.BatchParser\\9.0.242.0__89845dcd8080cc91\\Microsoft.SqlServer.BatchParser.dll";

    "C:\\Windows\\assembly\\GAC_MSIL\\System.Runtime.Remoting\\2.0.0.0__b77a5c561934e089\\System.Runtime.Remoting.dll";

    "C:\\Windows\\assembly\\GAC_MSIL\\Microsoft.Vsa\\8.0.0.0__b03f5f7f11d50a3a\\Microsoft.Vsa.dll";

    "C:\\Windows\\assembly\\GAC_32\\System.Data.OracleClient\\2.0.0.0__b77a5c561934e089\\System.Data.OracleClient.dll";

    "C:\\Program Files\\Microsoft SQL Server\\90\\SDK\\Assemblies\\Microsoft.SqlServer.ConnectionInfo.dll";

    "C:\\Windows\\assembly\\GAC_MSIL\\Accessibility\\2.0.0.0__b03f5f7f11d50a3a\\Accessibility.dll";

    "C:\\Windows\\assembly\\GAC_32\\System.Transactions\\2.0.0.0__b77a5c561934e089\\System.Transactions.dll";

    "C:\\Windows\\assembly\\GAC_MSIL\\System.DirectoryServices.Protocols\\2.0.0.0__b03f5f7f11d50a3a\\System.DirectoryServices.Protocols.dll";

    "C:\\Windows\\assembly\\GAC_MSIL\\System.Drawing\\2.0.0.0__b03f5f7f11d50a3a\\System.Drawing.dll";

    "C:\\Windows\\assembly\\GAC_MSIL\\System.Deployment\\2.0.0.0__b03f5f7f11d50a3a\\System.Deployment.dll";

    "C:\\Program Files\\Microsoft SQL Server\\90\\SDK\\Assemblies\\Microsoft.SqlServer.Smo.dll";

    "C:\\Windows\\assembly\\GAC_32\\System.EnterpriseServices\\2.0.0.0__b03f5f7f11d50a3a\\System.EnterpriseServices.dll";

    "C:\\Windows\\assembly\\GAC_MSIL\\System.Web.RegularExpressions\\2.0.0.0__b03f5f7f11d50a3a\\System.Web.RegularExpressions.dll";

    "C:\\Program Files\\Microsoft SQL Server\\90\\SDK\\Assemblies\\Microsoft.SqlServer.WmiEnum.dll";

    "C:\\Program Files\\Microsoft SQL Server\\90\\SDK\\Assemblies\\Microsoft.SqlServer.ServiceBrokerEnum.dll";

    "C:\\Windows\\assembly\\GAC_MSIL\\System.Configuration\\2.0.0.0__b03f5f7f11d50a3a\\System.Configuration.dll";

    "C:\\Windows\\assembly\\GAC_MSIL\\System.Web.Services\\2.0.0.0__b03f5f7f11d50a3a\\System.Web.Services.dll";

    "C:\\Windows\\assembly\\GAC_MSIL\\System.Management\\2.0.0.0__b03f5f7f11d50a3a\\System.Management.dll";

    "C:\\Windows\\assembly\\GAC_MSIL\\System.Design\\2.0.0.0__b03f5f7f11d50a3a\\System.Design.dll";

    "C:\\Windows\\assembly\\GAC_32\\System.Web\\2.0.0.0__b03f5f7f11d50a3a\\System.Web.dll";

    "C:\\Windows\\assembly\\GAC_MSIL\\System.Windows.Forms\\2.0.0.0__b77a5c561934e089\\System.Windows.Forms.dll";

    "C:\\Windows\\assembly\\GAC_MSIL\\System.Security\\2.0.0.0__b03f5f7f11d50a3a\\System.Security.dll";

    "C:\\Program Files\\Microsoft SQL Server\\90\\SDK\\Assemblies\\Microsoft.SqlServer.SmoEnum.dll";

    "C:\\Windows\\assembly\\GAC_MSIL\\System.Runtime.Serialization.Formatters.Soap\\2.0.0.0__b03f5f7f11d50a3a\\System.Runtime.Serialization.Formatters.Soap.dll";

    "C:\\Windows\\assembly\\GAC_MSIL\\Microsoft.JScript\\8.0.0.0__b03f5f7f11d50a3a\\Microsoft.JScript.dll";

    "C:\\Windows\\assembly\\GAC_MSIL\\System.Configuration.Install\\2.0.0.0__b03f5f7f11d50a3a\\System.Configuration.Install.dll";

    "C:\\Windows\\assembly\\GAC_MSIL\\Microsoft.VisualC\\8.0.0.0__b03f5f7f11d50a3a\\Microsoft.VisualC.dll";

    "C:\\Program Files\\Microsoft SQL Server\\90\\SDK\\Assemblies\\Microsoft.SqlServer.SqlEnum.dll";

    "C:\\Windows\\assembly\\GAC_32\\System.Data\\2.0.0.0__b77a5c561934e089\\System.Data.dll";

    "C:\\Windows\\assembly\\GAC_MSIL\\System.Drawing.Design\\2.0.0.0__b03f5f7f11d50a3a\\System.Drawing.Design.dll";

    "C:\\Program Files\\Microsoft SQL Server\\90\\SDK\\Assemblies\\Microsoft.SqlServer.Rmo.dll";

    "C:\\Windows\\assembly\\GAC_MSIL\\System.Data.SqlXml\\2.0.0.0__b77a5c561934e089\\System.Data.SqlXml.dll";

    "C:\\Windows\\assembly\\GAC_MSIL\\System.ServiceProcess\\2.0.0.0__b03f5f7f11d50a3a\\System.ServiceProcess.dll";

    "C:\\Program Files\\Microsoft SQL Server\\90\\SDK\\Assemblies\\Microsoft.SqlServer.RegSvrEnum.dll"|];

 relatedPaths = [||];

 referenceSatellitePaths = [||];

 referenceScatterPaths =

  [|"C:\\Windows\\assembly\\GAC_32\\System.EnterpriseServices\\2.0.0.0__b03f5f7f11d50a3a\\System.EnterpriseServices.Wrapper.dll"|];

 referenceCopyLocalPaths = [||];

 suggestedBindingRedirects = [||];}

This posting is provided "AS IS" with no warranties, and confers no rights.

Correct by Construction in F#

Correct by Construction in F#

Jomo Fisher—a theme in the design of the F# language is that problems in the code are revealed as compilation errors. Consider this C# code which is used to compose a courteous letter to a customer:

enum Courtesy { Mr, Ms, Dr }

class Customer {

    public Courtesy Courtesy { get; set; }

    public string Name { get; set; }

}

class Letter {

    public string Introduction { get; set; }

    public string Body { get; set; }

}

static Letter Correspond(Customer customer, string message) {

    switch (customer.Courtesy)

    {

        case Courtesy.Mr:

            return new Letter { Introduction = "Mr. " + customer.Name,

                                Body = message };

        case Courtesy.Ms:

            return new Letter { Introduction = "Ms. " + customer.Name,

                                Body = message };

    }

    return null;

}

This compiles without errors despite having some problems (can you spot them?)

I want to stop now and claim that I’m not picking on C# which is a wonderful language. It’s just that I need to compare F# to something in order to illuminate my point and I happen to know C# pretty well.

Now, transliterate the code above into F#:

#light

type Courtesy = Mr | Ms | Dr

type Customer = {

    Courtesy:Courtesy

    Name:string

}

type Letter = {

    Introduction:string

    Body:string

}

let Correspond(customer,message) =

    match customer.Courtesy with

    | Mr -> {Introduction = "Mr. " + customer.Name; Body=message}

    | Ms -> {Introduction = "Ms. " + customer.Name; Body=message}

    | _ -> null

Compiling this gives a warning on the last line:

error FS0043: The type 'Letter' does not have 'null' as a proper value.

In C#, objects are allowed to be null by default and your code is responsible for handling the possibility of nullity everywhere. F# objects are not allowed to be null and, except in a few special cases such as interoperating with non-F# code, you can assume that object instances aren’t null.

So the caller of the Correspond function need not worry about receiving a null Letter instance and I can just delete the last line:

let Correspond(customer,message) =

    match customer.Courtesy with

    | Mr -> {Introduction = "Mr. " + customer.Name; Body=message}

    | Ms -> {Introduction = "Ms. " + customer.Name; Body=message}

Now I get a warning:

warning FS0025: Incomplete pattern match on expression. The value ‘Dr’ will not be matched

This is an easy mistake to make: I forgot one of the cases in the Courtesy enumeration.

An aside on pattern matching: If you code in F# you’ll find yourself using pattern matching for a significant amount of the logic in your program. It’s far more than just a synonym for switch. It can do complex matching against just about any type of object. This, combined with completeness checking, helps eliminate a large class of bug.

Here’s my final corrected code:

let Correspond(customer,message) =

    match customer.Courtesy with

    | Mr -> {Introduction = "Mr. " + customer.Name; Body=message}

    | Ms -> {Introduction = "Ms. " + customer.Name; Body=message}

    | Dr -> {Introduction = "Dr. " + customer.Name; Body=message}

This idea that F# should lead you to write code that is correct by construction is not just about the features I mentioned above. Its fundamentally weaved through the language. Take a look at how casting works for another example.

Honestly, it took me some time to get used to. I particularly struggled with the non-nullity of object instances. I was used to being able to smuggle the special “null” value around without changing my code to accommodate it. I realize now I was just sweeping a potential problem under the rug.

This posting is provided "AS IS" with no warranties, and confers no rights.

Strange Confluence: An Immutable Queue in F#

Jomo Fisher--Reading one of my favorite blogs this morning--Eric Lippert's Fabulous Adventures in Coding--I came across his article on implementing an immutable queue in C#. The funny thing is that just yesterday I wrote exactly the same structure in F#. Here it is for your reading pleasure:

    type Fifo<'a> =

        new()={xs=[];rxs=[]}

        new(xs,rxs)={xs=xs;rxs=rxs}

        val xs: 'a list;

        val rxs: 'a list;

        static member Empty() = new Fifo<'a>()

        member q.IsEmpty = (q.xs = []) && (q.rxs = [])

        member q.Enqueue(x) = Fifo(q.xs,x::q.rxs)

        member q.Take() =

            if q.IsEmpty then failwith "fifo.Take: empty queue"

            else match q.xs with

                    | [] -> (Fifo(List.rev q.rxs,[])).Take()

                    | y::ys -> (Fifo(ys, q.rxs)),y

This is code modified from a mutable structure that I found in the F# distribution. The queues are pretty similar except for a few minor details:

• F# version doesn't implement IEnumerable<T>.
• F# version relies on the built-in list class which is semantically identical to an immutable stack.
• C# version carries the "popped" instance of T along with the queue itself whereas the F# version returns this as part of a tuple from Take(). I think I prefer my way on this point--it seems like information leakage for the queue have a memory of the last thing popped.

That's all for now, and as always...

This posting is provided "AS IS" with no warranties, and confers no rights.

Tight Code--A Puzzle in F#

Jomo Fisher--Luke Hoban wrote something in a blog entry that resonated with me:

One of the most striking features of F# code is that it is very terse - ideas can typically be expressed with a small amount of code. 

Don Syme once mentioned (I'm paraphrasing) that an aspirational goal for F# in the beginning was to make a compiler that could compile itself in less than 10,000 lines of code. Though that line count has since been passed I often get the sense that, with enough thought, I could boil whatever code I'm working on down to almost nothing.

Consider this coding problem (which I have since used as an interview question). Take a singly-linked-list of singly-linked-lists and pivot the inner values. For example say I have this list:

let have = [['a';'b';'1'];['c';'d';'2'];['e';'f';'3']]

Then the list I want is this:

let want = [['a';'c';'e'];['b';'d';'f'];['1';'2';'3']]

So the new list's first list has the first item from each of the original inner lists and so on. This problem actually came up in real-world piece of code I was working on. My first cut was procedural and about twenty lines of code. I don't have it here to show you, but after a few iterations and refactorings I got it down to a respectable nine lines:

let flatteninto source target =

    List.zip target source |> List.map(fun (head, tail)->head@[tail])

let pivot list =

    let rec work target = function

          head::tail-> work (flatteninto head target) tail

        | [] -> target

    let empties = list|>List.map(fun l->[])

    work empties list

At this point, I was stuck. It worked, but it seemed like there should be a better solution. In particular, the second to last line where I build up a list of empty lists didn't seem quite right. Being stuck, I asked my teammates whether there was a better solution out there. As it turns out, James Margetson had seen a beautiful four line solution to the problem.

I'll post the solution James showed me in a few days. In the meantime, I'd like to invite you to give the problem a try in the programming language of your choice. Can you cleanly beat my nine-line solution above? Can you get it down to four lines? I only ask that you don't change the input structure--singly-linked-list of singly-linked-list. Also, in my problem, the input was guaranteed to be well formed so I didn't need to check for jagged inner lists or other malformed inputs. Finally, notice that while I showed a 3x3 input in the example the dimensions don't have to be the same.

Update 11/20/2007 - Spoiler Alert!

As promised, here's the F# that James showed me

let rec transpose haves =

    match haves with

    | (_::_)::_ -> map hd haves :: transpose (map tl haves)

    | _         -> []

This is essentially the same as the Haskell algorithm that has been posted in the comments.

I want to thank the folks who posted solutions in various different languages--Scheme, Haskell, Ruby, C#, Python. Also, there was an OCaml solution which is indeed compatible with F#.

Several folks pointed out the analogy with matrix transpose. The code does get a lot easier when your input is an array of arrays, but you don't always get to pick your input representation.

One commenter opined that functional code may be easier to read than it is to write. This is true for me in one sense: there seems to always be a way to write the code a little better. Figuring out when I'm done is a challenge.

This posting is provided "AS IS" with no warranties, and confers no rights.

F# Team is Hiring

Do you want to help us ship F#? Check out these job postings:

Developer: http://members.microsoft.com/careers/search/details.aspx?JobID=5DF7A6AB-80C5-41CB-9A8D-5B344C33AE1D&start=1&interval=10&SortCol=DatePosted

Tester: http://members.microsoft.com/careers/search/details.aspx?JobID=B36FFEB2-4C11-4B9C-9B3F-5B23CC604A7B&start=1&interval=10&SortCol=DatePosted

The Least a C# Programmer Needs to Know about F# Part II--Modules

Jomo Fisher--Many languages, especially those in the OO vein, require an outermost class to put code in. Usually, good practice requires an enclosing namespace as well.  F# allows functions and even function calls in the outermost scope. Here is the minimal F# program:

printf "Hello!"

Really, that's the whole thing. My first concern upon seeing this was that the all these functions in the global namespace would eventually collide in larger projects making things unmanageable. It seemed a lot like returning to the nasty global state that you sometimes see in older C codebases. It turns out, however, that F# puts each file's functions, function calls and types inside its own construct called a "Module". Consider this slightly modified version:

// File Hello.fs

#light

let Say s = printf s

Say "Hello!"

Which is saved in file called Hello.fs. This defines a function called 'Say' and then calls it. Using Reflector, I can see the Say method decompiled into C#:

[CompilationMapping(SourceLevelConstruct.Module)]

public class Hello

{

    public static T Say<T>(Format<T, TextWriter, Unit, Unit> s)   {

        return Pervasives.printf<T>(s);

    }

}

The F# compiler has put the method into a public class called Hello . This is F#'s representation of the Module. The class name Hello is derived from the file name Hello.fs.  You can change the Module name if you like:

module MyModule =

    let Say s = printf s

    Say "Hello!"

For larger projects, I think its best to explicitly name modules. For smaller, one-off projects its convenient not to have to think about it.

In most .NET projects I've worked on, there usually ends up being a few utility classes that just have a bunch of related static methods in them. These are functions that just didn't cleanly fit the OO paradigm. Its tempting to think of these classes as code smells. After all, surely there's a clean OO representation for them that I haven't thought of yet, right?

I think the answer to this is: no, not everything fits well into object-orientation.

My proof by existence is to consider .NET's Stream classes that were released in .NET 1.0. These classes were extremely well factored. They beautifully hid the underlying media or communication protocol behind an abstract stream of information.  They were also damn hard to use for simple cases. In a later .NET release the File, Path and Directory classes were introduced. These were just classes with nice, simple static methods for doing the common things you want to do with files, paths and directories.

F#  makes this style of API a first-class citizen: the Module.

So am I saying good-bye to OO? No way. But I consider it a hammer and not every problem is a nail.

This posting is provided "AS IS" with no warranties, and confers no rights.

WideFinder--Naive F# Implementation

Jomo Fisher--Here's an interesting problem that some people are having fun with. Don Box posted a naive implementation in C# so I thought I'd post the equivalent in F#: 

#light

open System.Text.RegularExpressions

open System.IO

open System.Text

 

let regex = new Regex(@"GET /ongoing/When/\d\d\dx/(\d\d\d\d/\d\d/\d\d/[^ .]+)", RegexOptions.Compiled)

 

let seqRead fileName =

    seq { use reader = new StreamReader(File.OpenRead(fileName))

          while not reader.EndOfStream do

              yield reader.ReadLine() }

             

let query fileName =

    seqRead fileName

    |> Seq.map (fun line -> regex.Match(line))

    |> Seq.filter (fun regMatch -> regMatch.Success)

    |> Seq.map (fun regMatch -> regMatch.Value)

    |> Seq.countBy (fun url -> url)

And here's the code to call it:   

The Least a C# Programmer Needs to Know about F# Part I--Implicit Types

Jomo Fisher--A few weeks ago, a fellow C# programmer asked me what the biggest differences between programming in C# and programming in F# are. Since then, I've been building a list of differences. My plan was to write a single article that discussed everything. This morning the list got too long to reasonably put in a single article. Also, I'm not sure when I'll be done discovering the differences. So here's my first in a series of articles. (This is based on the 3.0 version of the C# language. If you want to see what's new in C#, it might be helpful to start here.)

You rarely mention types in F# code

In version 3.0, C# added the var keyword. This keyword allows you to not specify a type and instead rely on the compiler to figure out the type.  This works for locals only so most types are still explicitly specified in the code. In F#, this balance is reversed. You can explicitly specify types but you're rarely required to. F# has a powerful system for deducing the types. Consider this F# function:

let Add a b = a + b

This defines a function which adds two of something to each other. So what are the types of the variables a and b? The F# compiler has chosen int because of the addition that's happening in the function. A second function:

let AddPlusOne a b = a + b + 1.1

looks similar, but now the a, b and the return of the function are types as float. In this case, the compiler decides float is the right type because we're adding constant float value.

Most of the time in F# you don't specify types. I find myself relying heavily on the tooltips in Visual Studio for type information:

I think its legitimate to be uncomfortable with this level of implicitness. Especially coming from the C++ diaspora there is a tradition of being explicit when possible. Indeed, in F# you are free to explicitly specify types everywhere if you choose.

That said, I really like C#'s type inference and have used it in production code (LINQ to SQL). It tends to make the code more readable because you spend more time looking at the algorithm and less time looking at concrete type names.  I haven't shipped or maintained F# code yet, but my feeling is that more type inference is better.

This posting is provided "AS IS" with no warranties, and confers no rights.

Soma on F#

Soma announced some exciting news this morning. Developer Division--the people at Microsoft who make Visual Studio--is partnering with Microsoft Research on F#. We're going to fully integrate F# into Visual Studio:

“This is one of the best things that has happened at Microsoft ever since we created Microsoft Research over 15 years ago.  Here is another great example of technology transfer at work.  We will be partnering with Don Syme and others in Microsoft Research to fully integrate the F# language into Visual Studio and continue innovating and evolving F#.”

Don Syme and his team work out of Cambridge. Over the past few weeks we've been busily spinning up a team in Redmond to work with them. As its stands today, the team looks like this:

Cambridge: Don Syme (does everything), James Margetson (development) and Ralf Herbrich (development)

Redmond: Luke Hoban (PM), Me (development)

Of course we'll add more people over the next weeks and months. Critically, we still need to build the test organization.

The C# Product Unit is sponsoring the partnership and for the foreseeable future Luke and I will continue to work in the C# organization. I think this is a strong match because the C# org, as you probably expect, has a deep relationship with the other parts of Microsoft that will be important going forward: Parallel Fx (PFx), the CLR team, and so forth. We also have Anders Hejlsberg.

F# is a language that makes it easy to make beautiful, concise code. I'm excited to be part of getting it into people's hands.

This posting is provided "AS IS" with no warranties, and confers no rights.

Adventures in F#--Sweet Test-First Kung Fu

Jomo Fisher--Up until now, I've been avoiding using F# with the VS IDE. I've been using notepad.exe and fsc.exe because I wanted to build my own expectation for what the experience should be before I experienced what it actually was. I can tell you that I didn't expect the sweet experience of using the F# interactive window.

I've written in the past about Test Driven Development. Regardless of language, I really like the process of iteratively writing code and unittests tests for that code. For very small projects--simple algorithms and classes--I've found the process of getting going very tedious compared to the amount of actual code I want to write. In order to get started, you need a new project and solution for your code, a separate project for your tests and you need to reference your code project from your test project. All this means friction and tends to discourage firing up VS and freely inventing for very small projects.

Enter the F# Interactive window. Once you've installed F# and checked the Add-in box under Tools\Add-in Manager you'll see the F# interactive window. You can type code into this window and it will execute immediately. Importantly, you can select some text from your current source file and press alt-enter to execute it.

So here's my new process for these tiny one-off projects:

1) Ctrl-N to create a new text file (rename to mycode.fs)

2) Type in the skeleton of the function

3) Select function and press alt-enter

4) Write test, select it and press alt-enter (see failure)

5) Fix function to make test pass and goto 3

Notice that there's not a project or even a solution involved here--its just developer writing code. It's a really sweet experience. I only wish F# would install over C# Express 2008 since that's what I tend to use at home.

I like to show code in my posts when possible and I want to give you a visual idea of what I'm talking about. Here's a simple function I wrote--with tests--that takes a string in the form of A.B.C.D or vA.B.C.D and returns a tuple of 16-bit ints with values (A,B,C,D). The tests are at the end.

#light
let ParseVersion s = 
    // Build a list with each element of the version in reverse order.
    let rec parse(s:string,pos,count,result) = 
        let versionSize = 4
        if pos >= 0 then 
            if s.[pos] = 'v' && pos = 0 then parse(s,1,0,[])
            else 
                let dotPos = s.IndexOf(".", pos)
                if dotPos = -1 then parse(s, -1, count+1, int_of_string(s.Substring(pos))::result)
                else parse(s, dotPos+1, count+1, int_of_string(s.Substring(pos, dotPos-pos))::result)
        elif count < versionSize then parse(s, pos, count+1, 0::result) 
        else result
        
    let l = parse(s,0,0,[])
    (uint16(List.nth l 3), uint16(List.nth l 2), uint16(List.nth l 1), uint16(List.nth l 0))
    
ParseVersion "2.0.1"
ParseVersion "2.0"
ParseVersion "v2.0"
ParseVersion "v1.2.3.4"
ParseVersion "v1"
ParseVersion "1.2.3.4"

(Notice how I made it tail-recursive to take advantage of F#'s tail-call optimization?)

I wrote this using more-or-less test-first principles and I was very happy with the flow of the process.

This posting is provided "AS IS" with no warranties, and confers no rights.