[gclist] Java manchines and when to collect.
Mon, 15 Dec 97 08:57:01 -0800 (PST)
Jeremy Fitzhardinge wrote, quoting Mark Tillotson:
> > In fact aren't there some interesting theoretical research issues in
> > designing type-systems that can be secure, and yet give a language
> > the power to write its own storage-manager/GC ??
> Yep. I suspect you need a considerably more powerful type system than
> Java's though, but I haven't really looked into it. Are there any
> languages which can implement their own storage manager?
I think the Boehm, et al, collector is an existence proof for C. But
there are fewer such things for type-safe languages. (The Lisp machines
might count, but how do you categorize the hardware support?)
Luca Cardelli had some interesting ideas on the matter, in his 1989
paper _Typeful Programming_. Quoting section 9, ``System Programs'':
As we mentioned in the introduction, a language cannot be considered
"real" unless it allows some form of low-level programming; for example
a "real" language should be able to express its own compiler, including
its own run-time system (memory allocation, garbage collection,
etc.). Most interesting systems, at some point, must get down to the bit
level. One can always arrange that these parts of the system are written
in some other language, but this is unsatisfactory. A better solution is
to allow these low-level parts to be written in some variation (a subset
with some special extensions) of the language at hand, and be clearly
marked as such. An extreme situation is the infamous "assembly language
insert", but one can find much better solutions that are relatively or
completely implementation-independent, that provide good checking, and
that localize responsibility when unpredicted behavior results. Some
such mechanisms are considered in this section.
In a language based on dynamic storage allocation and garbage
collection, how does one write a garbage collector? The solution
involves identifying an allocation-free subset of the language, and
writing the garbage collector in that subset. In other words, one must
distinguish between stack allocation, where storage is easily
reclaimed, and heap allocation, which requires collection.
He introduces a notion of ``still'' types which can be stack allocated
and restrictions on them, and then talks about the type safety
violations which might be necessary to support a garbage collector.
This is probably the most speculative part of the paper, but it's a
useful starting point. (It's also my favorite paper on programming
languages from the past decade. Bears up well to rereading.)
The paper is available at:
(A4 and PDF variants of the paper are available from the same location.)