Path: utzoo!utgpu!jarvis.csri.toronto.edu!mailrus!ames!sun-barr!newstop!texsun!smunews!ti-csl!m2!gateley
From: gateley@m2.csc.ti.com (John Gateley)
Newsgroups: comp.lang.scheme
Subject: Re: (none)
Message-ID: <109911@ti-csl.csc.ti.com>
Date: 9 Feb 90 18:56:47 GMT
References: <9002051741.AA03862@heike.informatik.uni-dortmund.de> <SIMON.90Feb7120454@viking.cs.tu-berlin.de> <4782@brazos.Rice.edu>
Sender: news@ti-csl.csc.ti.com
Organization: TI Computer Science Center, Dallas
Lines: 28

In article <4782@brazos.Rice.edu> dorai@titan.rice.edu (Dorai Sitaram) writes:
<In article <SIMON.90Feb7120454@viking.cs.tu-berlin.de> simon@opal.tu-berlin.de (Simon Leinen) writes:
<$[Transforms fact into tail recursive form]
<$Unfortunately, most existing compilers don't perform this optimization
<$themselves.
<
<"Unfortunately"?  I wouldn't want the compiler to perform this
<optimization, for if you unwind the *-calls, you'll find the
<non-tail-rec version does (* n (* n-1 (* n-2 ... 1))), while the
<tail-rec one does (* 1 (* 2 (* 3 ... (* n 1)))).  The optimization
<hinges too much on the commutativity of * for my comfort.

This "optimization" can be a pessimization under certain circumstances:
when calling fact on a large number: By doing the multiplications in
reverse order, you spend more time the bignum arithmatic than is made
up by the loop overhead.

<(I guess you mean Scheme rather than Lisp, since none of the (other)
<Lisps bother even about tail-call optimization, not to speak of the
<optimizations that Holger and you speak of.)

While Scheme is the only Lisp I know of that requires tail-recursion,
other dialects of Lisp may provide it: the TI Explorer Common Lisp
compiler is one that does. I believe that Gnu's C compiler also does tail
recursion!

John
gateley@m2.csc.ti.com