Thursday, 30 December 2010

Performance-related features in F# and C#

Many people expect the performance of F# to be comparable to the performance of C# "because they both compile to the same intermediate language (CIL)". Although the VM obviously places the same ceiling on the performance of both F# and C# there are some features that affect performance differently between the two language implementations.

Firstly, C# and F# don't actually compile down to the same CIL because only F# generates tail calls. This affects performance when mutually recursive functions that represent the different states of a state machine tail call each other in order to move between states. This design pattern often appears in the context of asynchronous workflows that can tail call each other in F# but this will not even be possible with the new async support in C# 5.

Secondly, the implementation of delegates on .NET is currently quite inefficient and, consequently, F# uses its own FastFunc type for high-performance first-class functions.

Thirdly, F# uses .NET metadata to convey inline functions so that they can be exported across APIs and, of course, that can dramatically improve performance in certain circumstances. Moreover, F#'s inlining allows functions passed as arguments to higher-order functions to be completely inlined and type specialized. Our F# for Numerics library makes extensive use of this feature to ensure that per-type functions such as comparison are specialized, giving performance in F# up to 2,350× faster than the equivalent C# (!). In fact, some of our numerical routines are consistently several times faster than vendor-tuned Fortran in libraries like the Intel MKL.

Finally, pattern matching can be extremely laborious to express in C# because the language lacks pattern matching but it is almost impossible to maintain optimized C# code equivalent to many non-trivial pattern matches. In contrast, the F# compiler aggressively optimizes pattern matches during compilation.

Conversely, the C# compiler can be better at optimizing computations over value types (e.g. complex arithmetic).


Tuesday, 14 December 2010

Parsing mathematical expressions using active patterns

Active patterns allow arbitrary user-defined functions to be used to dissect values during pattern matching. This opens up some interesting possibilities with regard to parsing because it allows active patterns to be used to destructure streams of data when known patterns are encountered.

The following code sample creates several mutually-recursive active patterns that form a recursive descent parser for mathematical expressions:

> let rec (|Term|_|) = function
| Factor(e1, t) ->
let rec aux e1 = function
| '+'::Factor(e2, t) -> aux (e1 + e2) t
| '-'::Factor(e2, t) -> aux (e1 - e2) t
| t -> Some(e1, t)
aux e1 t
| _ -> None
and (|Factor|_|) = function
| '-'::Factor(e, t) -> Some(-e, t)
| Atom(e1, '*'::Factor(e2, t)) -> Some(e1 * e2, t)
| Atom(e, t) -> Some(e, t)
| _ -> None
and (|Atom|_|) = function
| c::t when '0'<=c && c<='9' -> Some(int(string c), t)
| '('::Term(e, ')'::t) -> Some(e, t)
| _ -> None;;
val ( |Term|_| ) : char list -> (int * char list) option
val ( |Factor|_| ) : char list -> (int * char list) option
val ( |Atom|_| ) : char list -> (int * char list) option

For example, the following parses the expression 1 + 2 × (3 - 4) × -5:

> let (Term e) = List.ofSeq "1+2*(3-4)*-5";;
val e : int * char list = (11, [])

The F# programming language is descended from the MetaLanguages (ML) family that were specifically bred for metaprogramming including parsing. For more information on metaprogramming with F#, read the following articles in The F#.NET Journal:

Sunday, 5 December 2010

Numerical methods: matrix inversion

The F#.NET Journal just published an article about numerical methods:

"Matrix inversion is one of the most important numerical methods with many practical applications. In practice, the numerical instability of matrix inverses leads to the use of linear solvers that effectively premultiply by the inverse of a matrix without having to explicitly compute the matrix inverse. This article disregards numerical accuracy in order to write the simplest possible function that computes the inverse of a matrix. The resulting function is just 8 lines of F# code and the remainder of the article is devoted to examining the generality and parallelization of this tiny function. We find that our tiny solution is up to 4.3× faster than Mathematica 7's built-in matrix inversion..."

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

Tuesday, 30 November 2010

"A Taste of F#" video lecture by Don Syme

Without further ado, here is Don Syme's recent Tech-Ed lecture on F# today and in the future:










Get Microsoft Silverlight

"F# is like waterfowl..."

Winner of the British Computer Society’s Roger Needham award, Byron Cook, described why F# is his language of choice in a recent interview:

"F# is like waterfowl: it looks very graceful and calm from above, but below the water its legs are furiously working to protect you from the reality below..."


What's your preferred .NET programming language?

Zoho are running a poll about language preference on .NET:

The results show a surprisingly large proportion of developers now choosing F#, even more than VB!

Monday, 22 November 2010

Checking for pangrams

A pangram is a phrase that uses every letter of the alphabet. The following F# function can be used to check a string to see if it constitutes a pangram:

> let isPangram (str: string) = (set['a'..'z'] - set(str.ToLower())).IsEmpty;;
val isPangram : string -> bool

The function works by computing a set difference, removing the set of letters used in the string from the set of letters in the alphabet. If the resulting set is empty then the string must have used every letter in the alphabet and, therefore, it is a pangram.

Note how easy F# makes it to build sets from arbitrary sequences (lists and strings of characters, in this case) and perform set theoretic operations such as set difference (and union and intersection) on them. This basic functionality has a wide variety of applications ranging from the manipulation of strings seen here to the computation of nth-nearest neighbors in computational science (see the article Traversing networks: the nth-nearest neighbor in The F#.NET Journal).

For example, the following verifies a popular English pangram:

> isPangram "The quick brown fox jumped over the lazy dogs";;
val it : bool = true

Sunday, 21 November 2010

Computational geometry: quick hull

The F#.NET Journal just published an article about computational geometry:

"Computing the convex hull of a set of points is a challenge of fundamental importance in computational geometry. Other tasks such as Delaunay triangulation can be built upon a convex hull algorithm and then tasks such as Ruppert's algorithm may be built upon those. This article describes the design and implementation of the quickhull algorithm in just 10 lines of F# code before going on to build a WPF-based GUI application that can be used to manipulate a convex hull interactively..."

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

Sunday, 14 November 2010

Visualizing a complete graph

Kean Walmsley posted an article describing how AutoCAD can be used to visualize a complete graph using vector graphics. This prompted Cay Horstmann to publish an article describing how the SPDE framework makes it possible to visualize the same thing using only 12 lines of Scala code. Here's how you can do the same thing in F# out-of-the-box in only 10 lines of code:

> #r "PresentationCore.dll";; > #r "PresentationFramework.dll";; > #r "System.Xaml.dll";; > #r "WindowsBase.dll";; > open System.Windows;; > let n = 24;; val n : int = 24 > let p i = let t = float(i % n) / float n * 2.0 * System.Math.PI Point(1.0 + sin t, 1.0 + cos t);; val p : int -> Point > let shape = Shapes.Polyline(Stroke=Media.Brushes.Black, StrokeThickness=0.001);; val shape : Shapes.Polyline > for i=0 to n-1 do for j=i+1 to n do Seq.iter shape.Points.Add [p i; p j];; val it : unit = () > Window(Content=Controls.Viewbox(Child=shape)) |> Application().Run |> ignore;;

When run from an F# interactive session, this program produces the following output:

Being able to solve simple problems simply and scale it up to sophisticated commercial software is why I love F#!

Wednesday, 10 November 2010

Concurrent programming: TCP relay server

The F#.NET Journal just published an article about concurrent programming:

"Asynchronous workflows are an incredibly useful feature of the F# programming language in the context of concurrent programming. This article describes a simple concurrent program that provides a relay server that can be instructed to connect to a TCP server and forward messages to it..."

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

Saturday, 6 November 2010

F# reaching a wider audience

There are now dozens of F#-related articles at The Code Project covering a variety of interesting topics.

Some vendors have also started to publish literature describing how their products can be used from F#. For example, the Extreme Optimization high-performance numerical libraries for .NET now provide examples in F#.

Recent events like Microsoft's PDC 2010 including a lecture from Don Syme on The Future of F# and the recent release of the F# compiler and tool stack as open source software have massively boosted the visibility of F# which is great to see, not least because sales of Visual F# 2010 for Technical Computing just doubled!


349 people following Don Syme on Twitter

Don Syme now has 349 followers on Twitter. Doesn't sound like an amazing accomplishment until you learn that Don has never tweeted anything in his life! Apparently he is too busy flying around the world giving awe-inspiring presentations about the F# programming language he created.

According to Phil Trelford, Twitter is hot for F# right now so I couldn't help but get my own account and start tweeting!


Wednesday, 27 October 2010

F# video interviews with Don Syme (parts 1-4)

David Gristwood has posted a fascinating four-part series of video interviews with the creator of the F# programming language, Don Syme:

  1. An introduction to F#.

  2. An F# tutorial.

  3. F# and Windows Azure.

  4. F# in use at Microsoft Research.

In addition to our old F# for Scientists book that Don mentions in the interview, you may also appreciate our new Visual F# 2010 for Technical Computing book.

Tuesday, 19 October 2010

Graph algorithms: topological sort and all-pairs shortest paths

The F#.NET Journal just published an article about graph theory:

"Following on from our previous article about depth- and breadth-first searches of graphs, this article examines some more involved algorithms that also have many practical applications. A topological sort of a directed acyclic graph produces the vertices in a sequence where every vertex reachable from another appears after it in the sequence. All-pairs shortest paths finds the shortest path from any vertex to any other vertex..."

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

Memory leaks in asynchronous workflows

During the development of a concurrent distributed application for a client, we repeated a common mistake of tail recursing in an asynchronous workflow using the do! construct. For example:

let agent execute =
   new MailboxProcessor<_>(fun inbox ->
      let rec loop() = async {
         let! msg = inbox.Receive()
         execute msg
         do! loop()
         }
      loop())

This is problematic because using do! in this context leaks stack frames every time the workflows recurses (which is typically every time a message is processed). Moreover, F# uses a trampoline to implement this stack so the consequence is not a stack overflow but, rather, a gradual memory leak.

So if your concurrent applications appear to be leaking a few kilobytes for each message they process, search for instances of do! in tail position and replace them with return! like this:

let agent execute =
   new MailboxProcessor<_>(fun inbox ->
      let rec loop() = async {
         let! msg = inbox.Receive()
         execute msg
         return! loop()
         }
      loop())

Sunday, 3 October 2010

Representing and searching graphs

The F#.NET Journal just published an article about graph theory:

"Graph theory is an important branch of mathematics in the context of programming because important problems can often be phrased in terms of graphs. This articles takes a look at the representation of graphs in F# and introduces the basic operations of depth-first and breadth-first searches..."

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

Wednesday, 15 September 2010

Distributed message passing

The F#.NET Journal just published an article about message passing:

"The F# programming language makes message passing easy thanks to union types and pattern matching. Asynchronous workflows leverage this to provide Erlang-style agent-based programming. However, Erlang programs can be distributed across multiple machines transparently but asynchronous workflows work only in-process. This article examines the use of TCP sockets and serialization to communicate values between machines in order to use distributed message passing..."

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

F# lectures from the New England F# user group

The New England F# user group in the United States have put up a great list of video lectures and associated slides here.

Sunday, 12 September 2010

Simulating predator-prey relationships

The F#.NET Journal just published an article about biological simulation:

"This article describes the design and implementation of a Windows Presentation Foundation application that simulates and visualizes the evolution of the predator and prey populations over time. This involves the numerical integration of a differential equation and the resulting trajectory is visualized as a parametric plot using the new charting and graphing functionality provided with .NET 4. The parameters of the simulation can be adjusted by the user and the graph is updated in real time..."

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

Wednesday, 1 September 2010

Draft F# Component Design Guidelines

The F# team at Microsoft have kindly released a draft of their F# Component Design Guidelines. This document provides a wealth of advice for professional F# developers covering both F#-facing code and code exposed to other .NET languages.

Recommended reading for all F# programmers!

Sunday, 29 August 2010

Calculator

The F#.NET Journal just published an article about typeful programming:

"The pedagogical calculator sample demonstrates how a program can evaluate mathematical expressions originating from the user interface of a calculator. This article describes the design and implementation of a calculator application that uses Windows Presentation Foundation to provide a graphical user interface similar to that of a traditional calculator. In particular, every effort is made to leverage static checking in order to catch as many bugs at compile time as possible. This includes not only sophisticated union types to represent the state of the state machine but also exhaustiveness and redundancy checking of the advanced pattern matches that result as well as their factoring to reduce code size..."

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

Wednesday, 18 August 2010

Don Syme lecturing at the F#unctional Londoners Meetup

Creator of the F# programming language and all-around great guy Don Syme will be giving a lecture at the F#unctional Londoners Meetup, Skills Matter eXchange, on 9th September 2010.

Saturday, 7 August 2010

Jon Harrop lectures on Parallel QR Decomposition

The Skills Matter eXchange have kindly uploaded the video of my recent lecture as well as the accompanying slides.

The core of this lecture is an explanation of why purely functional code that looks embarrassingly parallel often does not scale and how scalability can be achieved through the use of mutation.

The example used is QR decomposition where pure code achieves less than 2× speedup on 8 cores but impure F# code achieves over 7× speedup and beats the reference implementation of BLAS and LAPACK with 99% less code. However, the lessons learned are not specific to this algorithm or even to numerical methods in general but apply to all software running on .NET.

For vastly more information on this subject, stay tuned for our forthcoming Multicore .NET book.

Wednesday, 4 August 2010

Data structures: heaps

The F#.NET Journal just published an article about data structures:

"A min-heap is a tree-based data structure that satisfies the constraint that the children at any given branch are always larger than their parent and, consequently, the minimum element is at the root. Heaps are most notable as an efficient way to implement priority queues which, in turn, underpin a variety of algorithms including some seen in previous F#.NET Journal articles. This article examines skew heaps, leftist heaps, pairing heaps and splay heaps..."

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

Tuesday, 27 July 2010

F#unctional Londoners meetup lecture (28th July 2010)

Zach Bray of Trayport and Jon Harrop of Flying Frog Consultancy Ltd. will be presenting lectures at Skills Matter eXchange London (UK) at 6:30pm on Wednesday 28th July 2010.

Many thanks to Carolyn Miller and Phil Trelford for organizing F#unctional Londoners Meetup Group, an excellent series of events!

Saturday, 17 July 2010

Histogram equalization

The F#.NET Journal just published an article about image processing and the new charting functionality in .NET 4:

"Over- and under-exposed images have their intensity distributions skewed to the high or low end of the range. Histogram equilization is one technique to combat this effect digitally by spreading out the distribution of intensities in an image via the intensity histogram. This article describes a program for image enhancement using histogram equalization with an interactive WPF-based GUI using the new charting functionality in .NET 4 to visualize the intensity histograms in real time..."

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

Monday, 12 July 2010

F# vs Mathematica: an even faster pricer for American options

The previous post described a performance-critical pricer for American options. Upon reflection, the optimized Mathematica code had introduced many redundant computations in order to vectorize the code because vectorization offers considerable performance improvements in such a slow language. Our simple translation of the optimized Mathematica had not taken advantage of this by removing these redundant computations.

This new optimized and parallelized F# solution is now a whopping 960× faster than the original Mathematica code from Sal Mangano's Mathematica Cookbook:

let americanPut kk r sigma tt = let sqr x = x * x let ikk, a, nn, mm, tt0 = 1.0 / kk, 5.0, 1000, 200, sqr sigma * tt / 2.0 let k, h, s = 2.0 * r / sqr sigma, 2.0 * a / float nn, tt0 / float mm let alpha, k0, k1 = s / sqr h, 0.5 * (k - 1.0), 0.25 * sqr (k + 1.0) let x i = float i * h - a let ex = Array.init (nn+1) (fun i -> exp(x i)) let ek0x = Array.init (nn+1) (fun i -> exp(k0 * x i)) let pp0 i = max 0.0 (kk - kk * ex.[i]) let ek0a, k1s, a' = exp(k0 * a), k1 * s, 2.0 * alpha - 1.0 let mutable u = Array.init (nn+1) (fun i -> ek0x.[i] * pp0 i * ikk) let mutable u' = Array.create (nn+1) 0.0 for j=0 to mm-1 do let ek1sj = exp(k1s * float j) let k2 = alpha * ikk * ek0a * ek1sj u'.[0] <- alpha * u.[1] - a' * u.[0] + k2 |> max (ek0x.[0] * ek1sj * (1.0 - ex.[0])) let inline get (u: _ []) i m = max m (alpha * (u.[i+1] + u.[i-1]) - a' * u.[i]) for i=1 to nn/2 do u'.[i] <- get u i (ek0x.[i] * ek1sj * (1.0 - ex.[i])) for i=nn/2 to nn-1 do u'.[i] <- get u i 0.0 let u'' = u u <- u' u' <- u'' let k3 = kk * exp(-k1 * tt0) Seq.mapi (fun i u -> kk * ex.[i], k3 / ek0x.[i] * u) u Array.Parallel.init 1000 (fun i -> americanPut (float(i+1)) 0.05 0.14 1.0)

Note that the hardcoded constants nn and mm have been increased, sigma has been decreased to keep alpha just below 0.5 and strikes from 1 to 1,000 are computed in order to make the F# code take a significant fraction of the second (when the Mathematica takes several minutes!).

Friday, 9 July 2010

F# vs Mathematica: fast pricer for American options

UPDATE: A new F# solution that is 960× faster than the original Mathematica is available here.

Another example from Sal Mangano's Mathematica Cookbook, this time taken from Andreas Lauschke's example, is a "fast" pricer for American options. The relevant section of the book stresses the importance of performance in this context and the Mathematica code presented was heavily optimized by experts. Here is their code:

Specifically, this function has been optimized by pushing computational burden from the general-purpose term rewriting language of Mathematica onto the optimized C routines in its standard library and then compiling the high-level code into lower-level bytecode that is interpreted more efficiently, giving another 5× speedup.

However, this general approach to the optimization of Mathematica code has the unfortunate side effect of "foresting": introducing unnecessary intermediate data structures because built-in operations over them are faster than writing a direct solution in such a slow language. Consequently, a direct solution in a compiled language will usually be orders of magnitude faster. In this case, we found that the following translation to F# is 64× faster than Sal's original Mathematica benchmark:

let americanPut kk r sigma tt = let sqr x = x * x let a, nn, mm, tt0 = 5.0, 100.0, 20, sqr sigma * tt / 2.0 let k, h, s = 2.0 * r / sqr sigma, 2.0 * a / nn, tt0 / float mm let alpha, xn = s / sqr h, int(2.0 * a/h + 0.5) + 1 let x i = float i * h - a let ss = Array.init xn (fun i -> kk * exp(x i)) let k0, k1 = 0.5 * (k - 1.0), 0.25 * sqr (k + 1.0) let k1s = k1 * s let pp0 i = max 0.0 (kk - ss.[i]) let rec run (u: _ []) (u': _ []) j = if j=mm then u else let f i = let xi = -a + float i * h if xi >= 0.0 then 0.0 else exp(k0 * xi + k1s * float j) * (1.0 - exp xi) u'.[0] <- alpha * u.[1] - (2.0 * alpha - 1.0) * u.[0] + alpha / kk * exp(k0 * a + k1s * float j) |> max (f 0) for i=1 to u.Length-2 do u'.[i] <- alpha * (u.[i+1] + u.[i-1]) - (2.0 * alpha - 1.0) * u.[i] |> max (f i) run u' u (j+1) let u i = exp(k0 * x i) * pp0 i / kk let u = run (Array.init xn u) (Array.create xn 0.0) 0 ss, Seq.mapi (fun i u -> kk * exp(-k1 * tt0 - k0 * x i) * u) u Array.Parallel.init 10000 (fun strike -> let ss, ps = americanPut (float(strike+1)) 0.05 0.4 1.0 Seq.zip (Seq.take 60 ss) (Seq.take 60 ps))

The superior performance of the F# solution comes from two main benefits:

  • The F# program is compiled all the way down to machine code before being executed whereas the Mathematica code is interpreted. The intermediate data structures are then replaced by simple function calls. This alone makes the F# solution over 10× faster than the original Mathematica.

  • F# inherits the benefits of a highly-optimized multicore-capable run-time from the .NET platform. This allows us to use fine-grained parallelism to improve performance even further for another 6.1× speedup on this 8-core machine.

Thursday, 8 July 2010

F# vs Mathematica: parametric plots

Another example from Sal Mangano's Mathematica Cookbook (p.520) is an elegant little Mathematica program that uses a crude numerical integrator to plot the trajectory of a differential equation representing the populations of predators (foxes) and prey (rabbits):

This example, which was derived from this Wolfram Demonstrations sample, really plays to the strengths of the Mathematica language, not least its enormous standard library of graphing libraries.

However, .NET 4 does include new charting functionality so it is interesting to see how elegantly this can be written in F#. The following F# program implements the same functionality when evaluated interactively:

#r "System.Windows.Forms.dll" #r "System.Windows.Forms.DataVisualization.dll" #r "WindowsBase.dll" #r "WindowsFormsIntegration.dll" #r "PresentationCore.dll" #r "PresentationFramework.dll" #r "System.Xaml.dll" open System.Windows.Forms open System.Windows.Forms.DataVisualization.Charting let trajectory g k t = let evolve(r, f) = let dtrf = 0.0001 * r * f r + (1.0 - r/k)*r*g - dtrf, dtrf + (1.0 - g)*f Seq.scan (fun s _ -> evolve s) (50.0, 10.0) {1..t} use series = new Series(ChartType=SeriesChartType.Line) for x, y in trajectory 0.02 5e2 1500 do series.Points.AddXY(x, y) |> ignore use area = new ChartArea() area.AxisX.Title <- "Rabbits" area.AxisX.Minimum <- 0.0 area.AxisY.Title <- "Foxes" use chart = new Chart(Dock=DockStyle.Fill) chart.ChartAreas.Add area chart.Series.Add series use form = new Form() form.Controls.Add chart form.Show()

When evaluated, this F# program produces the following output:

This program will be the basis for a future F#.NET Journal article that introduces user interaction. Although Mathematica also makes user interaction easy as well, its relatively poor performance often makes interactive programs sluggish whereas the relevant code in our F# version of this program runs 64× faster than the original Mathematica and, consequently, produces a fluid user interface.

Wednesday, 7 July 2010

F# vs Mathematica: red-black trees

Mathematica is an expensive commercial application sold as software for "interactive technical computing". In particular, the product centers around the Mathematica programming language which is a very powerful and dynamic language based upon term rewriting with excellent graphical capabilities and a wealth of useful functionality in its standard library. However, Microsoft's new F# programming language not only provides most of the useful functionality found in Mathematica but has many other benefits, not least that it is completely free!

We have previously compared F# and Mathematica in the context of 2D vector graphics. This post is the first in a series comparing these languages. Specifically, this post compares data structures. The F# programming language is designed for efficient compilation to native code whereas the Mathematica language is generally evaluated via term rewriting which is, essentially, a very inefficient form of interpretation. Consequently, F# code is typically 10-1,000× faster than Mathematica code unless computational burden can be shifted onto functions written in other languages (usually those in the vast standard library).

The latest Mathematica-related book, Mathematica Cookbook by Sal Mangano, contains many examples including a translation of Chris Okasaki's immutable red-black trees from Haskell to Mathematica augmented with a function to remove an element from a tree. Unfortunately, the new function written by Sal Mangano is incorrect and silently corrupts the shape of the tree. Thus, we shall focus on the subset of the code presented in Sal's book that is correct. This code may be written as follows in F#:

type color = Red | Black type 'a t = Node of color * 'a * 'a t * 'a t | Leaf let balance = function | Black, z, Node (Red, y, Node (Red, x, a, b), c), d | Black, z, Node (Red, x, a, Node (Red, y, b, c)), d | Black, x, a, Node (Red, z, Node (Red, y, b, c), d) | Black, x, a, Node (Red, y, b, Node (Red, z, c, d)) -> Node (Red, y, Node (Black, x, a, b), Node (Black, z, c, d)) | x -> Node x let insert x s = let rec ins = function | Leaf -> Node (Red, x, Leaf, Leaf) | Node (color, y, a, b) as s -> if x < y then balance (color, y, ins a, b) elif x > y then balance (color, y, a, ins b) else s match ins s with | Node (Red, y, a, b) -> Node (Black, y, a, b) | t -> t

The Mathematica code is significantly more complicated (714 vs 1514 bytes) for two main reasons:

  • Mathematica has no types so it cannot express a type with an ordering, so a new rbTree data structure is created with an ordering and that must then be boxed and unboxed by hand.
  • Mathematica prohibits top-level or-patterns so the same pattern is repeated four times in the balance function.

The simpler F# solution is also 20× faster at inserting 100k elements and 100× faster at computing the range of depths in the resulting tree.

In the next post, we'll start to compare the graphical capabilities of the two languages.

Monday, 5 July 2010

Happy numbers

Consider the sequence obtained by summing the squares of the digits of a number and then repeating with the result. If this sequence ends with the number one then the numbers in the sequence are Happy Numbers.

One of the challenges on Rosetta code is to compute the first eight Happy Numbers. The current F# solution weighs in at 26 lines of code. Let's see if we can do better...

We begin by writing a next function that computes the next happy number after the given number:

> let rec next (m: Set<_>) n i = if i=1 then n else if m.Contains i then next Set.empty (n+1) (n+1) else Seq.sumBy (fun d -> pown (int d - int '0') 2) (string i) |> next (m.Add i) n;; val next : Set<int> -> int -> int -> int

Note the use of the string function to convert an int into its string representation and then the use of the int function to convert each char back into an int.

Finally, we use the List.scan function to build a list of accumulated results as the next function finds each of the happy numbers in turn:

> List.scan (fun n _ -> next Set.empty (n+1) (n+1)) 1 [1..7];; val it : int list = [1; 7; 10; 13; 19; 23; 28; 31]

The scan function is relatively new and, consequently, not as widely appreciated as perhaps it should be.

Our whole program weighs in at only 6 lines of code, much shorter than the original!

Sunday, 4 July 2010

Lorenz attractor

The Lorenz attractor is a fractal derived from the trajectory of a 3-dimensional dynamical system that exhibits chaotic flow. This blog post describes a 35-line program that computes trajectories of this attractor and visualizes them as a beautiful whisp using Windows Presentation Foundation:

The program is as follows:

> #r "PresentationCore.dll";; > #r "PresentationFramework.dll";; > #r "WindowsBase.dll";; > #r "System.Xaml.dll";; > let trajectory f (x, y, z) dt n = let s, b, p = 10.0, 8.0 / 3.0, 28.0 let mutable x = x let mutable y = y let mutable z = z let a = Array.zeroCreate n for i=0 to n-1 do a.[i] <- f (x, y, z) x <- x + s * (y - x) * dt y <- y + (x * (p - z) - y) * dt z <- z + (x * y - b * z) * dt a;; val trajectory : (float * float * float -> 'a) -> float * float * float -> float -> int -> 'a [] > open System.Windows;; > let whisp() = let rand = System.Random() let f x = x + pown (rand.NextDouble() - 0.5) 2 let x, y, z = f 10.0, f 0.0, f 20.0 let xys = let f(x, y, z) = Point(20.0 + x, 25.0 + y - z + 50.0) trajectory f (x, y, z) 0.003 2000 let line_to (xy: Point) = (Media.LineSegment(xy, true) :> Media.PathSegment) Media.PathGeometry[ Media.PathFigure(xys.[0], Seq.map line_to xys, false) ];; val whisp : unit -> Media.PathGeometry > do let group = Media.GeometryGroup() for i=1 to 100 do whisp() |> group.Children.Add |> ignore let brush = Media.SolidColorBrush Media.Colors.Red let path = Shapes.Path(Data=group, Stroke=brush, StrokeThickness=0.005) let box = Controls.Viewbox(Child=path, Stretch=Media.Stretch.Uniform) let window = Window(Content=box, Title="Lorenz attractor") (Application()).Run window |> ignore;;

The trajectory function generates an array derived from the coordinates along a trajectory with the given starting position. The whisp function computes a trajectory with a slightly randomized starting position and generates a WPF PathGeometry. Finally, the main program generates 100 whisps and visualizes them.

Rigid body dynamics demo

The F#.NET Journal just made another downloadable demo freely available. This demo is from the article Rigid body dynamics (15th January 2010).

The article walks through the design and implementation of a 250-line program that simulates the dynamics of a collection of solid balls as they bound around a scene, using Windows Presentation Foundation for visualization!

Friday, 2 July 2010

Diff

The F#.NET Journal just published an article about text processing:

"The unix program diff identifies differences between text files, line by line. This tool is most useful for comparing two versions of a program. This article develops a simple implementation of the diff tool based upon the longest common subsequence (LCS) algorithm with a graphical user interface written using Windows Presentation Foundation to visualize the difference between two text files..."

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

Tuesday, 29 June 2010

Expert F# 2.0

Don Syme et al. have updated their seminal text on F#, bringing hardcore developers all the gory detail in the new Expert F# 2.0 book.

This is the second book to cover the latest version of F# that shipped with Visual Studio 2010 in April. The first book was, of course, our own Visual F# 2010 for Technical Computing.

Saturday, 19 June 2010

Parallelism in .NET 4 and Visual F# 2010

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

"The latest version of the .NET Framework provides a wealth of functionality for parallel programming aimed at multicores. This includes not only the Task Parallel Library, that was previously available in the form of CTP releases, but also Parallel LINQ (PLINQ) and the new concurrent collections. The F# standard library has also been augmented with parallelized functions. This article examines each of these in turn..."

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

Sunday, 6 June 2010

A dragon curve in 17 lines of F#

Dragon curves are a family of self-similar fractal curves. The following 17-line F# program uses Windows Presentation Foundation to visualize the results of a simple recursively-constructed dragon curve:

open System.Windows open System.Windows.Media let m = Matrix(0.0, 0.5, -0.5, 0.0, 0.0, 0.0) let step segs = seq { for a: Point, b: Point in segs do let x = a + 0.5 * (b - a) + (b - a) * m yield! [a, x; b, x] } let rec nest n f x = if n=0 then x else nest (n-1) f (f x) [<System.STAThread>] do let ps = nest 14 step (seq [Point(0., 0.), Point(1., 0.)]) let d = Vector(Seq.min[for a, b in ps -> min a.X b.X], Seq.min[for a, b in ps -> min a.Y b.Y]) let lineTo p = (LineSegment(p, true) :> PathSegment) let path = Shapes.Path(Stroke=Brushes.Black, StrokeThickness=0.003) path.Data <- PathGeometry[for a, b in ps -> PathFigure(a-d, [lineTo(b-d)], false)] (Application()).Run(Window(Content=Controls.Viewbox(Child=path))) |> ignore

This program produces the following output:

Cache oblivious algorithms: Matrix multiply

The F#.NET Journal just published an article about cache oblivious algorithms:

"The widespread adoption of CPU caches around two decades ago forced a change in the way programmers traverse data structures when performance is of interest. The classic style was to iterate directly using for loops. Two new styles have emerged: either a cache aware set of loops that tile the dataset into fixed-size subsets that fit into a cache of a known size, or a cache oblivious style that uses divide and conquer to subdivide the problem until it fits into the cache regardless its size. This article describes the revolutionary idea of cache oblivious algorithms via the elegant and efficient implementation of a matrix multiply in F#. In particular, we demonstrate the importance of these techniques in the context of multicore programming...."

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

Tuesday, 25 May 2010

Mini hash table

Imagine you're stuck on a desert island with only a few keystrokes and you desperately need to create your own rudimentary hash table. What might you do?

Well, here's one possible solution: a function that takes a sequence of key-value pairs and builds a hash table, returning another function that searches the hash table for the given key in order to find its corresponding value:

> let hashtbl xs = let spine = [|for _ in xs -> ResizeArray()|] let f k = spine.[k.GetHashCode() % spine.Length] Seq.iter (fun (k, v) -> (f k).Add (k, v)) xs fun k -> Seq.pick (fun (k', v) -> if k=k' then Some v else None) (f k);; val hashtbl : seq<'a * 'b> -> ('a -> 'b) when 'a : equality

Here's how you might use it to look up some squares:

> let tbl = hashtbl [for x in 0..100 -> x, x * x];; val tbl : (int -> int) > tbl 4;; val it : int = 16 > tbl 12;; val it : int = 144

Thursday, 20 May 2010

Quicksort

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

"The quicksort algorithm was invented by Tony Hoare in 1960 and remains one of the most celebrated algorithms and is still of great practical value. Implementing some of the many variations of the quicksort algorithm serves as an excellent introduction to mixed-paradigm programming in F# and the implementation of a production-quality implementation benefits enormously from the use of a substantial number of exotic features of the F# language. Moreover, the quicksort algorithm is amenable to parallelization, which is of increasing relevance in the multicore era, so the performance characteristics of parallelizations of the implementations are also of great interest..."

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