[info] bytecode interpreters for tiny computers

[Eugen Leitl]

----- Forwarded message from Dave Long <dave.long at bluewin.ch> -----

From: Dave Long <dave.long at bluewin.ch>
Date: Fri, 5 Oct 2007 12:11:15 +0200
To: kragen-discuss at canonical.org
Cc: ambrus at math.bme.hu
Subject: Re: bytecode interpreters for tiny computers
X-Mailer: Apple Mail (2.752.3)

>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.


----- End forwarded message -----
-- 
Eugen* Leitl <a href="http://leitl.org">leitl</a> http://leitl.org
______________________________________________________________
ICBM: 48.07100, 11.36820 http://www.ativel.com http://postbiota.org
8B29F6BE: 099D 78BA 2FD3 B014 B08A  7779 75B0 2443 8B29 F6BE