stodghil@urd.cs.cornell.edu (Paul Stodghill) (12/07/90)
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)