The other day, I asked around here at Vertigo to see if anyone understood some new concepts that I had run across, those being monads and continuations. These are both concepts that you find in more functional languages such as Lisp, Scheme, Haskell, and so forth, but are also finding their way into more mainstream languages – notably in LINQ, due to its relationship to more functional ways of programming (such as its use of lambdas). We have a good environment here for asking questions like that, and the conversation soon evolved into other areas. One subject that came up was that of F#, which is a language that has come out of Microsoft Research. I had heard of the language before, but had not really explored it. I happened to have a little bit of bandwidth over the last few days, so, I thought I would do a little spelunking, and learn something new. Here's what I found J
So what's this F# thing, anyway?
What I found out is that F# is a programming language based on ML and OCaml. These are both languages with a high degree of functional programming aspects to them (which is not the opposite of dysfunctional programming), but which, unlike more 'pure' functional languages such as Scheme or Haskell, allows for more imperative styles of programming than those do – structures such as for and while loops exist, and look much as you would expect.
Unless you specify otherwise, everything in F# is immutable, much like the string construct in C#. This extends to areas that you might not expect. For instance, once you set an int to some specific value, that's it – you can't change it, unless you have marked it as mutable. The reason for this is because the language is primarily a functional one. Programs in functional languages contain functions which return values, which are then further used, etc – but each value or set of values is its own entity, and to change it while within a function is to produce a side effect, something undesirable in a functional language. In the strictest sense, functions return values but do not alter their parameters, or the outside world (which, incidentally, gives rise to the monad pattern mentioned earlier). F# follows these rules of functional programming, but also allows you to break those rules with the mutable keyword.
In F#, indentation is significant. For instance, take this bit of code out of my sample project :
if(i>0)then
newRect.up <- rectsArray.[i-1,j].rect
rectsArray.[i-1,j].down <- newRect.rect
In that sample, everything indented under the "if" is part of the if statement's block. (note: this is using the #light directive, which imposes these rules)
F# uses type inference for most things. For instance, given a statement such as
let gridSize = 45
the compiler determines by its use that gridSize has to be an integer. This is not a variant from the old days, but instead is the rough equivalent of the var keyword in C# - the language is typesafe, but most often types are inferred. You can, if need be, specify the type explicitly, such as :
let redBrush : SolidColorBrush = new SolidColorBrush(Colors.Red)
but F# seems to do a pretty good job of figuring things out.
F# also makes extensive use of lists, which are not the generic lists you would find in the .Net framework proper. Instead, they bear more of a resemblance to lists in LISP. A short discussion of what lists in F# are and what they can be used for can be found here.
A Sample Application
I kicked around several ideas for an application to build and learn in, but eventually settled on making a version of Conway's Game of Life. Because F# is functional and because of that potentially can execute each of the cells in parallel, it seemed like a good match. Unfortunately, because of the way I wrote the program, and because I needed to update a user interface (producing a side effect!), I am instead iterating over each one of the cells. Maybe in a future version, instead of using the List.iter function to do the heavy lifting, I can instead write it in a way where I can use List.map, which implements function mapping, and, if we also do things such as stick to non-mutable values, opens up a program to parallelism. The main gist was to get my head around the language, and I'm definitely still learning! In some respects I approached the true spirit of the language, but a fair bit of it is still written in an imperative style. Maybe phase two.
I also wanted to hone my WPF skills a little. I wanted to originally write this with a Silverlight front end, but, alas, F# support for Silverlight is not there yet. I also wanted to see if I could write it in such a way that everything is backended in F# with a WPF front end. This is doable, but most examples use F# code to generate WPF objects, which is not what I wanted. I wanted to be able to design in XAML and have the code in F#. In order to do this, I had to create a C# shim application, which basically starts up and then as soon as possible hands over control to the F# code.
Give my creature Life!
You've probably seen versions of the game of life before, but the main idea is, depending on how many of its neighbors are active, a cell is either turned on (that is, 'born', turned off ('dies'), or remains the same. If a cell has two active neighbors, it stays the same. With three active neighbors, it turns on. Otherwise, it turns off. Pretty simple rules, but the patterns which emerge can be complex. One other note about Life is that it is one of the simpler forms of cellular automata.
A sample Life pattern
Here are some interesting patterns for the Life game.
This seed that produces a pulsar, which is a relatively complex shape that pulses between about four states:
The pulsar in one of its final forms :
This is an f-pentomino, a seed that does not stabilize in a short period of time, and produces some interesting results :
A "methuselah", which is a pattern that runs for an extended period of time before stabilizing:
After a short period of time, the above pattern grows to:
The code for this blog entry can be downloaded here. Enjoy! And, as this is definitely a new skill set for me, please feel free to tear the code apart, tell me how to do it better, etc.
Other useful links I found :
The F# Language specification
F# in 20 minutes – contains installation instructions
Bending Cats using F#
a notepad implementation in F#/WPF
ACO (ant Colony Optimization) in F#
a blog about F# and WPF, lots of useful information
lots of information on F#
F# lists and how to use them
Fun links :
"Ook", an example of a dysfunctional language (as opposed to functional)
an Ook compiler for .Net
hello world in Ook
Blog post about the task parallel library and F#