From: jonl%kuwait@lucid.com (Jon L White)
Subject: Finalization, Weak-pointers, and Destructors.
Organization: The Ohio State University Department of Computer and Information Science
Date: Tue, 13 Oct 1992 21:28:52 GMT

[cc to comp.lang.clos also, since this question is asked so frequently]

re: Date: Tue, 13 Oct 92 10:54:48 PDT
    From: jaf@inference.com (Jose A. Fernandez)
    . . . 
    I have combed my CLtL, 2nd Ed, and found a bogus index entry for
    "weather," but nothing for "weak pointers," "weak set," or
    "finalization."  Do you have a few spare keystrokes for an explanation
    or a pointer to an explanation?

re: Date: Tue, 13 Oct 1992 11:42:51 GMT
    From: jmorrill@bbn.com (Jeff Morrill)
    . . . 
    If you "let go" of an object in the sense of removing the last pointer
    to it, then couldn't the application "finalize" the object at that time?



Here's a thumbnail sketch of what's going on.  

Languages that DO NOT have any automated storage reclamation schemes 
must rely upon user-defined "destructors" -- these are functions that 
"disassemble" the components of an object whose lifetime has expired, 
and most often such disassembly is purely for the purpose of explicitly
reclaiming the storage occupied by "sub objects" (the proliferation of
"sub objects" and their space requirements is why GC is such supremely
good idea for Object-Oriented Languages and Systems).  But a Destructor 
need not be limited to calling _free; it could, for example, punch out 
onto paper tape a record of that object's "funeral", and even launch 
thermonuclear war in the event that a "king" object is ever destroyed.

For automated memory management (read: GC) there is of course absolutely
no need to disassemble the object in order to reclaim the storage
occupied by its "sub objects".  But there IS still a need to perform
certain other side-effecting operations ocasionally (I'm excluding,
for sake of discussion, the two examples mentioned just above!)

Consider, for example, Lisp's ability to dynamically allocate objects 
that are "I/O Streams", and then subsequently  "drop them on the floor".
Now, the early successful Lisp systems used by AI researchers were "piggy-
backed" on top of the Time-Sharing Operating Systems of the day -- such as
TENEX (the precedessor of TOPS-20), ITS (the "Incompatible Time Sharing 
system, developed for the PDP-10 at the MIT AI Lab, as a counter to the 
"heavyweight" CTSS, or "Compatible Time Sharing System" on the IBM 704/709).
No matter how imperialistic be the Lisp, its GC could *never* control all 
the resources allocated to the Lisp process; yes, it could control all of 
the virtual memory allocation (at least in true Time Sharing systems)
but it could not control the allocation of "I/O channel handles", which
it would negotiate from the Operating System through a kind of Remote
Procedure Call.  And wouldn't you just know it, the OS would ocasionally
"run out" of allocatable I/O channels.  One of my earliest memories in
the development of PDP-10 MacLisp was adding the "finalization" code
that noticed when an I/O object was being GC'd, and that issued the 
system call to release the resources inside the OS dedicated to that I/O 
channel.  Today, the parallel problem is that of X-windows resources,
which probably aren't even allocated on the local mahcine; and the
end-user's ability to write his on OS-like interface code (perhaps
through an FFI?) means that the Lisp system itself cannot, by hidden
coding such as in PDP-10 MacLisp, cover all the necessary cases.

But one might say that a reasonable paradigm for invoking explicit 
RPC-like destructors (e.g., the release of remote X-windows resources) 
is through the use of UNWIND-PROTECT, in a dynamic context.  E.g.

  (with-x-windows ((my-win   (pop-it-up <somewhwere>))
		   (your-win (pop-it-up <somewhwere-else>)))
    <diddle-around-a-bit>)

 ==>

  (let ((my-win nil)
	(your-win nil))
    (unwind-protect 
	(progn 
	  (setq my-win   (pop-it-up <somewhwere>))
	  (setq your-win (pop-it-up <somewhwere-else>))
	  <diddle-around-a-bit>)
      (when my-win (take-it-down my-win))
      (when your-win (take-it-down your-win))))

This paradigm doesn't require any "finalization" facility in the GC; so 
what's wrong with it?  Well you may notice that that the main activity
is constrained to happen with the dynamic scope of this UNWIND-PROTECT;
and funny thing about that, there are many applications of indefinite
scope.  So the explicit "destruction" is certainly OK when applicable,
but folklore abounds with the endless errors of the poooor GC-less
programmer who keeps on trying to cram an indefinite-scope application
into some ill-defined dynamic scope.  

[By the bye, don't bother telling me publicly about the infinitesimal
window of vulnerability for this code to fail at taking-down an
allocated window; *privately*, I might tell you -- should you be so
inclined to hear it -- about how Lucid's multitasking LOCK'ing facility 
has  to use a variant of UNWIND-PROTECT called (glaaag!)
INTERRUPTIONS-INHIBITED-UNWIND-PROTECT . . . but this is another story.]



Finally (no pun intended!) what about "weak pointers"?  As it turns out, 
an implementation of "Finalization" is often done using a "weak set".
Consider why.

Suppose you kept a list of 35 objects such that whenever one of them is 
"reclaimed", it should be submitted to a function that will "clean up" or 
"finalize" the object [recall what "finalization" probably means for an 
X-window STREAM.]  This "enlistment" approach is probably taken by stop-
and-copy GC's, which do not --- despite the name -- "collect" any garbage,
but rather abandon it; on the other hand, *some* mark-and-sweep GC's might
take the time to examine every object being reclaimed, and determine 
whether to finalize it based on some other facet which is not based on the
objet's presence in a table of finalizable objects.   Then again, the
true GC might not implement finalization this way either.

So an ALIST comes to mind as an implementation for the "set of finalizable
objects -- just enter:
	(<object> . <finalization-function>)
whenever you want to assure the finalizatility of <object>.   But alas, 
merely to mention the <object> in a first-class list, or hash-table, or 
vector, or . . .  will forever prevent it from being GC'd.   Which kind of
defeats the whole purpose of making the entry into the finalization table.

Without going into more detail about possible uses of weakness, let me 
just say that an obvious paradigm is a program that would like to be 
able to ask a question like this:

   If there is an object being used by "someone", fitting the 
   description  blah-blah-blah, then let me have a pointer to it.

Now the question-asking module, and the object-creating module are
completely independent.  It might be that there are few ways for the 
creator module to communicate its information about what's "available" 
except by registering its objects into some kind of table.  But 
registration into a normal table (like lists, alists, hash-tables, etc)
will forever prevent the reclaimation of the object.  Instead, why not 
register it in a "weak" table, so that *IF* there happen to be any 
clients of the object -- any modules with pointers to that object
-- then the entry in the table will be preserved; but if every actual 
client drops all references to the object, then there is no need to 
keep the object around, despite its "registration" in the information 
table.

The essence of weak pointers is that table entries are automatically
removed when there are no other, non-table, pointers to the object
(and typically, you can have the object be either a key for a value
in the table).  And the reason why automated removal is necessary
is the same reason as to why dynamic-scoping for "destructors" is
not always satisfactory: namely, completely independent clients,
making and dropping references "at will".

"Weakness" permits independent GC'ing; and GC triggers "finalization";
and "finalization" can have arbitrary side-effects, such as lauching
1000 ships off into the sunset.  So "weakness" isn't merely a memory-
management optimization; it enables arbitrary asynchronous actions.



Incidentally, from earliest times, PDP-10 MacLisp had two kids of 
vectors -- one in which the elements were considered "roots" for the 
GC, and one in which they weren't.  The combination of the second kind 
of vector, along with a Post-GC "hook" made it possible for users to 
emulate a kind of weak-pointer.  And Gerry Sussman used just such a 
combination in the programming of the micro-Planner and CONNIVER systems 
(back in the early 1970's!) 



-- JonL --
Newsgroups: comp.lang.clos