Bytecode interpreters for tiny computers (2007)
dercuano.github.io
dercuano.github.io
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 KYes, though, cool stuff!
Yup. https://sneklang.org/ (Originally created for a machine with 32kB of flash and 2kB of RAM.)
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.
Also check out my old favorite Hedgehog Lisp: https://github.com/sbp/hedgehog
It's a functional-style Lisp dialect whose VM is 20K bytes. It uses an external ahead-of-time compiler, no resident interpreter.
Micropython is completely separate from Lua.
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.
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.
Bytecode interpreters for tiny computers - https://news.ycombinator.com/item?id=2250890 - Feb 2011 (9 comments)
Bytecode interpreters for tiny computers (2007) - https://news.ycombinator.com/item?id=1406981 - June 2010 (8 comments)
#0000 INC2k ADD2k &loop ADD2k LTH2k ,&loop JCN
assembled: fib.tal(10 bytes)
a000 00a1 b8b8 ab80 fb0d