Saturday, 17 December 2011

Rendering autostereograms

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

"An autostereogram is a tiling distorted such that the differences between one column of tiles and the next simulate the differences between images seen by the left and right eyes when viewing a 3D scene. This allows a practiced viewer to stare through the picture such that their eyes view the stereogram offset by a single column of tiles and, therefore, they perceive the image to be 3D. This article describes a simple technique that allows autostereograms to be generated by a parallelized F# program..."


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

Sunday, 11 December 2011

Metaprogramming: parsing with active patterns

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

"Metaprogramming is the art of writing programs that manipulate other programs and includes writing compilers and interpreters as well as more exotic tools such as theorem provers. This article walks through the construction of a mini ML interpreter and, in particular, uses a novel approach to parsing based upon F# active patterns. This allows us to write a lexer and parser for a toy functional language in under 100 lines of vanilla F# code..."


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

Saturday, 5 November 2011

Scalable servers with async F#

We recently pitted a traditional server built using synchronous C# 4, ADO.NET and WCF with an equivalent solution built using asynchronous F#, ADO.NET and Google Protocol buffers over sockets. The characteristics of the two solutions really demonstrate the advantages of an asynchronous approach when using .NET. Specifically, our asynchronous solution was found to have the following advantages:

  • 2× lower CPU usage¹

  • 12× lower memory usage¹

  • 90× lower max latency

  • 10× higher max client connections

  • 4× less code!

¹ with a constant stream of queries.

The basic ideas behind this real-world asynchronous server have already been covered in the following F#.NET Journal articles:

Furthermore, the forthcoming .NET 4.5 will be the first to provide a fully asynchronous ADO.NET interface by adding a new ReadAsync method to read individual records from a database query asynchronously. This will make it possible to write fully asynchronous database code in .NET for the first time.

Drawing tree maps

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

"A tree map is a simple way to visualize the relative sizes of a collection of objects in 2D. The idea is to recursively subdivide a rectangle into non-overlapping rectangles that have areas proportional to the weights they represent..."

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

Monday, 31 October 2011

Mine sweeper in 99 lines of F# code


Tomas Petricek's excellent F# Snippets site is a gold mine of educational samples. This mine sweeper in 99 lines of code is no exception!


Thursday, 27 October 2011

Using SQL Server Compact Edition

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

"In addition to the heavy weight SQL Server 2008 and its free sibling SQL Express, Microsoft also offer a light-weight database called SQL Server Compact Edition (CE) that requires fewer resources and, in particular, can be run from a DLL and does not require installation or background services. This article walks through the use of the Northwind database from SQL Server CE including a WPF-based user interface built upon asynchronous message passing..."

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

Observables and Reactive Extensions

The F#.NET Journal just published an article about event-based programming:

"Various recent additions to the .NET Framework have encouraged event-based programming, including observables and the recent Reactive Extensions (Rx) library. This article reviews the basic properties of observables and some of the core functionality in the Rx library before taking a look at a common problem in event-based programming: subscribing to a state machine..."

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

Saturday, 17 September 2011

Using sockets from Silverlight

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

"Silverlight applications can communicate with remote servers via TCP sockets. This can be done without requiring elevated permissions (e.g. in browser) provided a client access policy server is running on the remote machine. This article describes how both the client- and server-side solutions to this problem can be written in F#..."

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

Wednesday, 14 September 2011

Concurrent change sets

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

"Many applications that perform a series of insertions and removals to and from a set can benefit from the ability to maintain the currently-outstanding added and removed elements such that an external replica of the changing set can be updated in batches on demand. Perhaps the most valuable application is to decouple the performance of a background worker from the user interface thread and vice versa. This article studies a a solution that uses an asynchronous agent sitting between the worker and visualizer that allows the worker to add and remove elements at high throughput while the visualizer concurrently fetches change sets with low latency..."

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

Monday, 29 August 2011

Symbol tables

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

"Computations such as graph traversals are often most naturally expressed in terms of raw data such as the strings names of the entities involved. This simplicity is valuable but comes at a cost in terms of performance because operations over strings from a finite set are substantially slower than operations over an equivalent representation. Symbol tables offer the ability to replace strings with ints in order to accelerate computations over them. This article looks at a typical example application that stands to benefit from the use of a symbol table and then demonstrates how a symbol table can be implemented along with an efficient specialized dictionary for keys that are symbols, culminating in a 14× performance improvement..."

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

Sunday, 21 August 2011

Caching

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

"Caches are ubiquitous in CPUs themselves but this article takes a look at the kinds of caches that are used in higher-level applications such as distributed web services. Caches with random eviction, round robin and least-recently used (LRU) schemes are examined..."

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

Sunday, 31 July 2011

Symbolic differentiation and matrix inversion

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

"Previous F#.NET Journal articles have covered manipulating symbolic expressions, computing derivatives and inverting matrices. This article combines these concepts in order to build a small computer algebra system capable of symbolically computing and simplifying the inverse of the Hessian matrix and grad of a given expression. This foundation is then used to minimize a symbolic expression to arbitrary-precision using rational arithmetic..."

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

Sunday, 10 July 2011

Live migration

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

"An interesting application of agent-based programming is the ability to implement virtual agents that are capable of running concrete server applications and then allow the servers to be migrated between agents seamlessly. This article describes the design and implementation of a simple program that demonstrates the effect by allowing a trivial server to be live migrated from one agent to another by instructing the agent to suspend the server, send the server's state to another agent and resume the server's execution at the remote location..."

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

Monday, 4 July 2011

Progressive F# tutorials

Skills Matter have announced that they will be hosting Progressive F# Tutorials at their London office in August. The event includes lectures from many big names in the F# world including Tomas Petricek, Phil Trelford, Zach Bray and Robert Pickering. Topics covered include testing, user interface (Silverlight and WPF), concurrent and asynchronous programming.


Saturday, 18 June 2011

Chat server

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

"Perhaps the simplest complete working example that can be constructed using the generic server architecture described in the previous articles is a chat server that allows clients to logon and communicate by posting messages that are relayed to all other logged-on clients. This article describes a chat server and clients with GUI interface for demonstration..."

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

Sunday, 12 June 2011

Generic server architecture

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

"Server applications often have very similar requirements in terms of their overall architecture. This article describes the design and implementation of a generic server that allows incoming messages to be validated per-connection, executed centrally, dispatched either to a specific connection or all connections and with all outgoing messages being filtered before they are returned to the client. The result is an elegant fully-asynchronous and generic library for server-side programming that is applicable to a wide variety of real server applications..."

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

Sunday, 22 May 2011

k-means clustering

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

"The k-means clustering algorithm is a simple form of machine learning that categorizes a set of data points into k clusters each centered around its own centroid. This article describes the design and implementation of the k-means clustering algorithm and an example application to a standard Iris flower data set including downloading and massaging the data directly from the web and visualizing the resulting clusters using WPF and the new charting and graphing functionality in .NET 4..."

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

Saturday, 7 May 2011

Allocationless programming on .NET

The F#.NET Journal just published another article about low-latency programming:

"An extreme technique used in some latency-critical applications is to completely circumvent the garbage collector by replacing all heap allocations with the use of pre-allocated arrays of value types, effectively implementing manual memory management inside a managed programming language. This might be called Fortran-style programming on .NET but the advantage is that stalls due to garbage collection can be made less frequent or even eliminated entirely..."

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

Sunday, 17 April 2011

Using MPI over Infiniband from F#

The F#.NET Journal just published another article about low-latency message passing:

"Infiniband is a high-throughput low-latency communication fabric commonly used in supercomputers. This article describes how a standalone F# application can use the Intel MPI 4 library via PInvoke to send and receive messages over an Infiniband connection between two separate machines with latencies as low as 7µs..."

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

Graph theory: Strongly-connected components

The F#.NET Journal just published another article about graph algorithms:

"One of the most important fundamental algorithms in graph theory is Tarjan et al.'s 1972 algorithm for computing the strongly-connected components in a graph in linear time. Strongly-connected components are subgraphs where at least one path exists from any vertex to any other vertex. This has many applications and, in particular, is the basis of many more advanced algorithms from graph theory. This article describes both imperative and purely functional implementations of this algorithm and a WPF-based GUI application that visualizes the strongly connected components of a randomly-generated graph..."

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

Saturday, 26 March 2011

Don't install VS2010 SP1

The new Service Pack 1 for Visual Studio 2010 is buggy and may cause irreparable corruption:

Installing this service pack destabilized one of our development machines and, more worryingly, attempting to uninstall the service pack produces the above warning that it may irreparably corrupt the Visual Studio 2010 installation.

We have no reason to believe that this is F# specific (there have been many complaints from non-F# users) but some of our customers have reported that it destabilised their systems too, both the development environment and programs containing F# source code.

Our F# implementation of Okasaki's purely functional real-time queue data structure started to suffer from MissingMethodExceptions after we installed SP1. Two of our clients are experiencing problems using F# with Silverlight only after having installed SP1.

Therefore, we are recommending that users avoid this Service Pack until the issues have been identified and resolved.


Wednesday, 23 March 2011

Game of Concentration

The F#.NET Journal just published another article about game programming:

"Concentration is a popular game where the objective is to remember previously-seen cards when flipping over pairs in order to find matching pairs and remove them from the game until none remain. This article describes the design and implementation of a WPF application that implements the game of Concentration. In particular, a novel design is adopted that uses an asynchronous agent to handle user interface timeouts elegantly and a set of mutually recursive asynchronous workflows that implement the state machine of the game logic..."

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

Sunday, 13 March 2011

Sliding averages

The F#.NET Journal just published another article about a semi-numerical algorithm:

"Sliding window algorithms are a class of algorithms that treat streams of data by computing a statistic across a window for each position of the window within the data stream. Moving averages are sliding window algorithms that compute an average over each window. This article begins with a simple implementation of the sliding mean average and goes on to examine more efficient algorithms for both mean and median sliding averages..."

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

Wednesday, 23 February 2011

Seminar: Multicore Programming on .NET

Parallel programming veteran Joe Hummel is giving a full-day seminar about multicore programming on .NET in San Francisco. Interestingly, F# is should be the programming language of choice for this presentation...

"This 1-day workshop will introduce parallel programming support in .NET 4, and move rapidly from concepts to concrete examples. Topics include the new task-oriented programming model, exploiting data & task parallelism in your applications, design patterns for exposing parallelism, Task Parallel Library (TPL), Parallel LINQ, new concurrent data structures for more efficient parallel access, and proper exception handling in the presence of parallelism. We’ll also discuss cutting-edge Visual Studio 2010 tools for debugging and profiling of parallel apps, as well as tool support from Microsoft Research. The workshop will be demo-rich, with complete source code provided."

Wednesday, 9 February 2011

Real-time ray tracing in Silverlight

The F#.NET Journal just published another article about Silverlight:

"Ray tracing is a simple but powerful approach to photorealistic rendering and implementing a ray tracer is an excellent way to learn a programming language and, in particular, to learn about graphics and optimization in the context of numerical algorithms. This article walks through the design and implementation of a basic ray tracer that visualizes a 3D scene in a Silverlight bitmap and exploits parallelism in order to attain the performance required for real-time animation..."

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

F# share of UK job market triples in four months

The IT Jobs Watch website hosts up-to-date statistics about the prevalence of different keywords in UK job adverts including those mentioning Microsoft's new F# programming language. Incredibly, the proportion of job adverts mentioning F# has tripled in just four months:

More job adverts now mention F# than any other functional programming language, including OCaml, Haskell and even Scala.


Wednesday, 2 February 2011

F# for Visualization in Silverlight

We have developed a version of our F# for Visualization library that uses Microsoft's Silverlight instead of Windows Presentation Foundation for a client to use at the E-world 2011 exhibition in Germany next week. This variant allows our charts and graphs to be rendered in web pages without sacrificing any functionality from the original library.

Here is a screenshot of a simple graph visualized in Internet Explorer using the Silverlight version of F# for Visualization:

Just like the WPF version, this visualization required just a single line of code:

PlotControl([Function sin], (-6.0, 6.0))

If anyone else is interested in F# for Visualization on Silverlight, please comment here or drop us an e-mail to let us know!


Sunday, 23 January 2011

Introduction to Silverlight

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

"Microsoft's Silverlight allows .NET programs to be run directly in a compliant browser and all major browsers can support Silverlight. This articles describes how self-contained interactive Silverlight programs can be written entirely in the comfort of the F# programming language an easily to deployed to any web server (not necessarily Windows based) as an easy and efficient way to bring dynamic content to a website..."

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

Gradient descent

One of the most popular questions we receive about the old book F# for Scientists is how the gradient descent example can be rewritten to work with the current version of F# in Visual Studio 2010 rather than the early prototype covered in the book, running under Visual Studio 2005.

We begin by referencing the F# PowerPack and its Compatibility extension:

> #r "FSharp.Powerpack.dll";; --> Referenced 'C:\Program Files\FSharpPowerPack-2.0.0.0\bin\FSharp.Powerpack.dll' > #r "FSharp.Powerpack.Compatibility.dll";; --> Referenced 'C:\Program Files\FSharpPowerPack-2.0.0.0\bin\FSharp.Powerpack.Compatibility.dll' > #nowarn "62";;

Next, we define a small number that we be used to calculate numerical approximations to derivatives:

> let δ = epsilon_float ** (1.0 / 3.0);; val δ : float = 6.055454452e-06

The following function repeatedly applies the given function to the given initial value until the result stops changing:

> let rec fixedPoint f x = let f_x = f x if f_x = x then x else fixedPoint f f_x;; val fixedPoint : ('a -> 'a) -> 'a -> 'a when 'a : equality

The numerical approximation to the grad of a scalar field is built up from partial derivatives in each direction:

> let partialD f_xs f (xs : vector) i xi = xs.[i] <- xi + δ try (f xs - f_xs) / δ finally xs.[i] <- xi;; val partialD : float -> (vector -> float) -> vector -> int -> float -> float

The following function performs a single iteration of gradient descent by scaling the step size λ by either α or β if the result increases or decreases the function being minimized, respectively:

> let descend α β f (f': _ -> vector) (λ, xs, f_xs) = let xs_2 = xs - λ * f' xs let f_xs_2 = f xs_2 if f_xs_2 >= f_xs then α * λ, xs, f_xs else β * λ, xs_2, f_xs_2;; val descend : float -> float -> (Vector<float> -> 'a) -> (Vector<float> -> vector) -> float * Vector<float> * 'a -> float * Vector<float> * 'a when 'a : comparison

Finally, the following function uses the gradient descent algorithm to minimize a given function and derivative:

> let gradientDescent f f' xs = let _, xs, _ = fixedPoint (descend 0.5 1.1 f f') (δ, xs, f xs) xs;; val gradientDescent : (Vector<float> -> 'a) -> (Vector<float> -> vector) -> Vector<float> -> Vector<float> when 'a : comparison

For example, the following computes a numerical approximation to the derivative of a function:

> let grad f xs = Vector.mapi (partialD (f xs) f xs) xs;; val grad : (vector -> float) -> vector -> vector

And the following defines the famous Rosenbrock "banana" function that is notoriously difficult to minimize due to its curvature around the minimum:

> let rosenbrock (xs: vector) = let x, y = xs.[0], xs.[1] pown (1.0 - x) 2 + 100.0 * pown (y - pown x 2) 2;; val rosenbrock : vector -> float

The minimum at (1, 1) may be found quickly and easily using the functions defined above as follows:

> let xs = vector[0.0; 0.0] |> gradientDescent rosenbrock (grad rosenbrock);; val xs : Vector<float> = vector [|0.9977180571; 0.99543389|]

For the latest in-depth coverage of the F# programming language, read Visual F# 2010 for Technical Computing.

Sunday, 16 January 2011

Testing: Behaviour-Driven Development with F#

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

"Of the many approaches taken to testing, Behaviour-Driven Development (BDD) is unusual in aiming to provide human-readable tests that can be used by non-technical people. The objective is to write the tests in a high-level language, as close to plain English as possible with data provided in the form of bullet-point lists or tables, that are interpreted by the machine in order to drive a production system and verify its behaviour. Naturally, F# is ideal in this situation because the challenge is essentially to implement an interpreter for a Domain Specific Language (DSL), the task that this family of languages were specifically bred for. This article walks through a complete sample including Gherkin parser, interpreter and harnesses for the NUnit testing framework and F# interactive..."

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

Sunday, 9 January 2011

Simple and efficient hand-written parsers

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

"In addition to the powerful code generation tools and libraries that assist with parsing, the ability to write simple and efficient parsers by hand can also be extremely useful. This article examines three different kinds of hand-written parsers ranging from very simple and extensible recursive-descent parsers to highly efficient bottom-up parsers..."

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

Monday, 3 January 2011

Patterns are everywhere!

When people first learn languages from the ML family, like F#, they often mistakenly assume that patterns appear only in match or function expressions. In fact, patterns also appear on the left-hand-side of let-bound definitions. This is why you can write:

let f(a, b) = a + b

The pattern is used to destructure a tuple. Specifically, a pair. But this is not just restricted to tuples. You can use that pattern to destructure much more. For example, the following destructures a pair of pairs:

let f((x1, y1), (x2, y2)) = x1 + x2, y1 + y2

Things start to get interesting when you pull in some of the more advanced pattern matching features in F#. For example, the following uses an or-pattern to select the value x is bound to depending upon the structure of the input:

let def (_, Some x | x, None) = x

This function takes a pair of values. The second value is of an option type. If that second value has the structure Some then its argument is the return value of the def function. Otherwise, the structure is None and the first argument is returned. Therefore, this def function mimics the behaviour of the built-in defaultArg function, returning the value conveyed by an optional type (if any) or a given default value otherwise.

Pattern matching is one of the enormously powerful features offered by the F# programming language. This feature and more are described in my new book Visual F# 2010 for Technical Computing.