[gclist] Java manchines and when to collect.

[Paul Haahr]

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:

  http://research.microsoft.com/research/cambridge/luca/Papers/TypefulProg.ps

(A4 and PDF variants of the paper are available from the same location.)

Paul