Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!sdd.hp.com!uakari.primate.wisc.edu!aplcen!uunet!acad!peb
From: peb@acad.UUCP (Paul Baclaski)
Newsgroups: comp.lang.scheme
Subject: tail recursion optimization
Keywords: TRO tail recursion optimization garbage collection
Message-ID: <563@acad.UUCP>
Date: 6 Jul 90 23:09:51 GMT
Distribution: comp
Organization: Autodesk Inc., Sausalito, Ca.
Lines: 39

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!peb