Path: utzoo!attcan!uunet!snorkelwacker!think!zaphod.mps.ohio-state.edu!tut.cis.ohio-state.edu!ucbvax!bloom-beacon!THINK.COM!gls
From: gls@THINK.COM (Guy Steele)
Newsgroups: comp.lang.scheme
Subject: Scheme Digest #295
Message-ID: <9002081548.AA10809@ungar.think.com>
Date: 8 Feb 90 15:48:56 GMT
References: <DIGEST.184.900208.024543.17@MC.LCS.MIT.EDU>
Sender: daemon@athena.mit.edu (Mr Background)
Organization: The Internet
Lines: 39


   Date: 7 Feb 90 23:00:08 GMT
   From: Dorai Sitaram <titan!dorai@rice.edu>

   ... simon@opal.tu-berlin.de (Simon Leinen) writes:
   $... muenx@heike.informatik.uni-dortmund.de (Holger Muenx) writes:
   $This is why Lisp (or Scheme) programmers change a definition like
   $
   $	(define fac (lambda (n)
   $	  (if (= n 0)
   $	      1
   $	    (* n (fac (- n 1)))))) ; tail-call to *, but not to fac
   $
   $into the less obvious, but more efficient
   $
   $	(define fac (lambda (n)
   $	  (letrec ((fac-aux (lambda (n acc)
   $	             (if (= n 0)
   $	                 acc
   $	               (fac-aux (- n 1) (* n acc)))))) ; tail-call to fac-aux
   $	    (fac-aux n 1))))
   $
   $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.

Indeed, you do need to know that * is associative (commutativity
is not required).

See Darlington and Burstall. "A Transformation System for Developing
Recursive Programs", Journal of the ACM, January 1977, and a pile
of other papers that it inspired.

--Guy Steele