This article is also available in PDF
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.
(more…)
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:
(more…)
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
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…)
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
(more…)
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.
Those who know me knows that I am not a web-programmer. I don’t think I am compatible with PHP, HTML, XML, AJAX, and all the other web technologies out there. So when I need to do something with my domain I tend to rely heavily on open source software designed so that I have to write a minimum of code. The past months I have used Drupal for my homepage. It has worked okay, but lately I had grown a bit tired of it – it was slow, and it seemed impossible to get it to do exactly what I needed. Furthermore I couldn’t upgrade it to a more recent and secure version without crashing the entire webserver, so a new solution was needed.
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!
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…)