[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

tail recursion optimization



[Sorry about the delay in this reply. This mail was only just returned 
 due to network problems. Retrying; apologies if anyone gets duplicates.]

Date: Tue, 3 Jun 86 03:34 EDT
From: Kent M Pitman <KMP@SCRC-STONY-BROOK.ARPA>
Subject: tail recursion optimization
To: ram@CMU-CS-C.ARPA
cc: kmp@SCRC-STONY-BROOK.ARPA, common-lisp@SU-AI.ARPA
In-Reply-To: <RAM.12211792946.BABYL@C.CS.CMU.EDU>
Message-ID: <860603033423.2.KMP@RIO-DE-JANEIRO.SCRC.Symbolics.COM>

My point is that this isn't a beauty contest and your speech about
"what function calling means to me" is not going to carry any weight.

Did you read the passage I cited? On p59, in the named functions
description: "If a symbol appears as the first element of a function-
call form, then it refers to the definition established by the
innermost FLET or LABELS construct that textually contains the
reference or to the global definition (if any) if there is no such
containing construct".

The definition of DEFUN (p67) says (in a combination of text and
prose that (DEFUN name lambda-list {declaration | doc-string}* {form}*)
makes the global definition of NAME (ie, the thing referred to above) 
be (LAMBDA lambda-list {declaration | doc-string}*
     (BLOCK name {form}*))

I note in passing that were this adequate to assure closure of form 
over name, then FLET and LABELS would be the same. The whole point of
LABELS is to address this {mis}feature of the spec which does not provide
for the closure of a named function over its own function cell.

Anyway, getting back to my argument, p95 says I can setf the 
symbol-function of a symbol. (p90 defines that the symbol-function of
a symbol is what holds the global definition of a function.)

p438 assures me that compiling my program "should produce an equivalent
but more efficient program".

Given all this, I take the wording on p59 to say, effectively:
"Whether running interpreted or compiled, a piece of code which 
was denoted at the source level by a list the car of which was 
a function name not mentioned in any bounding FLET or LABELS 
will have behavior equivalent to that which would be obtained 
by applying the contents of the named function's symbol-value 
cell to the evaluated argument."

I'm not interested in debating whether this is a productive or 
efficient interpretation. I happen to personally prefer languages
which offer the meaning you describe. However, Common Lisp is not
such a language. I would support a move to change this aspect of
the language in a future spec, but I am adamant that the meaning
of a language must come (insofar as it is possible) from the wording
of its specification. In this case, the specification seems quite 
clear.

If you beleve that this is not a correct interpretation, please cite
supporting passages. You suggested that the wording is ambiguous
but offered no supporting evidence. All of your arguments were based
on what's efficient, not what's specified. At language design time,
you worry about efficiency implications. Once you've put the word on
paper, however, you can only worry about the implication of the wording
or about how you're going to change things in a later version.