[gclist] Reference counting on the fingers of one thumb.

John Carter john@dwaf-hri.pwv.gov.za
Tue, 14 Jan 1997 09:31:37 +0200 (SAT)

Greetings Collectors,

And thanks for the response, I have learnt a lot and once I follow all
the references, (more than one ;-), I will learn more.  Ah well, the
idea can't be that bad if everybody else has already thought of
it.... ;-)

Now onto some more itemize responses..

Greg Colvin greg@imrgold.com wrtoe :-
>The C++ draft has an auto_ptr template with semantics rather like your 
>one-thumb approach.  As the proposer of that class I don't mind saying that 
>it was not really a success -- mainly due to obscure interactions between 
>assignment, temporaries, and constness -- but the idea might be workable in 
>another language.  I don't see it as a replacement for garbage collection, 
>but just as an idiom that makes gc unnecessary for those programs that can 
>be expressed in that idiom.

I would explicitly expect my idea to fail in a C++ environment because
of the highly inconsistent semantics of the assignment operator and
the presence of the & operator. That is why I say the semantics of the
assignment operator has to be cleaned up first. (Not to mention that
C++ seems to grapple with the problem of temporaries and leave the
area defeated. Maybe I'm misreading the (not-the-latest) draft
standard.)  I entirely agree with you that it is an idiom that makes
GC unnecessary for largish areas that don't need GC. However, I do not
see it as precluding the possibility of GC.

But I will battle this issue more in response to Mauk...

From: "Mauk van der Laan" <maatwerk@euronet.nl>

>I don't think that such a redesign is nessesary to solve the GC
I don't think so either. GC is a solved problem, people are just
polishing up the brass work. (By gorrah, it is really shining fit to
blind these days compared to the very early implementations I met.)

My aim is an extra swipe of polish that achieves two things...
a) Cheap GC where full fledge GC is not needed.
b) A more reliable programming environment.

Let me state categorically where I'm coming from. I believe the most
important unsolved problem in computing is program reliability. I also
believe that it is in general unsolvable, but amenable to a variety of
"immunization" procedures. (GC is one of them, strict typing another,
"one-object-one-place" my idea for yet another...)

>The 'one-thing-one-place' paradigm is also valid in current languages.
NO! It is trivial, almost unavoidable to end up with objects having
many different names in most languages. I try to keep my own programs
fairly clean, but I know I can't do it in C++.

> And that is a strength that you are removing now. 
> Several common structures need multiple pointers.  
It is not a strength to create  spurious aliases all over the place. If
semantically that is what you mean, no problem. But if it happens 
unintentionally, it is an undetected bug that may go undetected for
many years.

>How are you building efficient linked lists? Are you going
>to pass a reference to an object as a pair of (array,index) values?
I envisage say the archetype list namely the LISP style lists as
follows :-
An object that two instance variables, one an array of arbitary objects 
and the other an integer index to the root of the array. The array
holds nodes that have pairs of integer indices into itself. One could
even build intelligence into the "add( Object)" method that will do a
GC if the array is full, requesting more storage if the GC fails. (OK,
so I will admit not being too concrete on this, it is hard to write the
library when the language design hasn't been done... (Come to think of
it, the converse is equally true...))

>Do you mean to do this only on objects, or also on simple data types
>(integers).  What does this do in your language:
>	type a(10)
>	type b = a
>In a true OO language as C++, <type> could be either simple types or
>objects, you cant treat
>them differently.

I'm _so_ glad you mention _this_ example and _this_ language.

The answer with C++ is you never know what the hell "b=a" actually
means without checking first whether :-
a) a and b are scalar. (It then means copy.)
b) b pointer and a an array. (It means copy a pointer to the base 
of the array.)
c) a and b are structs. (Its means shallow copy, ie. weirdly enough,
copy any enclosed arrays, and pointers, but not what the pointers are
pointing to.)
d) a and b are members of a class. The you have to check :-
  i. Does b have a non-trivial operator=()? If so do whatever that
does. (Even if what it does, is in fact, draw mickey mouse on the screen!) 
  ii. Does b have a non-trivial copy constructor? If so do whatever
that does.
  iii. Otherwise treat like a struct and do a shallow copy.
(Ps. Don't forget is a and b are different classes, any number of
impromptu conversions courtesy of operator=()'s and constructors of
that class or any ancestor class may be triggered.(PPS: Don't forget
you will have to dig these tidbits of info out of upteem dozen
"#include"'s some of which are switched in or out according to
preprocessor time #ifdef statements. Believe me, I've done this often enough
to have a religious fear of the process.))

In my language the semantics would be brutally simple. Deepcopy. Copy the
object and Deepcopy any subobjects.

From: James McCartney <james@clyde.as.utexas.edu>
>Its been done.
>There is a graph reduction functional language called Rewrite
>that was written for the Mac that has only use once objects.
Sigh! I don't have a Mac, but I will indeed have a look at it. Thanks
for note, do you have any reference? ftp address?

From: Daniel Wang <danwang@CS.Princeton.EDU>
>What you have sounds an awful like linear types/linear logics. Linear types
>have been studie quite a bit and there's been a good deal of theoretical
>work in this area. 
A couple of folks mentioned this in p/email, the answer is it seems a nice
idea theoretically, I would agree, I can think of lots of nice
properties these things would have when it comes to proving
correctness. I also would like to make it a practical thing as well. I
believe most of most programs can be written entirely on this basis
with the hairier structures neatly encapsulated in their own address
space. As I say, I coming at this from the point of view that program
reliability is what matters.

Any way I will indeed look at them. Thanks.

From: Eliot Moss <moss@rhea.cs.umass.edu>

>There's a major problem with your proposal, from my point of view. All you
>have done is push the gc problem off a level and back into the programmer's
Correct. But not necessarily onto the programmers lap. Onto the library
writers lap. Thus one program can use mark&sweep and colouring and
and conservative and whatever is applicable for each type of object
used. Also the GC becomes localized, sweeping through smallish
containers instead of all memory, most of which doesn't need collecting. 

>In fact, you have made the problem _harder_ than it is in other languages,
>since the pointer type in most other language is distinguished from integers,
>whereas you make no such distinction. 

I have bellyached muchly over this my self. I can, as was also
suggested by "Jon S Anthony <jsa@alexandria.organon.com>", make
pointers a derivative type of integers. (Thinks; what does this mean?
It encodes the object type pointed to, in the type information. Why
stop there? How about also a "weak pointer" to the container to make
sure it is not misapplied to the wrong container? Hmm. On the other
hand, part of the joy of an index is that they are just integers and
you can treat 'em as such, and can use them on other containers for
nefarious and unsafe purposes. Hmm. Details details details. Anybody
with firm opinions on this? My guess is a mix maybe? This issue must
have been argued to death back when they designed C and the pointer
arithmetic operations. Anybody with long memories? (Long memories are
needed, I keep meeting people, (not in this forum), that have
forgotten/were never told/were asleep in that lecture/... why we do
structured programming...))

From: hbaker@netcom.com (Henry G. Baker)
>There has been a lot of recent work on this idea in the context of
>'linear logic', but the idea is (of course) much older than that.
>Rather than attempt to give a comprehensive bibliography here, I will
>simply point to a number of notes that I have written on the subject:
>LFrpoly.html, LQsort.html, LRefCounts.html, LinearLisp.html
>(all of these papers are also available as .ps.Z)
Thanks as soon as my WWW connection is function again I will. An many
thanks for putting your papers online. Let me make this point crystal

People in non-first world, or not in richly funded university
positions have much trouble in accessing the published literature
body. (In case you wondering, this means 99.99% of us). Journals in
specialized areas are too ruddy expensive in foreign currency to
maintain unless absolutely essential to the head honsho (he/she with the
grant). Thus the internet / WWW has become an indispensible access
route. Maybe Web publishing isn't "Officially" peer reviewed, but it
is in effect. (I already have recieved recommendations to "look at
Henry Baker's work").

Thus people who take that extra bit of trouble and put their papers on
the Web are performing an inestimiable service to the larger scientific
community. Thanks again. And thanks to the FAQ compilers.

>types).  This language is called Clean, and I think that it may
>be downloadable for free.  See ftp.cs.kun.nl/pub/Clean/
Will do.

John Carter                    EMail: ece@dwaf-hri.pwv.gov.za
Telephone : 27-12-808-0374x194 Fax:- 27-12-808-0338

Founder of the Council for Unnatural Scientists.