Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!dali.cs.montana.edu!milton!uw-beaver!cornell!stodghil
From: stodghil@urd.cs.cornell.edu (Paul Stodghill)
Newsgroups: comp.lang.scheme
Subject: Question about tail-recursion
Message-ID: <49406@cornell.UUCP>
Date: 6 Dec 90 18:26:22 GMT
Sender: nobody@cornell.UUCP
Distribution: comp
Organization: Cornell Dept. of Computer Science
Lines: 68

In the Revised^n Report, it says,

 "Implementations of Scheme are required to be properly tail-recursive. This
 allows the execution of an iterative computation in constant space, even if
 the iterative computation is described by a syntactically recursive
 procedure."

I can't figure out what is meant by "syntactically recursive." Obviously
this is meant to cover the case,

 (define (fact x r) (if (= x 1) r (fact (- x 1) (* x r))))

but how about,

 (define fact (lambda (x r) (if (= x 1) r (fact (- x 1) (* x r)))))

or,

 (set! fact (lambda (x r) (if (= x 1) r (fact (- x 1) (* x r)))))

or,

 (define fact
   (let ((v (lambda (x r) (if (= x 1) r (fact (- x 1) (* x r))))))
      v))

or,

 (define (fact x r) (if (= x 1) r (apply fact (list (- x 1) (* x r)))))

or,

 ... continue arbitrarily nasty examples ...

I realize that all of these cases can be handled dynamically, but I am
interesting in the following,

 What compile-time transformation can be made to remove the
 tail-recursiveness from Scheme?

For example, "fact" might become,

 (define (fact x r)
   (iterative
     (lambda (x r)
       (if (= x 1)
          (exit r)
          (continue (- x 1) (* x r))))
     x r))

where "iterative," "exit," and "continue," might have the effect of,

 (define (exit r) (list 'EXIT r))
 (define (continue . rest) (cons 'CONTINUE rest))

 (define (iterative closure . initials)

   (define (iter-helper state)
      (if (eq? (car state) 'EXIT)
          (cadr state)
          (iter-helper (apply closure (cdr state)))))

   (iter-helper (cons 'CONTINUE initials)))

If anyone has any thoughts on this sort of transformation, I'd love to hear
them.

Paul Stodghill (stodghil@cs.cornell.edu)