It seems quite natural that someone who writes a Common Lisp system would
  write its guts in some other language first.  After a while, it would be
  possible to bootstrap the building process in the system itself, but it
  would seem natural to build some lower-level Lisp that would enable a
  highly portable substrate to be written, and then cross-compilation would
  be a breeze, but it still seems fairly reasonable to start off with a
  different compiler or language if you want anybody to repeat the building
  process from scratch, not just for GC, but for the initial substrate.  I
  remember having to compile GNU CC on SPARC with the SunOS-supplied C
  compiler and then with the GNU CC thus built, in order to arrive at a
  "native build" and that when Sun stopped shipping compilers with their
  application-only operating system, someone was nice enough to make
  binaries available for the rest of the world.

  Why is GC so special in your view?

Consider that the various Unix kernels out there do NOT use "all of
C;" they use subsets that on the one hand likely permit all the
_operators_ and control structures of the base language, but which
_EXCLUDE_ great gobs of "The Standard C Library," notably anything
that forcibly depends on malloc().

One of the Frequently Asked Questions about Linux is "So why don't you
port it to C++?  Wouldn't that make it lots better?"

The _real_ answer to that:  "Because the developers prefer C."

But another pointed reason not to is that C++ subsumes into the base
language a bunch of stuff that, in C, is part of LIBC, and, which, in
many cases, depends on having malloc()/free() (or equivalents thereof)
around to do their work, what with constructors and destructors and
the like.

In order to build an OS kernel in C++, you have to very carefully pick
a subset that doesn't require any underlying "runtime support."  By
the time you gut C++ that way, what you've got is basically C with
classes, and there's little point to calling it a "C++-based OS."

With Lisp, it's much the same story; you will at the "base" have to
have some basic set of functions and operations that DO NOT REQUIRE
RUNTIME SUPPORT, because the point of the exercise is to _implement_
that runtime support.

This actually suggests there being merit to the hoary question of
"What's a good `base CL?'" where you bootstrap with some minimal set
of operators, functions, and macros, and then implement the rest of
the system on top of that.

A necessary "base" would include some basic set of operators/functions
necessary for writing the garbage collector which do not themselves
make any use of dynamic memory allocation.  [Might this mean that the
'base' would exclusively use stack-based memory allocation?  I'd tend
to think so...]

The notion that the system could bootstrap itself without that limited
'base' seems very wishful.

I'll bet an interesting OS to look at would be SPIN, which was
implemented in Modula-3.  M3 offers the same "chewy garbage collection
goodness" of Lisp; presumably the SPIN kernel has to have certain
sections that implement the "memory management runtime support" in
such a way that they require no such runtime support.

Forth would be another candidate; one of the longstanding traditions
there is the notion of implementing "target compilers" which start
with a basic set of CODE words (e.g. - assembly language) and then use
that as a bootstrap on top of which to implement the rest of the
language.  

That actually points to a somewhat reasonable approach:
 - Write a function that issues assembly language instructions
   into a function;
 - Write some functions that issue groups of assembly language
   instructions ("macros" in the assembler sense);
 - Implement a set of memory management functions using that
   "bootstrap";
 - Then you've got the basis for implementing everything else on
   top of that.

(defun (setf car) (value cell)
  (check-type cell cons)
  (with-inline-assembly (:returns :eax)
    (:load-lexical cell :ebx)
    (:load-lexical value :eax)
    (:movl :eax (:ebx -1))))

  I actually tried to argue that the same would true of a Common Lisp
  system, but that portability constraints dictate that those who want to
  port a Common Lisp compiler to System X on the Y processor should be able
  to use the portable assembler (C) instead of having to start off writing
  non-portable assembler and use the system's assembler to bootstrap from.

  Needing *only* GCC, as you say, is predicated on the existence of a
  binary for your system to begin with.  How do people port GCC to a new
  platform om which they intend to build the GNU system?  My take on this
  is that it is no less dependent on some other existing C compiler than
  the similar problem for CL compilers is.  Duane, please help.  :)

Regards,
--
Nils Goesche
"Don't ask for whom the <CTRL-G> tolls."

There are Smalltalks (and lisps) that let you inline C or asm code...would
that be ok?

Or maybe read priveleges to it are root-only and root can set the
signing key for a particular installation -- but then you have a
problem that nobody can compile on one system and run on another.

Far far better to have potentially-dangerous processes running in
their own memory arenas where the OS can keep an eye on them in
case they try messing anything up.

  It sounds like _vastly_ more work than building on the native system with
  a native assembler and linker to build the first executables until you
  could replace those, too.  

  Back in the old days, I wrote 8080 and Z80 code on the PDP-10 and its
  cross-assembler for "microcomputers", because it was so fantastically
  more convenient to work on a real computer and deploy on a toy than work
  on the toy computer -- mostly all I did on the toy computer was to write
  an excellent terminal emulation program, in assembler.  However, the only
  reason this was more convenient was that it was a royal pain in the butt
  to try to use the toy computer for any development.  However, I had to
  copy the ROMs in that machine to the PDP-10 and basically regenerate its
  symbol table in order to make things work correctly.  Luckily, it had an
  emulator, and curiously, the PDP-10 emulated the code about 100 times
  faster than my toy computer executed it.  Were it not for the 100,000
  times difference in the cost of acquisition and ownership of the two
  computers, I would certainly have replaced my Exidy Sorcerer with a
  PDP-10.  Come to think of, my current home computer is strong enough to
  emulate a PDP-10 about 100 times faster than the real thing, too...

I went back and forth with Doug on this.  There are several issues you
need to think about:

-- If you use bit vectors, you pay for some shifting of bits etc.
   CMUCL actually generates somewhat suboptimal code for the X86 platform
   (and extra mask and returning a value that's not used)

-- If you use eight bit BYTE's and don't coerce the compiler to use machine
   integers to address the array.  You again pay for shifting for fixnum
   untagging.

-- If you use fixnums or machine integers (32 bit) fixnums can address
   them w/o untagging, and you get fast results BUT this is cheating (won't
   scale and it will spill over to L2 cache even with a small array.  Doug's
   machine has 1/2 speed L2 cache (P-II) so your results will vary if you
   have a full speed L2 (eg celeron will beat regular P-II).

this is about all I remember.  

There was also the additional issue of loop macro and declarations if
remember correctly.

Doug probably has a changelog of all this somewhere.  But disassemble and the
compiler trace facility of CMUCL should be helpful also.

cheers,

  This is probably doable, but in my experience with cross-compilation, you
  do not just generate code, you effectively generate a module that works
  with a much larger system.  To make this _really_ work, you have to have
  intimate knowledge of the target system.  Since the compiler is often the
  first thing you build on a new system in order to build the other tools
  you want to use there, my thinking is that you save a lot of time using a
  pre-existing compiler and like tool, particularly to ensure that you get
  the linking information right for that particular environment, what with
  all the shared library dependencies and whatnot.

But I'm thinking about a different problem space, not the one you are.

Thomas Bushnell's challenge is a good one.  And this thread has been
a good one, as well.  Several times I considered answering some of the
statements made on this thread, but have refrained because there are
so many issues and stochastic requirements.  So I thought I'd put
together several ideas and present them at once, from the point of
view of an Allegro CL developer.

As an initial summary, I submit that the entire lisp _could_ be
written entirely in lisp, but that it is not convenient to do so,
given the fact that we run our lisp on Unix and MS systems, which
are all C based, and even embedded systems tend to have libc
equivalent interfaces.  However, I do disagree that it is necessary
to require that the whole language be available for a GC written in
lisp, and will explain that later as well.

First, a background review of Allegro CL's structure, for those
who don't yet know:

 1. Most of Allegro CL is written in Allegro CL, and compiles per
architecture to bits (represented in code vector lisp objects)
using the Allegro CL compile and compile-file functions.

 2. A subsection of the kernel or "runtime" of Allegro CL is an
extension of CL I call runtime or "rs" code, which also use the
Allegro CL compiler, extended and hooked to produce assembler
source as output.

 3. Some small part of Allegro CL is written in C.  On some
architectures, the C++ compiler is used, but it is mostly written
in C style.  The major purpose of the C code is to parse the .h
header files of the system for the os interface.  We try mostly
to limit our C code to os-interface functionality and regularization.

In addition, as a kind of #3a: We also have written our garbage-collector
and our fasl-file reader in C.

The binaries from 2, 3, and 3a are all linked together using the system
linker to either produce a single executable, or to produce a simple
executable main and a shared-library.  In both cases, that link output
serves dual purpose as a bootstrap mechanism to load pure lisp code in
(i.e. from #1) or to re-estalish the environment dumped in a previous
lisp session.

The rs code in #2 is sort of a combination of superset/subset of regular
CL code; it understands both C and Lisp calling conventions, but does not
set up a "current function" for its own operation.  Since the produced
code is just assembler source, and does not set up a function object,
local constants are not allowed; only constants that are in the lisp's
global table can be referenced by rs code.  Recently, I added an
exception to this; string constants can now be represented in rs
code - these will become .asciz or equivalent directives in the
assembler source.  This allows such rs functions as

(def-runtime-q print-answer (n)
  (q-c-call printf "The answer is %d
" n))

I have also recently extended the rs code to allow for large
stack-allocated specialized arrays; we've always been able to
allocate stack-based simple-vectors in rs code, but due to the
rs code stack frame descriptors we provided for gc purposes, non-lisp
data had been restricted to a few hundred bytes until now.

Theoretically, due to these and other changes, we should now be
able to rewrite both the fasl reader and the garbage-collector
in rs code, but it hasn't been a high priority.  For the garbage
collector especially, there must be an incentive to make such a
potentially regressive move; it may be that a new gc to handle
concurrent MP might be just that incentive.

For #3, I was almost ready to disagree with Thomas Bushnell
because I believed that it is necessary to use C functionality
to interface to C library functions.  This is especially true
for the need to parse .h files, and to get the correct
definitions and interfaces based on particular #define constants.
If you doubt this, just try to figure out, for example, HP's
sigcontext structure, which has layer upon layer of C macrology
to define a large number of incompatible structure and interface
definitions.

However, I had to back off on any such disagreement, becuase it
certainly is _possible_ to write any of these interface functions
in lisp, using such facilities as our Cbind tool to pre-parse the
header files and to thus present all pertinent information to
the lisp-in-lisp code.  However, I still am not inclined to do such
a thing, because it would be specialized toward lisp bootstrap, and
thus not useful for anything else.  And why not use C at what it does
best (parse C header files)?  Besides, even our Cbind facility uses
the gcc front-end to do the initial parsing, so in essence a non-lisp
compiler part would still be used.  Bottom line; it is more convenient
to write our os-interface code in C, because it interfaces to C
libraries.  I suppose that we would remove such C interfaces if we
were porting our lisp to a Lisp operatring system.

Finally, I'd like to disagree wholeheartedly with the notion that
the full language must be available for the whole lisp implementation.
Specifically, I am responding to this point by Thomas Bushnell:

Let's extend this notion to an extensible language like Lisp.
Consider the start of a CL function foo:

(defun foo ()
   ...)

Now, the body of foo can refer to any CL functionality, including
foo itself.  However, it would generally be bad programming (i.e.
a bug) to allow a call to foo within foo which results in an
infinite recursion.  Thus, to some extent, foo is not fully
available to use as one wishes within foo.

Similar truths apply to a garbage-collector.  It might be
perfectly acceptable for a gc function to call cons, but it
had better be prepared to deal with the case where there is
no more room for a new cons cell, which would thus cause a
recursive call to the garbage-collector (presumably an infinite
recursion, since the reason for the initial gc call might have
been for lack of space).

And, as The Oracle in Matrix says, "What's really going to
bake your noodle ..." is that at least in CL, there is no
definition of what a garbage-collector actually _is_.  There are
a few references, but no definitions or specs...

But note that I began by asking about both Scheme and CL; the point is
that of course I could confine myself to a tiny subset of CL and do
things in PL/I (er, I mean "the loop macro").  

However, the real things I want are fairly simple:  I want complex
closures and I want cons.  I might want call/cc, at least, I'm not
willing to exclude that a priori.

A "pure" implementation means that you would do the same work the C
library people do, and make Lisp equivalents for the C header files
yourself.  Remember, *I'm* always thinking of this from a systems
design perspective, so "tell the other group to do the work" isn't
really a solution. :) But if the other group is doing the work anyway
(as is the case for people running a Lisp environment on Unix, then of
course, it's convenient to piggyback on them.

But why do that if there is a convenient solution?

One strategy:  suppose to GC an arena of N bytes takes N/10 bytes of
memory to hold dynamically allocated GC data structures.

One strategy is to just save that space always, so it's there.  Or, if
one is using stop-and-copy, then it's even easier to find space.