(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