Re: Storage management, was Compiler writers will love this language

nmm1@cus.cam.ac.uk (Nick Maclaren) wrote:


>|> I don't believe anyone has ever fixed the cyclic graph problem with
>|> reference-counting.
>
>As it is theoretically impossible to fix, that seems likely :-)


It is not impossible to make versions (but not pure ref count) that can
trace cyclicity in some circumstances:


I thought of a variation building on Tarjan's strongly connected
components (SCC) algorithm:
        http://www1.ics.uci.edu/~eppstein/161/960220.html#sca


This works so that the objects are numbered consecutively as they are
created. A cycle can then be detected if it points to another object with
(depending on the setup) higher/lower number, which can be used to adjust
the ref count so that deletion takes place appropriately also in cycles
(which initially must have some external ref pointing at them). A problem
arises though if, after an initial setup of references have been achieved,
they are relocated dynamically, creating new cycles. That is hard to track
down. But if that does not happen, one can make a version building on this
SCC algorithm to remove the cycles as well (or so I remember).


If one should get around this dynamically created cycles problem, perhaps
one ends up on essentially a tracing algorithm.


    Hans Aberg * Anti-spam: remove "remove." from email address.
                                    * Email: Hans Aberg <remove.haberg@member.ams.org>
                                    * Home Page: <http://www.math.su.se/~haberg/>
                                    * AMS member listing: <http://www.ams.org/cml/>

Return to the comp.compilers page.
Search the comp.compilers archives again.