There is a growing trend to include elements of functional programming in “mainstream” languages such as C#. If functional programming is so good this raises the question of why we don’t just move to a functional language. After all, there is an ideal candidate in the shape of F#, which is a true .NET-based language. So is F# so very different? Let’s find out.
What is functional programming?
It’s almost too easy to say that functional programming is all about using functions, but there are many ways of doing this.
Functional programming attempts to make programming more like mathematics by making programming functions more like mathematical functions. In maths a function is a set of rules that given an input set of values produces a single result – the value of the function.
This initially sounds very much like the sort of function we use in programming, but there are some important differences. For example a mathematical function doesn’t change any of its input values and certainly doesn’t change any value that isn’t part of the function. This is usually expressed by stating that mathematical functions don’t have side effects, whereas programming functions often do. A typical programmed function might well change its input parameters and pass them back as secondary results, and often changes variables, for example within the user interface, that are not really part of the function.
The key ideas in functional programming are “no side effects” and “immutability” – although many a keen functional programmer would be horrified by this oversimplification. Immutability relates to the idea that once a function has been evaluated it shouldn’t change its value – mathematical functions don’t. In many ways it is the requirement for immutability that is usually the most difficult to swallow.
Programming vs mathematics
Consider the familiar statement:
x=x+1;
…which means take the current value stored in x, add one to it and store the result back in x. In functional programming you really should consider x to be a function and the value stored in it is the value of the function x. Hence by the requirement for immutability its value can’t change and so any instruction like x=x+1 is complete nonsense. It is like writing:
Sin(1.4)=Sin(1.4)+1
…which is even more clearly nonsense.
The reason why this is so difficult for a traditional programmer to accept is that x=x+1 is the point where programming really diverges from mathematics. From the viewpoint most of us are familiar with, programming is about describing “procedure”, i.e. what happens, and it is perfectly normal to take the value stored in x, add one to it and store it back in x.
Most of what we have achieved has been via procedural programming even if we have been using functions. Functional programming is about non-procedural programming. It’s about static relationships and things that change as little as possible.
If this sounds a little unpromising remember that a function can still be “active” in the sense that it “works out a result” – but with no side effects and once the result is derived it doesn’t change.
You might very well at this point be doubting that functional programming can work – how can it possibly banish procedure from programming? I have to admit that in practice functional languages have to let a bit of “procedure” sneak in. Just as procedural languages such as C# have elements of functional programming, so function languages such as F# have elements of procedural programming.
What is important is to minimise their use and be aware of what you are doing. Many F# functions are used just for their side effects – usually called “imperative” programming. In practice working with F# is a mix of functional and imperative programming.
You might also find some of the mechanisms that functional programming languages “invent” contrived, and as much a transgression of the basic principles as a dropping back to procedural semantics, but it’s all an effort to keep the purity of the approach.
Added to this is the fact that F# is overtly a “mixed mode” language, attempting to fuse functional programming with other approaches. In this article the focus is on the functional as this is the least well-known of the approaches but lookout for others!
To understand the advantages on offer, you have to ask the question: what exactly is wrong with a procedural approach that a functional approach fixes? The simple answer is that if you don’t specify a procedure then the machine is free to decide exactly how to implement your code.
In theory, functional programming makes threading, and parallelism in general, very easy and fairly safe. A functional program is also supposed to be easier to prove correct, debug, and so on, than a procedural program and all of this is true – but this doesn’t mean that it is impossible to write a bad functional program.
F#
Enough of the theory, it’s time to see how it all works in F#. You can download, and find other information about F# from MSDN.
If you have a copy of Visual Studio installed then you will be able to create F# projects after installation. If you don’t want to risk your Visual Studio configuration then you can either use the command line compiler or you can use the Visual Studio Shell. The VS Shell is a cut-down IDE that can be used, free of charge, to host other languages and development tools without the need to install the full version of Visual Studio.
If you want to use the VS Shell then download and install the Integrated version runtime. The download that you need is called “Visual Studio 2008 Shell (integrated mode) with Service Pack 1 Redistributable Package”, and you need to unpack it and then use the installation program. Do this before you install F#, and you will discover that you have a choice of F# projects to work with. Notice that none of the Express versions of Visual Studio can be used with F#.
Some basic ideas
Once you have F# installed and working within Visual Studio – full version or Shell – you can create a new F# Application Project. This has a single F# source file with the one generated keyword “light”. This simply allows you to use the light version of F# syntax. Let’s start off with the traditional “Hello World” program:
open System printfn "Hello F# World" Console.ReadKey(true)
The open command simply loads a reference to a .NET library and it is needed if we want to use the Console object. The printfn function prints the string on the console and the ReadKey function waits until the user hits a key, any key. If you type this in and run it you will be rewarded with the traditional message (see Figure 1). However, in this case the Hello World example really isn’t very good. It’s a terrible example of a functional program as the printfn and ReadKey functions are being used for their side effects on the user interface. So with this said let’s move on quickly to a more functional example.
Figure 1: Hello World – but not a good example of functional programming
Functions
It is tempting to present examples where functional programming seems most at home – e.g. computing with a mathematical flavour – but there are lots of such examples already available, so let’s try and keep in the realm of general programming tasks. First we need to look a little more closely at the idea of a function. Declaring new “variables” is easy:
let i=1 let j=1
This creates two strongly typed immutable variables – once assigned a value you can’t change it. To define a simple function that adds two values together we can write:
let add x y = x + y
The first occurrence of x and y define the parameters for the function and what happens to the parameters is given by the expression to the right of the equals sign. In a functional language parameters like x and y are the only things that are “mutable” in the sense that they can be repeatedly given values each time the function is called. This idea of the parameter being the only mutable thing in functional programming is key to the subject of lambda calculus, from which the term “lambda expression” is derived. In lambda calculus mutable parameters are identified by writing a lambda in front of them.
Using the function is also easy:
let k=add i j
…and you can check that things are added together correctly using:
printfn "%i %i %i" i j k
If you know C, C++ or C# the use of the formatting string in the printfn function will be familiar – it simply means print three formatted integers.
Functional control structures
The most immediate question that any procedural programmer will want to ask is how to implement all of the standard control structures – the if statement and iteration in all its forms. The if statement is relatively easy as all you need to do is consider the usual if..then..else type construct as a function that returns either the “then” function or the “else” function – this is good functional programming. Notice that writing functions one after another implies the default order of execution so we haven’t completely avoided the procedural.
The enumeration loop is more problematic because most loops involve the idea of changing the value of something within the loop, and this isn’t allowed if what is in the loop is immutable. There are various ways that a functional language can avoid iteration. For example, to display the first ten integers you can use:
let nums=[1..10] printfn "%A" nums
The [1..10] is just a specification for a list in F# and you can avoid many explicit iterations by simply converting them into a list and a list operation. For example, suppose you want to print the squares of the first ten integers you can use:
let nums=[1..10] let sqr x = x*x let ans=List.map sqr nums printfn "%A" ans
First we create a list of the first ten integers, then define a function to perform the square operation and finally apply the sqr function to each of the values in the list. The List.map function takes any function and applies it to each member of the list and returns a new list of results. If you want to use a variable iteration range you can, as in:
let nums=[1..n]
…as long as n has a value when this is evaluated then it all works.
Notice that the map function takes a function as one of its parameters. In functional language the use of functions in the same way you use any other data type is called “first class” functions. There are lots of list processing functions and mastering these is a large part of mastering functional programming in F#.
This is a good place to introduce the notion of an anonymous function. Often functions are just used once and there is no need to give them a name – you just want to use them. F# supports anonymous functions – often called lambda expressions – that look just like C# lambda expressions. For example the calculation of the squares could have been written:
let ans=List.map (fun x -> x*x) nums
The fun keyword declares a function and the “arrow” can be thought of as showing how the parameters are transformed into the result. You can take this “anonymous” approach to functions and nest function calls to reduce the entire generation and printing of the squares to a single statement:
printfn "%A" (List.map
(fun x -> x*x) [1..10])
It is possible to take this approach so far that it becomes very difficult to follow what an F# program is doing – so beware.
What about finding the sum of all of the values in a list? The simple answer is that there is the sum function which returns the sum of a list. For example:
printfn "%A" (List.sum nums)
However this is a bit of a cheat as it doesn’t really give you any idea of how to convert an iteration with a “running computation” of a more general kind into functional form. You could say it hasn’t illustrated how mutable becomes immutable.
One solution to this more general problem is the use of a “fold” function. The best way to explain folding is via an example. The List.fold_left function accepts a function, an initialiser and a list as its parameters. The function plays the role of an “accumulator” in the sense that it collects up the results of the function applied to each element of the list. To sum a list for example you might use something like:
printfn "%A"
(List.fold_left (
fun a x-> a + x) 0 [1..10])
The accumulator function in this case is:
fun a x-> a + x
…the x parameter is set to each value of the list in turn and the a parameter is the result of the function applied to the previous list element. The 0 is the initialiser and sets the a parameter to zero in the function’s first call.
If you are following this explanation and are a long-time procedural programmer then you should be spluttering – but this is a loop in disguise! Well yes, but… think of it this way instead. The function is applied to the first element of the list x0:
f(0,x0)
…where the value of a is provided by the intialiser. Next it is applied to the second element in the list x1 but this time a is set to the result of the function applied to the first element, that is:
f(f(0,x0),x1)
The third evaluation is similar:
f(f(f(0,x0),x1),x2)
…and so on. Now you can see that what you have here is a nested function evaluation:
f(f(f(f(...(0,x0),x1),x2),x3)...,xN)
Hence folding is building nested function evaluations without having to write it all out manually. Now is folding a loop in disguise, or something different? For the record the foldleft function nests taking the list elements left to right and foldright takes them in the reverse order. You should also appreciate that folding is a very general and powerful technique that really does allow you to do more or less anything you could do by iteration. For example, you could use the Cons function, which is implemented as an operator :: (double colon) to build up a new list. For example, 1::[2;3;4] adds the number one to the start of the list to produce [1; 2; 3; 4]. To make use of this in a fold to reverse the order of the values you could use something like:
printfn "%A"
(List.fold_left
(fun a x-> x :: a) [] [1..n])
In this case the “accumulator” function:
fun a x-> x :: a
…takes each element of the list and adds it to the accumulator list being built up in a. A moment’s thought should convince you that this results in the list being reversed. Notice the use of the null list [] to initialise the fold.
Recursion and tail recursion
Similar functions provide all sorts of alternatives to writing an explicit for loop, and F# does also have an explicit for statement. However, the most celebrated way of avoiding iteration in functional programming is to use its more sophisticated alternative, recursion. If you are already happy with the idea of recursive functions then you fill find F# and recursion easy. Of course the unlikely word is “happy” – most programmers, even experienced ones, aren’t happy about recursion.
Let’s look at a very simple example – sum the first N integers recursively. A recursive definition means that the function is defined in terms of itself and to make sure that this isn’t a mistake, i.e. to make it certain that you intended to use the function in its definition, you have to use the keyword “rec” for recursive. The first thing to note is that SumN(0) has to be zero and if the parameter is any other value than zero then SumN(n)=n+SumN(n-1). With these two observations the recursion is easy to write:
let rec SumN n =
if n=0 then 0 else n + SumN(n-1)
The function can be used as normal, for example:
printfn "%A" (SumN 10)
Recursion bothers many programmers because it seems to be very inefficient. Consider what happens with SumN 10. First SumN 10 is called which starts to evaluate 10+SumN 9 but has to wait until SumN 9 has finished computing the sum of the first nine integers. Of course, SumN 9 has to wait while SumN 8 evaluates, which waits while SumN 7 evaluates and so on. When we reach Sum 0 then a result is returned and the whole waiting stack of functions “unwinds” in the reverse order they were called in doing the sum and building up the final result. This is easy but inefficient because all of the suspended copies of the function’s expression have to be kept alive on the stack until it all unwinds. Not good.
The best form of recursion is called “tail recursion” simply because it doesn’t leave a waiting trail of part-completed expressions on the stack. In tail recursion the recursive function ends with a simple call to itself and nothing more. What you have to do to create a tail recursive form of the function is to find a way to pass the computation down the recursion as it happens rather than do the job on the way “back up”. Often this requires an additional parameter used to carry the result to the last recursive function call. For example, our sum of the first N integers can be re-written in tail recursive form as:
let rec SumN n acc =
if n=0 then acc
else SumN (n-1) (n+acc)
The new acc parameter accumulates the result as the recursion proceeds and when we finally get to n=0 the result is returned.
In this case there is no need to keep track of the recursion and the compiler optimises things so that only a single stack frame is used. You can usually transform a recursion to tail recursion using this sort of result but it can be complicated and there is very little help in doing the job. The compiler doesn’t even indicate when a function is tail recursive. Should you worry about this subtle point? You should at least know about tail recursion because functional programmers often talk about it, but in the main it’s an optimisation and can be left for a later version of your application.
Currying
In using the previous tail recursive sum you have to adopt a slightly unnatural calling convention because of the need to initialise acc. For example to sum the first 10 integers you need to use:
printfn "%A" (SumN 10 0)
As the accumulator always has to be initialised to zero we can create a new function from SumN with the second parameter set to 0 – this is called “currying”:
let Sumn n=SumN n 0
Now we can call Sumn without having to specify the zero:
printfn "%A" (Sumn 10 )
The bigger picture
This article has concentrated on some of the key ideas in functional programming, in particular how to accept the almost paradoxical (to the procedural programmer) idea of immutability. What we haven’t examined in detail are the benefits of this approach – implementing parallelism in particular. Also missed out are the many powerful, but perhaps not so functionally pure, facilities of the language. F# isn’t an academic language and often the best way to express an idea is to use imperative or procedural programming and F# has the facilities you need – it has for loops, while loops and so on. It also has lots of interoperability with the .NET class library – and did I mention that it’s also object-oriented? Most of these non-functional innovations are fairly familiar and you should be able to make progress with the help of the manual and a few examples.
Dr. Mike James’ programming career has spanned many languages, starting with Fortran. The author of Foundations of Programming, he has always been interested in the latest developments and the synergy between different languages.
Comments