peb@acad.UUCP (Paul Baclaski) (07/07/90)
How do you take full advantage of tail recursion optimization?
R3RS states: "Implementations of Scheme are required to be properly
tail-recursive. This allows execution of an iterative computation
in constant space, even if the iterative computation is described
by a syntactically recursive procedure."
In ELK 7.0, I ran the following scheme program:
(define (randtest n)
(let loop
((r_min 10) (r_max 0) (k n) (sum 0) (r 0))
(set! r (/ (random) 2147483648))
(if (> k 0)
(loop (min r r_min)
(max r r_max)
(1- k)
(+ sum r)
r)
(print (list "avg:"
(/ sum n)
"min: "
r_min
"max: "
r_max)))))
(randtest 100000)
This ends up generating 20 garbage collects. This function
appears to be properly tail recursive (i.e., it does not operate
on the result of the recursive call), but still generates garbage.
Perhaps ELK 7.0 takes constant space in evaluating this program
(it must since it would have run out of stack space), but it does
not reuse cons cells in the named loop. Is reuse of cons cells
too much to ask for or not worth it?
Paul E. Baclaski
Autodesk, Inc.
{sun|decwrl|apple|xandau}!acad!pebpeb@acad.UUCP (Paul Baclaski) (07/07/90)
This is a correction to my original posting of this subject:
The ELK version is 1.0 not 7.0.
Also, it occurred to me that the set! might generate garbage, so
I tried it again without the set! (initializing r and passing it
in the recursive call as (/ (random) 2147483648)) and it generates
slightly less garbage (8% less), but still enough to make the
question valid.
Paul E. Baclaski
Autodesk, Inc.
{sun|decwrl|apple|xanadu}!acad!peb