[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Issue: TAIL-RECURSION-OPTIMIZATION (Version 2)
- To: CL-Cleanup@SAIL.Stanford.EDU
- Subject: Issue: TAIL-RECURSION-OPTIMIZATION (Version 2)
- From: Kent M Pitman <KMP@STONY-BROOK.SCRC.Symbolics.COM>
- Date: Sun, 2 Oct 88 21:44 EDT
- Supersedes: <881001212759.3.KMP@GRYPHON.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
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.]
References: 5.1 Forms (pp54-59), SYMBOL-FUNCTION (p90)
Edit history: 31-Aug-88, Version 1 by Pitman
01-Oct-88, Version 2 by Pitman (merge discussion)
Status: For Internal Discussion
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...)
...standard function calling sequence...)
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.
#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))
(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.
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.
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
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.
Compilers which chose to implement the optimization in question would
be able to produce better code.
No major aesthetic impact.
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
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.