Interesting; I was about to post a similar inquiry myself. My own
interest is in developing a kernel-based Lisp dialect or derivative,
probably quite far from the mainstream dialects, which would be
suitable for very-low-level programming, specifically one which could
be used to write an operating system kernel in. I am not alone in
this; as many of you may know, there has long been an interest in
developing a 'LispOS' for stock IA-32 hardware. Some discussion of
this can be found, among other places, at
http://www.mega-tokyo.com/forum/index.php?board=1
My particular approach has been to define a very minimal subset of the
language, which would use a basic stack allocation method more typical
of procedural languages for local variables. This would be used to
implement a basic memory manager and process scheduler, which in turn
would be used to implement a kernel-level GC process which would 'comb
out' the memory of the other system processes.
One question then becomes whether it would be feasible to use the
automatic memory management as a library extension of the base
language, or if it would be necessary to separately implement a more
complete dialect which uses the memory manager natively. If it is
extended, would it be desirable to 'hide' the low-level tools from the
client programmer, and if so, how would you go about doing so (e.g.,
namespace control, alternative function names, etc).
Would a language like this be worth the effort, or would it be just C
with a Lisp-like syntax? Could it be implemented with suitable
efficiency? What advantages and disadvantages would it have over a
conventional systems language like C or Modula-2?
On a lower-level, assuming a stack-based function environment as
mentioned earlier, what would actually be pushed onto the stack - cons
pairs? Individual pointers? The immediate variables themselves? If a
pair is used, then how would the variables they point to be allocated
without a heap? How could one create lists without a heap (since stack
memory only exists while the function using it is in context)? Other
large or variable-sized values (i.e., bignums)? Or would it
effectively be limited to only non-persistent local variables of fixed
maximum size (and those declared globally)? Certainly languages like C
work in this mannner, but can a Lisp-like language work under such
constraints and still have the advantages of Lisp?
I was also wondering if anyone had ever attempted to write a Lisp-like
language using a threaded interpreter, rather than a conventional one,
and what results they had with it.
Is this a reasonable line of inquiry, or am I (and the others with
similiar design plans) going headed towards a dead end? What similiar
projects have existed in the past (I know of TUNES, but AFAICT they're
still going), and what results did they have?
From: cr88192
Subject: Re: Lisp for low-level Systems Programming (was Re: Lisp w/out GC)
Date:
Message-ID: <vvet56sj9gp806@corp.supernews.com>
"Jay Osako" <······@hotmail.com> wrote in message
·································@posting.google.com...
> Interesting; I was about to post a similar inquiry myself. My own
> interest is in developing a kernel-based Lisp dialect or derivative,
> probably quite far from the mainstream dialects, which would be
> suitable for very-low-level programming, specifically one which could
> be used to write an operating system kernel in. I am not alone in
> this; as many of you may know, there has long been an interest in
> developing a 'LispOS' for stock IA-32 hardware. Some discussion of
> this can be found, among other places, at
>
> http://www.mega-tokyo.com/forum/index.php?board=1
>
I had once tried to write a scheme os, however, the kernel was written in c
and was using an interpreter at the time (since then my dialect has become
compiled, but would still need some c or assembler code to form the
runtime...).
eventually, though, I tried a design change (moving all the interpreter/...
stuff to userspace). after that my os was quickly mutating into being yet
another unix, and I then decided (hell: if I want to continue I can just use
the linux kernel).
of course, that took out many of my main motivations for working on it (I
had also wanted to be creative on the gui and ipc fronts in ways that are
problematic, even with X11 and linux...).
if I use linux though, and continue using most gnu style stuff, what does
that gain? I would just have some of my own apps running on yet another
linux distro...
sadly, X11 is too much tied to linux to just replace that, but my ideals
would want a different kind of gui subsystem (actually something more
similar to a variation of a raw gl-style drawing system). I could build a
layer on top of X and just use full-screen gl, but conventional apps would
probably not play well with this (I would need to figure a way to direct X
connections to something I controlled and thus simulate the lower level X
functionality...).
similarly, my ipc ideas could be kludged on top of loop-back udp, in fact, I
have often been doing this on windows anyways with some of my projects...
it just seems too much work for too little gain.
thus, my efforts on that front are dead for an undetermined time scale.
of course, I admit, this is very much unrelated to what you were talking
about.
> My particular approach has been to define a very minimal subset of the
> language, which would use a basic stack allocation method more typical
> of procedural languages for local variables. This would be used to
> implement a basic memory manager and process scheduler, which in turn
> would be used to implement a kernel-level GC process which would 'comb
> out' the memory of the other system processes.
>
maybe, I can't really guage this though...
> One question then becomes whether it would be feasible to use the
> automatic memory management as a library extension of the base
> language, or if it would be necessary to separately implement a more
> complete dialect which uses the memory manager natively. If it is
> extended, would it be desirable to 'hide' the low-level tools from the
> client programmer, and if so, how would you go about doing so (e.g.,
> namespace control, alternative function names, etc).
>
what I would more wonder is:
is it feasible to make a dialect which can operate standalone (quite likely
restricting a good portion of the language+possible features), yet still try
to use it as a more complete/featureful dialect?
it could be possible, but it may be difficult to make it cover that much
ground. likely multiple dialects would be necessary.
if you are willing to still have some c code (or a larger amount of
assembler) then more features can be added to the base language but it is
then less standalone.
as an example: my scheme dialect could be used to write an os, but I would
still need a fairly large amount of c code to handle the stuff it can't
(basically the generic cpu level stuff, mmu+process management+gc, drivers,
...). but by this point what really is the use of a lisp in the kernel
besides being a gimick?...
a more minimalist and utilitarian dialect would be needed for actual kernel
programming...
> Would a language like this be worth the effort, or would it be just C
> with a Lisp-like syntax? Could it be implemented with suitable
> efficiency? What advantages and disadvantages would it have over a
> conventional systems language like C or Modula-2?
>
depends on what is kept and what is lost...
without gc and dynamic typing, it is a lot closer to being like c...
personally, I don't believe it is really possible to compete all that well
in c's domain with something that is not c...
it may be possible however, eg, if features like closures, lexical scoping,
gc, dynamic typing, ... can be retained without having an unjustifiably
large amount of c code (an example would be retaining, say, a more
minimalistic gc that operates within a permanently mapped area of memory) it
may then be possible to do things, including working with the mmu, handling
interrupts without possibly deadlocking the gc or such (with ints+port
io+raw memory access one can write drivers), ...
possibly then much of the kernel could be written in a lisp, and at the same
time preserve the features. this could be cool.
the problem then is justifying why it is being done...
in this respect I could not justify my efforts to myself, there is endless
work in making an os something useful. linux has been going for over a
decade, and is nearly impossible to catch up with.
I was stuck with:
a basic kernel;
an incomplete c runtime (getting apps to compile and run on it was
problematic);
basic/incomplete networking (and unbearably slow tcp performance);
a few basic bits of a gui, this time stalling out due to limitations of
using a more c-style design.
> On a lower-level, assuming a stack-based function environment as
> mentioned earlier, what would actually be pushed onto the stack - cons
> pairs? Individual pointers? The immediate variables themselves? If a
> pair is used, then how would the variables they point to be allocated
> without a heap? How could one create lists without a heap (since stack
> memory only exists while the function using it is in context)? Other
> large or variable-sized values (i.e., bignums)? Or would it
> effectively be limited to only non-persistent local variables of fixed
> maximum size (and those declared globally)? Certainly languages like C
> work in this mannner, but can a Lisp-like language work under such
> constraints and still have the advantages of Lisp?
>
I am not sure.
the stack can contain slots.
I doubt one can get by with a lisp without some manner of gc.
assuming the implementation does not have large amounts of implicit
allocation (mine has craploads of implicit allocation, so it is
automatically ruled out) then one could probably get by without using calls
like list, cons, probably lambda, ...
one could maybe then write a gc, as for advantages: I don't know.
> I was also wondering if anyone had ever attempted to write a Lisp-like
> language using a threaded interpreter, rather than a conventional one,
> and what results they had with it.
>
my interpreter had faked threading.
my compiler does not (it uses real threads), but the problem with threading
is that it causes great problems with my gc (collections+threads lead quite
often to corrupt memory and such).
I can get by with cooperative threads, assuming at least I only have a
single worker and the main thread goes idle. it seems fairly stable then, of
course, then I am constrained...
> Is this a reasonable line of inquiry, or am I (and the others with
> similiar design plans) going headed towards a dead end? What similiar
> projects have existed in the past (I know of TUNES, but AFAICT they're
> still going), and what results did they have?
last I knew tunes was stuck in some sort of endless stall...
I gave up as I was afraid I would have little more than "yet another unix".
I am having less confidence recently. it seems like my understanding/skill
are fading away and I am somehow retracting into being a newbie...
From: Rahul Jain
Subject: Re: Lisp for low-level Systems Programming
Date:
Message-ID: <87ekugo32e.fsf@nyct.net>
"cr88192" <·······@hotmail.com> writes:
> sadly, X11 is too much tied to linux
I have no clue how you managed to conclude this. X11 has been
implemented, most visibly by TI, in Lisp (and has text in the
specification specifically to accomodate efficient implementation in
many Lisp environments).
--
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
"Rahul Jain" <·····@nyct.net> wrote in message
···················@nyct.net...
> "cr88192" <·······@hotmail.com> writes:
>
> > sadly, X11 is too much tied to linux
>
> I have no clue how you managed to conclude this. X11 has been
> implemented, most visibly by TI, in Lisp (and has text in the
> specification specifically to accomodate efficient implementation in
> many Lisp environments).
>
I meant more the opposite direction:
I can't as easily justify using linux without X11 as the render system...
dealing with vid drivers is not something where I want to tread lightly...
either I would have to make a layer on top of X11, and then reimplement
another layer of X11 to tie existing apps into a new render system, or
modify the XF86 core...
this is not easily justified.
actually, another possible thought is wm kludges, eg, having some desktops
or such being one render system, and others being plain ol' X...
the main limitation in my oppinion:
gl style rendering can't be easily used within the context of normal apps (I
need to make gl windows or such).
I can't project applications onto surfaces, perform lots of transformations
(say, eg, I want to turn the 4 desktops into textures on the inside of a
cube, then rotate between them, or maybe mix 2d and 3d graphics and such,
...).
all this may eventually exist within XF86, I don't know.
of course, X may be more capable than I think, I have not looked into any of
this in depth.
From: Rahul Jain
Subject: Re: Lisp for low-level Systems Programming
Date:
Message-ID: <87hdzcl2r2.fsf@nyct.net>
"cr88192" <·······@hotmail.com> writes:
> I meant more the opposite direction:
> I can't as easily justify using linux without X11 as the render system...
>
> dealing with vid drivers is not something where I want to tread lightly...
>
> either I would have to make a layer on top of X11, and then reimplement
> another layer of X11 to tie existing apps into a new render system, or
> modify the XF86 core...
OK. You could use linux's framebuffer interface, but that doesn't allow
you to use OpenGL.
> the main limitation in my oppinion:
> gl style rendering can't be easily used within the context of normal apps (I
> need to make gl windows or such).
[...]
> all this may eventually exist within XF86, I don't know.
It does (as do many X11 implementations), as the GLX extension, which
allows you to create OpenGL windows and place them as you want.
--
Rahul Jain
·····@nyct.net
Professional Software Developer, Amateur Quantum Mechanicist
"Rahul Jain" <·····@nyct.net> wrote in message
···················@nyct.net...
> "cr88192" <·······@hotmail.com> writes:
>
> > I meant more the opposite direction:
> > I can't as easily justify using linux without X11 as the render
system...
> >
> > dealing with vid drivers is not something where I want to tread
lightly...
> >
> > either I would have to make a layer on top of X11, and then reimplement
> > another layer of X11 to tie existing apps into a new render system, or
> > modify the XF86 core...
>
> OK. You could use linux's framebuffer interface, but that doesn't allow
> you to use OpenGL.
>
yes, a big problem.
> > the main limitation in my oppinion:
> > gl style rendering can't be easily used within the context of normal
apps (I
> > need to make gl windows or such).
> [...]
> > all this may eventually exist within XF86, I don't know.
>
> It does (as do many X11 implementations), as the GLX extension, which
> allows you to create OpenGL windows and place them as you want.
>
this is less than I was hoping for...
I can draw into gl windows and have gl windows.
but I can't:
perform transformations on other apps;
use other apps' backbuffers as textures;
otherwise change the behavior of the render-system;
...
this is part of my complaint.
seeing the 4 desktops being used as textures for a rotating hw-accel cube
would be cool, maybe having the app with active focus rise above the cube
and allowing me to move it freely in 3-space, maybe dropping it back onto
the surface of the cube when I am done with it... (or other such "irregular"
actions).
or at least, all this is part of my fantasy...
cr88192 wrote:
> but I can't:
> perform transformations on other apps;
> use other apps' backbuffers as textures;
> otherwise change the behavior of the render-system;
> ...
>
> this is part of my complaint.
>
I *strongly* suggest looking at the compositing engine architecture on
freedesktop.org. It changes the rendering flow of X, delegating to a
"compositing manager" minion akin to a window manager. It's already
non-vapor, you can download it now (a bit painfully, lots of unstable and
incomplete libraries to pull from CVS) and enjoy plenty of silly graphical
hacks. Since the combined weight of both KDE and GNOME is behind
freedesktop.org, it's likely to emerge as the standard.
Here's some blurb:
"Other applications can also use this to perform screen scraping (like VNC)
or other screen effects like a iconic view of the entire desktop with real
application contents."....
"Now that the final image is constructed programmatically, the possible
presentation on the screen is limited only by the fertile imagination of
the numerous eye-candy developers."
-- KeithPackard - CRL, HP Labs - 11 Nov 2003
http://xserver.freedesktop.org/Software/TranslucentWindows
"David Golden" <············@oceanfree.net> wrote in message
·······················@news.indigo.ie...
> cr88192 wrote:
>
> > but I can't:
> > perform transformations on other apps;
> > use other apps' backbuffers as textures;
> > otherwise change the behavior of the render-system;
> > ...
> >
> > this is part of my complaint.
> >
>
> I *strongly* suggest looking at the compositing engine architecture on
> freedesktop.org. It changes the rendering flow of X, delegating to a
> "compositing manager" minion akin to a window manager. It's already
> non-vapor, you can download it now (a bit painfully, lots of unstable and
> incomplete libraries to pull from CVS) and enjoy plenty of silly graphical
> hacks. Since the combined weight of both KDE and GNOME is behind
> freedesktop.org, it's likely to emerge as the standard.
>
ok, this may be helpful...
I will look into this.
>
> Here's some blurb:
>
> "Other applications can also use this to perform screen scraping (like
VNC)
> or other screen effects like a iconic view of the entire desktop with real
> application contents."....
>
> "Now that the final image is constructed programmatically, the possible
> presentation on the screen is limited only by the fertile imagination of
> the numerous eye-candy developers."
>
> -- KeithPackard - CRL, HP Labs - 11 Nov 2003
>
> http://xserver.freedesktop.org/Software/TranslucentWindows
>
ok,
cr88192 wrote:
>
> of course, X may be more capable than I think, I have not looked into any
> of this in depth.
It probably is, given the new fork that is making the headlines: recent
enhancements developing on freedesktop.org like the compositing engine and
so on (there's politics afoot - the XFree86 Core Team is apparently
disbanding...)
OpenGL might, on the other hand, be less capable than you think for
some kinds of graphical use - it's NOT a pixel-accurate specification -
implementations are required to carry out renderings internally
consistently, but different implementations' renderings can differ
significantly. See Appendix A - Invariants of the OpenGL spec.
People often want pixel accuracy in 2D GUI toolkits for a variety of good
reasons. People often think it's a great idea to write a GUI toolkit on top
of OpenGL. The two are not necesarily compatible: you'd have to either
choose a single opengl implementation or specify some stuff over and above
opengl if you really want pixel-identical renderings across implementations.
"David Golden" <············@oceanfree.net> wrote in message
·······················@news.indigo.ie...
> cr88192 wrote:
>
> >
> > of course, X may be more capable than I think, I have not looked into
any
> > of this in depth.
>
> It probably is, given the new fork that is making the headlines: recent
> enhancements developing on freedesktop.org like the compositing engine and
> so on (there's politics afoot - the XFree86 Core Team is apparently
> disbanding...)
>
ok.
> OpenGL might, on the other hand, be less capable than you think for
> some kinds of graphical use - it's NOT a pixel-accurate specification -
> implementations are required to carry out renderings internally
> consistently, but different implementations' renderings can differ
> significantly. See Appendix A - Invariants of the OpenGL spec.
>
hmm, you have a link to the actual opengl spec (I have largely learned from
experience and by looking at references...)?
I have not had any really signifigantly different experiences between cards
(though I have only really worked using ati, nvidia, and a few 3dfx cards
though...). as far as I can tell between cards the renderings look about the
same.
if it is just details, eg, that filtering and blending operations don't look
exactly the same or such, I believe this is no big deal...
> People often want pixel accuracy in 2D GUI toolkits for a variety of good
> reasons. People often think it's a great idea to write a GUI toolkit on
top
> of OpenGL. The two are not necesarily compatible: you'd have to either
> choose a single opengl implementation or specify some stuff over and above
> opengl if you really want pixel-identical renderings across
implementations.
>
I personally don't care much about pixel identicalness, as long as they look
about the same (and don't have really weird/ugly looking crap on some
cards...).
it could always be possible to fall back to software rendering for some
things if it is a big deal.
I have written most of my gui's using opengl though, if that helps explain
the bias. opengl is a lot more enjoyable than software rendering in my
oppinion at least...
all for now.
cr88192 wrote:
> hmm, you have a link to the actual opengl spec (I have largely learned
> from experience and by looking at references...)?
>
Well, it's on opengl.org, funny enough. The current stable opengl spec (1.5)
still has the relevant section about invariants.
http://opengl.org/documentation/spec.html
"David Golden" <············@oceanfree.net> wrote in message
·······················@news.indigo.ie...
> cr88192 wrote:
>
> > hmm, you have a link to the actual opengl spec (I have largely learned
> > from experience and by looking at references...)?
> >
>
> Well, it's on opengl.org, funny enough. The current stable opengl spec
(1.5)
> still has the relevant section about invariants.
> http://opengl.org/documentation/spec.html
>
hmm, yes, this may be quite helpful...
On Sat, 03 Jan 2004 15:56:17 -0800, Jay Osako wrote:
> Is this a reasonable line of inquiry, or am I (and the others with
> similiar design plans) going headed towards a dead end?
The main issue with using stock hardware is not the GC or the Lisp kernel.
AFAIK, everyone who's implemented any Lisp implementation has done that.
The real issues are the mapping, in a sufficiently Lispy way, of whatever
the processor interupt and memory protection system is and then building
device drivers that interface with them and expose themselves in a
suitably Lispy way. If you don't do that, you have very little advantage
over a standard implementation. In fact, many projects start to fool
about with a kernel and GC on top of a Linux or Windows systems because
writing device drivers and interrupt code is hard. None of them ever
amounted to a Lisp OS. If you don't want to answer the questions about
interupts, device drivers, and memory protection, you should probably
concentrate on portable programming tools like SLIME or develop more
portable ways of interfacing with foreign systems. You'll probably be
closer to something useful.
faa
From: cr88192
Subject: Re: Lisp for low-level Systems Programming (was Re: Lisp w/out GC)
Date:
Message-ID: <vvf7ps1n900073@corp.supernews.com>
"Frank A. Adrian" <·······@ancar.org> wrote in message
···································@ancar.org...
> On Sat, 03 Jan 2004 15:56:17 -0800, Jay Osako wrote:
>
> > Is this a reasonable line of inquiry, or am I (and the others with
> > similiar design plans) going headed towards a dead end?
>
> The main issue with using stock hardware is not the GC or the Lisp kernel.
> AFAIK, everyone who's implemented any Lisp implementation has done that.
> The real issues are the mapping, in a sufficiently Lispy way, of whatever
> the processor interupt and memory protection system is and then building
> device drivers that interface with them and expose themselves in a
> suitably Lispy way. If you don't do that, you have very little advantage
> over a standard implementation. In fact, many projects start to fool
> about with a kernel and GC on top of a Linux or Windows systems because
> writing device drivers and interrupt code is hard. None of them ever
> amounted to a Lisp OS. If you don't want to answer the questions about
> interupts, device drivers, and memory protection, you should probably
> concentrate on portable programming tools like SLIME or develop more
> portable ways of interfacing with foreign systems. You'll probably be
> closer to something useful.
>
I somewhat agree...
and yes, having gotten as far as I had, I can state that drivers are one of
the main things in the way...
there is udi, which had aimed for standardized drivers, but it is largely
stalled and the api didn't seem ultra-simple to implement...
without an os, one has just a monolithic program. if one breaks it apart,
they just have apps, ...
with apps it is harder to realize a dream, especially one of a unified-ish
system...
I had battled with ideas for unifying the apps into a kind of system, but
this in itself is difficult...
2 important pieces had been lost when I split up the system:
persistence (actually this was more when I went compiled), and "meshing"
(trying to be worked on, currently putting bets on jabber-rpc but also
seeing the fairly brutal limits of "karma" within xmpp, currently using a
local server with fairly high karma limits, thus my apps at present are not
being used on the open internet...).
I need to reimplement both to try to chase a dream...
others had been lost, more due to technical reasons (neither windows nor X
has good "gl integration"...).
as a partial result, I have ended up with lots of apps with "weird" user
interfaces that reside in their own windows.
later I may just have a gl window containing the ui's of various running
apps...
I am probably just stupid though...
From: Christopher C. Stacy
Subject: Re: Lisp for low-level Systems Programming (was Re: Lisp w/out GC)
Date:
Message-ID: <u4qvcxn3w.fsf@news.dtpq.com>
>>>>> On 3 Jan 2004 15:56:17 -0800, Jay Osako ("Jay") writes:
Jay> My own interest is in developing a kernel-based Lisp dialect or
Jay> derivative, probably quite far from the mainstream dialects,
Jay> which would be suitable for very-low-level programming,
Jay> specifically one which could be used to write an operating
Jay> system kernel in.
Common Lisp is primarily derived from the superset language that
had been very successfully used to implement operating systems.
The target machines included some hardware support for the language,
but that was just an optimization: you could implement the necessary
parts of the system on stock hardware. (The final version of the
"machine" did eliminate the hardware; it ran on 64-bit stock hardware.)
What you need is not a subset, but rather a superset of Common Lisp
that just has a few functions for accessing the metal so that you can:
manipulate unboxed values, read and write the control registers,
make memory references (eg. create and use machine pointers),
and you'll also need the atomic test-and-set instruction.
Strictly speaking, I think those are the only primitive
elements you'll need to bootstrap, language-wise.
That's more than C has, by the way (which is why you
can't quite write an operating system in unadorned C).
Language implementation-wise, note that your Lisp runtime
is now a part of the operating system, so its subprimitive
functionality needs to be written accordingly. For example,
even though 99.9% the code in GC and dynamic paging system
can be written in unadorned Common Lisp, the lowest level
parts of both of those things will interact with each other.
Jay> My particular approach has been to define a very minimal subset
Jay> of the language, which would use a basic stack allocation method
Jay> more typical of procedural languages for local variables.
Jay> This would be used to implement a basic memory manager and
Jay> process scheduler, which in turn would be used to implement
Jay> a kernel-level GC process which would 'comb out' the memory
Jay> of the other system processes.
Jay> Would a language like this be worth the effort, or would it be
Jay> just C with a Lisp-like syntax? Could it be implemented with
Jay> suitable efficiency? What advantages and disadvantages would
Jay> it have over a conventional systems language like C or Modula-2?
The MIT Lisp Machine systems can be considered as four progressive
classes of implementation: the CADR, the 3600, the Ivory chip, and
the DEC Alpha, (There's more to it than that, but no matter.)
The 3600 included a seperate front-end processor that was used
for booting the main machine and for offloading certain IO tasks.
Note that the FEP had nothing to do with the implementation of
the Lisp Machine's run-time system - it was a seperate machine.
The FEP was an MC68000 running its own disk operating system written
in a language called LIL (Lisp-like Implementation Language).
Your suggested approach seems reminiscent of the FEP: trim away
most of the functionality of Lisp for lowest-level part of your
kernel, to the point where it is arguably not really "Lisp".
Writing your micro-kernel implementation language (like LIL) in Lisp
would be very easy, and will allow you to freeload off Lisp's macros.
That is very powerful and should help a lot, if you go that route.
However, the more of your kernel that is implemented in real Lisp,
the easier it should be to write, maintain, and debug. For example,
you would like your OS to benifit from Lisp's object-reference model
(as opposed to the memory-location-reference model of C).
The question is where to draw the line, and you seem to be
naturally focused on the problem of automatic storage management.
The memory system is pervasive in both Lisp and the OS.
But most Lisp language functions neither cons nor release storage.
They just call, branch, return pointers, or access locations.
Restricting consing to the stack therefore is not about subsetting
language forms - it's more about restrictions on when and how one
is allowed to cons what objects, and all the support needed to
access the objects from the stack.
If this operating system is written (in any significant way)
in Lisp, then there will by definition be, at some level, a
full-blown Lisp with a garbage collector. This GC ought to be
tuned to the rest of the operating system's memory management.
In the end, there's no getting away from implementing it.
An operating system will need to provide (for its own internals)
certain static memory management features: placing interrupt vectors
and trap handlers, allocating page-aligned IO buffers, and so on.
It also needs to do simple static, and dynamic, memory allocation.
Then there is the dynamic address translation and paging system.
Along this boundary are the issues of moving data between the
various contexts (did I mention interrupts), and which by the
way also brings up any issues of pointer security.
I think that it would be easier to design and code one underlying
memory management and object-reference system, rather than two
or three different ones, in at least two different languages,
that need to participate with each other in fairly complex ways.
The OS is generally allowed to cons because the memory system
(part of the Lisp runtime) is present in the bootload.
When it is starting itself up (perhaps prior to virtual memory
being set up, garbage collector not yet initialized, etc.)
it only should cons according some specific controls.
And once it's up, there are of course other situations
where memory is managed specially.
Maybe the lowest-level part of the operating system does not
necessarily need to include a garbage collector. But Lisp
will still need its interface to the allocator, and it must
all be designed to operate with the GC when it's available.
The OS, the GC, and Lisp, could be thought of as distinct;
in another sense, they are all just part of each other.
Anyway, for the parts of the operating system that must only
cons under special controls, you expose the automatic and manual
memory system interfaces as Lisp forms.
In Genera, see the "Areas" and "Regions" facilities, which were
operated by interfaces like MAKE-AREA, *DEFAULT-CONS-AREA*,
and SYS:RESET-TEMPORARY-AREA. See also the stack-consing forms
such as STACK-LET and WITH-STACK-ARRAY. Those particular interfaces,
as well as things like SYS:PAGE-IN-ARRAY and STORAGE:WIRE-STRUCTURE,
were also available for ordinary user programs.
The lowest guts of your virtual memory system will consist
of unboxed integer arrays and calling the functions that
I mentioned at the beginning of this article.
One thing you might find really handy when writing that sort of
stuff is a macro that looks like a suped-up version of DEFMACRO,
but with bit-level control over the underlying memory structures.
(In other words, it's somewhat like a C struct; with the accessors
doing either type conversion or straight bit-level casting as needed.)
Jay> would it be desirable to 'hide' the low-level tools from the
Jay> client programmer, and if so, how would you go about doing so
Jay> (e.g., namespace control, alternative function names, etc).
The "desirability" question is the the same as for any operating
system, and depends on what you want people to do with it.
The interface design strategy is also the same: provide them with
a name binding, or not, and either allow or trap the operation based
on whatever policies you want.
Without knowing what kind of system model you have in mind it's
impossible to guess. I would suggest studying what Multics did
(in its large virtual memory dynamic linking model) and also check
out the general literature on pointer-based capability systems.
The Lisp Machine was a single-user multiprocessing system that
implemented a single large address space, with no internal security
mechanisms. Users were totally free to call any functions such
as SYS:%READ-MEMORY-ADDRESS and SYS:%LOGAND-BUS-INTERRUPT-MAP,
but were well advised not to do so.
However, the Lisp Machine implemented a very secure (and featureful)
networked file server system, developed by one of the Multics authors.
(It just wasn't secure from the local console user.)
Jay> One question then becomes
[...a bunch of questions]
I hope my ramblings have answered some of your questions
in a helpful way, or at least gave you some hints.
I guess my bottom line is that doing it in what probably
seems to be "the hard way" will pay off the best.
The answer is surely not about a creating a subset of
the ANSI Common Lisp forms.
Jay> I was also wondering if anyone had ever attempted to write a
Jay> Lisp-like language using a threaded interpreter, rather than a
Jay> conventional one, and what results they had with it.
Don't know anything about that (but it's been done for JAVA and is
supposed to perform better than the JIT approach).
Jay> Is this a reasonable line of inquiry, or am I (and the others with
Jay> similiar design plans) going headed towards a dead end?
Gee, I'm not much of a futurist.
Perhaps this will clear things up:
Windows are broken in the valley of the red men:
Through avarice, through force and violence the chief is scorned,
and will come to vex his supporters:
The eunichs give fight:
Brothers and cousins at war.
The law of Moore will be seen to decline:
After another much more seductive:
The path widens and the others long exiled return by night:
Lambda, Ivory, Starstone, and Rho united.
Well, perhaps not.
Certainly what you are proposing, if taken to the level of
what people generally think when "operating system" is uttered,
is nothing trivial. I like the idea that people are interested in it.
I didn't answer anything about how to implement (any kind of) Lisp,
such as the structure of your stacks or heap allocation strategies.
I don't know much about that, but the implementors of most of the
popular implementations hang out here and answer questions.
There must be some literature on that, but I don't have references;
I know there's plenty of Lisp GC material published.
I would of course suggest studying the open source code of existing
Lisp implementations such as CMUCL/SBCL, CLISP, Corman, and GCL.
That might also be where your own implementation begins from.
I would also suggest studying the design and implementation of
the Lisp Machine operating system. The most highly developed
version of that line of software was called "Symbolics Open Genera".
Little was published, but some Lisp Machine references can be found here:
http://kogs-www.informatik.uni-hamburg.de/~moeller/symbolics-info/literature.html
Open Genera is still available from Symbolics (although it has not been
under active development for more than a decade) and it comes with sources.
However, I think their license protects those trade secrets so you would
need to be a little careful of certain legalities in studying them for
developing your own competing (even if "free") product. Symbolics might
yet come out with a version of Open Genera for the new 64-bit machines.
(That's just pure speculation, though, and for some reason, the phrases
"consequences are undefined", "deamons out my nose", and "pigs can fly"
are springing into my mind. But it's a nice wish, anyway.)
There is, of course, a wealth of literature about operating system design
in general. Unfortunately, these days the popular books are heavily
oriented towards Unix. For contrast I would also recommend the book
"Inside Windows NT". I assume you want to develop something better
than either of those. Be sure to read the Multics papers.
Some more recent things to look at would be the Amoeba and EROS systems.
Questions about Lisp Machines can usually be answered on this newsgroup,
where a few of the developers and long-time users (and even a couple of
new newbie users) sometimes hang out. Some of us are also conversant
with other operating system designs.
From: Joe Marshall
Subject: Re: Lisp for low-level Systems Programming
Date:
Message-ID: <n093v982.fsf@comcast.net>
······@news.dtpq.com (Christopher C. Stacy) writes:
> The OS is generally allowed to cons because the memory system
> (part of the Lisp runtime) is present in the bootload.
> When it is starting itself up (perhaps prior to virtual memory
> being set up, garbage collector not yet initialized, etc.)
> it only should cons according some specific controls.
> And once it's up, there are of course other situations
> where memory is managed specially.
>
> Maybe the lowest-level part of the operating system does not
> necessarily need to include a garbage collector. But Lisp
> will still need its interface to the allocator, and it must
> all be designed to operate with the GC when it's available.
> The OS, the GC, and Lisp, could be thought of as distinct;
> in another sense, they are all just part of each other.
At LMI here's how we did it:
The boot code would either be downloaded into the processor from the
bus or it could be read from a ROM. When the processor started, all
interrupts and traps were turned off. You could not immediately CONS
because the free-pointer didn't exist.
The very first action the code took was to set up a direct mapping
between virtual and physical memory. This gave us an arena for
temporary consing until the real cons code was available. From this
we'd allocate the structures necessary for paging and GC (the page
tables and the region and area tables). We'd mark these pages as
`wired' (non-evictable, non-movable) and mark the remaining physical
and virtual memory as unallocated. We could then discard the direct
mapping and use the `Area' and `Region' allocation mechanisms.
Part of the page fault system would be available at this point
provided that a page did not need to be evicted. When a new page was
allocated, we could grab it out of the physical memory, so you had a
bit less than 16Meg you could use to finish getting things running.
The LMI GC was essentially a card-marking system with a hardware
assist. When writing a pointer it may be necessary to update a card,
so it was importart to get this part of the software up fairly early
on. The GC hardware needed to know the types of the pointers and the
generation numbers of the pages being written and the pages being
referenced. We'd load the GC hardware (depending on the boot load, if
it was a cold load, then there were no existing areas or regions, but
it was a saved world, the generation numbers were kept in a table that
was present at boot time).
At this point, there is enough structure to turn on the GC write
barrier. We'd turn it on and touch the allocated regions and areas to
update the cards. At this point, the real CONS was available to be
used. Provided that you got the rest of the page fault handler in
place before you used up physical memory, you could CONS at will.
Note that the GC isn't available yet. It didn't get initialized until
fairly late in the process. Once you have the ability to page to the
backing store, you have the full address space to allocate from before
you need to GC, so there is little urgency. The GC ran as a separate
process that monitored the consing rate and would step in from time to
time to free up storage.
> Jay> I was also wondering if anyone had ever attempted to write a
> Jay> Lisp-like language using a threaded interpreter, rather than a
> Jay> conventional one, and what results they had with it.
I have. It is incomplete and I haven't finished experimenting with it.
I don't want to spoil the surprise, but let me say that the results
are promising.
> Don't know anything about that (but it's been done for JAVA and is
> supposed to perform better than the JIT approach).
>
> Jay> Is this a reasonable line of inquiry, or am I (and the others with
> Jay> similiar design plans) going headed towards a dead end?
It is a reasonable line of inquiry. See
@misc{ ertl-threaded,
author = "M. Anton Ertl",
title = "Threaded Code Variations and Optimizations (Extended Version)",
url = "citeseer.nj.nec.com/ertl02threaded.html" }
@article{ ertl02vmgen,
author = "M. Anton Ertl and David Gregg and Andreas Krall and Bernd Paysan",
title = "{Vmgen} --- a generator of efficient virtual machine interpreters",
journal = "Soft\-ware\emdash Prac\-tice and Experience",
volume = "32",
number = "3",
month = "????",
pages = "265--294",
year = "2002",
url = "citeseer.nj.nec.com/article/ertl02vmgen.html" }
> There is, of course, a wealth of literature about operating system design
> in general. Unfortunately, these days the popular books are heavily
> oriented towards Unix. For contrast I would also recommend the book
> "Inside Windows NT". I assume you want to develop something better
> than either of those. Be sure to read the Multics papers.
> Some more recent things to look at would be the Amoeba and EROS systems.
> Questions about Lisp Machines can usually be answered on this newsgroup,
> where a few of the developers and long-time users (and even a couple of
> new newbie users) sometimes hang out. Some of us are also conversant
> with other operating system designs.
What?! You mean that Unix is not the entire world of operating systems?!
--
~jrm
I've been working on a project like this for some time now, and some
of my thought on it are written down here:
<http://www.cs.uit.no/~frodef/los0/>
Jay Osako wrote:
> My particular approach has been to define a very minimal subset of
> the language, which would use a basic stack allocation method more
> typical of procedural languages for local variables.
Unless you're specifically targeting resource-starved systems, I see
no reason to worry about minimalism (in terms of code/language
amounts). On the contrary, I think it's the last few years of relative
resource abundance (CPU cycles and memory in particular) that makes
e.g. lisp-based OS programming a good idea now. If your "base
language", whatever it is, clocks in at 0.1, 2, or 10 MB rarely
matters today when in many respects the smallest unit of RAM one cares
about is 128 MB.
Also, Common Lisp already supports stack allocation with the
dynamic-extent declaration. (But then I also consider Common Lisp to
be a very "procedural language".) How well some particular
implementation supports this is another question, but irrelevant if
you are the implementor of your own lispy systems language compiler.
> Would a language like this be worth the effort, or would it be just
> C with a Lisp-like syntax? Could it be implemented with suitable
> efficiency?
I think the many existing lisp implementations for e.g. unix and
windows demonstrates how efficient lisp can be. In fact, I believe
systems that are lisp all the way can probably achieve much more than
this, because they don't have to deal with a C environment and
hardware insulation.
--
Frode Vatvedt Fjeld
From: rydis (Martin Rydstr|m) @CD.Chalmers.SE
Subject: Re: Lisp for low-level Systems Programming (was Re: Lisp w/out GC)
Date:
Message-ID: <w4cllonfojb.fsf@boris.cd.chalmers.se>
······@hotmail.com (Jay Osako) writes:
> I was also wondering if anyone had ever attempted to write a Lisp-like
> language using a threaded interpreter, rather than a conventional one,
> and what results they had with it.
Maybe I misunderstand, but Qlambda/Qlisp (McCarthy & Gabriel) and
*Lisp (Steele at Thinking Machines) come to mind. (There were almost
certainly other people involved, but those are the names I remember.)
Regards,
'mr
--
[Emacs] is written in Lisp, which is the only computer language that is
beautiful. -- Neal Stephenson, _In the Beginning was the Command Line_
"Jay Osako" <······@hotmail.com> wrote in message
·································@posting.google.com...
> My particular approach has been to define a very minimal subset of the
> language, which would use a basic stack allocation method more typical
> of procedural languages for local variables. This would be used to
> implement a basic memory manager and process scheduler, which in turn
> would be used to implement a kernel-level GC process which would 'comb
> out' the memory of the other system processes.
I agree with the other poster that you need a superset of CL, not a subset.
On top of CL you'll need, minimally, an assembler (as poking hex values in
to memory is just plain evil). You'll also need some more direct control
over the memory management system.
Seriously, I think that the first step towards doing anything like this is
the compiler. If you have a CL compiler written in CL, then you will want
all of the attributes of CL that the compiler requires in your base system.
Folks constantly set the highest of goal with these systems, and then those
high goals seem to hold them back.
On a PC, you really need very little to get a functioning system (it needs
to be more sophisticated to be an efficient, and more performant system).
There is nothing stopping folks from using the BIOS to bootstrap early
development. That gives you "Free" console and disk access. There is no
reason to have to start the system with a paging allocator when you have
modern machines with gob tons of memory. You don't have to have every driver
written from scratch in protected mode. The system should be run in
protected mode, just to give the flat memory space, but you can fault back
to talk to the BIOS. It's ugly, but practical. Given these basic facilities,
you can start implementing a FAT file system, or any other file system. It
doesn't even matter if you start hitting 1G, or 4G, or whatever BIOS limits
on your drive. At least it's functional.
What you do need, though, is a compiler. A compiler with an assembler. Given
a memory map, the assembler can early on solve all ills. You need to have
detailed knowledge of the compiler so that you can make special, platform
dependent compiler tweaks to handle interrupts, etc.
Finally, you need an editor, but Hemlock is available as a solid base to
boot that up.
Once you have a self-hosting compiler, a REPL, and an editor, and a
filesystem, THEN the rest can be worked on, in place, on the platform. Heck,
it's even mostly portable at this early stage, because of the BIOS.
So, in summary, here's what I think is needed:
o A CL compiler in CL (CMUCL/SBCL are the only ones I know of for the
x86).
o An assembler in CL (a disassembler would be nice as well)
o A way to install CL assembler routines into interrupts
o A way to call high level CL from assembler (including interrupts).
o CL controllable memory manager.
o Console I/O (the BIOS will give you that, interfaced through
assembler)
o Block Disk I/O (the BIOS will give you that too)
o A file system in CL
o A boot manager that can select an image to boot. GRUB MIGHT work for
this.
o Console based REPL
o SAVE-IMAGE
o Console based Debugger
o Warm start capability (ctrl-alt-delete to get you back to the
REPL/Debugger)
o Console based Editor (Hemlock should be able to do this)
What don't you need?
o paged, virtual memory
o protected mode drivers
o network drivers
o graphics drivers
o multiprocessing/tasking
o GUIs
o Mice
o web browsers, network clients, etc.
Perhaps the paging unit is required to get GC going, but there's no reason
for swap day one.
In the past, folks seem to want to most sophisticated system available just
to start development. I think the crudest system available should be done
first in order to get the entire thing self hosted as quickly as possible,
then the rest will follow more naturally.
I had a friend who worked on a debugger for early OS/2, and he said once
they got their debugger debugging their debugger, development was much
faster. Same goes here. When you can start tweaking the paging system from
the REPL, or installing disk drivers on the fly from the REPL, things will
move MUCH faster. If a common file system is used, you can always use other
OSes for moving files across the net, etc. early on, at least until SLIP is
implemented (which is pretty straightforward, I understand).
None of these pieces need be particularly sophisticated, or super efficient,
or best of class. They simply need be functional.
Regards,
Will Hartung
(·····@msoft.com)
From: Christopher C. Stacy
Subject: Re: Lisp for low-level Systems Programming (was Re: Lisp w/out GC)
Date:
Message-ID: <ur7yeav6o.fsf@news.dtpq.com>
>>>>> On Mon, 5 Jan 2004 11:27:14 -0800, Will Hartung ("Will") writes:
Will> What you do need, though, is a compiler. A compiler with an assembler.
That might be useful for the process of writing the system,
but note that it is definitely not required in the system itself.
(I gave a list of what you need in the system: a few Lisp functions.)
From: Christopher C. Stacy
Subject: Re: Lisp for low-level Systems Programming (was Re: Lisp w/out GC)
Date:
Message-ID: <un092auu1.fsf@news.dtpq.com>
>>>>> On Mon, 5 Jan 2004 11:27:14 -0800, Will Hartung ("Will") writes:
Will> What you do need, though, is a compiler. A compiler with an assembler.
That might be useful for the process of writing the system,
but note that it is definitely not required in the system itself.
(I gave a list of what you need in the system: a few Lisp functions.)
Will> to start development. I think the crudest system available should
Will> be done first in order to get the entire thing self hosted as
Will> quickly as possible, then the rest will follow more naturally.
Cross-development is also extremely useful; for example, using Lisp your
workstation to download code and remotely debug the target machine.
For that, you need some sort of interface to front-console functionality.
For example, a serial-based interface to a BIOS that has commands for
poking at the machine.
Take a look at the BRiX OS project.
http://brix-os.sourceforge.net/
It uses a language called Crush that is pretty Lisp-y. Its got
lambdas, dynamic typing, optional type declarations, macros, and some
constraint stuff. And its all prefix-syntax too!
The cool thing about the OS is that it recognizes that with a safe
language, there is no need for the tradition kernel/application
seperation. Getting rid of this seperation makes many things (like
system calls) an order of magnitude faster.
> It uses a language called Crush that is pretty Lisp-y. Its got
> lambdas, dynamic typing, optional type declarations, macros, and
> some constraint stuff. And its all prefix-syntax too!
Sadly, it is adopting a "new syntax" that "will look similar to C...."
--
Fred Gilham ······@csl.sri.com
Jordan Hubbard: We have a crash bug. It needs to be fixed. We DO NOT
need to know how to print 3000 spaces in 11 different languages! :-)
Daniel Sobral: I concur. But if anyone wants to do it with loader,
: 3kbl 3000 0 do bl emit loop ; 3kbl will do the trick.
> Sadly, it is adopting a "new syntax" that "will look similar to C...."
Deja vu? Well, that's sad to hear. I wonder how this will affect their
macros --- Crush has fully procedural macros, and those will be hard
to do with a conventional syntax. Still, if the original poster is
really interested in a kernel-level Lisp, the current version of Crush
is certainly a good starting point.
From: David Golden
Subject: Re: Lisp for low-level Systems Programming (was Re: Lisp w/out GC)
Date:
Message-ID: <rYoKb.3394$HR.7608@news.indigo.ie>
Rayiner Hashem wrote:
> The cool thing about the OS is that it recognizes that with a safe
> language, there is no need for the tradition kernel/application
> seperation. Getting rid of this seperation makes many things (like
> system calls) an order of magnitude faster.
Hmm. Anyone tried loading a unix lisp into linux kernel memory space with
the kernel-mode hack[1] for loading executables?
(Wasn't there a proprietary unix that did this?)
[1] http://web.yl.is.s.u-tokyo.ac.jp/~tosh/kml/
David Golden <············@oceanfree.net> writes:
> Rayiner Hashem wrote:
>
>
> > The cool thing about the OS is that it recognizes that with a safe
> > language, there is no need for the tradition kernel/application
> > seperation. Getting rid of this seperation makes many things (like
> > system calls) an order of magnitude faster.
>
> Hmm. Anyone tried loading a unix lisp into linux kernel memory space with
> the kernel-mode hack[1] for loading executables?
Not that I know of, but that would be a nice environment to fiddle
with stuff in. Even nicer IMO would be a Lisp that could be loaded as
a kernel extension into Darwin's Mach. I mean, if C++ can do it...
> [1] http://web.yl.is.s.u-tokyo.ac.jp/~tosh/kml/
Oooh, cool. I especially like the idea of using typed assembly
language, although as usual, that safety isn't enforced. That
wouldn't be the Unix way, I guess :-P
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'
From: Massimo Dentico
Subject: Re: Lisp for low-level Systems Programming (was Re: Lisp w/out GC)
Date:
Message-ID: <btdaoc$ku1$1@news.ngi.it>
"David Golden" <············@oceanfree.net> wrote
in the message ·······················@news.indigo.ie...
> Hmm. Anyone tried loading a unix lisp into linux kernel memory space with
> the kernel-mode hack[1] for loading executables?
>
> (Wasn't there a proprietary unix that did this?)
>
>
> [1] http://web.yl.is.s.u-tokyo.ac.jp/~tosh/kml/
NOT strictly related to your question, but there is a Scheme in Linux
kernel space:
http://www.schemix.org/
Excerpt from its home page:
Schemix is a Scheme system, implemented as a patch to the Linux kernel.
It aims to attain R5RS compliance while remaining small, fast and easy
to understand.
The intended use of Schemix is for exploration of the Linux kernel and
for rapid, interactive prototyping of Linux drivers and other new kernel
features. To achieve this, Schemix attempts to make a large subset of
the kernel functionality available to Scheme programs. Interactivity is
via a character device, /dev/schemix which presents a REPL (Read, Eval,
Print Loop) to anyone having access to the device.
Regards.
--
Massimo Dentico
From: Massimo Dentico
Subject: Re: Lisp for low-level Systems Programming (was Re: Lisp w/out GC)
Date:
Message-ID: <btd98q$ke9$1@news.ngi.it>
"Jay Osako" <······@hotmail.com> wrote
in the message ·································@posting.google.com...
..snip..
>
> I was also wondering if anyone had ever attempted to write a Lisp-like
> language using a threaded interpreter, rather than a conventional one,
> and what results they had with it.
"Threaded" as in concurrent programming or as in threaded code?
Here an overview by Anton Ertl about threaded code:
http://www.complang.tuwien.ac.at/forth/threaded-code.html
In the second case there is at least one Scheme implementation
that can interest you, QScheme:
http://www.sof.ch/dan/qscheme/index-e.html
that *seems* (at least skimming the documentation) implemented as a
Forth-inspired VM: stack-based + a form of threaded code (token threaded
code?). The author claims it is from 2 and 70 times faster than other
Scheme interpreters.
Regards.
--
Massimo Dentico