Re: Compilers for systems programming (was: A C style compiler)

A bit more in response to Francois-Rene Rideau, who asked:
> As an important example, what language with automatic memory
> management could be used to *fully* implement its own (efficient) GC
> without hiding lots of details in custom hardware, or arbitrary
> software implementation choices?


I'll use Scheme as my example.


The implementor defines a subset of the language that will be used for
low-level systems programming and bootstrapping, making sure that the
compiler behaves predictably on this subset. For example, the subset
and compiler should have the property that no heap storage is
allocated except at syntactically obvious places, because you want to
avoid the infinite regress that would result from a heap storage
allocator that unexpectedly allocates heap storage.


For Scheme this subset might be the first order subset in which lambda
expressions are used only for top level definitions, rest arguments
are forbidden, and the library is restricted to operations that
translate into a small number of machine instructions. Writing a
garbage collector in this subset is just like writing a garbage
collector in C. If the subset also forbids non-tail calls to
non-primitive procedures, then it's just like writing a garbage
collector in assembly language.


Dr Richard A O'Keefe wrote:
> There was some work done on a Scheme system where the data
> representations &c were bound very late; I think that may have been
> done at Xerox too.


In dynamically typed and highly polymorphic languages, it is common to
represent all objects, or all objects except for those of some small
fixed set of primitive types (e.g. floating point numbers), using some
fixed number of bits, say 32 or 64. If all objects are represented
using the same number of bits, then everything that the compiler needs
to know about the language's types and representations can be packaged
up into a few tables: the type-checking and coercion rules, the side
effects, kill information, and register requirements for each
primitive operation, and so on. The compiler proper just knows how to
compile the core language, and how to clean up the target code
(e.g. instruction scheduling). Changing the representations used for
data has almost no impact on the compiler.


Will
--

Return to the comp.compilers page.
Search the comp.compilers archives again.