Sunday, 23 December 2007

Parallel programming with F#

Chance Coble has published a wonderful article about parallel programming in F#. In particular, the article describes how first-class functions make it easier to write parallel programs without sacrificing clarity.


Friday, 21 December 2007

Quick introduction to web services and databases

The F#.NET Journal just published an article describing how you can get started with web and database programming quickly and easily using F#:

"The F# programming language combines the expressive power of a modern functional programming language with the comprehensive libraries provided by the .NET framework. This article provides a quick introduction to two of the most widely used aspects of the .NET framework: web services and databases..."

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

Thursday, 20 December 2007

Review: Expert F#

Apress were kind enough to send me a complimentary copy of their latest F# book called Expert F# by Don Syme, Adam Granicz and Antonio Cisternino. Most notable among the authors, of course, is Don Syme who created the F# programming language and continues his role through its productization by Microsoft as lead developer. Now that I have spent some time perusing these 600 pages, I believe I can offer a fair opinion on who I think should read this book and why. I should also note that I am an author writing a competing book (F# for Scientists) for a competing publisher (John Wiley & Sons).

Expert F# does exactly what it says on the tin. Anyone serious about using F# professionally must have a copy of this book to hand because it is the only resource that describes how to build production-quality applications and libraries using F#. Robert Pickering's book Foundations of F# is a solid introduction to the language, particularly for object oriented programmers, but Expert F# goes the extra mile by covering everything a professional needs to know, such as the best way to design and implement interfaces in F# and when to bend the .NET guidelines in doing so.

In order to cover every important aspect of the F# language, from parsing with yacc to continuation passing, this book dives into every subject head first. Provided you are already familiar with the concepts involved, you'll quickly get up to speed on the F# way of doing things, but if you're a newbie then I think you'll find this book harder going than other introductory material on F#, like The F#.NET Journal articles. For example, by page 25 the book has already covered how to write a Windows Forms application that downloads web pages and counts the number of words in them. On the same page in Foundations of F#, you're still covering the Fibonacci function as an example of recursion. To be fair, that is as much a testament to the awesome expressive power of F# allowing you to write a web-fetching GUI application in a dozen lines of code but, still, you get the point!

In addition to covering all of the aspects of F# that are essential for professional programmers, Expert F# also covers several advanced topics, where F# represents the current state-of-the-art even among research languages. Two of the most notable subjects are active patterns and asynchronous workflows. The former being an elegant way to apply F#'s powerful OCaml-style pattern matching to alien data structures and the latter being a novel attack on concurrent programming.

Overall I think this is a superb book and I would not hesitate to recommend it to anyone wanting to learn more about the F# programming language. Since Microsoft's productization of F#, it is clear that this will be a force to be reckoned with in the world of professional programming languages and Expert F# is the companion everyone needs in order to learn how to harness this powerful new language. Easily worth its $35 eBook price tag.


Monday, 10 December 2007

Review: The F#.NET Journal

Lloyd Moore wrote the following review of The F#.NET Journal:

"There are two aspects that I would like to stress about the Fsharp Journal. The first is that I think that it has a unique ability to explain some tricky concepts across a very broad range of subjects in a fashion that is very straightforward, yet is comprehensive and very well explained.

The second reason is that its approach to introducing more advanced subjects, such as continuation passing style recursion, is done in a manner that helps one see not just the abstraction, but how it fits in a practical sense too."

Sunday, 9 December 2007

F# for Visualization beta for F# 1.9.3.7

The beta release of our F# for Visualization library and its demos are now available for the latest release of the F# compiler, version 1.9.3.7.

Thursday, 6 December 2007

F# in Visual Studio for free!

According to this blog post, you can now install the F# distribution into Microsoft's new Visual Studio 2008 shell to get F# working in a Visual Studio development environment absolutely free!

The Visual Studio mode for F# makes it much easier to author programs in F# so we highly recommend this approach for anyone who has been battling with a text editor and the command-line tools.

Monday, 3 December 2007

Parser Combinators

The F#.NET Journal just published an article about parser combinators:

"Certain applications are extremely well suited to functional programming and parsing is one of them. Specifically, the ability to write functional combinators that allow parsers for everything from integers up to symbolic expressions to be composed is more general and provides more opportunity for code reuse than the use of conventional parser generators such as fslex and fsyacc. This article explains how parser combinators may be designed and implemented in F#..."

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

Tuesday, 20 November 2007

Fifth member joins the F# team

Following the announcement in October that Microsoft are productizing F#, the F# team has been growing steadily. The original team of Don Syme and James Margetson was supplemented with Luke Hoban and Jumo Fisher shortly afterwards.

Chris Smith just announced that he is joining the F# team as a full-time tester. This is great news and Microsoft are clearly putting their money where their mouth is with F#.

Sequence expressions and comprehensions

The F#.NET Journal just published an article explaining how sequence expressions can be used to improve both the clarity and performance of F# code:

"The .NET framework provides a powerful generic interface called IEnumerable that allows containers to be treated as arbitrary sequences. The approach is now widely used in C# but F# takes IEnumerable to a new level with its Seq data structure. This article describes abstract sequences in F#, the comprehension syntaxes provided by F# to make their construction simpler and clearer and practical applications of sequences with several examples..."

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

Saturday, 3 November 2007

Optimizing a simple bytecode interpreter

The F#.NET Journal just published an article describing the implementation of a simple interpreter for a bytecode language:

"Interpreter and compiler writing is the bread and butter of the ML family of languages and F# is no exception. This article describes the design, implementation and optimization of an interpreter for a simple bytecode language..."

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

Thursday, 18 October 2007

Balanced Binary Search Trees

The F#.NET Journal just published an article describing the design and implementation of a basic balanced binary tree in F#:

"Functional programming languages like F# excel at handling immutable data structures. In the interests of efficiency, such data structures are typically based upon trees rather than hash tables. Key benefits include the ability to express algorithms elegantly using a declarative style and the inherent thread safety of immutable data structures makes them ideal for concurrent programming. This article describes the design and implementation of a basic balanced binary search tree data structure similar to that of the built-in Set module..."

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

Microsoft to productize F#

Microsoft have just announced that they are going to productize the F# programming language, bundle it with Visual Studio and place it alongside C# and Visual Basic in their arsenal of .NET languages.

This is tremendously good news for the F# community as the language and tools will now be developed even more quickly and Microsoft will be providing professional-grade support for commercial developers of F# solutions.

Interest in the F# programming language has been growing steadily this year and the language already has a solid user base, a growing set of third party libraries and even a job market. The productization of F# will greatly accelerate the adoption of this language and the technical prowess of the language will encourage users from other platforms to embrace .NET.

To learn more about the F# programming language from Microsoft, subscribe to The F#.NET Journal.

Wednesday, 3 October 2007

Parsing text with Lex and Yacc

The F#.NET Journal just published an article describing how the fslex and fsyacc tools can be used to generate parsers:

"The tool stack bundled with the F# distribution includes fslex and fsyacc tools that help in the construction of parsers. The ability to parse data in different formats is often very useful, particularly when translating between representations. This article introduces the concepts of lex and yacc-based parsing and describes how these tools may be used to construct robust and efficient parsers quickly and easily..."

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

Thursday, 20 September 2007

Implementing the FFT

The F#.NET Journal just published an article describing how a simple but efficient FFT algorithm may be implemented in F#:

"Writing an implementation of the Fourier transform is an excellent lesson in algorithm design and optimization. Moreover, the Fourier transform is one of the most essential tools in numerical computing, with applications ranging from spectral analysis to the multiplication of large integers. This article describes the design and implementation of a simple but efficient FFT..."

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

Saturday, 15 September 2007

High performance numerics with F#

We stumbled upon an interesting result recently whilst toying with numerical benchmarks ported from OCaml. Typically, OCaml programs are very easy to port but run more slowly under F# because the performance characteristics of the languages are different. However, we recently observed that some benchmarks optimized for OCaml actually run substantially faster in F# without having to make even a single change.

Specifically, the OCaml implementations of the numerically-intensive spectral-norm and n-body benchmarks from the Computer Language Shootout run more quickly in F#. We believe the reason is essentially that Microsoft's .NET compiler is much better at optimizing simple numerical algorithms, particularly loops over floating point arrays. Indeed, the results are all the more compelling because F# on vanilla 32-bit Windows XP Pro outperforms a longer, hand-optimized OCaml implementation running on OCaml's best-case platform for numerical programs, 64-bit Linux. In particular, bounds checking incurs a significant overhead in the spectral-norm benchmark and, we believe, the bounds checks are automatically hoisted from the inner loop in F# but this must be done manually in OCaml.


OCamlF#
Spectral-Norm14.3539.374
N-Body9.4696.933

This clearly shows that F# can achieve excellent performance on common machines for an important class of numerical algorithms.

For detailed articles covering all aspects of the F# programming language from Microsoft, subscribe to The F#.NET Journal today!

Thursday, 13 September 2007

Combinator Heaven

The F#.NET Journal published an article discussing the unique way that functions may be composed in functional languages using combinators:

"The ability to write higher-order functions that compose other functions in interesting ways is one of the most powerful forms of abstraction provided by the functional programming paradigm. Such functions are known as combinators . This article describes the basic concepts behind combinators with a variety of examples to demonstrate how practically useful this form of functional abstraction can be..."

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

Thursday, 23 August 2007

Friday, 17 August 2007

Exploiting Tail Recursion

The F#.NET Journal just published an article describing essential concepts in the design of functional loops:

"Recursion is essential to functional programming and the ability to write recursive functions that do not consume stack space can be pivotal. Function calls that require no stack space are called tail calls. This article describes the use of tail calls to write robust and efficient tail recursive functions in F#..."

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

Monday, 13 August 2007

Foundations of F# podcast

Robert Pickering, the author of "Foundations of F#", recently did an audio interview with Scott Hansel of HanselMinutes. The 25Mb audio file of the interview is available for download here.

Thursday, 2 August 2007

Introduction to DirectX

The F#.NET Journal just published an article describing basic use of DirectX in Windows Forms from the F# programming language:

The .NET platform contains library interfaces to almost all of the functionality bundled with the Windows platform. Hardware-accelerated graphics are no exception and Managed DirectX (MDX) for .NET provides a high-level and type-safe interface to the DirectX API...

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

F# 1.9.2 released

The F# team at Microsoft Research just released a new version of F#. This version adds several new features including:
  • use bindings: automatically dispose objects.
  • Slicing: refer to strided subarrays with a concise syntax.
  • Labelled and optional arguments: give function arguments names and default values.
  • Monadic-style asynchronous programming: a beautiful functional style for concurrent programs.
  • Visualization API: allows F# programs to use a uniform API to generate graphics using third-party products like Excel for F# for Visualization.
All of these features will be described in detail in future F#.NET Journal articles.

Monday, 16 July 2007

Introduction to .NET Threading

The .NET platform provides parallel execution of code through multithreading. A thread is an independent execution path, able to run simultaneously with other threads. This article describes the fundamentals of .NET threading and how this functionality can be leveraged elegantly by F# programs...

To read the rest of this article, subscribe to The F#.NET Journal today!

Monday, 9 July 2007

F# for Visualization 0.2.0

A new beta version of F# for Visualization was released yesterday.

This release adds a new threading model, allowing spawned visualizations to have their properties edited interactively either through the GUI or from an F# interactive session.

The next release will add support for the F# version of our high-performance 2D vector graphics library.

Tuesday, 3 July 2007

GUI Application: Sudoku Solver

This article walks through the design and implementation of a complete GUI application for solving Sudoku puzzles. This is perhaps the smallest interesting GUI application that demonstrates many different advantages of the F# programming language, including functional programming and .NET interoperability...

To read the rest of this article, subscribe to The F#.NET Journal today!

New Language Features

The F# programming language is about to have more exciting new features added:
  • Slicing
  • Asynchronous programming
Slicing is a useful syntax extension that allows subarrays to be referred to by offset and stride. This feature is taken from languages like Matlab and Python and can be used to express some array-based computations more succinctly. However, we should note that slicing is a vitally important optimization in Matlab and Python because looping contructs in these languages are very slow. This will not be the case in F#, where looping is already extremely fast.

Integrated support for asynchronous programming is a radical departure from the norm. This is a new syntax that transparently introduces a monadic style of programming specifically designed to make asynchronous programs both simpler and more robust. In particular, F# programs written in this style will benefit from the automatic handling of cancellations. This is a revolutionary new language feature and the preliminary example programs already demonstrate a huge improvement over conventional techniques.

Monday, 18 June 2007

Using the built-in Data Structures

The F#.NET Journal recently published its fifth article, on data structures:

"The .NET framework provides a wide variety of mutable data structures and the F# standard library supplements these with several immutable data structures that provide elegant functional interfaces. This article describes many of the built-in data structures, how they are used and when they are most applicable..."

To read the rest of this article, subscribe to The F#.NET Journal today!

Foundations of F# (review)

We just received our complimentary copy of Robert Pickering's excellent book "Foundations of F#".

This is the first book to cover the F# programming language from Microsoft. Robert has done an excellent job with this introductory book aimed at programmers with backgrounds in object-oriented or dynamic languages. The book covers various aspects of the .NET platform, object-oriented interoperability with existing libraries and some of Microsoft's more recent innovations, like LINQ.

"Expert F#" by Don Syme (the creator of F#) should be the next book published on F# later this year, followed closely by our own "F# for Scientists".

Friday, 1 June 2007

Objects and Augmentations

The F#.NET Journal just published an article discussing the use of object-oriented programming in F# and, in particular, the way F# types can be augmented to provide getters, setters, member functions, indexing and overloaded operators:

"In addition to functional programming, the F# language also offers object-oriented programming (OOP) in harmony with the .NET platform. The F# language takes powerful OOP concepts from C# and supplements them with elegant functional constructs. The result combines the best aspects of functional and object-oriented programming..."

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

Monday, 28 May 2007

Threading and Windows Forms

In order to keep a GUI responsive while other computations are being performed, it is essential to combine threading with GUI programming.

On the .NET platform, Windows Forms is the defacto-standard GUI library and it is not thread safe. This means that it is not safe to do anything with a form or any of the form's controls (GUI components) from any thread other than the one that created the form.

This is a serious headache for .NET developers and incorrect multithreaded code is a nightmare to debug.

Fortunately, the F# programming language greatly simplifies the task of adjusting GUIs from other threads. The fundamental concept is the same as the conventional solution on .NET: you create a message loop that queues operations that are to be evaluated on the GUI thread.

A GUI thread, new form and message loop may be created using:

let form = ref null
let make_form() =
form := new Form()
Application.Run(!form)
let thread = new Threading.Thread(make_form) in
thread.SetApartmentState(Threading.ApartmentState.STA);
thread.Start();


Note that we have been careful to keep a reference to the form that was created by the new thread.

The form cannot be edited directly from the main thread. However, the form.Invoke() method allows us to queue arbitrary operations for execution on GUI thread and these operations may alter the form at will. Moreover, these operations may be specified as simple functions of the type unit -> unit in F#.

For example, the form may be hidden safely by executing this code on any thread:


form.Invoke(fun () -> form.Visible <- false)


Although this does not make windows forms thread-safe in F#, it does greatly simplify the thread-safe use of windows forms.

Foundations of F#

Robert Pickering is now the author of the first F# book, Foundations of F#. The book is published by APress and they started printing it three days ago. Should hit stores in June!

Congratulations to Robert. Completing a book is an incredible achievement and, having seen the prerelease, I can say that this is a very solid introduction to the F# programming language.

We completed the translation of OCaml for Scientists to F# in February and F# for Scientists should be published by John Wiley & Sons later this year.

Saturday, 19 May 2007

XAML or F#?

XAML is an XML-based scene description language for Windows Presentation Foundation that allows designers to generate graphics and implement GUIs without having to write any code.

Although XAML is a domain specific language, the fact that it is based upon XML makes it quite verbose.

For example, Charles Petzold, author of the book Applications = Code + Markup, recently wrote several blog articles on the use of WPF and XAML, including the following XAML example that rotates four colored squares:

<Page xmlns="http://schemas.microsoft.com/winfx/2006/xaml/presentation"
xmlns:x="http://schemas.microsoft.com/winfx/2006/xaml"
WindowTitle="Rotating Geometry"
Title="Rotating Geometry">
<Page.Resources>
<RectangleGeometry x:Key="rect" Rect="0 0 100 100">
<RectangleGeometry.Transform>
<RotateTransform x:Name="rotate" />
</RectangleGeometry.Transform>
</RectangleGeometry>
</Page.Resources>

<Canvas>
<Path Canvas.Left="150" Canvas.Top="150"
Data="{StaticResource rect}" Fill="Red" />

<Path Canvas.Left="300" Canvas.Top="150"
Data="{StaticResource rect}" Fill="Blue" />

<Path Canvas.Left="150" Canvas.Top="300"
Data="{StaticResource rect}" Fill="Green" />

<Path Canvas.Left="300" Canvas.Top="300"
Data="{StaticResource rect}" Fill="Yellow" />
</Canvas>

<Page.Triggers>
<EventTrigger RoutedEvent="Page.Loaded">
<BeginStoryboard>
<Storyboard>
<DoubleAnimation
Storyboard.TargetName="rotate"
Storyboard.TargetProperty="Angle"
From="0" To="360" Duration="0:0:2"
RepeatBehavior="Forever" />
</Storyboard>
</BeginStoryboard>
</EventTrigger>
</Page.Triggers>
</Page>


This XAML example can be run directly from his web page.

We thought it would be interesting to translate this example into the F# programming language to see how it compares in terms of functionality and verbosity. Here is the resulting program using the F# for Visualization graphics library:

let square =
[vec3 0. 0. 0., vec3 0. 1. 0., vec3 1. 0. 0.;
vec3 1. 0. 0., vec3 0. 1. 0., vec3 1. 1. 0.] >
triangles

let at(c, x, y) =
let aux() = rot_z(time()) * translate(vec3 x y 0.)
dynamic_transform aux square >
color c

let scene =
[Color.Red, -0.75, -0.75;
Color.Blue, 0.75, -0.75;
Color.Green, -0.75, 0.75;
Color.Yellow, 0.75, 0.75] >
List.map at > group

Graphics3D(scene).Show


In the case of this simple example, the F# programming language can clearly represent the same content more concisely. Moreover, the graphics library provides an interactive 3D interface to the scene with the ability to export to JPEG.

For those designers wanting to generate real-time interactive 2D and 3D graphics who are daring enough to try functional programming, the F# language is a tempting tool. To learn more about the F# programming language, subscribe to the F#.NET Journal today.

Wednesday, 16 May 2007

Particle simulation

Real-time simulation of particle dynamics with a high-performance interactive 3D visualization running in parallel:

http://www.ffconsultancy.com/products/fsharp_for_visualization/demo3.html

3D Surface Plot

Another new demo for our graphics software. This time its a real-time interactive 3D surface plot of a function f(x,z) with only a single line of F# code:

http://www.ffconsultancy.com/products/fsharp_for_visualization/demo2.html

Our library maintains real-time performance even though the tesselation contains tens of thousands of triangles. The visualization can be manipulated with the mouse and exported as an image.

New Icosahedron demo

We just updated F# for Visualization with a new demo:

http://www.ffconsultancy.com/products/fsharp_for_visualization/demo1.html

This one shows off the latest mouse interactivity, export as image and some of the new API in only 6 lines of code.

F# for Visualization

Our F# for Visualization library just went into beta release. This software makes 2D and 3D graphics as easy to use as possible for F# programmers:

http://www.ffconsultancy.com/products/fsharp_for_visualization/

Join the beta release scheme now and get the final product free!

Tuesday, 15 May 2007

Who wants F#?

We've been looking at data submitted by readers registering interest in the F#.NET Journal:

http://www.ffconsultancy.com/products/fsharp_journal/register.html

The two most popular languages cited are C# and C++. No surprise there, perhaps. The C++ programmers are probably interested in learning something higher-level, with garbage collection and so forth. The C# programmers might be interested in leveraging F# for its integral support for interactivity, built-in numerical types, type inference and (more recently) beautiful support for asynchronous programming.

However, the next most popular language for people wanting to learn F# is Lisp. We found that quite surprising, for one because we didn't realise so many people knew Lisp. These guys are probably yearning for pattern matching, better performance, .NET interoperability and the elimination of run-time errors.

Of the submissions, around half cited performance critical applications as their domain. Compilation to native code is a major benefit here but F# also provides easy interoperability with native-code libraries like LAPACK and FFTW, some superb numerical libraries for .NET like the Extreme Optimization library from Numeric Edge as well as some wierd and wonderful options like compilation of F# to GPU using Accelerator.

Overall, the stage looks set for F# to make a serious impact on the way scientific computing is done, with a bewildering array of exciting projects in all of the major disciplines of science and engineering. Sounds like everyone wants F#.

3D Surface plot in 3 lines of code!

This demo shows a high-resolution 3D surface plot of a function f(x,z) rendered in real time using DirectX with only 3 lines of code:

http://www.ffconsultancy.com/products/fsharp_for_visualization/demo3.html

Monday, 14 May 2007

F# Development using Visual Studio 2005

"The F# distribution includes extensions to Microsoft Visual Studio that provide a rich development environment for F# programmers. In this article, we shall describe how this development environment can be setup and used to make development as easy and productive as possible..."

To read this article and watch its tutorial video, subscribe to the F#.NET Journal today:

http://www.ffconsultancy.com/products/fsharp_journal/

Tuesday, 8 May 2007

Structs vs classes

Whilst writing our FFT implementation in both C# and F#:

http://www.ffconsultancy.com/products/signal_processing_net/

I noticed several interesting things.

Firstly, C# doesn't provide a type for complex numbers. So you must either pull in a random library or write your own. I think that is a bit of a shame because Microsoft have clearly put a lot of effort into creating a high-performance .NET implementation and lots of people are clearly interested in writing numerical programs in .NET.

Secondly, when you define your own complex number type you have the choice between using a struct and using a class. The difference between the two is essentially that C# will pass a struct by value and a class by reference. The tradition in languages like C++ and C# is to use structs and unbox agressively yourself where possible, with the belief that structs are often faster.

I thought I'd tinker with this because my first F# implementation was 3x slower than my first C# implementation and I remembered that the complex number implementation in the F# standard library still uses a class (structs were only added to F# recently).

Sure enough, reimplementing the complex class in F# with a struct-based version brought the speed up to par, actually slightly faster than the C#.

This was the first of two interesting performance results. The whole program was made 3x faster simply by using a struct rather than a class. Another point for the faith-based view that structs are fast and well suited to atomic values.

Then I tried a similar experiment on our 2D and 3D vector graphics software:

http://www.ffconsultancy.com/products/fsharp_for_visualization/

changing the implementation of 2D and 3D vectors to structs. Surprisingly, although I had assumed that low-dimensional vectors have almost identical usage to complex numbers, using a struct is actually ~15% slower. Not a huge performance difference but an interesting result nonetheless.

So structs are not always faster, even for very simple types, and there is no substitute for benchmarking.

I should note that there are more differences between structs and classes in the context of C# because this language exposes more complicated argument passing semantics (value and reference types).

Sunday, 6 May 2007

FFTs again

Noting a distinct lack of decent and cheap FFT implementations for .NET that can be used in commercial products, we recently wrote our own implementations in C# and F#. We've actually made the C# implementation available as a product:

http://www.ffconsultancy.com/products/signal_processing_net/

Note the performance results that show a competitor giving quadratic worst-case performance!

Interestingly, the F# implementation is slightly faster than the C#. The style is very similar so the implementations are roughly the same size. F# gives more potential for factoring so I'm probably going to refactor the FFT kernel into something written in a functional style with the aim of exploiting concurrency.

Tuesday, 1 May 2007

The Essence of Functional Programming

Most programmers learning F# will be coming from a background of object-oriented programming languages like C++, Java and C#. For those readers, it is vitally important to forget about object-oriented programming when learning the F# programming language, even though it exposes the OO features of the .NET platform.

F# is fundamentally a functional programming language and the use of functions instead of objects often leads to shorter and clearer code. Indeed, many of the benefits of functional programming are already known to OO programmers in the form of "design patterns".

This article will elucidate the essential properties of functional programming...

To read the rest of this article subscribe to The F#.NET Journal now!

http://www.ffconsultancy.com/products/fsharp_journal/index.html?fsb

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:

http://www.ffconsultancy.com/products/fsharp_for_visualization/

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:

http://www.ffconsultancy.com/products/fsharp_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:

http://www.ffconsultancy.com/products/fsharp_journal/

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:

http://research.microsoft.com/~aphillip/spim/

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)
Array.map (fun x -> d.BeginInvoke(x, null, null)) a >
Array.map (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
a

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.

Thursday, 8 March 2007

Cellular Automata demo

I've just uploaded a 70-line demo program that renders the rule 30 cellular automaton into a bitmap and displays it in a window.

The program demonstrates the use of Windows Forms and bitmaps from F# as well as several idioms from functional programming including higher-order functions, currying and closures.

Tuesday, 6 March 2007

Fast Fourier Transforms

I've spent the past few weeks trying to pin down the best possible way to do some core computations used in scientific computing from .NET and the F# programming language.

Several of the examples from my book OCaml for Scientists use these techniques via libraries like FFTW and LAPACK. I'll translate some of them into F# for my forthcoming book F# for Scientists. I cannot over-emphasise the importance of these algorithms. They underpin so many different kinds of analysis used by scientists and picking the wrong implementation can cost you months of wasted work.

First up is the Fast Fourier Transform. This algorithm underpins many spectral-based methods (including time-frequency methods) and it is very difficult to write a good (fast and accurate) Fast Fourier Transform routine. In particular, the infamous Numerical Recipies presents a lot of misinformation on the subject and should be avoided.

I have tried dozens of FFT implementations in the past and found two good ones. Under Linux there is the excellent FFTW library by Matteo Frigo and Steven G. Johnson. This library actually handles the FFTs for Matlab. Also, Mathematica has an excellent FFT algorithm built-in that works not only with ordinary floats but also with interval arithmetic and even arbitrary-precision arithmetic!

So, what is available under .NET? There are some expensive commercial offerings as well as some free ones. I'll start by describing the common problems before getting onto the implementations themselves.

Generality: an FFT routine must be able to handle all lengths of input "n" from zero upwards. Surprisingly often, FFT routines are distributed that only handle integral powers of 2. More worryingly, scientists and engineers are often told that padding with zeros up to the next integral power of 2 is "ok" (it is not!) and that power of 2 sizes are much faster to transform (they are not!). Handling arbitrary sizes is extremely important because the errors introduced by zero padding can be severe and a significant amount of work is required to prove that the artificial errors do not affect the results.

Performance: an FFT routine suitable for general use must be able to maintain O(n log n) complexity for all input sizes "n". Prime factor decomposition can get you a long way there but you don't want O(n^2) when you try to transform a prime-length array, so that technique must be combined with something like Bluestein's convolution method to recover small prime factors albeit with a bigger constant prefactor.

As it turns out, the best free implementation that I've found for F# users so far is still the fantastic FFTW library. Their site has a precompiled Windows DLL. I've written minimal bindings that allow thread-safe access to FFTW from F#, with both guru and simple interfaces. Performance is excellent, 32-bit Windows XP Pro is only up to 35% slower than 64-bit Linux.

I'll publish the 90-line bindings ASAP and F# for Scientists will detail how the bindings are written and how they can be used as well as some complete example programs using this library to perform FFTs.

Faced with a lack of O(n log n) implementations suitable for inclusion in commercial products, we wrote our own implementations in C# and F#. The C# implementation is now available on our site:

http://www.ffconsultancy.com/products/signal_processing_net/

For end users wanting to compute FFTs cheaply, my recommendation is definitely for the free FFTW library. If you're writing a commercial product then you can buy a licence for it from MIT or, if a million dollars is out of your budget, you can buy our FFT implementation for only £99.

I'll disseminate my results on matrix computation next time...

Cheers,
Jon.

Sunday, 4 March 2007

ANTS profiler by RedGate software

The Cambridge-based company Red-Gate software have a profiler for .NET called the ANTS profiler and they recently started working on support for the F# programming language.

Saturday, 24 February 2007

FSharp.net

I just found an empty website at fsharp.net that contains forums for discussing F#. There are a few registered users already.

As much as I like the Hub, it can be very slow.

F# certainly seems to be gaining popularity. I've had 2,500 visitors to my F# demos so far this month. I've also changed my site to use the less ambiguous term "F#.NET" in the hope that this will catch on and become a better way to Google for the F# programming language.

Cheers,
Jon.

Saturday, 17 February 2007

Symbolic manipulation

The F# programming language excels at the manipulation of symbolic expressions. This includes compiler and interpreter writing (the manipulation of programs) but perhaps the most obvious application is computer algebra.

The language features that make F# ideal for symbolic processing are variant types and pattern matching. The following snippet of F# code defines a variant type and overloads the + and * functions, allowing symbolic mathematical expressions to be constructed using ordinary arithmetic operators:

type t =
| Q of int
| Var of string
| Add of t * t
| Mul of t * t with

static member ( + ) (f, g) = match f, g with
| Q n, Q m -> Q (n + m)
| Q 0, e e, Q 0 -> e
| f, Add(g, h) -> f + g + h
| f, g -> Add(f, g)

static member ( * ) (f, g) = match f, g with
| Q n, Q m -> Q (n * m)
| Q 0, e e, Q 0 -> Q 0
| Q 1, e e, Q 1 -> e
| f, Mul(g, h) -> f * g * h
| f, g -> Mul(f, g)
end

Composing symbolic expressions using these operators has the added benefit of performing some simplifying rearrangements. For example, adding 0 or multiplying by 1 has no effect.

> Q 2 + Q 1 * Var "x" + Q 0;;
val it : t = Add (Q 2,Var "x")

As well as being expressive, F#'s pattern matching is also very efficient. This implementation can simplify randomly generated expressions with 10^6 atoms in 0.386s on my 2.2GHz AMD64.

Cheers,
Jon.

Wednesday, 14 February 2007

Avoiding copying in functional programming languages

This boils down to an absolutely pivotal concept in functional programming
called referential transparency. This concept is one of the main stumbling
blocks for imperative programmers learning FPLs like F#. I
certainly had trouble grokking this concept when I ditched C++.

In essence, when a new immutable data structure is created from an existing
data structure, the new data structure has a lot in common with the original.
An imperative programmer immediately assumes (incorrectly) that the original
data structure must have been copied. In fact, there is never any need to
copy immutable data because you can simply refer back to the original, i.e.
referencing is transparent.

So FPLs effectively handle everything by pointer (mutable or immutable) and
the only copying you'll ever incur is copying pointers. In this case, the
pointers inside the record will be copied, which is nothing to worry about.

In the vast majority of cases, succinct F# code is efficient F# code. As
long as you don't explicitly copy lots of data, there won't be much copying
going on "under the hood".

Friday, 2 February 2007

F# is the perfect tool for scientists

I'm in the process of writing my next book "F# for Scientists" and, whilst looking for interesting examples, decided to try to mix web programming with science.

I ended up with a tiny F# script that can be run from an F# interactive session. The first few lines download the XML data on the C terminal domain of rabbit serum haemopexin (a piece of protein that I analysed many years ago). The XML data is stored in GZipped form, which is easily decompressed using built-in .NET library functions.

The resulting XML can be parsed using other .NET library functions but the result is much easier to handle if it is converted into an F# variant type (rather than a .NET object hierarchy). This can be done by a single, tiny F# function that can then be applied to any XML document. The result is displayed by the interactive session, making it much easier to dissect the XML tree structure and get at the data you want.

In this case, I extract the amino-acid sequence of the protein and compute the Kyte-Doolittle hydrophobicity profile. I intend to do a little analysis of this data (maybe calculating the pseudoperiodic features using wavelets) to illustrate how tertiary protein structure can be subtly related to simple functions of the sequence. Of course, the results of any computations can even be injected into Excel using .NET's "automation" API.

The F# interactive mode turns out to be ideal for scientists who want to slice and dice their data without having to write a complete program. Although a few other languages (e.g. Python, Matlab) provide interactive sessions, F# is vastly faster and a much more elegant language.

I believe that visualisation will be the killer reason for scientists to use F# though. The ability to spawn real-time visualisations from an interactive session is nothing short of awesome. The results are vastly superior to anything I've ever seen, even in expensive commercial packages like Matlab and Mathematica.

Consequently, I think it is highly likely that I'll start doing some visualisation-related work as soon as this book is polished. Programmatic visualisations can be done quite easily using .NET and Managed DirectX but F# and its interactive mode pave the way for supremely-elegant declarative graphics, where you just write "sphere here" and "cylinder there" to visualise a complete scene.

I'd like to abstract away quite a bit "under the hood". Rendering seemingly simple features like shadows is actually quite technically challenging and these kinds of visual clues are vitally important to the human ocular system.

I envisage a future where scientists can visualise their results using sophisticated 2D and 3D graphics with minimal effort and without having to buy books on game programming and learn about adaptive subdivision.

Cheers,
Jon.

Wednesday, 24 January 2007

RAII

In a recent usenet thread regarding the practical benefits of garbage collection, a C++ user stated that having a GC makes it harder to deterministically free resources such as file handles, database connections and texture maps. I'd like to address this issue by explaining how garbage collected language retain all of the benefits of determinism when necessary whilst also allowing programmers to free themselves from the burden of explicit deallocation.

Firstly, let me describe what Resource Acquisition Is Initialisation (RAII) is. This technique involves wrapping the handle for an external resource in a class that provides a constructor to obtain the resource and a destructor to release it, something like this in in a C++ library:

class File {
Handle h;
File(string name) : h(new Handle(name)) {}
~File { h.close(); }
}

and something like this is the user's code to read a string from the file:

{
File file = new File("myfile.txt");
string text;
file.handle >> string;
return string;
}

The file is automatically close by the destructor of the "file"object when the scope ends. Moreover, if an exception is raised in the middle of the function then C++ still calls the destructor and closes the file as the exception propagates past the end of the scope, ensuring that we do not leak file handles.

Had we used a finalizer in a garbage collected language to close the file, the point at which the finalizer gets invoked and the file is closed is not known. Consequently, this is bad style.

However, the benefits of RAII can be obtained in F#. Essentially, you implement your own scope in a higher-order function. For example, to read a file you could use something like this in the library:

let read file k x =
let ch = open_in file in
try k x ch finally
close_in ch

To read a string, a user would then write:

read "myfile.txt" (fun () -> input_line) ()

Exactly this functionality is provided in the Idioms module of the F# standard library. The Idioms.using function can be used to create and destroy resources deterministically, giving all of the benefits of RAII.

So, there's one less reason to use C++...

Cheers,
Jon.