[plt-scheme] call/cc and space

I spoke too broadly. I should have said that what I consider the
interesting cases of safe fon r space has nothing to do with GC. (Your
original message asserted that safe for space was entirely about GC,
IIUC.) Those cases are about stack management, not heap management
(and, as Matthias points out, you might call pop() gc). Sorry for the
confusion.

Anyways, the expensive/interesting problem, as I understand it, is that
when you enter a let (say), you hold on to the bindings in the let even
if the variable bound in the let is not free in the term you're working
on. For example, in mzscheme, this prints #t (followed by #f), but in a
safe for space implementation, it would print #f (followed by #f).

(require (lib "etc.ss"))

(define tmp #f)

(let ([x (build-list 10000 add1)])
  (set! tmp (make-weak-box x))
  (collect-garbage) ;; a bunch to make sure
  (collect-garbage) ;; nothing fishy with
  (collect-garbage) ;; finalizers or conservative
  (collect-garbage) ;; collection is going on.
  (printf "~s\n" (pair? (weak-box-value tmp))))

(collect-garbage)
(printf "~s\n" (pair? (weak-box-value tmp)))

Robby

At Tue, 7 Feb 2006 15:07:53 -0800, John Clements wrote:
> 
> On Feb 7, 2006, at 2:44 PM, Matthias Felleisen wrote:
> 
> >
> > On Feb 7, 2006, at 5:36 PM, Robby Findler wrote:
> >
> >> Safe-for-space has nothing to do with garbage collection (but that is
> >> the right paper! :)
> >
> > Is pop() a gc instruction? Some people think so. In that sense a  
> > lot of stuff is gc. -- Matthias
> 
> Huh?  On page 179 of the PLDI proceedings, Dr. Clinger (cc'ed)  
> describes the space complexity class of sfs evaluators.  In these  
> evaluators, the portion of the environment that is retained, for  
> instance, in an 'if' or a procedure call, is restricted to those  
> bindings that are referred to by "future" parts of the computation.  
> Here's the example he gives to show that the class of 'evlis'  
> evaluators is not a subset of the class of 'sfs' evaluators:
> 
> (define (f n)
>    (let ([v (make-vector n)])
>      (if (zero? n)
>          0
>          ((lambda () (begin (f (- n 1)) n))))))
> 
> A safe-for-space evaluator will consume a maximum amount of memory  
> that is linear in the size of n--because the references to 'v' in the  
> parent frames are collected, even though the call to 'f' is not in  
> tail position.
> 
> So while it's true that the theorem says nothing about _how_ this  
> efficiency must be achieved, the reference implementation defines  
> this complexity class explicitly in terms of a garbage collection  
> rule.  In what sense is this "nothing to do with garbage collection"?
> 
> John