Kernel LISP - how low down can it go?

[Dave Hudson]

On Wed, 21 May 1997, Dwight Hughes wrote:

> | 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.

Unfortunately of course the x86 isn't a word aligned architecture so 
things like exception handlers will need to be able to get at the full 32 
bits (this is one reason why I picked this as an example in fact).

> 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.

The idea of having the tags and dynamic typing is something that attracted
me to the idea of using Lisp in the first place.  All I was wondering was
if anyone had a handle on how much performance loss I might expect to see
from using them within an OS environment.  I'm sure that there are lots of
examples of relative performance between say C and Lisp at an application
level, but I've found that OS performance considerations can often be
somewhat different.  My other query is that if I wanted to be able to 
support dynamic typing all the way down (and not use any explicit static 
typing if I can avoid it), how much of a runtime system would I need that 
couldn't be coded in Lisp?

> 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 like challenges - especially where it involves taking code down to the 
lowest levels of the hardware.

> 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.

I don't like the assembler idea much either - my last OS development,
Artemis, used very little assembler code.  All that was needed was some
code to handle the entries and exits of system calls, ISRs and processor
traps, some CPU initialisation and context switching - everything else was
done in C.  I know from when I did this that my next OS development would
have to be at least as easy to modify (and preferable more so), but that
I'd like to have more control over the language implementation than gcc
was giving me. 

I'm starting to wonder if a new dialect of Lisp might not end up being
necessary for the low level stuff anyway?  Whenever I think about some of
the issues surrounding CPU traps or memory management I don't seem to be
able to think of a way of getting these facilities without going to a 
lower level than that provided by CL.  If this lower level isn't 
assembler then it must be some intermediate language.  I've always 
suspected that this might be the case (if anyone's read the plan I put on 
my web site for a project called Constellation they'll see this), but I 
was sort of hoping that someone would say something like: "well about 15 
years ago we built a LispM with 1k lines of assembler and everything else 
in Lisp" :-/

> 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 ....

This is the sort of reasoning I've applied with OS developments before - 
I've found that the really minimalist approach to kernel designs 
advocated by the designers of things like QNX and Exokernel leads to good 
base level systems that can be built upon.

> 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.)

I think one thing to be careful about is saying that C code is wonderfully
portable and that we would have to be aware of this if we were to invent
our own C-like Lisp for low level stuff.  My own experience is that whilst
a lot of C at an application level can be very portable, all of that
portability goes out of the window as soon as we start to manipulate the
hardware.


						Regards,
						Dave