Sharp Things

Use FsLex and FsYacc to make a parser in F#

Jomo Fisher — Tue, 15 Jun 2010 22:18:00 GMT

Update: The template I posted yesterday was for PowerPack 1.9.9.9 which is not the most recent version available. I have since updated the template to target PowerPack 2.0.0.0. If you installed the old template you may need to uninstall at Tools\Extension Manager...

-----------------------------

Jomo Fisher—F# is excellent for parsing text and creating new languages. The F# PowerPack contains two tools—FsLex.exe and FsYacc.exe—to create powerful lexers and parsers. However, it isn’t so easy to configure a Visual Studio project correctly to use these tools. To help with this, I made a project template that you can use to get started quickly. Just follow these quick steps:

1) Download the F# PowerPack from here.

2) In VS2010, go to File\New Project. Select ‘Online Templates’ and search for ‘F# Parsed’ (or my name).

The starter project implements a simple calculator language that you can grow into a more sophisticated Domain Specific Language or text processing application.

Credit goes to Matt Valerio and Brian McNamara for figuring out the details and to Don Syme for making the calculator language that this is based on. Bugs and omissions are probably my fault. Please let me know what you think, and whether you have any issues or spot any bugs that I should address.

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

Creating an OData Web Service with F#

Jomo Fisher — Sat, 29 May 2010 00:17:52 GMT

Jomo Fisher—I’ve spent a little time looking at the OData Web Service Protocol. There is quite a lot to like about it. It is an open, REST-ful format for communicating with a web service as if it were a database. You can query an OData service with LINQ.

To help me learn about it I set out to write a simple OData web service. I expected to have to do quite a lot of work because OData is very rich and just parsing the urls, which can contain SQL-like queries, looked to be hard work.

It turned out, however, to be pretty straight-forward. You basically just need to implement IDataServiceQueryProvider and IDataServiceMetadataProvider. All the heavy-lifting in terms of parsing is done for you. You get a nice System.Linq Expression which is easy to deal with (mainly because my service uses LINQ to Objects under the covers).

If you’d like to take a look at the service I wrote, I published it on Visual Studio Gallery. You just need to go to File\New Project in Visual Studio 2010:

Please let me know what you think, and whether you have any issues or spot any bugs.

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

F# Object Oriented Programming

Jomo Fisher — Wed, 26 May 2010 22:44:50 GMT

Jomo Fisher—F# has a functional heritage but it is actually very good at OO as well. Here’s an example of its nice, clean syntax for declaring a class:

Code Snippet
 type Vector(x : float, y : float) =
    member this.X = x
    member this.Y = y
 

Tim Ng posted a nice comparison of F# to C# for OO language features. If you’re a C# programmer interested in F#, this is a great place to start.

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

How to Enumerate all WMI Classes

Jomo Fisher — Tue, 25 May 2010 17:08:44 GMT

Jomo Fisher—Quick sample today. I’m mainly posting this because it took me a while to figure it out and I hope it might save someone some time. This is the F# code you would useto enumerate all WMI classes on your system and show the properties of each. of each.

Code Snippet
// WalkWmiTypes.fsx 
// Enumerate all WMI types on the local machine and show their property names and types. 
#r "System.Management" 
open System.Management 
  
let scope = ManagementScope("\\\\localhost\\root\\cimv2") 
let path = ManagementPath("") 
let mclass = new ManagementClass(scope, path, ObjectGetOptions()) 
let options = EnumerationOptions() 
options.EnumerateDeep <- true 
  
for obj in mclass.GetSubclasses(options) do 
    printfn "%s" (obj.ToString().Split(':').[1]) 
    for prop in obj.Properties do 
        printfn "    %s:%A" prop.Name prop.Type 

This is pure .NET, so it should be easily translatable to C# and VB. Let me know if you run into problems with that. The result looks like:

Output
Msft_WmiProvider_DeleteClassAsyncEvent_Post 
    ClassName:String 
    Flags:UInt32 
    HostingGroup:String 
    HostingSpecification:UInt32 
    Locale:String 
    Namespace:String 
    ObjectParameter:Object 
    provider:String 
    ResultCode:UInt32 
    SECURITY_DESCRIPTOR:UInt8 
    StringParameter:String 
    TIME_CREATED:UInt64 
    TransactionIdentifer:String 
    User:String 

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

F# Destroys Invading Aliens

Jomo Fisher — Thu, 18 Mar 2010 15:50:16 GMT

Wow, check out Chris’s StarCraft bot in F#: http://blogs.msdn.com/chrsmith/archive/2010/03/18/writing-a-starcraft-bot-in-f.aspx

F# Team is Hiring a Cross-Platform Developer

Jomo Fisher — Mon, 15 Mar 2010 20:29:10 GMT

We’re hiring a developer to help advance our cross-platform presence. Please do send and application if this looks like a good match for you.

From Don Syme’s blog:

Contract Position in the F# Team: Compiler and Visual Tools Software Engineer for Cross-Platform F#

We are now seeking applications for a contract position with the F# team!

Contract length: 9 months – 1 year
Hiring Group: Microsoft Research, Cambridge
Location: Cambridge UK. Remote working possible.

F# is a cross-platform language executing on any CLI implementation, including those found on Windows, Mac OS/X, Linux, Silverlight, XBox 360 and mobile phones. We are seeking a talented and highly motivated software engineer with experience in compilers and/or visual tools to make targeted improvements to the support the execution, development and tools experience across these platforms. Other tasks will include working with implementors of these CLI implementations, preparing web hosted material, preparing components for shared and open source release, working directly with communities interested in using F# across multiple platforms, including universities, and preparing demonstration applications for the use of F# across platforms.

The ideal candidate would have a passion for the F# language, strong .NET programming skills, knowledge of web design and programming, and knowledge of several of the above platforms. Experience in authoring parts of a compiler and/or interactive development environment would also be helpful, as would experience in open source development. The candidate will have the opportunity to work as part of the F# team in Cambridge UK, and a portion of remote working would also be considered.

Please send applications to Don Syme (dsyme@microsoft.com), or Ruth Lenton (ruth.lenton@microsoft.com)

http://blogs.msdn.com/dsyme/archive/2010/03/10/contract-position-in-the-f-team-compiler-and-visual-tools-software-engineer-for-cross-platform-f.aspx

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

Neat Samples: MEF in F# Scripts

Jomo Fisher — Wed, 10 Mar 2010 18:34:00 GMT

Jomo Fisher—I posted yesterday about using MEF in F# programs. In the comments Oldrich asked if it was possible to do the same thing in F# scripts. It is indeed possible. It actually looks like a really powerful combination because you can naturally extend your scripts just by adding new #load directives at the top.

There are three pieces to this sample. You have to break your interfaces out into a separate .fsx. Realistically, you’d probably do this in a real compiled F# program too so this isn’t a huge burden on simplicity.

Code Snippet

// MefInterfaces.fsx
// Expose an interface
type ITastyTreat =
    abstract Description : string

Code Snippet

// ChocolateCookie.fsx
#r "System.ComponentModel.Composition"
#load "MefInterfaces.fsx"
namespace ChocolateCookie
open MefInterfaces
open System.ComponentModel.Composition
[<Export(typeof<ITastyTreat>)>]
type ChocolateCookie() = 
    interface ITastyTreat with 
        member __.Description = "a delicious chocolate cookie"

Code Snippet

// MefHost.fsx
#load "ChocolateCookie.fsx"
open System.Reflection
open System.IO
open System.ComponentModel.Composition
open System.ComponentModel.Composition.Hosting
open MefInterfaces
// Set up MEF
let catalog = new AggregateCatalog()
let assemblyCatalog = new AssemblyCatalog(Assembly.GetExecutingAssembly())
let container = new CompositionContainer(catalog)
catalog.Catalogs.Add(assemblyCatalog)
// Jar that will contain tasty treats
type TreatJar() = 
    [<ImportMany(typeof<ITastyTreat>)>] 
    let cookies : seq<ITastyTreat> = null
    member __.EatTreats() =
        cookies |> Seq.iter(fun tt->printfn "Yum, it was a %s" tt.Description)
let jar = TreatJar()
container.ComposeParts(jar)
jar.EatTreats()

Thanks Oldrich, for giving me an excuse to try this out.

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

Neat Samples: Extend your F# program with MEF

Jomo Fisher — Wed, 10 Mar 2010 00:32:39 GMT

Jomo Fisher—The Managed Extensibility Framework is an interesting new technology in .NET 4.0. It lets you set up a plug in system for your application so that your program can acquire new functionality just by, for example, adding a .dll into a particular directory.

This is a simple example in F#. This code sets up MEF hosting and asks for all extensions in the c:\extensions folder.

Code Snippet
 // Host.fs
// A MEF host that eats tasty treats
open System.Reflection
open System.IO
open System.ComponentModel.Composition
open System.ComponentModel.Composition.Hosting
 
// Expose an interface
type ITastyTreat =
    abstract Description : string
 
// Set up MEF
let catalog = new AggregateCatalog()
let directoryCatalog = new DirectoryCatalog(@"c:\Extensions","*.dll")
let container = new CompositionContainer(catalog)
catalog.Catalogs.Add(directoryCatalog)
 
// Jar that will contain tasty treats
type TreatJar() = 
    [<ImportMany(typeof<ITastyTreat>)>] 
    let cookies : seq<ITastyTreat> = null
 
    member __.EatTreats() =
        cookies |> Seq.iter(fun tt->printfn "Yum, it was a %s" tt.Description)
 
let jar = TreatJar()
container.ComposeParts(jar)
jar.EatTreats()
 

This is how you implement an extension. Just build this into a .dll and drop it in the c:\extensions directory.

Code Snippet
 namespace ChocolateCookie
open Host
open System.ComponentModel.Composition
 
[<Export(typeof<ITastyTreat>)>]
type ChocolateCookie() = 
    interface ITastyTreat with 
        member __.Description = "a delicious chocolate cookie"
 

Now, if you run the host program you should see this:

Yum, it was a a delicious chocolate cookie
Press any key to continue . . .

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

Neat Samples: F#, Freebase and DGML

Jomo Fisher — Sat, 06 Mar 2010 21:37:26 GMT

Jomo Fisher – I recently posted about the freebase web service here. This sample reads biological classifications and renders them in DGML. The result is a huge graph, here’s a little piece of it:

Code Snippet
 // FreebaseDgml.fsx 
// Example of reading from freebase.com in F# using DataContract and JSON serializer and write the result
// in .dgml format.
// by Jomo Fisher 
#r "System.Runtime.Serialization" 
#r "System.ServiceModel.Web" 
#r "System.Web" 
#r "System.Xml" 
  
open System 
open System.IO 
open System.Net 
open System.Text 
open System.Web 
open System.Collections.Generic
open System.Security.Authentication 
open System.Runtime.Serialization 
  
[<DataContract>] 
type Result<'TResult> = { 
    [<field: DataMember(Name="code") >] 
    Code:string 
    [<field: DataMember(Name="result") >] 
    Result:'TResult 
    [<field: DataMember(Name="message") >] 
    Message:string 
    } 
 
[<DataContract>] 
type Classification = { 
    [<field: DataMember(Name="name") >] 
    Name:string 
    [<field: DataMember(Name="higher_classification") >] 
    HigherClassification:string 
    [<field: DataMember(Name="lower_classifications") >] 
    LowerClassifications:string array
    } 
  
let Query<'T>(query:string) : 'T = 
    let query = query.Replace("'","\"") 
    let queryUrl = sprintf "http://api.freebase.com/api/service/mqlread?query=%s" "{\"query\":"+query+"}" 
  
    let request : HttpWebRequest = downcast WebRequest.Create(queryUrl) 
    request.Method <- "GET" 
    request.ContentType <- "application/x-www-form-urlencoded" 
  
    let response = request.GetResponse() 
  
    let result = 
        try 
            use reader = new StreamReader(response.GetResponseStream()) 
            reader.ReadToEnd(); 
        finally 
            response.Close() 
  
    let data = Encoding.Unicode.GetBytes(result); 
    let stream = new MemoryStream() 
    stream.Write(data, 0, data.Length); 
    stream.Position <- 0L 
     
    let ser = Json.DataContractJsonSerializer(typeof<Result<'T>>) 
    let result = ser.ReadObject(stream) :?> Result<'T> 
    if result.Code<>"/api/status/ok" then 
        raise (InvalidOperationException(result.Message)) 
    else 
        result.Result 
  
let classifications = Query<Classification array>("[{'type':'/biology/organism_classification','name':null,'higher_classification':null,'lower_classifications':[]}]") 
 
 
let sb = StringBuilder()
  
sb.Append("<DirectedGraph xmlns='http://schemas.microsoft.com/vs/2009/dgml'>\n") |> ignore
 
sb.Append(" <Links>\n") |> ignore
for classification in classifications do 
    if classification.LowerClassifications<>null then
        for lower in classification.LowerClassifications do
            sb.AppendFormat("  <Link Source=\"{0}\" Target=\"{1}\"/>\n",classification.Name,lower) |> ignore
sb.Append(" </Links>\n") |> ignore
sb.Append("</DirectedGraph>\n") |> ignore
 
printfn "%s" (sb.ToString()) // Paste the results of this into a .dgml file.           
 

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

Neat Sample: F# and Bing API

Jomo Fisher — Sat, 06 Mar 2010 20:32:17 GMT

Jomo Fisher – I recently posted an sample of calling the Freebase web service with F#. Here’s another F# web service sample. This one uses the Bing Phone API to do a query. This time the code uses Xml instead of JSON and XmlDocument instead of a DataContract deserializer. This is pretty much a straight transliteration of one of the Bing SDK samples.

Code Snippet
 // BingPhone.fsx
// An example of using the a Bing web service API from F#
// by Jomo Fisher
open System.Net
open System.Xml
 
let appId = "your app id goes here";
 
let BuildRequest() : HttpWebRequest  = 
    let requestString = 
        "http://api.bing.net/xml.aspx?"
 
            // Common request fields (required)
            + "AppId=" + appId
            + "&Query=microsoft offices"
            + "&Sources=Phonebook"
 
            // Common request fields (optional)
            + "&Version=2.0"
            + "&Market=en-us"
            + "&UILanguage=en"
            + "&Latitude=47.603450"
            + "&Longitude=-122.329696"
            + "&Radius=10.0"
 
            // Phonebook-specific request fields (optional)
            + "&Phonebook.Count=10"
            + "&Phonebook.Offset=0"
            + "&Phonebook.FileType=YP"
            + "&Phonebook.SortBy=Distance";
 
    // Create and initialize the request.
    downcast HttpWebRequest.Create(requestString)
 
let DisplayErrors(errors:XmlNodeList) = 
    // Iterate over the list of errors and display error details.
    printfn "Errors:"
    for error in errors do
        for detail in error.ChildNodes do 
            printfn "%s: %s" detail.Name detail.InnerText
 
let DisplayResults( root:XmlNode, nsmgr:XmlNamespaceManager) = 
    // Add the Phonebook SourceType namespace to the namespace manager.
    nsmgr.AddNamespace("pho", "http://schemas.microsoft.com/LiveSearch/2008/04/XML/phonebook")
 
    let phonebook = root.SelectSingleNode("./pho:Phonebook", nsmgr)
    let results = phonebook.SelectNodes("./pho:Results/pho:PhonebookResult",nsmgr)
 
    let version = root.SelectSingleNode("./@Version", nsmgr).InnerText
    let searchTerms = root.SelectSingleNode("./api:Query/api:SearchTerms",nsmgr).InnerText
    let _,offset = System.Int32.TryParse(phonebook.SelectSingleNode("./pho:Offset", nsmgr).InnerText)
    let _,total =  System.Int32.TryParse(phonebook.SelectSingleNode("./pho:Total", nsmgr).InnerText)
 
    // Display the results header.
    printfn "Bing API Version %s" version
    printfn "Phonebook results for %s" searchTerms
    printfn "Displaying %d to %d of %d results" (offset + 1) (offset + results.Count) total
 
    // Display the Phonebook results.
    let builder = System.Text.StringBuilder();
    for result in results do
        builder.Length <- 0
        builder
            .AppendLine(result.SelectSingleNode("./pho:Business", nsmgr).InnerText)
            .AppendLine(result.SelectSingleNode("./pho:Address", nsmgr).InnerText)
            .Append(result.SelectSingleNode("./pho:City", nsmgr).InnerText)
            .Append(", ")|>ignore
 
        let stateOrProvince = result.SelectSingleNode("./pho:StateOrProvince", nsmgr).InnerText
        builder
            .AppendLine(stateOrProvince)
            .AppendLine(result.SelectSingleNode("./pho:PhoneNumber", nsmgr).InnerText)
            .Append("Average Rating: ")
            .AppendLine(result.SelectSingleNode("./pho:UserRating", nsmgr).InnerText)|>ignore
 
        printfn "%s" (builder.ToString())
 
let DisplayResponse(response:HttpWebResponse) = 
    // Load the response into an XmlDocument.
    let document = XmlDocument()
    document.Load(response.GetResponseStream());
 
    // Add the default namespace to the namespace manager.
    let nsmgr = XmlNamespaceManager(document.NameTable);
    nsmgr.AddNamespace("api","http://schemas.microsoft.com/LiveSearch/2008/04/XML/element");
 
    let errors = document.DocumentElement.SelectNodes("./api:Errors/api:Error", nsmgr)
 
    if errors.Count > 0 then
        // There are errors in the response. Display error details.
        DisplayErrors(errors);
    else
        // There were no errors in the response. Display the
        // Phonebook results.
        DisplayResults(document.DocumentElement, nsmgr);
 
 
let request = BuildRequest()
 
try
    // Send the request; display the response.
    let response = request.GetResponse()
    DisplayResponse(downcast response)
with ex ->
    // An exception occurred while accessing the network.
    printfn "%s" ex.Message
 

As before, let me know if there are other F# samples you’d like to see.

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

Neat Sample: F# and Freebase

Jomo Fisher — Sat, 06 Mar 2010 18:20:41 GMT

Jomo Fisher – The web service at Freebase.com lets you access all sorts of structured data from a web service. Here’s a sample that shows you how to access this data from F#. It uses DataContract and the JSON serializer. The code below reads and prints the elements of the periodic table.

Code Snippet
 // Freebase.fsx 
// Example of reading from freebase.com in F# using DataContract and JSON serializer
// by Jomo Fisher
#r "System.Runtime.Serialization"
#r "System.ServiceModel.Web"
#r "System.Web"
#r "System.Xml"
 
open System
open System.IO
open System.Net 
open System.Text 
open System.Web
open System.Security.Authentication 
open System.Runtime.Serialization
 
[<DataContract>]
type Result<'TResult> = {
    [<field: DataMember(Name="code") >]
    Code:string
    [<field: DataMember(Name="result") >]
    Result:'TResult
    [<field: DataMember(Name="message") >]
    Message:string
    }
 
[<DataContract>]
type ChemicalElement = {
    [<field: DataMember(Name="name") >]
    Name:string
    [<field: DataMember(Name="boiling_point") >]
    BoilingPoint:string
    [<field: DataMember(Name="atomic_mass") >]
    AtomicMass:string
    }
 
let Query<'T>(query:string) : 'T =
    let query = query.Replace("'","\"")
    let queryUrl = sprintf "http://api.freebase.com/api/service/mqlread?query=%s" "{\"query\":"+query+"}"
 
    let request : HttpWebRequest = downcast WebRequest.Create(queryUrl)
    request.Method <- "GET"
    request.ContentType <- "application/x-www-form-urlencoded"
 
    let response = request.GetResponse()
 
    let result = 
        try 
            use reader = new StreamReader(response.GetResponseStream())
            reader.ReadToEnd(); 
        finally 
            response.Close()
 
    let data = Encoding.Unicode.GetBytes(result);
    let stream = new MemoryStream()
    stream.Write(data, 0, data.Length);
    stream.Position <- 0L
    
    let ser = Json.DataContractJsonSerializer(typeof<Result<'T>>)
    let result = ser.ReadObject(stream) :?> Result<'T>
    if result.Code<>"/api/status/ok" then
        raise (InvalidOperationException(result.Message))
    else 
        result.Result
 
let elements = Query<ChemicalElement array>("[{'type':'/chemistry/chemical_element','name':null,'boiling_point':null,'atomic_mass':null}]")
 
elements |> Array.iter(fun element->printfn "%A" element)
 

Let me know if there are other F# samples you’d like to see.

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

F# February 2010 Release is out

Jomo Fisher — Thu, 11 Feb 2010 16:17:00 GMT

Don just put the announcement up: http://blogs.msdn.com/dsyme/archive/2010/02/10/announcing-the-f-february-2010-release.aspx

This is the version we've been using internally for a month or so and it is really polished and working nicely. Download it and give it a try.

F# Scripting, .NET 4.0 and Mixed-mode assemblies

Jomo Fisher — Tue, 17 Nov 2009 20:32:38 GMT

Jomo Fisher—There is a nice F# and DirectX demo that has been floating around for a while now. A recent version can be found here: http://code.msdn.microsoft.com/fsharpsamples/Wiki/View.aspx?title=Home&version=2

One of the recent problems we’ve seen is that, because of the support for side-by-side runtimes, .NET 4.0 has changed the way that it binds to older mixed-mode assemblies. These assemblies are, for example, those that are compiled from C++\CLI. Currently available DirectX assemblies are mixed mode. If you see a message like this then you know you have run into the issue:

Mixed mode assembly is built against version 'v1.1.4322' of the runtime and cannot be loaded in the 4.0 runtime without additional configuration information.

Though you may see it in the F# interactive, this message originates as an exception in the .NET 4.0 runtime. You may also see the message if you recompile a C#, VB or F# application that uses DirectX or other mixed-mode assembly against the .NET 4.0 runtime.

The good news for applications is that you have the option of falling back to .NET 2.0 era binding for these assemblies by setting an app.config flag like so:

<startup useLegacyV2RuntimeActivationPolicy="true">
<supportedRuntime version="v4.0"/>
</startup>

Things get a little trickier for scripts, though, since there is no .exe running. Here is a little snippet of code you can run in the F# repl to switch to 2.0 binding mode:

open System

open System.Runtime.InteropServices

open System.Runtime.CompilerServices

[<ComImport>]

[<InterfaceType(ComInterfaceType.InterfaceIsIUnknown)>]

[<Guid("BD39D1D2-BA2F-486A-89B0-B4B0CB466891")>]

type ICLRRuntimeInfo =

    // vtable slots

    abstract xGetVersionString : unit -> unit

    abstract xGetRuntimeDirectory : unit -> unit

    abstract xIsLoaded : unit -> unit

    abstract xIsLoadable : unit -> unit

    abstract xLoadErrorString : unit -> unit

    abstract xLoadLibrary : unit -> unit

    abstract xGetProcAddress : unit -> unit

    abstract xGetInterface : unit -> unit

    abstract xSetDefaultStartupFlags : unit -> unit

    abstract xGetDefaultStartupFlags : unit -> unit

    [<MethodImpl(MethodImplOptions.InternalCall, MethodCodeType=MethodCodeType.Runtime)>]

    abstract BindAsLegacyV2Runtime : unit -> unit

let rtInfo = RuntimeEnvironment.GetRuntimeInterfaceAsObject(Guid.Empty,typeof<ICLRRuntimeInfo>.GUID) :?> ICLRRuntimeInfo

rtInfo.BindAsLegacyV2Runtime()

This needs to be the first thing that runs in your interactive window.

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

F# Performance Tweaking

Jomo Fisher — Tue, 16 Sep 2008 21:14:00 GMT

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 — Tue, 02 Sep 2008 06:09:00 GMT

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"

Assuming you have all the stuff you need installed, when you run this script you’ll get an Excel spreadsheet:

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"

You would do this, for example, if your script only works with a particular version of an assembly or if you want to reference and older version.

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 — Sat, 30 Aug 2008 17:40:00 GMT

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 []

We’ve tried to bring this same philosophy of power and economy when integrating F# into Visual Studio. While F# does offer traditional MSBuild-based project support, sometimes you just want to write some code and not worry about projects and solutions. This is what F# scripts are for.

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.

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

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

Update on Fast Switching with LINQ

Jomo Fisher — Fri, 29 Aug 2008 18:44:00 GMT

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 — Mon, 25 Aug 2008 05:12:19 GMT

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 — Fri, 23 May 2008 00:59:00 GMT

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#

Jomo Fisher — Tue, 22 Apr 2008 22:56:00 GMT

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 — Wed, 12 Dec 2007 19:09:00 GMT

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 — Sat, 17 Nov 2007 22:37:51 GMT

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

Jomo Fisher — Tue, 30 Oct 2007 23:33:32 GMT

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 — Tue, 23 Oct 2007 20:31:03 GMT

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 — Mon, 22 Oct 2007 07:43:00 GMT

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:

for result in query @"file.txt" do

let url, count = result

One nice thing is that F#'s interactive window has a #time;; option which shows you wall-clock time and CPU time. Here is the result from running the code above on a 256meg file I concatenated together (I couldn't find the one Don was using):

Real: 00:00:06.899, CPU: 00:00:04.165, GC gen0: 416, gen1: 1, gen2: 0

It looks like the majority of the time is in CPU so there should be ample opportunity to parallelize. One thing to note: I think the interactive window is unoptimized--when I just compile and run the code, I get times in the sub 5-seconds range. My machine is a 4-way 2.4 GHz Core Duo.

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