Friday, 25 May 2012

Graph coloring in F#

Eric Lippert of the Visual C# compiler team at Microsoft wrote a fascinating series of five blog posts about graph coloring. The articles develop a C# program with 20 lines of code devoted to defining the problem (coloring the planar graph of borders between 13 South American countries) followed by another 200 lines of C# code to solve the graph coloring problem. In the fourth article, this culminates in the solution 0, 1, 2, 1, 2, 1, 0, 2, 0, 1, 2, 1, 3 that uses just three colors to solve the problem.
Let's solve the same problem using the F# programming language instead. We begin by defining the problem using a union type to represent the countries and nested lists to represent the adjacencies:
type Country =
  | Brazil | FrenchGuiana | Suriname | Guyana | Venezuala | Colombia
  | Ecuador | Peru | Chile | Bolivia | Paraguay | Uruguay | Argentina
 
let countries =
  [|Brazil; FrenchGuiana; Suriname; Guyana; Venezuala; Colombia;
    Ecuador; Peru; Chile; Bolivia; Paraguay; Uruguay; Argentina|]
 
let edges =
  [
    Brazil, [ FrenchGuiana; Suriname; Guyana; Venezuala; Colombia;
              Peru; Bolivia; Paraguay; Uruguay; Argentina ]
    FrenchGuiana, [ Brazil; Suriname ]
    Suriname, [ Brazil; FrenchGuiana; Guyana ]
    Guyana, [ Brazil; Suriname; Venezuala ]
    Venezuala, [ Brazil; Guyana; Colombia ]
    Colombia, [ Brazil; Venezuala; Peru; Ecuador ]
    Ecuador, [ Colombia; Peru ]
    Peru, [ Brazil; Colombia; Ecuador; Bolivia; Chile ]
    Chile, [ Peru; Bolivia; Argentina ]
    Bolivia, [ Chile; Peru; Brazil; Paraguay; Argentina ]
    Paraguay, [ Bolivia; Brazil; Argentina ]
    Argentina, [ Chile; Bolivia; Paraguay; Brazil; Uruguay ]
    Uruguay, [ Brazil; Argentina ] 
  ]
These are the vertices and edges of our graph.
The countries of South America are, of course, a planar graph so we know they can be assigned colors with no two adjacent countries having the same color using a total of no more than four different colors. Let us define the set of all four possible colors as follows:

let allColors = set[0..3]

The graph coloring problem may then be solved by adding our vertices and edges to an empty graph, generating a sequence of possible colorings at each step:

let solve (V, E)  =
  ((Set.empty, seq[Map.empty]), V)
  ||> Seq.fold (fun (vertices, solutions) vertex ->
    let neighbors =
      [|for src, dsts in E do
          if src = vertex then yield! Set.intersect vertices (set dsts) else
            for dst in dsts do
              if dst = vertex && Set.contains src vertices then
               yield src|]
    Set.add vertex vertices,
    seq { for color in solutions do
            for newColor in allColors do
              if Seq.forall (fun u -> color.[u] <> newColor) neighbors then
                yield Map.add vertex newColor color })

Eric's result may then be obtained by taking the first of the valid colorings and using it to enumerate the colors of each country in turn:

let answer =
  let _, colors = solve (countries, edges)
  let color = Seq.head colors
  [ for country in countries -> color.[country] ]

Remarkably, we have solved the same problem in just 19 lines of F# code! One can only imagine how much simpler Microsoft's Roslyn compiler could have been had it been written in F#...

Improving matrix-matrix multiply and prime number programs in F#

Several people have cited the comparison of Erlang, F#, Go and Java from here. Let us present some improved F# solutions.
The parallel matrix-matrix multiply makes heavy use of async for parallel programming, where it is an anti-pattern. So it may be productively rewritten using Tasks as follows:

let randomMatrix =
  let rnd = new System.Random()
  Array2D.init 500 500 (fun _ _ -> rnd.NextDouble())
 
let matrixMultiply (a:float[,]) (b:float[,]) =
  let rowsA, colsA = Array2D.length1 a, Array2D.length2 a
  let rowsB, colsB = Array2D.length1 b, Array2D.length2 b
  let result = Array2D.create rowsA colsB 0.0
  System.Threading.Tasks.Parallel.For(0, rowsA, fun i ->
    for j in 0 .. colsB - 1 do
      let mutable x = 0.0
      for k in 0 .. colsA - 1 do
        x <- x + a.[i,k] * b.[k,j]
      result.[i,j] <- x
  ) |> ignore
  result
matrixMultiply randomMatrix randomMatrix

This is 60x faster than the original async-based solution. However, this is a poor choice of algorithm because it lacks locality. Better algorithms are tiled or cache oblivious.
Their prime number generator makes heavy use of enumerable sequences which can be productively rewritten using recursion and arrays instead, as follows:

(* A very naive prime number detector *)
let isPrime (n:int) =
  let rec loop i = i*i > n || (n % i <> 0 && loop (i+1))
  loop 2
 
(* Return primes between m and n using multiple threads *)
let primes m n =
  Array.Parallel.init (n-m+1) (fun i -> m+i, isPrime (m+i))
  |> Array.Parallel.choose (function n, true -> Some n | _ -> None)
 
(* Run a test *)
while true do
  let timer = System.Diagnostics.Stopwatch.StartNew()
  primes 1000000000 1000100000
  |> ignore
  printfn "%fs" timer.Elapsed.TotalSeconds

This is 13x faster than their original seq-based solution.

Monday, 14 May 2012

Parallel programming in functional languages


Functional programming has immutable data structures and no side effect which are inherently suitable for parallel programming.
That is a common misconception. Parallelism is solely about performance and purity usually degrades performance. So purely functional programming is not a good starting point if your objective is performance. In general, purity means more allocation and worse locality. In particular, purely functional data structures replace arrays with trees and that incurs many more allocations and places far more burden on the garbage collector.
For example, measure the performance of the elegant purely functional "quicksort" in Haskell. Last time I checked, it was thousands of times slower than Sedgewick's conventional imperative solution on my machine.
Also, nobody has ever managed to implement an efficient dictionary data structure (pure or impure) or an efficient purely-functional sort in Haskell and nobody has figured out how to write an asymptotically efficient persistent disjoint set data structure and there is no known way to implement other basic data structures like purely functional weak dictionaries!
Moreover, the garbage collector in the defacto-standard Haskell implementation (GHC) is heavily optimized for pure code at the expense of mutation. For example, GHC's hash table is still 26× slower than .NET's. Historically, the performance of mutation was considered so unimportant in Haskell that writing a single pointer to an array was an O(n) operation in GHC for five years.
I investigate how to exploit multicore computation in a functional language, and target production code for some numerical applications.
The best way I have found is to learn how to write decent parallel programs for multicores in the imperative style (study Cilk, in particular) and then factor the code using first-class functions and tail call elimination into the impure functional style.
This means cache oblivious data structures and algorithms. Nobody has ever done this in Haskell. Indeed, none of the research published on parallel Haskell to-date has even mentioned the essential concept of cache complexity. Furthermore, although it is widely known that non-strict (aka lazy) evaluation renders space consumption unpredictable, it is not yet widely appreciated that this same problem renders scalability wildly unpredictable on multicores.
F# has Microsoft behind its back, and its parallel constructs such as PLINQ, TPL, Async Workflow have been well-documented and shown some potentials.
They are well beyond showing potential. Thousands of commercial applications have been built upon those industrial-strength foundations.
However, research about parallelism in Haskell is very active at the moment, and it posseses many nice features which haven't supported by F# yet:
You are assuming they are "nice features"? Read Simon Marlow's latest paper about this:
"...a combination of practical experience and investigation has lead us to conclude that this approach is not without drawbacks. In a nutshell, the problem is this: achieving parallelism with par requires that the programmer understand operational properties of the language that are at best implementation-defined (and at worst undefined). This makes par difficult to use, and pitfalls abound — new users have a high failure rate..."
My question is which language should I choose for functional parallelism?
I'd advise against parallel purely functional code for production because it is a complete wild card. Assuming you're happy to sacrifice some purity in order to attain competitive performance, I use and recommend F#.

Applications of priority queues

Priority queues are an abstract collection that allow random insertion of new elements and removal of the smallest or largest element. Here are a couple of applications of priority queues:

Heaps are a family of concrete data structures that can be used to implement priority queues efficiently. For implementations of heaps in F# see the article Data structures: Heaps in the F#.NET Journal.

Wednesday, 9 May 2012

Solving Einstein's Riddle

The F#.NET Journal just published an article about interactive logic programming:
"Einstein is said to have posed a logic puzzle, sometimes called the "zebra puzzle", that only 2% of people would be able to solve. This article reviews the puzzle and walks through a simple solver written in F# that finds the correct answer in a fraction of a second..."
To read this article and more, subscribe to The F#.NET Journal today!

Monday, 7 May 2012

Visualizing the Stanford Bunny using WPF

The F#.NET Journal just published an article about 3D graphics:
"Stanford University maintain a database of 3D models, perhaps the most famous of which is the Stanford Bunny. This is a 3D scan of a statue of a rabbit. The tesselated version contains 65,000 triangles and is stored as plain text in a PLY file. This article describes a program that embeds the mesh data as an embedded resource in a .NET assembly, parses it at run-time and visualizes the results in 3D using Windows Presentation Foundation..."

To read this article and more, subscribe to The F#.NET Journal today!

Sunday, 6 May 2012

How do I sort lexicographically in F#?


F# does this for you automatically when you define a tuple, record or union type:
> type Point = { X: float; Y: float };;
type Point =
  {X: float;
   Y: float;}
You can immediately start comparing values. For example, defining a 3-element list of points and sorting it into lexicographic order using the built-in List.sort:
> [ { X = 2.0; Y = 3.0 }
    { X = 2.0; Y = 2.0 }
    { X = 1.0; Y = 3.0 } ]
  |> List.sort;;
val it : Point list = [{X = 1.0;
                        Y = 3.0;}; {X = 2.0;
                                    Y = 2.0;}; {X = 2.0;
                                                Y = 3.0;}]
Note that the results were sorted first by X and then by Y.
You can compare two values of any comparable type using the built-in compare function.
If you want to use a custom ordering then you have two options. If you want to do all of your operations using your custom total order then it belongs in the type definition as an implementation ofIComparable and friends. If you want to use a custom ordering for a few operations then you can use higher-order functions like List.sortBy and List.sortWith. For example, List.sortBy (fun p -> p.Y, p.X) will sort by Y and then X because F# generates the lexicographic comparison over 2-tuples for you (!).
This is one of the big advantages of F#.