Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!cs.utexas.edu!yale!mintaka!bloom-beacon!dont-send-mail-to-path-lines
From: gyro@cymbal.reasoning.COM (Scott Layson Burson)
Newsgroups: comp.lang.scheme
Subject: Tail-calling and garbage collection
Message-ID: <9102190613.AA24577@cymbal.reasoning.com.>
Date: 19 Feb 91 06:13:21 GMT
References: <CARLTON.91Feb15122042@husc10.harvard.edu>
Sender: daemon@athena.mit.edu (Mr Background)
Reply-To: Gyro@reasoning.com
Organization: The Internet
Lines: 79


   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.

-- Scott