Re: Compiler writers will love this language

On 20 Jun 2003 00:02:55 -0400, Eric posted:
> mwotton@cse.unsw.edu.au (Mark Alexander Wotton) wrote
>>
>> Either that, or only released when all references to it have passed
>> out of scope. This is how many modern garbage-collected language
>> implementations work.
>
> This scheme (reference-counting) is used in VB6 for instance.


Reference counting and mark-and-sweep are just ways of implementing the basic
idea of deallocating when references are out of scope.


> VB7 (and every other .NET language?) uses generational,
> mark-and-sweep GC (hope that's the right term for it). When I read
> its description, it sounded like a rather elaborate scheme and one
> that would need a good deal of implementation effort. I prefer plain
> vanilla automatic reference-counting. Its deterministic (hence
> useful in real-time systems), simple to explain and understand, and
> a lot easier to implement and get right.


You do have the problem with reference-counting that it doesn't cope
very well with two-way links. Generational collection is nice partly
because it's complete (all unused allocations are reclaimed), and also
because it takes advantage of common memory use patterns: it's
optimised for the case of new objects pointing to old objects, which
is the usual case.


> I admit, reference-counting has its problems and I have been toying
> around with an idea for what I call "compile-time
> reference-counting". Basically, I am looking for a set of rules,
> that will allow the compiler to figure out when to release memory
> for an object, *without* having to allocate memory space for a
> reference counter value. Instead, using these rules, the compiler
> can analyse code at compile time and statically work out the
> life-time of an object. Its a bit wishy washy at the moment but if
> its at all possible, I will write a paper on it :)


It smells a bit undecidable to me. At least for the complete case, I think
this reduces to the halting problem.


    Object foo(Object x, Object y) {
if (halts(x)) {
return y;
} else {
return x;
}
    }


When do you release x's memory?


You may be able to find some decent heuristics, but I suspect it's a lot
harder than it looks.


mrak

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