on bootstrapping: first Mes 0.3 released

on bootstrapping: first Mes 0.3 released

[Jan Nieuwenhuizen]

Hi!

I am pleased to announce the first release of Mes: 0.3, representing
152 commits over 3 months since the second status report[1].

* About

    Mes aims to create an entirely source-based bootstrapping path.  The
    target is to [have GuixSD] boostrap from a minimal, easily inspectable
    binary --that should be readable as source-- into something close to
    R6RS Scheme.

    As bootstrapping is presumably easiest and probably most fun with
    Scheme, the next step for Mes is mescc: a C compiler/linker to
    boostrap into GNU Gcc and GNU Guile, possibly via Tiny-CC.

    It currently has an interpreter written in C (mes) with Garbage
    Collector (Jam Scraper), a library of loadable Scheme modules with
    test suite just barely enough to support a simple REPL (repl.mes)
    and a proof-of-concept c-compiler (mescc.mes) that produces an elf
    from the simplest of C files.

    Mes is inspired by The Maxwell Equations of Software: LISP-1.5[2]
    -- John McCarthy page 13

* Download

    git clone https://gitlab.com/janneke/mes

    wget https://gitlab.com/janneke/mes/repository/archive.tar.gz?ref=v0.3 -O mes-0.3.tar.gz

Mes runs from the source tree and can also be built, packaged and
installed in Guix[SD] by the usual

    guix package -f guix.scm


* Changes in 0.3 since 0.2
 ** Core
 *** Number-based rather than pointer-based cells.
 *** Garbage collector aka Jam scraper.
 A variant on SICP's stop and copy Garbage Collector (Jam Scraper?)
 algorithm has been implemented.
 *** The reader has been moved to Scheme.
 ** Language
 *** Simple loadable modules.
 *** Srfi-9 and match use handwritten syntax-rules (mes-use-module (mes syntax)).
 *** Optional syntax-case using psyntax (mes-use-module (mes psyntax)).
 ** Noteworthy bug fixes
 *** Srfi-0 has been fixed.

* Changes in 0.2 since 0.1
 ** Core
 *** Names of symbols and strings are list of characters [WAS: c-string].
 *** Sc-expand from pre-R6RS's psyntax has been integrated.
 *** Undefined variable error now shows the name of the undefined variable.
 *** There is now only one SCM type for builtin functions.
 *** Macro expansion has been cleaned-up.
 ** Language
 *** Mes now provides a subset of R6RS.
 *** Mes now provides syntax-case.
 *** Mes now provides `load'.
 ** Noteworthy bug fixes
 *** Using values as second parameter of builtin function yields first value.
 *** Quoted internals (e.g. 'if 'lambda) are now symbols.
 *** Syntax error now exits.
 *** Make+Bash voodoo has been replaced by build-aux/mes-snarf.scm.
 *** Apply now accepts multiple list arguments.
 *** Apply of character, inernal, number, string is an error.
 *** Quasisyntax reading 

* Changes in 0.1 (since progress report #2)
 ** Core
 *** expand_macro is now a separate function.
 *** A smaller core can now compiled using BOOT=1.
 The smaller core does not provide define, define-macro, or quasiquote;
 these are provided from a Scheme version of implemented eval/apply.
 ** Language
 *** Mes now provides a subset of R5RS.
 *** Mes now provides let-syntax.
 *** Mes now provides match.
 *** Mes now provides quasisyntax, unsyntax and unsyntax-splicing.
 ** User interface
 *** Mes now provides a REPL, run:
     scripts/repl.mes
 *** Mes compiler can be run as a script:
     scripts/mescc.mes doc/examples/main.c
 *** Macro expansion can be inspected in the REPL, e.g.:
     ,expand (and 0 1)
 ** Noteworthy bug fixes
 *** Performance: scripts/mescc.mes now takes 2s to compile main.c (was 1'20").
 *** Symbols are now truly unique.
   * '(), #t, #f are no longer symbols.

Greetings,
Jan

[1] https://lists.nongnu.org/archive/html/guile-user/2016-09/msg00061.html 
[2] http://www.softwarepreservation.org/projects/LISP/book/LISP%25201.5%2520Programmers%2520Manual.pdf

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

Re: on bootstrapping: first Mes 0.3 released

[Arne Babenhauserheide]

[-- Attachment #1: Type: text/plain, Size: 1449 bytes --]


Jan Nieuwenhuizen writes:

> I am pleased to announce the first release of Mes: 0.3, representing
> 152 commits over 3 months since the second status report[1].
>
> * About
>
>     Mes aims to create an entirely source-based bootstrapping path.  The
>     target is to [have GuixSD] boostrap from a minimal, easily inspectable
>     binary --that should be readable as source-- into something close to
>     R6RS Scheme.

This is really cool! Thank you for your work!

>     As bootstrapping is presumably easiest and probably most fun with
>     Scheme, the next step for Mes is mescc: a C compiler/linker to
>     boostrap into GNU Gcc and GNU Guile, possibly via Tiny-CC.
>
>     It currently has an interpreter written in C (mes) with Garbage
>     Collector (Jam Scraper), a library of loadable Scheme modules with
>     test suite just barely enough to support a simple REPL (repl.mes)
>     and a proof-of-concept c-compiler (mescc.mes) that produces an elf
>     from the simplest of C files.

How do you compile the interpreter?

>     Mes is inspired by The Maxwell Equations of Software: LISP-1.5[2]
>     -- John McCarthy page 13
…
> [1] https://lists.nongnu.org/archive/html/guile-user/2016-09/msg00061.html 
> [2] http://www.softwarepreservation.org/projects/LISP/book/LISP%25201.5%2520Programmers%2520Manual.pdf

Best wishes,
Arne
-- 
Unpolitisch sein
heißt politisch sein
ohne es zu merken

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 800 bytes --]

Re: on bootstrapping: first Mes 0.3 released

[Jan Nieuwenhuizen]

Arne Babenhauserheide writes:

>>     Mes aims to create an entirely source-based bootstrapping path.  The
>>     target is to [have GuixSD] boostrap from a minimal, easily inspectable
>>     binary --that should be readable as source-- into something close to
>>     R6RS Scheme.
>
> This is really cool! Thank you for your work!

Good, thanks!

>>     It currently has an interpreter written in C (mes) with Garbage
>>     Collector (Jam Scraper), a library of loadable Scheme modules with
>>     test suite just barely enough to support a simple REPL (repl.mes)
>>     and a proof-of-concept c-compiler (mescc.mes) that produces an elf
>>     from the simplest of C files.
>
> How do you compile the interpreter?

The current interpeter I consider to be a prototype in C; I use gcc.
However, HACKING mentions two ways forward

    ** Move mes.c into hex?
    One idea is to use OrianJ's amazing self-hosting
    [[https://github.com/oriansj/stage0][stage0]] hex assembler and
    minimal bootstrap binaries and rewrite the mes.c core to directly
    bootstrap into Scheme.

    ** Rewrite mes.c and generate hex?
    Another idea (thanks Rutger!) is to rewrite the mes.c core in a
    C/Assembly variant and have mescc produce the simple, annotated
    bootstrap binary.

Possibly you have an even better idea?  I am choosing to explore the
latter first: work on the compiler backend and write the interpreter in
its Assembly/C-like s-expressions.

> Best wishes,

Thanks, Greetings,
Jan

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

Re: on bootstrapping: first Mes 0.3 released

[Arne Babenhauserheide]

[-- Attachment #1: Type: text/plain, Size: 1273 bytes --]


Jan Nieuwenhuizen writes:

> Arne Babenhauserheide writes:
>> How do you compile the interpreter?
>
> The current interpeter I consider to be a prototype in C; I use gcc.
> However, HACKING mentions two ways forward
>
>     ** Move mes.c into hex?
>     One idea is to use OrianJ's amazing self-hosting
>     [[https://github.com/oriansj/stage0][stage0]] hex assembler and
>     minimal bootstrap binaries and rewrite the mes.c core to directly
>     bootstrap into Scheme.

This seems to be the strongest option, but also very expensive. And only
useful if it becomes a step on the way to compile GCC (the goal of
stage0).

>     ** Rewrite mes.c and generate hex?
>     Another idea (thanks Rutger!) is to rewrite the mes.c core in a
>     C/Assembly variant and have mescc produce the simple, annotated
>     bootstrap binary.
>
> Possibly you have an even better idea?  I am choosing to explore the
> latter first: work on the compiler backend and write the interpreter in
> its Assembly/C-like s-expressions.

I think the C/Assembly variant sounds better — maybe written in simple
enough style to be compiled by stage0 before that can compile GCC.

Best wishes,
Arne
-- 
Unpolitisch sein
heißt politisch sein
ohne es zu merken

[-- Attachment #2: signature.asc --]
[-- Type: application/pgp-signature, Size: 800 bytes --]

Re: on bootstrapping: first Mes 0.3 released

[Christopher Allan Webber]

Jan Nieuwenhuizen writes:

> The current interpeter I consider to be a prototype in C; I use gcc.
> However, HACKING mentions two ways forward
>
>     ** Move mes.c into hex?
>     One idea is to use OrianJ's amazing self-hosting
>     [[https://github.com/oriansj/stage0][stage0]] hex assembler and
>     minimal bootstrap binaries and rewrite the mes.c core to directly
>     bootstrap into Scheme.
>
>     ** Rewrite mes.c and generate hex?
>     Another idea (thanks Rutger!) is to rewrite the mes.c core in a
>     C/Assembly variant and have mescc produce the simple, annotated
>     bootstrap binary.
>
> Possibly you have an even better idea?  I am choosing to explore the
> latter first: work on the compiler backend and write the interpreter in
> its Assembly/C-like s-expressions.

First, I'm really excited you're making progress on Mes!

Second, Scheme48 did something similar to this, called "Pre-Scheme",
which is how they bootstrapped Scheme48 iirc.  Have you heard of it or
looked at it?

  https://en.wikipedia.org/wiki/PreScheme

Re: on bootstrapping: first Mes 0.3 released

[Ludovic Courtès]

Hi!

Jan Nieuwenhuizen <janneke@gnu.org> skribis:

> * Changes in 0.3 since 0.2
>  ** Core
>  *** Number-based rather than pointer-based cells.
>  *** Garbage collector aka Jam scraper.
>  A variant on SICP's stop and copy Garbage Collector (Jam Scraper?)
>  algorithm has been implemented.
>  *** The reader has been moved to Scheme.
>  ** Language
>  *** Simple loadable modules.
>  *** Srfi-9 and match use handwritten syntax-rules (mes-use-module (mes syntax)).
>  *** Optional syntax-case using psyntax (mes-use-module (mes psyntax)).
>  ** Noteworthy bug fixes
>  *** Srfi-0 has been fixed.

Impressive!

Is it a goal to try interpret a language as close as possible to that of
Guile, and have the same libraries?  I guess that could help in the
future: we could use (system base lalr), nyacc, etc.

Also, currently there’s approximately 2K lines of C.  How do you plan to
make sure that it doesn’t grow over time, or even that it shrinks?  :-)

This all sounds very promising, thanks a lot!

Ludo’.

Re: on bootstrapping: first Mes 0.3 released

[Jan Nieuwenhuizen]

Christopher Allan Webber writes:

> First, I'm really excited you're making progress on Mes!

Yay, thanks!

> Second, Scheme48 did something similar to this, called "Pre-Scheme",
> which is how they bootstrapped Scheme48 iirc.  Have you heard of it or
> looked at it?

Ah, that's nice.

>   https://en.wikipedia.org/wiki/PreScheme

Yes, that helps.  I looked briefly at Scheme48 but could not make
much of it.  This helps a lot.  Amazing trick.  It's not enough
if we want to bootstrap from source only, but it could help.

Greetings, Jan

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

Re: on bootstrapping: first Mes 0.3 released

[Jan Nieuwenhuizen]

Ludovic Courtès writes:

Hi!

> Impressive!

Thanks!

> Is it a goal to try interpret a language as close as possible to that of
> Guile, and have the same libraries?  I guess that could help in the
> future: we could use (system base lalr), nyacc, etc.

We definitely want Nyacc and PEG, and who can live without lambda*?
Other than that I intend to cut as many corners as I can get away with,
also wrt Guile compatibility; at least for now.

> Also, currently there’s approximately 2K lines of C.  How do you plan to
> make sure that it doesn’t grow over time, or even that it shrinks?  :-)

It was worse, about 2600LOC.  I worked very hard last week and also had
a bit of luck.  I found a performance clue-bat while reading Guile-1.8's
eval.c; now macros are expanded only once.

This helped so much that I finally started moving stuff from the C
prototype into Scheme; about 1000LOC have been removed.  The intepreter
with all dependencies, including cell creation and garbage collector is
now ~1000LOC.  That is able to execute a Scheme program that has been
loaded into memory.  Another ~500LOC is spent to load a minimal Scheme
program and to dump it, to provide a small posix interface, math
functions and do some error reporting.

Next up: 0.4 release.  Then I want to start working on the now very
simplistic compiler backend and hook it up to Nyacc's AST.  As the
current proof-of-concept C compiler runs in Guile too and Nyacc runs
in Mes this can be all done in Guile or a joint Guile/Mes project.

> This all sounds very promising, thanks a lot!

Yay, quit happy to hack on this!

Greetings,
Jan

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