Chris Smith's completely unique view

Lightweight PGN parser in F# – Part I

ChrSmith — Sat, 13 Jun 2009 19:43:27 GMT

If you’ve ever spent a lot of time around the game of Chess you’ve probably seen or interacted with the PGN file format in one way or another. PGN stands for Portable Game Notation and is a concise way to represent Chess games.

Using regular expressions I’ve written a very lightweight parser to handle the file format. I wouldn’t be surprised if the regular expressions don’t capture every legal .pgn file, but it shows how effective regular expressions can be for semi-structured data.

Not being a Chess player myself, I’m not really sure what to do with:

"Nxf7 Rxe1+"

but perhaps I’ll look at that in a future blog post.

Edit: On second thought, there is all sorts of wrong with this parser. For example, notice how move ‘3’ is listed twice. The ‘3…’ continues on after the comment.

Alas, once the raw list of moves is parsed another step to coalesce them is required. In addition, a commenter pointed out that the 1/2-1/2 is the result of the game (a draw). I’ll spend a little more time on this before I can call it an official ‘parser’ but it’s a nice start :D.

open System.Text.RegularExpressions

let pgnGameText = "
[Event \"F/S Return Match\"]
[Site \"Belgrade, Serbia Yugoslavia|JUG\"]
[Date \"1992.11.04\"]
[Round \"29\"]
[White \"Fischer, Robert J.\"]
[Black \"Spassky, Boris V.\"]
[Result \"1/2-1/2\"]
 
1. e4 e5 2. Nf3 Nc6 3. Bb5 {This opening is called the Ruy Lopez.} 3... a6
4. Ba4 Nf6 5. O-O Be7 6. Re1 b5 7. Bb3 d6 8. c3 O-O 9. h3 Nb8  10. d4 Nbd7
11. c4 c6 12. cxb5 axb5 13. Nc3 Bb7 14. Bg5 b4 15. Nb1 h6 16. Bh4 c5 17. dxe5
Nxe4 18. Bxe7 Qxe7 19. exd6 Qf6 20. Nbd2 Nxd6 21. Nc4 Nxc4 22. Bxc4 Nb6
23. Ne5 Rae8 24. Bxf7+ Rxf7 25. Nxf7 Rxe1+ 26. Qxe1 Kxf7 27. Qe3 Qg5 28. Qxg5
hxg5 29. b3 Ke6 30. a3 Kd6 31. axb4 cxb4 32. Ra5 Nd5 33. f3 Bc8 34. Kf2 Bf5
35. Ra7 g6 36. Ra6+ Kc5 37. Ke1 Nf4 38. g3 Nxh3 39. Kd2 Kb5 40. Rd6 Kc5 41. Ra6
Nf2 42. g4 Bd3 43. Re6 1/2-1/2
"

// Remove comments and markup from the PGN file
let removeMarkup text = 
    let tagPairs = new Regex(@"\[.*\]")
    let noTagPairs = tagPairs.Replace(text, "")

    let comments = new Regex(@"\{.*\}")
    let noComments = comments.Replace(noTagPairs, "")
    
    // Trim any leading whitespace and convert to a single-line
    noComments.Trim().Replace("\r", "").Replace("\n", " ")
        
// Get the list of moves, each prefixed with a number and one or three dots
let getMoves text =
    let factRegex = new Regex(@"\d+\.+", RegexOptions.Multiline)
    factRegex.Split(text)

let normalizedText = removeMarkup pgnGameText
    
let printGameMoves() = 
    getMoves normalizedText
    |> Array.map (fun move -> move.Trim())
    |> Array.iteri (fun idx move -> printfn "Move %2d: %s" idx move)

(*
OUTPUT:

> printGameMoves();;
Move  0: 
Move  1: e4 e5
Move  2: Nf3 Nc6
Move  3: Bb5
Move  4: a6
Move  5: Ba4 Nf6
Move  6: O-O Be7
Move  7: Re1 b5
Move  8: Bb3 d6
Move  9: c3 O-O
Move 10: h3 Nb8
Move 11: d4 Nbd7
Move 12: c4 c6
Move 13: cxb5 axb5
Move 14: Nc3 Bb7
Move 15: Bg5 b4
Move 16: Nb1 h6
Move 17: Bh4 c5
Move 18: dxe5 Nxe4
Move 19: Bxe7 Qxe7
Move 20: exd6 Qf6
Move 21: Nbd2 Nxd6
Move 22: Nc4 Nxc4
Move 23: Bxc4 Nb6
Move 24: Ne5 Rae8
Move 25: Bxf7+ Rxf7
Move 26: Nxf7 Rxe1+
Move 27: Qxe1 Kxf7
Move 28: Qe3 Qg5
Move 29: Qxg5 hxg5
Move 30: b3 Ke6
Move 31: a3 Kd6
Move 32: axb4 cxb4
Move 33: Ra5 Nd5
Move 34: f3 Bc8
Move 35: Kf2 Bf5
Move 36: Ra7 g6
Move 37: Ra6+ Kc5
Move 38: Ke1 Nf4
Move 39: g3 Nxh3
Move 40: Kd2 Kb5
Move 41: Rd6 Kc5
Move 42: Ra6 Nf2
Move 43: g4 Bd3
Move 44: Re6 1/2-1/2
val it : unit = ()
*)

Programming F# – Official Cover

ChrSmith — Thu, 14 May 2009 01:18:00 GMT

So as it turns out my petition for a kickass cover was ultimately unsuccessful. But the good news is that I’m not suck with something neither cute nor cuddly. Instead I got a Jellyfish, after spending some time thinking about it is pretty good. (Though certainly not as awesome as a hydra.)

Jellyfish Facts

Jellyfish can be found in every ocean. Therefore, in the time if trouble they can call on the nine pirate lords for help. Much like F# being able to use nine different programming paradigms and styles:

functional, imperative, object-oriented, metaprogramming, scripting, concurrent, reactive, declaritive, and awesome. (Yes, ‘awesome’ is a programming paradigm… and Haskell doesn’t support it.)

Jellyfish do not have a brain or central nervous system. Just like F#… umm… you don’t need a nervous system to write world-class applications? Let me get back to you on this one…
The real reason I’m excited about having a Jellyfish on the cover is that they can Sting and Kill you. Like F#, Jellyfish are deadly.

So anyways, this October be on the lookout for Jellyfish Book!

F# Scripting Zen – Bulk Updating Testcases

ChrSmith — Sat, 09 May 2009 17:35:00 GMT

As the F# team is busy working to finish up Visual Studio 2010, one task left to complete is to localize the compiler, so that on a Japanese machine the error messages will be in Japanese.

While I’m sure a few Ugly American Programmers might question the value of localized error messages, imagine if the F# compiler told you this every time you made a mistake:

"このタイプのパラメータ値を推定タイプ略語の安定の下では、消去されていません。このドロップ、または並べ替えのタイプのパラメータを、のタイプは、例えば、略語の使用によるものです< ' a >を= はまたは\ Ñ \ ttypeスワップ< 'は、 ' b > = ' b * 'を1つの。明示的にこの値の型のパラメータを宣言、 \ Ñ例： \ tlet金< 'は、 ' b > （（ x 、 y ）に：スワップ< ' b 、 ' a >を参照）：スワップ< 'は、 ' b > = （イは、 X ）"

Anyways, my job is to update our F# compiler test automation to be localization agonistic. Meaning that tests will work just fine on both English, Japanese, and any of the other dozen or so languages Visual Studio gets localized to.

The majority of our compiler automation works by taking a code file, compiling and running it, and if the process returns with a non-zero exit code report a failure. Negative tests - where we expect the code file not to compile – work by checking the compiler output for specific messages.

The following is a sample F# compiler testcase. Note that the ‘expected message’ is an arbitrary regular expression, which is why the ‘(‘ and ‘)’ need to be escaped with a backslash.

// FSB 1488, Implement redundancy checking for dynamic type test patterns

//<Expects status=warning>\(9,7-9,16\): warning FS0026: This rule will never be matched</Expects>

//<Expects status=warning>\(15,7-15,16\): warning FS0026: This rule will never be matched</Expects>

let _ =

match box "3" with

| :? string -> 1

| :? string -> 1 // check this rule is marked as 'never be matched'

| _ -> 2

let _ =

match box "3" with

| :? System.IComparable -> 1

| :? string -> 1 // check this rule is marked as 'never be matched'

| _ -> 2

exit 0

As you can probably guess, matching against English compiler output is problematic when testing a localized compiler. The F# QA team (consisting of 3 people) discussed a few options, but the design we settled on was simply encode more metadata into the ‘Expects’ tag, and simply not validate specific error text on non-English builds.

So we want to rewrite all of our negative tests to look something like this:

// FSB 1488, Implement redundancy checking for dynamic type test patterns

//<Expects id="FS0026" span=(9,7-9,16) status="warning">This rule will never be matched</Expects>

//<Expects id="FS0026" span=(15,7-15,16) status="warning">This rule will never be matched</Expects>

let _ =

match box "3" with

| :? string -> 1

| :? string -> 1 // check this rule is marked as 'never be matched'

| _ -> 2

let _ =

match box "3" with

| :? System.IComparable -> 1

| :? string -> 1 // check this rule is marked as 'never be matched'

| _ -> 2

exit 0

When the testcase is in this format, then rather than just matching the ‘message text’ we can build up the regular expression which we will match against the compiler output. So we will look for something like: <span> + <message id> + <text>.

Then, on localized installs we simply won’t match the text. (But still validate the line/column span of the error, and the error ID from the compiler.) This, combined with a little loc-specific testing, should be enough.

So how do you fix the testbed? We have ~1,600 automated testcases which use the <Expects> technique, of those ~600 which need to be updated. As much as I love manually going through and tweaking formatting of testcases, hopefully I can put my F# knowledge to good use and whip up an F# script do to this for me.

Defining Types

Before solving a problem in F#, the first step is usually defining new types. In this case, we want to create types to describe the metadata encoded in testcases.

I’d like to draw your attention to how concise F#’s syntax is for declaring types. If this were C# you would need to sprinkle in property getters and setters, curly braces and semicolons. Instead, creating discriminated unions and records is straight forward. In addition, I’ve added a static Parse methods which we will use later.

type MessageType =

| Warning

| Error

| NotIn

| Success

override this.ToString() =

match this with

| Warning -> "warning"

| Error -> "error"

| NotIn -> "notin"

| Success -> "success"

static member Parse(txt : string) =

match txt.ToUpper() with

| "WARNING" | "\"WARNING\"" -> Warning

| "ERROR" | "\"ERROR\"" -> Error

| "NOTIN" | "\"NOTIN\"" -> NotIn

| "SUCCESS" | "\"SUCCESS\"" -> Success

| _ -> failwithf "Unknown message type: [%s]" txt

type MessageRange =

| NoRange // No error range specified

| OnePoint of int * int // (a,b)

| TwoPoints of int * int * int * int // (a,b-c,d)

static member Parse(txt : string) =

let onePtRegex = @".*\\\((\d+),(\d+)\\\).*"

let twoPtRegex = @".*\\\((\d+),(\d+)-(\d+),(\d+)\\\).*"

let onePtMatch = Regex.Match(txt, onePtRegex)

let twoPtMatch = Regex.Match(txt, twoPtRegex)

if onePtMatch.Success then

OnePoint(int onePtMatch.Groups.[1].Value, int onePtMatch.Groups.[2].Value)

elif twoPtMatch.Success then

TwoPoints(int twoPtMatch.Groups.[1].Value, int twoPtMatch.Groups.[2].Value,

int twoPtMatch.Groups.[3].Value, int twoPtMatch.Groups.[4].Value)

else

NoRange

type ExpectedMessage =

{

MsgType : MessageType

MsgID : string

MsgRange : MessageRange

MsgText : string

}

Parsing (AKA Regular Expression voodoo)

Here comes the fun part: greping through each tescase file and trying to parse it using regular expressions.

I’ll be honest when I say that we haven’t been super-consistent in how to encode error messages. So some tests have error spans, some don’t. Some match the error ID, some don’t.

Admittedly this code could be better commented, but it should be pretty straight forward. Note that the removeTokens function could easily be rewritten to be a bunch of functions composed together (rather than using piplining). Having the separate ‘fixLineForm'X’ methods makes debugging a tad easier.

/// Given the match string for a testcase strip out error spans and compiler error numbers.

/// E.G. "\(9,18-9,21\): warning FS0035: This form of object expression is deprecated."

/// becomes: "This form of object expression is deprecated"

let removeTokens line =

let fixLine regexPattern (groupIdx : int) line =

let m =

Regex.Match(

line,

regexPattern)

if m.Success then

m.Groups.[groupIdx].Value

else

line

// Specify error range (a,b-c,d): error FS????:

let fixLineForm1 = fixLine @"\\\(\d+,\d+-\d+,\d+\\\)..(error|warning) FS\d\d\d\d..([^<]*)" 2

// Specify error range (a,b): error FS????:

let fixLineForm2 = fixLine "\\(\d+,\d+\\): (error|warning) FS\d\d\d\d..([^<]*)" 2

// Start with error FS????:

let fixLineForm3 = fixLine @"(error|warning) FS\d\d\d\d..([^<]*)" 2

// Start with FS????:

let fixLineForm4 = fixLine @"FS\d\d\d\d..([^<]*)" 1

// Just error range (Note this must come before line form1)

let fixLineForm5 = fixLine @"\\\(\d+,\d+-\d+,\d+\\\)..([^<]*)" 1

// Just error FS????

let fixLineForm6 = fixLine @"(error|warning) FS\d\d\d\d([^<]*)" 2

line |> fixLineForm1 |> fixLineForm2

|> fixLineForm3 |> fixLineForm4

|> fixLineForm5

/// If the line contains an <Expects> block, parse out the error ID, span, and text
/// and rewrite it making them explicit.

let fixExpectedMessageLine line =

let isMessageLineRegex = "//.*<Expect[^>]*status=([^>]+)>([^<]*)</Expect.+"

let m = Regex.Match(line, isMessageLineRegex)

if m.Success then

// If we've identified it as a line containing testcase metadata,

// parse it and rewrite it.

let message =

{

MsgType = MessageType.Parse(m.Groups.[1].Value)

MsgID = (let id = Regex.Match(m.Groups.[2].Value, ".*(FS\d\d\d\d).*")

if id.Success then id.Groups.[1].Value

else "FS0191")

MsgRange = MessageRange.Parse(m.Groups.[2].Value)

MsgText = removeTokens (m.Groups.[2].Value)

}

let spanPart =

match message.MsgRange with

| NoRange -> ""

| OnePoint(x,y) -> sprintf "span=\"(%d,%d)\" " x y

| TwoPoints(a,b,c,d) -> sprintf "span=\"(%d,%d,%d,%d)\" " a b c d

if message.MsgType = Error || message.MsgType = Warning then

sprintf

"//<Expects id=\"%s\" %sstatus=\"%s\">%s</Expects>"

message.MsgID spanPart (message.MsgType.ToString()) message.MsgText

else

// Only rewrite negative tests, skip SUCCESS or NOTIN tests...

line

else

// This line didn't contain any metadata information

line

Fixing Testcases

The work to actually fix testcases requires a few utility functions. I’ll cover each one in order.

First is my favorite four-line sequence expression: return all files under a given folder. Using yield! inside of a sequence expression is quite sexy.

let rec filesUnder basePath =

seq {

yield! Directory.GetFiles(basePath)

for subDir in Directory.GetDirectories(basePath) do

yield! filesUnder subDir }

Next is creating a type called FixedFile, which keeps track of any changes we made to the source code. (That is, if we need to rewrite any lines containing testcase metadata.) The code simply tries to modify each line, and if the updated array of strings is different then we know the file has been modified.

You cannot compare two arrays to see if they are equal in C#, because it will use referential equality (comparing pointers.) The F# code on the other hand uses structural equality (comparing array elements).

type FixedFile = { FilePath : string; FileFixed : bool; UpdatedLines : string[] }

let fixFile filePath =

let lines = File.ReadAllLines(filePath)

let fixedLines = lines |> Array.map fixExpectedMessageLine

// Note use of structural equality

{

FilePath = filePath

FileFixed = (lines <> fixedLines)

UpdatedLines = fixedLines

}

Next is a couple of functions to checkout a file for edit using using Source Depot. (Shelling out to tf.exe to use Visual Studio Team Foundation Server would work just as well.)

/// Spawns a new process. Returns (exit code, stdout)

let shellExecute executablePath workingDir args =

let startInfo = new ProcessStartInfo()

startInfo.FileName <- executablePath

startInfo.WorkingDirectory <- workingDir

startInfo.Arguments <- args

startInfo.UseShellExecute <- false

startInfo.CreateNoWindow <- true

startInfo.RedirectStandardOutput <- true

let proc = Process.Start(startInfo)

proc.WaitForExit()

(proc.ExitCode, proc.StandardOutput.ReadToEnd())

/// Checks out a given file for edit

let checkoutFile filePath =

printfn "Checking out: %s" filePath

let pathToSD = @"d:\Tools\SourceDepot\sd.exe"

let enlistmentPath = @"D:\dd\cambridge_staging_3\src\"

// Add working directory so SD knows which client to use...

let (ec, txt) = shellExecute pathToSD enlistmentPath ("edit " + filePath)

printfn "SD exited with code %d\n%s" ec txt

()

Putting it Together

Unfortunately our script is somewhat anti-climactic. To fix all 600 compiler testcases the actual work is done in six lines of code:

@"D:\dd\cambridge_staging_3\src\tests\fsharpqa\Source"

|> filesUnder

|> Seq.map fixFile

|> Seq.filter (fun fixedFile -> fixedFile.FileFixed)

|> Seq.iter (fun ff -> checkoutFile ff.FilePath

File.WriteAllLines(ff.FilePath, ff.UpdatedLines))

So about 167 lines later, I have a script file that automates a task that would have easily taken a couple work days to complete. This F# script leveraged the existing IO and Regular Expressions libraries built into .NET, and can easily be packaged into a class library and shared with other developers.

So when you next encounter a problem you want to automate, consider looking to see if an F# script is the right solution for you.

F# Community Roundup

ChrSmith — Tue, 05 May 2009 16:17:55 GMT

There’s plenty going on in the F# community these days, I figured I’d provide a shameless plug for few blog posts or videos I especially liked.

Toronto F# Study Group

If you live in Soviet Canuckistan and are in the Toronto area, Justin Lee is hosting an F# Study Group at the Dark Horse Cafe in Spadina on Thursday, May 7th.

IL analysis using F#

Ian Voyce looks (briefly) at some minimal F# code for picking apart the IL of a managed assembly. This is certainly something that I’d love to see more of in the future.

To learn a bit more about IL, a great resource is Haibo Luo’s (now defunct) blog.

Jason Olson, the Tom Cruise of F#?

Jason Olson F# lover and all around nice guy has been busy the past few weeks:

Imperative Computation in F#

Thomas Petricek has a great blog post up showing how you can create imperative constructs for F# code when using computation expressions. In short, you can add support for break and continue within while loops (just like C#).

// Counts '1, 3, 5, 7, 9'
imperative { 
    for x in 1 .. 10 do 
        
        if x % 2 = 0 then 
            do! continue // <---
            
        printfn "number = %d" x 
}
 
// Counts '1, 2, 3' and then stops   
imperative { 
    for x in 1 .. 10 do

      if x >= 4 then 
        do! break // <---

      printfn "number = %d" !x
}

If you’d like to keep a better pulse on what the blogosphere has to say about F#, checkout the Planet F# RSS feed.

Idiomatic F# – Functional vs. Imperative

ChrSmith — Thu, 23 Apr 2009 16:37:16 GMT

Our story begins with this guy, Stuart Bowers, sipping functional programming cool aid out of a kickass mug from Cafe Press.

Stuart is a developer on Amalga and full-time F# developer at Microsoft. The world is at a loss because this man does not blog...

Anyways, he has been reviewing chapters some chapters of my book and we recently had a long conversation about what should be idiomatic F# style which I’d like to share.

The Problem

Question: What is the ‘correct F# way’ to write the following code:

Create a shared, mutable value and spawn two thread pool threads to sum elements in a list. (Intentionally creating a race condition, which was the point of the code example.)

The Imperative (?) Way

Let’s start with how to do this imperatively.

open System.Threading

let sumArray (arr : int[]) =
    let total = ref 0

    // Add the first half
    let thread1Finished = ref false
    ThreadPool.QueueUserWorkItem(
        fun _ -> for i = 0 to arr.Length / 2 - 1 do
                    total := arr.[i] + !total
                 thread1Finished := true
        ) |> ignore

    // Add the second half
    let thread2Finished = ref false
    ThreadPool.QueueUserWorkItem(
        fun _ -> for i = arr.Length / 2 to arr.Length - 1 do
                    total := arr.[i] + !total
                 thread2Finished := true
        ) |> ignore

    // Wait while the two threads finish their work
    while !thread1Finished = false ||
          !thread2Finished = false do

          Thread.Sleep(0)

    !total

The imperative code is very straight forward and offers a few benefits:

Simplicity. Not a whole lot is actually going on, just two calls to QueueUserWorkItem and a couple of boolean flags to keep track of when the threads complete.

However, there are some drawbacks too:

Redundancy. Both lambdas passed to QueueUserWorkItem are essentially the same, so the code is duplicated. If you want to spice things up, such as adding logging you will either forget to update the code in both locations or simply add it twice.
Hidden data. The key difference between the two threads is the range of elements in the array that they sum. The first array counts 0 to len / 2 – 1, the second thread to len / 2 to len. However, this crucial fact is buried in the code in two separate places.

The Functional (?) Way

Now let’s examine how to do this in a more functional style.

open System.Threading

let sumArray (arr : int[]) =
    // Define a location in shared memory for counting
    let total = ref 0

    // Define two flags in shared memory
    let thread1Finished, thread2Finished = ref false, ref false
    
    // Generate a lambda to sum a section of the array. 
    let sumElements (startIndex,endIndex) flag = 
          fun (_:obj) -> 
              for i = startIndex to endIndex do
                total := arr.[i] + !total
              flag := true  
    
    // Divy up the array
    let firstHalf  = 0,(arr.Length / 2 - 1)  
    let secondHalf = (snd firstHalf)+1,(arr.Length - 1)
    
    // Generate Delegates to sum portions of the array
    let thread1Delegate = sumElements  firstHalf  thread1Finished
    let thread2Delegate = sumElements  secondHalf thread2Finished
    
    [ thread1Delegate; thread2Delegate ]       // Queue up the delegates     
    |> List.map ThreadPool.QueueUserWorkItem   // Queue the use work items
    |> ignore                                  // Ignore the results 
        
    // Wait while the two threads finish their work
    while !thread1Finished = false ||
          !thread2Finished = false do

          Thread.Sleep(0)

    !total

Let me start with the drawbacks of this functional style first:

Too many values. There are seven let bindings in the function – presumably they are all important.
Concept count. This more functional way of doing thing certainly requires you to understand a bit about F# coding. (Mapping the thread code to a curried QueueUserWorkItem is pretty hot though.)

While arguably obfuscated, the functional style offers some clear benefits:

Important data is called out. Rather than hard coding the ‘0 to len / 2’ and ‘len / 2 to len’ values, the bounds for which to sum array elements is called out explicitly and on consecutive lines. This makes declaring an off-by-one error much easier to spot and fix.
Code reuse. Rather than hard coding the two thread pool functions, a sumElements function is introduced which takes explicit bounds to sum.

Personally I’m partial to the simplicity of the first example, but the value in calling out the range values in the second example shouldn’t be discounted. One of the best things I like about F# is that being a multi-paradigm language there is usually more than one approach to solve a problem, meaning you have options.

Thanks goes to Stuart for letting me post his code. I’m curious to hear what you think with regard to the two styles, please leave a comment and let me know what you think.

F# and the PFX Round 1

ChrSmith — Wed, 08 Apr 2009 20:21:00 GMT

I’m currently working on a chapter for Programming F# titled Asynchronous and Parallel Programming which should turn out pretty well. Anyways, I have an example that was too awesome not to blog.

In this post I’ll show how to use the Parallel Extensions to the .NET Framework for finding the shortest path between two nodes on a graph.

Problem Description

Let’s say you are planning a road trip this summer, you will start in city X and travel to city Y. Since your car cannot fly, you cannot head straight to city Y. Instead, you need to find the shortest path from X to Y. (With bonus points for site seeing, like the World’s Largest Rocking Chair in Iowa)

CS Gangstas have studied this problem and gave it the banal name ‘Shortest path problem’. If you do your research you can find plenty of clever and efficient algorithms; in this blog post I’ll just be solving this problem using a simple approach.

The Algorithm

The simplest way to solve this problem is create a dictionary of ‘shortest known path to city X’. Then, keep track of the cities you would like to visit and the distance traveled so far on that route.

If you are at a city and the distance you have traveled so far exceeds the shortest known path, then return because you already know a shorter route to that city.

Otherwise, update your ‘shortest known path’ data structure, and visit all of the city’s neighbors and repeat the process. Once you have exhaustively tried all paths the resulting ‘shortest known path’ data structure will contain the shortest path from your starting city to your final destination.

Lame Solution in C#

Let’s try to quickly write this up in C#.

    enum City
    {
        LosAngeles,
        Seattle, 
        // [List cities here]
        Boston,
        NewYork
    }

    /// <summary>
    /// Initialize the routes between cities and the distances. 
    /// Example: int distTweenBostonAndChicago = x[Boston][Chicago];
    /// </summary>
    static void InitializeDistances(Dictionary<City, Dictionary<City, int>> dist)
    {
        // [Load your data here]
        return new Dictionary<City, Dictionary<City, int>>();
    }

    /// <summary>
    /// Object to represent a route to a given city.
    /// </summary>
    class Route
    {
        public Route()
        {
            DistanceTraveled = 0;
            Route = new List<City>();
        }
        /// <summary>
        /// Add a new leg to an existing route.
        /// </summary>
        public Route(Route r, City nextCity, int distance)
        {
            DistanceTraveled = r.DistanceTraveled + distance;
            Route = new List<City>(r.Route);
            Route.Add(nextCity);
        }
        public int DistanceTraveled { get; set; }
        public List<City> Route { get; set; }
    }

    /// <summary>
    /// This makes up for C# not having Tuples...
    /// </summary>
    class CityToVisit
    {
        public CityToVisit(City c, Route r)
        {
            this.City = c;
            this.Route = r;
        }
        public City City { get; set; }
        public Route Route { get; set; }
    }

    static void Main(string[] args)
    {
        var distTweenCities = new Dictionary<City, Dictionary<City, int>>();
        InitializeDistances(distTweenCities);

        var StartingCity = City.LosAngeles;
        var FinalDestination = City.NewYork;

        // Keep track of the shorest paths to get from the starting city to
        // any other reachable city.
        var shortestPaths = new Dictionary<City, Route>();

        // Initialize our 'cities to visit' list, begining at our start city having
        // traveled zero miles.
        var citiesToVisit = new Stack<CityToVisit>();
        citiesToVisit.Push(new CityToVisit(City.LosAngeles, new Route());


        while (citiesToVisit.Count > 0)
        {
            var curLoc = citiesToVisit.Pop();

            // Have we visited this city before? If not, then add it...
            if (!shortestPaths.ContainsKey(curLoc.City))
                shortestPaths.Add(curLoc.City, nextCity.Route);

            // Is the route we used to get here shorter than the best known?
            if (shortestPaths[curLoc.City] < curLoc.Route.DistanceTraveled)
            {
                // Update our shortest paths...
                shortestPaths[curLoc.City] = nextCity.Route;

                // ... and visit all of its neighbors using this shortest path
                foreach (var neighboringCity in distTweenCities[curLoc.City].Keys)
                {
                    var updatedRoute = new Route(curLoc.Route, 
                                                 neighboringCity, 
                                                 distTweenCities[curLoc.City][neighboringCity];
                    var cityToVisit = new CityToVisit(neighboringCity, updatedRoute); 
                    
                    citiesToVisit.Push(cityToVisit);
                }
            }
        }

        Console.WriteLine("Shorest path from {0} to {1} is {2} miles.",
                          StartingCity, FinalDestination, 
                          shortestPaths[StartingCity][FinalDestination]);
    }
}

Awesome Solution in F#

So while the above code solves the problem, it suffers two major setbacks. First, the algorithm behaves on order O(N^2), which means it is slow. This wouldn’t be as much of a problem if it weren’t for problem two: the implementation is single threaded.

Being either slow or being single threaded is OK, but both at the same time is bad news.

Fortunately in CLR 4.0 (and available on 3.5 in CTP form) the Parallel Extensions to the .NET Framework (PFX) make parallelizing code pretty simple.

It is pretty clear how you to execute our algorithm in parallel, simple parallelize the process of visiting each city. The problem however comes when you are trying to read or write from the shorestPaths dictionary. Having multiple threads read and write from the same data structure at the same time is a recipe for disaster.

However, the PFX contain some built-in collection types that are designed exactly for this sort of application. The PFX ConcurrentDictionary type acts and behaves just like a normal dictionary, except that you can safely use it in a concurrent environment. (I know that sounds really vague, I’ll write more about the benefits of the ConcurrentDictionary type in a later post.)

Pedant’s Note: The solution locks on STDOUT so output messages don’t spew nonsense to the output; however this effectively makes the program run synchronously.

open System
open System.Threading.Tasks
open System.Collections.Generic
open System.Collections.Concurrent
    
type City = 
    | Boise     | LosAngeles    | NewYork   | Seattle
    | StLouis   | Phoenix       | Boston    | Chicago   
    | Denver
    
// Known disances between US cities in miles. If there is a path from A to B,
// there is also a path from B to A. If no path is listed, then you cannot travel
// between the two cities.
let distTweenCities = 
    let distances = new Dictionary<City, Dictionary<City, int>>()
    
    [
        (Boise,   Seattle, 496);      (Boise,   Denver,  830);    
        (Boise,   Chicago, 1702);     (Seattle, LosAngeles, 1141); 
        (Seattle, Denver,  1321);     (LosAngeles, Denver,  1022);  
        (LosAngeles, Phoenix, 371);   (Phoenix, Denver,  809);      
        (Phoenix, StLouis, 1504);     (Denver,  StLouis, 8588);     
        (Denver,  Chicago, 1009);     (Chicago, NewYork, 811);     
        (Chicago, Boston,  986);      (StLouis, Chicago, 300);
        (Boston, StLouis,  986);      (NewYork, Boston,  211)
    ]
    // Convert the list of links between cities into a dictionary
    |> List.iter (fun (cityA, cityB, dist) -> 
        
        if not <| distances.ContainsKey(cityA) then
            distances.Add(cityA, new Dictionary<City, int>())
        if not <| distances.ContainsKey(cityB) then
            distances.Add(cityB, new Dictionary<City, int>())
            
        distances.[cityA].Add(cityB, dist)
        distances.[cityB].Add(cityA, dist))
        
    // Return our dictionary of dictionaries of distances
    distances

let stdout = Console.Out

let shortestPathBetween startingCity finalDestination =
    
    // Keep track of the shorest path from 'startCity' to a given city, and
    // the path used to get to that city.
    let shortestPaths = new ConcurrentDictionary<City, int * City list>()
    
    let rec searchForShortestPath curCity distanceSoFar citiesVisitedSoFar = 

        // Visit all available cities from the current city
        let visitAvailableDestinations() =
            
            let availableDestinations = distTweenCities.[curCity]
            
            // Loop through destinations and spawn new tasks
            for dest in availableDestinations.Keys do
                Task.Factory.StartNew(
                    new Action(fun () -> 
                        searchForShortestPath 
                            dest 
                            (distTweenCities.[curCity].[dest] + distanceSoFar) 
                            (citiesVisitedSoFar @ [dest])
                )) |> ignore

        // Have I already found a way to travel to this city?
        let visitedBefore = shortestPaths.ContainsKey(curCity)
        
        if not visitedBefore then
            // First time visiting this city, add to our 'visited cities'
            shortestPaths.TryAdd(curCity, (distanceSoFar, citiesVisitedSoFar))
            
            lock stdout 
                 (fun () -> printfn 
                                "Origional route to %A (%d) via: %A" 
                                curCity distanceSoFar citiesVisitedSoFar)

            
            visitAvailableDestinations()
        else // We have visited this city before, let's see if this route is faster
            let shortestKnownPath, cities = shortestPaths.[curCity]
            
            if distanceSoFar < shortestKnownPath then
                // Update shortest path, revisit neighboring cities
                shortestPaths.[curCity] <- (distanceSoFar, citiesVisitedSoFar)
                
                lock stdout 
                     (fun () -> printfn 
                                    "Found shorter route to %A (%d) via:  %A" 
                                    curCity distanceSoFar citiesVisitedSoFar)
                
                visitAvailableDestinations()
            else // Ignore, we have already found a faster way to get here
                ()

    // Create the master task to find the shortest path between the two cities
    let t = 
        Task.Factory.StartNew(
            new Action(fun () -> searchForShortestPath startingCity 0 [])
        )
    t.Wait()
    
    let dist, path = shortestPaths.[finalDestination]
    
    printfn 
        "The shortest distance from %A to %A is %d miles, with route:\n%A" 
        startingCity finalDestination 
        dist path

Book Update – NEW Coauthor!

ChrSmith — Thu, 02 Apr 2009 02:28:03 GMT

You might be concerned about my lack of blogging, perhaps that I was lost in the woods and perhaps eaten by a bear. Well, unfortunately, all of my time has been devoted to three tasks:

Writing Programming F#
Passing Programming Languages
Shipping F# in Dev10

I would like to give you an update on item #1 my book, as there have been some rather interesting developments. There are plenty of great books on F# being written, and book competition is a great thing. However, one F#-related book in particular has caught my attention:

Real World Functional Programming

By Tomas Petricek

Tomas currently works as an intern at Microsoft Research in Cambridge on F# and is crazy-smart. (Seriously, he’s a level-9 ninja master at F#. Have you checked out F# Web Tools?)

But I’m not too worried about my book competing with his for two reasons:

His book is about Functional Programming and mine is specifically about F#. So while there is some overlap, his book is about applications of functional programming while mine is about concepts and syntax.
His has some creepy looking dude* and mine will (hopefully) have a fire-breathing Hydra on the cover.

For a time I wasn’t worried about Tomas’ book. Until now…

It was recently announced that Manning was adding a co-author to Tomas’ book; none other than Jon Skeet himself. Make no mistake, Jon is not some mortal programmer. Rather, his brain contains 63.8% of all knowledge on StackOverflow.

So Real World Functional Programming not only has one great authoring. But now it has two. So really, any other book on F# or functional programming is simply hosed. No point in publishing it – Tomas Petricek and Jon Skeet are teaming up to write a book on functional programming. Save your time and go home.

I don’t mind the challenge of competing with this book, but it certainly raises the stakes.

I’ve been making a few phone calls to Tim O’Reilly and Laurel Ruma about what we can do about this. It took a while to get layers to figure things out, but now I have a new coauthor of my own for Programming F#:

That’s right. CHUCK NORRIS has agreed to not only write the forward, but help coauthor the book to!

Chuck and I are still working out who will own which chapters, but I’ve been able to get an advanced copy of his forward to the book.

Dear Reader,

The fact you are sitting here reading this forward means that you weren’t already killed by the Russians. You have me and me alone to thank for that.

In this book Chris Smith and I will teach you how to roundhouse kick concurrency issues, use an M16 to mow down mutation-related bugs, and how to divide by zero. (I’ve been doing it for years, and trust me – it’s worth it.)

…

While I am very excited to have Chuck onboard, reading the page on Jon Skeet Facts has me worried.

Jon Skeet is immutable. If something's going to change, it's going to have to be the rest of the universe.
The Dining Philosophers wait while Jon Skeet eats.
Jon Skeet can recite π. Backwards.
When Jon gives a method an argument, the method loses
When Jon pushes a value onto a stack, it stays pushed
When invoking one of Jon's callbacks, the runtime adds "please"

It may be a tough call as for which book turns out better, but I can’t wait to see the results! In related news, Chapters 1-4 of Programming F# are available on Rough Cuts with another couple on the way. So stay tuned!

*Rumor has it that, the “creepy looking dude” on the cover of Real World Functional Programming is Danish philosopher Søren Kierkegaard [pic]… but does he breath fire?

Petition for Programming F#’s Book Cover!

ChrSmith — Mon, 02 Feb 2009 18:41:46 GMT

You might have noticed my blogging has slowed down to a lull; never fear, this is just because I have been working it is been because I have been hard at work writing I am working full steam on finishing up Programming F#. But I cannot finish this book without your help, read on.

The good news

The good news is that the first three chapters of Programming F# should be available online at O’Reilly’s Rough Cuts site very soon. (Maybe this week…) Signing up for Safari will give you access to pre-release chapters of the book as well as give me feedback on how to make the book better. (Something I would greatly appreciate.)

The bad news

But to be honest, as much as I’d like your feedback on early chapters of the book what I really need your help on is convincing ‘the man’ that Programming F# deserves a better cover than merely a fish, a rat, or a rabbit. Seriously, a rabbit?!? The linked books are all great, but having some cute and cuddly creature on the front doesn’t really inspire me to take the technology seriously.

That is why when I first announced the book I mocked up a cover with a Squig.

But ‘the man’ shot me down. You see, if O’Reilly is going to start having creatures more awesome than a frog on the cover they need to enforce a few other rules:

The creature should be easily identifiable. The awesomeness of the Squig is self-evident, but few can name what it is exactly. The cover on the book should be something people could recognize.
The creature can’t be copyright. Most of the Squig’s awesomeness was due to the fact it was created by Games Workshop, currently licensed to Mythic Entertainment. Licensing stuff like this makes lawyers cry at night.

So I literally went back to the drawing board to think about what animal best represents F#. Something that conveys its multi-paradigm nature. Specifically, it supports imperative, object-oriented, and functional programming

Then it hit me. What creature has three heads and totally kicks ass?

Cerberus

Cerberus (Greek: Κέρβερος, Kérberos) is the name given to the entity which, in Greek and Roman mythology, is a multi-headed dog which guards the gates of Hades, to prevent those who have crossed the river Styx from ever escaping.

Now we are onto something, but to be honest having the gatekeeper for hell on the cover of my book doesn’t sit too well with me. While certainly keeping the denizens of Hades in check is a noble task, it carries along a lot of spirtual baggage. Is Cerberus evil? Or just doing his job? Also, it isn’t like there are many cerberi – rather there is just the one (that I know of).

So, unfortunately I need to try again. But the more I think about it I like my second choice much better. Instead of Cerberus I went with a G-D-M-F-fire-breathing-HYDRA!

Hydra

You don’t F with those, you know why? Because it’s got multiple heads, and since the specifics on hydras are pretty unclear I’m going to go ahead and say that the hydra on the cover of my book is both undead and breathes fire.

Yes people, a lich hydra that breaths hellfire from its multi-paradigm heads of destruction.

So, I present to you, the cover of my book hopefully awesome enough to make the powers that be rethink their ‘cute and cuddly’ colophons.

Use Multi-Paradigm Programming to Devour Your Foes!

“The only thing better than one fire-breathing paradigm is three!”

Yeah, NOW we are talking.

Call to Action!

However, to be clear this isn’t my official book cover, but it would certainly be awesome if it was. So I need your help to convince the good folks at O’Reilly the same.

So please politely send a tell to @LaurelAtOReilly on Twitter and let her know that a Hydra would make a much better cover than whatever the hell is on the cover of Unix in a Nutshell.

I also have a Cafe Press site up for T-Shirts. I haven’t received mine in the mail yet so I can’t comment on how well they will turn out.

Thanks for your help and support. And remember: the ability to breath fire is always better than being furry. Always.

Deep Fried F#

ChrSmith — Thu, 15 Jan 2009 23:17:35 GMT

Episode 24: Chatting about F# with Chris Smith and Dustin Campbell

“Get your code on!” Being the international media sensation that I am, back at PDC Dustin Campbell and I recorded a podcast for Deep Fried Bytes. The podcast turned out awesome. Well, after I figured out how to talk into the mic.

Some takeaways:

Both C# F# rob Peter to pay Paul.
Where? Everywhere! It’s general purpose baby!
I like long walks on the beach, fireside chats, and functional programming.

A special thanks goes out to Jeff the waterboy.

New Years resolutions v2.0.0.9

ChrSmith — Thu, 15 Jan 2009 21:56:03 GMT

So I was tagged by my new homie Sarah Dutkiewicz AKA Coding Geekette about blogging my goals for 2009. I was on the fence at first about whether or not to share such private information with the world. But after seeing Jay Wren admit to being a “Law and Order addict”, I couldn’t embarrass myself too much.

First let me provide a disclaimer. These goals certainly make me sound like some sort of ultra-driven alpha-male type person. But rest assured that I’m just as lazy and apathetic about life as you are, it just happens that 2009 will be a busy year.

Graduate with my Masters degree

I have been taking classes at the University of Washington Professional Masters Program for about two years now and hopefully I will graduate this spring. Getting my Computer Science Masters degree is very important for backing up my reputation as a true CS Gangsta.

Of course it will be hard to divide my time between ‘actual class’ and just watching the lectures for Structure and Interpertation of Computer Programs by Hal Abelson and Gerald Sussman. Who doesn’t want to learn Lisp?

Finish writing Programming F#

Programming F# is coming along, but not without its tribulations. I’m trying to convince John Osborn that my book should, in fact, have a Squigg on the cover.

I’m going to try to get the first few chapters on O’Reilly’s Rough Cuts site by the end of the month. So stay tuned!

~~Ship F# in Visual Studio 2010~~

Kick ass and take names at work

Working as a tester at Microsoft has a few perks. Not only do I get free soda but I actually get paid to complain and criticize our software. (It is so much fun people do that already for free!) Anyways, it is my personal mission to see F# ship in Visual Studio 2010 and be the most awesome feature in the box. So in 2009 my goal is to do just that.

Drop the dead weight

Who doesn’t have ‘lose some weight’ as part of their New Year’s resolutions? To mix things up, rather than simply going to the gym, I’m going to see how much weight I lose by quitting Taco Bell cold turkey. New rule, no more delicious nacho cheese chalupas with chicken for a whole year. Can I do it? Only time will tell…

And my last, and perhaps most important, goal is:

Enjoy 2009 more than 2008

Truth be told 2008 had a lot of drama-lama-ding-dong for me and I’m looking to being drama-free for 2009. Go skiing more, spend more time with friends and family. I want to cultivate and encourage that which is awesome. If you have any suggestions let me know.

In the spirit of transforming blogging into modern chain letters, I’ll tag:

· ’Dr.’ Brian McNamara

· Kirill ‘C# genius’ Osenkov

· Dustin ‘kind of a big deal’ Campbell*

*Despite the nickname, Dustin is not actually a big deal. Maybe if he blogged more often…

Speech Recognition is gun and easy!

ChrSmith — Wed, 31 Dec 2008 07:03:55 GMT

Evidently Microsoft ninjaed a new assembly into the .NET framework with the 3.0 release called System.Speech.dll. If adding speech recognition or speech synthesis to your applications sounds like fun, read on.

Step 1: Train your computer

The first step for meaningful speech recognition is to tell your computer who is in charge. Open up the Control Panel, navigate to Ease of Access, Speech Recognition options, then select Training. The process of training will take about 10 minutes and is pretty tedious, but the results are well worth it.

Step 2: Write some F# code

This is the easy part.

#light

open System
open System.Speech.Recognition

let sp = new SpeechRecognitionEngine()
let defaultDictationGrammar = new DictationGrammar()

defaultDictationGrammar.Name <- "Default Dictation"
defaultDictationGrammar.Enabled <- true

sp.LoadGrammar(defaultDictationGrammar)
sp.SetInputToDefaultAudioDevice()

sp.RecognizeAsync(RecognizeMode.Multiple)

sp.SpeechRecognized.Add(fun args -> printfn "Recognized [%f] '%s'" args.Result.Confidence args.Result.Text)

printfn ("(Just start talking. Press any key to quit.)")
Console.ReadKey(true) |> ignore

Step 3: Profit

Early results look promising, although it doesn't handle early 90's rap very well...

F# No Longer Vaporware

ChrSmith — Wed, 10 Dec 2008 23:05:00 GMT

REDMOND, WA - Sadly, after nearly four years of stringing developers along with Microsoft's longest touted non-product, F# was accidentally checked into the Visual Studio 2010 source tree Microsoft sources report. This mistake killed what would have been one of Microsoft's most popular vaporware project by giving it an actual release date.

The checkin was made by an intern, who was simply experimenting with his new Visual Studio Team Foundation Server enlistment. As a result of the checkin the F# compiler and project system will eventually ship with the next release of Visual Studio, Microsoft's premier development tool.

When asked about the event, senior researcher and language creator Don Syme lamented:

“It’s crazy. I mean, what do we do now - we can’t get it out. I was just working on F# as a way of getting out of all of those boring academic conferences. A way of looking busy for my boss. Then I come back from lunch Monday and the sucker was checked-in. This is a total ******* catastrophe.

I really don’t understand this place, you think we would have learned our lesson. You know those .NET Generics – same thing there too. Once Microsoft, always Microsoft – this place never changes.”

In fact, the entire F# team was shocked to hear the news. Developer Brian McNamara was quoted, “I didn’t sign on to work 80-hours a week only to have my code released to the world. This sucks, you mean to tell me that now people are going to actually use F#?”

Luke Hoban, program manager for the project was also troubled:

“Giving demos with this functional programming stuff is one thing; but an actual F# product is definitely another. If we ship it people will actually expect F# to be usable. You know, solve real world problems and stuff. This changes our whole strategy. When we were just demoing all we had to worry about was style. Substance on the other hand requires hard work.”

According to Hoban, most vaporware projects at Microsoft get terminated long before they build up much hype. F# was one of the company's most successful vaporware projects until last Monday. "We were able to keep up the illusion of shipping for so long by putting out CTP and beta releases. We probably could have probably shipped those things for another few years before people caught on that we never actually intended to ship F# in an officially supported release."

Below is an image the F# team was hoping to only mock up using PowerPoint and MSPaint. But after the source code accident, the screen shot is from an actual build of Visual Studio 2010.

Currently the F# team in Redmond, Washington is scrambling to recover. Developer Jomo Fisher set up an emergency meeting with Senior Vice President S. Somasegar to discuss the potential ramifications of introducing .NET developers to functional programming.

The impact of this news is slowly being felt across the broader .NET developer community as well. Matthew Podwysoki, an avid F# blogger, was frustrated to hear the news:

“The bleeding edge of software has always been vaporware. Actually shipping F# in a box is so banal. How else am I supposed to impress people if not by saying that I know F#, a space-age programming language that you’ve never heard of.

If it becomes mainstream then I’ll probably have to learn something else. I mean, what’s next? People writing books for O'Reilly and putting flesh-eating demons on the cover? Come on.”

Not everybody reacted as emotionally to the news. Program manager Dustin Campbell tried to give perspective:

“Sometimes even the most promising projects ship. It happens. It is just part of software development. Either through good management, realistic schedules, or solid programmers some projects actually complete on time.

You just need to hope your next project will turn out better. If I were those F# guys, I’d be twice as lackadaisical in the planning of version 2.0.”

It may take weeks or even months for the team to cope with the unexpected realization that F# will eventually become a reality in Visual Studio 2010. In the mean time, you can protect yourself from productivity improvements induced by the language by avoiding any future Beta or CTP releases of Visual Studio 2010.

When Visual Studio 2010 is released, your best and only defense is to be prepared. Microsoft has began recommending that interested developers watch Luca Bolognese’s presentation titled An Introduction to Microsoft F#.

Check back here for more information on this story as it develops.

F# Zen - Array slices

ChrSmith — Tue, 09 Dec 2008 19:37:29 GMT

Sorry for not being as regular with blogging, I've been sick and working hard on something pretty exciting. Don will post an announcement sooner or later.

Anyways, did you know that in F# you can easily take out a chunk of an array using an Array Slice? This is a simple syntax for selecting a subset of an array, which creates a new array copying the values. This slice syntax also works for 2D arrays as well in much the same way. (E.g., daysOfYear.[*, ..5])

Here are some simple examples:

open System
let daysOfWeek = Enum.GetNames( typeof<DayOfWeek> );;

// Standard array slice, elements 2 through 4
daysOfWeek.[2..4];;

// Just specify lower bound, elements 4 to the end
daysOfWeek.[4..];;

// Just specify an upper bound, elements 0 to 2
daysOfWeek.[..2];;

// Specify no bounds, get all elements (clones the array)
daysOfWeek.[*];;

F# Zen - ROT13

ChrSmith — Fri, 07 Nov 2008 22:33:24 GMT

Below is a primitive implementation of ROT13 / Ceasar Cipher in F#. In short it is a simple encryption algorithm that works by 'shifting' each letter 13 places. So an 'a' becomes an 'n', a 'b' becomes an 'o', and so on. To decrypt the text you simply move 13 places in reverse.

We can do this in F# easily using function composition. Given a string, which is also a sequence of characters, we pass it to Array.of_seq so we have an array of characters. This will enable us to replace each character with its encrypted version. Next we map each character to our encryption function, which I'll go over next. Finally, we take our array of encrypted characters and return a new string.

To actually do the encryption, we will compose three functions together. int, will convert the character to its integer representation. "(+) 13" is a curried version of the (+) function, so it adds 13 to its argument. And then we compose that with the char function, which will convert the integer result to a character.

#light

(**
 * ROT13 in F#
 * 
 * 1. Convert the sequence of chars (string) to an array of chars
 * 2. For each character do the following:
 *    - Convert the character to an integer
 *    - Add 13 to the integer value of the character (by currying (+))
 *    - Convert the integer to a character
 * 3. Create a new string based off the encrypted characters
 *)
 
let EncryptText (text : string) = 
    text
    |> Array.of_seq
    |> Array.map (int >> ((+) 13) >> char)
    |> (fun chars -> new string(chars))

let DecryptText (text : string) = 
    text
    |> Array.of_seq
    |> Array.map (int >> ((+) -13) >> char)
    |> (fun chars -> new string(chars))

let Test message =
    let encrypted = EncryptText message
    let decrypted = DecryptText encrypted

    printfn "Original Message  = %s" message
    printfn "Encrypted Message = %s" encrypted
    printfn "Decrypted Message = %s" decrypted
    
Test "The quick fox jumped over the lazy dog"

F# Elevator Pitch

ChrSmith — Sat, 01 Nov 2008 16:24:00 GMT

At the PDC I spent about eight hours a day for a full week answering the same question again and again: “What is F# and why should I use it.” While I would love to give a long and nuanced answer to this, in order to achieve a high throughput you need to resort to using the Elevator Pitch style.

The Pitch

So your boss comes to you and says your company is about to go bankrupt unless you write some application that will save the day. Having been told this time and time again you fire up Visual Studio and get to work.
The data access layer is trivial; you have code generators and UI tools to help out. The presentation layer is easy too – you have WYSIWYG designers. All you need to do them is wire these things together, which is straightforward in an object-oriented language. So from the get-go building the framework for your application is easy.

Your boss sees that your project is ‘mostly done’ and breathes a sigh of relief. He then starts stressing out about other things. But in reality, now is the time that the hard programming work begins. Conceptually you’re just putting the meat in your application – some business logic, implementing an algorithm, transforming some data. General computation. But this is really painful in C#.

Think about design patterns. They are actually really simple concepts, but require a complex web of types and interfaces to implement. This is because at heart everything in an OO language must be a class, so if you want to represent something simpler than that – a function, an algorithm, a piece of data – you have to build some OO hierarchy on top of it.

You could waste your time writing a lot of boiler plate code that has nothing to do with solving your problem, but fortunately there is a better way.

Instead of burning a week or two writing your functions and algorithms in terms of classes, you write your code in F#. F# is a new .NET programming language that approaches programming from an entirely different perspective. Abstracting algorithms, numeric computation, data analysis and exploration – all of these things are just easier in F#. Because that’s what the language is built to do.

So you write some part of your application in F# and shave weeks off your development time. And, because of the interoperability of the CLR, you can use it directly with your C# code and your boss/team is none the wiser. Your company is saved and you don’t have to work this weekend.

F# will make you extremely productive at algorithmic-level development (AKA programming in the small). So you can use F# where it makes sense and C# for everything else. F# is powerful new language for your tool belt.