Craig Johnston <caj@lfn.org> wrote:
+---------------
| When I run a simple factorial procedure written so as to be tail-recursive
| with large values of n, elk baloons up to over 10 megs, while scm for
| instance stays around 1 meg in size.  
| 
| Is elk not properly tail-recursive?
+---------------

I'm not completely sure. I've been studying the Elk source recently, and
while it's clear that there's a lot of code in there to handle tail calls
(including tail recursion), it's not clear that it's correct in all cases. 

For example, in the case of a Scheme procedure tail-calling itself, it
*re-uses* the current procedure frame instead of allocating a new one.
I can think of some pathological cases [not necessarily even involving
call/cc ;-} ] where that won't give the correct results.

On the other hand, in the case of a straight-forward classic "iterative"
tail-recursion, such as a simple factorial:

	(define (my-fact n)
	  (define (helper n accum)
	    (if (zero? n)
	      accum
	      (helper (- n 1) (* n accum))))
	  (helper n 1))

the problem you're seeing is *not* with the evaluator, but with the
generational garbage collector -- I think it may be just a little too
eager to grab new memory when allocating an object, rather than trigger
a full collection (which might avoid expanding the heap). 

I ran "(my-fact 10000)" in two versions of Elk: one with the generational
collector, and the other with the stop-and-copy collector. Note the heap
growth with the generational collector:

	> (garbage-collect-status)
	(generational)
	> (my-fact 10000)
	[Garbage collecting... 45% reclaimed]
	...[7 more "collecting" messages deleted]...
	[Heap expanded to 3072K (to allocate new object)]
	...[12 more "collecting" messages deleted]...
	[Garbage collecting... 42% reclaimed]
	[Heap expanded to 4096K (to allocate new object)]
	[Heap expanded to 5120K (to allocate new object)]
	[Garbage collecting... 45% reclaimed]
	...[10 more "collecting" messages deleted]...
	[Heap expanded to 6144K (to allocate new object)]
	[Heap expanded to 7168K (to allocate new object)]
	[Garbage collecting... 44% reclaimed]
	[Garbage collecting... 44% reclaimed]
	[Heap expanded to 8192K (to allocate new object)]
	[Heap expanded to 9216K (to allocate new object)]
	[Heap expanded to 10240K (to allocate new object)]
	[Garbage collecting... 45% reclaimed]
	...[4 more "collecting" messages deleted]...
	28462596809170545189064132121198688901480514017027...
	...rest of result deleted...
	> 

So we ended up with ~10 MB of heap (total of 11.6 MB process size).

Whereas with the stop-and-copy collector:

	> (garbage-collect-status)
	(stop-and-copy)
	> (my-fact 10000)
	[Garbage collecting... 47K of 1024K]
	[Garbage collecting... 48K of 1024K]
	[Garbage collecting... 48K of 1024K]
	...[95 more "collecting" messages deleted]...
	[Garbage collecting... 60K of 1024K]
	[Garbage collecting... 60K of 1024K]
	[Garbage collecting... 60K of 1024K]
	28462596809170545189064132121198688901480514017027...
	...rest of result deleted...
	>

we end up with only one meg of heap (~2.5 MB total process size).
So clearly, this one didn't "blow up" the same way.

I suspect you might be able to tune the generational collector to
better suit your needs, but I'm not familiar enough with it (yet)
to know what the knobs are. [Sorry.]


-Rob

-----
Rob Warnock, 8L-855		rpw3@sgi.com
Applied Networking		http://reality.sgi.com/rpw3/
Silicon Graphics, Inc.		Phone: 650-933-1673
2011 N. Shoreline Blvd.		FAX: 650-964-0811
Mountain View, CA  94043	PP-ASEL-IA