muenx@heike.informatik.uni-dortmund.de (Holger Muenx) (11/01/90)
Hi...
I just started to implement another functional programming language. It
contains lists which are done similar to Scheme's CONS - CAR - CDR.
Now let's have a tree T with left and right subtrees L and R. The final tree T
obviously can be contructed by something like T = (CONS L R). Let's assume the
evalution order is left-most-inner-most. So first the subtree L is
constructed, then subtree R and finally the CONS shown above is executed.
Here comes my question: What happens if the construction of L is finished and
the system realizes while dealing with R that there is no more space available?
Of course, garbage collection is started. But there is no reference to
the left subtree because it is ready constructed and hold only in some intern
register or stack of the underlying language. All contents of L will be
regarded as unused of the garbage collection algorithm.
It is simple to see that it is not enough to have a global register which
contains the CAR of a pair while constructing the CDR. My next idea was the
brute force approach: I had a additional stack on which I pushed explicitely
everything to which there were no other reference and which could be destroyed
by garbage collection although it is no garbage. While garbage collection I
used the references on the stack as roots of used cell trees too. It worked but
unfortunately this creates much expense and is susceptible for mistakes.
I am sure that there is a more elegant solution which I have not considered
yet. Any idea?
Thanks in advance,
-Holger
===========================================================================
|| Holger Muenx, IRB, Universitaet Dortmund, 4600 Dortmund, West-Germany ||
|| Internet: muenx@heike.informatik.uni-dortmund.de ||
===========================================================================