This paper is a major contribution to digital archival. I'm embarrassed that I hadn't read it until now. Thanks, HN!
I've been thinking a lot about how to solve this problem myself.
Kay says their Smalltalk virtual machine for the 8086 was 6 kilobytes of machine code; I think we can do several times better than that. The most recent BF interpreter I wrote, in 2014, http://canonical.org/~kragen/sw/aspmisc/brainfuck.c, is a bit over a page of code, and with -Os, it compiles to 863 bytes of i386 code (768 bytes .text, 38 bytes .init, 23 bytes .fini, 34 bytes .rodata). Maybe the ideal archival architecture would take a little more code than BF to interpret, because an actually efficient BF implementation has to do all kinds of somewhat unpredictable optimizations.
Another would be a simple register machine, something like the PIC; also in 2014, I wrote a proposal for a nearly-MOV-machine version called "dontmove" at http://canonical.org/~kragen/sw/aspmisc/dontmove.md. The C implementation at http://canonical.org/~kragen/sw/aspmisc/dontmove.c compiles to 855 bytes of i386 machine code (38 .init, 784 .text, 23 .fini, 10 .rodata) and is dramatically more efficient than a simple BF implementation, and unlike BF, it has features like memory indexing and subroutine calls; but it's not as well tested.
Each of BF and Dontmove took me about half an hour to implement. Even though a simple Dontmove implementation is exponentially faster than a simple BF implementation, it's still orders of magnitude slower than native code. I'm still exploring how to better bridge that gap; ideally implementing the virtual machine wouldn't take the entire afternoon that is the goal of Chifir, and it wouldn't run as slow as Chifir. I suspect that some kind of SIMT architecture (like GLSL and GPUs in general) might be the right path, allowing a simple emulator to amortize interpretation overhead over many lanes of data. I expect Alan would be allergic to this idea.
As mentioned in the Cuneiform paper, Lorie and van der Hoeven have published some papers on what they call a Universal Virtual Computer, directed at archival, but unfortunately some of the design decisions in the UVC run strongly counter to the goal of ensuring that from-scratch implementations have a good chance of being compatible: bignum registers, for example, and complicated fundamental operations like float division. The consequence is that writing emulators to run on the UVC should be very easy, but no two implementations of the UVC will be compatible, so those emulators will not run successfully on new implementations of the UVC written after we are all dead.
An issue barely mentioned in this paper is I/O devices. You'll note, for example, that Chifir has no mouse and no real-time clock, although it does have a keyboard and a framebuffer; its keyboard interface is somewhat underspecified but appears to lack control, alt, or other similar modifier keys, and there are no key-release events, and as abecedarius points out, reading the keyboard is blocking. This means that it will be impossible to write simple video games for Chifir that move your guy only as long as you hold down a key, and the lack of a real-time clock means that it can't do animations at a constant speed. It's likely that the specification and implementation of I/O devices for an archival virtual machine will require as much effort as that of the CPU.
I've been thinking a lot about how to solve this problem myself.
Kay says their Smalltalk virtual machine for the 8086 was 6 kilobytes of machine code; I think we can do several times better than that. The most recent BF interpreter I wrote, in 2014, http://canonical.org/~kragen/sw/aspmisc/brainfuck.c, is a bit over a page of code, and with -Os, it compiles to 863 bytes of i386 code (768 bytes .text, 38 bytes .init, 23 bytes .fini, 34 bytes .rodata). Maybe the ideal archival architecture would take a little more code than BF to interpret, because an actually efficient BF implementation has to do all kinds of somewhat unpredictable optimizations.
Some kind of Forth machine, like Calculus Vaporis https://github.com/kragen/calculusvaporis, is one possibility.
Another would be a simple register machine, something like the PIC; also in 2014, I wrote a proposal for a nearly-MOV-machine version called "dontmove" at http://canonical.org/~kragen/sw/aspmisc/dontmove.md. The C implementation at http://canonical.org/~kragen/sw/aspmisc/dontmove.c compiles to 855 bytes of i386 machine code (38 .init, 784 .text, 23 .fini, 10 .rodata) and is dramatically more efficient than a simple BF implementation, and unlike BF, it has features like memory indexing and subroutine calls; but it's not as well tested.
Each of BF and Dontmove took me about half an hour to implement. Even though a simple Dontmove implementation is exponentially faster than a simple BF implementation, it's still orders of magnitude slower than native code. I'm still exploring how to better bridge that gap; ideally implementing the virtual machine wouldn't take the entire afternoon that is the goal of Chifir, and it wouldn't run as slow as Chifir. I suspect that some kind of SIMT architecture (like GLSL and GPUs in general) might be the right path, allowing a simple emulator to amortize interpretation overhead over many lanes of data. I expect Alan would be allergic to this idea.
As mentioned in the Cuneiform paper, Lorie and van der Hoeven have published some papers on what they call a Universal Virtual Computer, directed at archival, but unfortunately some of the design decisions in the UVC run strongly counter to the goal of ensuring that from-scratch implementations have a good chance of being compatible: bignum registers, for example, and complicated fundamental operations like float division. The consequence is that writing emulators to run on the UVC should be very easy, but no two implementations of the UVC will be compatible, so those emulators will not run successfully on new implementations of the UVC written after we are all dead.
An issue barely mentioned in this paper is I/O devices. You'll note, for example, that Chifir has no mouse and no real-time clock, although it does have a keyboard and a framebuffer; its keyboard interface is somewhat underspecified but appears to lack control, alt, or other similar modifier keys, and there are no key-release events, and as abecedarius points out, reading the keyboard is blocking. This means that it will be impossible to write simple video games for Chifir that move your guy only as long as you hold down a key, and the lack of a real-time clock means that it can't do animations at a constant speed. It's likely that the specification and implementation of I/O devices for an archival virtual machine will require as much effort as that of the CPU.