4 ms·
Bytecode interpreters for tiny computers (2007)
- dang 5y agoRelated: Bytecode interpreters for tiny computers - https://news.ycombinator.com/item?id=2250890 https://news.ycombinator.com/item?id=2250890 - Feb 2011 (9 comments) Bytecode interpreters for tiny computers (2007) - https://news.ycombinator.com/item?id=1406981 https://news.ycombinator.com/item?id=1406981 - June 2010 (8 comments)
- benhoyt 5y agoI had an ideal along these lines a while back that I called "nibbleforth": https://github.com/benhoyt/nibbleforth https://github.com/benhoyt/nibbleforth
- entaloneralie 5y agoI had to try and find out how many bytes it would be with UxnVM in comparison: #0000 INC2k ADD2k &loop ADD2k LTH2k ,&loop JCN assembled: fib.tal(10 bytes) a000 00a1 b8b8 ab80 fb0d
- kragen 5y agoNice! https://100r.co/site/uxn.html https://100r.co/site/uxn.html
- FullyFunctional 5y agoThis 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. [1] https://en.wikipedia.org/wiki/Kolmogorov_complexity https://en.wikipedia.org/wiki/Kolmogorov_complexity [2] https://tromp.github.io/cl/Binary_lambda_calculus.html https://tromp.github.io/cl/Binary_lambda_calculus.html
- kragen 5y agoIt'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 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.
- karmakaze 5y agoCool stuff: 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
- buescher 5y agoDoesn'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? Yes, though, cool stuff!
- throwaway81523 5y agoYeah 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.
- spc476 5y agoWikipedia has a page on it: <https://en.wikipedia.org/wiki/SWEET16 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).
- kragen 5y agoI'm glad you liked it!
- teddyh 5y ago> 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/ https://sneklang.org/ (Originally created for a machine with 32kB of flash and 2kB of RAM.)
- throwaway81523 5y agoThat 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. Also check out my old favorite Hedgehog Lisp: https://github.com/sbp/hedgehog 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.
- rurban 5y agoGenerally 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.
- throwaway81523 5y agoThe AOT compiled code for Hedgehog is bytecode. I just mean that the bytecode compiler is on a PC host rather than inside the embedded mcu. Micropython is completely separate from Lua.
- rurban 5y agomicropython 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.
- guessbest 5y agoI remember the Basic Stamp being incredibly popular in the 90's and not being able to get one.