This article is also available in PDF
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
I am kind of between projects right now so I am wondering what I should do next. I really like functional programming, and in particular languages like Erlang, Haskell and F#. So I started to wonder if I should make an Erlang compiler for the .NET runtime.
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:
In this small article I will show you how you can use the power of functional programming to write data structures for parallel processing that scales well on any number of cores.
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.
For a while I have looked at the schedule for the JAOO conference in Aarhus, Denmark this year, and thought: What a pity there is so little about functional programming. I mean, functional programming is really moving into the mainstream developer community these years as yet another (and very powerful) tool in our toolboxes. But that is not reflected in the schedule for JAOO, unfortunately.
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!
Switching to another programming language is difficult. Especially if you are switching from an imperative one to a functional one. There are a number of reasons why you would think that switching is bad, and when considering F# I dare say that none of those reasons are correct. The language compiles to IL (Intermediate Language) code that runs on Microsofts tried and tested .NET runtime (or Mono’s ditto). You have access to all the same classes in the .NET hierarchy that you have from any other .NET capable language. You can write web applications, WinForms applications or console applications in F#. You can connect to any kind of database that you can connect to from any other .NET language. You can use your existing C# og VB.NET code in your F# applications, or you can write F# code and use it in your existing applications. You have the opportunity to write more concise and maintainable code in a language that has much higher performance than any other functional language I know – with the possible exception of Clean, but that is still debatable, and you can mix functional programming with object oriented ditto at your leasure.
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. (more…)
For a while I have been toying with F# – a strict, functional programming language – primarily to get to know the language. I have written a few utility programs and I am working on the problems defined on the Project Euler site. These mathematical problems are perfect for being solved in a functional programming language and it is a great way to work with a new language as well as getting a brush-up on your mathematics.
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
After posting the previous blog entry on Mono IL code, Marek Safar and Miguel de Icaza from the Mono team noticed that I had made the rather embarassing mistake of compiling the code in debug-mode when compiling with Microsofts compiler. That left me with quite a red face, but now is the time to do it properly.
For this test I have written a small application that computes prime numbers using a rather inefficient but simple algorithm. The program calculates the prime numbers between 2 and 100,000 (yeah, I just love primes). This is done 1,000 times and the average execution time is displayed. (more…)
When working on RemotingLite and MPAPI I came across a couple of oddities, and a single fact that one might expect:
- Mono”s gmcs.exe compiler generates much less IL code than Microsofts csc.exe.
- Code compiled with Mono”s compiler runs more efficiently on Microsofts runtime than code generated with Microsofts compiler.
- Code compiled with Mono”s compiler runs significantly slower on Mono”s runtime than Microsoft-compiled code on Microsofts runtime.
Keep in mind that this has only been tested with a couple of applications, and that Mono might not be fully optimized to run on my laptop with Windows XP as an operating system. For that this little test cannot be thought of as anything remotely conclusive. Furthermore I am not an expert on Mono, and perhaps I have left out some compiler optimizations that I am simply unaware of. If that is the case then please contact me.
For this test I have compiled the RemotingLite v.1.2.3 and MPAPI v.1.0 frameworks with gmcs.exe. I have Mono 126.96.36.199 and Microsoft .NET 2.0 and 3.0 installed on my system. The tests have been done with the two sample applications I wrote for the MPAPI framework. (more…)
After weeks of writing, rewriting and testing the code for the Message Passing API (MPAPI) it is finally finished.
MPAPI is a framework that enables programmers to write concurrent, parallel and/or distributed software systems – in essence building cluster computers. I started writing it for a couple of reasons:
- My research into genetic programming (GP) was stalling a bit due to limited computing resources. Since I have a few computers around the house I wanted to enlist them in the huge computations that are necessary in GP, and I wanted to write a framework for building such distributed systems.
- For years I have written multithreaded (concurrent, parallel) software using the normal constructs for that in C++, Java and C#. Time and again I have debugged such applications, and I have yet to see a multithreaded program that is bugfree. It is simply too complex to write such applications using the normal synchronization mechanisms in languages with shared state concurrency. After writing a bit of Erlang code I was profoundly pleased with the way that language handles concurrency, and the ideas I have learned from that language has been incorporated into MPAPI. (more…)
Version 1.2 of the RemotingLite has now been released. Head on over to CodePlex to get the source and binary.
In this release
This release focuses on performance improvements. Up until version 1.1 the framework just used a BinaryFormatter to serialize an entire message to and from the service host. This is now done in a much more efficient manner.
Furthermore the service host will not send method arguments back to the client unless they are passed by reference. This was just a result of poor programming.
Finally I have tuned the transport protocol a bit. All this makes the framework much more efficient.
More to come?
I wrote this framework to provide remoting for the Message Passing API. Originally I used Windows Communication Foundation but that won”t work well on Mono.NET.
The rewritten MPAPI framework is currently being tested and as that progress I learn about shortcomings and bugs in the RemotingLite framework as well, since it is being tested in a “real world” situation with multiple distributed nodes. Hence I cannot guarantee that version 1.2 is the final release.