bytecode interpreters for tiny computers

[Dave Long]

> I've previously come to the conclusion that there's little reason for
> using bytecode in the modern world, except in order to get more
> compact code, for which it can be very effective.  So, what kind of a
> bytecode engine will give you more compact code?

As dc source is its own bytecode, fib in dc (courtesy of Zsbán  
Ambrus) weighs in at 20 bytes:

1dp[pdsd+ldrlxx]dsxx

unfortunately, like SWEET16, dc code blows up quickly after leaving  
its domain.  J is probably the closest equivalent among more modern  
general-purpose languages, and although fib appears to be much longer  
in J (courtesy Marluth @ Everything2), at around 28 bytes:

1:`((],+/@(_2&{.))@$:@<:)@.*

the 8 queens puzzle (which I believe would be very painful in dc;  
Gödel-coding doesn't lend itself to data-structure manipulation) can  
be expressed in only about twice as many bytes[1] (which is still  
smaller than the PowerPC fib -- how's that for density?):

(#~[:(0=>./)[:,/[:([:}.([:i.#)=[:|(]-"1{.))\.|:)(i.A.~[:i.!) 8

-Dave

:: :: ::

[0] for those few who don't have dc, but do have python, see:
http://en.literateprograms.org/Desk_calculator_(Python)

[1] such dense code requires many more bytes of commentary:
http://en.literateprograms.org/Eight_queens_puzzle_%28J%29

> I'm not sure what +* is for, but I'm guessing it was ADDNZ.

It appears to be for implementing each iteration of (Russian/ 
Egyptian/...) Peasant Multiplication.

http://en.wikipedia.org/wiki/Ancient_Egyptian_multiplication
http://www.cut-the-knot.org/Curriculum/Algebra/ 
PeasantMultiplication.shtml

very weakly related: "[FoRK] basic number theory"
http://www.xent.com/pipermail/fork/Week-of-Mon-20060731/042377.html

> ... 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.  This should allow you to interactively  
> get out-of-memory errors with great convenience and flexibility.

I have been considering implementing a dc/J-like expression language  
for compiling to smaller AVRs -- I don't tend to have pins free for  
interactive use, but maybe it'd be worth looking into an interpreter  
for the larger AVRs.