[mercury-users] Automatic Recognition of Uniqueness

[Andrew Bromage]

G'day all.

On 09-Sep-1998, Ralph Becket <rwab1 at cam.sri.com> wrote:

> > Or is this what people mean by compile-time garbage collection?

Fergus Henderson wrote:

> Yes, that's basically what people usually mean by compile-time garbage
> collection.

There are actually two things that I've heard called "compile-time
garbage collection".

The definition that might spring to mind first is freeing up memory
(i.e. inserting free()-like operations into the generated code) for
structures which are known to be globally dead.  After all, freeing
memory is what garbage collection does, right?  Doing it at
compile-time therefore must be compile-time garbage collection.

This is what we (internally in the Mercury team) call compile-time
garbage collection.

>From an implementation point of view, freeing up memory in this way
only really makes sense if you're using a malloc-style allocation
scheme, where you actually _can_ free structures.  In Hans Boehm's
conservative GC (which is what we use by default) that works, however
the Mercury native garbage collector, which is in development as we
speak, won't support this operation.

What Ralph proposes we internally call "structure reuse", where
structures which are globally dead can be reused for later
constructions.

The analyses for both CTGC and structure reuse are almost identical.
The only difference is that for structure reuse you need some extra
(but quite easy to work out) information to tell how much of the
structure has to be reconstructed.  Consider the forward destructive
mode of append:

	:- pred append(list(T), list(T), list(T)).
	:- mode append(di, di, uo) is det.

	append(Xs, Ys, Zs) :-
		(
			Xs = [],
			Zs = Ys
		;
			Xs = [X | Xs1],		% This '.'/2 dies here
			append(Xs1, Ys, Zs1),
			Zs = [X | Zs1]
		).

The compiler should be able to work out that to reconstruct Zs from Xs
in the second clause, you only have to clobber the tail of Xs with Zs1.
You don't need to change the head, nor the tag.

> Andrew Bromage has been working on fixing the limitations in the analysis
> and Simon Taylor has been working on getting the compiler to take advantage
> of it to do update-in-place for user-defined data structures.  These changes
> are nearly ready, I believe, but they won't make it into release 0.8.

Yes.  Most of the changes are still quite beta.  It would be unreasonable
to unleash an extremely unstable compiler on an unsuspecting user
community. :-)

Cheers,
Andrew Bromage