F#: A Tail of recursion

Get it? Tail recursion? It is a joke you see, you are not laughing, well, I am not being paid to make you laugh.

Anyway, in all seriousness if you are like me, you look around at various things, reading snippets about various languages and the concept of tail recursion keeps on coming up and it is rare that anyone really describes what on earth it is.

Recursion is a part of functional programming, you go through uni and more often than not the lectures will claim it is what makes a language functional, (they are wrong, but my anger towards the educaction of my profession is another story).

So what happens in normal recursion is that when your program calls a function it pushes the instruction pointer (the address in the program code that identifies the next operation to execute). Once the function returns the stack is cleared and the instruction pointer is restored and the program continues along its merry way. Simple stuff right, all coming back to you from your computer theory classes?

Anyway recursion can throw a spanner into the works, a stack generally has a fixed block of memory it is allowed to use, generally around 1mb, so if your recursive function is given a large amount of data to work through, you will most probably enter the realms of the stack overflow.

So this is where tail recursion comes into play, the idea behind tail recursion is that nothing will execute after the recursive call, since there is nothing left to execute after the recursive call there is no need to store the instruction pointer on the stack, so indeed the stack stays nice and safe and you will not see that dreaded stack overflow.

BUT I hear you say, that is all well and good for simple recursive functions, but what happens when I need to do some operations of the result?

To answer this, lets us do an example.

let rec fib = function

| 0 -> 0

| 1 -> 1

| n -> fib(n - 1) + fib(n - 2)

This is not a tail recursive function and infact if you wanted to know the fibonanci number of somethign stupidly large you will get a stack overflow.

What we know about fibonnaci numbers is x = (x -1) + (x -2) and when we are working out x we already know x -1 and x -2 so we can pass them around as parameters

let fib n =

let rec loop acc1 acc2 = function

| 0 -> acc1

| n -> loop acc2 (acc1 + acc2) (n -1)

loop 0 1 n

F# Guards are my hero

Previously I mentioned pattern matching which is a nice feature of F#. It is suggested that it is the most powerful feature of F# and I am starting to see why especially in conjunction with Guards.

Continuing my comparrison of F# and Erlang pattern matching erlang also offers guards, but it only has only a few built in guards where as F# you can do whatever you like.

For example

let randomTest = function

| x when (x > 0 && x <> "return value"

|0 -> 0

|x when (x <> "return value"

Granted my example is retarded and simplistic and pointless but hopefully you can see the awesomeness of being able to give whatever you want in the guard clause.

Also the cause doesn't need to be built in functions it could be something like

|x when (x > 0 && (someFunction x) == true) -> "return value"

The downside.

Erlang only offers a small set of built in guards because that way they can guarentee they will terminate but in F# since the programmer can define his own guard clauses, who knows, if they make a mistake the function may never terminate.

So F# gives a decent amount of control over patterns but no promise of relability

Fibonacci Sequence, I totally know you

Edit -> sorry about the formatting, it exploded and I am far to lazy to fix it.

So I have looked at the first tutorial of F# and created my first program which I will get onto in a minute.

My first impressions is that F# is the bastard son of many programming ideas, for example each of these are valid forms of iteration within F#

let processItems (items : Item []) = 

  for i in 0 .. items.Length do

    let item = items.[i] in

      proc item

And

let rec processItems = function
  | []       -> ()
  | hd :: tl ->
      proc hd;
      processItems tl // recursively enumerate list

And

for item in collection do 
  process item

So to say it is a functional langauge isn't entirely correct. It is a mixed paradigm
taking ideas from OO, imperative and functional, which in itself is really 
interesting. 

Onto my sample program, like most tutorials the first thing they get you to do is a 
fibonacci sequence generator.

Here she is

start code

#light open System  let rec fib = function
    | 0 -> 0
    | 1 -> 1
    | n -> fib (n-1) + fib (n-2) 
let main() = 
    Console.WriteLine("fib 1 = {0}", (fib 1))
    Console.WriteLine("fib 2 = {0}", (fib 2))
    Console.WriteLine("fib 3 = {0}", (fib 3)) 
    Console.WriteLine("fib 4 = {0}", (fib 4))
    Console.WriteLine("fib 5 = {0}", (fib 5)) 
main()

end code


The #Light line is a nice one, when playing in the REPL everything was of this sort 
of format

let x = 5;;

But #light allows the programmer to omit redundant tokens such as the ';;' and it 
makes whitespace important. So so tabs throw warnings, but if you have set up your 
vim correctly, it will have no issue.

Secondly pattern matching. You do not need to use if, else, switch etc statements 
which is cool. From my understanding of erlang, F# seems to offer a nice stepping in 
point to a very unique language. But that being said I do not know enough about either
language to support that claim very well.

Lets Get Functional

Yesterday, the topic came up of various languages and F# came up, a Microsoft sponsored functional .NET language. It peaked my interest with another language possibly picking up GUI side of APP and I decided to look into it.

So the next few entries will be my thoughts, excitment, terror and anger about learning this new langauge.

My source of education.

http://en.wikibooks.org/wiki/F_Sharp_Programming

It took me an hour to download everything required to run this, but I am more than willing to accept it is because my internet decided it was stupid, but my anger quickly dissapated as I opened its repl. Everyt lanaguge should have a repl it is the greatest learning tool ever so YAY for that.

F# does not do implicit casts as the tutorial claims that C# does. This isn't really a negative for me as during my relationship with C# I have noticed its cast system is attrocious, it cannot be trusted and a developer should simply accept that they need to handle casting themselves.

So now I am down to actually learning the langauge, I will let you all know how I go.

For all the programming questions you would never think to ask

My bosses blog

enjoy

http://captainmisterhagan.blogspot.com/

Darkstar, mean joke or Nazi Super Weapon

First post and I go call the nice folks at Sun of being Nazi Scientists or jerks. Way to go me.

Anyway, the app that I have been working on for the last 6 months was released, the heavens opened and we were praised as returning heroes, the next day we were told to increase our user count from 40 to 4000. YAY

The previous server design was in WCF, mainly because it worked well with WPF which can give you gold class ink just like that, which was rocking for us as we are a ink heavy application. But for all the love that WPF gave us, it was heavily outweighed by WCF kick us in the nuts over and over again. It was terrible, it handled threading awkwardly for one, and my favorite complaint is that it just drops TCP connections sometimes, because it can. YAY.

So with this in mind we decided to shift our headspace from that of C# into that of Java, more specifically that of Project Darkstar, hence the topic of my post. Seriously check them out. (http://projectdarkstar.com/)

Sun has decided to release for free the sever architecture for a MMORPG, it has a tiny API (whichy I am not sure is good or bad yet) and it seems to be powered by magic. Originally when we ran benchmarking for WCF all locally on a HP Elitebook 2730p we managed to push out around 400 transactions a second, all on all not to bad but way off our mark, with darkstar we have managed to get just under 1600, that is out performing our servers, so yeah WOW.

I am somewhat skeptical, more inclined to think that we have screwed up our benchmarking maths somewhere, but really, if you cannot trust sun with your servers who can you trust?

EDIT

I was telling horrible lies ,we can push the local server to around 5000 transactions per seconds. God bless you Darkstar you Nazi super weapon you