Saturday, 28 April 2007

Easy Visualization with F#

F# interactive sessions provide unrivalled potential for high-performance numerical computing (compilation to native code) coupled with interactive visualization.

Flying Frog Consultancy are beta testing their forthcoming visualization package for F# that adds first-class graphics to the language, providing easy access to high-performance graphics both from F# programs and spawned from interactive sessions.

The beta release with a tutorial video and three demos is available here:

Tuesday, 17 April 2007

Pattern matching

Compared to conventional programming languages, F# takes dynamic dispatch to a whole new level using an approach called pattern matching. This article guides the reader through the fundamental concepts that underpin pattern matching before providing some examples demonstrating the power of pattern matching in general programming...

The complete article is on-line at the F#.NET Journal:

Sunday, 15 April 2007

The F#.NET Journal

Flying Frog Consultancy are starting The F#.NET Journal to publish fortnightly articles about the F# programming language:

The articles cover a wide range of topics, including an introduction to functional programming, pattern matching, the .NET platform and more advanced material demonstrating the use of the F# interactive mode for data dissection and visualization.

Subscribe for as little as £10 per month.

Friday, 13 April 2007

Stochastic Pi-Calculus

I had a fascinating meeting yesterday with some of the guys at Microsoft Research Cambridge. In particular, I was introduced to the "stochastic pi-calculus" for the first time:

Despite the scary-sounding name, this is actually a very elegant and simple approach to simulating "population", in this case the populations of different species of biological molecules in an organism.

A system is defined by a flow chart that gives the rates of transitions between states (e.g. the rate of production of a protein). The simulator takes chooses from the possibilities at random, resulting in a Monte-Carlo simulation that is faster than a discrete time simulator and more accurate than a simple symbolic solution.

The applications for such a generic simulator are very diverse. Some obvious ones are chemical reactions in chemistry and ecosystems in population biology. However, the package needs a user interface overhaul if it is going to be used by working scientists.

We were discussing the prospect of using the 2D vector graphics engine that I have been developing over the past decade and it occurs to me that many people in the F# community could benefit from this functionality and I could sell the library. If you're interested in buying visualization tools from us them please comment on this blog entry and let me know what you need. I already have quite a repository of software and it is about time I started releasing products based on F#, given the current explosion in the number of F# users.

Monday, 9 April 2007

Exploiting concurrency

As a functional programming language, F# provides many higher-order functions for manipulating data structures. The "map" function is one of the most important ones. The map function takes two arguments, a function and a data structure, and returns a new data structure of the same kind where each element is the result of applying the given function to the corresponding element in the input data structure.

For example, map f [1; 2; 3] computes [f 1; f 2; f 3]. Functions that manipulate other functions in this way (higher-order functions, curried functions and combinators) are the essence of functional programming.

An interesting feature of the "map" function is that the applications of the given function "f" can be done concurrently (in parallel). When the function "f" is slow (takes longer than a microsecond), or when it is to be applied many times (such that the whole map takes over a millisecond), a concurrent implementation of the map function can make efficient use of multiple CPUs and significantly outperform the sequential map function.

The F# standard library does not yet provide concurrent versions of such higher-order functions. This is partly due to the fact that the seemingly simple task of writing such a function is made very complicated by the large number of trade-offs involved in the design of the map function.

Whilst writing F# for Scientists, I have discovered that there is a very significant middle-ground that provides a map function with sufficiently low overhead that it is useful in a wide variety of situations without having to resort to dangerous optimizations that can result in deadlocks (e.g. the use of a global thread pool) and race conditions. You'll have to read the book to learn how a more sophisticated "map" function can be implemented!

The parallel map function is most simply written using the asynchronous invocation of a delegate. This is a slightly alien concept for F# programmers. A delegate is just the .NET name for a closure and delegates provide methods called BeginInvoke and EndInvoke that allow them to be executed concurrently. Moreover, this approach handles both the collection of results from the invocation and any exceptions that might be raised during their execution.

To make the asynchronous interface for a closure available, it must be converted into a delegate. This can be done using the System.Converter class.

The following implementation of a parallel map uses this approach:

let global_map f a =
let d = new System.Converter<'a, 'b>(f) (fun x -> d.BeginInvoke(x, null, null)) a > (fun a -> d.EndInvoke(a))

Although simple, this map function can be used to distribute computations among CPUs. However, there are many problems with this function. Firstly, the asynchronous invocation relies upon the global .NET thread pool. As the worker threads are not local to each application of the "map" function, they can be deadlocked if this map function is used recursively (i.e. if "f" calls "map"). Secondly, there is considerable overhead in queueing function applications on the global thread pool. So the performance of this function can be greatly improved upon by using a different approach (the "map" function described in F# for Scientists is up to 100x faster).

Despite its shortcomings, this parallel map function should be enough to get you leveraging parallelism and exploiting those dual cores that you paid so much for!

For keen readers wishing to learn more about threading on the .NET platform, I highly recommend Joseph Albahari's mini e-book Threading in C#.

Foreign Function Interface (FFI)

Interoperability with native-code libraries is an unsung hero in the F# world. This little-discussed feature makes it easy to interface to libraries like LAPACK, FFTW and legacy code written in unmanaged languages.

The following F# snippet illustrates minimal use of the F# foreign function interface to implement a very fast discrete sine transform function that looks and acts just like an ordinary F# function.

The following module binds the primitive C functions exported by the excellent FFTW library:
module Primitive =
open System.Runtime.InteropServices
open Microsoft.FSharp.NativeInterop

[<dllimport(@"libfftw3-3.dll", entrypoint="fftw_malloc">]
extern double *fftw_malloc(int size);

[<dllimport(@"libfftw3-3.dll", entrypoint="fftw_free">]
extern void fftw_free(double *data);

[<dllimport(@"libfftw3-3.dll", entrypoint="fftw_plan_r2r_1d">]
extern void *fftw_plan_r2r_1d(int n, double *i, double *o,
int kind, int flags);

[<dllimport(@"libfftw3-3.dll", entrypoint="fftw_destroy_plan">]
extern void destroy_plan(void *plan);

[<dllimport(@"libfftw3-3.dll", entrypoint="fftw_execute">]
extern void execute(void *plan);

The following function allocates an array using the FFTW library's custom allocation function to ensure optimal data alignment:
open Primitive

let make n =
let ptr = fftw_malloc(8*n)
let na = NativeArray.FromPtr(ptr, n)
ptr, na

Finally, the following function uses the FFTW library to plan how to do a Fourier transform before actually doing it:
let dst a =
let n = Array.length a
let ptr, arr = make n
Array.iteri (fun i x -> arr.[i] <- x) a
let plan = fftw_plan_r2r_1d(n, ptr, ptr, 7, 0)
execute plan
destroy_plan plan
let s = 1. / sqrt(float(2*(n + 1)))
let a = Array.init n (fun i -> s * arr.[i])
fftw_free ptr

That is all that is required to the use C interface of this part of the FFTW library from F# code.

The F# distribution contains extensive bindings for the LAPACK linear algebra library, which covers the other main facet of scientific computation.

The design and use of these techniques will be described in detail in my forthcoming book F# for Scientists.