Scheme Digest #295

[Guy Steele <gls@think.com>]

   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