Re: Garbage collector necessary (for Ada access types)?

[cis.ohio-state.edu!news.sei.cmu.edu!bb3.andrew.cmu.edu!crabapple.srv.cs.c mu.edu!monnier@ucbvax.Berkeley.EDU (Stefan Monnier)]

In article <aecolley.736460217@unix1.tcd.ie> aecolley@unix1.tcd.ie (Adrian Coll
ey) writes:
>I want to write an Ada-to-ANSI-C transpiler.   Most of this seems
>possible, if not straightforward (even tasks).  My problem is how
>to handle deallocation of memory objects.
>
>Reference counting is out: a ring of records each containing pointers
>to one another would each have positive refcounts, even when
>inaccessible.  Deallocating objects when the access type definition
>goes out of scope is another non-starter - most access types are
>declared with permanent lifetime (in package specifications as
>private types) so deallocation will never happen.
>
>Garbage collection seems to be an obvious way to solve it, but for
>the usual reasons (elegance, efficiency etc.) I want to avoid this
>if at all possible.

Ouch !
Just try to decide all this at compile-time, and look at your code.
I'm sure your notion of elegance will change :-)

(I won't insist on the efficiency argument. Just to say that GC
doesn't seem to require much more time than explicit deallocation)

>Is there any proven method of analysing a program to tell the "right
>time" to deallocate a value ?  Is this an instance of the halting
>problem or other impossible problem ?

What you want is called "compile-time GC". It is in general impossible
to do. What is meant by 'compile-time GC' in reality is to analyse the
code so as to determine what (and when) can be explicitely
deallocated. The rest will be handled by a run-time GC.

If you really don't want a real GC, I guess reference counting will
buy you more (for less work) than compile-time GC.

>Replies to me.  References to famous/obscure papers or reports welcome.
>A summary will follow if there's anything worth summarising.
>
>--Adrian.

If you don't want to spend too much time in your compiler just for the
GC problem (emitting code so that the GC knows what is a pointer andwhat
is not), you can use a conservative GC (you can even use 'ready-to-go'
ones for C: it replaces the malloc and the mfree becomes useless). But
beware its limitations: such GC is generally slower and doesn't guarantee
you won't have "memory leaks".


	Stefan