Better Living through Software

So I decided to use F# (basically OCaml) instead of scheme for the pure functional version of my puzzle solver.  I wish I had started with F# in the first place.  What a gorgeous language!  Implementing in F# showed me what I was doing wrong in the C# version, and now I can implement the C# version without the yield keyword.

Here is the complete rotate routine in F#.

let cards = [ "K"; "Q"; "J"]
let sides = [0; 1]

let rec rotate outer inner result =
  match outer with
  | o::tail ->
      if tail = [] then
        [for i in inner ->
          (o, i)::result
        ]
      else
          [for i in inner
             for l in rotate tail inner ((o,i)::result) -> l]
  | [] -> []

do print_any (rotate cards sides [])

I was really surprised with how productive F# is.  I thought I would get annoyed at its strong typing versus scheme, but it made dealing with nested lists a lot easier.  And with the VS2008 integration, the editor shows you inferred types almost real-time, simply by hovering.  Once I figured that out, I no longer needed fsi interpreter window open.

Amazingly, F# has yield functionality as well, but I stayed far away from it.  Even funnier, F# has a “mutable” keyword, since nothing is mutable by default.  There is nothing better than programming when everything is immutable.

Now, the whole reason I wanted to compare C# 3.0 functional versus scheme was to get a sense for how well the compiler can optimize the recursions.  I think F# works as well as scheme for this purpose.  Check out the following code sample:

let rec range a b =
  if a > b then []
  else a :: range (a + 1) b

let rec sum list =
    match list with
    | h::tail -> (sum tail) + h
    | [] -> 0

do print_any (sum (range 0 1000))

Even if you’re not familiar with Caml/F#, you can tell what this does.  The range function returns a list of numbers inclusive from a to b, and the sum function adds a list of numbers together.  Note that both functions are implemented recursively!  So when we add up the numbers 1 to 1000, both functions trigger recursion 1000 levels deep. 

Code like this would crash in C++ or C# because you can’t recurse that deep — especially if you’re passing everything immutably by value.  But the sum returns instantly in F#, because the compiler doesn’t actually push the call stack 1000 times — it doesn’t implement things the way an imperative language would.

I was speculating that C# 3.0 might put C# recursion performance closer to par with scheme and F#, by heavy use of iterators and compiler advancements.  So I found a great description of how iterators work over on Wes’s blog.  He includes some perf charts and hints at a potential new “yield foreach” syntax that would have helped me out.  It looks like iterators perform well.

C# version 3.0 is a huge advance, but still not as nice as F# for my preferred style.  While the iterators perform and chain amazingly well, I can still get into trouble by recursing too deep.  And C# (like Python) discourages you from passing around lots of big lists by value.  List processing in C# has gotten a lot better, but still not as nice as F#.

This entry was posted on Sunday, December 30th, 2007 at 10:56 am and is filed under Life at Microsoft. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.