[erlang-questions] conditional expressions

Richard O'Keefe ok@REDACTED
Thu Nov 20 04:01:02 CET 2008

On 20 Nov 2008, at 4:10 am, David Mercer wrote:

> Can someone please explain the tail recursion problem with andalso?


fun all(f, []) = true
   | all(f, x::xs) = f x andalso all(f, xs);

The recursive call here is a tail call:
when that recursive call is finished there is nothing
to be done with the result except to return it.


all(_, []) -> true;
all(F, [X|Xs]) -> F(X) andalso all(F, Xs).

The recursive call here is NOT a tail call,
because it is semantically the equivalent of

all(_, []) -> true;
all(F, [X|Xs]) ->
     case F(X)
       of false -> false
        ; true -> R = all(F, Xs),
                  if R == true ; R == false -> R end

Of course SML and Haskell don't need to check because the
type system means that the code that gets past the compiler
couldn't possibly fail such a check.  But Lisp and Smalltalk
and Python don't bother making any such check, even though
it _might_ fail if it _were_ done.

Skipping the check on R doesn't seem to be much of a problem
in practice.  Loss of tail recursion here IS a problem.

More information about the erlang-questions mailing list