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 ||
===========================================================================gyro@CYMBAL.REASONING.COM (Scott Layson Burson) (11/03/90)
Date: 1 Nov 90 14:34:06 GMT From: Holger Muenx <mcsun!unido!laura!heike.informatik.uni-dortmund.de!muenx@uunet.uu.net> 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? You are basically on the right track. The only improvement that I know of to the approach you are taking is to arrange to be able to scan the CPU control stack and registers to find roots, so they do not have to be kept on a separate stack. I don't know of anyone who has successfully done this without writing their own native-code compiler (and even then it can be quite tricky to get right, as you might imagine). Oh, as I reread your message I see that I may have misunderstood. When you say you "pushed explicitly" the objects onto the root stack, do you mean "explicitly" in the sense of doing this in user code, or in the sense of having the interpreter do it? In Scheme and other Lisps this job is handled automatically by the interpreter, so the user doesn't have to think about it. Maybe that's what you meant. This problem of needing to be able to find roots just might be the most subtle aspect of Lisp implementation design, and the one with the most pervasive effects, in the sense that you have to set up certain conventions you will follow and then make sure they are adhered to throughout the system. Do not despair. The problem really is as hard as it looks, but it has also been solved numerous times and in numerous ways. -- Scott