Wednesday, December 12, 2007

Erlang, Tail Recursion, and Living the Dream

Erlang Eureka! describes a moment of discovery as the narrator walks through a Erlang code example. Function loop is an example of a function that runs within its own thread, awaits messages from other threads, and then acts on received messages. Note that function loop is a loop only in the sense that loop repeats by calling itself.
loop(Module, State) ->
{call, From, Request} ->
{Result, State2} = Module:handle_call(Request, State),
From ! {Module, Result},
loop(Module, State2);
{cast, Request} ->
State2 = Module:handle_cast(Request, State),
loop(Module, State2)
Loops, such as for and while loops, are a considered to be iterative. Function loop is a different beast in that it uses recursion to mimic the iterative loop mechanism. Function loop uses a type of recursion that is called "tail recursion". Essentially if a function returns the return value of a recursive call, it is tail recursive.

In languages such as Java, C, C++, C# and Ada (imperative languages), tail recursion is frowned upon because it risks overflowing the stack Tail recursion can be easily replaced with an iterative approach, a process called tail call optimization.

On the other hand, functional languages such as Erlang, Lisp, Scheme, and F# make use of tail recursion as we can see from the code example.


1. Iteration by recursion is required because variables may be assigned only once in most functional languages, including Erlang. This "assign once" feature is one of the key reasons that Erlang can manage state well in the face of concurrency. Notice how State is updated within loop and stored in State2 which is passed by parameter to the tail recursive call to loop.

2. Functional programming language compilers, such as Erlang, perform tail call optimization. Functional language programmers will actually structure code to achieve tail recursion (pretty different). See A Deeper Look at Tail Recursion.

I also would like to credit Jomo Fisher's Adventures in F# -- Tail Recursion in Three Languages blog .

Its funny how I set off to research this topic. After experimenting with Erlang over a weekend and blogging about it, I went to work on Monday and actually thought about implementing a loop using recursion, for about a microsecond. My fingers stopped so fast that they left skid marks on the keyboard. Could you imagine implementing an application's main loop using recursion and several seconds into operation the stack overflows, the application crashes, and there you sit feeling very dumb?

With a bolt of lightening, a clear perspective of the differences between imperative and functional programming languages lay before me.

It is great when your work is interesting and your work-place is your laboratory - that is why I am Living the Dream.

1 comment:

Jeff Moser said...

Glad to see you're enjoying functional programming!

When I was taking a compiler course at Purdue, one of our assignments was to do tail-call elimination on a subset of the functional language ML. Just like you said, you look for a final statement where you call yourself (let rec) and then you don't have to emit another stack frame. Almost all of ML & Scheme's libraries are implemented like this.

I really think that with Soma's endorsement, F# will be the first functional language that will let us play with these concepts at work and actually get things done and shipped. That's why I'm glad that Erik Meijer, Joe Duffy, Don Syme, and Joe Armstrong are friends and share ideas.

Even today by downloading the compiler, you can write all your code that manipulates trees, parsing, etc, in F# and get the sweet compiler magic that makes the code really efficient, and then call it from C# or any .net language.