Sunday, 27 December 2009

Evolution: the weasel program

An interesting challenge is called Evolutionary Algorithm and draws upon a famous computer simulation written by Richard Dawkins to demonstrate the power of random variation and non-random cumulative selection in natural and artificial evolutionary systems, and how this process differs from chance.

The program begins with a random string of letters and spawns a generation of 200 random mutations of the parent string, selects the fittest mutation (by similarity to an "ideal" string) and uses that individual to spawn the next generation. The ideal string used is "METHINKS IT IS LIKE A WEASEL".

The results of this program clearly demonstrates how selection can drive random processes to solve problems extremely efficiently: only 6 generations were required to reproduce the ideal string exactly. In fact, randomized algorithms are of great practical importance and a similar technique, simulated annealing, is used as an example in our F# for Technical Computing book.

Our F# solution is as follows:

let target = "METHINKS IT IS LIKE A WEASEL"
let charset = "ABCDEFGHIJKLMNOPQRSTUVWXYZ "
 
let rand = System.Random()
 
let fitness (trial: string) =
  Seq.zip target trial
  |> Seq.fold (fun d (c1, c2) -> if c1=c2 then d+1 else d) 0
 
let mutate parent rate _ =
  String.mapi (fun _ c ->
    if rand.NextDouble() < rate then c else
      charset.[rand.Next charset.Length]) parent
 
do
  let mutable parent =
    String.init target.Length (fun _ ->
      charset.[rand.Next charset.Length] |> string)
  let mutable i = 0
  while parent <> target do
    let pfit = fitness parent
    let best, f =
      Seq.init 200 (mutate parent (float pfit / float target.Length))
      |> Seq.map (fun s -> (s, fitness s))
      |> Seq.append [parent, pfit]
      |> Seq.maxBy (fun (_, f) -> f)
    if i % 100 = 0 then
      printf "%5d - '%s'  (fitness:%2d)\n" i parent f
    parent <- best
    i <- i + 1
  printf "%5d - '%s'\n" i parent

This program produces the following output:

    0 - 'CEUMIDXSIXOOTSEHHXVMD IHTFWP'  (fitness: 6)
  100 - 'PEPHIZLB NGSIO LCWE AQEKCSZQ'  (fitness:11)
  200 - 'MESHIZHB IQ IO LTWGGAQWMKSRX'  (fitness:13)
  300 - 'MESHIZHB IQ IO LTWGGAQWMKSRX'  (fitness:13)
  400 - 'METHIVKS ITLIN LYKJPABWDASEU'  (fitness:19)
  500 - 'METHINKS IT IB LIKEFA WDASEL'  (fitness:25)
  518 - 'METHINKS IT IS LIKE A WEASEL'

F# examples on Rosetta Code

Rosetta Code is a wonderful community-driven wiki containing examples of dozens of programming tasks written in dozens of languages.

Naturally, we couldn't resist the challenge to solve many of these tasks in F# and we shall be publicizing our results here and even developing some into full-blown F#.NET Journal articles.

Perhaps the most surprising result is that the F# solutions are extremely concise even when compared with bleeding-edge research languages such as Haskell. For example, the Haskell solution to the Data Munging 2 problem is:

type Date = String
type Value = Double
type Flag = Int
type Record = (Date, [(Value,Flag)])
 
duplicatedDates :: [Record] -> [Date]
duplicatedDates [] = []
duplicatedDates [_] = []
duplicatedDates (a:b:tl)
    | sameDate a b = date a : duplicatedDates tl
    | otherwise    = duplicatedDates (b:tl)
    where sameDate a b = date a == date b
          date = fst
 
numGoodRecords :: [Record] -> Int
numGoodRecords = length . filter recordOk
    where recordOk :: Record -> Bool
          recordOk (_,record) = sumOk == 24
              where sumOk = length $ filter isOk record
                    isOk (_,v) = v >= 1
 
parseLine :: String -> Record
parseLine line = (date, records')
    where (date:records) = words line
          records' = mapRecords records
 
          mapRecords :: [String] -> [(Value,Flag)]
          mapRecords [] = []
          mapRecords [_] = error "invalid data"
          mapRecords (value:flag:tail) =
              (read value, read flag) : mapRecords tail
 
main :: IO ()
main = do
  contents <- readFile "readings.txt"
  let inputs = map parseLine $ lines contents
  putStrLn $ show (length inputs) ++ " total lines"
  putStrLn "duplicated dates:"
  mapM_ putStrLn $ duplicatedDates inputs
  putStrLn $ "number of good records: " ++ show (numGoodRecords inputs)

whereas our F# solution is simply:

let dates = HashSet(HashIdentity.Structural)
let mutable ok = 0
 
do
  for line in System.IO.File.ReadAllLines @"readings.txt" do
    match String.split [' '; '\t'] line with
    | [] -> ()
    | date::xys ->
        if dates.Contains date then
          printf "Date %s is duplicated\n" date
        else
          dates.Add date
        let f (b, t) h = not b, if b then int h::t else t
        let _, states = Seq.fold f (false, []) xys
        if Seq.forall (fun s -> s >= 1) states then
          ok <- ok + 1
  printf "%d records were ok\n" ok

This really highlights the dramatic step forward that F# represents, not only improving upon the previous generation of mainstream programming languages but even leaping beyond research.

Tuesday, 22 December 2009

Zach Cox' word count challenge

Zach Cox published an interesting challenge on his blog recently: to traverse a directory hierarchy of files and compute the total distribution of word frequencies. Here is a simple F# solution:

open System.IO

let rec words_of_dir dir =
  seq { for dir in Directory.GetDirectories dir do
          yield! words_of_dir dir
        for file in Directory.GetFiles dir do
          use reader = new StreamReader(File.OpenRead file)
          while not reader.EndOfStream do
            yield! reader.ReadLine() |> String.split [' '; '.'; ':'; ';'; '?'] }

do
  @"C:\Users\Jon\Downloads\20_newsgroups"
  |> words_of_dir
  |> Seq.countBy id
  |> Seq.sortBy (fun (_, n) -> -n)
  |> printf "%A\n"

Taking only 17.5s at only 14 lines of code, this F# combines the brevity of the most concise solution (Ruby) with the performance of the fastest solution (Scala).

Monday, 21 December 2009

Trending F# jobs in the UK

As a pioneering functional programming language on the world's favorite platform, F# is set to explode onto the job scene following its first major release as part of Visual Studio 2010 on 22nd March 2010.

The ITJobsWatch website is everyone's first stop for analysing trends in the UK job market and, interestingly, their statistics for the F# language indicate that the number of F# jobs is over 4× higher than the same period last year and the average salary has risen to £70k or €79k or US$112k:

This is the fastest growth in demand and salary of any functional programming language! Extrapolating the current trends, demand for F# programmers will be higher than for C++ programmers in 2012!

Suffice to say, the demand and salary of F# programmers in the UK will be a trend to watch over the next couple of years.

Wednesday, 16 December 2009

Generating and visualizing 2D mazes

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

"Maze generation is a remarkably complex and diverse subject that essentially falls into the category of network or graph theory but is most often seen in the context of games and puzzles. The characteristics that make a maze interesting for humans to try to navigate are subjective and not easily defined and, consequently, the design and implementation of an automatic maze generator is as much an art as it is a science. This article describes the design and implementation of a simple but effective maze generation algorithm including WPF-based visualization. The algorithm is elegantly expressed in terms of recursive functions and purely functional data structures..."

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

Parsing and visualizing binary Geographic Information System data

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

"Detailed vector descriptions of worldwide geographical data are freely available in the Shapefile format. This article describes how polygonal data can be parsed from the binary Shapefile format and visualized using Windows Presentation Foundation easily and efficiently using F#. The result is a simple program that draws a map of the world and can be used as the basis for a wide variety of Geographic Information System (GIS) applications from cartography to climatology..."

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

Tuesday, 8 December 2009

Book review: F# for Scientists

James Litsios has kindly published the eighth review of our book F# for Scientists on Amazon and, like every other review, gave the book the highest possible rating of 5/5 stars and described the book as "An excellent book that presents a broad set of examples of use of F#".

We also recently published the F# for Technical Computing book that covers Windows Presentation Foundation, the Task Parallel Library and Message Passing Interface (MPI) for parallel programming, asynchronous workflows for concurrent programming, LINQ for XML, named and optional arguments, standard .NET interfaces for interoperability and dozens of other exciting new features.

Monday, 16 November 2009

Logic programming: n-queens and knight's tour problems

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

"Logic programming is a paradigm often seen in problem solving and AI. This article introduces the subject of logic programming and explains why the F# language is ideally suited to these kinds of applications, using the familiar examples of solving the n-queens problem and finding a knights tour. Moreover, the differences between the .NET implementation and those bred specifically for this style of programming is described and techniques that can be used to close the performance gap are discussed..."

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

Friday, 6 November 2009

F# for Visualization 0.4.0.2 released

A new release of our F# for Visualization library is now available to beta release subscribers. This release is designed to work with the new October 2009 CTP release of F#.

Parallelizing the SciMark2 benchmark: part 1

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 first in a series revisiting the SciMark2 benchmark to examine the potential for parallelizing each of its components. Specifically, the Fast Fourier Transform (FFT) and Successive Over-Relaxation (SOR) tasks are covered in this article. 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!

Low-lock algorithms

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

"Locks are the defacto-standard approach to concurrent programming. With locks, shared mutable resources are protected using mutual exclusion to ensure consistency of the shared state from the point of view of different threads. However, locks are slow and, consequently, many situations can benefit from the avoidance of locks in favor of lower-level solutions. Much research has gone into non-blocking (obstruction-free, lock-free and wait-free) algorithms. This article introduces the concepts that underpin the implementation of non-blocking algorithms, including the .NET memory model, and explains how this can be leveraged to avoid locks with the simple example of lazy evaluation..."

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

Thursday, 29 October 2009

F# for Numerics 0.2.0.4 released

A new version of F# for Numerics has been released that works with the new F# 1.9.7.8 October 2009 CTP release. Beta subscribers may download this new release at no extra charge here.

Monday, 19 October 2009

New F# release and roadmap

The October 2009 CTP release of F# (aka beta 2) is now available here. Microsoft have also announced an official release date for Visual Studio 2010 of 22nd March 2010.

Our F# for Numerics and F# for Visualization products will be updated to work with the latest F# beta release at no extra charge for our beta subscribers, as always.

Tuesday, 6 October 2009

FFT demo from the F#.NET Journal

The F#.NET Journal just made another downloadable demo freely available. This demo is from the article Visualizing the Fourier Transform (30th September 2009).

The article develops and explains the entire program which, including parallelized 2D FFT implementation and real-time WPF-based visualization, is under 150 lines of F# code!

Sunday, 4 October 2009

Visualizing the Fourier Transform

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

"The Fourier transform is one of the most important numerical methods and underpins most forms of spectral analysis. This article describes a simple image compression technique that uses the Fast Fourier Transform (FFT) to remove the high-frequency components of an image. The 2D FFT is efficiently parallelized and the resulting application provides a WPF GUI allowing the user to control the accuracy of the approximation..."

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

F# for Technical Computing out now!

Our new book F# for Technical Computing has been published and is now available for order!

This is currently the only published book to cover the latest version of the F# programming language and also covers the following exciting topics:

  • Windows Presentation Foundation for interactive 2D and 3D graphics.
  • The Task Parallel Library for shared-memory parallel programming on multicores and MPI for distributed parallelism on clusters.
  • LINQ for the dissection of XML data.
  • Sequence expressions.
  • Asynchronous workflows for concurrent programming.
  • Functional design patterns (tail calls, untying the recursive knot and continuation passing style).
  • Purely functional data structures (balanced trees, tries, lazy streams and queues).
  • Named and optional arguments.
  • .NET interfaces including IEnumerable, IComparable and IDisposable.
  • Performance in the context of caches and multicores.
  • Reflection.

Every graph in the book was created with our own F# for Visualization library and the complete source code including code to interactively generate all of the graphs is provided as a Visual Studio 2008 project when you buy F# for Technical Computing!

Sunday, 20 September 2009

Huffman data compression

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

"Data compression algorithms are not only very useful in practice but are also extremely compelling pragmatic examples of programming theory. The popular Huffman data compression algorithm is from the family of entropy encoding compression algorithms. This article walks through the construction of a simple array-based Huffman compressor and decompressor written entirely in F# before converting the functions to handle sequences on-demand in order to provide incremental compression and decompression..."

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

Saturday, 12 September 2009

F# for Technical Computing book now available for preorder

Our new F# for Technical Computing book is nearing completion and is now available for preorder.

This full-color book covers the latest May 2009 CTP version of F# with all of its new features including sequence expressions and asynchronous workflows as well as all of the latest libraries and tools including Windows Presentation Foundation (WPF) for visualization, the Task Parallel Library (TPL) for easy parallelism, LINQ for XML processing, F# for Numerics and F# for Visualization for interactive technical computing. New topics covered include laziness, purely functional data structures, parallel programming, concurrent programming and regular expressions.

Order F# for Technical Computing today and a copy will be sent to you when the book is published (before the end of September).

Friday, 4 September 2009

Traversing networks: the nth-nearest neighbor

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

"Graph theory has a great many practical applications ranging from compiler internals to the study of the structural characteristics of materials. This article describes the design and implementation of a program that finds the nth-nearest neighbors of a given vertex in an infinite graph. This problem is of interest in the context of atomic structures..."

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

Tuesday, 18 August 2009

Dynamic programming: Levenshtein edit distance

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

"Levenshtein distance is a metric used to measure the amount of difference between a pair of sequences in terms of the number of insertions, deletions and substitutions required to get from one sequence to the other. Computing the Levenshtein distance is an interesting problem in dynamic programming with many practical applications including spell checkers and the study of DNA in bioinformatics. This article describes how the basic algorithm may be implemented and then optimized, including the use of both generic and specialized memoization..."

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

Advantages of Pattern Matching

Following the May 2009 CTP release of F#, this new programming language is finally starting to gain some serious traction. However, many people trying to learn about the advantages and disadvantages of F# are being misled by much of the oversimplified journalistic material being made available. We shall endeavour to address this by releasing short articles in the form of blog posts that augment the common information with valuable insights.

Perhaps the most common misconception is that functional programming is the primary advantage of the F# programming language over alternatives like C#. This is misleading for two main reasons. Firstly, the latest C# 3.0 version provides extensive support for funtional programming including lambda functions and the .NET 3.5 framework is already taking advantage of this with the System.Func and System.Action generic delegates. Secondly, the F# programming language provides a wealth of other valuable features that are as advantageous as functional programming but which are not found in any other mainstream programming languages. Pattern matching over variant types is one such feature.

Grouping code by function rather than class lets you use pattern matching, which is far more powerful and efficient than alternatives such as method dispatch in object-oriented programming:

  • Pattern matches can act upon ints, floats, strings and other types as well as objects. Method dispatch requires an object.
  • Pattern matches can act upon several different values simultaneously: parallel pattern matching. Method dispatch is limited to the single this case in mainstream languages.
  • Patterns can be nested, allowing dispatch over trees of arbitrary depth. Method dispatch is limited to the non-nested case.
  • Or-patterns allow subpatterns to be shared. Method dispatch only allows sharing when methods are from classes that happen to share a base class. Otherwise you must manually factor out the commonality into a separate member (giving it a name) and then manually insert calls from all appropriate places to this superfluous function.
  • Pattern matching provides exhaustiveness and redundancy checking which catches many errors and is particularly useful when types evolve during development. Object orientation provides exhaustiveness checking (interface implementations must implement all members) but not redundancy checking.
  • Non-trivial parallel pattern matches are optimized for you by the F# compiler. Method dispatch does not convey enough information to the compiler's optimizer so comparable performance can only be achieved in other mainstream languages by painstakingly optimizing the decision tree by hand, resulting in unmaintainable code.
  • Active patterns allow you to inject custom dispatch semantics.

Interestingly, although F# is one of the world's first production-quality functional programming language implementations, it still provides features like or-patterns and active patterns that are not available in other academic functional languages such as Haskell.

You can learn all about pattern matching in F# from the F#.NET Journal article "How to Leverage Pattern Matching" (16th April 2007).

Tuesday, 4 August 2009

Optimizing the Burrows-Wheeler Transform

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

"The Burrows-Wheeler Transform (BWT) is one of the few preconditioners used in data compression and, in particular, is the core of the popular bzip2 compression utility. This article describes a simple 12-line implementation of the BWT in F# and progressively optimizes the implementation to use a customized quicksort then shared-memory parallelism. On 8 cores, the final optimized implementation is over 1,000× faster than the original..."

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

Thursday, 16 July 2009

Traveling Salesman demo from The F#.NET Journal

The F#.NET Journal just made another downloadable demo freely available. This demo is from the article Solving the Traveling Salesman problem using Simulated Annealing (31st December 2008).

The article develops and explains the entire program which, including optimization algorithm and real-time WPF-based visualization, is under 170 lines of F# code!

2D Scalable Vector Graphics with XNA: part 1

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

"Vector graphics represent images in terms of lines and curves on a fictional canvas. This resolution-independent representation is ideal for high resolution output devices such as printers but the inevitable march of technology has ossified vector graphics on the desktop as a fundamental component of both Apple's and Microsoft's latest graphical user interfaces. Vector graphics are best represented as trees and manipulated using recursion. Consequently, F# is an extremely powerful tool for writing programs that manipulate vector graphics. This article describes the design and implementation of a simple library for 2D vector graphics written in F# and using XNA for visualization. This would be ideal for games that include 2D graphics with lots of zooming..."

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

Saturday, 11 July 2009

Fluid Dynamics demo from the F#.NET Journal

The F#.NET Journal just made another downloadable demo freely available. This demo is from the article Simulating smoke in real-time using fluid dynamics (16th January 2008).

The article develops and explains the entire program which, including parallelized numerical code and WPF-based visualization, is only 175 lines of F# code!


Tuesday, 7 July 2009

Ray Tracer demo from The F#.NET Journal

The F#.NET Journal just made another downloadable demo freely available. This demo is from the article Implementing a simple Ray Tracer (16th January 2008).

The article develops and explains the entire program which, including ray intersection routines, visualization, parallelization and GUI controls, is only 160 lines of F# code!

Monday, 6 July 2009

F# development with Visual Studio 2008

The F#.NET Journal just published an article about the current integrated development environment for F#:

"The May 2009 Community Technology Preview (CTP) release of F# includes an advanced Visual Studio mode for F# development. This article describes how this may be installed (including the free version of Visual Studio) and used to evaluate F# code interactively and develop F# applications including the generation of standalone .NET executables suitable for redistribution and the static linking of other .NET assemblies (e.g. C# compiled to DLL) as well as new features in the development environment itself..."

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

F# for Visualization 0.4.0.1 released

A minor bug fix release of F# for Visualization is now available.

Wednesday, 17 June 2009

Least squares: a case study in optimization

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

"The challenge of finding the least squares best fit of a linear sum of functions is a common problem in regression. Linear algebra provides a powerful and general solution by expressing this problem in terms of matrices and then computing the QR decomposition in order to solve the matrix equation. This article describes a remarkably simple implementation of QR decomposition in F# before developing progressively more optimized implementations using the guidance of performance profiles and without sacrificing generality. In particular, heavy use of the F# keyword "inline" is made in order to express efficient reusable numerical methods..."

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

Friday, 12 June 2009

F# for Numerics 0.2.0.2 released

A new version of our F# for Numerics library for F# has been released. This version includes:

  • Eigenvalues and eigenvectors of real symmetric matrices (the LinearAlgebra.Float.symmetric_eigen and LinearAlgebra.Float32.symmetric_eigen functions).
  • Singular Value Decomposition of real matrices (the LinearAlgebra.Float.svd and LinearAlgebra.Float32.svd functions).
  • Complex Cholesky decomposition of positive definite Hermitian matrices (the LinearAlgebra.Complex.cholesky function).
  • Real and complex Log Gamma function (the Special.gammaln and Special.Complex.gammaln functions).
  • Real and complex Beta function (the Special.beta and Special.Complex.beta functions).

The HTML documentation for this product is freely available on-line.

Wednesday, 10 June 2009

F# for Visualization 0.4.0.0 released

F# for Visualization version 0.4.0.0 has just been released. This version includes a variety of enhancements.

Perhaps the most important enhancement is the introduction of dynamically typed functions scene and Typeset.math which try to build vector scenes and typeset mathematical layouts, respectively, from values of any type. The View function can be used to visualize any value of any type. For example, the following defines and then visualizes a matrix of rational numbers:

> let A =
    Matrix.Generic.of_seq
      [ for i in 0N..4N ->
          [ for j in 0N..4N ->
              1N / (i + j + 1N) ] ];;
val A : Matrix<BigNum> = matrix [[1N; 1/2N; 1/3N; 1/4N; 1/5N]
                                 [1/2N; 1/3N; 1/4N; 1/5N; 1/6N]
                                 [1/3N; 1/4N; 1/5N; 1/6N; 1/7N]
                                 [1/4N; 1/5N; 1/6N; 1/7N; 1/8N]
                                 [1/5N; 1/6N; 1/7N; 1/8N; 1/9N]]
> View A;;

This makes it a lot easier to see what is going on during matrix computations!

Plots may now be augmented with an "epilog". For example, the following creates a graph of the sinc function:

let g = Plot([Function sinc], (-12., 12.), (-0.3, 1.1))

Accurately typeset axis labels may be added to create a professional-quality plot:

g.Labels <- (Char 'x', Row[Text "sinc"; math "(x)"])

Finally, the first positive root of this function may be highlighted by adding a single data point and a label describing the exact coordinate:

let pi = System.Math.PI
g.Data <- [Function sinc; Data[pi, 0.]]
g.Epilog <- Label(scene(Row[math "("; Greek.pi; math ", 0)"]),
                  0.003, Point(System.Math.PI, 0.), Vector(1.2, 1.2))

Axis and grid styles and the font sizes of ticks are now configurable.

Finally, the DLL is 30% smaller than before!

Monday, 1 June 2009

Sudoku Solver demo from the F#.NET Journal

The F#.NET Journal just made another downloadable demo freely available. This demo is from the article Designing and implementing a Sudoku Solver (30th June 2007).

The entire program, developed and explained in the article, including logic solver and programmatic GUI is under 150 lines of F# code!

Visualizing linear algebra: Singular Value Decomposition

The F#.NET Journal just published an article about the interactive visualization of linear algebra:

"Singular Value Decomposition (SVD) is an important algorithm from linear algebra that decomposes a matrix into the product of three simpler matrices. The resulting decomposition has several applications. This article describes the design and implementation of an F# program that computes the SVD of an image and uses it to create a lossy compression algorithm with controllable quality. This involves numerical methods for computing the eigenvalues of real symmetric matrices and interactive visualization of the result as a standalone Windows Presentation Foundation application that uses the Task Parallel Library to leverage multicores..."

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

A self-contained executable demo of the program developed in this article is freely available.

Tuesday, 26 May 2009

Downloadable demos from the F#.NET Journal

Articles published in the F#.NET Journal often culminate in fun graphical programs. Consequently, we have begun the process of uploading demos that everyone can download and enjoy. The first such demo, from the article Real-time Finite Element Materials simulation (15th June 2008), is now freely available for download from the F#.NET Journal web page.

This demo simulates a simple 2D material using finite element methods and the flexible object can be grabbed and pulled with the mouse in order to deform and even smash it:

The entire self-contained F# program is under 200 lines of code and uses Windows Presentation Foundation for easy and efficient real-time visualization.

Friday, 22 May 2009

F# for Numerics 0.1.0.1 and F# for Visualization 0.3.2.2

We have completed the updates of our F# for Numerics and F# for Visualization libraries to work with the latest F# May 2009 CTP (1.9.6.16) and the results are now available to our beta release scheme subscribers.

Although the latest version of F# contains many improvements and breaking changes, the updates turned out to be relatively straightforward and the resulting libraries passed all tests first time. Congratulations to the F# team for such a polished release! We recommend that all users upgrade to the latest F# for a better development experience.

Thursday, 21 May 2009

Pythagoras Tree

A Pythagoras tree is a simple vector graphics image:

The following F# program uses the F# for Visualization library to render this image:

#light

open System.Windows.Media
open FlyingFrog.Graphics

let pi = System.Math.PI

let rotate t = RotateTransform(t / pi * 180.).Value

let branches m =
[ m * rotate(pi/2. - asin(4. / 5.)) * scale(4. / 5., 4. / 5.) *
translate(0., 1.);
m * translate(-1., 0.) * rotate(-pi/2. + asin(3. / 5.)) *
scale(3. / 5., 3. / 5.) * translate(1., 1.) ]

let line_loop xys = Contour.Closed [ for x, y in xys -> line_to x y ]

let square = line_loop [1., 0.; 1., 1.; 0., 1.; 0., 0.]

let shape brush m =
Shape([ Interior brush;
Stroke(Brushes.DarkGreen, { width = 0.01 }) ],
[ Contour.map (fun p -> p * m) square ])

let trunks brush ms = Group(List.map (shape brush) ms)

let rec tree n ms =
if n=0 then [trunks Brushes.Green ms] else
let ms' = List.collect branches ms
trunks Brushes.BurlyWood ms :: tree (n-1) ms'

do
let view = View(Group[])
for n = 1 to 12 do
view.Scene <- Group(tree n [Matrix.Identity])
Run()

Download and run the demo!.

F# 1.9.6.16 released

Don Syme has announced the release of a new version of F# that replaces the old F# September 2008 CTP. This new release brings F# much more into alignment with the rest of .NET 4, in preparation for the first full product release of F# in Visual Studio 2010. The release is available either as part of the latest Visual Studio 2010 beta or as a separate F# May 2009 CTP that works with Visual Studio 2008.

Many of the improvements in the new version of F# are breaking changes that require existing software to be updated, such as the renaming of basic functions. For example, the List.fold_right function from OCaml has been renamed List.foldBack. We are in the process of bringing our F# for Visualization and F# for Numerics libraries up to date with respect to the latest F# CTP. Our forthcoming book F# for Technical Computing will not only cover the latest version of F# but also all of the latest library versions and new techniques for integration and interoperability.

F# for Numerics 0.1.0.0 released

F# for Numerics 0.1.0.0 has just been released. This includes a wealth of new features and improvements such as:

  • Numerical integration.
  • Bessel functions.
  • Skewness and kurtosis.
  • Series: natural numbers, Fibonacci, primes.
  • Seeding of Mersenne Twister with a uint32.
  • Constants: epsilon_float32 and delta32.

Subscribe to our beta release scheme today!

Wednesday, 20 May 2009

F# for Visualization 0.3.2.1 released

F# for Visualization 0.3.2.1 has just been released. This includes bug fixes, performance improvements and new examples.

Purely functional data structures: real-time queues and catenable lists

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

"This is the second article in a series describing the design and implementation of some purely functional data structures. Real-time queues and catenable lists that provide reliable O(1) time complexity operations are described in detail. In particular, laziness is used to ensure that operations are performed efficiently even when the data structures are used persistently. This culminates in the creation of some useful new data structure implementations...."

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

Monday, 11 May 2009

Nice F# screencast by Jason Olson

Jason Olson has done a great beginners introduction to F# in the form of a video of him walking the viewer through F# using an interactive session.

In particular, Jason explains many of the basic features of the F# language that surprise beginners who have never seen an interactive statically-typed functional programming language before. This is recommended viewing for anyone struggling with basic features like patterns and curried functions.

Thursday, 7 May 2009

F# as a next-generation platform for high-performance interactive technical computing

We are now in the throws of writing a new book on F# called F# for Technical Computing that is due out in a few months. Amongst other things, we are generating diagrams for the book using our own F# for Visualization library and making extensive use of our F# for Numerics library and Microsoft's excellent Parallel Extensions to .NET Framework 3.5 June 2008 CTP in order to build a next-generation platform for high-performance interactive technical computing.

The following screenshot shows the real-time visualization of performance measurements over the array, list and set data structure implementations provided with the F# September 2008 CTP:



There are several interesting aspects to this F# program:

  • Individual benchmarks for a given data structure are executed in parallel in order to obtain results faster without artificially degrading the measurements for other data structures via GC load.
  • The parallelism is so effective that 90% CPU usage is sustained across all 8 cores.
  • Parallel threads update the visualizations concurrently in real time safe in the knowledge that F# for Visualization handles all thread-related issues automatically and efficiently.
  • The randomized algorithms in the benchmarks are fuelled by the high-performance Mersenne Twister implementation in our F# for Numerics library.
  • The entire program is under 80 lines of code.
  • The resulting high-fidelity diagrams are ideal for inclusion in quality printed literature such as our full-color books.

Here is the entire source code:

open FlyingFrog
open FlyingFrog.Graphics
open FlyingFrog.Graphics.Typeset
let log2 x =
log x / log 2.0
let plot_mem =
Plot([], (0., 20.), (-25., 0.0),
Labels=(Char 'n', Sub(Char 't', Text "mem")))
let plot_mem_rel =
Plot([], (0., 20.), (0., 20.0),
Labels=(Char 'n', Fraction(Sub(Char 't', Text "set"), Sub(Char 't', Text "array"))))
let plot_iter =
Plot([], (0., 20.), (-30., -20.0),
Labels=(Char 'n', Sub(Char 't', Text "iter")))
let plot_foldl =
Plot([], (0., 20.), (-30., -20.0),
Labels=(Char 'n', Sub(Char 't', Text "foldl")))
let plot_foldr =
Plot([], (0., 20.), (-30., -20.0),
Labels=(Char 'n', Sub(Char 't', Text "foldr")))
let tss =
[for plot in 1 .. 4 ->
[for i in 1 .. 3 ->
[for i in 0 .. 101 -> float i, infinity]]]
let iters = 4001
let inline time f n m =
let rand = Random.MersenneTwister()
let t = System.Diagnostics.Stopwatch.StartNew()
let mutable j = 0
while t.ElapsedMilliseconds < 100L do
for k=0 to j do
f (abs(rand.int()) % n) m
j <- j + 1 float t.ElapsedMilliseconds / 1e3 / float j
let inline run d f mem iter foldl foldr =
System.Threading.Parallel.For(0, iters, fun i' ->
let i = iters * i' % 101
let n = 2. ** (float i / 100. * 20.) > int
let m = f n
let t' = time mem n m > log2
if snd tss.[0].[d].[i] > t' then
tss.[0].[d].[i] <- log2(float n), t'
for f, tss in [iter, tss.[1]; foldl, tss.[2]; foldr, tss.[3]] do
let t' = (time f n m / float n) > log2
if snd tss.[d].[i] > t' then
tss.[d].[i] <- log2(float n), t'
if i' % 100 = 0 then
plot_mem.Data <- [for ts in tss.[0] -> Data ts]
plot_mem_rel.Data <-
[Data(Array.map2 (fun (i, ts) (_, ta) -> i, 2. ** ts / 2. ** ta)
tss.[0].[0] tss.[0].[2])]
plot_iter.Data <- [for ts in tss.[1] -> Data ts]
plot_foldl.Data <- [for ts in tss.[2] -> Data ts]
plot_foldr.Data <- [for ts in tss.[3] -> Data ts]
)
let inline array_mem x (a: _ array) =
let rec aux i =
i < Array.length a && (a.[i] = x aux(i+1))
aux 0
do
run 2 (fun n -> Array.init n (fun i -> float i))
(fun n m -> ignore(array_mem (float n) m))
(fun n m -> Array.iter ignore m)
(fun n m -> Array.fold_left ( + ) 0.0 m > ignore)
(fun n m -> Array.fold_right ( + ) m 0.0 > ignore)
run 0 (fun n -> set (seq {for i in 0 .. n-1 -> float i}))
(fun n m -> ignore(Set.mem (float n) m))
(fun n m -> Set.iter ignore m)
(fun n m -> Set.fold_left ( + ) 0.0 m > ignore)
(fun n m -> Set.fold_right ( + ) m 0.0 > ignore)
run 1 (fun n -> [for i in 0 .. n-1 -> float i])
(fun n m -> ignore(list_mem (float n) m))
(fun n m -> List.iter ignore m)
(fun n m -> List.fold_left ( + ) 0.0 m > ignore)
(fun n m -> List.fold_right ( + ) m 0.0 > ignore)
Run()
 

Monday, 4 May 2009

Re: Microsoft canning F#

We went to Cambridge to meet Don Syme last week and attended a great lecture by Tom Wickham-Jones from Wolfram Research. I spoke to Don about the concerns among some of our customers regarding the future of F# and he assured me that they are focused entirely on forthcoming releases with a schedule that spans years. The next release, beta 1, is due out this month and a beta 2 is scheduled for release before the full 2010 release next year.


Purely functional data structures: streams and batched queues

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

"This article is the first in a series describing the design and implementation of some very useful purely functional data structures. Lazy evaluation, lazy streams and batched queues are described in detail. In particular, new .NET interfaces, classes and objects are used factor the implementations of the data structures and various built-in interfaces are implemented in order to support equality, comparison and hashing of these new data structures...."

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

Sunday, 19 April 2009

Massive savings on F# for Visualization and F# for Numerics

We just slashed the price of source code licenses for our F# for Visualization and F# for Numerics libraries.

F# for Visualization augments F# with graphing and visualization capabilities that can be used directly from F# interactive sessions running in Visual Studio itself, as well as WPF Controls that can be used in your own standalone programs. Plot 2D functions and 3D functions, 3D objects and embed the visualization capabilities in your own programs with our reusable Windows Presentation Foundation controls. Read the full documentation here.

F# for Numerics provides a wide variety of invaluable numerical methods with elegant F# interfaces that allow you to solve numerical problems quickly and easily from the comfort of F#, both interactively and in your own standalone programs. Read the full documentation here.

Thursday, 16 April 2009

Lempel-Ziv-Welch data compression

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

"LZW is a simple and effective dictionary-based data compression algorithm originally published in 1984 and subsequently used in several prominent places including the GIF image format. This article describes simple purely-functional implementations of the compression and corresponding decompression algorithms before examining the translation and optimization of these algorithms into longer but more efficient imperative equivalents. In particular, F#'s sequence expressions are used extensively to create on-the-fly compressors and decompressors ideal for stream processing...."

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

Wednesday, 8 April 2009

Book review: F# for Scientists

Mike Hadlow, a freelance .NET developer from Brighton England, recently wrote a review of our book F# for Scientists:

"I read most of F# for Scientists by Dr Jon Harrop over the Christmas holidays. Now, don’t be put of by the title, it’s a really wonderful little book. I’m no scientist, my undergraduate degree was a general social science pick and mix affair, but I found most of it straightforward. I had to skip some of the complex mathematics but that didn’t seem to hurt my appreciation of programming principles being discussed.

It’s really nice to find a small programming book. Far too many assume too little intelligence from the reader and waffle at length on trivial subjects. It doesn’t help that the IT profession seems to value its books by the killogram. Dr Harrop doesn’t suffer from either of these traits and is happy to introduce difficult subjects in a concise and direct style. Now that means that I sometimes had to spend a while on each page to make sure I understood it, but that’s far better than reading page after page of whatever for dummies.

If I’ve taken anything from this book, it’s a much better understanding of currying. I talked about it a while back when discussing an excellent presentation of functional C# by Oliver Sturm, but at that time I hadn’t understood how central it was to understanding F#..."

Thanks Mike!

Don't forget we are drawing upon the expertise we gained from the feedback about F# for Scientists in our forthcoming book F# for Technical Computing that will cover all of the latest libraries including parallel and concurrent programming the F# way.


Tuesday, 31 March 2009

Aperiodic tilings

The F#.NET Journal just published an article about the generation and visualization of tilings using F#:

"Many sets of polygons can be used to tile an infinite 2D plane. The term "aperiodic tilings" is used informally to refer to tilings that are not periodic. Such tilings are not only of mathematical and scientific interest because they give rise to unexpected diffraction patterns when they appear in quasicrystalline materials but also because they are often beautiful and, consequently, have been used in ornamental decorations for centuries. This article describes a simple program that visualizes tilings using Windows Presentation Foundation where the tilings are described using generic rewrite rules implemented in terms of a .NET interface...."

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

Sunday, 29 March 2009

Retraining? Consider F#...

I was just chatting with a friend who is a Microsoft certified trainer and he mentioned that the recession has boosted their turnover significantly as many people are earning new qualifications to in order to prepare themselves for today's highly-competitive hi-tech job market.

Employers have been quick to recognise that bleeding-edge programming languages like F# are an excellent way for them to identify the most motivated and intelligent applicants for a wide range of programming-related jobs.

So why not put F# at the top of your list of languages to learn in 2009?

Here are some resources to help you get started:


Monday, 16 March 2009

Units of measure

The F#.NET Journal just published an article about an exciting new feature in F#:

"The F# programming language is the first mainstream language in the world to offer statically type checked units of measure. This advanced feature is easy to use and checks the dimensional consistency of programs that manipulate physical quantities. This article introduces units of measure in the F# programming language with the basic constructs, the built-in measures provided with F#, several worked examples of units of measure in action and, finally, a discussion of the caveats of this exciting new language feature..."

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

Tuesday, 10 March 2009

New book: F# for Technical Computing

We have started work on a completely new book about the F# programming language called F# for Technical Computing. This new full-color book builds upon our OCaml for Scientists book and our F#.NET Journal articles and will cover the latest version of F# with all of its new features including sequence expressions and asynchronous workflows as well as all of the latest libraries and tools including Windows Presentation Foundation (WPF) for visualization, the Task Parallel Library (TPL) for easy parallelism, LINQ for XML processing, F# for Numerics and F# for Visualization for interactive technical computing.

F# for Technical Computing is scheduled to be published by Flying Frog Consultancy Ltd. in September 2009.

Sunday, 1 March 2009

Working with Regular Expressions

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

"Regular expressions are a domain-specific language for pattern matching over sequences of characters. This functionality provides a concise and efficient way to dissect strings and, consequently, is used in many forms of string processing including the definition of lexers. This article describes how .NET's support for regular expressions can be used to manpulate strings easily and efficiently from the F# programming language..."

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

A free article, but which one?

To celebrate the 50th article anniversary of The F#.NET Journal in two months time we would like to give one of our existing articles away for free but we don't know which article you freeloaders want the most. So please leave a comment here stating which article you would most like to read.

All of the articles currently available to subscribers are enumerated on The F#.NET Journal web page.

Tuesday, 17 February 2009

Low-level optimization tips and tricks: part 2

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

"The F# programming language is a fantastic tool for technical computing because it combines easy interactive high-level programming with excellent performance and multicore capability. This makes it feasible to solve a wide variety of problems without having to drop to low-level languages like C for performance. This article describes garbage collection friendliness, data structure specialization, efficient loops and the use of structs to avoid boxing..."

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

Sunday, 8 February 2009

F# for Scientists source code: chapter 4

The source code from chapter 4 Numerical Analysis of our book F# for Scientists is now available from the book's web page.

This chapter covers number representations, algebraic properties, interpolation, numerically-robust solutions of a quadratic and variance calculation as well as arbitrary- and adaptive-precision numerics.

Wednesday, 4 February 2009

Emergent behaviour: flocking boids

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

"Artificial life became a popular topic in the 1980s. In particular, with the discovery that simple rules defining the behaviour of individuals could give rise to sophisticated behaviour of groups of individuals. This unexpected result was described as "emergent behaviour" and one of the most famous examples was a computer program called "Boids" that used only three simple rules to govern the dynamics of individuals but produced remarkably realistic flocking behaviour of the population as a whole. This article describes an interactive boids simulator with a graphical user interface implemented using Windows Presentation Foundation..."

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

Monday, 26 January 2009

Free article: Introduction to F#

We have updated the freely-available first article from The F#.NET Journal. The article now includes a brief history of F#, enumerates many of the advantages of F# and cites some existing industrial applications of F# before describing how you can get the latest version of F# from Microsoft's new F# home page and how you can get developing F# for free using Visual Studio 2008 Shell.

Now that we are approaching 50 articles in the database, totalling almost 130,000 words, we have also decided to release another one of our existing articles for free. Please comment here and let us know which of our articles you would most like to see!


Wednesday, 21 January 2009

Book review: F# for Scientists

James O'Brien has kindly written a review of our book F# for Scientists:

"Excellent from first to last. Whilst the extensive science-oriented examples will benefit F#'s current market - efficient scientific and financial computing - the clarity of writing will benefit all programmers approaching F# for the first time.

Newcomers will not find another dry description of the programming language but rather an exploration of the ideas and principles of functional programming that will benefit their technique in whatever language they use. This is most brilliantly illustrated by the visualization chapter and by the sections dealing with XML processing in which functional techniques are used to produce solutions far more succinct, yet still more expressive, than their imperative or object-oriented cousins.

The material is challenging - it is intended to be - but persevering will bring far greater rewards than ploughing through the latest O'Reilly cookbook. Learning functional programming will improve the skills of every programmer, and so will reading this book."

And don't forget about our more recent book F# for Technical Computing.

Sunday, 18 January 2009

Simulating smoke in real-time using fluid dynamics

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

"In scientific computing, the task of simulating fluid flow accurately by solving the Navier-Stokes equation is notoriously difficult. However, it is possible to compute numerical approximations quickly enough that fluids dynamics may be simulated in real time. This article describes a simple fluid dynamics simulator that uses Microsoft's Task Parallel Library (TPL) to parallelize the computationally intensive operations and uses Windows Presentation Foundation to visualize the results in real time..."

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

Friday, 16 January 2009

Forthcoming book: Programming F#

Microsoft's F# team member Chris Smith has announced that he has been writing a new book Programming F# for O'Reilly that is scheduled for publication later this year.

This book joins "F# in a Nutshell" by Ted Neward and Amanda Laucher and "Real World Functional Programming with examples in F# and C#" by Tomas Petricek as the other hotly-anticipated books covering F# that are due to be published in 2009.

Microsoft's new F# home page lists the three existing F# books, F# for Scientists by Jon Harrop, Foundations of F# by Robert Pickering and Expert F# by Don Syme, on their Learn F# page.


Monday, 12 January 2009

F# for Visualization 0.3.2.0

A new release of our F# for Visualization product is now available to beta subscribers. Version 0.3.2.0 introduces two new features:

  • 2D scatter plots.
  • Multiple plots: functions and data on the same graph.

Demos of these new features will be made available on our site over the next few days.