bootOS VS sectorlisp

wow, this is impressive.

I wrote a similar x86-16 assembler in < 512 B of x86-16 assembly, and this seems much more difficult <https://github.com/kvakil/0asm/>. I did find a lot of similar tricks were helpful: using gadgets and hashes. Once trick I don't see in sectorc which shaved quite a bit off of 0asm was self-modifying code, which 0asm uses to "change" to the second-pass of the assembler. (I wrote some other techniques here: <https://kvakil.me/posts/asmkoan.html>.)

bootOS (<https://github.com/nanochess/bootOS>) and other tools by the author are also amazing works of assembly golf.

I'm glad you enjoyed it! Have you tried running it?

One could reasonably argue that SKF isn't really "booting" on an old 386 PC; though it'll probably run on one, you need to get Linux running on the PC first, because SKF can't read the input source code from disk or write the output executable to disk on its own, and it needs something to load it into memory and start it running as well. And, unlike real Forths, it's a batch-mode compiler: it can't be used interactively. The sense in which it's a "tiny bootstrap" is that it's a compiler that compiles itself, not the sense of "bootstrapping" that means to load oneself into RAM.

— ⁂ —

In 02007 I wrote https://github.com/kragen/tokthr as an investigation into precisely the question of "just how small a fully functional Forth environment could be packed". By using bytecode ("token threading") rather than DTC or ITC, tokthr provides "90% of" a traditional interactive Forth environment in about 1400 bytes, all bytecode except for a 239-byte machine-code core. Unfortunately, because it's incomplete, it's impossible to know whether the remaining 10% of the functionality requires adding another 10% to the code or another 90%—as in the old joke about how the first 90% of the project takes the first 90% of the schedule, and the remaining 10% takes the other 90%.

My best guess, though, is that it'd be about 1700 bytes, so in 2KiB you'd have about 350 bytes left for the user program, which is probably about 64–128 lines of code. Interpretation can be slow, but it sure makes for denser code, and you don't need to have two copies of the interpreted code in RAM when you're bootstrapping.

There have definitely been 8KiB interactive Forth systems, and I think there have been 4KiB ones, which was also the size Wozniak required for a BASIC interpreter on the Apple. tokthr suggests that 2KiB might be achievable for a stripped-down Forth.

Óscar Toledo G.'s bootOS https://github.com/nanochess/bootOS is a particularly interesting non-Forth system in this OS/IDE/debugger vein, because it has enough functionality to write programs (in hexadecimal machine code), load them from disk, edit them, and save them, all in 512 bytes of code. It does require somewhat more than 512 bytes of RAM, but still very little—much less than has ever been present on a machine that it could run on.

— ⁂ —

My thinking on Forth, which is something I'm an amateur at, has changed a little bit since I wrote tokthr and SKF. I think that if you evaluate Forth as a programming language, it's generally going to look pretty deficient. It's more bug-prone and harder to read than alternatives like C, Lisp, BASIC, or assembly language, although it does support compile-time metaprogramming and powerful abstraction facilities.

But if you ask the question, "What's the simplest usable development environment I can build?" the answer starts to look a lot like Forth, especially if you're running on a poorly characterized piece of hardware where you need to prioritize interactive experimentation with I/O ports. It gives you an interactive, scriptable environment for poking around, similar to what Tcl gives you https://yosefk.com/blog/i-cant-believe-im-praising-tcl.html but in 4 kilobytes rather than the megabyte and a half Tcl demands. And the environment includes not just a scriptable command line and the usual programming-language things like arithmetic, subroutines, variables, and arrays, but also compile-time metaprogramming, virtual memory, an editor that allows you to recompile code at screenful granularity (usually), a memory dumper, access to raw hardware devices, an assembler (usually), sometimes multithreading, and a sort of debugger.

As in BASIC or Lisp or Python or Tcl, your UI is a REPL, so your programming language is also your command language; but, unlike in BASIC, your command language is extensible, so in many cases it can also work as the user interface to your application.

In BASIC or in a C debugger you number the lines of code in your program; in Forth you name them, so you can "single-step" your program by running them one at a time. Then the ? word gives you a quick way to examine your variable values interactively, again as in a debugger. Like, here's me trying to interactively debug a square-root routine into existence in GForth on Linux:

    variable square variable guess  ok

He also wrote bootOS, "a monolithic operating system in 512 bytes of x86 machine code."

https://github.com/nanochess/bootOS

I'm assuming you are referring to https://github.com/jart/sectorlisp which I gather is an attempt to make a Lisp that fits in a disk boot sector?

I think SIMD was a distraction to our conversation, most code doesn't use it and in the future the length agnostic, flexible vectors; https://github.com/WebAssembly/flexible-vectors/blob/master/... are a better solution. They are a lot like RVV; https://github.com/riscv/riscv-v-spec, research around vector processing is why RISC-V exists in the first place!

I was trying to find the smallest Rust Wasm interpreters I could find, I should have read the source first, I only really use wasmtime, but this one looks very interesting, zero deps, zero unsafe.

16.5kloc of Rust https://github.com/rhysd/wain

The most complete wasm env for small devices is wasm3

20kloc of C https://github.com/wasm3/wasm3

I get what you are saying as to be so small that there isn't a place of bugs to hide.

> “There are two ways of constructing a software design: One way is to make it so simple that there are obviously no deficiencies, and the other way is to make it so complicated that there are no obvious deficiencies. The first method is far more difficult.” CAR Hoare

Even a 100 line program can't be guaranteed to be free of bugs. These programs need embedded tests to ensure that the layer below them is functioning as intended. They cannot and should not run open loop. Speaking of 300+ reimplementations, I am sure that RISC-V has already exceeded that. The smallest readable implementation is like 200 lines of code; https://github.com/BrunoLevy/learn-fpga/blob/master/FemtoRV/...

I don't think Wasm suffers from the base extension issue you bring up. It will get larger, but 1.0 has the right algebraic properties to be useful forever. Wasm does require an environment, for archival purposes that environment should be written in Wasm, with api for instantiating more envs passed into the first env. There are two solutions to the Wasm generating and calling Wasm problem. First would be a trampoline, where one returns Wasm from the first Wasm program which is then re-instantiated by the outer env. The other would be to pass in the api to create new Wasm envs over existing memory buffers.

See, https://copy.sh/v86/

MS-DOS, NES or C64 are useful for archival purposes because they are dead, frozen in time along with a large corpus of software. But there is a ton of complexity in implementing those systems with enough fidelity to run software.

Lua, Typed Assembly; https://en.wikipedia.org/wiki/Typed_assembly_language and Sector Lisp; https://github.com/jart/sectorlisp seem to have the right minimalism and compactness for archival purposes. Maybe it is sectorlisp+rv32+wasm.

If there are directions you would like Wasm to go, I really recommend attending the Wasm CG meetings.

https://github.com/WebAssembly/meetings

When it comes to an archival system, I'd like it to be able to run anything from an era, not just specially crafted binaries. I think Wasm meets that goal.

https://gist.github.com/dabeaz/7d8838b54dba5006c58a40fc28da9...

Based on this, the next thing you wrote, and your reference to running a minimal Gentoo: I think you might be a Scheme fan in the making. Scheme is the minimal Lisp. (Okay, that might be sectorlisp which fits in 512 bytes.) It’s hands down my favorite language. While it’s evolved on its own to be more of a superset of Scheme, Racket is my Scheme of choice.

sectorlisp