functional programming model efficiency (Erlang specific)

Question

Hi I am a newbie in the Erlang world. When I think of how we need to solve the following problem (and there are a long list of similar ones), I think it's really inefficient because we are speaking of a lot of recursion. Apprently, language like C/Java would not need the clumsy recursion to solve this problem, but with Erlang (I guess other functional programming language needs to as well, maybe?) you must do in such a way.

---

Example 3 - Append

This program concatenates two lists:

append([], List) -> List;

append([First|Rest], List) -> [First | append(Rest,List)].

Can anyone give an explanation why this is not a problem ?

Answer 1

First of all, read the Erlang efficiency guide on recursions.

As for the clumsiness, don't forget that Erlang lists are single-linked lists, so you only have a "pointer" to the head of the list, and need to access elements by traversing the list. This would require the same amount, but different kind of clumsiness from those languages with all the pointer or reference juggling.

As for efficiency, you can implement it in a tail recursive fashion. Tail recursion is optimized (see this SO question) in a way that the compiled code becomes similar to what you implement in C++, only difference is that instead of the code pointer jumping around, the stack pointer is rewind, etc.

Anyway, try to implement the very same functionality in Java and C++ and then we will see which one is clumsier and more readable.

Answer 2

Tail recursion is optimized in every functional language -- it has no overhead compared to a procedural language's loop (or, ahem, goto;-). While the specific example you give might or might not be "tail recursion" depending on the language (lazy vs eager functional languages, for examples), when you're coding in one specific language you can generally refactor to a purely tail-recursive expression... if and when that's needed.

In a lazy language, e.g. Haskell, the append in (the Haskell's equivalent of) [First | append(Rest, List)] would be just saved as a "thunk" to be execute when and IF needed, as opposed to eagerly expanded at once. Then, when, later, somebody pattern matches THAT thunk against a head/tail structure -- then, and only then, the thunk is first executed.

Eager (non-lazy) languages have a different approach, but it's not any less efficient (although lazy-language fans might argue it IS less elegant;-).

Answer 3

Well, why do you think recursion is inefficient?

In Erlang's case it uses tail recursion (.Net IL can do this as well), which is actually slightly more efficient in terms of processing.

For example, with tail recursion, the CPU does something like this:

var first_list, second_list

label START_ITER:
  if(first_list is empty)
    goto FINISH

  var first_elem = first_list[0]
  var first_list.start_element = first_list[1]

  second_list[n+1] first_elem
  goto START_ITER

label FINISH:
  return second_list

Whereas with a for loop, you get something like this:

var first_list, second_list

var i = 0
var limit = first_list.length

label START_ITER:
  if(i == limit)
    goto FINISH

  second_list[n+i+1] = first_list[i]
  i += 1
  goto START_ITER

label FINISH:
  // Done

The thing to note with the tail recursive example is that the list splitting just changes the node in the list that first_list points to. The for loop example uses more variable assignments to do much the same thing.

This also illustrates an important point with the differences between tail recursion (which is just a goto) and normal recursion, which will actually load up a function onto the stack. This just does not happen with tail recursion, and in erlang in general.

It's a close call, but there are some extra checks and additions in a for loop, so I can't recommend one over the other in terms of efficiency, but it terms of style, recursion has it down perfectly.

I believe it was best put as "To Iterate is Human, to recurse, divine"

Answer 4

You might not know about "erlc -S" and "to_core" options, which lets you inspect the bytecodes (BEAM or HiPE)

http://stackoverflow.com/questions/586362/pattern-matching-implementation

http://www.nabble.com/Re%3A-Idiomatic-Erlang%2C-style-performance-question-p18061921.html

HTH

Answer 5

Hi I am a newbie in the C world. When I think of how we need to solve the following problem (and there are a long list of similar ones), I think it's really inefficient because we are speaking of a lot of looping. Apprently, language like Erlang would not need the clumsy looping to solve this problem, but with C (I guess other procedural programming language needs to as well, maybe?) you must do in such a way.

See what I did there? ;)

As stated by others, recursion is a perfectly normal (and efficient) way to solve things in many languages. Not directly related, but... for some things, recursion is considerably clearer to understand than looping would be (the reverse is, of course, also true)... fib(n).