gyro@cymbal.reasoning.COM (Scott Layson Burson) (02/12/91)
This is a follow-up to my previous message about a beneficial property of tail-recursion elimination vis-a-vis garbage collection. Jim McDonald of Lucid has pointed out to me that my message might be taken to imply that the benefit I was describing is somehow unique to Scheme, and couldn't be had in an implementation of Common Lisp even if that implementation supported full tail-recursion elimination, as do, for instance, Lucid CL and Coral CL. I didn't mean to say that; I meant to be claiming this benefit for tail-recursion elimination independent of language. It's just that the CL I use the most is a more traditional implementation, and so I sloppily thought of that as a property of the language, which it isn't. -- Scott
harlan@copper.ucs.indiana.edu (Pete Harlan) (02/14/91)
gyro@cymbal.reasoning.COM (Scott Layson Burson) writes:
[tail-recursion isn't a property of a language, but an implementation concern]
Certainly a compiler for any language may perform tail-call
optimization, and in this respect it is a language-independent issue.
However, when a *language*, rather than a compiler, guarantees an
optimization, it opens the door for a programming style that might not
be a portable program in the language if the optimization were not
guaranteed.
W.r.t. tail-call optimization, I can write a continuation-passing
style program in Scheme and it is correct; if I transliterate it to
Common Lisp, the correctness of the program depends on whether the CL
compiler performs tail-call optimization. Thus the program can't be
properly called a CL program.
In other words, the Scheme language includes CPS programs, while
Common Lisp does not. The difference is an 'optimization', but this
only proves that when you guarantee an optimization for a language,
rather than a compiler, you (might) expand the set of valid programs
for that language.
Peter "I Love Passing Continuations Around" Harlan
Indiana University harlan@copper.ucs.indiana.edu
[Perhaps the problem lies in language specifications ignoring the
concept of finite computer memory? This makes it difficult to even
define what tail-call optimization might mean. In any case, this is
a bug, not a feature, in language specifications, since memory is
indeed limited.]carlton@husc10.harvard.edu (david carlton) (02/16/91)
In article <harlan.666514120@copper> harlan@copper.ucs.indiana.edu (Pete Harlan) writes:
Certainly a compiler for any language may perform tail-call
optimization, and in this respect it is a language-independent issue.
However, when a *language*, rather than a compiler, guarantees an
optimization, it opens the door for a programming style that might not
be a portable program in the language if the optimization were not
guaranteed.
really? the scheme semantics doesn't mention tail recursion anywhere
that i can tell, which would seem to imply that optimizing it out
doesn't change the actual meaning of a program. indeed, i have a hard
time seeing how it could, since converting a tail-recursive function
call to a jump merely involves throwing out information that is
useless, so it is hard for me to see how it could possibly change the
meaning of anything. could you please send a me program (written in
scheme) that works in scheme but wouldn't if scheme didn't handle tail
recursion properly, so i can see what you are talking about?
W.r.t. tail-call optimization, I can write a continuation-passing
style program in Scheme and it is correct; if I transliterate it to
Common Lisp, the correctness of the program depends on whether the CL
compiler performs tail-call optimization. Thus the program can't be
properly called a CL program.
In other words, the Scheme language includes CPS programs, while
Common Lisp does not. The difference is an 'optimization', but this
only proves that when you guarantee an optimization for a language,
rather than a compiler, you (might) expand the set of valid programs
for that language.
again, i am confused. writing programs in a CPS style would be
horribly wasteful of memory if a program didn't optimize
tail-recursive function calls into jumps, but it should still give the
same result. unless, of course, the implementation runs out of
memory. so i suppose that there are programs that are valid scheme
but are invalid without this optimization, but the only such programs
are ones that would run forever. are there any others?
david carlton
carlton@husc9.harvard.eduhanche@imf.unit.no (Harald Hanche-Olsen) (02/17/91)
In article <CARLTON.91Feb15122042@husc10.harvard.edu> carlton@husc10.harvard.edu (david carlton) writes: In article <harlan.666514120@copper> harlan@copper.ucs.indiana.edu (Pete Harlan) writes: Certainly a compiler for any language may perform tail-call optimization, and in this respect it is a language-independent issue. However, when a *language*, rather than a compiler, guarantees an optimization, it opens the door for a programming style that might not be a portable program in the language if the optimization were not guaranteed. really? the scheme semantics doesn't mention tail recursion anywhere that i can tell, which would seem to imply that optimizing it out doesn't change the actual meaning of a program. indeed, i have a hard time seeing how it could, since converting a tail-recursive function call to a jump merely involves throwing out information that is useless, so it is hard for me to see how it could possibly change the meaning of anything. On a machine with infinite memory, optimizing tail recursion does not change the meaning of programs. However, in Scheme you can write a loop using a tail call and the loop can execute millions of times without running out of memory if it can do it once. I'd say that whether or not the program runs out of memory changes its meaning, whether the semantics say so or not ... - Harald Hanche-Olsen <hanche@imf.unit.no> Division of Mathematical Sciences The Norwegian Institute of Technology N-7034 Trondheim, NORWAY
pcg@cs.aber.ac.uk (Piercarlo Grandi) (02/19/91)
On 16 Feb 91 23:24:34 GMT, hanche@imf.unit.no (Harald Hanche-Olsen) said:
hanche> In article <CARLTON.91Feb15122042@husc10.harvard.edu> carlton@husc10.harvard.edu (david carlton) writes:
carlton> really? the scheme semantics doesn't mention tail recursion
carlton> anywhere that i can tell, which would seem to imply that
carlton> optimizing it out doesn't change the actual meaning of a
carlton> program.
Actually the english text (as opposed to the denotational semantics) of
the 3.99 scheme report mandates tail recursion in the implementation
wherever possible. The denotational semantics are only *part* of the
scheme report. Clearly tail recursion does not make a difference in the
world of mathematics, but scheme is not lambda calculus; the report
defines the behaviour of conforming scheme *language implementations*,
to the point of prescribing specific syntax and giving various levels of
conformance.
The scheme report is essentially the specification of scheme's 'eval'
function (which is never explicitly mentioned :->), and some "quality of
implementation" requirements *are* indeed explicitly made.
hanche> I'd say that whether or not the program runs out of memory
hanche> changes its meaning, whether the semantics say so or not ...
Well said! However, more than its meaning, it changes its behaviour, and
here we are skating on very thin ice. The semantics of "bottom" and of
partial functions are not that easy to agree about :-).
--
Piercarlo Grandi | ARPA: pcg%uk.ac.aber.cs@nsfnet-relay.ac.uk
Dept of CS, UCW Aberystwyth | UUCP: ...!mcsun!ukc!aber-cs!pcg
Penglais, Aberystwyth SY23 3BZ, UK | INET: pcg@cs.aber.ac.ukgyro@cymbal.reasoning.COM (Scott Layson Burson) (02/19/91)
Date: 15 Feb 91 17:20:42 GMT
From: david carlton <carlton@husc10.harvard.edu>
In article <harlan.666514120@copper> harlan@copper.ucs.indiana.edu (Pete Harlan) writes:
Certainly a compiler for any language may perform tail-call
optimization, and in this respect it is a language-independent issue.
However, when a *language*, rather than a compiler, guarantees an
optimization, it opens the door for a programming style that might not
be a portable program in the language if the optimization were not
guaranteed.
really? the scheme semantics doesn't mention tail recursion anywhere
that i can tell, which would seem to imply that optimizing it out
doesn't change the actual meaning of a program. indeed, i have a hard
time seeing how it could, since converting a tail-recursive function
call to a jump merely involves throwing out information that is
useless, so it is hard for me to see how it could possibly change the
meaning of anything. could you please send a me program (written in
scheme) that works in scheme but wouldn't if scheme didn't handle tail
recursion properly, so i can see what you are talking about?
Garbage collection and tail-call optimization occupy an interesting
position as language design properties go. As you quite correctly point
out, they do not change the meaning of any program, and thus they don't
show up in an abstract semantics. Nevertheless they are very
important... [cont'd]
W.r.t. tail-call optimization, I can write a continuation-passing
style program in Scheme and it is correct; if I transliterate it to
Common Lisp, the correctness of the program depends on whether the CL
compiler performs tail-call optimization. Thus the program can't be
properly called a CL program.
In other words, the Scheme language includes CPS programs, while
Common Lisp does not. The difference is an 'optimization', but this
only proves that when you guarantee an optimization for a language,
rather than a compiler, you (might) expand the set of valid programs
for that language.
again, i am confused. writing programs in a CPS style would be
horribly wasteful of memory if a program didn't optimize
tail-recursive function calls into jumps, but it should still give the
same result. unless, of course, the implementation runs out of
memory.
I would disagree with Pete Harlan's use of the words "correct" and
"valid" in this context, supplying instead the word "practical", which
is what garbage collection and tail-call optimization are really about.
so i suppose that there are programs that are valid scheme
but are invalid without this optimization, but the only such programs
are ones that would run forever. are there any others?
Yes! On any given finite computer there are a lot of programs that can
be written that will run out of memory in an implementation without
garbage collection and tail-call optimization, but will execute to
completion in an implementation with these properties (and, in fact,
will be perfectly reasonable programs that you might very well actually
want to write). It is definitely not necessary that a program be
infinite in order for the difference to show up (since we have no
infinite computers). As a practical matter, it turns out that a
guarantee that all implementations will have these properties makes for
a very considerable expansion and generalization in the ways that
programs can be written.
I am repeatedly mentioning garbage collection and tail-call optimization
in the same breath, by the way, not to suggest that they must always
appear together -- clearly they needn't -- but because they are like
each other in this way. Tail-call optimization can be seen as garbage-
collecting the stack; in fact, one can even imagine an implementation
that worked exactly that way: it would wait until all available stack
space was exhausted, then delete all useless frames from the stack.
Useless frames are easy to detect, on a typical machine, because the
return address of the frame points directly to the pop-frame-and-return
instruction sequence.
-- Scotthieb@heston.cs.indiana.edu (Robert Hieb) (02/20/91)
Two points: 1) The "official" Scheme semantics is an approximation. There are various aspects of Scheme that are under-specified, over-specified, or wrongly-specified by the denotational specification. 2) There is more than one way to model a language. It is not clear that a denotational model is the best way to model a language like Scheme. An operational model might be better in some respects. To expand on the second point, consider the lambda calculus. Although there are denotational models, the primary model must be beta reduction. It is worth noting that beta reduction is clean with respect to both tail recursion and garbage. In fact, beta reduction is even clean with respect to environments, a claim which few Scheme systems can make. That is, the environment of a closure or continuation in most Scheme implementations hangs onto variable bindings that are not free in the text of the closure or continuation (or in the transitive closure thereof). Garbage collection and tail recursion are too fundamental to Scheme to ignore based on a notion of semantics that is not broad enough to include them. Without guarantees of both Scheme would be useless as a programming language. One would be forced to add specific looping and allocation/deallocation constructs. C with first-class closures and continuations would be an interesting language, but not Scheme. Bob Hieb Indiana University