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) ->
receive
{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)
end.

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.

Why?

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.