Abstract

This article is a short tutorial on how to write extensible recursive
descent parsers with no mutable state using monads in F#. The parsers
that are build using the techniques described here are able to accept
ambiguous grammars, and have arbitrary lenght lookahead. These LL(*)
(Parr 2007) parsers are not limited to any finite number of lookaheads.
Although this potentially reduces performance in comparison to machine
generated bottom-up parsers, the techniques described in this article
will make simpler and more elegant parsers. Also the parsers eliminate
the need for lexical analysis (tokenization) which is done on the
fly.

Parser Type

We start by defining the signature of our parser functions. The type
signature is:

  type Parser<'r> = Parser of (char list -> ('r*char list) list)

That is, a parser is a function that takes a list of characters and
produces a list of tuples. The tuple consists of the result and the
- usually updated – character list that is the remainder of the input
to be parsed. Putting these result tuples in a list enables us to
accept ambiguous grammars.

A parser function also needs to be applied so we define a partial
function for that:

  let parse (Parser p) = p

Monadic Bind Combinators

The monadic bind combinator >>= will run
a parser and apply those results (remember that a parser returns a
list of results) to the next parser. The combinator takes a parser
and a function that, given a result, returns a new parser. The result
of applying the second parser to the list of results is a list of
lists of results, and these lists will be concatenated before returning:

  let (>>=) p f = Parser(fun cs ->
    List.concat [for (r,cs') in parse p cs -> parse (f r) cs'])

A parser is typically of the general format:

  parser1 >>= fun r1 ->
  parser2 >>= fun r2 ->
  ...
  parsern >>= fun rn ->
  mreturn (s r1 r2 ... rn)

where s is a semantic function that is applied to the results
of the parsers.

We might not be interested in the result of a parser but only in the
fact that it succeeded. So instead of writing

  parser1 >>= fun _ ->
  parser2 >>= fun _ ->
  ...

we simply want to discard the result right away and write:

  parser1 >>
  parser2 >>
  ...

The combinator >> can be expressed in
terms of >>=:

  let (>>) p q = p >>= fun _ -> q

Fundamental Parsers

In order to construct more complex parsers and combinators, both general
and specific to a grammar, we define a few basic parsers. The first
simply injects a value into a result without consuming any input characters:

  let mreturn r = Parser(fun cs -> [(r,cs)])

The next is a parser that returns an empty result, often denoted λ,
Λ or ϵ:

  let lambda = Parser(fun _ -> [])

Next is the item parser. This parser consumes a single character
unconditionally:

  let item = Parser(fun cs ->
    match cs with [] -> [] | c::cs' -> [(c,cs')])

Using these fundamental parser we can define two other fundamental
parser. The first is the conditional parser:

  let sat cond =
    item >>= fun c -> if cond c then mreturn c else lambda

which takes the first character and applies a conditional function
to it. If the condition evaluates to true the character is
returned, otherwise an empty result is returned.

The char parser consumes a character if and only if the character
matches:

  let char c = sat ((=)c)

and the digit parser consumes a character if and only if
the character is in the range [0..9]:

  let digit = sat (fun c ->
    (List.tryFind ((=)c) ['0'..'9']).IsSome)

The alpha parser acts like digit:

  let alpha = sat (fun c ->
    (List.tryFind ((=)c)(List.append
      ['a'..'z'] ['A'..'Z'])).IsSome)

Choice Combinators

Often we need to be able to make a choice between two or more different
parsers. The choice combinator does just that:

  let (<|>) p q = Parser(fun cs ->
    match parse p cs with
    | [] -> parse q cs
    | rs -> rs)

The choice combinator takes two arguments p and q,
both of which are parsers. It first applies the first parser. If it
succeeds then that result is returned- If the result is an empty list
it means it failed, and q is parsed. Note that q
might also fail.

There is another and equally important choice combinator: the ambiguous
choice combinator. It appends the result of each parser to each other
and returns that as a result. If one or the other parser fails with
[] the result is that from the other parser.

  let (++) p q = Parser(fun cs ->
    List.append (parse p cs) (parse q cs))

Recursive Combinators

The Kleene* and Kleene (0-or-many and 1-or-many
repetitions of a parser, respectively) combinators are expressed in
terms of each other:

  let rec many0 p = many1 p <|> mreturn []
  and many1 p = p >>= fun r -> many0 p >>= fun rs -> mreturn (r::rs)

Sometimes it is necessary to check that not only a single character
but an entire string can be parsed, for example when parsing keywords:

  let rec symbol cs =
    match cs with
    | [] -> mreturn []
    | c::cs' -> char c >> symbol cs' >> mreturn cs

Ambiguous Choice and LL(*)

The ++ combinator is important since it lets us parse ambiguous
grammars. Suppose we have the simple grammar:

Our first attempt at writing a parser looks like this:

  let rec expr =
    number >>= fun n ->
    char ';' >>
    mreturn n
  and number = integer <|> dec
  and integer =
    many1 digit >>= fun digits ->
    mreturn <apply sematic function on digits>
  and dec =
    many1 digit >>= fun digits ->
    char '.' >>
    many0 digit >>= fun decimals ->
    mreturn <apply sematic function on nums and decimals>

At first glance it looks fine. We expect to parse a number followed
by a semicolon and nothing more in this example. But what happens
if we try to parse the string “123.4;”? The number
parser returns an integer. The rest of expr fails since it
expects a semicolon but finds a period.

If we substitute the use of <|> with ++ the result
is different:

  ...
  and number = integer ++ dec
  ...

The ++ combinator applies both parsers and return [(123,['.';'4';';']);(123.4,[';'])]
as a result. The >>= combinator takes
this list of results and applies the next parser (here char
'.'...) on both. Since the next character after 123 is not
. this is discarded and only 123.4 is usable.

This simple example demonstrates the ability to write parsers with
arbitrary length lookahead without having to explicitly implement
a lookahead parser.

Other Useful Parsers and Functions

A few string helper functions might come in handy since a string and
a character list are not the same thing in F#. We therefore use the
unary functions

  // convert a string to a list of characters
  let (~&) (str:string) = str.ToCharArray() |> List.ofArray
  // convert a list of characters to a string
  let (~%) (chars:char list) = new String(Array.ofList chars)

There are other combinators that are quite useful:

• Parse a series of parser p separated by a parser sep
  and return the list of results from parsing p. For example,
  parsing the string aba or abababa:

    let sepBy p sep =
      p >>= fun r ->
      many0 (sep >> p) >>= fun rs ->
      mreturn (r::rs)
• Parse p followed by another parser e:

    let endBy p e =
      p >>= fun r ->
      e >>
      mreturn r
• Parse a new line and an end-of-line. Note that "rn"
  is a newline on win32 systems.

    let newline = symbol &"\r\n"
    let endofline = many0 (char ' ') >> newline >> many0 (char ' ')
• Parse any number (\geqq1) of spaces, here defined as either '
  ' or 't':

    let space = many1 (char ' ' <|> char '\t')
• Either parse the parser p or nothing. In grammar terms it is
  expressed as p – Λ and is the equivalent
  of 0 or 1 successful applications of p.

    let orLambda p = (p >>= fun v -> mreturn [v]) <|> mreturn []

Of course, it is possible to construct any number of parsers and combinators
given the ones already mentioned here. It all depends on the particular
needs when implementing a parser for any given grammar, and this tutorial
is by no means exhaustive.

Error Messages

Parsers that either return a successful result or nothing at all are
not particular useful; we need to be able to combine error messages
and send them back up the chain so they can be displayed to the programmer.

We would like to be able to write an error message like “Error
at line x, column y. Unexpected end-of-file. Expected ‘.’, ‘;’ or
‘n”‘. To do this we extend our parser definition
thus:

  type Parser<'r> = Parser of (char list ->
    (('r*char list) list*string list*string*int))

That is, a parser is a function that takes a list of characters and
returns a tuple with 4 values. Their meanings are:

• ('r*char list) list : the result of the parsing. An empty
  list if the parser fails.
• string list : a list of strings of what the parser expected
  when it failed.
• string : a description of the unexpected, for example
  “end-of-file” or “‘;’“.
• int : a pointer to where the error is. Here we use the number
  of characters not parsed yet. This number can easily be converted
  to line- and column number in the original input.

The monadic bind combinator must still run a parser and apply the
results to the next parser. Results will still be concatenated. Each
result list is followed by a list of strings describing what the parser
expected, and these must likewise be concatenated. The bind combinator
looks like this:

  let (>>=) p f = Parser(fun cs ->
    match parse p cs with
    | ([],exs,unex,pos) -> ([],exs,unex,pos)
    | (rs,_,_,_) ->
      List.map (fun (r,cs') -> parse (f r) cs') rs
      |> List.fold (fun (rs,exs,_,_) (rs',exs',unex,pos) ->
      (List.append rs' rs,List.append exs' exs,unex,pos))
        ([],[],"",len cs))

The >> combinator is the same as before.

The choice operators also needs to handle the new parser type:

  let (++) p q = Parser(fun cs ->
    let (prs,pexs,punex,ppos) = parse p cs
    let (qrs,qexs,qunex,qpos) = parse q cs
    (  List.append prs qrs,
      List.append pexs qexs,
      (if ppos<qpos then punex else qunex),
      min ppos qpos))

  let (<|>) p q = Parser(fun cs ->
    match parse p cs with
    | ([],exs,_,_) ->
      let (rs,exs',unex,pos) = parse q cs
      (rs,List.append exs exs',unex,pos)
    | other -> other)

And the fundamental parsers mreturn and lambda likewise:

  let mreturn r = Parser(fun cs -> ([(r,cs)],[],"",len cs))

  let lambda = Parser(fun cs -> ([],[],"",len cs))

where len is a partial function that calls List.length.
In addition we need an err parser that takes a string that
describes something unexpected:

  let err unex = Parser(fun cs -> ([],[],unex,len cs))

It is not always desirable to return a long list of what was expected
(think: the entire alphabet when a digit was expected) so a replace-expected-errors
operator >>@ is needed:

  let (>>@) p exp = Parser(fun cs ->
    match parse p cs with
    | ([],_,unex,pos) -> ([],[exp],unex,pos)
    | other -> other)

The item parser is changed so it returns an error message
if it is applied to an empty input:

  let item = Parser(fun cs ->
    match cs with
    | [] -> ([],[],"end-of-file",0)
    | c::cs' -> ([(c,cs')],[],"",0))

The sat parser is enhanced to take a string. This string
will describe what was expected if the condition is not met and is
injected into the result using the >>@
operator:

  let sat cond exp =
    (item >>= fun c -> if cond c then mreturn c else err %[c])
    >>@ exp

The char parser uses sat and now looks like this:

  let char c = sat ((=)c) %[c]

This way the char parser will return the character in the
list of expected’s if the input does not satisfy the condition.

The parsers digit and alpha uses sat so
they too must supply an error message in case of failure:

  let digit = sat (fun c ->
    (List.tryFind ((=)c) ['0'..'9']).IsSome) "a digit"

  let alpha = sat (fun c ->
    (List.tryFind ((=)c) (List.append
      ['a'..'z'] ['A'..'Z'])).IsSome) "a letter"

The symbol parser which takes a list of characters and recursively
applies the char parser to the input is enhanced using the
>>@ parser in case of failure:

  let rec symbol cs =
    (match cs with
    | [] -> mreturn []
    | c::cs' -> char c >> symbol cs' >> mreturn cs)
    >>@ %cs

The endBy parser must take the last error message from p
and concatenate it with the error message from e using the
++ combinator:

  let endBy p e =
    p >>= fun r ->
    (p ++ e) >>
    mreturn r

To test that we have reached the end of the input we have the parser
endoffile:

  let endoffile = Parser(fun cs ->
    match cs with
    | [] -> ([([],[])],[],"",0)
    | _ -> ([],["end-of-file"],%[List.head cs],len cs))

An example

Let us use what we have written to implement a parser that accepts
languages of the following simple grammar (Scott 2006):

First order of business is to specify what the parser will be returning.
We want the parser to return a list of some type of expression which
we can later evaluate. Evaluation can then either be executing the
program in an interpreter, or some sort of compilation with generation
of machine code, byte code, IL-code or something else. In this example
we evaluate by interpreting, and the parser will return a list of
expressions which is specified in the following discriminated union:

  type Expr =
    | Number of decimal
    | Identifier of string
    | Assignment of string*Expr
    | Read of string
    | Write of Expr
    | AddOp of Expr*Expr
    | SubOp of Expr*Expr
    | MulOp of Expr*Expr
    | DivOp of Expr*Expr

The values of this discriminated union becomes the semantic functions
in our production rules. The production rules can be implemented using
the combinators like this:

  let rec program = endBy (sepBy stmt endofline) endoffile
  and stmt = read <|> write <|> assignment
  and read =
    ( symbol &"read" >>
      many1 (char ' ') >>
      many1 alpha >>= fun identifier ->
      Read (%identifier) |> mreturn) >>@ "Read <var-name>"
  and write =
    ( symbol &"write" >>
      many1 (char ' ') >>
      expr >>= fun e ->
      Write e |> mreturn) >>@ "Write <expression>"
  and assignment =
    ( many1 alpha >>= fun identifier ->
      symbol &":=" >>
      expr >>= fun e ->
      Assignment(%identifier,e) |> mreturn)
     >>@ "<var-name>:=<expression>"
  and expr =
    term >>= fun t ->
    (term_tail >>= fun (op,b) -> mreturn (op t b)) <|> mreturn t
  and term_tail =
    addop >>= fun op ->
    expr >>= fun b ->
    mreturn (op,b)
  and term =
    factor >>= fun f ->
    (factor_tail >>= fun (op,b) -> mreturn (op f b)) <|> mreturn f
  and factor_tail =
    mulop >>= fun op ->
    term >>= fun b ->
    mreturn (op,b)
  and factor =
    ( char '(' >>= fun _ ->
      expr >>= fun e ->
      char ')' >>
      mreturn e)
    <|> number
    <|> (many1 alpha >>= fun identifier ->
        Identifier(%identifier) |> mreturn)
  and addop =
    (char '+' >> mreturn (fun a b -> AddOp(a,b))) <|>
    (char '-' >> mreturn (fun a b -> SubOp(a,b)))
  and mulop =
    (char '*' >> mreturn (fun a b -> MulOp(a,b))) <|>
    (char '/' >> mreturn (fun a b -> DivOp(a,b)))
  and number = integer ++ decimal
  and integer =
    many1 digit >>= fun digits ->
    Decimal.Parse(%digits+",0") |> Number |> mreturn
  and decimal =
    many1 digit >>= fun nums ->
    char '.' >>
    many1 digit >>= fun decimals ->
      Decimal.Parse(%nums + "," + %decimals)
      |> Number
      |> mreturn

This parser is capable of parsing programs like this one:

  let prog =
    "read a
    read b
    sum:=a+b
    prod:=a*b
    c:=b
    write sum
    write prod
    write c
    write ((43.2*a)+(2*b))/32.45"

Finally, evaluating the program can be done by calling parse
program &prog and passing the result to the evaluate function
in the very simple evaluation sample code below:

  let vars = new Dictionary<string,decimal>()

  let rec eval stmt =
    match stmt with
    | Number d -> d
    | Identifier id ->
      if vars.ContainsKey(id) then vars.[id]
      else new Exception(sprintf "Unknown variable '%s'" id) |> raise
    | Assignment (id,exp) ->
      let v = eval exp
      vars.Add(id,v)
      v
    | Read id ->
      Console.Write (sprintf "%s > " id)
      let v = Console.ReadLine() |> Decimal.Parse
      vars.Add(id,v)
      v
    | Write exp ->
      let v = eval exp
      Console.WriteLine v
      v
    | AddOp (e1,e2) -> (eval e1) + (eval e2)
    | SubOp (e1,e2) -> (eval e1) - (eval e2)
    | MulOp (e1,e2) -> (eval e1) * (eval e2)
    | DivOp (e1,e2) -> (eval e1) / (eval e2)

  let rec evaluate stmts =
    match stmts with
    | [] -> ()
    | stmt::stmts' ->
      eval stmt |> ignore
      evaluate stmts'

As I have shown it is quite easy to define readable, elegant parsers
using monads. Furthermore, it is easy to use the existing combinators
and parsers to write new ones.

This article is also available in PDF

References

Parr, T. (2007) The Definite ANTLR Reference – Building Domain-Specific
Languages.

Scott, M.L. (2006) Programming Language Pragmatics, 2
edition.

I like Erlang for a number of reasons: It is simple, it is a functional programming language, the language is designed around the actor-model for interprocess (Erlang processes that is) communication, a system written in Erlang is very robust, and creating computing clusters and high-availability servers is almost too easy.

So if I am about to start making an implementation of Erlang for the .NET platform there are a few obstacles and questions that needs to be addressed first:

1. Should it be pure Erlang on the .NET runtime, or should there be interoperability with the rest of .NET? While the first is easier than the latter, I am a big fan of programmers having several tools available – all of which have their justification in different parts of a software project. Giving programmers more tools will only improve their performance as well as have an impact on the number of errors in software – something that is skyrocketing in these times where software systems grow more and more complex, and development teams become larger and larger. And we will see a rise in different technologies in the near future; The DLR (Dynamic Language Runtime) is right around the corner, and F# is becoming more and more mainstream and will be included in the official Microsoft .NET language stack.
2. In Erlang a process (abstractly speaking the equivalent of a thread) is extremely light weight. As a consequence a system written in Erlang can easily have 10.000 processes running concurrently with no discernible impact on performance. This is not possible with regular .NET threads. I have been experimenting with making such light weight threads and have been successful as a proof-of-concept as well as some running code. So that is no big problem – it just needs some hard work.
3. The actor model that Erlang uses to communicate between processes is wonderfully simple to use and understand, and the same goes for implementing the framework behind it; I have written a framework for message passing in C# on distributed nodes, and I use the actor model heavily in F# so I understand it thouroughly.
4. Should a compiler compile directly to IL code? Writing a compiler that outputs IL code is hard work, and the complexity is perhaps too much to handle. But I have also been experimenting with compiling from one (simple) functional language to F# and then using the F# compiler itself to produce IL code. Much easier.

So it seems that I have at least some of the obstacles covered. What I need to address is how to bridge Erlang and .NET since the former is strictly functional and the latter focuses on object orientation.

I have also been searching the net for something similar, but I have only found some propositions and small articles about the benefits of having Erlang for the .NET platform. I think I will start this project as an academic exercise and see where it takes me. Maybe I can even find someone who are willing to help on such a project..? If you have any input whatsoever you are welcome to comment below or send me an email.

Is Erlang on the .NET platform desirable and feasible? Are there any Erlang programmers out there with comments or ideas?

What is one of the primary concerns for programmers right now? Writing high performance code that scales well regardless of whether the software is running on a CPU with one, two or 1000 cores.

Todays software does not scale well, and one of the major obstacles is making it run efficiently on multiple cores without encountering the problems that are bound to arise when programming with multiple threads. When dealing with parallel processing data parallelism is a great tool to accomplish the goal of writing highly scalable software.

In functional programming a list is one of the most fundamental data structures you can find. Furthermore it is also great for – say – iterating, and it is very easy to make parallel. I will show you a few examples written in F# – a functional programming language for the .NET platform with roots in ML and OCaml. I will demonstrate the principles with a simple data type (PList) that can be used in a wide variety of ways for processing data, and which utilizes the number of cores in your computer without you having to worry about it.

Finally I will endulge in a bit of theory for extending this data structure to span multiple machines connected in a computing cluster.

Constructing the Data Structure

A list is, as I mentioned earlier, a singly linked list. Each node contains an element e of some generic type ‘a, and it also has a pointer to the next node in the list.

In order to parallelize this data structure we need to break it up into two or more bits depending on the number of cores. There is another aspect to consider here and that is whether or not we risk performing some I/O or other stuff on each element that potentially will pause the thread. A rule of thumb says to allocate twice as many threads as there are cores in the CPU(s), but for this example we will just use the number of cores in the machine.

So how do we decide on the scheme on which we base the data structure of the parallel list? Consider this: We have a list of integers between 1 and 10 and we want to construct a new list by mapping the function x*x on each element. In F# it might look like this:

let sqrlist = List.map (fun x -> x*x) [1..10]

The List.map function iterates through the entire list, applies the (here anonymous) function to each element, and adds the result to the new list.

This is all very well but it is strictly sequential. If we split the list into two separate lists, each containing half the elements of the original list, we can apply List.map to two smaller lists in parallel. But splitting the list is not feasible – the list needs to be partitioned beforehand. And to do this I use a queue to act as the placeholder for each of the sequential sublists. Each time I want to add an element to the parallel list I simply dequeues the first element (which is a sequential list), adds the element to that list, and enqueues the result. This ensures that the list is always balanced, and adding the values 1..10 in a parallel list with two sublist will result in the following:

The first 3 insertions yields the following results

And continuing with all 10 insertions will yield this:

So the first order of business is to define the queue. In the .NET generic collections library there is an implementation, but it is purely imperative and I wanted to use a purely functional one. So I implemented one following the template from the book Purely Functional Data Structures by Chris Okasaki.

type Queue<'a>() =
    let mutable outlist:'a list = []
    let mutable inlist:'a list = []
 
    member q.Enqueue v = inlist <- v::inlist
    member q.Dequeue() =
        match outlist with
        | h::t  ->  outlist <- t
                    h
        | []    ->  match List.rev inlist with
                    | []    -> failwith "Empty queue"
                    | h::t  ->  outlist <- t
                                inlist <- []
                                h
    member q.to_list() = List.rev inlist |> List.append outlist
    member q.Clear() =
        outlist <- []
        inlist <- []
    member q.Length with get() = (List.length outlist)+(List.length inlist)

This data structure does not perform quite as well as the imperative one from the .NET library but it has the benefit of being purely functional, enabling you to implement it in your language of choice.

The next line of code is just to create a type alias between a queue of lists of type ‘a with the type name ‘a plist.

type 'a plist = Queue<’a list>

Next comes the module that holds the interesting functions. In the standard list this module is called List so I will call this module PList. This module contains a few functions that are not part of the original List module, but remember that this is just for playing around and showing you how it works.

The first of these functions is create_empty which – like the name implies – creates an empty plist. The signature is

create_empty : unit -> 'a plist

and the implementation is

/// Create an empty plist
let create_empty<'a>() =
    let plist = new Queue<'a list>()
    [1..Environment.ProcessorCount] |> List.iter (fun _ -> plist.Enqueue [])
    plist

The next function is add which adds a single element to the list. It is similar to the cons (‘::’) operator on regular lists. As described earlier it dequeues the first list in the queue, adds the element to this list and enqueues it in the list again. This is done in order to preserve order as well as keeping the parallel list balanced. The signature is

add : 'a plist -> 'a -> 'a plist

and the implementation is

/// Create a new list (in order to preserve immutable state) by adding
/// an element to the original. Rotate the sequential lists in order
/// to balance the data.
let add (plist:'a plist) e =
    let newList = new Queue<'a list>()
    List.iter (fun lst -> plist.Dequeue() |> newList.Enqueue) (plist.to_list())
    let lst = newList.Dequeue()
    newList.Enqueue (e::lst)
    newList

Then there is the function from_list which serves no other purpose than providing you with a single function to add a whole list of elements in one go. The signature is

from_list : 'a list -> 'a plist

and the implementation looks like this

/// Create a new plist from the sequential list lst
let from_list (lst:'a list) =
    let newList = create_empty<'a>()
    List.iter (fun e -> newList.Enqueue (e::newList.Dequeue())) lst
    newList

Finally there are a few interesting functions that do exist in the original List module. The first one is map. As you may – or may not – know this function takes a list of elements as well as a function and returns a new list. The elements of the new list is the result of applying the function to each element of the first list and it has the signature

map : ('a -> 'b) -> 'a plist -> 'b plist

What this parallel version does is simply to use a thread for each sequential list in the queue, here using the async monad from the F# library. The async monad does not spawn a thread per se, but puts a job on the .NET thread pool. The thread pool hold a number of idle threads and you can use them for anything asynchronous. This is just so the CLR and the operating system won’t have to go through the hard work of creating and destroying threads all the time.

Lets get back on track again. Each thread (or asynchronous task) uses the standard List.map, and the results from all the threads are compiled into a new parallel list by enqueueing the new sequential lists in a new queue. The implementation is

/// Asynchronously map the function to all elements and return a new
/// parallel list with the result.
let map f (plist:'a plist) =
    let map_async f lst = async {  return List.map f lst }
    let tasks = plist.to_list() |> List.map (fun lst -> map_async f lst)
    let newList = new Queue<'a list>()
    Async.Run(Async.Parallel tasks) |> Array.iter (fun seqList -> newList.Enqueue seqList)
    newList

The next function is length which just returns the number of elements in the parallel list. It has the signature

length : 'a plist -> int

and is implemented like this

/// Calculate the length of the parallel list by adding the lengths of the sequential lists
let length (plist:'a plist) =
    plist.to_list() |> List.map (fun lst -> List.length lst) |> List.sum

The last function is iter. This does the same as map except that it just iterates through the list without creating a new one. This is the equivalent of running an imperative for-loop over the list [n..m], and has the signature

iter : ('a -> unit) -> 'a plist -> unit

and the implementation of iter is

/// Iterate through all elements by doing it asynchronously for all
/// sequential lists.
let iter f (plist:'a plist) =
    let iter_async f lst = async {  List.iter f lst }
    let tasks = plist.to_list() |> List.map (fun lst -> iter_async f lst)
    Async.Run(Async.Parallel tasks) |> ignore

Load Balancing

I wrote earlier that there might be a problem if you use this approach for processing asynchronous tasks. How can that be? Well, suppose you have 2 cores in your CPU. You create a parallel list using two sequential lists. This parallel list contains URL’s that you want to fetch with the map function, in effect creating a new list of strings with the HTML in. So when you apply the function fetch_url to PList.map the PList will create two asynchronous tasks – one for each sequential list in the parallel list. What happens if one of the threads tries to fetch an URL from a really slow server? The entire thread pauses until all the data is fetched, leaving just one other thread to continue while the first one waits. So here you might want to spawn, say, 2 asynchronous tasks for each core. This will provide the CPU with more threads to work with in case anyone sits idle.

On the other hand, if the list consists of something that does not make the threads wait, for example a list of strings that needs to be parsed, too many threads will only slow things down since the CPU now has to switch between too many threads.

I invite you to experiment with this. You can provide a “loadfactor” to the create_empty function.

Extending PList to Span Multiple Machines

If we introduce the notion of “location” to the code, we can begin to experiment in another way. Consider this: A normal computer can be viewed as depicted below

A computer can have a number of CPU’s that in turn can have a number of cores. A computing cluster can be viewed similarly by extending the graph like this

where the individual computers are connected by some sort of network. What if we switch the nodes above out with a “location” object and use such a graph when we create and use our parallel data structures? We would use such a location object when creating our data structures; I could use a “local CPU location” object to create a parallel list running in local process space with the same number of sequential lists inside as there are cores in this particular CPU. Or I could use the top node of my location graph – the “cluster location” object to create a parallel list that spans the entire cluster of computers, in effect creating a distributed parallel data structure for my processing and storing of data. This is just something I am experimenting with.

Just kidding. No one in their right mind would say that they write bugfree code. One of the tools to help weed out the bugs before the code hits production is automatic testing, more specifically unit testing. This helps fix some problems but it also presents some of its own.

The Dilemma

The dilemma I am constantly finding myself in is this: I want to make beautiful code and design, but I also want to make sure it is functioning as it should. Now, there are a number of more or less subtle ways to make your code less error prone and one is by making it as succint as possible, and writing it according to a specific design. That in itself is what we as programmers should strive for, because succint code that is written according to an easy-to-understand specification or  design is also easier for other programmers to read, update and bugfix.

Another way to reduce the number of errors in your code is of course by using unit testing. This, however, seriously hampers good design – in fact it works directly against good design; Suppose I have made a class with a number of methods. All methods except one are private or protected since they only serve to partition the task of the single public method. I don’t want to write a unit test (some would call it an integration test) for this single method since it would 1) cause side effects in my database/file system, and 2) is so complex that writing a serious test would requiere days of work because of the data setup required by the method as well as the sheer number of possibilities for testing inside and outside the boundaries of the valid inputs.

Okay, but what if I just test some or all of the private methods that handles some specific subproblem? Well, I would have to make them public in order to test them. This goes directly against my design, as well as the principles of encapsulation: the unnecessarily public methods only tends to make the interface of the class more confusing, especially for any programmer who later looks at – or uses – the class.

Another example: I am writing a method that takes a number of inputs, do some magic to these inputs to produce new data and writes those to disk/database/network/… Clearly the persistency is of no specific concern here, so in order to test this I have to split the method into two or more and test those separately. And if I’m really “lucky” I have to use dependency injection. All this only adds more code and serves no other purpose – other than enabling me to test the code – than making the code harder to read as well as partitioning code that conceptually and by function belongs together as a single unit.

Then there is the all-pervasive question of how much. How much should I test? Some say that we need to test as much as possible. That presents two distinct problems:

1. Should I really test everything? I write a lot of code that is so simple that writing a test case for it is simply a waste of time. And adding over 200% more (test) code is simply not justifiable to anyone who have an economic interest in the project.  Besides, this just gives you a false sense of security as well as multiplying the number of errors in your test code.
2. How many inputs should I test the mthod against? All possible? Well, some accepts an infinite number of input combinations. So how will I choose the right inputs, both valid, invalid and borderline? Again, this only serves to give you a false sense of security.

In my daily work I write unit tests, and I even use it occasionally in my private projects. But writing succint code that is structured logically is an even better way to write error free code as well as maintainable code. I really do not like having to make designs that resemble something I wrote in high school, and having my creativity hampered by… a tool. That is just wrong, and a lot of ugly code has been written on that account – code that is a nightmare to maintain, use and develop.

And what really makes me wonder is this: often I have heard the argument “writing a test forces me to think about how I would use this-and-that component”. Well, if you hadn’t thought about it before you started writing it you shouldn’t start at all. Some people even like to write the test before they write the functionality. I’m not one of those guys but still I have to write tests. Unit testing is often utilized in projects that uses so called “agile” development, but in my experience not everyone gets more agile that way.

Yeah yeah, occasionally I find bugs that I didn’t think about when writing a test. But more often than not I spend way too much time correcting an old test case to fit the new requirements than I do actually implementing those requirements.
I state that the way we write tests today are inferior and an almost complete waste of time – a hell of a lot of bugs are found by the users regardless, and my time is better spent writing correct, logical, succint – and by definition – maintainable code than writing all those tests.

I write tests, but I don’t have to like it.

There was one presentation of Scheme but the speaker (and I simply can’t remember his name, sorry) unfortunately cancelled. Fortress has been put on the schedule and I managed to get Robert Pickering to come and talk about F#. I also talked to Chris Smith and I am currently trying to persuade the conference organizers to put him on the schedule too. It is a bit late in the process but I am doing my very best!

So pack your tooth brushes and laptops and head for the nearest airport or train station. I look forward to meeting you at JAOO!

But what about testing? In these TDD (Test Driven Development) oriented days being able to properly test your code with automated unit- and integration tests is paramount. And if you have to use another (or perhaps write your) test framework than the one you are already using and familiar with, that might be an insuperable problem. Fortunately you can easily use NUnit with F# and I will show you how.

Testing your F# code from C#

The most obvious way to go about testing F# code for a new F# programmer is writing your tests in C# (if you are a C# programmer. Let’s just assume that). This is okay since you are used to writing tests in this language, and it is no different from writing tests in one project that tests classes written in C# in another project. Let us start by defining an easily testable class in F#:

#light
namespace TestableLib
 
type TestableClass() =
    member tc.DoubleNumber n = 2*n
    member tc.SquareNumber n = n*n

A typical test fixture written in C# for this class looks like the following piece of code. It is a bit overdesigned – using a test fixture setup in this test is a bit too much, but bear with me for a while.

using NUnit.Framework;
using TestableLib;
 
namespace TestApplication
{
    [TestFixture]
    public class TestableClassTest
    {
        private TestableClass _testableClass = null;
 
        [TestFixtureSetUp]
        public void TestFixtureSetup() { _testableClass = new TestableClass(); }
 
        [Test]
        public void TestDoubleNumber()
        {
            Assert.AreEqual(2, _testableClass.DoubleNumber(1));
            Assert.AreEqual(8, _testableClass.DoubleNumber(4));
            Assert.AreEqual(512, _testableClass.DoubleNumber(256));
        }
 
        [Test]
        public void TestSquareNumber()
        {
            Assert.AreEqual(1, _testableClass.SquareNumber(1));
            Assert.AreEqual(16, _testableClass.SquareNumber(4));
            Assert.AreEqual(10000, _testableClass.SquareNumber(100));
        }
    }
}

This obviously works for methods defined in modules instead of classes. This is F#-modules, not .NET modules. A module in F# is resolved as a class in C#, and all methods defined in the module file are static methods on this class.

#light
module TestableModule
 
let doubleNumber n = 2*n
let squareNumber n = n*n

A couple of test methods could look like this:

[Test]
public void TestModuleDoubleNumber()
{
    Assert.AreEqual(2, TestableModule.doubleNumber(1));
    Assert.AreEqual(8, TestableModule.doubleNumber(4));
    Assert.AreEqual(512, TestableModule.doubleNumber(256));
}
 
[Test]
public void TestModuleSquareNumber()
{
    Assert.AreEqual(1, TestableModule.squareNumber(1));
    Assert.AreEqual(16, TestableModule.squareNumber(4));
    Assert.AreEqual(10000, TestableModule.squareNumber(100));
}

Writing test fixtures in F#

Whether you are testing a class written in C#, VB.NET, F# or any other .NET language you can write the tests in F# too. This is because you can annotate type definitions and members with attributes as you can with any other language. You will of course have to reference the “nunit.framework.dll” file where the attributes we use are defined.
Test fixtures are classes too so we define a new type with a default constructor, and annotate the class and the methods with the attributes defined in the NUnit.Framework namespace:

#light
namespace TestableLib
open NUnit.Framework
 
type TestableClass() =
    member tc.DoubleNumber n = 2*n
    member tc.SquareNumber n = n*n
 
[<TestFixture>]
type TestClass() =
    let mutable testableClass = TestableClass()
 
    /// This is not necessary since the mutable testableClass is already set
    /// but is just for showing how to define a test fixture setup method.
    [<TestFixtureSetUp>]
    member tc.TestFixtureSetUp() = testableClass <- TestableClass()
 
    [<Test>]
    member tc.TestDoubleNumber() =
        Assert.AreEqual(2, testableClass.DoubleNumber(1))
        Assert.AreEqual(8, testableClass.DoubleNumber(4))
        Assert.AreEqual(512, testableClass.DoubleNumber(256))
 
    [<Test>]
    member tc.TestSquareNumber() =
        Assert.AreEqual(1, testableClass.SquareNumber(1));
        Assert.AreEqual(16, testableClass.SquareNumber(4));
        Assert.AreEqual(10000, testableClass.SquareNumber(100));

The output from the F# project can then be opened in the NUnit runner just like any other assembly with test fixtures defined.

Note to Visual Studio users

Since F# is still not part of the official .NET language stack (I am currently using version 1.9.4) there are a few minor(!) hurdles to overcome. If you normally use Visual Studio you are used to be able to add references to the projects in the IDE. This is not possible with F# project since the Visual Studio integration is not functioning optimally – or at least as good as other supported languages. But you can add a reference manually by selecting the property page of the project and adding a reference with the “-R” option. I have used ‘-R “c:\Program Files\NUnit 2.4.7\bin\nunit.framework.dll”’.

I have made an implementation of the Huffman compression algorithm in F# to showcase a few of the important things that make functional programming so great to some classes of problems.

Huffman tree generated from the text ‘this is an example of a huffman tree’. Source:wikipedia.org

I will not go into detail about the Huffman algorithm itself. The following quote is from wikipedia.org about Huffman coding.

Huffman coding uses a specific method for choosing the representation for each symbol, resulting in a prefix-free code (sometimes called “prefix codes”) (that is, the bit string representing some particular symbol is never a prefix of the bit string representing any other symbol) that expresses the most common characters using shorter strings of bits than are used for less common source symbols. Huffman was able to design the most efficient compression method of this type: no other mapping of individual source symbols to unique strings of bits will produce a smaller average output size when the actual symbol frequencies agree with those used to create the code. A method was later found to do this in linear time if input probabilities (also known as weights) are sorted.

The code

The following code is an implementation of the Huffman algorithm in F#. The program does not encode a string into a compressed bit array, but will use the Huffman algorithm to count how many bits there will be in a compressed string. It is easy to see what needs to be altered in order for the algorithm to actually output a compressed array.

Furthermore the code cannot decode a compressed array. This is because I am just showcasing a few topics. It is easy to write a method that uses the Huffman tree to decode an array of bits into the original input string.

Finally the representation of the Huffman codes is not considered when calculating the size of the compressed array. In an application that actually writes the compressed data to a file or a stream, the huffman codes needs to be stored too in order for the decoder to properly decode the data.

#light
module FsHuffmanEncoder
 
// Define a node type using a discriminated union
type Node =
    | InternalNode of int * Node * Node // an internal node with a weight and two subnodes
    | LeafNode of int * byte // a leaf with a weight and a symbol
 
/// Get the weight of a node (how many occurencies are in the input file)
let weight node =
    match node with
    | InternalNode(w,_,_) -> w
    | LeafNode(w,_) -> w
 
/// Creates the initial list of leaf nodes
let createNodes inputValues =
    let getCounts (leafNodes:(int*byte)[]) =
        inputValues |> Array.iter
            (fun b ->   let (w,v) = leafNodes.[(int)b]
                        leafNodes.[(int)b] <- (w+1,v))
        leafNodes
    [|for b in 0uy..255uy -> (0,b)|] |> getCounts
    |> List.of_array
    |> List.map LeafNode
 
/// Create a Huffman tree using the initial list of leaf nodes as basis
let rec createHuffmanTree nodes =
    match nodes |> List.sort (fun node1 node2 -> compare (weight node1) (weight node2)) with
    | first :: second :: rest ->
        let newNode = InternalNode((weight first)+(weight second),first,second)
        createHuffmanTree (newNode::rest)
    | [node] -> node
    | [] -> failwith "Cannot create a huffman tree without input nodes"
 
/// Get a map of (symbol, length-of-huffman-code) pairs used when calculating the theoretical
/// length of the output.
let getHuffmanCodes topNode =
    let rec assignBitPattern node =
        match node with
        | LeafNode(_,v) -> [(v,[])]
        | InternalNode(_,leftNode,rightNode) ->
            let lCodes = assignBitPattern leftNode |> List.map (fun (v,c) -> (v,false::c))
            let rCodes = assignBitPattern rightNode |> List.map (fun (v,c) -> (v,true::c))
            List.append lCodes rCodes
    assignBitPattern topNode |> List.map (fun (v,(c:bool list)) -> (v,List.length c))
    |> Map.of_list
 
/// Calculates the theoretical size of the compressed data (without representing the
/// Huffman tree) in bits, and prints the result to stdout
let encode (input:byte[]) =
    let mapByte huffmanCodes b =
        match Map.tryfind b huffmanCodes with
        | Some huffmanCodeLength -> huffmanCodeLength
        | None -> failwith "Unknown input byte - invalid huffman tree"
    let huffmanCodes = createNodes input |> createHuffmanTree |> getHuffmanCodes
    let size = [|0|] // this is an ugly hack, but it is just for show and tell
    Array.iter (fun b -> size.[0] <- size.[0] + mapByte huffmanCodes b) input
    printfn "Original size      : %d bits" (input.Length*8)
    printfn "Compressed size    : %d bits" size.[0]

The main entry point of the application:

#light
module Main
open FsHuffmanEncoder
open System.IO
 
let fileName = @"c:\uncompressed_text.txt"
encode (File.ReadAllBytes(fileName))

Important lessons in this example

Type definitions with Discriminated union

One of the first things you notice in the code above is the definition of the type Node. This consists of either a LeafNode or an InternalNode type, and these are just names for the tuples that they represent. These named tuples are called discriminators, and can be used in pattern matching like so:

let weight node =
	match node with
	| InternalNode(w,_,_) -> w
	| LeafNode(w,_) -> w

Pattern matching is an important construct in any functional programming language, and is used all over.

Pipelining

The |> “forward pipe” operator is a very important operator in F#, and you should familiarize yourself with it. There is nothing special about it, and a description of it could be “function application in reverse”. Using |> has the advantage of making your code much easier to read and to understand the flow.

The following two lines of code are exactly the same. The first uses the normal way of calling functions, the second line uses a pipe to do the same.

List.iter (fun x -> x*2) myList
myList |> List.iter (fun x -> x*2)

It should be clear that when using big compound statements with a lot of inline function calls in function parameters the pipe operator helps make the code more readable.

Mutable state

Immutable state is one of the core properties of functional programming languages. Immutable state helps programmers write more succint programs as well as more robust programs; if the state is not shared there are no race conditions, no invalid reads/writes of memory.

But some times mutable state can enable you to write some piece of code in a more efficient manner. In the Huffman example I use a mutable array to store the count of each input symbol. This could of course be done using immutable state, but the code would be more complex and the performance more poor.

The lesson here is that although you should strive to use immutable data structures as much as possible, using mutable state is okay – and even preferable – in some situations. And when interfacing with the .NET libraries, or code written in an imperative .NET language, you automatically use shared state.

Integration with other .NET languages

Using existing .NET libraries

Using .NET libraries from F# code is just as easy as from any other language. In the Huffman example I use the class System.IO.File to read the bytes from a file on disk. At the top of the source file the statement open System.IO functions in the same manner as a using statement in C#.

The statement encode (File.ReadAllBytes(fileName)) – which could also be written File.ReadAllBytes(fileName) |> encode using the pipe operator – simply calls the method ReadAllBytes defined in the class File.

Using the encoder from C#

Using types defined in F# in another programming language is just as easy as the other way around. The above example has a module statement. This automatically resolves as a type in C#, and all methods are public static methods. Using the encoder from C# could then look like this:

static void Main(string[] args)
{
	string fileName = @"c:\uncompressed_text.txt";
	FsHuffmanEncoder.encode(File.ReadAllBytes(fileName));
}

Defining types with instance members is just as easy in F# as in any other language.

Recursion

Recursion is another important concept in functional programming. Iterating over a list is something you do a lot in programming, and defining a recursive function to do just that is more efficient than using some imperative construction (which is quite legal in F#).

Tail recursion

But recursion is a double edged sword. If you have programmed recursive methods in an imperative language you have probably also run into one or more stack overflow exceptions.

Each time a method is called the return value is pushed on the execution stack so the runtime knows where to return to when the current method call terminates. If you are not careful in terminating your recursive methods in time an unlimited number of values are pushed onto the execution stack. In reality the stack overflows and the program terminates with a nasty exception. This is also something you must be aware of when defining recursive functions in F#, especially since recursion is a key programming technique in functional programming and is thus used much more intensely.

Fortunately most funtional programming languages – including F# – implements what is known as “tail recursion”. Tail recursion enables you to write recursive functions that will never result in a stack overflow – you are able to write eternally recursive functions. This is done by ensuring that the last expression in a function definition is the recursive call.

The following function will result in a stack overflow exception

let rec badRecursiveFunction n =
	match n with
	| _ when n<9999999999 -> badRecursiveFunction (n+1)
	| _ -> printfn "%d" n //some big number

This function however is tail recursive and will terminate gracefully without putting a stain on the execution stack

let rec tailRecursiveFunction n =
	match n with
	| 9999999999 -> printfn "%d" n //some big number
	| _ -> tailRecursiveFunction (n+1)

All that ends well is tail recursive?

Be careful, though. Making sure that the last expression written in the code is the recursive method is not enough. You have to make sure that it is the last expression evaluated on the stack machine in the runtime.

Consider the following example. The function “sum” takes a list of numbers as input and sums them.

#light
 
let sum numbers =
	| [] -> 0
	| head::tail -> head + sum tail

At first glance this looks tail recursive, but that is not the case. If you apply [3;5] the expression is evaluated like this:

sum [3;5]	= 3 + ( sum [5] )
		= 3 + ( 5 + sum [] )
		= 3 + ( 5 + ( 0 ) )

In order to properly evaluate this expression the values are pushed onto the evaluation stack (this is effectively the result of evaluating the expression ‘sum’) and then the operator ‘+’ is executed. This way ‘sum’ is not the last expression to execute even though it looks like it when reading the code.

So you need to know how the stack machine in the runtime functions in order to write reliable, high performance code. Knowing the language is never enough.

Reference implementation i C#

A somewhat equivalent implementation of the above algorithm written in C# can be seen below.

using System;
using System.Collections.Generic;
using System.Text;
 
namespace CsHuffmanLib
{
    /// 
    /// C# version of the Huffman algorithm
    /// 
    public class CsHuffmanEncoder
    {
        private abstract class Node
        {
            public int frequency = 0;
        }
 
        private class LeafNode : Node
        {
            public byte symbol;
            public bool[] bitPattern;
 
            public LeafNode(byte symbol, int frequency)
            {
                this.frequency = frequency;
                this.symbol = symbol;
            }
        }
 
        private class InternalNode : Node
        {
            public Node leftNode;
            public Node rightNode;
 
            public InternalNode(Node leftNode, Node rightNode)
            {
                this.leftNode = leftNode;
                this.rightNode = rightNode;
                frequency = leftNode.frequency + rightNode.frequency;
            }
        }
 
        public int Encode(byte[] input)
        {
            List leafNodes = GetLeafNodes(input);
            Node topNode = ConstructTree(new List(leafNodes));
            AssignBitPatterns(topNode, new List());
 
            int bitCount = 0;
            foreach (byte b in input)
            {
                //find the matching symbol and store the bit count
                foreach (Node node in leafNodes)
                {
                    LeafNode leafNode = node as LeafNode;
                    if (leafNode.symbol == b)
                    {
                        bitCount += leafNode.bitPattern.Length;
                        break;
                    }
                }
            }
 
            //make sure the number of bits is dividable by 8 before converting to bytes
            return bitCount / 8 + ((bitCount % 8) != 0 ? 1 : 0);
        }
 
        private List GetLeafNodes(byte[] input)
        {
            //initialize the list that is used to count symbol occurences
            List initialLeafList = new List();
            for (int i = 0; i < 256; i++)
                initialLeafList.Add(new LeafNode((byte)i, 0));
 
            //iterate through all inputs to get frequencies
            foreach (byte b in input)
                initialLeafList[(int)b].frequency++;
 
            //remove any symbols that have a frequency of 0
            List finalLeafList = new List();
            foreach (LeafNode leaf in initialLeafList)
                if (leaf.frequency > 0)
                    finalLeafList.Add(leaf);
            return finalLeafList;
        }
 
        private Node ConstructTree(List nodes)
        {
            Node node1, node2;
            while (nodes.Count > 1)
            {
                //find the two smallest nodes (by frequency)
                node1 = FindSmallestNodeByFrequency(nodes);
                node2 = FindSmallestNodeByFrequency(nodes);
                nodes.Add(new InternalNode(node1, node2));
            }
            return nodes[0];
        }
 
        private Node FindSmallestNodeByFrequency(List nodes)
        {
            Node node = nodes[0];
            foreach (Node n in nodes)
                if (n.frequency < node.frequency)
                    node = n;
            nodes.Remove(node);
            return node;
        }
 
        private void AssignBitPatterns(Node node, List bitsSoFar)
        {
            LeafNode leafNode = node as LeafNode;
            if (leafNode != null)
                leafNode.bitPattern = bitsSoFar.ToArray();
            else
            {
                InternalNode internalNode = node as InternalNode;
                bitsSoFar.Add(false); //left node
                AssignBitPatterns(internalNode.leftNode, bitsSoFar);
                bitsSoFar.RemoveAt(bitsSoFar.Count - 1);
                bitsSoFar.Add(true); //right node
                AssignBitPatterns(internalNode.rightNode, bitsSoFar);
                bitsSoFar.RemoveAt(bitsSoFar.Count - 1);
            }
        }
    }
}

Anyway, the webcast is about an hour long, and is really interesting.

Remember to check out Joe Armstrongs blog if you are interested in Erlang and functional programming.

Granted, Drupal is a big content management system and is not designed to run a small homepage. Yes, I am an idiot when it comes to web technologies – so what. Fortunately a good colleague suggested WordPress for my website, so this saturday I have spent an incalculable number of hours trying to convert the blog entries and pages from Drupal to WordPress.

Whatever happened to compatible technologies..? If there is an easy way to convert data from one CMS to another it has eluded me. I had to do it by hand (export from the MySql database to a local file, use a text editor to edit the INSERT-statements and extract the HTML, copy-paste into the new system, and repeat…), but now it is complete (I think). The only regret I have is that I lost the comments for the blog entries, but that is a small price to pay.

So now I can lean back and enjoy the fruits of my hard labour. And hope that I will not need to upgrade my website again… ever!

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