655 lines
21 KiB
JavaScript
655 lines
21 KiB
JavaScript
/**
|
||
* Bootstrap procedure for Ulambda Scheme
|
||
*
|
||
* Copyright (C) 2017, 2018 Mike Gerwitz
|
||
*
|
||
* This file is part of Ulambda Scheme.
|
||
*
|
||
* Ulambda Scheme is free software: you can redistribute it and/or modify
|
||
* it under the terms of the GNU Affero General Public License as
|
||
* published by the Free Software Foundation, either version 3 of the
|
||
* License, or (at your option) any later version.
|
||
*
|
||
* This program is distributed in the hope that it will be useful,
|
||
* but WITHOUT ANY WARRANTY; without even the implied warranty of
|
||
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
|
||
* GNU General Public License for more details.
|
||
*
|
||
* You should have received a copy of the GNU Affero General Public License
|
||
* along with this program. If not, see <http://www.gnu.org/licenses/>.
|
||
*
|
||
* Ideally, the user should be able to bootstrap Ulambda Scheme with nothing
|
||
* more than what they already have installed on their computer, in the
|
||
* environment that Ulambda was designed to run in---the web browser.
|
||
* Node.js was used during official development, but that is a large system
|
||
* that should not be a necessary dependency---it should be needed only for
|
||
* convenience.
|
||
*
|
||
* To run this process on a local development environment using Node.js, see
|
||
* `../bootstrap.js'. To run in your web browser, see `../bootstrap.html'.
|
||
*/
|
||
|
||
'use strict';
|
||
|
||
|
||
/**
|
||
* Bootstrap procedure for Ulambda Scheme
|
||
*
|
||
* This abstracts the bootstrap process in such a way that it can be run in
|
||
* any JavaScript environment. Notably, we need to support not only Node.js
|
||
* (which is convenient for development and automation), but also a web
|
||
* browser, which allows users to bootstrap using only their runtime
|
||
* environment and no additional tools.
|
||
*
|
||
* Prebirth and every compiler thereafter are designed to be able to be run
|
||
* from the command line, accepting source code on standard input. Such a
|
||
* concept does not exist in a browser environment, and therefore cannot
|
||
* exist here; there is an awkward abstraction to work around that.
|
||
*/
|
||
class Bootstrap
|
||
{
|
||
/**
|
||
* Initialize bootstrap process
|
||
*
|
||
* The file loader `getf' must accept a path to a file to load and
|
||
* return a Promise representing the contents of that file. The logger
|
||
* function `logf' must accept a string message and, as an optional
|
||
* argument an Error. `prebirth' should be `Prebirth' from
|
||
* `prebirth.js'.
|
||
*
|
||
* @param {function(string):Promise} getf file loader
|
||
* @param {function(string,Error=}} logf logger
|
||
* @param {Prebirth} prebirth Prebirth
|
||
*/
|
||
constructor( getf, logf, prebirth )
|
||
{
|
||
this._getf = getf;
|
||
this._logf = logf;
|
||
this._prebirth = prebirth;
|
||
}
|
||
|
||
|
||
/**
|
||
* Perform bootstrapping process
|
||
*
|
||
* This compiles each of the phases of Ulambda Scheme beginning with
|
||
* Prebirth. This will evolve in complexity as we continue to move
|
||
* forward.
|
||
*
|
||
* There is currently no final result from this method other than
|
||
* log output and an indication of success or failure; that'll change as
|
||
* we get further along and will produce the final compiler.
|
||
*
|
||
* @return {undefined} nothing yet.
|
||
*/
|
||
bootstrap()
|
||
{
|
||
this._strout( 'header' );
|
||
|
||
return this._birth()
|
||
.then( birth => this._rebirth( birth ) )
|
||
.then( rebirth => this._testViable( rebirth ) )
|
||
.catch( e => this._error( e ) )
|
||
.then( status =>
|
||
this._log( "=> " + this._doneMessage( status ) )
|
||
);
|
||
}
|
||
|
||
|
||
/**
|
||
* Produce self-hosted Birth
|
||
*
|
||
* Prebirth will be used to compile Birth, which is written in
|
||
* Prebirth Lisp. Birth will then be used to compile itself, becoming
|
||
* self-hosting.
|
||
*
|
||
* This process is self-verifying: Birth compiled with both Prebirth and
|
||
* Birth itself should produce output that is identical (with regards to
|
||
* JavaScript's string representation). In practice, since Birth uses
|
||
* only ASCII, this amounts to verifying that the outputs are
|
||
* bytewise-identical.
|
||
*
|
||
* The result of this method will be a unary function that, given a
|
||
* Birth Lisp source string, will compile that string into JavaScript.
|
||
*
|
||
* @return {Promise<function(string):string>} Birth compiler
|
||
*/
|
||
_birth()
|
||
{
|
||
return this._loadPaths(
|
||
[
|
||
[ "birth.scm", "Birth" ],
|
||
[ "libprebirth.js", "libprebirth" ],
|
||
].concat( Bootstrap._rebirthDeps )
|
||
)
|
||
.then( files =>
|
||
{
|
||
this._strout( 'prebirthDesc' );
|
||
|
||
const preout = this._prebirth.compile(
|
||
files[ "birth.scm" ],
|
||
files[ "libprebirth.js" ],
|
||
);
|
||
|
||
return [ preout, files ];
|
||
} )
|
||
.then( ( [ birthjs, files ] ) =>
|
||
{
|
||
this._strout( 'prebirthComplete', birthjs.length );
|
||
this._strout( 'birthCompiled' );
|
||
this._strout( 'birthSelfCompiling' );
|
||
|
||
const birthf = this._makeCompiler( birthjs, files );
|
||
|
||
const [ e, birthout ] = birthf( files[ "birth.scm" ] );
|
||
|
||
if ( e ) {
|
||
throw e;
|
||
}
|
||
|
||
this._verifyBirthOutput( birthout, birthjs );
|
||
|
||
return birthf;
|
||
} );
|
||
}
|
||
|
||
|
||
/**
|
||
* Verify that self-compiled Birth output BIRTHOUT matches that of
|
||
* Prebirth-compiled Birth BIRTHJS
|
||
*
|
||
* @param {string} birthout self-compiled Birth
|
||
* @param {string} birthjs Prebirth-compiled Birth
|
||
*
|
||
* @throws {Error} on non-match
|
||
*
|
||
* @return {undefined}
|
||
*/
|
||
_verifyBirthOutput( birthout, birthjs )
|
||
{
|
||
if ( birthout === '' ) {
|
||
throw Error( "Self-compilation yielded no output" );
|
||
}
|
||
|
||
this._strout( 'birthVerify' );
|
||
|
||
if ( birthout !== birthjs ) {
|
||
this._strout( 'birthVerifyFail' );
|
||
|
||
throw Error(
|
||
"Birth self-compilation output does not match Prebirth!"
|
||
);
|
||
}
|
||
|
||
this._strout( 'birthVerifyOk' );
|
||
}
|
||
|
||
|
||
/**
|
||
* Create unary function wrapping the compiler JS with a stub
|
||
* filesystem FS
|
||
*
|
||
* The unary function accepts a source file which is then passed to the
|
||
* compiler via the stub filesystem on "/dev/stdin". The output of the
|
||
* compiler is returned as a string.
|
||
*
|
||
* The stub filesystem should contain the contents of all files
|
||
* dynamically loaded by the compiler JS. This abstraction allows the
|
||
* bootstrapping process to work in any environment without regards to
|
||
* whether a filesystem even exists, and regardless of whether loading
|
||
* is a synchronous or asynchronous operation.
|
||
*
|
||
* @param {string} js JavaScript code of compiler (to be eval'd)
|
||
* @param {Object} fs mapping of filename to content for stub filesystem
|
||
*
|
||
* @return {string} compiler output
|
||
*/
|
||
_makeCompiler( js, fs = {} )
|
||
{
|
||
const birth = new Function(
|
||
'let __fsinit = this.__fsinit;' +
|
||
'let require = this.require;' +
|
||
'let out = "";\n' +
|
||
'const console = { log: str => out += str + "\\n" };\n' +
|
||
'try {' + js + '} catch( e ) { return [ e, out ]; }' +
|
||
'return [ null, out ];'
|
||
);
|
||
|
||
return scm =>
|
||
{
|
||
fs[ "/dev/stdin" ] = scm;
|
||
return birth.call( { __fsinit: fs } );
|
||
};
|
||
}
|
||
|
||
|
||
/**
|
||
* Compile Rebirth using Birth and yield unary compiler function
|
||
*
|
||
* This begins the recursive compilation of Rebirth, beginning with
|
||
* the first generation Re¹birth, using the self-hosted Birth. The
|
||
* first generation of Rebirth is written purely in Birth Lisp. The
|
||
* resulting compiler has more features than Birth, which is then used
|
||
* to compile itself again, producing a compiler with even more
|
||
* features. This process repeats until the output does not change.
|
||
*
|
||
* @param {function(string):string} birth Birth
|
||
*
|
||
* @return {Promise<function(string):string>} final Rebirth generation
|
||
*/
|
||
_rebirth( birth )
|
||
{
|
||
return this._loadPaths(
|
||
[ [ "rebirth.scm", "Rebirth" ] ].concat( Bootstrap._rebirthDeps )
|
||
).then( files =>
|
||
this._compileRebirth( birth, files[ "rebirth.scm" ], files )
|
||
);
|
||
}
|
||
|
||
|
||
/**
|
||
* Recursively compile Rebirth until two consecutive generations match
|
||
* and yield the unary compiler function for the final generation
|
||
*
|
||
* The first time this method is called, it should be called with Birth
|
||
* as the unary compiler function COMPILE. It should each time be
|
||
* provided with the Rebirth source code SCM and the necessary stub
|
||
* filesystem FS (these are identical for each recursive invocation of
|
||
* this method).
|
||
*
|
||
* Recursion terminates when the compiler COMPILE output matches that of
|
||
* the previous generation PREV, at which point the unary compiler
|
||
* function COMPILE will be yielded as the final generation (with the
|
||
* final generation number being N-1 to account for the duplicate).
|
||
*
|
||
* @param {function(string):string} compile compiler (Birth or Rebirth)
|
||
* @param {string} scm Rebirth source
|
||
* @param {Object} fs stub filesystem for Rebirth
|
||
* @param {number=} n target Rebirth generation id
|
||
* @param {string=} prev previous Rebirth generation
|
||
*
|
||
* @return {Promise<function(string):string>} final Rebirth generation
|
||
* or Error on error
|
||
*/
|
||
_compileRebirth( compile, scm, fs, n = 1, prev = "" )
|
||
{
|
||
this._strout( 'rebirthCompiling', n );
|
||
|
||
const [ e , birthout ] = compile( scm );
|
||
|
||
if ( e || birthout === '' ) {
|
||
return Promise.reject(
|
||
e || Error( "Rebirth compilation yielded no output" )
|
||
);
|
||
}
|
||
|
||
this._strout( 'rebirthCompiled', n, birthout.length );
|
||
|
||
const rebirthf = this._makeCompiler( birthout, fs );
|
||
|
||
if ( birthout === prev ) {
|
||
this._strout( 'rebirthDone', ( n - 1 ) );
|
||
return Promise.resolve( compile );
|
||
}
|
||
|
||
// recurse, but just in case we're running in a browser, give a
|
||
// change to repaint the log (otherwise we'd just hang until every
|
||
// Rebirth is compiled)
|
||
return new Promise( accept =>
|
||
setTimeout( () => accept( this._compileRebirth(
|
||
rebirthf, scm, fs, ( n + 1 ), birthout
|
||
) ) )
|
||
);
|
||
}
|
||
|
||
|
||
/**
|
||
* Compile and run the Rebirth Viability Test suite
|
||
*
|
||
* Once a Rebirth generation has been chosen, it can be used to compile
|
||
* and run a test suite. This suite not only aids in hacking the
|
||
* bootstrap process and preventing regressions, but also makes clear
|
||
* _what_ part of Rebirth might have problems.
|
||
*
|
||
* If the test suite succeeds, then Rebirth is said to be viable and can
|
||
* then be used to compile Ulambda core.
|
||
*
|
||
* The return value is a Promise that is either resolved with the given
|
||
* REBIRTH or rejected with an error. In either case, the output of the
|
||
* test suite will be logged to the console.
|
||
*
|
||
* @param {function(string):string} compile Rebirth compiler
|
||
*
|
||
* @return {Promise<function(string):string>} final Rebirth generation
|
||
* or Error on error
|
||
*/
|
||
_testViable( rebirth )
|
||
{
|
||
return this._loadPaths( [
|
||
[ "rebirth/test.scm", "Rebirth Viability Test" ],
|
||
] )
|
||
.then( ( { "rebirth/test.scm": scm } ) =>
|
||
{
|
||
this._strout( 'rebirthTestCompiling' );
|
||
|
||
const [ e, testsuite ] = rebirth( scm );
|
||
|
||
if ( e || testsuite === '' ) {
|
||
return Promise.reject(
|
||
e || Error( "Rebirth test suite yielded no output" )
|
||
);
|
||
}
|
||
|
||
this._strout( 'rebirthTestCompiled', testsuite.length );
|
||
|
||
// invoke the compiled test suite, making note of both the
|
||
// error and the output
|
||
const [ te, output ] = this._makeCompiler( testsuite )();
|
||
|
||
this._log( output.trimRight() );
|
||
|
||
if ( te !== null ) {
|
||
this._strout( 'rebirthTestFailed' );
|
||
return Promise.reject( te );
|
||
}
|
||
|
||
this._strout( 'rebirthTestDone' );
|
||
|
||
// rebirth is good, so continue to propagate it
|
||
return Promise.resolve( rebirth );
|
||
} );
|
||
}
|
||
|
||
|
||
/**
|
||
* Produce a promise for the file contents of each of `path'
|
||
*
|
||
* See also `#_loadPath'.
|
||
*
|
||
* @param {Array<string>} paths file paths
|
||
*
|
||
* @return {Promise} resolved with map of paths to associated data
|
||
*/
|
||
_loadPaths( paths )
|
||
{
|
||
return Promise.all(
|
||
paths.map( ( [ path, desc ] ) =>
|
||
this._loadPath( path, desc )
|
||
)
|
||
).then( files => files.reduce(
|
||
( files, [ path, data ] ) => ( ( files[ path ] = data ), files ),
|
||
{}
|
||
) );
|
||
}
|
||
|
||
|
||
/**
|
||
* Produce a promise for the file contents of `path'
|
||
*
|
||
* This action is logged with the description `desc' and the length of
|
||
* the result.
|
||
*
|
||
* This uses the loader function provided via the constructor, which
|
||
* must return a Promise.
|
||
*
|
||
* @param {string} path file path
|
||
* @param {string=} desc file description for logging
|
||
*
|
||
* @return {Promise} promise of array including path and string data
|
||
*/
|
||
_loadPath( path, desc = "" )
|
||
{
|
||
this._strout( 'loadingf', desc, path );
|
||
|
||
return this._getf( path )
|
||
.then( data =>
|
||
{
|
||
this._strout( 'loadedf', path, data.length );
|
||
|
||
return [ path, data ];
|
||
} );
|
||
}
|
||
|
||
|
||
/**
|
||
* Promise to log a string identified by `id'
|
||
*
|
||
* All given arguments in `args' will be passed to the function handling
|
||
* that identifier.
|
||
*
|
||
* @param {string} id string identifier (see `_strmap')
|
||
* @param {Array} args string arguments
|
||
*
|
||
* @return {Promise}
|
||
*/
|
||
_strout( id, ...args )
|
||
{
|
||
return Promise.resolve(
|
||
this._log( this._str.apply( this, arguments ) )
|
||
);
|
||
}
|
||
|
||
|
||
/**
|
||
* Generate a string identified by `id'
|
||
*
|
||
* All given arguments in `args' will be passed to the function handling
|
||
* that identifier.
|
||
*
|
||
* @param {string} id string identifier (see `_strmap')
|
||
* @param {Array} args string arguments
|
||
*
|
||
* @return {string} generated string
|
||
*/
|
||
_str( id, ...args )
|
||
{
|
||
const strf = Bootstrap._strmap[ id ];
|
||
|
||
if ( strf === undefined ) {
|
||
throw Error( `Unknown strmap '${id}'` );
|
||
}
|
||
|
||
return strf.apply( null, args );
|
||
}
|
||
|
||
|
||
/**
|
||
* Log string using logger function
|
||
*
|
||
* @param {string} str string to log
|
||
*
|
||
* @return {undefined}
|
||
*/
|
||
_log( str )
|
||
{
|
||
this._logf( str );
|
||
}
|
||
|
||
|
||
/**
|
||
* Log error using logger function
|
||
*
|
||
* `e.message' will be used as the log string, with `e' itself being
|
||
* passed as the second argument to the logger function.
|
||
*
|
||
* @param {Error} e error
|
||
*
|
||
* @throws {Error} e
|
||
*
|
||
* @return {undefined}
|
||
*/
|
||
_error( e )
|
||
{
|
||
const str = this._str( 'fatal', e );
|
||
|
||
this._logf( str, e );
|
||
|
||
throw e;
|
||
}
|
||
|
||
|
||
/**
|
||
* Return either success or failure message given `status'
|
||
*
|
||
* @param {boolean} status success/failure indicator
|
||
*
|
||
* @return {string} success/failure message
|
||
*/
|
||
_doneMessage( status )
|
||
{
|
||
return ( status === false )
|
||
? this._str( 'fail' )
|
||
: this._str( 'ok' );
|
||
}
|
||
}
|
||
|
||
|
||
/**
|
||
* Rebirth file dependencies
|
||
*
|
||
* These are all the files (include)'d by Rebirth. This is unfortunately
|
||
* necessary because of how the filesystem abstraction works
|
||
* cross-environment, otherwise the browser would have to be blocking for
|
||
* synchronous I/O (which we do not want, as it hangs the browser).
|
||
*
|
||
* @type {Array<Array<string>>}
|
||
*/
|
||
Bootstrap._rebirthDeps = [
|
||
[ "rebirth/es.scm" ],
|
||
[ "rebirth/relibprebirth.scm" ],
|
||
[ "rebirth/macro.scm" ],
|
||
[ "rebirth/compiler.scm" ],
|
||
];
|
||
|
||
|
||
/**
|
||
* Output strings in an easily accessible map
|
||
*
|
||
* This both keeps the code a bit more easily comprehensible by removing
|
||
* large strings from procedural logic, and allows for future localization.
|
||
*
|
||
* We can do better once we get to a localization stage---Error messages
|
||
* aren't part of this map, for example.
|
||
*
|
||
* @type {string}
|
||
*/
|
||
Bootstrap._strmap = {
|
||
header: () =>
|
||
"\\\\ // \\\\\\\n" +
|
||
" \\\\ // \\\\\\\n" +
|
||
" \\\\// Ulambda \\\\\\\n" +
|
||
" \\\\\\ Scheme ///\n" +
|
||
" \\\\\\ ///\n" +
|
||
" \\\\\\ ///\n",
|
||
|
||
loadingf: ( desc, path ) =>
|
||
( desc )
|
||
? `Loading ${desc} from ${path}...`
|
||
: `Loading ${path}...`,
|
||
|
||
loadedf: ( path, len ) =>
|
||
`Loaded ${path} (len=${len}).`,
|
||
|
||
prebirthDesc: () =>
|
||
"+ Prebirth is a very basic Lisp dialect with a compiler\n" +
|
||
"+ implemented in ECMAScript. Birth is the same\n" +
|
||
"+ compiler, but re-implemented in Prebirth Lisp.",
|
||
|
||
prebirthComplete: ( len ) =>
|
||
`Birth compilation complete (len=${len}).`,
|
||
|
||
birthCompiled: () =>
|
||
"+ Birth has been compiled with Prebirth. Since Birth is\n" +
|
||
"+ a re-implementation of Prebirth, it can now be used\n" +
|
||
"+ to compile itself.",
|
||
|
||
birthSelfCompiling: () =>
|
||
"Self-compiling Birth...",
|
||
|
||
birthVerify: () =>
|
||
"Verifying self-compilation output...",
|
||
|
||
birthVerifyFail: () =>
|
||
"\n" +
|
||
"The self-compilation of Birth yielded output\n" +
|
||
"that differs from Prebirth's compilation of Birth.\n" +
|
||
"This verification step is a self-test to ensure\n" +
|
||
"consistency between the two implementations.\n\n" +
|
||
"Unfortunately, to fix this, you need to hack\n" +
|
||
"Prebirth and/or Birth. Please report a bug!",
|
||
|
||
birthVerifyOk: () =>
|
||
"Birth output matches that of Prebirth.\n" +
|
||
"+ We are now bootstrapped using a very primitive\n" +
|
||
"+ Birth Lisp. Birth can now be used to compile the\n" +
|
||
"+ next generation of bootstrap compilers, Rebirth.",
|
||
|
||
rebirthCompiling: n =>
|
||
"Compiling Re" + Bootstrap._supmap[ n ] + "birth...",
|
||
|
||
rebirthCompiled: ( n, len ) =>
|
||
( n > 1 ) ? `Compilation complete (len=${len}).` :
|
||
`+ The first generation of Rebirth (Re¹birth) has been\n` +
|
||
`+ compiled using Birth (len=${len}). The next step is\n` +
|
||
`+ to have Re¹birth build itself, producing Re²birth.\n` +
|
||
`+ This will repeat, each time producing a compiler with\n` +
|
||
`+ additional features capable of compiling the next\n` +
|
||
`+ generation. This process will end once two\n` +
|
||
`+ consecutive generations yield identical output.`,
|
||
|
||
rebirthDone: n =>
|
||
"+ Rebirth stopped changing after Re" + Bootstrap._supmap[ n ] +
|
||
"birth, so that\n" +
|
||
"+ generation will serve as our final one. We will now\n" +
|
||
"+ use it to compile and run a primitive test suite that\n" +
|
||
"+ will determine its viability (whether it might be able\n" +
|
||
"+ to compile Ulambda). Running a test suite will allow\n" +
|
||
"+ us to clearly see any problems that may exist.",
|
||
|
||
rebirthTestCompiling: () =>
|
||
"Compiling Rebirth Viability Test...",
|
||
|
||
rebirthTestCompiled: len =>
|
||
`Compilation complete (len=${len}).`,
|
||
|
||
rebirthTestFailed: () =>
|
||
"+ Rebirth failed its test suite! This means that it is\n" +
|
||
"+ likely not suitable for compiling Ulambda, and so we\n" +
|
||
"+ cannot proceed with bootstrapping. If you are hacking\n" +
|
||
"+ the bootstrap process, the above failures will give you\n" +
|
||
"+ useful information; otherwise, please report this bug\n" +
|
||
"+ so that someone can help to fix it for you. Bummer.",
|
||
|
||
rebirthTestDone: () =>
|
||
"+ Rebirth appears to be a viable candidate! The last\n" +
|
||
"+ step is to use it to compile Ulambda.",
|
||
|
||
fatal: ( e ) =>
|
||
"\n\n!!! " + e.toString() + "\n\n" +
|
||
"Something has gone terribly wrong!\n" +
|
||
"See the console for a stack trace.\n\n",
|
||
|
||
ok: () =>
|
||
"Bootstrap successful (but not yet complete)!",
|
||
|
||
fail: () =>
|
||
"Bootstrap failed.",
|
||
};
|
||
|
||
|
||
/**
|
||
* Map of number to Unicode superscript
|
||
*
|
||
* This may be implemented as either a string or an array; the notation
|
||
* _supmap[n] will work the same in either case.
|
||
*
|
||
* @type {string}
|
||
*/
|
||
Bootstrap._supmap = "⁰¹²³⁴⁵⁶⁷⁸⁹";
|
||
|
||
|
||
// for use in a CommonJS (e.g. Node.js) environment
|
||
if ( typeof module !== 'undefined' ) {
|
||
module.exports = Bootstrap;
|
||
}
|