Sector 0

I have been a software developer for more than 8 years now, and all this time I have been developing software in imperative languages like C++, Java and C#. During the years I have occasionally had a taste of functional programming in the language Haskell. The interest has never been big enough to do some real software development, but lately I have looked more into a couple of other functional programming languages, namely Erlang and F#.

What is functional programming

Functional programming is a different programming paradigm than what most programmers are used to. Programs written in imperative languages like C++, C# and Java are sequential programs, whereas programs written in a functional programming languages (FPL) is an expression, an is evaluated as such.

So in a FPL you write expressions, and in imperative languages you write methods. Code written in a FPL is more concise and easier to understand, and in short the benefits of using a FPL are listed here:

• More concise code, which means faster development time and fewer bugs.
• More comprehensible code, which again leads to fewer bugs and higher reliability.
• Immutable state, which leads to more reliable programs since writing multithreaded programs is easier without having to worry about shared state, locks and the problems that arise from this.

But don”t take my word for it. Try it yourself – I have listed a few links at the bottom of this post to some FPLs and articles. Also, you should read John Hughes article from The Computer Journal here: Why Functional Programming Matters.

An example

As an example I have written two small programs which calculates the number of primes between 2 and 9,999,999. The first one is written in C#:

static void Main(string[] args)
{
	int count = 0;
	for (int candidate = 2; candidate <= 9999999; candidate++)
		if (IsPrime(candidate))
			count++;
	Console.WriteLine(count);
}
 
private static bool IsPrime(int candidate)
{
	int max = ((int)Math.Sqrt(candidate)) + 1;
	for (int divisor = 2; divisor <= max; divisor++)
		if ((candidate % divisor) == 0)
			return false;
	return true;
}

and the second in F#:

#light
module PrimeCalculator
open System
 
let isPrime candidate =
    match candidate % 2=0 with
    | true ->   0
    | _ ->      let rec isDividable candidate divisor max =
                    match candidate with
                    | _ when divisor>max -> 1 //it is a prime
                    | _ when candidate % divisor=0 -> 0 //not a prime
                    | _ -> isDividable candidate (divisor+1) max
                isDividable candidate 2 ((int)(Math.Sqrt((float)candidate)))
 
let rec countPrimes n max count =
    match n>max with
    | true -> count
    | _ -> countPrimes (n+1) max (count+(isPrime n))
 
let primeCount = countPrimes 2 9999999 0
printfn "#primes = %d" primeCount

A much more succinct and readable version can be seen here. Notice however that this version does not perform as fast as the version above.

#light
 
let rec isPrime n divisor =
    match n with
    | _ when divisor>(int)(sqrt ((float)n)) -> true
    | _ -> if n%divisor=0 then false else isPrime n (divisor+1)
 
[2..9999999] |> List.filter (fun x -> isPrime x 2) |> List.length |> printfn "#primes = %d"

Since this is F#, and F# is a superset of OCaml, you can use object oriented programming mixed with your functional programming. But you can also use imperative programming mixed with either functional or object oriented code. The following code does the same as above, but uses imperative code to iterate through all possible prime candidates. This version is even slower, but much less RAM intensive.

I will get into the performance of the different coding styles in a later article, since this is obviously a major factor. This isn’t a surprise since F# is a functional programming language. More on that later.

#light
 
let rec isPrime n divisor =
    match n with
    | _ when divisor>(int)(sqrt ((float)n)) -> true
    | _ -> if n%divisor=0 then false else isPrime n (divisor+1)
 
let mutable count = 0
for x in 2..9999999 do
    if isPrime x 2 then count <- count+1
printfn "#primes = %d" count

Another example of how concise and expressive a FPL is, is this implementation of the quicksort algorithm written in Haskell:

qsort []     = []
qsort (x:xs) = qsort (filter (< x) xs) ++ [x] ++ qsort (filter (>= x) xs)

Erlang

One of the languages that I think will have a profound effect on the future of programming is Erlang. The reason I think that is, that it is the language for writing parallel, concurrent and distributed applications at the moment; it was designed with parallel and distributed computing in mind, as I wrote about in an earlier post.
In Erlang each thread (they call it a “process”) is extremely lightweight compared to a normal operating system thread: an Erlang process takes up 300 bytes of space (plus the state, of course), with the result that the scheduler can switch between them in no time. A typical Erlang system runs several thousand processes without any discernible performance penalty.

Another thing that distinguishes Erlang from most other functional programming languages (FPL) is how easy it is to learn. In contrast with some other FPL”s (and I have seen some really esoteric ones) it is simple and intuitive; It took me a few days of reading and writing to learn the basics of the language, how to spawn processes, and how to write distributed applications.

The only drawback of Erlang is its performance, which is quite poor compared to C# or other modern imperative languages. But it is only few types of applications that really need to keep the CPU(s) busy all the time – a lot of the time the CPUs are idle; a normal client- or server application that is constantly in the red is usually sick in one way or the other.

F#

F# (pronounced F-Sharp) is a relatively new programming language from Microsofts research department. It is a dialect of Objective Caml (OCaml), and you can in fact compile most OCaml code with the F# compiler and run it without any modifications. F# gives you all the benefits of a FPL, and a performance profile comparable to that of C#. I don”t mean to sound like a bad commercial, but the benefits are all too clear to me – in some applications performance is paramount.

Besides, in november 2007 Microsoft announced that it will move the language from research to the list of supported .NET programming languages.

What makes this language so important is that it is compiled and run on the normal .NET runtime, just like any other .NET language. First of all this gives us the benefit of using a virtual machine that has been tested and optimized through several years. Second of all – in line with the .NET “mantra” – F# gives programmers the ability to interface with other .NET languages and the huge framework behind the .NET runtime. And I don”t mean “interfacing” as in using some kind of language bridge. No, it is native: from F# programs you have access to the framework available to all other .NET languages, and from any other .NET language you can use components written in F#.
This gives programmers a big advantage when writing software. You can for example choose to write the user interface code in an imperative language like C#, and write the data processing code in F#, which is much more concise and intuitive when it comes to expressing algorithms and formulaes in code.

The ability to seamlessly combine two or more languages is the true strength of F#. I intend to explore that fact more when researching genetic programming, by utilizing my MPAPI framework to build parallel and distributed applications, with the core functionality developed in F#.

What do you think? Is this where we are heading in the future, is this where we should be heading, or is the various projects to parallelize (and further complicate) the languages as we know them the way to go? Try googling “parallel computing” on Google’s blog search and see what”s cooking in this interesting area.

Links

• F# homepage at Microsoft Research
• Open Erlang
• Haskell
• Objective Caml
• Why Functional Programming Matters
• F# Primer