Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!think.com!hsdndev!husc6!carlton From: carlton@husc10.harvard.edu (david carlton) Newsgroups: comp.lang.scheme Subject: Re: Tail-calling and garbage collection Message-ID: Date: 15 Feb 91 17:20:42 GMT References: <9102112032.AA03542@cymbal.reasoning.com.> Sender: news@husc6.harvard.edu Organization: Citizens for Boysenberry Jam Lines: 41 In-reply-to: harlan@copper.ucs.indiana.edu's message of 14 Feb 91 06:48:40 GMT In article 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.edu