A year or so back, there was a rather interesting discussion on what
was termed "minimal" subsets of Lisp. I am curious if anything
further has happened with some of the efforts discussed in terms of
creating "minimal" lisps.
I have a specific question of interest on the subject, and I'll do my
best to word it precisely:
Given a hardware situation where NO compiler is available for any
language above the assembly level, and the goal is a running ANSI
Common Lisp, what would be the implementation path to take that would
result in the least amount of low level coding (or least difficult, if
the minimal AMOUNT of low level code would involve difficult coding)
that would produce a working ANSI Common Lisp? Assume a source code
version of ANSI Common Lisp that was written itself in ANSI Common
Lisp, in such a fashion that it could build more complex layers
without recursive calls to functionality in other complex layers (such
a beast would have to know what the core building blocks it would have
to work with would be, of course - so it would have to be written in
such a fashion that no single part of the definition required that its
own definition already be working, except for the parts to be
implemented in assembly language.)
Additional design points:
1. Efficiency is not a major concern for the bootstrap process - it
should have a reasonable expected finishing time but simplicity and
ease of understanding would be the major concerns. (Put another way,
the assumption would be that the assembly functionality might have to
be defined on multiple hardware platforms, and speed on any one
platform is not important. After the running ANSI CL is established,
it can proceed to re-compile itself for better performance. A few
hours on bootstrap are not so critical, since it should need to be
done only rarely (or once) per platform.)
2. The tradeoff between additional assembly code for ease of
implementing the ANSI CL in ANSI CL part and minimizing the amount of
assembly code needed should be optimized for ease of understanding
first, and ease of implementation second - efficiency is a distant
3rd. If parts of the spec that could theoretically be implemented in
CL but would be far simpler to understand and fairly easy to implement
in assembly code pop up, it is OK to specify the behavior as needing
to be defined in assembly code provided a clear and unambiguous
definition of the required behavior is given.
To those who will immediately respond that this is an uninteresting
problem because we are not likely to face a situation where cross-
compilation is more difficult than hand coding, I acknowledge that it
is probably true cross-compilation will always be simpler. My
interest is partically historical (in the early days there WERE no
compilers, and someone had to do the job by hand - in retrospect, what
would have been the quickest path to maximum functionality with
minimal work, if ANSI CL were the target) and partially a desire to
reduce the required knowledge set to the minimum (knowledge of the
machine platform, and knowledge of Lisp - any cross compilation effort
would almost certainly need both of these. If you are cross compiling
from one Lisp to another this same knowledge set should be enough as
well, but the supposition for the exercise is that NO working Lisp
compilers are available - perhaps in a distant future unimaginable
folly has resulted in all working binaries of Lisps being too old to
run on any available hardware platform, if you need a scenario.)
In a sense, the first historical bootstrapping processes are what took
computers from simple electrical devices to everything they are today
- the bootstrap is what MAKES a computer into a computer from its
component parts. To me that is a fascinating process, and the
question "what would it take to go from inert metal to ANSI CL" is an
interesting one. Is there any literature on such a topic?
Cheers,
CY
P.S. I will confess a background motivation for this question is the
Axiom project, which is founded on Lisp - the "30-year horizon"
thinking of our project leader also lead me to the question "how can
the knowledge being encoded into these computer languages survive
indefinitely - what would it take to revive the living Axiom system
even if we are somehow left with no running system which supports our
current binary dependencies or understands our source code? Well, if
we work inside Lisp for everything (a goal for at least some of us on
the project) that reduces the question to "how does one get Lisp
working starting from nothing?" (OK, OK there are issues with
graphics systems like X and GDI and whatnot - but the core of the
system is non-graphical.) It is not a likely scenario but interesting
enough for me to pose the question. It also might have some bearing
on formally proving correctness on various platforms, but I don't know
enough about that yet to be sure.
On Jun 11, 2:58 pm, C Y <···········@yahoo.com> wrote:
> A year or so back, there was a rather interesting discussion on what
> was termed "minimal" subsets of Lisp. I am curious if anything
> further has happened with some of the efforts discussed in terms of
> creating "minimal" lisps.
>
> I have a specific question of interest on the subject, and I'll do my
> best to word it precisely:
>
> Given a hardware situation where NO compiler is available for any
> language above the assembly level, and the goal is a running ANSI
> Common Lisp, what would be the implementation path to take that would
> result in the least amount of low level coding (or least difficult, if
> the minimal AMOUNT of low level code would involve difficult coding)
> that would produce a working ANSI Common Lisp? Assume a source code
> version of ANSI Common Lisp that was written itself in ANSI Common
> Lisp, in such a fashion that it could build more complex layers
> without recursive calls to functionality in other complex layers (such
> a beast would have to know what the core building blocks it would have
> to work with would be, of course - so it would have to be written in
> such a fashion that no single part of the definition required that its
> own definition already be working, except for the parts to be
> implemented in assembly language.)
>
> Additional design points:
>
> 1. Efficiency is not a major concern for the bootstrap process - it
> should have a reasonable expected finishing time but simplicity and
> ease of understanding would be the major concerns. (Put another way,
> the assumption would be that the assembly functionality might have to
> be defined on multiple hardware platforms, and speed on any one
> platform is not important. After the running ANSI CL is established,
> it can proceed to re-compile itself for better performance. A few
> hours on bootstrap are not so critical, since it should need to be
> done only rarely (or once) per platform.)
>
> 2. The tradeoff between additional assembly code for ease of
> implementing the ANSI CL in ANSI CL part and minimizing the amount of
> assembly code needed should be optimized for ease of understanding
> first, and ease of implementation second - efficiency is a distant
> 3rd. If parts of the spec that could theoretically be implemented in
> CL but would be far simpler to understand and fairly easy to implement
> in assembly code pop up, it is OK to specify the behavior as needing
> to be defined in assembly code provided a clear and unambiguous
> definition of the required behavior is given.
>
> To those who will immediately respond that this is an uninteresting
> problem because we are not likely to face a situation where cross-
> compilation is more difficult than hand coding, I acknowledge that it
> is probably true cross-compilation will always be simpler. My
> interest is partically historical (in the early days there WERE no
> compilers, and someone had to do the job by hand - in retrospect, what
> would have been the quickest path to maximum functionality with
> minimal work, if ANSI CL were the target) and partially a desire to
> reduce the required knowledge set to the minimum (knowledge of the
> machine platform, and knowledge of Lisp - any cross compilation effort
> would almost certainly need both of these. If you are cross compiling
> from one Lisp to another this same knowledge set should be enough as
> well, but the supposition for the exercise is that NO working Lisp
> compilers are available - perhaps in a distant future unimaginable
> folly has resulted in all working binaries of Lisps being too old to
> run on any available hardware platform, if you need a scenario.)
>
> In a sense, the first historical bootstrapping processes are what took
> computers from simple electrical devices to everything they are today
> - the bootstrap is what MAKES a computer into a computer from its
> component parts. To me that is a fascinating process, and the
> question "what would it take to go from inert metal to ANSI CL" is an
> interesting one. Is there any literature on such a topic?
>
> Cheers,
> CY
>
> P.S. I will confess a background motivation for this question is the
> Axiom project, which is founded on Lisp - the "30-year horizon"
> thinking of our project leader also lead me to the question "how can
> the knowledge being encoded into these computer languages survive
> indefinitely - what would it take to revive the living Axiom system
> even if we are somehow left with no running system which supports our
> current binary dependencies or understands our source code? Well, if
> we work inside Lisp for everything (a goal for at least some of us on
> the project) that reduces the question to "how does one get Lisp
> working starting from nothing?" (OK, OK there are issues with
> graphics systems like X and GDI and whatnot - but the core of the
> system is non-graphical.) It is not a likely scenario but interesting
> enough for me to pose the question. It also might have some bearing
> on formally proving correctness on various platforms, but I don't know
> enough about that yet to be sure.
"Historical" is right. A one-machine bootstrap is quite literally an
awesome task, not least because you need tools like an editor and file
handling. Are all these to be written in assembly language? I've
never heard of someone doing that since the early 60's.
Anyway, it's just as you say. Implement a very minimal L subset
compiler (or interpreter) C in assembly then rewrite (or write) the
compiler in the L subset (call this C'), use C to compile C'. Now use
C' to compile C', and you're off to the races. Keep adding
functionality so that C' compiles ever more of L. As soon as you
implement a new feature F, you can recompile C' and then rewrite C' to
use F and recompile yet again.
As a practical matter, it may be easier to bootstrap a language other
than CL, e.g. try ANSI C to get a compiler that will compile gcc, then
use this to build one of the standard C-based CL systems.
While you're at it, next time you need to spread butter, start by
digging for iron ore in the back yard... ;-)
Cheers!
On Jun 11, 7:49 pm, Gene <············@gmail.com> wrote:
> "Historical" is right. A one-machine bootstrap is quite literally an
> awesome task, not least because you need tools like an editor and file
> handling. Are all these to be written in assembly language? I've
> never heard of someone doing that since the early 60's.
Heh - that would actually be an interesting thing to try and add to
the hardware design of the platform :-). You'd have the sound card,
the graphics card, the editor card... Surely an absolutely minimalist
editor wouldn't be too hard - it's not like you'd need Emacs to input
assembly code with the sole object of feeding it to a bootstrap
process.
> Anyway, it's just as you say. Implement a very minimal L subset
> compiler (or interpreter) C in assembly then rewrite (or write) the
> compiler in the L subset (call this C'), use C to compile C'. Now use
> C' to compile C', and you're off to the races. Keep adding
> functionality so that C' compiles ever more of L. As soon as you
> implement a new feature F, you can recompile C' and then rewrite C' to
> use F and recompile yet again.
I guess that's one of the major questions - how many such iterations
must exist between a reasonable assembly subset and full ANSI CL. I
suppose you might have to have multiple definitions of some concepts
to be used at each stage of the bootstrap.
> As a practical matter, it may be easier to bootstrap a language other
> than CL, e.g. try ANSI C to get a compiler that will compile gcc, then
> use this to build one of the standard C-based CL systems.
I guess. I'm not sure how in theory a C detour would help, but it
might simplify matters - or perhaps a c-like stage would be inevitable
in the bootstrap definition cycle.
> While you're at it, next time you need to spread butter, start by
> digging for iron ore in the back yard... ;-)
Hey, I never claimed it was a sane idea - just an interesting
one. ;-) The idea of how to bootstrap modern technology from flint
tools, fire, and whatever can be found around you is another such
interesting problem (and one that might actually be of practical
interest in the case of space travel, where you need to use what's
already ahead of you at your destination as much as possible) but I
have a feeling figuring out how THAT worked would make bootstrapping a
computer look like a trivial freshman homework problem.
Cheers, and thanks.
CY
On Mon, 11 Jun 2007 19:17:44 -0700, C Y <···········@yahoo.com> said:
| ...
| I guess. I'm not sure how in theory a C detour would help, but it
| might simplify matters - or perhaps a c-like stage would be inevitable
| in the bootstrap definition cycle.
By the way, it has been pointed out that FORTH may be a better
candidate than C or even assembly language for the next language
after machine language.
---Vassil
(who has only done partial gedanken bootstrapping).
--
The truly good code is the obviously correct code.
Vassil Nikolov wrote:
> On Mon, 11 Jun 2007 19:17:44 -0700, C Y <···········@yahoo.com> said:
> | ...
> | I guess. I'm not sure how in theory a C detour would help, but it
> | might simplify matters - or perhaps a c-like stage would be inevitable
> | in the bootstrap definition cycle.
>
> By the way, it has been pointed out that FORTH may be a better
> candidate than C or even assembly language for the next language
> after machine language.
+1. Forth is amazingly simple and elegant, although
its elegance lies along a different axis than Lisp's.
Building a working Forth VM by entering opcodes via
front-panel switches seems quite feasible. Getting
from there to an interactive Forth interpreter would
be somewhat more challenging :-)
-- JK
On Jun 12, 11:49 am, JK <·········@kneuro.net> wrote:
> +1. Forth is amazingly simple and elegant, although
> its elegance lies along a different axis than Lisp's.
> Building a working Forth VM by entering opcodes via
> front-panel switches seems quite feasible. Getting
> from there to an interactive Forth interpreter would
> be somewhat more challenging :-)
That's an interesting idea - use Forth to get the maximum
functionality with the minimum work, and build Lisp from that :-).
I'm poking around, and while most of what I see is Forth for various
operating systems I'm seeing a few suggestions to the effect that only
a few dozen instructions in machine code may be needed to start
building up a Forth system:
http://discuss.joelonsoftware.com/default.asp?design.4.357910.27
Does anybody know of a good forth implementation for machine
bootstrapping?
The next step would be implementing a basic Lisp in Forth (enough to
bootstrap ANSI). Does anyone know where either of these papers might
be had?
http://portal.acm.org/citation.cfm?id=59413.59429
http://portal.acm.org/citation.cfm?id=59413.59435
This might also be related (a thesis):
TLISP: A Small Lisp Interpreter Implemented in Forth Suryadevara,
Prasad Thomas Hand
I can't seem to find any references to even a way to order them, much
less find them online.
For more insanity, I wonder if one could design a motherboard that
used something like this http://www.ultratechnology.com/chips.htm to
provide the first Forth bootstrap environment directly in hardware
rather than as an implemention in another machine language.
Or, even beyond that, go straight to the source and have someone make
a tweaked version of the CADR hardware on a chip:
http://www.unlambda.com/cadr/index.html
Now THERE's a project idea - has anyone ever considered attempting to
implement an ANSI common lisp using the MIT CADR emulator as a
starting point? I suppose if you're down to this level, you might be
able to get to design your own hardware anyway, and if the target is
lisp you might as well make your hardware to support that direction.
That might be a way to create a real (or potentially real),
documented, "bootstrap from the metal" computer process that could
actually work, and could even be tested using the emulator (updated to
reflect any circuit modifications found to be necessary.) Then create
a book with all the hardware diagrams and describing how to physically
create the machine, and make that volume one of the manuals of the
system - "From Metal to Machine".
Neat - a project whose coolness is equaled only by its pointless
insanity :-).
C Y wrote:
> On Jun 12, 11:49 am, JK <·········@kneuro.net> wrote:
>
>>+1. Forth is amazingly simple and elegant, although
>>its elegance lies along a different axis than Lisp's.
>>Building a working Forth VM by entering opcodes via
>>front-panel switches seems quite feasible. Getting
>>from there to an interactive Forth interpreter would
>>be somewhat more challenging :-)
>
>
> That's an interesting idea - use Forth to get the maximum
> functionality with the minimum work, and build Lisp from that :-).
>
> I'm poking around, and while most of what I see is Forth for various
> operating systems I'm seeing a few suggestions to the effect that only
> a few dozen instructions in machine code may be needed to start
> building up a Forth system:
> http://discuss.joelonsoftware.com/default.asp?design.4.357910.27
A bare-bones "indirect-threaded" Forth VM's central loop
(aka the "inner interpreter") can be implemented in 10
instructions on the 386. (Probably fewer, but I know it
can be done in 10.) Once you've got the inner interpreter
going, hand-compiling Forth code is relatively simple.
You can hand-compile the interpreter and some I/O primitives,
and you're off to the races. My own iteration of this
process is available at the URL in my sig; although it's
strictly a toy, it does boot on an Intel PC and provide
a functioning Forth interpreter and bytecode compiler.
(But I cheated and used NASM instead of hand-compiling
all the way to machine code.)
I think the "Explicit Control Evaluator" for Scheme
(discussed in the later sections of SICP) might be
ported with a reasonable amount of effort, in order
to a achieve a Lisp-atop-Forth.
-- JK
http://www.kneuro.net/jkforth/
On Jun 14, 8:07 pm, JK <·········@kneuro.net> wrote:
> A bare-bones "indirect-threaded" Forth VM's central loop
> (aka the "inner interpreter") can be implemented in 10
> instructions on the 386. (Probably fewer, but I know it
> can be done in 10.) Once you've got the inner interpreter
> going, hand-compiling Forth code is relatively simple.
Wow.
> You can hand-compile the interpreter and some I/O primitives,
> and you're off to the races. My own iteration of this
> process is available at the URL in my sig; although it's
> strictly a toy, it does boot on an Intel PC and provide
> a functioning Forth interpreter and bytecode compiler.
Cool :-). Out of curosity, could it also be booted from a CDROM? (I
don't have much in the way of Floppy drives any more.)
> (But I cheated and used NASM instead of hand-compiling
> all the way to machine code.)
:-). Is that the step that would have to be done on a per-arch basis?
Or, perhaps a better question - how much code/functionality must be
customized to each platform before you can abstract to just Forth?
> I think the "Explicit Control Evaluator" for Scheme
> (discussed in the later sections of SICP) might be
> ported with a reasonable amount of effort, in order
> to a achieve a Lisp-atop-Forth.
Is that type of Scheme a subset of Lisp? (I don't know much about
Scheme, really - just that it's sort of a "small Lisp that isn't quite
lisp").
C Y <···········@yahoo.com> writes:
> On Jun 14, 8:07 pm, JK <·········@kneuro.net> wrote:
>> You can hand-compile the interpreter and some I/O primitives,
>> and you're off to the races. My own iteration of this
>> process is available at the URL in my sig; although it's
>> strictly a toy, it does boot on an Intel PC and provide
>> a functioning Forth interpreter and bytecode compiler.
>
> Cool :-). Out of curosity, could it also be booted from a CDROM? (I
> don't have much in the way of Floppy drives any more.)
You could probably use a simulator, such as Qemu or Bochs, to play
with it.
C Y wrote:
> Cool :-). Out of curosity, could it also be booted from a CDROM? (I
> don't have much in the way of Floppy drives any more.)
When I was actually working on the thing, I usually ran it
in a Bochs (bochs.sourceforge.net).
>>(But I cheated and used NASM instead of hand-compiling
>>all the way to machine code.)
>
> :-). Is that the step that would have to be done on a per-arch basis?
> Or, perhaps a better question - how much code/functionality must be
> customized to each platform before you can abstract to just Forth?
Not much. There are occasional "minimal Forth" threads on
c.l.forth which Google can find for you.
>>I think the "Explicit Control Evaluator" for Scheme
>>(discussed in the later sections of SICP) might be
>>ported with a reasonable amount of effort, in order
>>to a achieve a Lisp-atop-Forth.
>
>
> Is that type of Scheme a subset of Lisp? (I don't know much about
> Scheme, really - just that it's sort of a "small Lisp that isn't quite
> lisp").
Scheme is a full-fledged dialect of Lisp, macros and everything.
I think the various SICP evaluators handle only a subset, but
maybe enough to get further work done.
-- JK
C Y <···········@yahoo.com> writes:
> Now THERE's a project idea - has anyone ever considered attempting to
> implement an ANSI common lisp using the MIT CADR emulator as a
> starting point? I suppose if you're down to this level, you might be
> able to get to design your own hardware anyway, and if the target is
> lisp you might as well make your hardware to support that direction.
Actually, an idea I've had rolling around in my head would be to use
more available hardware to build a next-generation Lisp machine.
Consider that the amd64 architecture uses 64-bit pointers but current
implementations use only 48 bits to address memory[1]. The way the
math works is that you can treat addresses as sign-extended integers,
with the "negative" values pointing to the top half of memory and the
"positive" values pointing to the bottom half.
This means that you can do tagged pointers without losing a single bit
of addressability (unlike the way many current Lisps trade having
4-byte- or 8-byte-aligned pointers for some tag bits). You get 16 or,
if you want to allow for the next step in amd64 implementations which
would make use of 56 bits of their pointers, 8 bits of tagging and can
still have a pointer to any single byte in your address space.
Since tagged pointers would be easy to do and the hardware is readily
available and fairly inexpensive, it would theoretically not be all
that hard to build a next-generation Lisp machine on an amd64 system.
You'd need to put a lot of work into it, of course, but the end result
could certainly be quite worth it.
Any thoughts on this hare-brained idea?
[1] http://en.wikipedia.org/wiki/Amd64#Virtual_address_space_details
On Jun 14, 6:56 pm, Ari Johnson <·········@gmail.com> wrote:
> Since tagged pointers would be easy to do and the hardware is readily
> available and fairly inexpensive, it would theoretically not be all
> that hard to build a next-generation Lisp machine on an amd64 system.
> You'd need to put a lot of work into it, of course, but the end result
> could certainly be quite worth it.
>
> Any thoughts on this hare-brained idea?
It's a neat one. Of course, in a TRUE bootstrap situation you need to
be able to build hardware that can be (at least in theory) built
without having to use a computer to control the machines needed to
make the hardware, and once you've got the hardware that can do that
you don't have a true bootstrap situation (in the "hardest" sense)
since you have at least the computers needed to make an amd64 already
present. For today's hardware however, it's a very interesting idea.
I guess my first thought would be that to build a new Lisp machine, a
lot of pieces not covered by ANSI would be needed - drivers, video
display, etc. Would all that need to be re-designed from the
beginning? (I'm assuming it would be if the full benefit from the
drivers is to be realized.)
C Y <···········@yahoo.com> writes:
> On Jun 14, 6:56 pm, Ari Johnson <·········@gmail.com> wrote:
>> Since tagged pointers would be easy to do and the hardware is readily
>> available and fairly inexpensive, it would theoretically not be all
>> that hard to build a next-generation Lisp machine on an amd64 system.
>> You'd need to put a lot of work into it, of course, but the end result
>> could certainly be quite worth it.
>>
>> Any thoughts on this hare-brained idea?
>
> It's a neat one. Of course, in a TRUE bootstrap situation you need to
> be able to build hardware that can be (at least in theory) built
> without having to use a computer to control the machines needed to
> make the hardware, and once you've got the hardware that can do that
> you don't have a true bootstrap situation (in the "hardest" sense)
> since you have at least the computers needed to make an amd64 already
> present. For today's hardware however, it's a very interesting idea.
I certainly wasn't thinking of going that far. My idea isn't to play
around with the world of bootstrapping from desert sand into a working
system so much as to have a nifty workstation.
> I guess my first thought would be that to build a new Lisp machine, a
> lot of pieces not covered by ANSI would be needed - drivers, video
> display, etc. Would all that need to be re-designed from the
> beginning? (I'm assuming it would be if the full benefit from the
> drivers is to be realized.)
You could always build ANSI CL on top of whatever dialect of Lisp you
end up exposing to the user from the OS.
Ari Johnson <·········@gmail.com> writes:
> Actually, an idea I've had rolling around in my head would be to use
> more available hardware to build a next-generation Lisp machine.
> Consider that the amd64 architecture uses 64-bit pointers but current
> implementations use only 48 bits to address memory[1]. The way the
> math works is that you can treat addresses as sign-extended integers,
> with the "negative" values pointing to the top half of memory and the
> "positive" values pointing to the bottom half.
>
> This means that you can do tagged pointers without losing a single bit
> of addressability (unlike the way many current Lisps trade having
> 4-byte- or 8-byte-aligned pointers for some tag bits). You get 16 or,
> if you want to allow for the next step in amd64 implementations which
> would make use of 56 bits of their pointers, 8 bits of tagging and can
> still have a pointer to any single byte in your address space.
>
> Since tagged pointers would be easy to do and the hardware is readily
> available and fairly inexpensive, it would theoretically not be all
> that hard to build a next-generation Lisp machine on an amd64 system.
> You'd need to put a lot of work into it, of course, but the end result
> could certainly be quite worth it.
>
> Any thoughts on this hare-brained idea?
We should take a lesson from prior efforts. In the days of the
IBM/360, which had 24-bits of address in a 32-bit data path, the upper
8 bits were used not only by lisp implementations, but also by other
applications, which took advantage of those upper bits to tag data in
various ways. The reasoning was "well, nobody will ever use all 24
bits for addressing, let alone 32 bits; we're safe in using those
bits." Then came the XA architecture (the extension of the address
space to 32 bits) and there was quite a scramble to change the
software to be compatible with the new addressing. Unfortunately any
program that used those upper bits were not portable to XA, because
whereas in the 24-bit addressing the value #x00123456 represented the
same address as #x80123456, in XA they were actually different
addresses and the upper byte would have to be masked out before any
addressing operation occured - this negated the "free" advantage of
having those extra bits.
Back to the present: we know that x86-64 arechitecture limits its
number of bits of addressing, but we don't know for how long - the
chip vendors themselves probably don't know for sure - it will
probably be driven by competition. And although the x86-64 seems to
be at the top of the hill right now in popularity, there is no reason
to assume that it will stay that way. So I would guess, for now, that
you have at least a few years to implement and make popular your "new"
tagging design, which is architecture-specific. Note that other
architectures vary in the number of bits that are significant. We at
Franz have decided that it is not worth the risk of making such an
effort, only to have the rug pulled out from under us because of an
assumption that cannot be guaranteed.
--
Duane Rettig ·····@franz.com Franz Inc. http://www.franz.com/
555 12th St., Suite 1450 http://www.555citycenter.com/
Oakland, Ca. 94607 Phone: (510) 452-2000; Fax: (510) 452-0182
On Jun 15, 6:40 pm, Duane Rettig <····@franz.com> wrote:
>
>
> Back to the present: we know that x86-64 arechitecture limits its
> number of bits of addressing, but we don't know for how long - the
> chip vendors themselves probably don't know for sure - it will
> probably be driven by competition. And although the x86-64 seems to
> be at the top of the hill right now in popularity, there is no reason
> to assume that it will stay that way. So I would guess, for now, that
> you have at least a few years to implement and make popular your "new"
> tagging design, which is architecture-specific. Note that other
> architectures vary in the number of bits that are significant. We at
> Franz have decided that it is not worth the risk of making such an
> effort, only to have the rug pulled out from under us because of an
> assumption that cannot be guaranteed.
Well, you can buy machines now which can have up to 41 bits of address
space of *physical* memory in their maximal configuration (128GB per
board, 16 boards). And this is just machines I know about, there are
probably larger ones. It's rather unlikely that one of these boxes
would be run as a single logical host rather than domained, but it
could be. So I can foresee machines which would exceed the limit in a
few years.
And that doesn't even start to describe the problem. What about, for
instance, wanting to map a (possibly sparse) file? Files can be
really, really big...
--tim
Tim Bradshaw <··········@tfeb.org> wrote:
+---------------
| Well, you can buy machines now which can have up to 41 bits of address
| space of *physical* memory in their maximal configuration (128GB per
| board, 16 boards). And this is just machines I know about, there are
| probably larger ones.
+---------------
The SGI Altix 4700 <http://www.sgi.com/products/servers/altix/4000/>
can be ordered with up to 128 TB of main memory, which takes 47 bits
to address, but the IO/memory split takes one more bit, so that's
really 48 bits of physical address in a commercial product *today*!
[By the way, that's with up to 512 CPUs running ccNUMA, with
all of the memory cache-coherently available to all the CPUs
(sequential consistency, same as SMP).]
+---------------
| It's rather unlikely that one of these boxes would be run as a
| single logical host rather than domained, but it could be.
+---------------
The SGI Altix 4700 does that. It's even supported in that
configuration by both SuSE [Enterprise Server 9 or 10] and
RedHat [Enterprise Advanced Server 4 or 5] Linuxes (though
you probably really, really want to add SGI ProPack to get
the extra tuning tools).
+---------------
| So I can foresee machines which would exceed the limit in a few years.
+---------------
Yup.
+---------------
| And that doesn't even start to describe the problem. What about,
| for instance, wanting to map a (possibly sparse) file? Files can
| be really, really big...
+---------------
Well, now that you mention it... ;-} ;-}
SGI's XFS filesystem already supports file sizes up to 9.0e18 bytes,
which is already 63 bits. [It would have been 64, but a Unix/Linux
seek pointer is a signed integer, so you lose the sign bit. They
*do* permit 18.0e18 bytes (64 bits) per filesystem, though.]
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Duane Rettig <·····@franz.com> writes:
> Ari Johnson <·········@gmail.com> writes:
>
>> Actually, an idea I've had rolling around in my head would be to use
>> more available hardware to build a next-generation Lisp machine.
>> Consider that the amd64 architecture uses 64-bit pointers but current
>> implementations use only 48 bits to address memory[1]. The way the
>> math works is that you can treat addresses as sign-extended integers,
>> with the "negative" values pointing to the top half of memory and the
>> "positive" values pointing to the bottom half.
>>
>> This means that you can do tagged pointers without losing a single bit
>> of addressability (unlike the way many current Lisps trade having
>> 4-byte- or 8-byte-aligned pointers for some tag bits). You get 16 or,
>> if you want to allow for the next step in amd64 implementations which
>> would make use of 56 bits of their pointers, 8 bits of tagging and can
>> still have a pointer to any single byte in your address space.
>>
>> Since tagged pointers would be easy to do and the hardware is readily
>> available and fairly inexpensive, it would theoretically not be all
>> that hard to build a next-generation Lisp machine on an amd64 system.
>> You'd need to put a lot of work into it, of course, but the end result
>> could certainly be quite worth it.
>>
>> Any thoughts on this hare-brained idea?
>
> We should take a lesson from prior efforts. In the days of the
> IBM/360, which had 24-bits of address in a 32-bit data path, the upper
> 8 bits were used not only by lisp implementations, but also by other
> applications, which took advantage of those upper bits to tag data in
> various ways. The reasoning was "well, nobody will ever use all 24
> bits for addressing, let alone 32 bits; we're safe in using those
> bits." Then came the XA architecture (the extension of the address
> space to 32 bits) and there was quite a scramble to change the
> software to be compatible with the new addressing. Unfortunately any
> program that used those upper bits were not portable to XA, because
> whereas in the 24-bit addressing the value #x00123456 represented the
> same address as #x80123456, in XA they were actually different
> addresses and the upper byte would have to be masked out before any
> addressing operation occured - this negated the "free" advantage of
> having those extra bits.
>
> Back to the present: we know that x86-64 arechitecture limits its
> number of bits of addressing, but we don't know for how long - the
> chip vendors themselves probably don't know for sure - it will
> probably be driven by competition. And although the x86-64 seems to
> be at the top of the hill right now in popularity, there is no reason
> to assume that it will stay that way. So I would guess, for now, that
> you have at least a few years to implement and make popular your "new"
> tagging design, which is architecture-specific. Note that other
> architectures vary in the number of bits that are significant. We at
> Franz have decided that it is not worth the risk of making such an
> effort, only to have the rug pulled out from under us because of an
> assumption that cannot be guaranteed.
Addressing wouldn't be broken because you would be forced to do the
masking yourself. It is my understanding that x86-64 will signal an
exception if you attempt to dereference an address that is not in
"canonical form," meaning one that would point to memory in the
unaddressable middle of the address space.
The idea, though, was not to create a Lisp that can be used on top of
any x86-64 platform, but rather to create a Lisp-centric platform atop
the x86-64 hardware. Whether this is a useful idea in any way is an
exercise for the reader, but it is no different than the use of Lisp
machine hardware that provides 40-bit tagged pointers with a 32-bit
address space. Like I said, a next-generation Lisp machine, not a
generic and for-all-time Lisp. We have those already and they are
probably much more useful than a new Lisp machine would be, anyhow. :)
On Jun 14, 6:21 pm, C Y <···········@yahoo.com> wrote:
> Or, even beyond that, go straight to the source and have someone make
> a tweaked version of the CADR hardware on a chip:
>
> http://www.unlambda.com/cadr/index.html
>
> Now THERE's a project idea - has anyone ever considered attempting to
> implement an ANSI common lisp using the MIT CADR emulator as a
> starting point? I suppose if you're down to this level, you might be
> able to get to design your own hardware anyway, and if the target is
> lisp you might as well make your hardware to support that direction.
>
1. The issues of bootstrapping are only a very, very, small fraction
of the issues involved in making a good Common Lisp implementation.
2. One of the important basic issues is how to get adequate run-time
performance. Most modern CL implementations need sophisticated
compilers, clever calling conventions and memory coding, and carefully
coded garbage collectors. These are all linked together. The treatment
of multi-threading and interaction with the operating environment cuts
across all of these as well.
3. The CADR system (and its descendants) chose an architecture of a
microcoded uniprocessor, with a specialized tagged memory architecture
to solve the problem of run-time performance. They were competitive at
the time with Lisp compilers on contemporary CPUs, but further
increases in performance depended on hardware improvements to speed up
the microarchitecture, and the resulting software is very hard to port
to general purpose CPUs, as opposed to emulation layers. Once you need
an emulation layer of software, you are basically never going to beat
the Lisp implementations running without that extra layer of overhead,
so this strategy only helps preserve the investment in the original
non-portable software, while continuing to lag in performance.
It is not at all clear that such a machine could be efficiently
implemented with today's available FPGAs, for instance. I'm guessing
that, even if it is possible, such explicitly microcoded CPUs are
probably not the most efficient way to use FPGA gates, and
furthermore, even if you did, the resulting CPU would not compete very
strongly against general purpose CPUs and modern Lisp implementations.
Part of the basis for my belief is that no-one appears to be
successfully creating emulators of old DEC CPUs in FPGA hardware, and
I suppose many more people used those than Lisp Machines; another is
that CPUs designed for FPGAs generally are RISC. I could be quite
wrong.
Even projects to replicate 8-bit microcomputers tend not to give very
exciting results.
On Jun 15, 7:40 pm, ···············@hotmail.com"
<············@gmail.com> wrote:
> 1. The issues of bootstrapping are only a very, very,
> small fraction of the issues involved in making a
> good Common Lisp implementation.
Quite true. The question of making a good implementation is not
actually central to my original question - my focus is more on the
question of going from bare, inanimate hardware to a Lisp environment
- "desert sand to running machine" is a good phrase. Presumably, once
the not-so-good Lisp is running, it could be used to compile the good
Lisp - but that first, high performance implementation is probably not
a good target for a hard bootstrap.
My question doesn't really have any bearing on a modern situation
(baring, as someone else mentioned above, a doomsday scenario where we
have lost all technology). It's more of an intellectual exercise and
a historical curiosity - even if it never will again be necessary to
actually perform a hard, no technology bootstrap I would like to
understand the process - kind of a "where did we come from" question.
I suppose it might not hurt to actually have prepared the actual
necessary steps in case some unforeseen disaster actually DOES require
the process (or a space colony which must start industry from very
minimal resources, perhaps) but I'm not seriously proposing such a
project. It could be correctly characterized as both massively
difficult and unnecessary so long as our current technological base
endures.
> 2. One of the important basic issues is how to get
> adequate run-time performance. Most modern CL
> implementations need sophisticated
> compilers, clever calling conventions and memory coding, > and carefully coded garbage collectors. These are all
> linked together. The treatment of multi-threading and
> interaction with the operating environment cuts
> across all of these as well.
Right. My curiosity was directed towards the question "If we were
forced again to start from nothing, how do we get to a reasonably
modern CL with the minimum amount of effort?"
> 3. The CADR system (and its descendants) chose an
> architecture of a microcoded uniprocessor, with a
> specialized tagged memory architecture to solve the
> problem of run-time performance. They were competitive at
> the time with Lisp compilers on contemporary CPUs, but
> further increases in performance depended on hardware
> improvements to speed up the microarchitecture, and the
> resulting software is very hard to port to general
> purpose CPUs, as opposed to emulation layers. Once you
> need an emulation layer of software, you are basically
> never going to beat the Lisp implementations running
> without that extra layer of overhead, so this strategy
> only helps preserve the investment in the original
> non-portable software, while continuing to lag in
> performance.
So was the design decision incorrect even at the time? I'm sure
modern systems have moved ahead but if one had to start from designing
the bare metal using very basic technology would the original tradeoff
still make sense? (I.e. you're building the machines you will use to
build the machines you actually WANT to work with.)
> It is not at all clear that such a machine could be
> efficiently implemented with today's available FPGAs,
> for instance. I'm guessing that, even if it is possible,
> such explicitly microcoded CPUs are probably not the
> most efficient way to use FPGA gates, and furthermore,
> even if you did, the resulting CPU would not compete very
> strongly against general purpose CPUs and modern Lisp
> implementations.
Not surprising. The goal for this system wouldn't be top performance,
but achieving maximum capability with minimal starting resources.
I.e., the system which would let you implement the modern system. I'm
not proposing to actually build it, and certainly I wouldn't expect it
to achieve anything interesting performance wise - I'm just curious as
to what the "best" path would be if we WERE forced to begin again.
On Jun 15, 12:21 am, C Y <···········@yahoo.com> wrote:
> On Jun 12, 11:49 am, JK <·········@kneuro.net> wrote:
>
> > +1. Forth is amazingly simple and elegant, although
> > its elegance lies along a different axis than Lisp's.
> > Building a working Forth VM by entering opcodes via
> > front-panel switches seems quite feasible. Getting
> > from there to an interactive Forth interpreter would
> > be somewhat more challenging :-)
>
> That's an interesting idea - use Forth to get the maximum
> functionality with the minimum work, and build Lisp from that :-).
>
> I'm poking around, and while most of what I see is Forth for various
> operating systems I'm seeing a few suggestions to the effect that only
> a few dozen instructions in machine code may be needed to start
> building up a Forth system:http://discuss.joelonsoftware.com/default.asp?design.4.357910.27
>
> Does anybody know of a good forth implementation for machine
> bootstrapping?
>
> The next step would be implementing a basic Lisp in Forth (enough to
> bootstrap ANSI). Does anyone know where either of these papers might
> be had?
>
> http://portal.acm.org/citation.cfm?id=59413.59429http://portal.acm.org/citation.cfm?id=59413.59435
>
> This might also be related (a thesis):
> TLISP: A Small Lisp Interpreter Implemented in Forth Suryadevara,
> Prasad Thomas Hand
>
> I can't seem to find any references to even a way to order them, much
> less find them online.
>
> For more insanity, I wonder if one could design a motherboard that
> used something like thishttp://www.ultratechnology.com/chips.htmto
> provide the first Forth bootstrap environment directly in hardware
> rather than as an implemention in another machine language.
>
> Or, even beyond that, go straight to the source and have someone make
> a tweaked version of the CADR hardware on a chip:
>
> http://www.unlambda.com/cadr/index.html
>
> Now THERE's a project idea - has anyone ever considered attempting to
> implement an ANSI common lisp using the MIT CADR emulator as a
> starting point? I suppose if you're down to this level, you might be
> able to get to design your own hardware anyway, and if the target is
> lisp you might as well make your hardware to support that direction.
>
> That might be a way to create a real (or potentially real),
> documented, "bootstrap from the metal" computer process that could
> actually work, and could even be tested using the emulator (updated to
> reflect any circuit modifications found to be necessary.) Then create
> a book with all the hardware diagrams and describing how to physically
> create the machine, and make that volume one of the manuals of the
> system - "From Metal to Machine".
>
> Neat - a project whose coolness is equaled only by its pointless
> insanity :-).
Thanks for the link. This newsgroup is getting more interesting all
the time, since I started my own microprocessor design, simulated in
Common Lisp (btw. for anyone who might be interested, what I dub the
r1 iteration, has been completed after 10 months work, the only thing
I should do yet is setup my current website to publish anything).
One of the things that I was thinking about was almost the same as the
post which started the thread : implement a C compiler first, or go
for a way to implement a CL ? One possibility is to create a system
which implements CLISP byte codes.
Going to the bare metal is more difficult, but the idea that seemed
most logical to me (and which I found also used by Movitz), is to
create a library between the processor and the CL implementation,
which can be called with the standard CL calling mechanism, and which
returns objects which can be used by CL.
In the case of Movitz, this part is called Muerte, and is probably now
mostly geared towards the x86. However, it should be possible to
define a more abstract machine, and have assemblers and data files in
Common Lisp, geared towards specific architectures and which provide
primitives to control the hardware, and implement a CL with a virtual
system control library on top of that.
For me personally, in view of my own project, the choice between C and
CL is not that clear cut. If one chooses for C, then a whole lot of
software is immediately available, CL included. If one chooses for CL,
then what software is available that is only written in CL ? Is there
a TCP/IP stack available e.g. ? What about stable editors ?
Regards,
Jurgen
On Jun 25, 4:14 am, jurgen_defurne <··············@pandora.be> wrote:
> Thanks for the link. This newsgroup is getting more interesting all
> the time, since I started my own microprocessor design, simulated in
> Common Lisp (btw. for anyone who might be interested, what I dub the
> r1 iteration, has been completed after 10 months work, the only thing
> I should do yet is setup my current website to publish anything).
Cool!
> One of the things that I was thinking about was almost the same as the
> post which started the thread : implement a C compiler first, or go
> for a way to implement a CL ? One possibility is to create a system
> which implements CLISP byte codes.
Hmm. One thought - if you use the Clisp byte code, does that make
everything that can run on the system GPL by default? It's been a
while since I looked at the Clisp licensing stuff...
> Going to the bare metal is more difficult, but the idea that seemed
> most logical to me (and which I found also used by Movitz), is to
> create a library between the processor and the CL implementation,
> which can be called with the standard CL calling mechanism, and which
> returns objects which can be used by CL.
You mean a library in machine/assembly language?
> In the case of Movitz, this part is called Muerte, and is probably now
> mostly geared towards the x86. However, it should be possible to
> define a more abstract machine, and have assemblers and data files in
> Common Lisp, geared towards specific architectures and which provide
> primitives to control the hardware, and implement a CL with a virtual
> system control library on top of that.
Sort of a driver system which is geared to providing a Lisp virtual
machine?
> For me personally, in view of my own project, the choice between C and
> CL is not that clear cut. If one chooses for C, then a whole lot of
> software is immediately available, CL included. If one chooses for CL,
> then what software is available that is only written in CL ? Is there
> a TCP/IP stack available e.g. ? What about stable editors ?
Going for existing functional software, C is almost certainly the
clear winner today. I don't know about TCP/IP stacks for Lisp - if
Movitz or the CADR lisp machine code don't have anything I'm not sure
who would. Stable editors... as far as stuff written entirely in
Lisp I don't know of too much - Movitz has some kind of Emacs-like
editor running, and there is Climacs.
I guess I'm a bit unclear - are you scratch designing a new Lisp
machine including operating system, or wanting a new chip to run
existing applications (including CL) on?
jurgen_defurne wrote:
> For me personally, in view of my own project, the choice between C and
> CL is not that clear cut. If one chooses for C, then a whole lot of
> software is immediately available, CL included. If one chooses for CL,
> then what software is available that is only written in CL ? Is there
> a TCP/IP stack available e.g. ?
slitch: see http://lukego.livejournal.com/4993.html
> What about stable editors ?
Hemlock has been around since the 1980s I think, so for some definition
that counts as "stable". It probably has some unix dependencies, but
nothing insuperable.
-dan
On Jun 26, 1:40 am, Daniel Barlow <····@coruskate.net> wrote:
> jurgen_defurne wrote:
> > For me personally, in view of my own project, the choice between C and
> > CL is not that clear cut. If one chooses for C, then a whole lot of
> > software is immediately available, CL included. If one chooses for CL,
> > then what software is available that is only written in CL ? Is there
> > a TCP/IP stack available e.g. ?
>
> slitch: seehttp://lukego.livejournal.com/4993.html
>
> > What about stable editors ?
>
> Hemlock has been around since the 1980s I think, so for some definition
> that counts as "stable". It probably has some unix dependencies, but
> nothing insuperable.
>
> -dan
Yeah, I was thinking about Hemlock, but I could not remember the name.
I tried it once, but it hung quite fast. Thats the reference about
stable editors.
Jurgen
Gene wrote:
> On Jun 11, 2:58 pm, C Y <···········@yahoo.com> wrote:
>> A year or so back, there was a rather interesting discussion on what
>> was termed "minimal" subsets of Lisp. I am curious if anything
>> further has happened with some of the efforts discussed in terms of
>> creating "minimal" lisps.
>>
>> I have a specific question of interest on the subject, and I'll do my
>> best to word it precisely:
>>
>> Given a hardware situation where NO compiler is available for any
>> language above the assembly level, and the goal is a running ANSI
>> Common Lisp, what would be the implementation path to take that would
>> result in the least amount of low level coding (or least difficult, if
>> the minimal AMOUNT of low level code would involve difficult coding)
>> that would produce a working ANSI Common Lisp? Assume a source code
>> version of ANSI Common Lisp that was written itself in ANSI Common
>> Lisp, in such a fashion that it could build more complex layers
>> without recursive calls to functionality in other complex layers (such
>> a beast would have to know what the core building blocks it would have
>> to work with would be, of course - so it would have to be written in
>> such a fashion that no single part of the definition required that its
>> own definition already be working, except for the parts to be
>> implemented in assembly language.)
[...]
>> P.S. I will confess a background motivation for this question is the
>> Axiom project, which is founded on Lisp - the "30-year horizon"
>> thinking of our project leader also lead me to the question "how can
>> the knowledge being encoded into these computer languages survive
>> indefinitely - what would it take to revive the living Axiom system
>> even if we are somehow left with no running system which supports our
>> current binary dependencies or understands our source code? Well, if
>> we work inside Lisp for everything (a goal for at least some of us on
>> the project) that reduces the question to "how does one get Lisp
>> working starting from nothing?" (OK, OK there are issues with
>> graphics systems like X and GDI and whatnot - but the core of the
>> system is non-graphical.) It is not a likely scenario but interesting
>> enough for me to pose the question. It also might have some bearing
>> on formally proving correctness on various platforms, but I don't know
>> enough about that yet to be sure.
>
> "Historical" is right. A one-machine bootstrap is quite literally an
> awesome task, not least because you need tools like an editor and file
> handling. Are all these to be written in assembly language? I've
> never heard of someone doing that since the early 60's.
>
> Anyway, it's just as you say. Implement a very minimal L subset
> compiler (or interpreter) C in assembly then rewrite (or write) the
> compiler in the L subset (call this C'), use C to compile C'. Now use
> C' to compile C', and you're off to the races. Keep adding
> functionality so that C' compiles ever more of L. As soon as you
> implement a new feature F, you can recompile C' and then rewrite C' to
> use F and recompile yet again.
>
> As a practical matter, it may be easier to bootstrap a language other
> than CL, e.g. try ANSI C to get a compiler that will compile gcc, then
> use this to build one of the standard C-based CL systems.
How well specified is clisp's virtual machine, and how big is the set of
primitives/subprimitives? It seems to me that for the purpose you're
sort of thinking about, being able to implement a simple VM would
probably suffice. (ABCL might be another useful candidate, since the
specification of the Java virtual machines will likely be around for a
while.)
On the one hand, compiling to some kind of byte code will be slower
(execution-wise) than compiling to bare metal, but on the other hand
barring some kind of _Canticle for Leibowitz)_ scenario any machine that
might be used to re-animate your work would likely be signficantly
faster. And you might even be in a position to turn a VM specification
directly into something much like hardware. Or use whatever JIT
compilers are around then to turn your combination of VM and VM code
into code for whatever's around.
(My assumptions, probably wrong, about future recover of current or past
software is that the investigators will have pretty good tools for
programming, and that the main problem will be the creation of
sufficiently accurate emulations.)
paul
Paul Wallich <··@panix.com> wrote:
+---------------
| Gene wrote:
| > As a practical matter, it may be easier to bootstrap a language other
| > than CL, e.g. try ANSI C to get a compiler that will compile gcc, then
| > use this to build one of the standard C-based CL systems.
|
| How well specified is clisp's virtual machine, and how big is the set of
| primitives/subprimitives? It seems to me that for the purpose you're
| sort of thinking about, being able to implement a simple VM would
| probably suffice. (ABCL might be another useful candidate, since the
| specification of the Java virtual machines will likely be around for a
| while.)
+---------------
CMUCL's byte codes might also be a good choice. They run in the
same VM as normal compiled-to-machine-code CMUCL functions, and
byte-compiled functions can can & be called by native-compiled
functions. If I'm reading the CMUCL source correctly, there are
only ~23 bytes codes you need to implement [though some of them
have fairly hairy semantics under the covers].
To implement the byte-code VM on bare metal, I would write a
cross-assembler in CL, then write code the interpreter for the
byte-code VM in a DSL consisting of CL macros that expanded
to assembler source [well, "source" here being one s-expr per
instruction], much like the "VOPs" in the CMUCL native compiler
itself. [You can use CMUCL's own byte-code interpreter as a
model.] Add some start-up & driver code (in the same assembler),
cross-assemble, cross-link, & copy over, and you have your "VM".
Then just use the normal CMUCL compiler to byte-compile any code
you want [such as the full CMUCL compiler itself!!], and copy the
byte-compiled FASLs across to run in your VM. [Yes, this means the
VM will also have to be taught how to read CMUCL ".bytef" FASLs.]
It's interesting that this topic is coming up at this point.
For some time now, I've actually been discussing this [building
a standalone CMUCL byte-code VM, only in C, not assembler] with
some friends as a possible way to simplify the bootstrapping of
CMUCL itself, with the goal being same one as achieved by the SBCL
project -- that is, to be able to compile the system "from scratch"
with only a C compiler for the target architecture and only "some"
running CL implementation available (on the same or a connected
machine) -- but using a rather different approach (the byte-code VM)
to get to that goal.
+---------------
| On the one hand, compiling to some kind of byte code will be
| slower (execution-wise) than compiling to bare metal...
+---------------
Yes, significantly slower. The following function:
(defun spin (x)
(dotimes (i x)
(declare (fixnum i x))))
when run in CMUCL's interpreter, byte-compiled, and native-compiled
modes on an x86 architecture takes about 7400, 700, and 2 cycles per
iteration, respectively.[1] That is, for this particular trivial
micro-benchmark, byte-compiled code is about 350 times slower than
native machine code, and raw interpreted code[2] is another 10+ times
slower than that.
But, hey, what's a mere factor of 350x amongst friends during
bootstrapping?!? ;-} ;-}
-Rob
[1] Note: On x86, the native-compiled inner loop for SPIN is
these four instructions [and, yes, the "MOV ECX, EBX" could
be hoisted outside the loop!]:
L0: ADD EAX, 4
L1: MOV ECX, EBX
CMP EAX, ECX
JL L0
On Athlon CPUs [including Athlon-64 in 32-bit mode], the speed
of this four-instruction loop depends on the memory alignment
of the compiled code. I haven't done an extensive analysis, but
it appears that some alignments produce the 2 CPU-cycle/iteration
speed I report above, while some alignments yield 3 cycles/iteration.
I have seen the speed of SPIN change from one to the other (or back)
as a result of a GC.
[2] Well, even "interpreted" code in CMUCL is "IR1-converted" before
being run, so that macros are only expanded once.
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Gene <············@gmail.com> writes:
> "Historical" is right. A one-machine bootstrap is quite literally an
> awesome task, not least because you need tools like an editor and file
> handling. Are all these to be written in assembly language? I've
> never heard of someone doing that since the early 60's.
I did quite a lot of a single machine bootstrap in the early 80's.
I was a young hobbyist bootstrapping a home-brew machine
based around the Motorola 6809 micro-processor. (That was the
8-bit stop gap between the 6800 and 68000)
I wrote an assembler in machine code. Now-a-days this kind
of obessive/compulsive disorder can be treated with
selective serotonin re-uptake inhibitors, 60mg fluoxetine
being a typcial daily dose.
I then coded routines to implement cons, car, and cdr, and a
garbage collector. The aim was to write a very simple Lisp
interpretter. I got as far as writing assembler that used my
routines to compute pascals triangle. I think I hand
compiled something like
(defun pascal (list)
(print list)
(pascal (mapcar #'+
(cons 0 list)
(append list (list 0)))))
My garbage collector seemed to work, letting me cons
megabytes on a machine with 32kilobytes of RAM. It is of
course crucial to continue taking medication to avoid a
relapse.
If you want to target a 6809 I still have the listings from
the assembler. (I still have the machine but the monitor
EPROM has forgotten.)
Alan Crowe
Edinburgh
Scotland
On Jun 12, 10:48 am, Alan Crowe <····@cawtech.freeserve.co.uk> wrote:
> If you want to target a 6809 I still have the listings from
> the assembler. (I still have the machine but the monitor
> EPROM has forgotten.)
That would be neat to see, actually :-). Is it online somewhere?
Alan Crowe <····@cawtech.freeserve.co.uk> writes:
> Gene <············@gmail.com> writes:
>
>> "Historical" is right. A one-machine bootstrap is quite literally an
>> awesome task, not least because you need tools like an editor and file
>> handling. Are all these to be written in assembly language? I've
>> never heard of someone doing that since the early 60's.
>
> I did quite a lot of a single machine bootstrap in the early 80's.
> I was a young hobbyist bootstrapping a home-brew machine
> based around the Motorola 6809 micro-processor. (That was the
> 8-bit stop gap between the 6800 and 68000)
>
> I wrote an assembler in machine code. Now-a-days this kind
> of obessive/compulsive disorder can be treated with
> selective serotonin re-uptake inhibitors, 60mg fluoxetine
> being a typcial daily dose.
>
> I then coded routines to implement cons, car, and cdr, and a
> garbage collector. The aim was to write a very simple Lisp
> interpretter. I got as far as writing assembler that used my
> routines to compute pascals triangle. I think I hand
> compiled something like
>
> (defun pascal (list)
> (print list)
> (pascal (mapcar #'+
> (cons 0 list)
> (append list (list 0)))))
>
> My garbage collector seemed to work, letting me cons
> megabytes on a machine with 32kilobytes of RAM. It is of
> course crucial to continue taking medication to avoid a
> relapse.
>
> If you want to target a 6809 I still have the listings from
> the assembler. (I still have the machine but the monitor
> EPROM has forgotten.)
If you wanted to bootstrap on current hardware, you wouldn't have to
write the garbage collector so soon. AFAIK, Movitz runs without a
garbage collector yet.
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
On Jun 12, 11:04 am, Pascal Bourguignon <····@informatimago.com>
wrote:
> If you wanted to bootstrap on current hardware, you wouldn't have to
> write the garbage collector so soon. AFAIK, Movitz runs without a
> garbage collector yet.
Movitz has a 2-space copying GC. I believe that NIL, however, did not
have any.
Paul Khuong
Alan Crowe <····@cawtech.freeserve.co.uk> writes:
> I did quite a lot of a single machine bootstrap in the early 80's.
> I was a young hobbyist bootstrapping a home-brew machine
> based around the Motorola 6809 micro-processor. (That was the
> 8-bit stop gap between the 6800 and 68000)
>
> I wrote an assembler in machine code. Now-a-days this kind
> of obessive/compulsive disorder can be treated with
> selective serotonin re-uptake inhibitors, 60mg fluoxetine
> being a typcial daily dose.
>
> I then coded routines to implement cons, car, and cdr, and a
> garbage collector. The aim was to write a very simple Lisp
> interpretter. I got as far as writing assembler that used my
> routines to compute pascals triangle. I think I hand
> compiled something like
>
> (defun pascal (list)
> (print list)
> (pascal (mapcar #'+
> (cons 0 list)
> (append list (list 0)))))
>
> My garbage collector seemed to work, letting me cons
> megabytes on a machine with 32kilobytes of RAM. It is of
> course crucial to continue taking medication to avoid a
> relapse.
>
> If you want to target a 6809 I still have the listings from
> the assembler. (I still have the machine but the monitor
> EPROM has forgotten.)
Consider me suitable impressed!
This is the kind of stuff I'd dreamet of doing, but never really learned
enough to getting started. I might be the medication is added to the
water where I live.
/andreas
--
A: Because it fouls the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
In article <·······················@c77g2000hse.googlegroups.com>,
C Y <···········@yahoo.com> wrote:
> A year or so back, there was a rather interesting discussion on what
> was termed "minimal" subsets of Lisp. I am curious if anything
> further has happened with some of the efforts discussed in terms of
> creating "minimal" lisps.
>
> I have a specific question of interest on the subject, and I'll do my
> best to word it precisely:
>
> Given a hardware situation where NO compiler is available for any
> language above the assembly level, and the goal is a running ANSI
> Common Lisp, what would be the implementation path to take that would
> result in the least amount of low level coding (or least difficult, if
> the minimal AMOUNT of low level code would involve difficult coding)
> that would produce a working ANSI Common Lisp? Assume a source code
> version of ANSI Common Lisp that was written itself in ANSI Common
> Lisp, in such a fashion that it could build more complex layers
> without recursive calls to functionality in other complex layers (such
> a beast would have to know what the core building blocks it would have
> to work with would be, of course - so it would have to be written in
> such a fashion that no single part of the definition required that its
> own definition already be working, except for the parts to be
> implemented in assembly language.)
>
OpenMCL needs C. From there it can bootstrap itself, AFAIK.
--
http://lispm.dyndns.org
Rainer Joswig <······@lisp.de> writes:
> In article <·······················@c77g2000hse.googlegroups.com>,
> C Y <···········@yahoo.com> wrote:
>
>> A year or so back, there was a rather interesting discussion on what
>> was termed "minimal" subsets of Lisp. I am curious if anything
>> further has happened with some of the efforts discussed in terms of
>> creating "minimal" lisps.
>>
>> I have a specific question of interest on the subject, and I'll do my
>> best to word it precisely:
>>
>> Given a hardware situation where NO compiler is available for any
>> language above the assembly level, and the goal is a running ANSI
>> Common Lisp, what would be the implementation path to take that would
>> result in the least amount of low level coding (or least difficult, if
>> the minimal AMOUNT of low level code would involve difficult coding)
>> that would produce a working ANSI Common Lisp? Assume a source code
>> version of ANSI Common Lisp that was written itself in ANSI Common
>> Lisp, in such a fashion that it could build more complex layers
>> without recursive calls to functionality in other complex layers (such
>> a beast would have to know what the core building blocks it would have
>> to work with would be, of course - so it would have to be written in
>> such a fashion that no single part of the definition required that its
>> own definition already be working, except for the parts to be
>> implemented in assembly language.)
>>
>
> OpenMCL needs C. From there it can bootstrap itself, AFAIK.
It needs a working lisp, AFAICT. [1] claims that "[t]here's a
circular dependency between the full heap image and the bootstrapping
image, in that each is used to build the other."
[1] http://openmcl.clozure.com/Doc/index.html#Development-cycle
Greetings!
This topic has arisen recently in gcl work. Has anyone developed a
small but *practical* list of opaque lisp primitives on which a full
system can usefully be built?
Take care,
Rainer Joswig <······@lisp.de> writes:
> In article <·······················@c77g2000hse.googlegroups.com>,
> C Y <···········@yahoo.com> wrote:
>
> > A year or so back, there was a rather interesting discussion on what
> > was termed "minimal" subsets of Lisp. I am curious if anything
> > further has happened with some of the efforts discussed in terms of
> > creating "minimal" lisps.
> >
> > I have a specific question of interest on the subject, and I'll do my
> > best to word it precisely:
> >
> > Given a hardware situation where NO compiler is available for any
> > language above the assembly level, and the goal is a running ANSI
> > Common Lisp, what would be the implementation path to take that would
> > result in the least amount of low level coding (or least difficult, if
> > the minimal AMOUNT of low level code would involve difficult coding)
> > that would produce a working ANSI Common Lisp? Assume a source code
> > version of ANSI Common Lisp that was written itself in ANSI Common
> > Lisp, in such a fashion that it could build more complex layers
> > without recursive calls to functionality in other complex layers (such
> > a beast would have to know what the core building blocks it would have
> > to work with would be, of course - so it would have to be written in
> > such a fashion that no single part of the definition required that its
> > own definition already be working, except for the parts to be
> > implemented in assembly language.)
> >
>
> OpenMCL needs C. From there it can bootstrap itself, AFAIK.
>
> --
> http://lispm.dyndns.org
--
Camm Maguire ····@enhanced.com
==========================================================================
"The earth is but one country, and mankind its citizens." -- Baha'u'llah
Camm Maguire <····@enhanced.com> writes:
> Greetings!
>
> This topic has arisen recently in gcl work. Has anyone developed a
> small but *practical* list of opaque lisp primitives on which a full
> system can usefully be built?
Something else than the primitives used in McCarthy's original lisp?
/andreas
--
A: Because it fouls the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
C Y <···········@yahoo.com> writes:
> [...]
> To those who will immediately respond that this is an uninteresting
> problem because we are not likely to face a situation where cross-
> compilation is more difficult than hand coding, I acknowledge that it
> is probably true cross-compilation will always be simpler. My
> interest is partically historical (in the early days there WERE no
> compilers, and someone had to do the job by hand - in retrospect, what
> would have been the quickest path to maximum functionality with
> minimal work, if ANSI CL were the target) and partially a desire to
> reduce the required knowledge set to the minimum (knowledge of the
> machine platform, and knowledge of Lisp - any cross compilation effort
> would almost certainly need both of these.
The first Von Neumann computers were programmed directly in octal.
Remember that in the Hollerith code used in punched cards, the
characters #\0 thru #\9 were encoded as the numbers 0 thru 9,
therefore you could easily enter binary data into the computer. There
was no need for any conversion.
But even some of the first assemblers were written in themselves (the
"bootstrapping" being done by the programmer "hand-compiling" it).
> If you are cross compiling
> from one Lisp to another this same knowledge set should be enough as
> well, but the supposition for the exercise is that NO working Lisp
> compilers are available - perhaps in a distant future unimaginable
> folly has resulted in all working binaries of Lisps being too old to
> run on any available hardware platform, if you need a scenario.)
As soon as assemblers or compilers were available, cross compiling was
used to develop the next generation of computer. The true boot
strapping really occured only once.
> In a sense, the first historical bootstrapping processes are what took
> computers from simple electrical devices to everything they are today
> - the bootstrap is what MAKES a computer into a computer from its
> component parts. To me that is a fascinating process, and the
> question "what would it take to go from inert metal to ANSI CL" is an
> interesting one. Is there any literature on such a topic?
>
> Cheers,
> CY
>
> P.S. I will confess a background motivation for this question is the
> Axiom project, which is founded on Lisp - the "30-year horizon"
> thinking of our project leader also lead me to the question "how can
> the knowledge being encoded into these computer languages survive
> indefinitely - what would it take to revive the living Axiom system
> even if we are somehow left with no running system which supports our
> current binary dependencies or understands our source code? Well, if
> we work inside Lisp for everything (a goal for at least some of us on
> the project) that reduces the question to "how does one get Lisp
> working starting from nothing?" (OK, OK there are issues with
> graphics systems like X and GDI and whatnot - but the core of the
> system is non-graphical.) It is not a likely scenario but interesting
> enough for me to pose the question. It also might have some bearing
> on formally proving correctness on various platforms, but I don't know
> enough about that yet to be sure.
Have a look at AIM-8,
http://www.informatimago.com/develop/lisp/small-cl-pgms/aim-8/
ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-008.pdf
and at the history of the JOHNNIAC:
http://www.rand.org/pubs/research_memoranda/2005/RM5654.pdf
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
On Jun 11, 9:36 pm, Pascal Bourguignon <····@informatimago.com> wrote:
> The first Von Neumann computers were programmed directly in octal.
>
> Remember that in the Hollerith code used in punched cards, the
> characters #\0 thru #\9 were encoded as the numbers 0 thru 9,
> therefore you could easily enter binary data into the computer. There
> was no need for any conversion.
>
> But even some of the first assemblers were written in themselves (the
> "bootstrapping" being done by the programmer "hand-compiling" it).
Ah. I vaguely remember something from the assembly class in college
about that - essentially the language served as a way to organize the
thoughts of the developers, and at the same time (once loaded
successfully) provided the tools to automatically carry out further
conversions of the same type.
> As soon as assemblers or compilers were available, cross compiling was
> used to develop the next generation of computer. The true boot
> strapping really occured only once.
Right. Perhaps the historical process does in fact closely approach
the optimal path from nothing to today's compilers, but I would be
curious none the less as to what the "minimal" bootstrapping cycle
would actually be. Not that it is likely to interest anyone else, of
course...
> Have a look at AIM-8,http://www.informatimago.com/develop/lisp/small-cl-pgms/aim-8/ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-008.pdf
>
> and at the history of the JOHNNIAC:http://www.rand.org/pubs/research_memoranda/2005/RM5654.pdf
Thanks! Will do.
CY
On Jun 12, 4:23 am, C Y <···········@yahoo.com> wrote:
> On Jun 11, 9:36 pm, Pascal Bourguignon <····@informatimago.com> wrote:
>
> > The first Von Neumann computers were programmed directly in octal.
>
> > Remember that in the Hollerith code used in punched cards, the
> > characters #\0 thru #\9 were encoded as the numbers 0 thru 9,
> > therefore you could easily enter binary data into the computer. There
> > was no need for any conversion.
>
> > But even some of the first assemblers were written in themselves (the
> > "bootstrapping" being done by the programmer "hand-compiling" it).
>
> Ah. I vaguely remember something from the assembly class in college
> about that - essentially the language served as a way to organize the
> thoughts of the developers, and at the same time (once loaded
> successfully) provided the tools to automatically carry out further
> conversions of the same type.
>
> > As soon as assemblers or compilers were available, cross compiling was
> > used to develop the next generation of computer. The true boot
> > strapping really occured only once.
>
> Right. Perhaps the historical process does in fact closely approach
> the optimal path from nothing to today's compilers, but I would be
> curious none the less as to what the "minimal" bootstrapping cycle
> would actually be. Not that it is likely to interest anyone else, of
> course...
>
> > Have a look at AIM-8,http://www.informatimago.com/develop/lisp/small-cl-pgms/aim-8/ftp://p...
>
> > and at the history of the JOHNNIAC:http://www.rand.org/pubs/research_memoranda/2005/RM5654.pdf
>
> Thanks! Will do.
>
> CY
I think the minimal bootstrapping you need is getting the computer
control unit to work and having a place where you can read a program
from. Is that the kind of information you are looking for ?
For one reason or another, I have developed this same interest in the
previous 10 months. My first goal was to design a CPU myself, using CL
as simulation language. The simulation I built was on the component
level, i.e. I have designed components, which can be interconnected
like an electronic circuit. Part of my goal is to look what I can/
could achieve with TTL (this is a nice link : http://mycpu.eu/).
However, during the study and design I also got more interested in how
early computers where built, and a little bit in the philosophy
regarding the things needed for a civilisation to achieve computers in
one way or another. I even bought a copy of A.D. Booth's 'Automatic
Digital Calculators'.
Regards,
Jurgen
On Jun 25, 4:54 am, jurgen_defurne <··············@pandora.be> wrote:
> I think the minimal bootstrapping you need is getting the computer
> control unit to work and having a place where you can read a program
> from. Is that the kind of information you are looking for ?
Sort of. Above Paul Wallich mentioned a "Canticle for Leibowitz"
style situation where all technology was lost except for printed
information in books, and Ari Johnson's phrase "bootstrapping from
desert sand" I like as well. Those are the scenarios I find
interesting - scenarios where that kind of knowledge is not just part
of hardware experimentation and development but NECESSARY for any use
of any preserved knowledge or abilities defined in computer code.
Today, cross compilation is always going to be simpler than the true
"hard" bootstrap. My curosity was directed towards the situation
where human beings without computers must create a computer. It
happened once, and I was curious as to what would be needed if it ever
had to happen again. Hence my interest in the CADR lisp machine and
the Forth on a chip designs - I don't know if they could be produced
without computers running the hardware to make them, but it's
certainly more likely than a non-computerized fab of any modern
processor/chip. Then you use that computer to run the machines that
can make the hardware you want ;-). It's a process that is documented
(hopefully) in the history of computer development - what I was
curious about was if knowing what we know now there is a theoretical
"best" way to go from nothing to a reasonable computer running Lisp.
(Then, if Axiom requires only Lisp, such a machine (if it had enough
memory and CPU oomph) could be used to type in a complete working
Axiom system and make the mathematical knowledge defined in Axiom
"live" again.)
It's an unlikely doomsday scenario, and not one I seriously think will
happen given how widespread computers are nowadays. Still, there's a
fascinating magic to the process - going from cold metal to a machine
that can do some problems in symbolic integration.
There is one other possible scenario that would need this knowledge,
actually - defeating with 100% certainty Ken Thompson's microcode
level backdoor security hole: http://www.acm.org/classics/sep95/ To
defeat such techniques without having any running binary that can be
trusted, a machine must be created and bootstrapped in isolation.
(Maybe - perhaps there are ways around it, but if so I don't know
them.)
> For one reason or another, I have developed this same interest in the
> previous 10 months. My first goal was to design a CPU myself, using CL
> as simulation language. The simulation I built was on the component
> level, i.e. I have designed components, which can be interconnected
> like an electronic circuit. Part of my goal is to look what I can/
> could achieve with TTL (this is a nice link :http://mycpu.eu/).
Nifty! That's a neat project.
> However, during the study and design I also got more interested in how
> early computers where built, and a little bit in the philosophy
> regarding the things needed for a civilisation to achieve computers in
> one way or another. I even bought a copy of A.D. Booth's 'Automatic
> Digital Calculators'.
Nice to know I'm not the only one out there with such an
interest :-). Perhaps it's the sort of thing some non-profit
somewhere could take on - collection, organization, and preservation
of the knowledge necessary for a civilization to develop computers.
Cheers,
CY
C Y <···········@yahoo.com> writes:
> There is one other possible scenario that would need this knowledge,
> actually - defeating with 100% certainty Ken Thompson's microcode
> level backdoor security hole: http://www.acm.org/classics/sep95/ To
> defeat such techniques without having any running binary that can be
> trusted, a machine must be created and bootstrapped in isolation.
> (Maybe - perhaps there are ways around it, but if so I don't know
> them.)
If you trust your transistor provider, it should not be too hard to
build a computer from them. But the historical boot process is
probably not far from the optimum: it will be easier to build a binary
processor for which you'll write the first program by hard wiring it
into some "ROM", like they did with the patch panels, this first
program being a monitor that will allow you to load and store further
programs in your RAM, and one of the second programs you'll load will
be an assembler. At this stage, there will probably be no point in
using a sexp syntax, and you'll write a simple assembler with the
normal assembler syntax. And the third program may be a lisp
implementation, like LISP 1.5.
Perhaps you'd want to design your transistor processor as a lisp
machine, but it'll probably require more transistors (eg you'd have
more type checking to implement), so I'd bet you'll stay closer to the
historical bootstrap (remember, each transistor is 3 opportunities to
burn your fingers).
Now if you don't trust your transistor provider (they could install
some processor with bluetooth capability in all their transistors to
spy on their working and once this massively parallel computer out of
your control detects that you are compiling a login program, they'll
backdoor it), then you'll have to make your own silicium. It's a lot
of work, but it starts pleasantly: go to the beach...
But you can't be 100% sure, God may have installed a backdoor in the
sand you'll use.
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
On Jun 25, 7:11 pm, Pascal Bourguignon <····@informatimago.com> wrote:
> If you trust your transistor provider, it should not be too hard to
> build a computer from them. But the historical boot process is
> probably not far from the optimum: it will be easier to build a binary
> processor for which you'll write the first program by hard wiring it
> into some "ROM", like they did with the patch panels, this first
> program being a monitor that will allow you to load and store further
> programs in your RAM, and one of the second programs you'll load will
> be an assembler. At this stage, there will probably be no point in
> using a sexp syntax, and you'll write a simple assembler with the
> normal assembler syntax. And the third program may be a lisp
> implementation, like LISP 1.5.
First panels are needed, then assembler, then *something-better*.
Makes sense. I suppose it might be of interest to rig up a punch card
reader to send the needed electrical impulses, but that might be just
extra overhead.
> Perhaps you'd want to design your transistor processor as a lisp
> machine, but it'll probably require more transistors (eg you'd have
> more type checking to implement), so I'd bet you'll stay closer to the
> historical bootstrap (remember, each transistor is 3 opportunities to
> burn your fingers).
Right.
> Now if you don't trust your transistor provider (they could install
> some processor with bluetooth capability in all their transistors to
> spy on their working and once this massively parallel computer out of
> your control detects that you are compiling a login program, they'll
> backdoor it), then you'll have to make your own silicium. It's a lot
> of work, but it starts pleasantly: go to the beach...
Heh. I'm not that paranoid, I just mentioned that scenario as a
possible situation where such knowledge would be needed. The
technological steps in going from "guy with club" to "modern research
lab" is another interest of mine, although I suspect the description
would be considerably longer than the computer bootstrap story. All
of the myrid requirements of technology really make one appreciate the
magnitude of what has been accomplished. Purified metals, PCB design,
polymers, LEDs, power supples, precision machining, etc. etc. etc.
Fascinating.
> But you can't be 100% sure, God may have installed a backdoor in the
> sand you'll use.
Sorry if the discussion is an annoying one. I find the subject
interesting personally, in part because it is a difficult task to
attempt without knowledge of how to approach it. Someone clearly did
it once, and the knowledge of how it is done I think is worth
preserving.
Cheers,
CY
C Y <···········@yahoo.com> writes:
>> But you can't be 100% sure, God may have installed a backdoor in the
>> sand you'll use.
>
> Sorry if the discussion is an annoying one. I find the subject
> interesting personally, in part because it is a difficult task to
> attempt without knowledge of how to approach it. Someone clearly did
> it once, and the knowledge of how it is done I think is worth
> preserving.
On the contrary, it's very interesting. For example, if you want to
bootstrap an industry on Mars.
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
On Jun 27, 3:43 pm, Pascal Bourguignon <····@informatimago.com> wrote:
> C Y <···········@yahoo.com> writes:
> >> But you can't be 100% sure, God may have installed a backdoor in the
> >> sand you'll use.
>
> > Sorry if the discussion is an annoying one. I find the subject
> > interesting personally, in part because it is a difficult task to
> > attempt without knowledge of how to approach it. Someone clearly did
> > it once, and the knowledge of how it is done I think is worth
> > preserving.
>
> On the contrary, it's very interesting. For example, if you want to
> bootstrap an industry on Mars.
Indeed! In fact, that's actually an even more different problem
because there is no convenient combustible stockpile of dead animal
matter and we can't wait around a few tens of thousands of years for
human ingenuity to work - the tech base must function continuously
from the get go. It is necessary to "seed" enough technology to
enable a self-reproducing and self-supporting technological base, with
only the inorganic raw materials of the Martian surface as input.
Also, we have no knowledge of any concentrations of the key elemental
materials we would need, so mining would have to wait for extensive
mineral surveys.
Anyway, straying off topic. I imagine NASA has smart people thinking
about it - someday I'll have to hunt up their reports.
CY
;; This buffer is for notes you don't want to save, and for Lisp
evaluation.
;; If you want to create a file, visit that file with C-x C-f,
;; then enter the text in that file's own buffer.
On Jun 28, 1:36 pm, C Y <···········@yahoo.com> wrote:
> > On the contrary, it's very interesting. For example, if you want to
> > bootstrap an industry on Mars.
[[...]]
> Indeed! In fact, that's actually an even more different problem
> because there is no convenient combustible stockpile of dead animal
> matter and we can't wait around a few tens of thousands of years for
> human ingenuity to work - the tech base must function continuously
> from the get go. It is necessary to "seed" enough technology to
> enable a self-reproducing and self-supporting technological base, with
> only the inorganic raw materials of the Martian surface as input.
> Also, we have no knowledge of any concentrations of the key elemental
> materials we would need, so mining would have to wait for extensive
> mineral surveys.
Years ago, I read a book that really inspired me with hope and a
bright outlook towards Martian exploration - the lesson was to use
local materials as much as is possible!
http://www.amazon.com/Case-Mars-Robert-Zubrin/dp/0684835509
as usual, nothing much has happened since the book was
written... (depending on your degree of pessimism).
Back on topic, I thought about these articles when I first saw this
post: I am a bit late in posting, but no one's mentioned them.
An Incremental Approach to Compiler Construction
http://lambda-the-ultimate.org/node/1752
http://scheme2006.cs.uchicago.edu/11-ghuloum.pdf
NB: Scheme specific, but close enough. Scheme, Common Lisp, any Lisp,
same difference.
C Y wrote:
> Today, cross compilation is always going to be simpler than the true
> "hard" bootstrap. My curosity was directed towards the situation
> where human beings without computers must create a computer. It
> happened once, and I was curious as to what would be needed if it ever
> had to happen again.
I think Forth would make this process more simpler than other languages,
because the syntax of Forth is even simpler than Lisp and you can translate
it very straightforward, and by hand, to assembler code. I just finished my
first Forth CPU, implemented as a VHDL program (yes, it works in hardware
on my 2 FPGA boards, the LED is blinking!), with an emulator written in
Forth:
http://www.frank-buss.de/forth/cpu1/
It has a very simple architecture and if you have too much time, it should
be possible to build it with 74xx parts (and some memory) in some weeks.
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
Frank Buss <··@frank-buss.de> writes:
> C Y wrote:
>
>> Today, cross compilation is always going to be simpler than the true
>> "hard" bootstrap. My curosity was directed towards the situation
>> where human beings without computers must create a computer. It
>> happened once, and I was curious as to what would be needed if it ever
>> had to happen again.
>
> I think Forth would make this process more simpler than other languages,
> because the syntax of Forth is even simpler than Lisp and you can translate
> it very straightforward, and by hand, to assembler code. I just finished my
> first Forth CPU, implemented as a VHDL program (yes, it works in hardware
> on my 2 FPGA boards, the LED is blinking!), with an emulator written in
> Forth:
>
> http://www.frank-buss.de/forth/cpu1/
>
> It has a very simple architecture and if you have too much time, it should
> be possible to build it with 74xx parts (and some memory) in some weeks.
But you can implement a Lisp reader very simply too.
You don't need to implement all the complexities of a CL reader, you
can parse only symbols and numbers (the rest, including strings and
lists, being done with a few simple reader macros).
--
__Pascal Bourguignon__ http://www.informatimago.com/
NOTE: The most fundamental particles in this product are held
together by a "gluing" force about which little is currently known
and whose adhesive power can therefore not be permanently
guaranteed.
Pascal Bourguignon wrote:
> But you can implement a Lisp reader very simply too.
>
> You don't need to implement all the complexities of a CL reader, you
> can parse only symbols and numbers (the rest, including strings and
> lists, being done with a few simple reader macros).
Parsing lists is a basic requirement for a Lisp system and not as easy as
parsing Forth, but it could be simple to build a Lisp-cross compiler in
Lisp and if you don't fear the backdoor problem, you are right and it is
not too difficult to bootstrap a Lisp system. But with Forth it is even
easy to bootstrap it without a cross-compiler, see e.g. this example:
http://www.ioccc.org/1992/buzzard.2.design
With Lisp and without a cross-compiler you have to translate the initial
parser by hand to machine code, which is more difficult than translating a
Forth interpreter by hand, especially if the assembler has Forth-like
opcodes. A solution could be to develop an assembler which has Lisp-like
opcodes :-)
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
C Y wrote:
> There is one other possible scenario that would need this knowledge,
> actually - defeating with 100% certainty Ken Thompson's microcode
> level backdoor security hole: http://www.acm.org/classics/sep95/ To
> defeat such techniques without having any running binary that can be
> trusted, a machine must be created and bootstrapped in isolation.
> (Maybe - perhaps there are ways around it, but if so I don't know
> them.)
When compiling a C compiler, this backdoor is easy to implement, so you
can't be sure that the new C compiler doesn't includes it. But when
developing a new CPU with VHDL and cross-compiling a self invented
assembler language, I can't think of a way to introduce the backdoor,
because the backdoor author has to know the target architecture or the host
language to infect it with the backdoor code.
But to be 100% sure, you could print out an assembly listing of your
bootstrap code and verify the memory on the target hardware with a hardware
counter and LED output :-)
--
Frank Buss, ··@frank-buss.de
http://www.frank-buss.de, http://www.it4-systems.de
C Y wrote:
> Given a hardware situation where NO compiler is available for any
> language above the assembly level, and the goal is a running ANSI
> Common Lisp, what would be the implementation path to take that would
> result in the least amount of low level coding (or least difficult, if
> the minimal AMOUNT of low level code would involve difficult coding)
> that would produce a working ANSI Common Lisp? Assume a source code
> version of ANSI Common Lisp that was written itself in ANSI Common
> Lisp, in such a fashion that it could build more complex layers
> without recursive calls to functionality in other complex layers (such
> a beast would have to know what the core building blocks it would have
> to work with would be, of course - so it would have to be written in
> such a fashion that no single part of the definition required that its
> own definition already be working, except for the parts to be
> implemented in assembly language.)
As others have mentioned, a nice strategy is to implement a small
bytecode interpreter in assembler, and then target the bytecode
interpreter.
If you are interested in implementation strategies for Lisp-languages
then you definitely want to read LiSP aka "Lisp in Small Pieces".
<http://www-spi.lip6.fr/~queinnec/WWW/LiSP.html>
--
Jens Axel S�gaard