Subject: Re: Lisp is being maligned (was Lisp is *SLOW*)
From: Erik Naggum <clerik@naggum.no>
Date: 1997/08/04
Newsgroups: comp.lang.lisp,comp.lang.c++,comp.programming
Message-ID: <3079676458456671@naggum.no>


* Bryant Brandon
| While I'm here, would someone kindly tell me the exact difference between
| tail-recursion and generic recursion?

I'll try.

generally, "recursion" refers to cycles in the call tree.  however, the
trivial case when you call yourself to solve a smaller problem than you
were given is more commonly referred to as "recursion" than the general
call-tree cycle.

for instance, if you are given an item and a list of items in which to
search for it, the result is either false if the list is empty, true if the
first element of the list is what you're looking for, and otherwise the
same as the result of searching for the item in the _rest_ of the list,
thus having reduced the problem to two simple cases and a smaller problem
congruent to the original problem.  as in:

    (defun find-item (item list)
      (cond ((endp list) nil)
	    ((eq item (first list)) t)
	    (t (find-item item (rest list)))))

we note that this function calls itself at the very end of itself and that
it does nothing with the value returned but return it to its own caller.
obviously, calling yourself with new arguments when the old arguments are
never needed and then immediately returning whatever such a call returns is
a special case.  this special case is called "tail-recursion", and it can
be accomplished with a jump to the start of the function.  consider the
straight-forward rewrite (yes, this _is_ Common Lisp):

    (defun find-item (item list)
      (tagbody
       recurse
	(cond ((endp list) nil)
	      ((eq item (first list)) t)
	      (t (setq list (rest list))
		 (go recurse)))))

(which, incidentally, is a transformation many C programmers do by hand.)

now consider the case where two functions produce a cycle in the call tree:

    (defun evenp (integer)
      (if (zerop integer)
	t
	(oddp (1- integer))))

    (defun oddp (integer)
      (if (zerop integer)
	nil
	(evenp (1- integer))))

it is obvious that these functions satisfy the criterion that their
original arguments are never used after the last call, and that they return
the value of the last call directly.  however, they don't call themselves,
so the obvious rewrite is not available.

at this point, we're moving onto calling conventions in various languages,
and this is a large topic, so I'll just note that Scheme _requires_ a call
whose value is immediately returned to be a _jump_.  that is, at assembly
level, what would have been

    call <whatever>
    return

_must_ be written

    jump <whatever>

this is true even if the `return' instruction does a lot of work to clean
up things after itself, but only if that cleanup does not depend on
information local to the function where it occurs.  e.g., in the most
common calling convention for C, the calling function must remove arguments
it has pushed on the stack (an optimization to use registers for some of
the arguments does not change this picture), and only the caller can do
this because a function does not know how it was called.  this is one of
the legacies of C that are impossible to get rid of (which is why C++ has
it, despite the fact that C++ functions know how many arguments they must
have been called with), and which makes interoperability with other
languages such a hard problem.

ANSI Common Lisp does not impose the requirement to do call/return as jump
on its implementations, but many are very good at detecting cases where it
can do this safely.  naturally, there are calling convention "gotchas" that
may inhibit an implementation from doing this.

hope this helps.

#\Erik
-- 
404 Give me a URL I cannot refuse.