gls@THINK.COM (Guy Steele) (02/08/90)
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