[erlang-questions] Idiomatic Erlang, style/performance question

Richard A. O'Keefe ok@REDACTED
Fri Jun 20 06:23:49 CEST 2008


On 19 Jun 2008, at 8:30 am, Circular Function wrote:
> Is there a styleguide somewhere on Erlang?

"Do what Joe Armstrong does in his book."

> Hmm while writing I got a thought. Is the last function tail- 
> recursive?
> I have only heard that term but never used it.
> Is tail-recursion faster or uses less memory, what is the advantage/ 
> disadvantage?

I prefer the term "Tail-Call Optimisation" because it is more accurate.
The idea (as explained in "Lambda - the Ultimate Goto") is that if the
dynamically last thing a function does (in any language) is to return
the result of another function call, then there is no point in keeping
the current stack frame.  You might as well arrange for the new
function to return directly to the original caller.  Think of *all*
tail calls as "argument binding + GOTO".

It is always better if a compiler does tail call optimisation  
(correctly)
than if it doesn't.  Even the C compiler I normally does it.  (It may  
not
be a coincidence that the machine is a SPARC where stack frames are
larger than you would think.)  It doesn't cost you anything in time, and
it's a win in (stack) space.  [I am ignoring debugging issues here,  
which
is why Smalltalk doesn't do TCO.]

However, there is a *different* question, which is whether writing a
function so as to exploit tail call optimisation is always a win over
writing in some other fashion.  And that has the answer, "no, sometimes
one way is better, sometimes the other, depending on what you are  
doing."

The main advantage of TCO is the way it lets you think:
control structure = procedure call.  You don't have to choose between
tail recursion and iteration, because they *are the same thing*.  So
it's OK for Erlang not to offer a 'while' loop, for example.
>

> powerx(N, 0) -> 1;
> powerx(N, P) when is_integer(P), P > 0 ->
>         N * powerx(N, P - 1);
> powerx(N, P) when is_integer(P), P < 0 ->
>         1 / powerx(N, -P).
>
There are no tail calls here; after the calls to powerx/2
have finished, there is still something for the caller to do.
>
> powerc(N, P) ->
>         if
>                 P > 0 ->
>                         N * powerc(N, P - 1);
>                 P < 0 ->
>                         1 / powerc(N, -1 * P);
>                 P == 0 ->
>                         1
>         end.

The only change of any significance here is the PAINFULLY
EYE-JARRING indentation by 8 columns.  The stack space
required is O(N).
>
>
> power(N, P) when is_integer(P), P >= 0 ->
>         ipower(N, P, 1);
>     power(N, P) when is_integer(P), P < 0 ->
>         1/ipower(N, -P, 1).

The first call here is a tail call, the second is not.
>
>
>     ipower(0, _, R) -> R;
>     ipower(N, P, R) -> ipower(N, P-1, R*N).

This is equivalent to

	ipower(N, P, R) {
	    while (P != 0) P--, R *= N;
	    return R;
	}

The amount of stack space required is O(1).





More information about the erlang-questions mailing list