Wednesday, 29 February 2012

Writing a CIL disassembler

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

"The .NET Framework provides powerful reflection capabilities oriented towards compiling run-time generated code to CIL from .NET languages such as F#. In essence, the System.Reflection.Emit namespace provides a programmatic CIL assembler. Relatively little support is provided for the inverse problem of disassembling bytecode back to CIL instructions although this can be very useful for instrumenting assemblies with new code to record code coverage, capture unit tests and measure performance characteristics and so forth. This article walks through the design and implementation of a tiny CIL disassembler that applies the reflection API to itself in order to obtain the required mappings from bytecodes to CIL instructions..."


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

Tuesday, 28 February 2012

Benefits of F#

The Visual F# programming language has a variety of technical benefits that can reduce development costs, reduce time-to-market and improve quality. This post enumerates some of these benefits in the context of different application domains.
Asynchronous servers: Metaprogramming (e.g. parsing): Technical computing: GUI applications: Logic programming: Testing: Performance:

Sunday, 26 February 2012

Vector Graphics Editor

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

"The combination of asynchronous workflows and union types with pattern matching make F# a powerful tool for GUI programming. This article examines the design and implementation of a simple vector graphics editor written in F# built around the concept of passing messages between the user interface thread and a background agent that implements the application logic..."


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

Bloom filter

A Bloom filter is a probabilistic alternative to a set. Membership in a bloom filter can be tested extremely quickly but only probabilistically, returning two values representing probable membership and definite non-membership.

The following class implements a purely functional Bloom filter in F#:
type BloomSet<'a when 'a: equality>(xs: seq<'a>) =
    let bits = System.Collections.BitArray(65536)
 
    let idx x n = (x >>> n) &&& 0xffff
 
    do
      for x in xs do
        let x = x.GetHashCode()
        bits.[idx x 0] <- true
        bits.[idx x 16] <- true
 
    member __.ProbablyContains(x: 'a) =
      let x = x.GetHashCode()
      bits.[idx x 0] && bits.[idx x 16];;
type BloomSet<'a when 'a : equality> =
  class
    new : xs:seq<'a> -> BloomSet<'a>
    member ProbablyContains : x:'a -> bool
  end
The constructor creates a Bloom filter from the given sequence of elements. The ProbablyContains function tests for probable membership.

For example, the following demonstrates how the proportion of false positives rises with the number of elements in the Bloom filter for our fixed size (64kb) internal array:
for n in [1000; 10000; 100000] do
    let rand = System.Random()
    let xs = set [for _ in 1..n -> rand.NextDouble()]
    let s = BloomSet xs
    let ys = set [0.0 .. 0.001 .. 1.0] - xs
    let count x = if s.ProbablyContains x then 1 else 0
    let pFail = float (Seq.sumBy count ys) / float ys.Count
    printfn "%0.2f%% false positives when n=%d" (100.0 * pFail) n;;
0.10% false positives
7.89% false positives when n=10000
82.02% false positives when n=100000
Just like sets, Bloom filters have many practical applications.

Sunday, 12 February 2012

The Very Concurrent Garbage Collector

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

"One of the most interesting research papers on garbage collection describes an unusual algorithm called the "Very Concurrent Garbage Collector" (VCGC) that manages to recycle unreachable heap blocks with only the occasional global synchronization with mutator threads in order to snapshot the global roots. This article walks through the design and implementation of VCGC in F#. Given that the subject of concurrent garbage collectors is notoriously difficult, this demonstrates how prototype solutions written in high-level languages like F# can help with correctness. Furthermore, the implementation adopts an allocationless programming style in order to leverage the benefits of this GC algorithm and we find that maximum pause times are over 100x shorter than with the default .NET 4 workstation GC and wall-clock performance is only slightly worse..."


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

Prototyping a mark-sweep garbage collector

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

"Garbage collectors can be notoriously difficult to write. Consequently, the availability of a working simulation can help greatly when trying to write a production-quality garbage collector. This article walks through the design and implementation of a prototype mark-sweep garbage collector. This not only demonstrates that it is possible to prototype low-level tools in F# but also serves as an educational example about garbage collection itself..."


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