Path: utzoo!attcan!uunet!crdgw1!uakari.primate.wisc.edu!zaphod.mps.ohio-state.edu!wuarchive!cs.utexas.edu!yale!cmcl2!lanl!jlg
From: jlg@lanl.gov (Jim Giles)
Newsgroups: comp.lang.misc
Subject: Re: C's sins of commission
Message-ID: <65665@lanl.gov>
Date: 13 Oct 90 00:46:59 GMT
References: <1990Oct11.100302.19258@maths.nott.ac.uk>
Organization: Los Alamos Natl Lab, Los Alamos, N.M.
Lines: 32

From article <1990Oct11.100302.19258@maths.nott.ac.uk>, by anw@maths.nott.ac.uk (Dr A. N. Walker):
> In article <1224@exodus.Eng.Sun.COM> chased@rbbb.Eng.Sun.COM
> (David Chase) writes:
>> [...]								In C,
>>C++, Pascal, Modula-2, BCPL, and PL/1, the programmer is responsible
>>for ensuring that whatever the pointer points to is not reused while
>>the pointer is in use.  Getting this wrong leads to messy bugs [...]
> 
> 	In sensible languages (like Algol), storage allocation and,
> more importantly, deallocation is monitored by the compiler and the
> run-time support.  So this bug is detected mostly as a compilation
> error, occasionally as a run-time fault, but in any case *when it
> happens*, not when the program inexplicably fails some time later.

Yes.  But at considerable overhead.  The fastest method I know of is a
reference counting scheme which is order (N+M*C); where N is the number
of nodes descended from the pointer being monitored, M is the number of
edges in the structure connecting those N nodes, and C is the number of
simple cycles in the structure (a simple cycle is one which either
entirely contains each cycle which overlaps it or which is entirely
contained within each overlapping cycle).

Note that this issue arises identically for recursive data structures
which allow aliasing.  So this technique is equally applicable (or
expensive) regardless of whether the pointers involved are explicit
or not.  In fact, for my language feature (the 'aliased' attribute),
the user must either take the responsibility for explicitly allocating
and deallocating them or he must pay the overhead for an automatic
maintenence of them.  This is why 'aliased' is optional and is off
by default (among other reasons).

J. Giles