* HACKING: Update status, some ideas where to go next.
* NEWS: Update status.
* README: Update.
* doc/ANNOUNCE: Move from top.
* doc/ANNOUNCE-2: Likewise.
* doc/ANNOUNCE-0.3: New file.
+++ /dev/null
-Subject: on bootstrapping: introducing Mes
-Date: Sun, 19 Jun 2016 13:08:02 +0200
-
-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
-
+++ /dev/null
-Subject: on bootstrapping: 2nd status report on Mes
-Date: Sun, 25 Sep 2016 13:52:11 +0200
-
-Hi!
-
-In June I announced[0] Mes as a project that seeks to reduce the size of/
-dependency on bootstrap binaries, esp. for a system like GuixSD
-
-The strategy was to create a minimal trusted binary (prototyped in C but
-eventually to be hand-crafted in assembly/hex) that interpets a minimal
-LISP. Then using this minimal but already convenient LISP, extend it
-into Scheme and write a tiny C compiler/linker.
-
-Last time I had a minimal LISP-1.5-resembling interpreter in 900 lines
-of C that could interpret itself and an extension layer written in LISP
-providing a minimal Scheme environment. I was stuck on adding macros in
-LISP and had a broken macro implentation in C that I wanted to remove.
-Also I hoped to greatly reduce the size of the C part.
-
-New status[1]
-
- * Provide Scheme primitives directly in 1400 lines of C
- * Remove LISP-1.5 staging
- * closures clue-bat, fixing bugs in begin, lambda, lexical
- scoping etc. ... learned a lot!
- * quasiquote, unquote, unquote-splicing (in C, too slow in Scheme)
- * define-macro (in C)
- * define-syntax, syntax-rules (in Scheme, using define-macro)
- * all primitives needed to run LALR (strings, vectors, records,
- some srfi bits; mostly in Scheme)
- * test suite with 97 tests that run with Mes and also with Guile
- * minimal and partial ANSI C parser for hello world
- * minimal and simplistic 32 bit elf c-ast->elf generator
-
- Mes can now create a running 32-bit elf binary from this hello
- world C source with a simplistic for loop
-
- int main ()
- {
- int i;
- puts ("Hi Mes!\n");
- for (i = 0; i < 4; ++i)
- puts (" Hello, world!\n");
- return 1;
- }
-
- It takes Mes 1'20" to compile this program, Guile takes 0.5 seconds.
-
- * cannot get psyntax.pp hooked-up or running
- * do not understand syntax stuff [well enough] to implement in C
- -> no let-syntax, no MATCH
- -> no syntax-case, no PEG parser
-
-In theory the bootstrapping problem I set out to solve seems to be
-cracked. The remaining problem is reduced to `just work':
-implementing a minimal C compiler in Scheme. Questions here: I'm not
-convinced yet that this is a meaningful project...aaand I really not
-want to tackle this without having MATCH, which Mes does not have yet.
-
-Of the possible directions that I see
-
- 0 write the C compiler in Scheme without match
- 1 rewrite match without let-syntax
- 2 grok+write let-syntax/syntax-case using define-macro, some bits in C
- 3 run and hook-up psyntax.pp...BUT that would probably require:
- 4 address performance problem, possibly by
- 5 rewrite Mes into a VM-based solution
-
-none I find really attractive. Option 5, a VM is proven to work but
-that's quite a change of direction. Looking at other VM-based projects
-(e.g. GNU Epsilon[2]) I fear that this must result in a much larger code
-base in C, throwing out the minimal trusted binary idea. The other
-puzzles and work 0, 2 or 3 still need to be done.
-
-However, diving into syntax-macro or eval work (2 or 3) most probably
-needs the performance issue addressed. And if it turns out that a big
-VM solution is needed, that may still invalidate this project after
-having done even more work.
-
-Help! :-) Ideas?
-
-Greetings,
-Jan
-
-[0] https://lists.gnu.org/archive/html/guile-user/2016-06/msg00061.html
-[1] https://gitlab.com/janneke/mes
-[2] http://git.savannah.gnu.org/cgit/epsilon.git
performance: still writing as much as possible in Scheme but having a
mescc compiler that takes not more than some seconds to run.
-Now that portable R6RS syntax-case runs and mes.c has grown to
-~1200LOC with another ~300LOC of optional C code, some effort must
-probably be directed into making that smaller.
+Now that we have [[https://github.com/schemeway/lalr-scm][Dominique Boucher's LALR]], a [[https://www.cs.indiana.edu/chezscheme/syntax-case/old-psyntax.html][Pre-R6RS portable
+syntax-case]] with R7RS ellipsis, [[http://www.nongnu.org/nyacc/][Nyacc]] and [[https://www.gnu.org/software/guile/docs/master/guile.html/PEG-Parsing.html][Guile's PEG]] parsers, it's
+time to start doing something useful.
-** Move mes.c into hex?
+* Bugs
+** The Scheme reader is very slow.
+** Catch/throw are a syntax only hack for Nyacc.
+** Fluids are a hack for Nyacc.
+** Prototype mes.c depends on a C compiler.
+*** Translate C-prototype mes.c into annotated 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
+*** Rewrite mes.c in Schemy/Sexp-C and generate annotated hex?
+Another idea (thanks Rutger!) is to rewrite the mes.c core in a s-exp
C/Assembly variant and thave mescc produce the simple, annotated
bootstrap binary.
-* Bugs
-** Core is too fat
-mes.c is ~1500 lines (~10,000LOC Assembly) which seems much too big to
-start translating it to assembly/hex.
+** Actually do something useful
+*** Rewrite the mescc compiler to work on the Nyacc AST.
+The proof-of-concept mescc compiler uses a simple, whoefully
+incomplete AST produced by a simplistic LALR-based C-parser.
+*** Implement more bits of the compiler.
+As Mes now runs Nyacc, and Guile runs the mescc compiler, this
+compiler can be developed using Guile.
+*** Compile mes.c using mescc.
+A first milestone, next up is...
+*** Compile the [[https://en.wikipedia.org/wiki/Tiny_C_Compiler][Tiny C Compiler]]
-** Actually do something useful, build: [[https://en.wikipedia.org/wiki/Tiny_C_Compiler][Tiny C Compiler]]
* OLD: Booting from LISP-1.5 into Mes
Mes started out experimenting with booting from a hex-coded minimal
*** [[http://www.scheme-reports.org/][Scheme Reports]]
*** [[ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-349.pdf][Scheme - Report on Scheme]]
*** [[ftp://publications.ai.mit.edu/ai-publications/pdf/AIM-452.pdf][RRS - Revised Report on Scheme]]
-
* Changes in 0.4 since 0.3
** Core
-*** Smaller C-reader
+*** Improved performance.
+Macros are now memoized; after expansion and before eval'ing the
+expanded form, their input s-expression is replaced by the expansion.
+This yields a nice performance improvement which finally allowed
+moving all non-essential bits from the C-core into Scheme...including
+the reader. The Scheme reader is much, much slower than the previous
+C version, making Mes--again-- feel slow. Think of that as a feature.
+*** Bootstrap with minimal reader in C.
The C-reader needs only support reading of words and lists
-(s-expressions), line-comments. Quoting, characters, strings,
-block-comments are all handled by the Scheme reader later.
+(s-expressions), line-comments to read the initial [[file:module/mes/read-0.mes][Scheme reader]] which
+then takes over and handles reading of quoting, characters, strings,
+block-comments.
+*** Reduced size.
+Total C size: ~1500LOC. The main Mes evaluator is now ~1000LOC
+including cell creation and garbage collector. This code is able to
+execute a Scheme progam 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.
+*** Programs can be dumped and loaded using --dump and --load.
** Language
-*** Keywords are supported.
+*** Minimal syntactic exception support for Nyacc.
+*** Minimal syntactic fluids support for Nyacc.
+*** Keywords are now supported.
*** Cond now supports =>.
-*** Lambda* and define* are now supported.
-*** #;-comment is now supported.
-*** Non-nested #| |#-comment is now supported.
+*** Guile's optargs: lambda* and define* are now supported.
+*** #;-comments are now supported.
+*** Non-nested #| |#-comments are now supported.
+*** Quasisyntax is now supported.
*** R7RS syntax-rules with custom ellipsis, with-ellipsis are now supported.
+*** 9 new [partial] modules
+(mes fluids), (mes nyacc), (mes optargs), (mes pmatch), (mes peg),
+(srfi srfi-13), (srfi srfi-9-psyntax), (srfi srfi-26), (srfi srfi-43),
+(rnrs arithmetic bitwise), (sxml xpath)
+*** 36 new functions
+1+, 1-, abs, and=>, append-reverse, ash, char<=?, char<?, char>=?,
+char>?, even?, filter, delete, delq, vector-copy, fold, fold-right,
+getenv, iota, keyword->symbol list-head, list-tail, negative?, odd?,
+positive?, remove!, remove, string->number, string-copy,
+string-prefix?, string=, string=?, symbol->keyword symbol-append,
+symbol-prefix?, unless, write, zero?.
** Noteworthy bug fixes
+*** Macros are now memoized.
+*** An error is reported when using a wrong number of arguments with a call.
+*** Cond now evaluates its test clauses only once.
+*** Append can also handle one argument.
+*** For-each now supports 2 list arguments.
+*** Map now supports 3 list arguments.
+*** Backslash in string is supported.
*** Closure is not a pair.
+*** All standard characters are supported.
+*** Mescc now also runs in Guile.
* Changes in 0.3 since 0.2
** Core
*** Number-based rather than pointer-based cells.
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.
+Collector (Jam Scraper), a library of loadable Scheme modules--
+notably [[https://github.com/schemeway/lalr-scm][Dominique Boucher's LALR]], [[https://www.cs.indiana.edu/chezscheme/syntax-case/old-psyntax.html][Pre-R6RS portable syntax-case]] with
+R7RS ellipsis, [[http://www.nongnu.org/nyacc/][Nyacc]] and [[https://www.gnu.org/software/guile/docs/master/guile.html/PEG-Parsing.html][Guile's PEG]] --and 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: [[http://www.softwarepreservation.org/projects/LISP/book/LISP%25201.5%2520Programmers%2520Manual.pdf][LISP-1.5]] -- John
McCarthy page 13.
* Other
make check
- make guile-check
make mes-check
make paren
make mescc
+ scripts/nyacc-calc.mes
+ scripts/nyacc.mes
+
+ make guile-check
+ make guile-mescc
+ guile/nyacc-calc.scm
+ scripts/nyacc.scm
--- /dev/null
+Subject: on bootstrapping: introducing Mes
+Date: Sun, 19 Jun 2016 13:08:02 +0200
+
+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
+
--- /dev/null
+Subject: on bootstrapping: first Mes 0.3 released
+
+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
--- /dev/null
+Subject: on bootstrapping: 2nd status report on Mes
+Date: Sun, 25 Sep 2016 13:52:11 +0200
+
+Hi!
+
+In June I announced[0] Mes as a project that seeks to reduce the size of/
+dependency on bootstrap binaries, esp. for a system like GuixSD
+
+The strategy was to create a minimal trusted binary (prototyped in C but
+eventually to be hand-crafted in assembly/hex) that interpets a minimal
+LISP. Then using this minimal but already convenient LISP, extend it
+into Scheme and write a tiny C compiler/linker.
+
+Last time I had a minimal LISP-1.5-resembling interpreter in 900 lines
+of C that could interpret itself and an extension layer written in LISP
+providing a minimal Scheme environment. I was stuck on adding macros in
+LISP and had a broken macro implentation in C that I wanted to remove.
+Also I hoped to greatly reduce the size of the C part.
+
+New status[1]
+
+ * Provide Scheme primitives directly in 1400 lines of C
+ * Remove LISP-1.5 staging
+ * closures clue-bat, fixing bugs in begin, lambda, lexical
+ scoping etc. ... learned a lot!
+ * quasiquote, unquote, unquote-splicing (in C, too slow in Scheme)
+ * define-macro (in C)
+ * define-syntax, syntax-rules (in Scheme, using define-macro)
+ * all primitives needed to run LALR (strings, vectors, records,
+ some srfi bits; mostly in Scheme)
+ * test suite with 97 tests that run with Mes and also with Guile
+ * minimal and partial ANSI C parser for hello world
+ * minimal and simplistic 32 bit elf c-ast->elf generator
+
+ Mes can now create a running 32-bit elf binary from this hello
+ world C source with a simplistic for loop
+
+ int main ()
+ {
+ int i;
+ puts ("Hi Mes!\n");
+ for (i = 0; i < 4; ++i)
+ puts (" Hello, world!\n");
+ return 1;
+ }
+
+ It takes Mes 1'20" to compile this program, Guile takes 0.5 seconds.
+
+ * cannot get psyntax.pp hooked-up or running
+ * do not understand syntax stuff [well enough] to implement in C
+ -> no let-syntax, no MATCH
+ -> no syntax-case, no PEG parser
+
+In theory the bootstrapping problem I set out to solve seems to be
+cracked. The remaining problem is reduced to `just work':
+implementing a minimal C compiler in Scheme. Questions here: I'm not
+convinced yet that this is a meaningful project...aaand I really not
+want to tackle this without having MATCH, which Mes does not have yet.
+
+Of the possible directions that I see
+
+ 0 write the C compiler in Scheme without match
+ 1 rewrite match without let-syntax
+ 2 grok+write let-syntax/syntax-case using define-macro, some bits in C
+ 3 run and hook-up psyntax.pp...BUT that would probably require:
+ 4 address performance problem, possibly by
+ 5 rewrite Mes into a VM-based solution
+
+none I find really attractive. Option 5, a VM is proven to work but
+that's quite a change of direction. Looking at other VM-based projects
+(e.g. GNU Epsilon[2]) I fear that this must result in a much larger code
+base in C, throwing out the minimal trusted binary idea. The other
+puzzles and work 0, 2 or 3 still need to be done.
+
+However, diving into syntax-macro or eval work (2 or 3) most probably
+needs the performance issue addressed. And if it turns out that a big
+VM solution is needed, that may still invalidate this project after
+having done even more work.
+
+Help! :-) Ideas?
+
+Greetings,
+Jan
+
+[0] https://lists.gnu.org/archive/html/guile-user/2016-06/msg00061.html
+[1] https://gitlab.com/janneke/mes
+[2] http://git.savannah.gnu.org/cgit/epsilon.git
projects / mes.git / commitdiff