Subject: Re: Lisp is being maligned (was Lisp is *SLOW*) From: Erik Naggum <firstname.lastname@example.org> Date: 1997/08/04 Newsgroups: comp.lang.lisp,comp.lang.c++,comp.programming Message-ID: <email@example.com> * 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.