RE: You missed my later work

RE: You missed my later work

[Jeremiah]

I had recently watched your FOSDEM talk https://fosdem.org/2017/schedule/event/guixsdbootstrap/ [fosdem.org]
Which you seem to have confused my hex assembler as an end in itself, rather than the first step in Stage0

Basically, I decided to steal a good idea from the C and pascal languages (o-code and p-code specificly)
Define a trivial to implement virtual machine (vm.c vm.h vm_decode.c and vm_instructions.c [optionally tty.c and/or dynamic_execution_trace.c but neither is required])
Who's entire instruction set is define in ISA_HEX_Map.org

That way all platforms can independently verify every step

Looking at your work, I can't help but wonder if we might be making that bootstrap step harder than it has to be.
What if we converted my lisp interpreter into a lisp compiler? Could that simplify your initial bootstrap?
Since instead of trying to do the full C compiler in scheme in a single step, we could do:
Primitive_scheme -> minimal_scheme -> full_scheme -> done

What do you think?

Jeremiah Orians
State of Michigan
Cell phone: (517) 896-2948

> -----Original Message-----
> From: Jan Nieuwenhuizen [mailto:janneke@gnu.org]
> Sent: Tuesday, March 28, 2017 5:09 PM
> To: Orians, Jeremiah (DTMB) <OriansJ@michigan.gov>
> Subject: Re: You missed my later work
> 
> Orians, Jeremiah (DTMB) writes:
> 
> Hi!
> 
> Thanks for reaching out.
> 
>> https://github.com/oriansj/stage0 [github.com]
> 
>> It includes everything one needs, starting from a hex monitor to a primitive lisp for
>> a very portable VM specification (Which is also included and implemented)
> 
> You implemented a LISP? I'll have to look into it! I looked at your
> amazing self hosting hex assembler and that's what got me going on
> implementing Mes.
> 
> What do you mean by `You missed my later work?,' are you referring to
> some event? I have been very busy working on Mes: a scheme intepreter
> written in C, that can execute a Scheme program which is a C compiler
> that can compile itself. I'm almost done: Guile can run the C compiler
> in Scheme, Mes still fails.
> 
> Have you been following Mes? I'm wondering if we can/should work
> together somehow. It seems we very much are working towards a similar
> goal.
> 
> Greetings, janneke.
> 
> --
> Jan Nieuwenhuizen <janneke@gnu.org> | GNU LilyPond http://lilypond.org [lilypond.org]
> Freelance IT http://JoyofSource.com [JoyofSource.com] | Avatar® http://AvatarAcademy.nl [AvatarAcademy.nl] 
 

Re: You missed my later work

[Jan Nieuwenhuizen]

Hi Jeremiah!

> I had recently watched your FOSDEM talk https://fosdem.org/2017/schedule/event/guixsdbootstrap/ 
> Which you seem to have confused my hex assembler as an end in itself,
> rather than the first step in Stage0

Ah, that's why you say `You missed.'  Sorry for giving that suggestion.

What I really meant to say I think, is that your self hosting stage0 hex
assembler was one of the things that inspired me to start Mes.  I knew
you planned stage0 as a first step but I could not imagine how the next
steps would work out, at the time.

> Basically, I decided to steal a good idea from the C and pascal
> languages (o-code and p-code specificly)

Aah, okay.  That' smart.  I got questions why I did not start with forth
or brainfuck.

> Define a trivial to implement virtual machine (vm.c vm.h vm_decode.c
> and vm_instructions.c [optionally tty.c and/or
> dynamic_execution_trace.c but neither is required])
> Who's entire instruction set is define in ISA_HEX_Map.org

Found it... https://github.com/oriansj/stage0/blob/master/ISA_HEX_Map.org

> That way all platforms can independently verify every step
>
> Looking at your work, I can't help but wonder if we might be making
> that bootstrap step harder than it has to be.

Yes...

> What if we converted my lisp interpreter into a lisp compiler? Could
> that simplify your initial bootstrap?

Quite possibly...

> Since instead of trying to do the full C compiler in scheme in a
> single step, we could do: Primitive_scheme -> minimal_scheme ->
> full_scheme -> done
>
> What do you think?

What you describe here makes lots of sense.  It very much resembles
something that I was aiming to do initially.  I wanted to bootstrap my
Scheme from Lisp-1.5 and prototype my Lisp-1.5 interpreter in C, only to
replace that prototype in C later by something in assembly --> and hook
up your stage0 or more.

...however, for the bootstrap problem we need [almost] a full C
compiler, enough to compile Tiny C (tcc).  I found Matt Wette's Nyacc,
which is a full C parser in Guile.

Then I got thinking: It could make sense to start a full C compiler
project in Guile?  That could be useful also outside of the bootstrap
process.  And if we have a full C compiler in Scheme, then maybe having
a Scheme interpreter (or VM?) in C is good enough.

So that's what I have been working towards, I should be quite close to
releasing Mes 0.5 which should be self-hosting: A Scheme interpreter
that can run a C compiler written in Scheme that can compile itself.

On the one hand that would be a very simple bootstrap setup.  On the
other hand this still leaves us with a fairly big bootstrap binary.
Possibly using your work as a front end to this removes that issue?

What do you think?

Greetings, janneke

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

Re: You missed my later work

[Jeremiah]

> Aah, okay.  That' smart.  I got questions why I did not start with forth
> or brainfuck.

Well now you could have told them we already had the forth
https://github.com/oriansj/stage0/blob/master/stage2/forth.s
but none of the people in the forth community bothered to build upon it

> ...however, for the bootstrap problem we need [almost] a full C
> compiler, enough to compile ....

Nope, we just needed to get more creative.
I could hand assemble a C compiler like
https://web.archive.org/web/20160604041431/http://homepage.ntlworld.com/edmund.grimley-evans/cc500/cc500.c
or
https://github.com/rswier/c4/blob/master/c4.c

in assembly with a couple months of effort but the key is not to keep
trying to take huge steps but rather simple ones.

For example break up the C compiler problem into pieces, for example
have a seperate C preprocessor, a single file C compiler that only
produces assembly and just leverage the already existing assembly
infrastructure I already made.

> On the one hand that would be a very simple bootstrap setup.  On the
> other hand this still leaves us with a fairly big bootstrap binary.
> Possibly using your work as a front end to this removes that issue?

I honestly feel that is absolutely something that has to be done.
However, you'll have to constrain yourself to what language features in
C that you use to make the path from what I have completed to what is
required possible.

Some questions I have are as follows:
1) Could the C preprocessor componet of Nyacc be isolated and simplified
enough to run on stage0's lisp interpreter and solve the C preprocessor
question?

2) is cc500 or C in 4 functions good enough to bootstrap mescc or do we
need to extend on of them or find/make a different C compiler that could
be compiled by one of them which could get the job done?

3) has anyone looked at stripping tcc down to only using integers,
structs, bytes and strings and outputting assembly instead of a binary?

4) or have we become too focused on getting C working that we missed
implementing another language (perhaps PL/0 or algol w) might end up
saving us a bunch of work?

5) Are there any languages for which it would be easier to implement C
than assembly or simpler than trying to parse C in S-expressions?

6) Are there any primitives I could implement into my Lisp that would
make C parsing trivial?

7) What else could I be missing about this problem?

-Jeremiah

Re: You missed my later work

[Jan Nieuwenhuizen]

[cc: Matt, author of Nyacc]

> Well now you could have told them we already had the forth
> https://github.com/oriansj/stage0/blob/master/stage2/forth.s
> but none of the people in the forth community bothered to build upon it

You created a fully bootstrappable LISP and FORTH, wow!

That would make my answer easier; I started with Scheme/Lisp because
you have to start somewhere, and I like that better.

> For example break up the C compiler problem into pieces, for example
> have a seperate C preprocessor, a single file C compiler that only
> produces assembly and just leverage the already existing assembly
> infrastructure I already made.

That could open up new possibilities.  However, there are so many
choices, is this going to help us get forward right now?

> I honestly feel that is absolutely something that has to be done.
> However, you'll have to constrain yourself to what language features in
> C that you use to make the path from what I have completed to what is
> required possible.
>
> Some questions I have are as follows:
> 1) Could the C preprocessor componet of Nyacc be isolated and simplified
> enough to run on stage0's lisp interpreter and solve the C preprocessor
> question?

@Matt: would separating the cpp part from Nyacc be feasible?  Do you
also think that's helpful?

> 2) is cc500 or C in 4 functions good enough to bootstrap mescc or do we
> need to extend on of them or find/make a different C compiler that could
> be compiled by one of them which could get the job done?

Thanks for the pointers!  I just released Mes 0.5, which is now fully
self hosting.  We would need to investigate.  However, if we restrict
the boostrapping path to either Mes or stage0+Mes, how could this help?

> 3) has anyone looked at stripping tcc down to only using integers,
> structs, bytes and strings and outputting assembly instead of a binary?

Compiling tcc is near the top of my priority list -- just below
releasing Mes 0.5 (done) and discussing the next step (doing that now).
So if nothing changes, I'll be working to compile tcc, any help or
insights to make that easier are much appreciated.

> 4) or have we become too focused on getting C working that we missed
> implementing another language (perhaps PL/0 or algol w) might end up
> saving us a bunch of work?

Posibly.  Christopher Webber mentioned PreScheme to me so I guess he's
a fan.  Mes is currently prototyped in C, if we could move that to
[Pre]Scheme that would be great!

However, my first priority is to close the bootstrap loop, i.e. get
either GCC or Guile compiled from what's Mes now. 

> 5) Are there any languages for which it would be easier to implement C
> than assembly or simpler than trying to parse C in S-expressions?

Mes/Scheme? ;-)  I'm not sure that i understand thihs question.

> 6) Are there any primitives I could implement into my Lisp that would
> make C parsing trivial?

The one thing holding me back to attempt glueing your stage-N LISP to
Mes is performance (and well, being terribly busy working to release Mes
:-).  Currently mescc takes 2h30' to compile itself.  Compiling tcc is
still a lot of work and is 10x as big...

I fear that running mes on stage-N's LISP adds another 2 factors of
perfomance penalty...

> 7) What else could I be missing about this problem?

It seems you're asking all the right questions...THANK!  However,
although this full source bootstrapping endeavor has been a lot of fun
until now, one of the biggest difficulties has been to reduce the number
of open questions...almost anything seems possible.  So I was hoping to
get more answers and all I get is more questions ;-)

Thanks, greetings
janneke

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

Re: You missed my later work

[Matt Wette]

> On Apr 27, 2017, at 5:55 AM, Jan Nieuwenhuizen <janneke@gnu.org> wrote:
> 
> 
> [cc: Matt, author of Nyacc]
> 
>> Well now you could have told them we already had the forth
>> https://github.com/oriansj/stage0/blob/master/stage2/forth.s
>> but none of the people in the forth community bothered to build upon it
> 
> You created a fully bootstrappable LISP and FORTH, wow!
> 
> That would make my answer easier; I started with Scheme/Lisp because
> you have to start somewhere, and I like that better.
> 
>> For example break up the C compiler problem into pieces, for example
>> have a seperate C preprocessor, a single file C compiler that only
>> produces assembly and just leverage the already existing assembly
>> infrastructure I already made.
> 
> That could open up new possibilities.  However, there are so many
> choices, is this going to help us get forward right now?
> 
>> I honestly feel that is absolutely something that has to be done.
>> However, you'll have to constrain yourself to what language features in
>> C that you use to make the path from what I have completed to what is
>> required possible.
>> 
>> Some questions I have are as follows:
>> 1) Could the C preprocessor componet of Nyacc be isolated and simplified
>> enough to run on stage0's lisp interpreter and solve the C preprocessor
>> question?
> 
> @Matt: would separating the cpp part from Nyacc be feasible?  Do you
> also think that's helpful?
> 

Not sure what you are asking.  Do you want a standalone CPP or a CPP-less C parser?

Re: You missed my later work

[Jeremiah]

> That could open up new possibilities.  However, there are so many
> choices, is this going to help us get forward right now?
You are right, it might not be an ideal step

> Thanks for the pointers!  I just released Mes 0.5, which is now fully
> self hosting.  We would need to investigate.  However, if we restrict
> the boostrapping path to either Mes or stage0+Mes, how could this help?

The idea is to make a sub-C compiler that supports only enough of the C
language required to bootstrap your MES, which I then could hand convert
to assembly and thus solve your lower bootstrapping problem.

> Compiling tcc is near the top of my priority list -- just below
> releasing Mes 0.5 (done) and discussing the next step (doing that now).
> So if nothing changes, I'll be working to compile tcc, any help or
> insights to make that easier are much appreciated.

Use the tests included in tcc, as once you can compile all of them your
compiler should support everything required to compile tcc.

> Posibly.  Christopher Webber mentioned PreScheme to me so I guess he's
> a fan.  Mes is currently prototyped in C, if we could move that to
> [Pre]Scheme that would be great!
>
> However, my first priority is to close the bootstrap loop, i.e. get
> either GCC or Guile compiled from what's Mes now. 

Absolutely agreed. And in the mean time, I'll be making tools to help
your bootstrap become ever easier. I'm looking at following the C
evolutionary path and implementing the META II compiler compiler and a
couple similiar tools.

> The one thing holding me back to attempt glueing your stage-N LISP to
> Mes is performance (and well, being terribly busy working to release Mes
> :-).  Currently mescc takes 2h30' to compile itself.  Compiling tcc is
> still a lot of work and is 10x as big...
>
> I fear that running mes on stage-N's LISP adds another 2 factors of
> perfomance penalty...

How about an easier problem? If your mes was written in lisp, why not
write a lisp compiler capable of compiling the lisp and thus solving the
performance problem.

As once an interpreter is made, you are already 30% done writing a
working compiler.

> It seems you're asking all the right questions...THANK!  However,
> although this full source bootstrapping endeavor has been a lot of fun
> until now, one of the biggest difficulties has been to reduce the number
> of open questions...almost anything seems possible.  So I was hoping to
> get more answers and all I get is more questions ;-)

How is this for some answers.
We are not smarter than all of the great minds of computer science that
have used teams of hundreds to create the foundation of tools upon which
we now stand.

But we have something they didn't... The answers of what worked well.

From that I assert that the correct course of action for us is the
following:
Build simple, easy and fun tools that simplify the task of solving the
problem.

Your lisp interpreter, actually is closer to becoming a lisp compiler
than mine is. Should that interest you, it would solve your performance
problems.

Thank you as always,
-Jeremiah

Next steps for Mes, stage0+? -- Re: You missed my later work

[Jan Nieuwenhuizen]

>> Thanks for the pointers!  I just released Mes 0.5, which is now fully
>> self hosting.  We would need to investigate.  However, if we restrict
>> the boostrapping path to either Mes or stage0+Mes, how could this help?
>
> The idea is to make a sub-C compiler that supports only enough of the C
> language required to bootstrap your MES, which I then could hand convert
> to assembly and thus solve your lower bootstrapping problem.

Ah, and this is what you would need a separate cpp for?

>> Compiling tcc is near the top of my priority list -- just below
>> releasing Mes 0.5 (done) and discussing the next step (doing that now).
>> So if nothing changes, I'll be working to compile tcc, any help or
>> insights to make that easier are much appreciated.
>
> Use the tests included in tcc, as once you can compile all of them your
> compiler should support everything required to compile tcc.

Thanks for the pointer, I missed that.  I have looked into that
yesterday.  There are 55 tests and Mes has two obvious reasons why none
of them work: we need to supply some headers <stdio.h>, <string.h>, and
they are using printf in all tests.

I am curious to see how far Mes will get :-)

>> Posibly.  Christopher Webber mentioned PreScheme to me so I guess he's
>> a fan.  Mes is currently prototyped in C, if we could move that to
>> [Pre]Scheme that would be great!
>>
>> However, my first priority is to close the bootstrap loop, i.e. get
>> either GCC or Guile compiled from what's Mes now. 
>
> Absolutely agreed. And in the mean time, I'll be making tools to help
> your bootstrap become ever easier. I'm looking at following the C
> evolutionary path and implementing the META II compiler compiler and a
> couple similiar tools.

It's good to hear my plan makes sense to you (see below).  What's the
META II compiler compiler?

>> The one thing holding me back to attempt glueing your stage-N LISP to
>> Mes is performance (and well, being terribly busy working to release Mes
>> :-).  Currently mescc takes 2h30' to compile itself.  Compiling tcc is
>> still a lot of work and is 10x as big...
>>
>> I fear that running mes on stage-N's LISP adds another 2 factors of
>> perfomance penalty...
>
> How about an easier problem? If your mes was written in lisp, why not
> write a lisp compiler capable of compiling the lisp and thus solving the
> performance problem.

Indeed, that would be great!  Writing mes.c in Scheme fairly easy of
course; I've done almost that a couple of times already.  Being able to
compile [some] Scheme to native code would be very nice in itself too,
not just for bootstrapping.

> As once an interpreter is made, you are already 30% done writing a
> working compiler.

I was hoping for that, I still need some inspiration here.

>> It seems you're asking all the right questions...THANK!  However,
>> although this full source bootstrapping endeavor has been a lot of fun
>> until now, one of the biggest difficulties has been to reduce the number
>> of open questions...almost anything seems possible.  So I was hoping to
>> get more answers and all I get is more questions ;-)
>
> How is this for some answers.

Yes, thanks a lot!  When I started Mes it looked like an almost
impossible task and what needs to be done can still look daunting.
Questions are great, but some balancing with answers is very helpful.

> We are not smarter than all of the great minds of computer science that
> have used teams of hundreds to create the foundation of tools upon which
> we now stand.
>
> But we have something they didn't... The answers of what worked well.

Yes, I see.  That's the knowledge that must somehow regain.  It's
probably a good thing that not everything works well :-)

> From that I assert that the correct course of action for us is the
> following:
> Build simple, easy and fun tools that simplify the task of solving the
> problem.

Check!

> Your lisp interpreter, actually is closer to becoming a lisp compiler
> than mine is. Should that interest you, it would solve your performance
> problems.

Hmm...It would make sense to write this lisp compiler in lisp, of
course.  No need to write it in C.  Hmm.  I wonder if someone would want
to help transforming the mes.c interpreter into a mes.scm compiler?

> Thank you as always,

Greetings,
janneke

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

Re: Next steps for Mes, stage0+? -- Re: You missed my later work

[Jeremiah]

> Ah, and this is what you would need a separate cpp for?
It would certainly simplify the task of implementation

> Thanks for the pointer, I missed that.  I have looked into that
> yesterday.  There are 55 tests and Mes has two obvious reasons why none
> of them work: we need to supply some headers <stdio.h>, <string.h>, and
> they are using printf in all tests.
>
> I am curious to see how far Mes will get :-)

We can just implement stubs to move ahead and flush them out as we move
forward.
Having seen your work, I am certain Mes will go far :-)

> It's good to hear my plan makes sense to you (see below).  What's the
> META II compiler compiler?

https://en.wikipedia.org/wiki/META_II
One might think of it as an early parser generator, which what actually
was used to create the first B compiler.

> Indeed, that would be great!  Writing mes.c in Scheme fairly easy of
> course; I've done almost that a couple of times already.  Being able to
> compile [some] Scheme to native code would be very nice in itself too,
> not just for bootstrapping.

Especially since, the lisp compiler would allow us to save most of the C
bootstrapping steps and simply improve the lisp side of the equation
until implementing a C compiler in lisp becomes a solved problem.

> I was hoping for that, I still need some inspiration here.

How is this for inspiration?
http://piumarta.com/software/maru/
https://github.com/darius/ichbins

> Yes, thanks a lot!  When I started Mes it looked like an almost
> impossible task and what needs to be done can still look daunting.
> Questions are great, but some balancing with answers is very helpful.
Given first hand experience, my answer is as follows:
Lisp infrastructure seems like the correct course of action.
Which implies the following tasks:
1) add a lisp compiler that only supports the bare minimuim required for
useful work.
2a) Flush out MES C compiler as the most important Lisp program it needs
to compile
or
2b) leaverage minimal Lisp compiler to bootstrap full featured Lisp
compiler written in Lisp, which is then used to compile MES C compiler
and thus reduce implementation restrictions placed on MES C compiler.
3) Use the MES C compiler to compile tcc, make and other essential
bootstrap programs to finish the trusted compile path.
4) Extend and enhance Stage0 lisp to include cell compaction and thus
optimize garbage collection performance.
5) Cooperate to select what primitives would be implemented to allow the
stage0 lisp interpeter would need to get the first lisp compiler running
fast.

> Yes, I see.  That's the knowledge that must somehow regain.  It's
> probably a good thing that not everything works well :-)
certainly saves us from the estimated 4,400 Man-years spent
implementing the first algol compiler...

> Hmm...It would make sense to write this lisp compiler in lisp, of
> course.  No need to write it in C.  Hmm.  I wonder if someone would want
> to help transforming the mes.c interpreter into a mes.scm compiler?
It might take me a little bit to get up to speed with your code base but
I am always willing to try to help.

Sounds like we are going to have lots of fun together :D

-Jeremiah