Kernel LISP - how low down can it go?

[Dwight Hughes]

| From: Dave Hudson <dave@humbug.demon.co.uk>

  [  snip  ]

| As an example, with C on a 386 I can use the full 32 bits of a register
to
| store value information since everything is statically typed.  This lets
| me do interesting things with say virtual memory and exception handling
| (e.g. I can get the address of a faulting instruction).  If I now move to
| a dynamically typed language such as Scheme (I appologise now for my lack
| of knowledge of CL) I either need to create a new primitive type that can
| give me 32 bits still whilst still providing a type tag or I need to use
| some sort of language dialect that uses type inference (something like
| Infer say).

While getting a full 32 bits within Lisp is a bit difficult, if your tag
for integers is to make the lowest order bit 0 (or make the two lowest
order bits 0) this covers the majority of uses you will have for
addressing or bitwise logic in a 32 bit word aligned architecture.
You can also use the integers directly without masking out the tag
for general arithmetic. If you didn't mind explicit typing, Lisp
could generate code as efficient as C for this setup, though there
may be some limitations I've not considered.
 
| Clearly in the first case I end up with something that's inherently more
| expensive to use (than I'd get with C) whilst the second doesn't really
| give me the language I want (I obviously want dynamic typing).  A third
| alternative might be to do most of the exception handling in some sort
| of assembler micro-kernel and then pass the details back out to the Lisp
| code in a different way.
| 
| Is there a fourth alternative that I don't know of (or didn't think of)?

Well, the true Kernel Lisp would probably have to support explicit typing
and you would probably have to use it to get efficiency at the lowest
level. You could probably deal with tags for a compound object rather
efficiently - an object header word that tags a byte vector, 16 bit word
vector, 32 bit word vector, etc. and have efficient operations defined
for those within the Lisp compiler. At the cost of some memory you
regain the efficiency of C for most operations and you still have the
safety of tags (objects all the way down), one of the primary reasons
we want to do a LispOS anyway -- after all, fandango on core is not as
much fun as it sounds.

| Along a similar line, someone on this list (I think it was Henry Baker) 
| commented that they'd like to implement some of the GC in Lisp - wouldn't

| this run into the same sort of problems (i.e. the dynamically-typed Lisp 
| code would inherently run much slower than an assembler version would
do)?
| 
| I would think that a similar argument must be true for the idea of making

| bignums out of fixnums?

BTW, in some Lisps, bignums are simply vectors of fixnums. Not really my
idea of elegance in implementation, but whatever.

| If I understand it correctly, this sort of thing wasn't so much of an
| issue with the original Lisp machines because they had hardware support
| for type tagging.

True, and 36 or 40 bit words.

| Does anyone know of any tricks that allow me to hit the sort of C
| performance levels, or anywhere where I might be able to find such
| information?  Alternatively, if the answer is to resort to a core
| assembler runtime system, does anyone have any ideas on what it ought to
| contain? 

For higher level work good CL compilers can in fact equal or exceed the
performance of optimized C (CMU-CL can do this on some RISC based
CPUs, though not (yet) the x86 family). At the lowest levels, well,
that's why we are having this Kernel Lisp discussion isn't it? Reaching
the goal of Lisp-to-the-metal, without compromises, on vanilla hardware
will be challenging.

I *really* don't like the idea of using assembly for the runtime. For
one, it is hell to write and to change -- the LispOS needs room to easily
evolve and change from bottom to top. For another, the assembly portions
will be as opaque as hardware to the higher level LispOS. We want to
be able to change and update and fix *everything* from within the LispOS.
To get there I think we will need to either define a new dialect of Lisp
or a specialized extended subset of CL to get down to the hardware
efficiently.

To answer your question about what the runtime should contain - as little
as possible ;). Seriously, what it will contain will need to change and
evolve
with the LispOS. Much has been said about what the LispOS should be, but
not much about what it must have at the beginning. We need to start as
simple as we can and plan the evolutionary stages needed to finally create
what we desire. Complex systems that work well derive from simpler systems
that work well, which derive from ....

| BTW please don't think I'm knocking Lisp here (vs C) - if the answer is 
| that I need to live with the performance losses then fine, but I'd like 
| to try and understand the size of any losses sooner rather than later.

Until we develop the tools and techniques we need, if we can create the
needed structures in C without propagating "C-ness" into the LispOS
environment, then we should do so. This will also help us define
what the minimum runtime should be. We will need assembly for some
things, but this should be ruthlessly minimized (I want to run the
LispOS on PowerPC and Alpha boxes too, without having to completely redo
everything). (No the C part would not be any less opaque than the
assembly code to the LispOS, but it would be a hell of a lot easier
to change and to port.)

-- Dwight