[plt-scheme] call/cc and space

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



-------------- next part --------------
A non-text attachment was scrubbed...
Name: smime.p7s
Type: application/pkcs7-signature
Size: 2430 bytes
Desc: not available
URL: <http://lists.racket-lang.org/users/archive/attachments/20060207/c7fe2af4/attachment.p7s>