4 ms·

Bytecode interpreters for tiny computers

73 points by gnosis 16y ago

comex 16y ago
I think requiring the interpretation of fib to be recursive is a little biased toward stack-based language VMs. Non-recursive ARM (thumb) solution, 14 bytes: 0: 2100 movs r1, #0 2: 3801 subs r0, #1 4: dd01 ble.n 0xa 6: 4401 add r1, r0 8: e7fb b.n 0x2 a: 4608 mov r0, r1 c: 4770 bx lr
- comex 16y ago
  Self-reply: I'm an idiot, this just computes the sum of 1 to n. Doing fib requires a few more instructions.
aidenn0 16y ago
I didn't see any mention of the Infocom z-machine bytecode (http://www.gnelson.demon.co.uk/zspec/ http://www.gnelson.demon.co.uk/zspec/); it would be interesting to see how it compares.
rch 16y ago
Is it blasphemy to want Go to have a horse in this race? An equivalence beyond eval anyway... http://golang.org/pkg/exp/eval/ http://golang.org/pkg/exp/eval/
spitfire 16y ago
Hurray for the mention of P-Code.
haberman 16y ago
Bookmarked "toread" -- it looks to be a really insightful look at byte-code that compares and analyzes a bunch of language implementations. What an interesting guy. He runs a blog masquerading as a mailing list (that's what this link is from: "Kragen-tol" is a mailing list for "Kragen thinking out loud") which looks to be full of lots of interesting and incredibly detailed essays across a wide range of subjects. His homepage (http://www.canonical.org/~kragen/ http://www.canonical.org/~kragen/) doesn't mention the mailing list at all (?), but it does have a bunch of other intriguing and random things, like a list of all the people he knows, for the purpose of telling search engines about it: http://www.canonical.org/~kragen/pik/ http://www.canonical.org/~kragen/pik/
- Someone 16y ago
  I am not sure about that insightful. He complains that literals on the F21 take two instructions. The Forth way is to define constants you need often like this: : 1 1 ; (that denies a function called 1 that 'returns' the integer 1) With that function in place (3 instructions, I guess), you can replace n usages of the literal 1 (2n instructions) by n calls of that function (n instructions), for a total of n+3 instructions. So, this pays of if n>=3. Oh, and subroutine calls are cheap on Forth hardware (one cycle for a call and zero cycles for a return is easily achievable)
sedachv 16y ago
Dubé and Feeley went back to rework BIT after PICBIT: http://www.scribd.com/doc/49352760/BIT-A-very-compact-Scheme-system-for-microcontrollers http://www.scribd.com/doc/49352760/BIT-A-very-compact-Scheme... With the R4RS library it only needs 13KiB ROM and they claim you can run programs in less than 5KiB RAM. And it comes with a real-time GC. Not hand-coded assembler small, but the kind of development, testing and prototyping environment you get with Scheme is awesome. The MuP21 sounds really impressive. 6000 transistors including video and DRAM is hard to believe.
ChuckMcM 16y ago
The Parallax BASIC Stamp used NRZ encoded bit tokens. The ROM for the interpreter was 1K words (14 bit words) as I recall. It is really efficient in terms of space. Build a bit aligned FPGA CPU would be pretty cool, and using a serial EEPROM quite efficient in terms of I/O busses but like the PDP-8/S probably very very slow.

73 points by gnosis 16y ago

comex 16y ago

I think requiring the interpretation of fib to be recursive is a little biased toward stack-based language VMs. Non-recursive ARM (thumb) solution, 14 bytes: 0: 2100 movs r1, #0 2: 3801 subs r0, #1 4: dd01 ble.n 0xa 6: 4401 add r1, r0 8: e7fb b.n 0x2 a: 4608 mov r0, r1 c: 4770 bx lr

comex 16y ago
Self-reply: I'm an idiot, this just computes the sum of 1 to n. Doing fib requires a few more instructions.

aidenn0 16y ago

I didn't see any mention of the Infocom z-machine bytecode (http://www.gnelson.demon.co.uk/zspec/ http://www.gnelson.demon.co.uk/zspec/); it would be interesting to see how it compares.

rch 16y ago

Is it blasphemy to want Go to have a horse in this race? An equivalence beyond eval anyway... http://golang.org/pkg/exp/eval/ http://golang.org/pkg/exp/eval/

spitfire 16y ago

Hurray for the mention of P-Code.

haberman 16y ago

Bookmarked "toread" -- it looks to be a really insightful look at byte-code that compares and analyzes a bunch of language implementations. What an interesting guy. He runs a blog masquerading as a mailing list (that's what this link is from: "Kragen-tol" is a mailing list for "Kragen thinking out loud") which looks to be full of lots of interesting and incredibly detailed essays across a wide range of subjects. His homepage (http://www.canonical.org/~kragen/ http://www.canonical.org/~kragen/) doesn't mention the mailing list at all (?), but it does have a bunch of other intriguing and random things, like a list of all the people he knows, for the purpose of telling search engines about it: http://www.canonical.org/~kragen/pik/ http://www.canonical.org/~kragen/pik/

Someone 16y ago
I am not sure about that insightful. He complains that literals on the F21 take two instructions. The Forth way is to define constants you need often like this: : 1 1 ; (that denies a function called 1 that 'returns' the integer 1) With that function in place (3 instructions, I guess), you can replace n usages of the literal 1 (2n instructions) by n calls of that function (n instructions), for a total of n+3 instructions. So, this pays of if n>=3. Oh, and subroutine calls are cheap on Forth hardware (one cycle for a call and zero cycles for a return is easily achievable)

sedachv 16y ago

Dubé and Feeley went back to rework BIT after PICBIT: http://www.scribd.com/doc/49352760/BIT-A-very-compact-Scheme-system-for-microcontrollers http://www.scribd.com/doc/49352760/BIT-A-very-compact-Scheme... With the R4RS library it only needs 13KiB ROM and they claim you can run programs in less than 5KiB RAM. And it comes with a real-time GC. Not hand-coded assembler small, but the kind of development, testing and prototyping environment you get with Scheme is awesome. The MuP21 sounds really impressive. 6000 transistors including video and DRAM is hard to believe.

ChuckMcM 16y ago

The Parallax BASIC Stamp used NRZ encoded bit tokens. The ROM for the interpreter was 1K words (14 bit words) as I recall. It is really efficient in terms of space. Build a bit aligned FPGA CPU would be pretty cool, and using a serial EEPROM quite efficient in terms of I/O busses but like the PDP-8/S probably very very slow.