1) Introduction: Density Is King (With a Tiny VM)
2) Indirect Threaded 16-bit FORTH: Not Great For Density
3) Naive Lisp: Terrible for Density
4) Lua's VM: Four-Byte Register-Based Instructions
5) The MuP21 and F21 instruction sets
6) Local Variables: Registers Or Stacks?
7) Adapting the MuP21 Instruction Set to a Smalltalk-Like System
8) Speculative Case Study: An F21-like Squeak
9) Steve Wozniak's SWEET 16 Dream Machine
10) NanoVM: Java Bytecodes on the AVR
11) Code-Compact Data Structures
12) Library Design
13) Other Existing Small Interpreters
14) Conclusions: Squeak Rules, We Should Be Able To Do Python In A Few K
Doesn't the SWEET16 make it straightforward to drop in and out of straight 6502 machine code? Making it more like a library or virtual coprocessor? Did anyone ever target it with a compiler?
Yeah Sweet16 was just a way to get denser code on a 6502, by giving you a 16 bit register VM so you could do 16 bit operations without having to expand out multiple 8 bit instructions. For a compiler target you might be better off with bytecode. I remember looking at the sweet16 description and thinking it would be hard to compile to, though partly because the docs I looked at weren't very complete. It was architecturally odd too though.
Wikipedia has a page on it: <https://en.wikipedia.org/wiki/SWEET16>. It's architecturally odd because it was designed to run on a 6502 with as small as footprint as possible (about 300 bytes of code, 32 bytes of RAM) and only did a few operations (add, sub, cmp, call, return, inc, dec, load, store, branch-on-condition).
> With this approach, it should be possible to get a very slow language, with flexibility something like Python's, into maybe 2000-6000 bytes of a microcontroller's ROM
Yup. https://sneklang.org/ (Originally created for a machine with 32kB of flash and 2kB of RAM.)
That is cool, it looks like Python, how did they get it so small? Is it garbage collected? Is the interpreter entirely resident in the Arduino or does it rely on an external communication app hosting the compiler? That approach is actually underutilized in my opinion.
I gotta say that AVR Arduino hardware is almost silly by now. The Raspberry Pi Pico is probably the successor basic MCU board these days. It costs $4 retail, and has a dual ARM M0+ cpu with 264KB of ram and 2MB of SPI flash, so it can run Micropython and other relatively full featured software.
Generally AOT compiled code is 10x bigger than a compact and flexible bytecode interpreter.
Also miles more unsafe. I.e micropython is based on Lua, as also microruby and potion, just with a proper OO and GC added.
micropython derived from lua, as well as potion, which started those microlang movement and which I am the current maintainer of, as well as microruby and p2. And a few others.
This is a fascinating topic and is related to the Kolomogorov complexity [1] and the densest I'm aware of is John Tromp's Binary lambda calculus [2]. I don't see a reason why the implementation would be larger than the Java NanoVM.
However programs in the pure λ-calculus are likely to be slower than necessary and I'd go with one enriched with at least basic integers and integer ops.
ADD: yes I know that Kolomogorov just measures self-replication, but I think it's a good proxy for code entropy. At least, I don't know of a better one.
It's an interesting idea. Apparently there's a 400-byte implementation of Tromp's blc, but I suspect you could make the interpreter both smaller and faster by using bytecodes rather than Tromp's binary codes, which I think are optimized for giving a plausible measure of Kolmogorov complexity.
I've also been working on an interpreter called Qfitzah for large machines; it implements a term-rewriting language with pattern-matching, dynamic containers, dynamic typing, and dynamic polymorphism in under 1000 bytes: http://canonical.org/~kragen/sw/dev3/qfitzah.s
My next step on it is to enrich it with basic integers and integer ops.
I don't think Kolmogorov complexity measures self-replication. Rather, it uses the code to produce ("replicate") a string to measure that string's entropy.
