Issue: TAIL-RECURSION-OPTIMIZATION (Version 2)

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

[Some people didn't get copies of this when I sent it last night, so
 I'm retrying. -kmp]

I tried to merge the discussion, mostly trying to use the terms "early
binding" and "tail recursion" more correctly. The changes pervade the
text.

I admit to making the changes somewhat hastily in an effort to get out
of here at a reasonable hour tonight.  I hope David Gray and Eric Benson
will check carefully for any major problems since they were the ones
most vocal by the previous writeup.

[Btw, I wanted to reply to some specific comments by Gray and Masinter
with which I disagree, but I don't have time right now. I'll try to get
to them another time.]
 -kmp

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

Problem Description:

  Early binding of function names to function definitions is generally
  inhibited in Common Lisp because CLtL says the compiler must assume
  that any opaque function call might change the definition of a
  function in between calls to that function.

  The inability to do early binding is a barrier to doing traditional
  optimizations such as tail recursion removal. For example, the best
  a compiler can typically do right now when a function FOO calls
  itself tail recursively is approximately:
    (IF (EQ #'FOO ...what compiler expects...)
        ...fast jump...
        ...standard function calling sequence...)

Proposal (TAIL-RECURSION-OPTIMIZATION:PERMIT-EARLY-BINDING):

  Permit early binding in some situations, but do not require them.

  Specifically, with SPEED=0, the compiler should not do early binding
  (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 (except as discussed below).

  Specify that the NOTINLINE declaration can be used within a function
  to inhibit early binding of a function name to its definition,
  regardless of the OPTMIZE SPEED setting.

  Specify that the NOTINLINE proclamation can be used to globally
  inhibit early binding of a function name to its definition, 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.
      Therefore, the function BAR will always see the current definition
      of FOO even in the face of runtime redefinition.

Rationale:

  Early binding 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 early binding 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 early binding.
  As such, they are compatible with the proposal.

  Lucid Common Lisp does early binding, and so does not conform to CLtL in
  some cases.

  The TI Explorer assumes a function will not redefine itself and does
  tail recursion removal at `higher optimization levels.'

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.

  David Gray has expressed reservations about this to the OPTIMIZE SPEED
  quality at all since he sees it as a semantic issue.

  Masinter points out that there might be some relation of this to 
  the issue FUNCTION-COERCE-TIME.