Concurrency (continued)

Well, I've translated about 15kLOC of OCaml/OpenGL to F#/DirectX now: my Smoke vector graphics engine. The translation has been amazingly painless, especially considering the commercial benefits of opening the Windows market.

Smoke's basic design revolves around a scene graph that appears to be purely functional to the user but actually caches as much as possible to improve performance (this is why Smoke is 10x faster than Microsoft's Avalon, Adobe's SVG viewer and Macromedia's flash for complex scenes). I've skipped most of this translation because DirectX lacks a lot of vital functionality compared to OpenGL, specifically display lists (that transparently compile static geometry and upload it to the graphics card) and a tesselator (that converts winding-rule polygons into triangles).

I spent two weeks tracking down a really annoying bug. This bug manifested itself as access violations from Managed DirectX (not supposed to be possible!), corrupted IL (also not supposed to be possible) and weird-looking corrupted renderings. I originally blamed the problem on Windows Forms not being thread safe. Having scoured the docs for information on that I started to blame Managed DirectX.

As it happens, the problem was caused by an innocuous-looking closure in my F# code. I had replaced a cached OpenGL display list with a cached closure that would render a geometry. However, different visualisation windows can share the same scene graph and, particularly, the same caches. And this cached closure was caching the DirectX device that it was rendering to. Consequently, the OnPaint method of one window, running in one thread, was trying to write to a device that belonged to another thread. Hence the corruption. It seems that DirectX doesn't check for this and, consequently, it was sometimes resulting in memory corruption.

Aside from this one annoying bug, the ability to perform computations concurrently in F# is nothing short of miraculous. My immutable OCaml code runs concurrently with no changes. I only used immutable data structures four times in 15kLOC of code. Once I had wrapped these with locks, to prevent different threads from accessing them simultaneously, the entire 15kLOC was ready to exploit my dual core system. Sure enough, performance is almost doubled!

There's no way this could have been done in two weeks had I been using C++ or C#...

I'll upload a demo showing the graphics capabilities of my libraries ASAP. In the mean time: happy hacking!

Cheers,
Jon.

Windows forms and Threads

I've been trying to get the vector graphics renderer from Presenta to play nice with the F# interactive mode. I only just discovered the problem and, in fact, I think it is the same problem that wreaks havoc with all Windows Forms applications when run from the interactive mode (including the bundled F# samples).

The problem arises when you try to spawn forms and continue using the interactive mode. The UIs are then executing on the same thread as the interactive mode itself. This would be fine provided everyone played nice and yielded every now and again using Application.DoEvents() but the interactive mode blocks waiting for user input. If you're playing with one of the F# samples from the interactive mode and its GUI freezes then try hitting return in the interactive mode to make the GUI responsive again.

Anyway, I tried to fix this in various ways, spawning threads, and had no luck... until today. It turns out that the fix is really easy. The fundamental problem is that Windows Forms are not thread safe. They use a "message loop" to convey things like the need for repaint and this whole loop must execute on the UI thread and not in any other thread. You can invoke messages from other threads but, if you just want to spawn a background window (e.g. for visualisation) and don't care what happens to it, there is no need to worry about invoking messages.

So all you do to create a completely separate "application" is spawn a thread, create your form and apply Application.Run(form) to it. The call to Application.Run sets up a completely new message loop for that thread. I've been playing with it this afternoon and it seems to work perfectly. I can spawn multiple windows visualising different data from the interactive mode and they all run beatifully. Moreover, they can take advantage of my dual core because they are running in separate threads.

One final discovery: there is a thread.IsBackground boolean property that is false by default. All background threads are killed when the last foreground thread dies. For example, if you have a GUI thread and a worker thread then you can make the GUI thread the foreground thread (the default setting) and set IsBackground in the worker thread to true so that it is killed when the GUI is closed. I've been bitten by not doing this during development, when a process hangs around after I believed I had finished it and I can't then rebuild because the EXE is in use.

Anyway, I'll be putting lots of essential bits of information like this in my book "F# for Scientists"...

Array manipulation (continued)

I've been studying the slice-based approach to array manipulation used by the Python and Matlab implementations of a 1D, 4-tap discrete wavelet transform. I am particularly interested in this because of the idea of incorporating Matlab-like array slicing in future versions of F#.

Here is the Python code (written by Sturla Molden):

def D4_Transform(x, s1, d1, d2):
odd = x[1::2]
even = x[:-1:2]
d1[:] = odd[:] - C1*even[:]
s1[:-1] = even[:-1] + C2*d1[:-1] + C3*d1[1:]
s1[-1] = even[-1] + C2*d1[-1] + C3*d1[0]
d2[0] = d1[0] + s1[-1]
d2[1:] = d1[1:] + s1[:-1]
even[:] = C4 * s1[:]
odd[:] = C5 * d2[:]
if x.size > 2:
D4_Transform(even,s1[0:even.size/2],
d1[0:even.size/2],d2[0:even.size/2])

The discrete wavelet transform computes downsampled convolutions repeatedly until no data remains. My F# implementation of this transform is:

let rec d4_aux a n =
let n2 = n lsr 1 in
let tmp = Array.make n 0. in
for i=0 to n2-2 do
tmp.(i) <- a.(i*2)*.h0 +. a.(i*2+1)*.h1 +. a.(i*2+2)*.h2 +. a.(i*2+3)*.h3;
tmp.(i+n2) <- a.(i*2)*.g0 +. a.(i*2+1)*.g1 +. a.(i*2+2)*.g2 +. a.(i*2+3)*.g3;
done;
tmp.(n2-1) <- a.(n-2)*.h0 +. a.(n-1)*.h1 +. a.(0)*.h2 +. a.(1)*.h3;
tmp.(2*n2-1) <- a.(n-2)*.g0 +. a.(n-1)*.g1 +. a.(0)*.g2 +. a.(1)*.g3;
Array.blit tmp 0 a 0 n;
if n > 4 then d4_aux a (n lsr 1)

Firstly, this could be simplified by using a new type to represent a cyclic array. However, unless the modulo indexing was hoisted from loops over the array, this would adversely affect performance.

Note that the F# is both shorter and faster than the Python. In fact, the F# is as fast as C++!

The next thing to note is that the the Python code doesn't use slicing because it is a good idea in general but, rather, because it evades touching the arrays element-wise (which would be very slow in an interpreted language like Python). So, are slices useful?

My F# program could be written more succinctly using slices:

let rec d4_aux tmp a n =
let n2 = n lsr 1 in
for i=0 to n2-2 do
tmp.(i) <- dot h a.[i*2:];
tmp.(i+n2) <- dot g a.[i*2+1:];
done;
Array.blit tmp 0 a 0 n;
if n > 4 then d4_aux a (n lsr 1)

Where a.[i:] denotes a kind of IEnumerable starting at index "i".

This has saved quite a bit of code but optimising this back to the original is quite difficult.

So I think slices would be useful in F#. However, I think they will be much more useful if they are part of a generic framework for handling random-access containers, like IList, such that you can take slices of slices, or slices of random-access containers that aren't arrays (e.g. functional arrays implemented as balanced binary trees).

On a related note, I'd like an equivalent of OCaml's stream parsing syntax extension. This could be done using the upcoming feature "active patterns" to dissect an IEnumerable (now called Seq).

In summary, I think slices will be useful in F# but I don't think they will be as prevelant in F# as they are in languages like Matlab and Python because F# already provides very fast element-wise access.

Array manipulation

I was just browsing comp.lang.python for the first time and this post caught my eye:

http://groups.google.co.uk/group/comp.soft-sys.matlab/msg/de710b0e8c16e022?hl=en&

The post gives Matlab and Python code (using numpy) to perform a 1D discrete wavelet transform using the Daubechies D4 wavelet (which is one up from the Haar wavelet).

To a functional programmer, this implementation would benefit from deforesting or lazy evaluation. Specifically, this approach eagerly generates lots of unnecessary arrays. The reason is that this approach is faster in Matlab and Python (and other language with slow interpreters and comparatively-fast whole-array operators, like Mathematica) but it is much slower in compiled general-purpose languages like C, C++, Java, OCaml, SML, Haskell and F#.

The essence of optimising such programs in languages like F# is very interesting. You take the definition of a new array, like "even":

let even = Array.init (n/2) (fun i -> x.(2 * i + 1))

and you replace it with a closure:

let even i = x.(2 * i + 1)

Not only is the latter more succinct, it also evades the allocation and filling of a whole array by representing the array as an implicit data structure. This is a deforesting optimisation because it avoids unnecessary allocation and is actually a simple version of the optimisation that I used to improve upon the performance of Numerical Recipies' simulated annealing solution to the travelling salesman problem in my book OCaml for Scientists.

In F#, this will be lightning fast but in interpreted languages like Matlab and Python, indirecting through a closure invokes the heavy machinery of the general purpose interpreter and, consequently, is many times slower. I've done the test and my OCaml implementation is half as long as the Python and 3x faster. F# will give similar results, of course.

I believe that a lazily evaluated F# extension to IList would be very valuable, just as IEnumerable.map and filter are valuable. It could include common functions like "even" and "odd" (which fetch every other element in an IList subtype, e.g. an array). The discrete wavelet transform could then be written very succinctly and elegantly and would serve as an excellent example of the value of real functional programming.

Raytracer posted on Reddit

There's a discussion about my raytracer and F# in general following a post about my ray tracer on Reddit:

http://programming.reddit.com/info/t70b/comments

Graphics with .NET

I've spent the past couple of weeks developing graphical demos using F# and .NET. My previous blogs mention the ray tracer and spinning teapot Direct X demo.

Under .NET, developers are spoiled for choice when it comes to graphics. You can use WinForms and bitmaps, as I did for the ray tracer. There's managed DirectX, which I used for the teapot. More recently, Microsoft have create XNA and WPF.

However, none of these systems are as easy to use from languages like C# and F# as competing systems, such as OCaml and OpenGL. In my book "OCaml for Scientists" I introduce OpenGL visualisation with a 6-line program that reliably displays a blank window. That takes over 80 lines of code with managed Direct X because you must limit the minimum size of the Direct X widget or it will crash and you must handle device losses and resets yourself. To make matters harder, it is almost impossible to find accurate information on how this is accomplished.

I appreciate that this is boiler-plate code, you get it working once and then cut and paste it into every one of your programs but it is too much to expect users to write those 80 lines of code everytime they want to see a triangle.

In Mathematica, for example, you can write a single line of code to get a 3D surface plot that you can then export as a PostScript or PDF file:

Plot3D[Sin[x^2+y^2], {x, -3, 3}, {y, -3, 3}]

I want to be able to do this from F#, 100x faster and with .NET interoperability.

So I set about writing a library to make it as easy as possible to do real-time, interactive, 2D and 3D visualisation from F#. The foundation comes from the code base of our presentation software Presenta:

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

In addition to compiling and running programs to create visualisations, you can now slice and dice your data in the F# interactive mode and have it throw up windows visualising your data as you go. You can even control the contents of the windows after they've been created!

Needless to say, I'll be commercialising this as soon as its done. One thing is ringing true though - F# is the next stage in the evolution of programming languages!

Cheers,
Jon.

DirectX demo

I've uploaded a DirectX written in F#:

http://www.ffconsultancy.com/dotnet/fsharp/teapot/

Quotations

Tomas Petricek posted an interesting blog entry on the use of quotations in F#:

http://cs.hubfs.net/blogs/tomasp/archive/2006/07/07/413.aspx

To paraphrase, you can quote some F# code:

> <@1+2*3@>

and get the abstract syntax tree representing that code:

val it : ast = Add(Int 1, Mul(Int 2, Int 3))

Ray tracer

Just uploaded a new F# example program with executable and complete source code:

http://www.ffconsultancy.com/dotnet/fsharp/raytracer/index.html

Sudoku solver in F#

I've uploaded the first of many example F# programs: a Sudoku solver complete with GUI.

http://www.ffconsultancy.com/dotnet/fsharp/sudoku/

Google Trends shows F# taking off

I've been doing a lot of Google Trend searches to improve the direction of my company recently. The results certainly seem to back my decision to go into the F# market:

http://www.google.com/trends?q=f%23&ctab=0&geo=all&date=all

F# has been visible for a few years but has really started to increase during 2006.

Cheers,
Jon.

Welcome to my new blog about the F# programming language for .NET. I'll be posting any interesting tidbits that I find on this blog.

Check out our F# web pages here:

http://www.ffconsultancy.com/dotnet/fsharp/index.html