From kragen@dnaco.net Sun Aug 23 21:06:59 1998
Date: Sun, 23 Aug 1998 21:06:58 -0400 (EDT)
From: Kragen <kragen@dnaco.net>
To: hugi-compo@makelist.com
Subject: small life entries
Message-ID: <Pine.SUN.3.96.980823204846.21201e-100000@picard.dnaco.net>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
X-Keywords:
X-UID: 1363
Status: O
X-Status: 

You know, small game-of-life programs are interesting in a way small
Pong programs are not -- Life is, I believe, theoretically equivalent
to a Turing machine in computational power.

It would be interesting to see how small one could make a Turing
machine.  Here's one in C, but I'm sure someone can do better in x86
machine code:
/* ./executable 4 '  }"!{ "} #}123123123123#!{!X|!"|!#|# {!X| #}##{' '"""""    !'  */
int n,p=0,s=32;char*pt;main(int c,char**v){n=atol(v[1]);while(s!=33){pt=v[2]+3*(n*(s-32)+v[3][p]-32);s=pt[0];v[3][p]=pt[1];p+=pt[2]-'|';}puts(v[3]);}

(If you try this program, you should be aware of the following:
1. incorrect input will likely crash the process -- and if you're in
DOS, your computer.
2. The example input above assumes UNIX quoting conventions -- ''
quotes anything as one word and gets dropped.  If you're going to try
to run it in DOS (not advisable) then maybe you should change it so you
don't have to have spaces and double-quotes in your input -- maybe
change '32' and '33' in the code to '65' and '66', for example.
3. The example input in the comment programs the TM to subtract
base-one numbers.
4. The program as written assumes your charset is ASCII.
)

Another possibility, which is likely to be more interesting, would be
the smallest implementation of FORTH.  pfe comes with some ANSI FORTH
compliance tests, and I'm sure there are some others sitting around.

Here's an indirect-threaded FORTH VM in C, including a little bit of
boot code (which doesn't do anything interesting.)  To do a full FORTH
implementation would probably require an auxiliary data file, which
could be unlimited in size.

typedef int c;extern c m[];c x,y,pc,ds[32768],rs[32768],*rp=rs,*dp=ds;
CI(){for(;;){x=m[pc++];(*((c(*)())m[x]))(m[x+1]);}}
PR(c x){*rp++=x;}c RP(){return *--rp;}
PD(c x){*dp++=x;}c DP(){return *--dp;}
CX(c pfa){PR(pc);pc=pfa;}RX(){pc=RP();}
JX(){pc=m[pc];}FX(){x=DP();if(x)pc++;else JX();}
SX(){x=DP();PD(DP()-x);}
EX(){x=DP();putchar(x);}GX(){PD(getchar());}
LX(){PD(DP()<0);}
NX(){PD(m[pc++]);}
QX(){exit(DP());}
c m[32768]={3,20,RX,JX,FX,SX,EX,GX,LX,NX,QX,0,0,0,0,0,0,0,0,0,
30,9,33,6,9,10,6,9,0,10,CX,32,35,35,2,CX,37,7,6,9,10,6,2};
main(){pc=0;CI();}

(When I wrote this, I didn't really understand pfas in the normal FORTH
way.  m[x+1] should really be just x+1 in CI(), and that requires some
changes to the rest of the program, but ought to make it smaller.)

I'm pretty sure a full Forth VM, including boot code, can fit in under
1K of x86 machine code.  (It could probably fit in under 1K of C, in
fact.)

Kragen

-- 
<kragen@pobox.com>       Kragen Sitaker     <http://www.pobox.com/~kragen/>
We are forming cells within a global brain and we are excited that we might
start to think collectively.  What becomes of us still hangs crucially on
how we think individually.  -- Tim Berners-Lee, inventor of the Web