diff options
Diffstat (limited to 'README.txt')
| -rw-r--r-- | README.txt | 198 |
1 files changed, 140 insertions, 58 deletions
diff --git a/README.txt b/README.txt index 3ed4635..54c2a2c 100644 --- a/README.txt +++ b/README.txt @@ -9,23 +9,50 @@ ~~~~~~~~~~~~~~ ~~~~~~~~~~~~~~~ - The documentation is a work in progress. It doesn't say most of the things -it needs to, yet. - Evocation is a dialect of Forth, grown to Irenes' tastes. It is meant to someday be a platform for experimenting with parse theory, type theory, databases, and other things Forth is not traditionally known for, as well as with language design, which it is. It is a self-hosting compiler, meaning the -only thing you need to build it is a copy of itself. +only thing you need to build it is a copy of itself. It is written entirely +without the aid of differentiable neural networks in any capacity, and always +will be. + + Evocation has practical utility, but the primary reason for making it is +spiritual and aesthetic: Irenes believe it is a thing that should exist, and +chose to create it in the most enjoyable way they could find. At present, Evocation targets only one architecture, amd64. It is rare among compiled Forths in that it targets a 64-bit architecture. - Someday, Evocation will also be self-bootstrapping, meaning that it will be -able to "compile" itself into a commented hex dump of itself for ease of -auditing. This rests on the insight, from the mescc and guix developers, that -the difference between source code and binary is comments. The efforts in this -direction are described below under "Hexing Evocation for Distribution". + In addition to being self-hosting, Evocation is also self-bootstrapping, +meaning that the compiler can run in a special "show your work" mode which, +instead of a regular binary, outputs a commented hex dump which is heavily +instrumented with explanations of the provenance of every single byte of ouput +and how to audit that it is correct. This hex dump is suitable for checking +into source control, and can then be converted to a binary executable through +a process that is itself straightfoward to audit. + + This hex-dump strategy rests on the insight, from the mescc and guix +developers, that the difference between source code and binary is comments. +However, to Irenes' knowledge, Evocation is the first compiler to be able to +generate this hex dump of itself from an implementation in a high-level +language, rather than an assembly language. Thus the coinage of the term +"self-bootstrapping" to describe it. + + Those not familiar with Ken Thompson's classic paper on this topic[1] will +find it a short, lighthearted read which provides the motivation for this type +of bootstrapping. + + The details of how the bootstrapping is used are described below under +"Hexing Evocation for Distribution". + + This documentation is a perpetual work in progress, but it's getting closer +to being a viable introduction. Please do weigh in on things you wish it +talked about but doesn't. + + If you've obtained this code repository without a link, its authoritative +copy is at https://code.irenes.space/evocation - but there's no need to hit +the network; everything you need should already be in this directory. ~~~~~~~~~~~~ @@ -34,29 +61,31 @@ direction are described below under "Hexing Evocation for Distribution". Since we have chosen not to distribute Evocation in binary form, you don't have a copy of it yet and cannot take advantage of its self-hosting properties -for your first-ever version. Happily, until the self-bootstrapping properties -are ready, we have maintained compatibility with the original version of -Evocation which was written in a program called flatassembler, which you will -have to acquire. - -TODO mention the terminal +for your first-ever version. Happily, because it is also self-bootstrapping, +you don't need to. Simply run: - To get started, first build the flatassembler version: + $ ./hex < evoke.hex > evoke + $ chmod 755 evoke - $ fasmg quine.asm quine - $ chmod 755 quine + These are Unix shell commands, which need to be run in a command terminal +of some sort. If you're running Linux or another Unix variant, you probably +already have a program that gives you a terminal; there are many to choose +from. On other OSes, you may need to go find one. Using the terminal may be +scary at first, but once it becomes familiar it is a very deep creative tool +that changes how you relate to computers. We promise to be gentle about not +demanding too much proficiency, too quickly. - It's called "quine" for historical, sentimental reasons having to do with -the original architecture. It is not a Quine, in the sense that it is not a -program that outputs its own source. When the self-bootstrapping is done, it -will be moved to a historical subdirectory and this misnomer will no longer -matter. + If you need to learn about the terminal, you may enjoy the Fujoshi Guide to +Web Development[2] or the Wizard Zines[3]. - This "quine" binary is a working Evocation interpreter, but it's incomplete -and will become more so with time. So, next, build Evocation-in-Evocation: + This tiny program "hex" has been checked into git as a binary, and is the +root of trust for everything Evocation does. It is the only binary component. +If you wish, you may inspect its contents by any means you wish and compare +them to the bootstrapped hex dump of "hex" itself, in the file "hex.hex", +which describes the purpose and provenance of every byte. It's short. - $ (cat labels.e elf.e transform.e execution.e; echo 's" pyrzqxgl" allocate-string dup 262144 read-to-buffer'; cat core.e linux.e output.e amd64.e execution-support.e log-load.e; echo pyrzqxgl swap 262144 read-to-buffer; cat core.e linux.e output.e amd64.e execution-support.e log-load.e dynamic.e input.e interpret.e flow-control.e linux-dynamic.e ; echo pyrzqxgl; cat evoke.e) | ./quine > evoke - $ chmod 755 evoke + It's a significantly larger undertaking, but if you have sufficient reason +to, you can audit the contents of "evoke.hex" in the same way. Now keep your "evoke" binary somewhere safe, and use it to build new versions as you modify Evocation. @@ -232,17 +261,37 @@ built-in library. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ There may come a point in your explorations when you wish to make changes to -the compiler. When doing so, please always make sure to build -Evocation-in-Evocation both via Evocation-from-flatassembler, as described in -"Building" above, and with itself, like this: +the compiler. When you have a change you want to try it out, you can use your +existing copy of Evocation to compile a new one, like this: $ (cat labels.e elf.e transform.e execution.e; echo 's" pyrzqxgl" allocate-string dup 262144 read-to-buffer'; cat core.e linux.e output.e amd64.e execution-support.e log-load.e; echo pyrzqxgl swap 262144 read-to-buffer; cat core.e linux.e output.e amd64.e execution-support.e log-load.e dynamic.e input.e interpret.e flow-control.e linux-dynamic.e ; echo pyrzqxgl; cat evoke.e) | ./evoke > evoke2 $ chmod 755 evoke2 - The two versions evoke and evoke2 should be bytewise identical; if they are -not, please fix that. This is an important property which would be very -difficult to get back if we ever lose it, it's easier to maintain it -in-the-moment. + You can then run ./evoke2 and try out the new features you added. Fun, +right? :) + + If you're planning to submit your changes for inclusion, please also verify +that your compiled output is stable: Run the compilation command again but +change the last part from "./evoke > evoke2" to "./evoke2 > evoke3". The two +versions evoke2 and evoke3 should be bytewise identical; if they are not, +please fix that. This is an important property which would be very difficult +to get back if we ever lose it, it's easier to maintain it in-the-moment. + + For learning about operating system internals and discovering more reference +material, Irenes recommend the osdev wiki[4]. In particular, Evocation's +executable format is ELF[5] in its the 64-bit version[6]; its interface with +the kernel is the System V ABI[7] in its AMD64 version[8]; and the Intel +processor reference manual[9] was consulted heavily for understanding the +instruction set architecture. + + If you want to learn more about Forth implementation in particular, check +out Jonesforth[10]. If you want to see a different creative direction a modern +Forth dialect has gone in, look at Factor[11]. If you're interested in +concatenative languages other than Forth, check out the uxn VM[12] and its +language uxntal[13]. + + Irenes sadly do not have recommendations for learning about compiler +concepts. ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ @@ -273,14 +322,13 @@ than necessary; many of those bytes are used for error message strings, on the principle that it's very important that it be easy to distinguish a successful invocation of "hex" from a failed one. - Although the hex transform is not yet fully the compiled "hex" has proven -quite stable, and the hex transform does work on it. So, a copy of the -compiled "hex" is checked into source control so that it can serve as a root -of trust for future Evocation builds. For ease of auditing, a commented hex -dump version of this binary, produced via the hex transform, is also checked -in, as "hex.hex" (We heard you liked metacircularity, so we put some -metacircularity in your metacircularity so you can be metacircular while -you're metacircular.) + The compiled "hex" has proven quite stable, and the hex transform does work +on it. So, a copy of the compiled "hex" is checked into source control so that +it can serve as a root of trust for all Evocation builds. For ease of +auditing, a commented hex dump version of this binary, produced via the hex +transform, is also checked in, as "hex.hex" (We heard you liked +metacircularity, so we put some metacircularity in your metacircularity so you +can be metacircular while you're metacircular.) If you need to compile "hex", you can do so as follows: @@ -291,29 +339,63 @@ you're metacircular.) $ (cat labels.e elf.e transform.e; echo 's" xyzzy" allocate-string dup 262144 read-to-buffer'; cat core.e linux.e output.e amd64.e execution-support.e log-load.e dynamic.e input.e interpret.e flow-control.e linux-dynamic.e labels.e elf.e hex.e; echo 'xyzzy s" hex-source" variable 1024 1024 * allocate s" hex-binary" variable 1024 1024 * allocate s" hex-metadata" variable hex-metadata hex-binary dup hex-source 5 roll hex-transform bye ' ) | ./evoke > hex.hex - Although the hex transform doesn't yet work on Forth programs (only programs -written in Evocation-assembly), if you intend to play around with this you may -wish to know how to attempt to run it on things. The latest draft way to do -that is: + The program "hex" is written in Evocation-assembly, but the hex transform +also works on Forth programs, including Evocation itself. To produce the +hex-dump version of Evocation, do: - $ (cat labels.e elf.e transform.e; echo 's" xyzzy" allocate-string dup 1048576 read-to-buffer'; cat core.e linux.e output.e amd64.e execution-support.e log-load.e dynamic.e input.e interpret.e flow-control.e linux-dynamic.e labels.e elf.e transform.e execution.e; echo 's" pyrzqxgl" allocate-string dup 262144 read-to-buffer '; cat core.e linux.e output.e amd64.e execution-support.e log-load.e; echo pyrzqxgl swap 262144 read-to-buffer; cat core.e linux.e output.e amd64.e execution-support.e log-load.e dynamic.e input.e interpret.e flow-control.e linux-dynamic.e; echo pyrzqxgl; cat evoke.e; echo 'xyzzy s" evoke-source" variable 1024 1024 2 * * allocate s" evoke-binary" variable 1024 1024 4 * * allocate s" evoke-metadata" variable evoke-metadata evoke-binary dup evoke-source 5 roll hex-transform bye ' ) | ./evoke > evoke.hex + $ (cat labels.e elf.e transform.e; echo 's" xyzzy" allocate-string dup 1048576 read-to-buffer'; cat core.e linux.e output.e amd64.e execution-support.e log-load.e dynamic.e input.e interpret.e flow-control.e linux-dynamic.e labels.e elf.e transform.e execution.e; echo 's" pyrzqxgl" allocate-string dup 262144 read-to-buffer '; cat core.e linux.e output.e amd64.e execution-support.e log-load.e; echo pyrzqxgl swap 262144 read-to-buffer; cat core.e linux.e output.e amd64.e execution-support.e log-load.e dynamic.e input.e interpret.e flow-control.e linux-dynamic.e; echo pyrzqxgl; cat evoke.e; echo 'xyzzy s" evoke-source" variable 1024 1024 4 * * allocate s" evoke-binary" variable 1024 1024 4 * * allocate s" evoke-metadata" variable evoke-metadata evoke-binary dup evoke-source 5 roll hex-transform bye ' ) | ./evoke > evoke.hex - It should run to completion, producing output. The output is even correct in -the sense that passing evoke.hex through ./hex will give a binary that's -byte-for-byte identical to evoke, but the output has various problems such as -displaying assembly parameters in the wrong order, having insufficient -explanation of label references and definitions, not showing dictionary entry -headers in any special way, and so on. All these cosmetic issues should be -fixable now, and should likely be the focus of any development efforts. + It should run to completion, producing output in evoke.hex. Passing +evoke.hex through ./hex will give a binary that's byte-for-byte identical to +evoke. - It also takes several minutes to run, which Irenes believe is because of the -use of linked lists rather than hash tables for the various dictionaries. -Adding a hash table is a task to do after bootstrapping is complete. + This does take several minutes to run (as many as ten, as of this writing), +but the cause is known: The metadata output buffer is stored in a way that +requires linear traversal for several operations. This dominates the runtime; +when it is fixed, the largest remaining cost will be the use of linked lists +rather than hash tables for the various dictionaries. These are both tasks to +do in the near future, now that bootstrapping is complete. Nearly all of this runtime is attributable to the log-load transform; if you're working on something that doesn't involve the log-load transform, you may find it useful to temporarily comment out the call to log-load-transform -in execution.e, replacing it with two invocations of drop. +in execution.e, replacing it with two invocations of drop. This will not +produce a working compiler, but it will finish faster. Now get debugging! :) + + ~~~~~~~~~~~~~~ +~~ References ~~ + ~~~~~~~~~~~~~~ + + When you read something you enjoy, you should always check its list of +references to discover other stuff you might like. In graduate school they'll +teach you that reading citations is a great way to find out about things, but +here, you just got the lesson for free! + +[1] Ken Thompson, "Reflections on Trusting Trust" + https://doi.org/10.1145/358198.358210 +[2] "The Fujoshi Guide to Web Development" + https://www.fujoweb.dev/ +[3] Julia Evans, "wizard zines" + https://wizardzines.com/ +[4] osdev wiki + https://wiki.osdev.org/ +[5] "Tool Interface Standard (TIS) Executable and Linking Format (ELF) + Specification", version 1.2. + https://refspecs.linuxfoundation.org/elf/elf.pdf +[6] "ELF-64 Object File Format", version 1.5 draft 2. + https://uclibc.org/docs/elf-64-gen.pdf +[7] "System V Application Binary Interface" + https://www.sco.com/developers/devspecs/gabi41.pdf +[8] "System V Application Binary Interface AMD64 Architecutre Processor + Supplement", version 1.0. + https://gitlab.com/x86-psABIs/x86-64-ABI/ +[9] "Intel 64 and IA-32 Architectures Software Developer's Manual" + https://www.intel.com/content/www/us/en/developer/articles/technical/intel-sdm.html +[10] https://github.com/nornagon/jonesforth/ +[11] https://factorcode.org/ +[12] https://100r.co/site/uxn.html +[13] https://wiki.xxiivv.com/site/uxntal.html + |