A virtual machine

Emulation is the reproduction of the behavior of a physical computer's circuitry with software. Given that an emulator can translate the actions of one computer onto an other, the same program can sometimes be used on both.

Virtual Machines are software emulating the actions of real and imaginary computers. Someone could devise a fictional computer that is not necessarily based on existing hardware, write software for this fantastical computer, implement an emulator for it, and use the same program across vastly different systems via an emulator.

Over the years, I wrote software for a multitude of peripherals and frameworks, the vast majority is now defunct due to either falling behind on the ever-changing toolchains or simply the hardware being discontinued. Perhaps it's just a matter of time until people build emulators to make these projects usable again, otherwise these projects were never truly mine, and my learning of these languages only ever belonged to the platforms.

I. An Adequate Number Of Bits

During my research into portability, I kept thinking about how frictionless it is to play classic console games today. Pulling on that thread led me to projects designed explicitly for virtual machines, such as Another World which is equally easy to play today due to its targeting of a portable virtual machine, instead of any ever-changing physical hardware.

For a time, I thought I ought to be building software for the NES to ensure its survival against the wave of disposable modern platforms — So, I did. Unfortunately, most of the software that I care to write and use require slightly more than an 8-button controller, namely a keyboard and a pointing device.

II. Tarpits & Houses Of Cards

If the focus of this experiment is to ensure the support of a piece of code by writing emulation software for each new platform, the specifications should be painless to implement.

Let's use the time one would need to write a passable emulator as a limit in complexity for this system. Could a computer science student implement an emulation of the 6502 instructions in an afternoon? Could that design be simplified, changed in some way to make it more approachable for would-be implementers?

• Smalltalk is a complete computing environment and virtual machine, that was said to take about a year for one person to implement.
• Lisp(tal) is a fully featured symbolic functional architecture that takes about a month to implement. It comes with the complexities of garbage collection, extensive memory usage, and endless edge cases.
• Brainfuck(tal) is a 8-Instructions architecture taking at most an afternoon for one person to implement. What it does away in emulation complexity, it offloads onto the toolchain needed to make programs fast and writing them a pleasant experience.
• Subleq(tal) is a 1-Instruction architecture taking at most an hour for one person to implement. Similar tarpit to brainfuck, only moreso.

So, let's set a limit to the complexity of the system to a week, since it would be an equally Herculean task to build an emulator and assembler for a machine with thousands of instructions; or a single instruction machine building abstract logic from thousands of primitive parts.

III. Things Betwixt

In 1977, a programmer created the CHIP-8 virtual machine with 36 instructions, 16 registers and 4096 bytes of memory. It had no mouse device, its controller is 16 keys organized in a square, the screen is barely capable of displaying readable text, but I was able to write an implementation in a weekend.

In 1964, a computer scientist proposed the SECD abstract machine with 10 instructions and 4 stacks. The superficially documented implementation specifies a list processing system capable or hosting functional languages. The system was later expanded with arithmetic and IO operations, but rests on an intricate and inefficient garbage collected system. I was able to write an implementation in about two weeks.

In the early 1980s , when computer access was still not yet widespread, a paper computer was designed, consisting of a piece of paper with 21 lines of code and eight registers. The instruction set of five commands(inc, dec, jmp, isz, stp) is small but Turing complete, meaning that it can approximately simulate the computational aspects of any other real-world general-purpose computer, and is therefore enough to represent all mathematical functions.

Somewhere along this voyage into finding a suitable host for my programs, I began thinking about electronic waste, and I couldn't justify surrounding myself with yet more electronics.

This dream platform would therefore be designed to be emulated, its complexity would be designed around the complexity of software and not that of hardware, so I do no consider FPGAs.

IV. Back & Forth

The balancing act of virtual machine instructions, assembler, emulator and the resulting capabilities of its language eventually brought me back to stack machines.

Concatenative languages consist of breaking a program into a list of words, and to interpret each word, words are often combinations of other words, combined to create more complex words. Brackets and parentheses are unnecessary: the program merely performs calculations in the order that is required, letting the automatic stack store intermediate results on the fly for later use. Likewise, there is no requirement for precedence rules.

In Forth, memory is made of blocks of cells, which are typically 16-bits in length, meaning that each piece of data is a number from 0 to 65535. For this specific imaginary system, I wanted the memory to consist of cells of 8-bit, or numbers from 0 to 255. For example, the 12 / (34 - 12) sequence is equivalent to the 6 bytes:

uxntal |  #  12  34 OVR SUB DIV
binary | a0  12  34  07  19  1b

In order words to keep the assembly programming pleasant and fend off the need to abstract computation to a high-level language, I've combined a few stack-machine operations, arithmetic, bitwise functions and reached an expressive virtual machine that can be implemented in a weekend running at a reasonable speed. An emulator capable of running the self-hosted assembler is about 150 lines of C.

   Stack I                Logic                  Memory I               Arithmetic
00 BRK --              08 EQU a b -- a=b      10 LDZ abs8 -- [abs]   18 ADD a b -- a+b
01 INC a -- a+1        09 NEQ a b -- a≠b      11 STZ val abs8 --     19 SUB a b -- a-b
02 POP a --            0a GTH a b -- a>b      12 LDR rel8 -- [rel]   1a MUL a b -- a×b
03 NIP a b -- b        0b LTH a b -- a<b      13 STR val rel8 --     1b DIV a b -- a÷b

   Stack II               Stash                  Memory II              Bitwise
04 SWP a b -- b a      0c JMP addr --         14 LDA abs16 -- [abs]  1c AND a b -- a&b
05 ROT a b c -- b c a  0d JCN cond8 addr --   15 STA val abs16 --    1d ORA a b -- a|b
06 DUP a -- a a        0e JSR addr -- . pc16  16 DEI dev -- [dev]    1e EOR a b -- a^b
07 OVR a b -- a b a    0f STH a -- . a        17 DEO val dev --      1f SFT a hl8 -- res>>l<<h

   Immediate
00 BRK --              20 JCI cond8 --        40 JMI --              60 JSI -- . pc16
80 LIT -- [pc]8        a0 LIT2 -- [pc]16      c0 LITr -- . [pc]8     e0 LIT2r -- . [pc]16

Its documentation encourages re-implementation instead of adoption of a specific implementation. It operates on bytes as to remain portable on small systems, abstracting I/O entirely to the host system via dedicated opcodes. For it to work as an Archival Computer, it must remain completely detached from dependencies, and highly discoverable for future generation:

• Frozen Specification: Uxn is implicitly frozen at 0 Kelvin, it can be implemented in a hundred lines in most languages.
• Zero Dependencies: The toolchain is entirely bootstrappable, no dependency on host OS semantics beyond I/O abstraction.
• Minimal Conventions: Varvara is the current baseline specification, but is not frozen.
• Archival Format Contract: Uxntal has a standard for ROM metadata, but is not frozen.
• Operational Correctness: Opctest is an extensive test suite that validates every single opcode, passing the test yields a compatible implementation. Correctness is defined operationally, Uxn has no undefined behaviors and cannot error.
• Independent Redundancy: Uxn, by way of Varvara, has open source emulation for dozens of architectures already.
• Artifact friendliness: Deterministic execution model is inspectable step-by-step, accessible symbol files.
• Cultural Preservation Efforts: The ecosystem features its own sign-language and glyph system, but currently lacks multilingual documentation.

incoming: devlog 2022