ForeignDependencies: The Semantics

[John Meacham]

ack! no with my intended semantics, cycles are not a problem anymore
than they are for weak pointers or the touchForeignPtr method.
everything will still be GCed just like normal. 

(note that these are pretty much exactly the Weak Pointer semantics, if
you like replace 'ForeignDependency' with Weak Pointer as you read and
it should make sense)

addForeignDependency k v   creates a weak pointer from k to v. a weak
pointer ONLY affects GCing and guarantees __nothing about the ordering of
the finalizers__ for the key and value (I will show why this is not a
problem). 

A ForeignDependency guarantees exactly and only this:

  If k is considered alive by the garbage collector then v is
  considered alive by the garbage collector. 

note, that this makes sense, in haskell, if k' has a reference to v'
then if k' is alive then v' is alive. however, if the reference exists
in C land, the garbage collector cannot know about it so a
ForeignDependency is the mechanism that makes the relationship known to
the haskell runtime. 

cycles will be handled just like cycles in haskell, they will be
collected if the cycle is unreachable. the order of the finalizers is
not guaranteed in any way. this is not a problem for the following
reason, assume you have two ForeignPtrs k and v with a ForeginDependency
from k to v with coresponding C structurs ck and cv. this implied there
is a C pointer from inside ck to cv. lets look at the cases

case 1:
k alive
v dead
this is invalid since the ForeignDependency from k -> v keeps v alive,
nothing is collected.  so this turns into
k alive
v alive

case 2:
k dead
v alive
k is finalized, v is not and perhaps reused. also okay since cv can
exist independently of ck (and perhaps might be shared by several C
structures) and will be finalized at some later point

case 3:
k dead 
v dead
now, what order do you run the finalizers in? it doesnt matter, if v is
finalized first, then obviously k is no longer valid, __but since k is
dead we already know it will not be touched again__. if the opposite
order is chosen, then it is equivalant to the second case above.



now, a cycle doesnt matter, imagine a two cycle between a and b. that
just means that as long as either is alive they both are alive. if they
both are dead, they both are dead and their finalizers can run in any
order.

note, that this is equivalant to what ghc Weak pointers do,
(except weak pointers may be applied to any values, rather than just
ForeignPtrs)
addForeginDependency k v = mkWeak k v Nothing
is a suitable implementation.

I will save the talk of 'breaking ForeignDependencies' for another mail
as it is an independant issue.


references:
http://haskell.cs.yale.edu/ghc/docs/latest/html/base/System.Mem.Weak.html
(although you can ignore most of the complexity of this since we wont
want to add finalizers)

-- 
---------------------------------------------------------------------------
John Meacham - California Institute of Technology, Alum. - john at foo.net
---------------------------------------------------------------------------