Prev: online shopping
Next: python admin abuse complaint
From: Tim Bradshaw on 2 Feb 2010 16:27 On 2010-02-02 19:25:51 +0000, Pascal J. Bourguignon said: > I imagine it doesn't need to know anything about LIST. It needs to know that LIST (or, really MY-NON-CL-DEFINED-FUNCTION-RETURNING-A-LIST) does not hang onto any of the structure it returns. If it does then that part of the structure is not otherwise inaccessible. Obviously it can know this for LIST, but it can not know this in general.
From: Kaz Kylheku on 2 Feb 2010 16:33 On 2010-02-02, Paul Khuong <pvk(a)pvk.ca> wrote: > In article <87eil3xww0.fsf(a)informatimago.com>, > pjb(a)informatimago.com (Pascal J. Bourguignon) wrote: >> I imagine it doesn't need to know anything about LIST. >> >> It only needs to have a hook in the low-level allocator. >> >> Something like: >> >> (defvar *zone* (make-garbage-collected-heap)) >> >> (defun malloc (tag size) (allocate-in-zone *zone* tag size)) >> >> (defun cons (a d) >> (let ((k (malloc 'cons (size-of 'cons)))) >> (setf (car k) a >> (cdr k) d) >> k) > > Nope. A function can cons stuff up without (only) returning it. A > trivial example would be a cache system. Not *all* consing performed > while computing a value that will be bound to a dx variable will end up > being otherwise unreachable. A function which conses additional objects which it does not return, does not keep its actions entirely secret. It leaves a tell-tale trail of allocations inside *zone*. The object bound to *zone* can be structured such that it can tell the compiler what new objects have been allocated since before the function call. Let the previous objects in *zone* be called G1, and all new allocations G0. After the function returns, its (values ...) can be treated as a root set for traversing *zone*, to mark values that are reachable from that set. Any G0 objects which do not end up marked are ``secret objects'': things that the function consed that it did not reveal to the caller. These objects can be promoted to the regular garbage collected heap. Something like that.
From: Tim Bradshaw on 2 Feb 2010 17:03 On 2010-02-02 21:33:18 +0000, Kaz Kylheku said: > Any G0 objects which do not end up marked are ``secret objects'': things that > the function consed that it did not reveal to the caller. These objects can > be promoted to the regular garbage collected heap. I think it's much harder than that. The function may not allocate any objects it does not return, but it may stash them somewhere. Apologies for the gratuitous use of LOAD-TIME-VALUE to create the secret location below, it could just be a special variable or something: (defun list/stashed (&rest elts) (let ((e (load-time-value (cons nil nil)))) (if elts (setf (car e) elts) (car e))))
From: Pascal J. Bourguignon on 2 Feb 2010 17:57 Tim Bradshaw <tfb(a)tfeb.org> writes: > On 2010-02-02 19:25:51 +0000, Pascal J. Bourguignon said: > >> I imagine it doesn't need to know anything about LIST. > > It needs to know that LIST (or, really > MY-NON-CL-DEFINED-FUNCTION-RETURNING-A-LIST) does not hang onto any of > the structure it returns. If it does then that part of the structure > is not otherwise inaccessible. Obviously it can know this for LIST, > but it can not know this in general. Yes, correct. -- __Pascal Bourguignon__
From: Kaz Kylheku on 2 Feb 2010 18:01
On 2010-02-02, Tim Bradshaw <tfb(a)tfeb.org> wrote: > On 2010-02-02 21:33:18 +0000, Kaz Kylheku said: > >> Any G0 objects which do not end up marked are ``secret objects'': things that >> the function consed that it did not reveal to the caller. These objects can >> be promoted to the regular garbage collected heap. > > I think it's much harder than that. The function may not allocate any > objects it does not return, but it may stash them somewhere. Apologies > for the gratuitous use of LOAD-TIME-VALUE to create the secret location > below, it could just be a special variable or something: > > (defun list/stashed (&rest elts) > (let ((e (load-time-value (cons nil nil)))) > (if elts > (setf (car e) elts) > (car e)))) In this case, you have to know that this is going on and that you cannot declare that the returned object has dynamic extent. A mechanism for dynamic-extent only has to work in the cases where the program hasn't invoked undefined behavior. |