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.
So what is all this talking about “automatic testing”? I know my code work so I don’t have to write some “test case” just to verify that; A complete waste of time!
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 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 (more…)
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
I recently discovered this webcast called “Erlang – software for a concurrent world” by Joe Armstrong. It is recorded at a JAOO conference. Yes, I wrote “a”… I can’t find any info on which one it is but i strongly suspect it is from either London, Sydney or Brisbane in 2008.
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.
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. (more…)
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 188.8.131.52 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…)