Re: Scheme style auto-resizing hashtable (fwd)

[Maciej Stachowiak <mstachow@mit.edu>]

jglascoe@jay.giss.nasa.gov writes:
> On Thu, 19 Nov 1998, Maciej Stachowiak wrote:
> 
> > 
> > jglascoe@jay.giss.nasa.gov writes:
> > > 
> > > Yes it's safer, but when will it collect?  Do you really think it's going
> > > to start collection in the middle of a "list->hash-table" operation? 
> > 
> > It certainly can. I even think Guile's GC will interrupt long running
> > C operations that manipulate Scheme data.
> > 
> 
> but it can't possibly start GC'ing parts of the list; how could it
> possibly know which parts of the list are no longer needed?
> 
> 

Here's an example (not using C, but it is possible to generalize this
to C in Guile at least):

(iota 10000) creates a list from 0 - 9999.


Now, suppose I do


;; yes, I know this can be trivially wirtten in terms of map and
;; reverse

(define (double-reverse-list ls)
  (double-reverse-list-helper ls ()))


(define (double-revers-list-helper ls accum)
  (if (null? ls)
      accum
      (double-reverse-list-helper (cdr ls) (cons (* 2 (car ls)) accum)))))



(double-reverse-list (iota 10000))


This can collect the traversed portion of the list generated by iota
as soon as they are no longer needed. This is because there will be no
references to them on the call stack, since all recursive calls or
calls to another procedure are in tail position and the only reference
to the head of the iota-generated list is in the call to
double-reverse-list which disappears off the call stack as soon as it
tail-calls double-reverse-list-helper (this may change in the presence
of debugging, I don't know).

 - Maciej