on bootstrapping: introducing Mes

on bootstrapping: introducing Mes

[Jan Nieuwenhuizen]

Hi,

I have a minimal LISP-1.5-resembling interpreter in C that now can
also interpret itself

    https://gitlab.com/janneke/mes

It was inspired by the seemingly often ignored bootstrapping question
made so painfully visible by GuixSD and by OriansJ with their self
hosting hex assembler project.

As a next step after a hex assembler I was thinking of getting Scheme up
and running and use that to create a tiny C compiler, probably using
PEG.  For that I think we need define-syntax, which I had a peek at and
still scares the all-sorts-of-things out of me :-)

I searched for minimal Lisp/Scheme to get that going and found an
article called the Maxwell Equations of Software 1) with a pointer to
the 1962 LISP 1.5 paper by John McCarthy 2).

First I `implemented' Mes/LISP-1.5: the bottom half of page 13 and the
necessary helper procedures defined on pages 8-12 using Guile, removing
all but the primitives needed to run LISP-1.5/Mes (I think): car, cdr,
cond, cons, define, eq?, '()/nil, null?, pair? and quote.  I cheated
with read, and with display and newline for debugging.

Then I translated the program into C and got rid of read by using
getchar/ungetchar.

It's been great fun and now I'm kind of stuck a bit at the point of
implementing macros.  I have a simplistic version in C but want to
remove that again --I like the idea of having the absolute minimal LISP
interpreter in C-- and only introduce macros after having bootstrapped
into the LISP/Mes domain.

Greetings,
Jan

1) http://www.michaelnielsen.org/ddi/lisp-as-the-maxwells-equations-of-software/
2) http://www.softwarepreservation.org/projects/LISP/book/LISP%201.5%20Programmers%20Manual.pdf
3)

-- 
Jan Nieuwenhuizen <janneke@gnu.org> | GNU LilyPond http://lilypond.org
Freelance IT http://JoyofSource.com | Avatar®  http://AvatarAcademy.nl  

Re: on bootstrapping: introducing Mes

[Mike Bushroe]

I have been quietly lurking for quite some time now, but this stirs up old
memories. Back in college we built a compile for a local language called
'y' which was very similar to C, and the compiler was written in 'yacc',
yet another compiler compiler.

It sounds like you are moving to a two layer approach, a base layer in C
that would have to be compiler for any new host that would interpret a
minimal subset of LISP, and then a full LISP interpreter that would support
most or all of the language. If this is really the case, you should
consider what you want/need in the lower level, and what you want to push
up into the stripped LISP layer. Remember that no matter how small the
lower level C core is, it will still need to be cross compiled to run on
any other platform. Since gcc it easily available and good at cross
compiling that is not a major problem. But it does mean that keeping in
very small and limited may not buy you very much. So implementing macros in
the LISP layer should be compared with implementing them in C, if that
proves easier.

  Another suggestion if you want to have this easily portable would be to
add a third component, the OS/hardware interface. If you have one small C
file to cross compile, an unchanging covering layer of LISP to handle most
of the more complex parts of the interpreter, and an interface descriptor
file then you have the advantage that the core C code and the LISP upper
layer code never change (accept for cross-compiling the C for a new
machine) then the only file that needs changing is the OS/hardware file.
And if you create the format for that to be human readable text that
matched a text description of the task to be performed and then the text,
code, shell instructions needed to perform that code it would be fairly
easy for anyone else to modify the package to work in any custom
application that they had.

  As for the scary part of define-syntax, once you have a tokenizer written
from the getc, ungetc routines, it is fairly straight forward to use the
tokens returned (variable names, numbers, language commands, math/logic
operators, and block/structure symbols) and build a state machine that
walks through each syntax sequence starting with a new code line and
sending out assemble code lines to compile or executing steps in an
interpreter. Using recursion for numeric expressions and nested block
structures. Yes, scary at first but it is surprising how quickly language
breaks down into recursive syntax structures.

 Regardless of how you proceed from here, good luck and it sounds like you
are having fun!

Mike

On Sun, Jun 19, 2016 at 4:08 AM, Jan Nieuwenhuizen <janneke@gnu.org> wrote:

> Hi,
>
> I have a minimal LISP-1.5-resembling interpreter in C that now can
> also interpret itself
>
>     https://gitlab.com/janneke/mes
>
> It was inspired by the seemingly often ignored bootstrapping question
> made so painfully visible by GuixSD and by OriansJ with their self
> hosting hex assembler project.
>
> As a next step after a hex assembler I was thinking of getting Scheme up
> and running and use that to create a tiny C compiler, probably using
> PEG.  For that I think we need define-syntax, which I had a peek at and
> still scares the all-sorts-of-things out of me :-)
>
> I searched for minimal Lisp/Scheme to get that going and found an
> article called the Maxwell Equations of Software 1) with a pointer to
> the 1962 LISP 1.5 paper by John McCarthy 2).
>
> First I `implemented' Mes/LISP-1.5: the bottom half of page 13 and the
> necessary helper procedures defined on pages 8-12 using Guile, removing
> all but the primitives needed to run LISP-1.5/Mes (I think): car, cdr,
> cond, cons, define, eq?, '()/nil, null?, pair? and quote.  I cheated
> with read, and with display and newline for debugging.
>
> Then I translated the program into C and got rid of read by using
> getchar/ungetchar.
>
> It's been great fun and now I'm kind of stuck a bit at the point of
> implementing macros.  I have a simplistic version in C but want to
> remove that again --I like the idea of having the absolute minimal LISP
> interpreter in C-- and only introduce macros after having bootstrapped
> into the LISP/Mes domain.
>
> Greetings,
> Jan
>
> 1)
> http://www.michaelnielsen.org/ddi/lisp-as-the-maxwells-equations-of-software/
> 2)
> http://www.softwarepreservation.org/projects/LISP/book/LISP%201.5%20Programmers%20Manual.pdf
> 3)
>
> --
> Jan Nieuwenhuizen <janneke@gnu.org> | GNU LilyPond http://lilypond.org
> Freelance IT http://JoyofSource.com | Avatar®  http://AvatarAcademy.nl
>
>


-- 
"Creativity is intelligence having fun." — Albert Einstein

Re: on bootstrapping: introducing Mes

[Ludovic Courtès]

Hi!

Jan Nieuwenhuizen <janneke@gnu.org> skribis:

> I have a minimal LISP-1.5-resembling interpreter in C that now can
> also interpret itself
>
>     https://gitlab.com/janneke/mes
>
> It was inspired by the seemingly often ignored bootstrapping question
> made so painfully visible by GuixSD and by OriansJ with their self
> hosting hex assembler project.

Sounds fun!

> As a next step after a hex assembler I was thinking of getting Scheme up
> and running and use that to create a tiny C compiler, probably using
> PEG.  For that I think we need define-syntax, which I had a peek at and
> still scares the all-sorts-of-things out of me :-)
>
> I searched for minimal Lisp/Scheme to get that going and found an
> article called the Maxwell Equations of Software 1) with a pointer to
> the 1962 LISP 1.5 paper by John McCarthy 2).
>
> First I `implemented' Mes/LISP-1.5: the bottom half of page 13 and the
> necessary helper procedures defined on pages 8-12 using Guile, removing
> all but the primitives needed to run LISP-1.5/Mes (I think): car, cdr,
> cond, cons, define, eq?, '()/nil, null?, pair? and quote.  I cheated
> with read, and with display and newline for debugging.
>
> Then I translated the program into C and got rid of read by using
> getchar/ungetchar.
>
> It's been great fun and now I'm kind of stuck a bit at the point of
> implementing macros.  I have a simplistic version in C but want to
> remove that again --I like the idea of having the absolute minimal LISP
> interpreter in C-- and only introduce macros after having bootstrapped
> into the LISP/Mes domain.

From a bootstrapping viewpoint, since Mes is in C, we’re back to the
same problem we have with Guile.  :-) Guile has an interpreter written
in C, for bootstrapping purposes, and it’s capable of running any kind
of Scheme code, I think, including the full macro expander.

To make the bootstrap Guile smaller, maybe we could remove .go files
from it and build them as the initial step.  That would be comparable to
the strategy you suggest, I think.

Cheers,
Ludo’.

Re: on bootstrapping: introducing Mes

[Jan Nieuwenhuizen]

Ludovic Courtès writes:

>> It was inspired by the seemingly often ignored bootstrapping question
>> made so painfully visible by GuixSD and by OriansJ with their self
>> hosting hex assembler project.
>
> Sounds fun!

:-)

>> As a next step after a hex assembler I was thinking of getting Scheme up
>> and running and use that to create a tiny C compiler, probably using
>> PEG.  For that I think we need define-syntax, which I had a peek at and
>> still scares the all-sorts-of-things out of me :-)

> From a bootstrapping viewpoint, since Mes is in C, we’re back to the
> same problem we have with Guile.  :-) Guile has an interpreter written
> in C, for bootstrapping purposes, and it’s capable of running any kind
> of Scheme code, I think, including the full macro expander.

Ah.  I possilby did not make myself clear --that or I don't understand
the problem.  The C interpreter is now 900 lines and I hope to simplify
it into about half.  I intend to make it so tiny that it can be easily
implemented in annotated hex, so that we only need OriansJ's hex
assembler.

So the idea is to go from one small verifyable binary straight into
LISP and build a tiny C compiler on top of that.

> To make the bootstrap Guile smaller, maybe we could remove .go files
> from it and build them as the initial step.  That would be comparable to
> the strategy you suggest, I think.

It's not so much about smaller per se, but about making the initial
binary we have to trust so small that it can be inspected byte-for-byte.
Not sure yet if that's feasible or helpful, but as you guessed it's fun :-)

Greetings,
Jan

-- 
Jan Nieuwenhuizen <janneke@gnu.org> | GNU LilyPond http://lilypond.org
Freelance IT http://JoyofSource.com | Avatar®  http://AvatarAcademy.nl  

Re: on bootstrapping: introducing Mes

[Jan Nieuwenhuizen]

Mike Bushroe writes:

Hi!

> I have been quietly lurking for quite some time now, but this stirs up
> old memories. Back in college we built a compile for a local language
> called 'y' which was very similar to C, and the compiler was written
> in 'yacc', yet another compiler compiler. 

That's great.  Starting this project it seems like old times revisited
in a way...bootstrapping was once real important and gains renewed
interest.

> It sounds like you are moving to a two layer approach, a base layer in
> C that would have to be compiler for any new host that would interpret
> a minimal subset of LISP, and then a full LISP interpreter that would
> support most or all of the language.

Ah sorry, not exactly.  I intend to write the initial LISP interpreter
in binary/hex...the current implementation in C is only intended to be
an intermediate stage in the development process, i.e., to figure out
what exactly is needed as a minimal interpreter.  Experimenting using C
is easier than in assembly and close enough to make change to assembly
later.

> As for the scary part of define-syntax, once you have a tokenizer
> written from the getc, ungetc routines, it is fairly straight forward
> to use the tokens returned (variable names, numbers, language
> commands, math/logic operators, and block/structure symbols) and build
> a state machine that walks through each syntax sequence starting with
> a new code line and sending out assemble code lines to compile or
> executing steps in an interpreter. Using recursion for numeric
> expressions and nested block structures. Yes, scary at first but it is
> surprising how quickly language breaks down into recursive syntax
> structures.

Thank you, that's a most helpful encouragement!

> Regardless of how you proceed from here, good luck and it sounds like
> you are having fun!

Sure thing, and I've already learned quite a bit I thought I already
knew about intepreting lisp. :-)

Greetings,
Jan

-- 
Jan Nieuwenhuizen <janneke@gnu.org> | GNU LilyPond http://lilypond.org
Freelance IT http://JoyofSource.com | Avatar®  http://AvatarAcademy.nl  

Re: on bootstrapping: introducing Mes

[Mike Bushroe]

On Tue, Jun 21, 2016 at 10:07 AM, Jan Nieuwenhuizen <janneke@gnu.org> wrote:

> Mike Bushroe writes:
>
> Hi!
>
> Ah sorry, not exactly.  I intend to write the initial LISP interpreter
> in binary/hex...the current implementation in C is only intended to be
> an intermediate stage in the development process, i.e., to figure out
> what exactly is needed as a minimal interpreter.  Experimenting using C
> is easier than in assembly and close enough to make change to assembly
> later.
>


> Greetings,
> Jan
>
> --
> Jan Nieuwenhuizen <janneke@gnu.org> | GNU LilyPond http://lilypond.org
> Freelance IT http://JoyofSource.com | Avatar®  http://AvatarAcademy.nl
>

Jan,
  I think I better understand what you are working on now. The vest-pocket
assembly code bootstrap is a great idea for getting Scheme working where
Scheme has never been before. But it may limit the bootstrapping to only
X86 based machines. While the majority of users will be installing onto
that, you might consider something that supposedly is more universal.
Something like Java that is supposed to be available for almost everything
from small embedded systems to the latest and greatest CPUs and OSs. It
would also be a smaller change than C to assembler although is truly very
close to assembler on a good CPU. On the other hand Java is 'yet another
language' and one I have not worked with yet myself. I have done some
assembly programming, even on X86 based machines.

  I enjoyed the compiler course at the university and it sounds like you
are having fun here. And since I never really got a feel for LISP let alone
Lambda functions I doubt I will have any further suggestions that would be
helpful. You are already getting to beyond what I have experience with.

Mike

-- 
"Creativity is intelligence having fun." — Albert Einstein

Re: on bootstrapping: introducing Mes

[Ludovic Courtès]

Jan Nieuwenhuizen <janneke@gnu.org> skribis:

> Ludovic Courtès writes:

[...]

>> From a bootstrapping viewpoint, since Mes is in C, we’re back to the
>> same problem we have with Guile.  :-) Guile has an interpreter written
>> in C, for bootstrapping purposes, and it’s capable of running any kind
>> of Scheme code, I think, including the full macro expander.
>
> Ah.  I possilby did not make myself clear --that or I don't understand
> the problem.  The C interpreter is now 900 lines and I hope to simplify
> it into about half.  I intend to make it so tiny that it can be easily
> implemented in annotated hex, so that we only need OriansJ's hex
> assembler.
>
> So the idea is to go from one small verifyable binary straight into
> LISP and build a tiny C compiler on top of that.

I see, that makes sense.  libguile/{eval,memoize}.c alone is 1,900+
lines, and it relies on other parts of libguile, as well as libgc.  So
in that sense, Mes is quite an achievement, and probably better suited
to make a small binary!

>> To make the bootstrap Guile smaller, maybe we could remove .go files
>> from it and build them as the initial step.  That would be comparable to
>> the strategy you suggest, I think.
>
> It's not so much about smaller per se, but about making the initial
> binary we have to trust so small that it can be inspected byte-for-byte.
> Not sure yet if that's feasible or helpful, but as you guessed it's fun :-)

I understand now.

Thanks for explaining!

Ludo’.

Re: on bootstrapping: introducing Mes

[Amirouche Boubekki]

On 2016-06-19 13:08, Jan Nieuwenhuizen wrote:
> Hi,
> 
> I have a minimal LISP-1.5-resembling interpreter in C that now can
> also interpret itself
> 
>     https://gitlab.com/janneke/mes
> 
> It was inspired by the seemingly often ignored bootstrapping question
> made so painfully visible by GuixSD and by OriansJ with their self
> hosting hex assembler project.

This sound fun (and scary!). What do you think about GNU epsilon? 
doesn't
your goals intersect somewhat?