Issue: TAIL-RECURSION-OPTIMIZATION (Version 1)

[Kent M Pitman <KMP@STONY-BROOK.SCRC.Symbolics.COM>]

Issue:        TAIL-RECURSION-OPTIMIZATION
References:   5.1 Forms (pp54-59), SYMBOL-FUNCTION (p90)
Category:     CHANGE
Edit history: 31-Aug-88, Version 1 by Pitman
Status:	      For Internal Discussion

Problem Description:

  Useful tail-recursion optimizations are not permitted by CLtL because
  the compiler must assume that any opaque function call might change
  the definition of a function in between calls to that function, so a
  direct jump to the code is not appropriate.

  The best a compiler can do right now is approximately:
    (IF (EQ #'FOO ...what compiler expects...)
        ...fast jump...
        ...standard function calling sequence...)

Proposal (TAIL-RECURSION-OPTIMIZATION:PERMIT):

  Permit tail-recursion optimizations in some situations, but do not
  require them.

  Specifically, with SPEED=0, the compiler should not produce
  tail-recursion optimizations (for the sake of tracing, stack debugging,
  and reloading in interactive debugging), but with in other with higher
  speed settings, it is permitted to make such optimizations.

  Specify that the NOTINLINE declaration can be used within a function
  to inhibit tail recursive calls from within that function, regardless
  of the OPTMIZE SPEED setting.

  Specify that the NOTINLINE proclamation can be used to globally
  inhibit tail recursive calls to a particular function, regardless
  of the OPTMIZE SPEED setting.

Test Cases:

  #1: (DEFUN FACTORIAL-2 (X &OPTIONAL (N 1))
        (COND ((= X 0) N)
	      (T (FACTORIAL-2 (- X 1) (* N X)))))

      The compiler is permitted to (but not required to) treat this
      as if the following had been written instead:

      (DEFUN FACTORIAL-2 (X &OPTIONAL (N 1))
	(LABELS ((FACTORIAL-2 (X &OPTIONAL (N 1)))
		   (COND ((= X 0) N)
			 (T (FACTORIAL-2 (- X 1) (* N X)))))
	  (FACTORIAL-2 X N)))

  #2: (DEFMACRO DEFUN-AUTOLOADING (NAME FILE)
	`(PROGN (PROCLAIM '(NOTINLINE ,NAME))
		(DEFUN ,NAME (&REST ARGUMENTS)
		  (LET ((OLD-ME #',NAME))
		    (LOAD ,FILE)
		    (LET ((NEW-ME #',NAME))
		      (WHEN (EQ OLD-ME NEW-ME)
			(ERROR "Function ~S was undefined after autoload." ',NAME))
		      (APPLY NEW-ME ARGUMENTS))))))
      (DEFUN-AUTOLOADING FOO "foo.lisp")
      (DEFUN BAR (X) (FOO X))

      The compiler must not make assumptions about the contents of FOO,
      so the function BAR will always see the current definition of FOO even
      in the face of runtime redefinition.

Rationale:

  Tail recursion optimization is an important source of speed improvement.

  Program modularity is of key importance to many Common Lisp programmers,
  and it would be rash to say that the compiler could simply violate function
  boundaries at whim. Nevertheless, for Common Lisp to successfully compete
  with other languages, it should be designed in a way that at least permits
  implementations to make this optimization.

  This proposal is designed to achieve a workable compromise between issues of
  speed and debuggability.

  Some implementations do tail recursion removal already even when it is
  not permitted. Such implementations have an unfair benchmark advantage over
  "correct but slow" implementations in the marketplace. This would even the
  odds for those implementations who would do the optimization if only it were
  correct.

Current Practice:

  Symbolics Genera and Symbolics Cloe not currently do tail recursion
  optimization. As such, they are compatible with the proposal.

Cost to Implementors:

  None. This permits action for those interested in taking it, but does
  not require any action.

Cost to Users:

  Small. Some users who do runtime redefinition of functions would have to
  add some declarations if they were compiling code with SPEED>0.

Cost of Non-Adoption:

  Lisp would show up poorly against other languages in certain benchmarks.

  Lisp vendors who do this optimization even though it's technically not
  correct would continue have an unfair business advantage over vendors
  over those who respect the rules of the language.

Benefits:

  Compilers which chose to implement the optimization in question would
  be able to produce better code.

Aesthetics:

  No major aesthetic impact.

Discussion:

  Pitman explored a number of different variants of this proposal before
  sending this one. He's not wedded to the details here, but just tried to
  submit something that would sound plausible. If there are ways to change
  things which would make this proposal more palatable, he's happy to
  hear them.

  Charles Hornig (Symbolics) observes that SPEED=0 is perhaps not quite
  the right criterion. The issue of whether absolute values of the 
  OPTIMIZE qualities are what's of interest or only relative values of
  the different qualities is an open topic. For now, this proposal uses
  SPEED 0 just to be conservative. If everyone can agree on something
  broader, we could change the proposal. Alternatively, we can just 
  adopt that part of the proposal `as is' and work on a separate proposal
  on how to deal with OPTIMIZE qualities.