🚀 go-pugleaf

In article <677@tuvie> brock%tuvie.UUCP@mcvax (Inst.f.Prakt.Info 1802)
Ulrich Neumerkel asks:

>   1. Does anybody know some reports about its realisation?

There is an internal MIT report:
   Sharon E. Perl
   "VAX CLU Implementation Notes"
   MIT Laboratory for Computer Science, DSG Note 124, 29 November 1984.
This describes many aspects of the VAX CLU implementation including the
mark-sweep garbage collector. You could obtain this from Barbara Liskov's
group at MIT.

>   2. Immutable objects seem to be an ideal area to implement much more
>   sophisticated storage allocation mechanisms than simple GC-algs: Consider
>   two independently created sequences, structures or oneofs which are
>   occasionally identical. The GC could remove one of them as one can be
>   replaced with no effect by the others. ... has anybody considered this
>   problem?

I have not seen this suggested for CLU, but it has been proposed for
functional languages. In particular see:
    William Stoye
    "The Implementation of Functional Languages Using Custom Hardware"
    University of Cambridge Computer Laboratory
    Technical Report 81, (Thesis), December 1985, p 4.7.
A different approach is the hashing cons provided in some functional language
systems.

>   Ulrich Neumerkel (ulrich@vip.UUCP  UUCP: ...!mcvax!tuvie!vip!ulrich)

Robert Cooper (rcbc@cs.cornell.edu)

> 1) Does anybody know some reports about [CLU GC's] realisation?

There is a MIT internal document on the implementation of CLU.  I can't
remember its title (and my copy has gone walkabout), but the author
is Sharon Pearl.

Among the gems of useful information in this note are a description
of CLU object formats and an outline of the garbage collection algorithm.

> 2) [Suggestion to have the GC replace identical instances of an imutable
> type with one instance]

In most real cases this optimisation would give little space saving.
On the down side, the runtime cost would be considerable.  Every heap
node would need a type field which would need to be initialised, the
GC would need to do extra work for every node (i.e. to check if it was
immutable).  Finally for each immutable type (with N instances), it will
cost a minumum of order N (when all instamces are identical) and probably
Nlog(N) to eliminate the duplicates.  The duplicate elimination algorithm
would need to be applied of times to get optimal space saving.

There are also "theological" issues here.  Are two equal valued but
distinct instances of an immutable type truely identical?  If you stick
to the operations defined in the CLU RM, they probably are.  But if you
use some of the other code supplied by MIT (e.g. the _cvt function), equal
valued instances of an immutable type are distinguishable.

[I admit it ... I'm a hacker :-)]

-- Steve