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
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…)
During the christmas holidays i had the opportunity to sit down and investigate the functional programming language Erlang, and i was not disappointed at all. I had heard some rumors about this particular language from various sources, particularly when i was at the JAOO conference in September 2007.
Now, there are a number of fundamental differences between a functional programming language and an imperative language like Java or C# that i like, all of which i will not delve into in this post (more on that later). But what really struck me with Erlang is the primitives for concurrent programming and building fault tolerant systems. Concurrent programming – and distributed ditto – has been build into the language from the very beginning due to the source of the language which makes it much more complete. (more…)