[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
tail recursion optimization
- To: ram@cmu-cs-c
- Subject: tail recursion optimization
- From: Kent M Pitman <KMP@SCRC-STONY-BROOK.ARPA>
- Date: Tue, 3 Jun 86 02:27 EDT
- Cc: kmp@SCRC-STONY-BROOK.ARPA, Common-Lisp@SU-AI
- In-reply-to: <RAM.12211763396.BABYL@C.CS.CMU.EDU>
This isn't the sort of thing that is decided by a beauty contest.
As Earl pointed out, the manual is clear on this point. By the way,
the following is a valid CL function and I would be really irritated
if it didn't work...
(DEFUN FOO (X Y)
(REQUIRE 'FOO-SUPPORT) ;`Autoload' real definition of FOO!
(FOO X Y))
The definition of named functions on p59 seems to me to have pretty
clear implications in this regard.
Of course, nothing keeps you from writing a compiler which can
conditionally compile code using your optimization. However, the
default should be "off" for that switch when compiling CL programs
since it would break portable programs. If someone were to turn on
the switch, the code would not behave internally according to the
CL model, although externally it could be called by CL code since
it would be an abstraction violation of the caller to know whether
the caller was implemented using recursion or iteration. Presumably
your native SPICE:COMPILE and SPICE:COMILE-FILE functions could
observe some switch variable which CL:COMPILE-FILE and LISP:COMPILE
would bind to a safe value.
By the way, it seems to me that a CL which doesn't allow asynchronous
interrupts or multiprocessing in a shared address space should be
allowed to code-walk an expression for proof that a particular
function can be safely turned into tail-recursive call. However,
my feeling is that systems which allow me to interrupt them
and change global functions/values would be, although perhaps
technicaly within their rights to do this optimization, also likely
to confuse CL users whose model of their program might be violated
and whose "portable" experience in debugging would prove violated.