F# News

Fast Generic Pretty Printing

2012-01-08T23:16:00.001Z

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

"The ability to convert values into legible strings efficiently, a process known as generic pretty printing, has a variety of uses including debugging and serialization. This article takes a look at the characteristics of the built-in pretty printer before considering alternatives including combinators and reflectors with a view to improving performance. Ultimately, a generic solution is proposed that runs 7,600× faster than the built-in F# solution on our test case..."

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

Rendering autostereograms

2011-12-17T19:27:00.001Z

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!

Metaprogramming: parsing with active patterns

2011-12-11T21:24:00.001Z

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!

Scalable servers with async F#

2011-11-05T14:06:00.005Z

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

2011-11-05T12:29:00.002Z

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!

Mine sweeper in 99 lines of F# code

2011-10-31T10:08:00.003Z

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!

Using SQL Server Compact Edition

2011-10-27T13:45:00.001Z

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

2011-10-27T13:41:00.002Z

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!

Using sockets from Silverlight

2011-09-17T19:35:00.001Z

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!

Concurrent change sets

2011-09-14T22:48:00.002Z

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!

Symbol tables

2011-08-29T14:09:00.003Z

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!

Caching

2011-08-21T21:42:00.001Z

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!

Symbolic differentiation and matrix inversion

2011-07-31T20:30:00.001Z

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!

Live migration

2011-07-10T09:00:00.001Z

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!

Progressive F# tutorials

2011-07-04T09:33:00.005Z

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.

Chat server

2011-06-18T20:50:00.001Z

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!

Generic server architecture

2011-06-12T11:19:00.003Z

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!

k-means clustering

2011-05-22T13:37:00.002Z

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!

Allocationless programming on .NET

2011-05-07T13:45:00.002Z

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!

Using MPI over Infiniband from F#

2011-04-17T22:56:00.002Z

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

2011-04-17T22:54:00.001Z

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!

Don't install VS2010 SP1

2011-03-26T14:53:00.005Z

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.

Game of Concentration

2011-03-23T23:28:00.002Z

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!

Sliding averages

2011-03-13T16:19:00.000Z

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!

Seminar: Multicore Programming on .NET

2011-02-23T16:15:00.004Z

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."

Real-time ray tracing in Silverlight

2011-02-09T22:39:00.001Z

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

2011-02-09T18:23:00.006Z

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.

F# for Visualization in Silverlight

2011-02-02T21:02:00.005Z

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!

Introduction to Silverlight

2011-01-23T23:25:00.001Z

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

2011-01-23T23:11:00.004Z

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.

Testing: Behaviour-Driven Development with F#

2011-01-16T21:52:00.001Z

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!

Simple and efficient hand-written parsers

2011-01-09T21:25:00.002Z

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!

Patterns are everywhere!

2011-01-03T14:32:00.004Z

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.

Performance-related features in F# and C#

2010-12-30T02:49:00.004Z

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).

Parsing mathematical expressions using active patterns

2010-12-14T09:20:00.002Z

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:

Most popular F# samples

2010-12-10T13:10:00.004Z

Here's a short-list of our most popular blog posts that describe example F# programs:

Numerical methods: matrix inversion

2010-12-05T15:29:00.001Z

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!

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

2010-11-30T09:59:00.001Z

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

"F# is like waterfowl..."

2010-11-30T09:29:00.003Z

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?

2010-11-30T09:24:00.002Z

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!

Checking for pangrams

2010-11-22T11:28:00.006Z

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 n^th-nearest neighbors in computational science (see the article Traversing networks: the n^th-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

Computational geometry: quick hull

2010-11-21T12:44:00.002Z

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!

Visualizing a complete graph

2010-11-14T18:09:00.005Z

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#!

Concurrent programming: TCP relay server

2010-11-10T21:18:00.001Z

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!

F# reaching a wider audience

2010-11-06T21:03:00.004Z

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

2010-11-06T17:32:00.002Z

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!

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

2010-10-27T17:17:00.011Z

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

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.

Graph algorithms: topological sort and all-pairs shortest paths

2010-10-19T12:31:00.001Z

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

2010-10-19T10:41:00.006Z

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())

Representing and searching graphs

2010-10-03T22:54:00.002Z

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!

Distributed message passing

2010-09-15T23:45:00.001Z

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

2010-09-15T23:44:00.004Z

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

Simulating predator-prey relationships

2010-09-12T12:32:00.002Z

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!

Draft F# Component Design Guidelines

2010-09-01T22:40:00.003Z

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!

Calculator

2010-08-29T23:56:00.002Z

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!

Don Syme lecturing at the F#unctional Londoners Meetup

2010-08-18T21:37:00.003Z

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.

Jon Harrop lectures on Parallel QR Decomposition

2010-08-07T01:00:00.002Z

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.

Data structures: heaps

2010-08-04T06:18:00.001Z

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!

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

2010-07-27T22:43:00.000Z

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!

Histogram equalization

2010-07-17T02:33:00.002Z

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!

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

2010-07-12T00:45:00.005Z

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!).

F# vs Mathematica: fast pricer for American options

2010-07-09T14:09:00.006Z

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.

F# vs Mathematica: parametric plots

2010-07-08T00:10:00.006Z

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.

F# vs Mathematica: red-black trees

2010-07-07T01:31:00.011Z

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.

Happy numbers

2010-07-05T08:58:00.004Z

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!

Lorenz attractor

2010-07-04T02:00:00.004Z

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

2010-07-04T01:36:00.002Z

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!

Diff

2010-07-02T14:28:00.001Z

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!

Expert F# 2.0

2010-06-29T23:27:00.002Z

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.

Parallelism in .NET 4 and Visual F# 2010

2010-06-19T15:26:00.004Z

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!

A dragon curve in 17 lines of F#

2010-06-06T18:53:00.005Z

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

2010-06-06T17:11:00.002Z

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!

Mini hash table

2010-05-25T02:18:00.003Z

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

Quicksort

2010-05-20T04:19:00.002Z

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!

Java vs F#

2010-05-14T03:16:00.009Z

Dr Cliff Click of Azul Systems, specialists in manycore JVM systems, recently published a blog post about the performance of Java compared primarily to C and C++ but also discussing C# and .NET. Three of Cliff's comments are of particular interest:

Under the heading "Places where C/C++ beats Java for obvious reasons":

"Value Types, such as a 'Complex' type require a full object in Java." - Dr Cliff Click

What Cliff forgot to mention is that .NET also provides value types and a far more compelling example than complex numbers is the humble hash table.

Consider the task of filling a hash table with 10,000,000 associations from integers to single-precision floating point numbers. This may be accomplished in Java as follows:

package hashtablebenchmark;

import java.util.HashMap;

public class Main {
    public static void main(String[] args) {
        int n = 10000000;

        for (int j=0; j<10; ++j) {
            long startTime = System.currentTimeMillis();
            HashMap hashtable = new HashMap(n);

            for(int i=1; i<=n; ++i) {
                hashtable.put(i, 1.0f / i);
            }

            System.out.println("m[100] = " + hashtable.get(100));
            long time = System.currentTimeMillis() - startTime;
            System.out.println("Took: " + time / 1e3 + "s");
        }
    }
}

The equivalent program in F# is not only shorter but also 17× faster:

let n = 10000000
let m = System.Collections.Generic.Dictionary(n)
for i=1 to n do
  m.[i] <- 1.0f / float32 i
printf "m[100] = %f\n" m.[100]

Specifically, Java takes 6.967s initially and 5.733s steady state whereas F# takes only 0.414s.

In fact, F# completes this benchmark so quickly that we would like to give it more work but Java cannot handle any more work without running out of memory on this 4Gb machine.

Elsewhere, Cliff also writes of Java:

"Very Good Multi-Threading Support. Parallel programming is just easier in Java." - Dr Cliff Click

and later:

"Not that I track C# all that closely but... I believe the JIT produces substantially slower code than Java" - Dr Cliff Click

Allow us to demonstrate the otherwise. The Computer Language Shootout contains a well-formed benchmark called spectral-norm for which the fastest Java solution is a 173-line parallel program. This implementation may be rewritten in only 24 lines of F#:

let A i j = 1.0 / float((i + j) * (i + j + 1) / 2 + i + 1)

let inline mul A (u: _ []) (v: _ []) =
  System.Threading.Tasks.Parallel.For(0, v.Length, fun i ->
    let mutable vi = 0.0
    for j = 0 to v.Length - 1 do
      vi <- vi + A i j * u.[j]
    v.[i] <- vi) |> ignore

let AtAu u v =
  let w = Array.create (Array.length u) 0.0
  mul (fun i j -> A i j) u w
  mul (fun i j -> A j i) w v

do
  let n = 5500
  let u, v = Array.create n 1.0, Array.create n 0.0
  for i = 0 to 9 do
    AtAu u v
    AtAu v u
  let u, v = vector u, vector v
  printf "%0.9f\n" (sqrt(Vector.dot u v / Vector.dot v v))

In the Java, dozens of lines of code were devoted to parallelism. In contrast, only two lines of code were altered to parallelize the F#. So it would seem that parallel programming is not "just easier in Java".

The the serial Java takes 12.722s initially and 12.299s steady state whereas F# takes only 12.18s from a cold start. On this 8-core 2xE5405 2.0GHz Xeon, the parallel Java takes 1.839s initially and 1.820s steady state whereas the parallel F# takes only 1.60s from a cold start. The fact that Java is slower in every single case indicates that the CLR's JIT is not "producing substantially slower code than Java".

Finally, Cliff made no mention of two other design deficiencies that cripple Java's performance. Firstly, their type erasure approach to generics incurs massive performance degradation for a lot of generic code because it leads to unnecessary boxing. Secondly, the JVM's lack of tail call elimination is not only a growing hindrance in the era of functional programming but the only general-purpose workaround, trampolines, is typically 10× slower that necessary.

If you want to learn how to write fast parallel programs in F#, read our book Visual F# 2010 for Technical Computing.

Parallelizing the SciMark2 benchmark: part 2

2010-05-06T01:27:00.001Z

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

"The SciMark2 benchmark is one of the better benchmarks for programming languages and their implementations in the context of technical computing. This article is the second in a two-part series revisiting the SciMark2 benchmark to examine the parallelization of each of its component tasks. Specifically, the Monte-Carlo, sparse matrix-vector multiplication and LU decomposition tests. The results are of general interest in the context of improving performance on multicores using parallel programming..."

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

Visual F# 2010 key binding cheat sheet

2010-04-19T23:31:00.002Z

Download your copy of Microsoft's official F# key bindings cheat sheet here.

"by moving to F# we reduced code size by nearly 75 percent"

2010-04-19T21:02:00.004Z

Grange Insurance of Columbus OH recently published a compelling case study regarding their use of Microsoft's new Visual F# 2010 programming language.

They cite clarity as a major advantage of F#:

"We liked that Visual F# is tailored to highly mathematical problems, helping programmers work more closely to the problem domain and enabling actuaries and other nonprogrammers to review the code as they would a math formula,"

and parallelism:

"We liked the .NET Parallel Extensions available through F# for managing parallelism automatically through the runtime system."

and integrated development environment and interoperability with existing technologies:

"We also liked that Visual F# is an integrated part of the Visual Studio tool set and the .NET Framework. That meant our programmers could use the same IDE and powerful .NET libraries they knew from having developed the earlier version of the solution in Visual C#."

For other F# success stories, read the freely available first article from The F#.NET Journal.

Visual F# 2010 for Technical Computing

2010-04-19T00:12:00.007Z

Following the ground-breaking product release of Visual F# by Microsoft as part of Visual Studio 2010, we have updated our F# for Technical Computing book to cover both F# 2.0 and .NET 4.

Visual F# 2010 for Technical Computing includes a variety of changes throughout the book, some affecting changes to the language and others affecting the use of libraries. The three most prominent changes are:

Chapter 10: Concurrent Programming now covers the final production-quality implementation of asynchronous workflows in the F# 2.0 language.
Chapter 11: Parallel Programming now replaces the TPL CTP with the constructs for shared-memory parallelism that have been integrated into .NET 4. Both the API and the performance characteristics have changed considerably.
Chapter 12: Performance has been completely revamped due to massive improvements in the F# compiler and the new garbage collector in .NET 4.

One particular surprise was the substantial difference in performance characteristics between Visual Studio 2010 and the F# prereleases. Several of the benchmarks covered in the book show 400% changes!

The A* algorithm

2010-04-15T19:42:00.001Z

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

"The A* algorithm is often used for route finding in game AI and is a generalization of Dijkstra's shortest-path algorithm from graph theory. This article describes two generic implementations of the A* algorithm written in F#. The first implementation is a simple prototype written in a purely functional style using data structures provided by F#. The second implementation uses mutable .NET collections to perform the same computation substantially more quickly. Finally, an example application is provided that finds a route across the Grand Canyon..."

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

Visual Studio 2010 with F# out now!

2010-04-14T13:31:00.005Z

MSDN subscribers can now download Visual Studio 2010 that provides the first fully-supported product release of the new F# programming language. Don Syme, the creator of F# at Microsoft Research Cambridge, posted an emotional blog article accompanying this release as it represents the culmination of 7 years of work.

We shall be updating all of our F#-related products to work with the new product release and, in particular, our F# for Numerics and F# for Visualization software libraries will now see their first product releases as well. Future articles in the F#.NET Journal will cover every aspect of Visual Studio 2010 in detail.

Note that there is no Visual F# Express edition and, at the time of writing, there is no user-friendly way to develop F# on .NET 4 for free. However, you can develop F# 2.0 on .NET 3 using Visual Studio 2008 or compile F# 2.0 for .NET 4 using the command-line compilers. Brian McNamara of the F# team has encouraged anyone wanting Visual F# Express to upvote this motion. Hopefully we will see another Visual Studio 2010 Shell with separate F# release that makes it easy to develop F# software with the latest libraries for free. The F# team are also committed to open source cross-platform development, to the extent that they are hiring a new contractor specifically to help with this.

Book review: F# for Scientists

2010-04-11T00:32:00.003Z

Our 2006 book F# for Scientists has received its ninth review on Amazon and, like all previous reviews, was given the maximum 5-star rating!

Andre M. Van Meulebrouck from California writes:

A hallmark of this book is conciseness. (The book itself is fairly small and thin; and nicely hardbound.)
This book is a gold mine of great information that could take years to fully digest!
While the book is titled as a scientific book, and it is that; it also has much more to offer. It should be of great interest to scientists, mathematicians, statisticians, computer scientists, financial programmers, and any programmers who want to write good code. It features a well balanced selection of topics including: algorithms, data structures, visualization, graphics, threading, performance, and optimization. The use of DirectX is demonstrated. Some compilation techniques are also shown.
A nice selection of recursive list algorithms are presented that showcase the kind of problem solving that can be done purely with recursion and list processing. These are classic idioms that are good to be exposed to; like power set, and substitution with replacement.
Many of the examples are very much in the spirit of the Scheme Revised Reports, wherein the most gutted possible examples are used to demonstrate a given primitive or concept. Nothing extraneous to cause distractions.
There is a complement to this book called "F# for Technical Computing" that can be purchased from Flying Frog Consultancy. The complementary book adds nicely to the material in "F# for Scientists"; with discussions on such topics as parallel computing and WPF. In addition, the complementary book features longer page sizes, a stay flat (music book style) binding, and color; all of which I really like. (I wish more technical books made use of color because code is much easier to read when you see comments in one color, keywords in another, etc..)
Both books are gems. There are also counterparts to these books for OCaml programmers.
Relevant software can also be obtained from the Flying Frog Consultancy (which has, as part of its logo: "Putting the fun in functional since 2005").

An e-mail client in F#

2010-04-03T02:25:00.002Z

The F#.NET Journal just published an article about the design and implementation of a complete GUI application:

"An e-mail client is an application that checks a remote mailbox for incoming messages and allows the user to send newly composed messages and replies to received messages. Incoming e-mails are typically read using the Post Office Protocol version 3 (POP3) which is a simple plain-text protocol implemented over TCP sockets. Outgoing e-mails are sent using the Simple Message Transfer Protocol (SMTP), an implementation of which is provided by the .NET framework. This article describes the design and implementation of an e-mail client that can be used for basic e-mail handling but, in particular, is easily programmed to perform tasks such as transaction processing automatically..."

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

.NET 4's improved tail call elimination

2010-03-18T22:09:00.003Z

Existing versions of the .NET Framework sometimes unnecessarily fail to eliminate tail calls. Grant Richins of Microsoft recently published a blog post explaining how this has been addressed in .NET 4. The improvements make it entirely feasible to write idiomatic pure and impure functional F# programs relying upon tail call elimination without having to worry about stack overflows.

Such changes in the very fabric of .NET also demonstrate just how committed Microsoft are to their new F# programming language.

New VS2010 release date

2010-03-18T22:03:00.002Z

Microsoft have updated the product page for Visual Studio 2010 (which includes F#!) with a new release date of 12th April 2010 under the "Buy" section.

24 days and counting!!!

Writing an article editor with Windows Presentation Foundation

2010-03-16T05:27:00.002Z

The F#.NET Journal just published an article about the design and implementation of a complete GUI application:

"This article describes the article editing tool we are creating to help automate the process of generating journal content. The editor provides a simple text editor where the author writes a form of markdown. The markdown is interactively parsed and pretty printed in a separate pane and the editor allows the result to be exported to HTML for inclusion in the journal. The application is based entirely upon Windows Presentation Foundation..."

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

F# vs Unmanaged C++ for parallel numerics

2010-03-10T00:30:00.003Z

We obtained a surprising performance result when comparing optimized parallel ray tracers written in F# and C++ recently. The following two programs render the same highly complex scenes containing over a million objects. Surprisingly, the 136-line managed F# program runs slightly faster at 17s than the 168-line unmanaged C++ which takes 18s.

Here is the F# program:

let t = System.Diagnostics.Stopwatch.StartNew()

let delta = sqrt epsilon_float

[<Struct>]
type vec =
  val x : float
  val y : float
  val z : float

  new(x, y, z) = {x=x; y=y; z=z}

  static member ( + ) (a : vec, b : vec) = new vec(a.x+b.x, a.y+b.y, a.z+b.z)
  static member ( - ) (a : vec, b : vec) = new vec(a.x-b.x, a.y-b.y, a.z-b.z)
  static member ( * ) (a, b : vec) = new vec(a*b.x, a*b.y, a*b.z)

let vec x y z = new vec(x, y, z)

let dot (a : vec) (b : vec) = a.x * b.x + a.y * b.y + a.z * b.z
let length r = sqrt(dot r r)
let unitise r = 1. / length r * r

type scene = Scene of vec * float * scene_type
and scene_type =
  | Sphere
  | Group of scene * scene * scene * scene * scene

let infinity = System.Double.PositiveInfinity

let inline ray_sphere (d : vec) (v : vec) r =
  let vx = v.x
  let vy = v.y
  let vz = v.z
  let disc = vx * vx + vy * vy + vz * vz - r * r
  if disc < 0. then infinity else
    let b = vx * d.x + vy * d.y + vz * d.z
    let b2 = b * b
    if b2 < disc then infinity else
      let disc = sqrt(b2 - disc)
      let t1 = b - disc in
      if t1 > 0. then t1 else b + disc

let ray_sphere' (o : vec) (d : vec) (c : vec) r =
  let vx = c.x - o.x
  let vy = c.y - o.y
  let vz = c.z - o.z
  let vv = vx * vx + vy * vy + vz * vz
  let b = vx * d.x + vy * d.y + vz * d.z
  let disc = b * b - vv + r * r
  disc >= 0. && b + sqrt disc >= 0.

type hit = {mutable l: float; mutable nx: float; mutable ny: float; mutable nz: float}

let intersect_sphere (dir: vec) hit l' (center: vec) =
    let x = l' * dir.x - center.x
    let y = l' * dir.y - center.y
    let z = l' * dir.z - center.z
    let il = 1. / sqrt(x * x + y * y + z * z)
    hit.l <- l'
    hit.nx <- il * x
    hit.ny <- il * y
    hit.nz <- il * z

let rec intersect dir hit = function
  | Scene(center, radius,typ) ->
      let l' = ray_sphere dir center radius
      if l' < hit.l then
          match typ with
          | Sphere ->
              intersect_sphere dir hit l' center
          | Group(a, b, c, d, e) ->
              intersect dir hit a
              intersect dir hit b
              intersect dir hit c
              intersect dir hit d
              intersect dir hit e

let rec intersect' orig dir = function
  | Scene(center, radius, typ) ->
      ray_sphere' orig dir center radius &&
      match typ with
      | Sphere -> true
      | Group (a, b, c, d, e) ->
          intersect' orig dir a ||
          intersect' orig dir b ||
          intersect' orig dir c ||
          intersect' orig dir d ||
          intersect' orig dir e

let neg_light = unitise(vec 1. 3. -2.)

let rec ray_trace dir scene =
  let hit = {l=infinity; nx=0.; ny=0.; nz=0.}
  intersect dir hit scene;
  if hit.l = infinity then 0. else
    let n = vec hit.nx hit.ny hit.nz in
    let g = dot n neg_light in
    if g < 0. then 0. else
      if intersect' (hit.l * dir + delta * n) neg_light scene then 0. else g

let fold5 f x a b c d e = f (f (f (f (f x a) b) c) d) e

let rec create level c r =
  let obj = Scene(c, r,Sphere)
  if level = 1 then obj else
    let a = 3. * r / sqrt 12.
    let rec bound (c, r) = function
      | Scene(c', r',Sphere) -> c, max r (length (c - c') + r')
      | Scene(_, _, Group(v, w, x, y, z)) -> fold5 bound (c, r) v w x y z
    let aux x' z' = create (level - 1) (c + vec x' a z') (0.5 * r)
    let w, x, y, z = aux a (-a), aux (-a) (-a), aux a a, aux (-a) a
    let c, r = fold5 bound (c + vec 0. r 0., 0.) obj w x y z in
    Scene(c, r, Group(obj, w, x, y, z))

let level, n = 11, 2048

let scene = create level (vec 0. -1. 4.) 1.
let ss = 4

do
  use ch = System.IO.File.Create("C:\Users\Jon\Documents\Visual Studio 10\Projects\F#\RayTracer\image.pgm", n * n + 32)
  sprintf "P5\n%d %d\n255\n" n n
  |> String.iter (ch.WriteByte << byte)
  let image = Array.create (n*n) 0uy
  System.Threading.Tasks.Parallel.For(0, n, fun y ->
    for x = 0 to n - 1 do
      let mutable g = 0.
      for dx = 0 to ss - 1 do
        for dy = 0 to ss - 1 do
          let aux x d = float x - 0.5 * float n + float d / float ss
          let dir = unitise(vec (aux x dx) (aux y dy) (float n))
          g <- g + ray_trace dir scene
      image.[x+y*n] <- 0.5 + 255. * g / float (ss*ss) |> byte)
  |> ignore
  ch.Write(image, 0, n*n)
  printf "Took %gs" t.Elapsed.TotalSeconds

And here is the C++ program:

#include "stdafx.h"
#include <vector>
#include <iostream>
#include <fstream>
#include <limits>
#include <cmath>

using namespace std;

numeric_limits<double> real;

double delta = sqrt(real.epsilon()), infinity = real.infinity();

struct Vec {
  double x, y, z;
  Vec(double x2, double y2, double z2) : x(x2), y(y2), z(z2) {}
};

Vec operator+(const Vec &a, const Vec &b)
{ return Vec(a.x+b.x, a.y+b.y, a.z+b.z); }

Vec operator-(const Vec &a, const Vec &b)
{ return Vec(a.x-b.x, a.y-b.y, a.z-b.z); }

Vec operator*(double a, const Vec &b) { return Vec(a*b.x, a*b.y, a*b.z); }

double dot(const Vec &a, const Vec &b) { return a.x*b.x + a.y*b.y + a.z*b.z; }

double length(const Vec &a) { return sqrt(dot(a, a)); }

Vec unitise(const Vec &a) { return (1 / sqrt(dot(a, a))) * a; }

struct Hit {
 double lambda;
  Vec normal;
  Hit() : lambda(infinity), normal(Vec(0, 0, 0)) {}
};

struct Sphere;

struct Scene {
  virtual ~Scene() {};
  virtual void intersect(Hit &, const Vec &) const = 0;
  virtual bool intersect(const Vec &, const Vec &) const = 0;
  virtual Sphere bound(Sphere b) const = 0;
};

struct Sphere : public Scene {
  Vec center;
  double radius;
  Sphere(Vec c, double r) : center(c), radius(r) {}
  ~Sphere() {}
  double ray_sphere(const Vec &dir) const {
    double b = center.x*dir.x + center.y*dir.y + center.z*dir.z;
    double disc = b*b - dot(center, center) + radius * radius;
    if (disc > 0) {
      double d = sqrt(disc), t2 = b + d;
      if (t2 > 0) {
  double t1 = b - d;
  return (t1 > 0 ? t1 : t2);
      }
    }
    return infinity;
  }
  bool sray_sphere(const Vec &orig, const Vec &dir) const {
    Vec v = center - orig;
    double b = dot(v, dir), disc = b*b - dot(v, v) + radius * radius;
    return (disc < 0 ? false : b + sqrt(disc) >= 0);
  }
  void intersect(Hit &hit, const Vec &dir) const {
    double lambda = ray_sphere(dir);
    if (lambda < hit.lambda) {
      hit.lambda = lambda;
      double
  nx = lambda*dir.x - center.x,
  ny = lambda*dir.y - center.y,
  nz = lambda*dir.z - center.z;
      double il = 1/sqrt(nx*nx + ny*ny + nz*nz);
      hit.normal.x = il*nx;
      hit.normal.y = il*ny;
      hit.normal.z = il*nz;
    }
  }
  bool intersect(const Vec &orig, const Vec &dir) const
  { return sray_sphere(orig, dir); }
  Sphere bound(Sphere b) const {
    return Sphere(b.center, max(b.radius, length(center - b.center) + radius));
  }
};

typedef vector<Scene *> Scenes;

struct Group : public Scene {
  Sphere b;
  Scenes child;
  Group(Sphere b, Scenes c) : b(b), child(c) {}
  ~Group() {
    for (Scenes::const_iterator it=child.begin(); it!=child.end(); ++it)
      delete *it;
  }
  void intersect(Hit &hit, const Vec &dir) const {
    if (b.ray_sphere(dir) < hit.lambda)
      for (Scenes::const_iterator it=child.begin(); it!=child.end(); ++it)
 (*it)->intersect(hit, dir);
  }
  bool intersect(const Vec &orig, const Vec &dir) const {
    if (!b.sray_sphere(orig, dir)) return false;
    for (Scenes::const_iterator it=child.begin(); it!=child.end(); ++it)
      if ((*it)->intersect(orig, dir)) return true;
    return false;
  }
  Sphere bound(Sphere b) const {
    Sphere b2 = b;
    for (Scenes::const_iterator it=child.begin(); it!=child.end(); ++it)
      b2 = (*it)->bound(b2);
    return b2;
  }
};

double ray_trace(const Vec &neg_light, const Vec &dir, const Scene &s) {
  Hit hit;
  s.intersect(hit, dir);
  if (hit.lambda == infinity) return 0;
  double g = dot(hit.normal, neg_light);
  if (g < 0) return 0.;
  Vec p = hit.lambda*dir + delta*hit.normal;
  return (s.intersect(p, neg_light) ? 0 : g);
}

Scene *create(int level, Vec c, double r) {
  Scene *s = new Sphere(c, r);
  if (level == 1) return s;
  Scenes child;
  child.reserve(5);
  child.push_back(s);
  double rn = 3*r/sqrt(12.);
  for (int dz=-1; dz<=1; dz+=2)
    for (int dx=-1; dx<=1; dx+=2)
      child.push_back(create(level-1, c + rn*Vec(dx, 1, dz), r/2));
  Sphere b2(c + Vec(0, r, 0), r);
  for (Scenes::const_iterator it=child.begin(); it!=child.end(); ++it)
    b2 = (*it)->bound(b2);
  return new Group(b2, child);
}

int _tmain(int argc, char* argv[]) {
  int level = (argc==3 ? atoi(argv[1]) : 11),
    n = (argc==3 ? atoi(argv[2]) : 2048), ss = 4;
  Vec neg_light = unitise(Vec(1, 3, -2));
  Scene *s(create(level, Vec(0, -1, 4), 1));
  ofstream out;
  std::vector<char> image(n*n);
  #pragma omp parallel for
  for (int y=0; y<n; ++y)
    for (int x=0; x<n; ++x) {
      double g=0;
      for (int dx=0; dx<ss; ++dx)
  for (int dy=0; dy<ss; ++dy) {
    Vec dir(unitise(Vec(x+dx*1./ss-n/2., y+dy*1./ss-n/2., n)));
    g += ray_trace(neg_light, dir, *s);
  }
      image[x+(n-1-y)*n] = .5 + 255. * g / (ss*ss);
    }
  out.open("C:\\Users\\Jon\\Documents\\image.pgm", std::ios_base::binary);
  out << "P5\n" << n << " " << n << "\n255\n";
  out.write(&image[0], n*n);
  return 0;
}

An introduction to asynchronous workflows

2010-03-02T05:41:00.001Z

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

"Asynchronous workflows were introduced into the F# programming language in 2007 and have recently matured pending the imminent release of the first officially-supported F# in Visual Studio 2010. This article describes the basic concepts that underpin this language feature and walks through some simple examples that demonstrate both basic and advanced use of this language feature..."

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