Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!rutgers!sri-spam!sri-unix!hplabs!sdcrdcf!darrelj
From: darrelj@sdcrdcf.UUCP (Darrel VanBuer)
Newsgroups: net.lang.lisp
Subject: Re: call/cc and proper tail recursion
Message-ID: <3378@sdcrdcf.UUCP>
Date: Sun, 26-Oct-86 11:04:30 EST
Article-I.D.: sdcrdcf.3378
Posted: Sun Oct 26 11:04:30 1986
Date-Received: Mon, 27-Oct-86 01:42:22 EST
References: <20000003@uicsrd> <20000008@uicsrd>
Reply-To: darrelj@sdcrdcf.UUCP (Darrel VanBuer)
Organization: System Development Corporation R&D, Santa Monica
Lines: 54

Tail recursion results in no stack growth and the efficiency of iteration
because by the time the compiler finishes with it, it IS iteration.  I.e.
when the compiler finds any leg of code which ends activity in a function by
returning the value of another call to the function, it instead fixes up the
argument values and jumps to the top of the function.
Example
DEFUN ASSOC(KEY LST)
  (COND((EQ KEY(CAAR LST))
          (CAR LST))
       (T (ASSOC KEY (CDR LST))))
compiles to something like: (for a simple stack machine)
ASSOC:
	GETVAL KEY
	GETVAL LST
	CAR
	CAR
	EQ
	JUMPifFALSE FIXTAIL
	GETVAL LST
	CAR
	RETURN
FIXTAIL:
	GETVAL LST
	CDR
	SETQ LST
	JUMP ASSOC   (instead of CALL ASSOC; RETURN)

On tail recursion and function calls with bad side effects on local
variables (where, prior to recursion calls a function which sets a local
variable of the supposedly recursive function; then the iterative unfolding
collapse all the bindings into a single binding.  There are several ways of
dealing with the problem:

1.  Do as Scheme: use strict lexical binding -- if you can't see a reference
to a variable in directly embedded code, there ARE NO REFERENCES to it;
there is no such thing as a SPECIAL variable in scheme; thus tail recursion
is always safe based on static analysis of a single function.
2.  Ignore the problem during optimization and lusers get what they deserve
in manipulating special variables [They could always write
  (PROG1 (SELF --) (DUMMYFUNCTION)) to defeat the tail optimization]
3.  Have the compiler do some sort of extended analysis of the safety of
function calls.  This could range in sophistication from checking a list of
functions known to be free of side effects to elaborate analysis of all user
functions.  Then only do tail optimization in cases where it's known to be
safe.
-- 
Darrel J. Van Buer, PhD
System Development Corp.
2525 Colorado Ave
Santa Monica, CA 90406
(213)820-4111 x5449
...{allegra,burdvax,cbosgd,hplabs,ihnp4,orstcs,sdcsvax,ucla-cs,akgua}
                                                            !sdcrdcf!darrelj
VANBUER@USC-ECL.ARPA