(2025-06-01) A VM so tiny that it even fits on a HP 12C
-------------------------------------------------------
Picture this. It's 1983, the year before the year of our Lord Orwell, and you
are a 7-to-12-year-old kid living in a rather developed country who just 
found out that personal computers already exist and are spreading across 
homes. Of course, your family quickly lets you know that not only a home PC, 
but even a portable BASIC one with a single-line screen or a mere 
programmable calculator is something prohibitively expensive to buy for 
someone as young as you. But you still wanna learn at least something about 
computers as your bright and fresh mind (rightfully) sees them as the future 
of technology. You don't miss any tech-related TV shows in the time free 
from school and homework. When suddenly... You see a solution to your 
dilemma demonstrated right on one of those shows: a working computer model 
that fits on a sheet of paper. You quickly grab a pencil and a sheet of 
paper, redraw what they show on the TV screen, note the set of five very 
simple instructions and finally start writing your own programs. You enjoy 
the process even though you have to execute every step by yourself. Believe 
it or not, this is how a lot of German children got into programming in 
1983, when "Der Know-How Computer" had been demonstrated in the WDR 
Computerclub TV show.

What personally fascinated me when I read about this educational project was
the fact that, despite the original worksheet (a printable version of which 
was created around the same time and distributed in over 400000 copies 
across the entire (West) Germany) was pretty limited to its 21 program steps 
and 8 registers, the instruction set itself was proven to be 
Turing-complete, which means that, in theory, given enough steps and 
registers, it can do any arbitrarily complex computation. And it's just five 
instructions we're talking about:

- increment a register (add 1),
- decrement a register (subtract 1),
- skip the next instruction if the contents of a register is zero,
- jump to an instruction,
- halt the program.

Yeah, that's it. No extra I/O required: you put the values into the registers
before starting the program and read the values off the registers after it 
finishes. The original sheets started the numbering of both instructions and 
registers from 1, so that kids could better understand this. However, we can 
also make use of this fact in order to merge the "jump" and "halt" 
instructions into just the "jump" one, replacing "halt" with "jump to 0" 
(looks familiar, huh?). This brings the total instruction count to just four 
in the set, which means all the opcodes can fit into just two bits. Finally, 
I'd like to do some rearrangement and bring the jump instruction first and 
also assign some three-letter mnemonics to all those. With that, we get the 
following opcodes: 0) JMP, 1) INC, 2) DEC, 3) ISZ. After writing a simple 
Python script to emulate this instruction set (a task that pretty much 
everyone can accomplish in like 5 minutes), I realized that this is the 
tiniest non-OISC Turing-complete VM I have ever dealt with, which in turn 
brought a crazy idea to my mind: why not emulate it on the HP 12C?

The actual task turned out not as trivial as it sounded. First, I had to
assess how much memory I had at my disposal. Realistically, 10 (host) 
registers at most, which needed to be split between the program and the data 
memory. Ultimately, I decided to allocate five registers for the program and 
five for data. Five registers for the program can contain five steps each 
(taking 10 digits), which dictated the maximum program length of 25 steps 
(comparable to the 21 in the original paper version) and the two-digit 
instruction format: instr = opcode * 25 + opreg, where opreg can either be a 
register ("paper" register number minus 1) or a step number (1 to 24). The 
five data registers, on the other hand, are plain host registers that can 
hold arbitrary integers and be read or written by the program. Of course, 
the only way of accessing either of those would be indirect, so I really 
could only afford 85 (host) program steps at most to implement this emulator 
for the main registers R0 to R8 and additionally RFV to remain free.

Then, I needed to figure out how to decode the packed instructions and
decrease the amount of conditionals when executing them. I won't go over the 
details of the program format and the VM implementation itself here, but 
you, as usual, may read all that in my 12C document ([1]) under the 
"KHCEmu12" section. However, I can't stress enough how important it was to 
properly debug the instruction decoding part and the indirect addressing 
bits, considering all Rn pre-increments and post-decrements and whatnot. 
This is something that you won't see in any Python-based emulator. Also, to 
decrease the amount of conditionals, I combined the increment and decrement 
instructions into a single formula, given that the opcode is 1 for 
incerement is 2 for decrement: regs[opreg] += 3 - opcode * 2. Maybe sticking 
to four conditionals instead of three might yield faster code, but then I 
might not be able to stay within the 85-step limit. The actual KHCEmu12 
program turned out to be 80 steps long, by the way.

Now, is there any practical use we could get out of this? For the masses, not
much: even a simple canonical addition program for KHC runs for about 71 
seconds when emulated on the original 12C and trying to add 5 and 8. 
However, the real value here is that it does work and does indeed produce 
the correct results. On some forums, I had seen some nonsense statements 
that HP 12C "isn't Turing-complete". Well, what I just did proves the 
opposite: not only is it Turing-complete by itself, but it is also capable 
of running Turing-complete VMs! Not to mention that, just like the KHC 
itself was an educational tool for the children to learn elementary 
programming concepts, writing KHCEmu12 was a way for me to learn advanced 
programming concepts on the 12C, confirming once again how damn capable of a 
machine this is despite all its known quirks and limitations.

And this, my friends, is how the two topics I covered throughout the previous
weeks finally have met at one point. Of course, I'm not going to abandon 
them both anytime soon, but for the next month or so, I want to switch my 
phlog to something completely different. Something so minimalistic that it 
doesn't involve any electronics whatsoever, yet it cannot be truly mastered 
in a day, a week or a month. Yet another journey is ahead of me, and I feel 
like being ready to walk it.

--- Luxferre ---

[1]: gopher://hoi.st:70/0/docs/own/hp-12c-soft.txt