Path: csiph.com!usenet.pasdenom.info!aioe.org!.POSTED!not-for-mail From: "Rod Pemberton" Newsgroups: comp.lang.forth Subject: Re: Brainfuck in ANS Forth Date: Fri, 02 May 2014 22:37:01 -0400 Organization: Aioe.org NNTP Server Lines: 165 Message-ID: References: <80e059b1-2b0a-4b96-9c93-ab4ef88d9822@googlegroups.com> <53638d07$0$2938$e4fe514c@news2.news.xs4all.nl> <921a887e-606a-4f77-b1a6-ecd89357f025@googlegroups.com> NNTP-Posting-Host: CNsg4fVcCsvs3UaOgZtQCw.user.speranza.aioe.org Mime-Version: 1.0 Content-Type: text/plain; charset=iso-8859-1; format=flowed; delsp=yes Content-Transfer-Encoding: 7bit X-Complaints-To: abuse@aioe.org User-Agent: Opera Mail/12.16 (Linux) X-Notice: Filtered by postfilter v. 0.8.2 Xref: csiph.com comp.lang.forth:30066 On Fri, 02 May 2014 18:04:31 -0400, Mark Wills wrote: > On Friday, 2 May 2014 17:06:52 UTC+1, Mark Wills wrote: >> Darn it Hans. I thought I was done with it. Now you've gone and started >> something ;-) > > This is apparently a complete BF interpreter coded in C. > > char > m[9999],*n[99],*r=m,*p=m+5000,**s=n,d,c;main(){for(read(0,r,4000);c=*r; > r++)c-']'||(d>1||(r=*p?*s:(--s,r)),!d||d--),c-'['||d++||(*++s=r),d||(*p+=c== > '+',*p-=c=='-',p+=c=='>',p-=c=='<',c-'.'||write(2,p,1),c-','||read(2,p,1));} > > Wow! Ugh... I tested every BF interpreter and compiler I could find a few years back. Usually, the short BF interpreters have something which doesn't work perfectly, i.e., boundary conditions, undefined behavior change, etc. I found five that are really good. What I did was write a BF to C converter in C which optimizes additions, subtracts, pointer shifts. Everyone does this. But, I also eliminate deadcode and optimize clears and setting of cells. It also manipulates a pointer and value separately. It does this because some BF programs can do many adjustments to a single cell, i.e., without moving the pointer. This reduces pointer dereferences in C and allows the value to be placed in a register. It does all that in a single pass, emitting C directly, ANSI C, without allocating any memory. It just uses a handful of variables. I've been interested in three other optimizations to BF. One of them basically requires a powerful expression match and rewriting capabilities, e.g., program directed text editor. These had to do with cell compression or compaction. I.e., if only the first and third cells are used, the code would be rewritten to use the first and second. The third was conversion to statically named cells in C, i.e., treatment of each cell as a named variable in C. This only works if pointer movement within loops is balanced. Unbalanced movement of the pointer within a loop - ending on a different cell - means the next time through the loop, a different set of cells is accessed. That, of course, means that if each cell is named, a different set of names would be needed for each time through the loop. That's a problem in C (without using pointers). Unbalanced loops happen for any of the "search" sequences for BF. I also did two trivial analyses of common BF sequences, to determine what the main operations are. Because operators in BF can be repeated, I used some compression to reduce to a basic form. I'd have to check my results for the exact number. I'll just say there was about a half-dozen to a dozen primary sequences, i.e., not too many. So, 14 to 20 operations when you take into account the original 8. BF needs a few things like setting values and chars directly, strings, larger integers to be more useful. It would've been nice if BF had one more operation, to clear a cell. That would eliminate trivial loops allowing optimizers to work on loops that do something. So, I use '~' tilde to do a cell clear instead of '[-]' or '[+]'. I'd recommend not using the '[+]' to clear since you don't know how integer wrapping is handled for a specific interpreter. Anyway, this is what my C program outputs for the "Hello World!" program. The specific one you posted. There are many... Notice the initial setting of value 'v' to 8 and the save value, adjust pointer, reload value sequences, and other optimizations. Obviously, there are no optimizations to emit a complete or partial strings ... Obviously, the assembly for it is still longer and more complicated than it should be, but that's mostly due to the language simplicity. Compile BF "Hello World!" to C conversion using 'gcc -Wall -ansi -pedantic -O2'. It should compile clean and work with GCC (Linux, DJGPP, etc). #include #define SZ 32768 int main(void) { unsigned char a[SZ],*p,v; for(p=a;p<&a[SZ];*p=0,p++); p=a; v=8; while(1) { if(!v)break; *p=v;p++;v=*p; v+=4; while(1) { if(!v)break; *p=v;p++;v=*p; v+=2; *p=v;p++;v=*p; v+=3; *p=v;p++;v=*p; v+=3; *p=v;p++;v=*p; v++; *p=v;p-=4;v=*p; v--; } *p=v;p++;v=*p; v++; *p=v;p++;v=*p; v++; *p=v;p++;v=*p; v--; *p=v;p+=2;v=*p; v++; while(1) { if(!v)break; *p=v;p--;v=*p; } *p=v;p--;v=*p; v--; } *p=v;p+=2;v=*p; putchar(v); *p=v;p++;v=*p; v-=3; putchar(v); v+=7; putchar(v); putchar(v); v+=3; putchar(v); *p=v;p+=2;v=*p; putchar(v); *p=v;p--;v=*p; v--; putchar(v); *p=v;p--;v=*p; putchar(v); v+=3; putchar(v); v-=6; putchar(v); v-=8; putchar(v); *p=v;p+=2;v=*p; v++; putchar(v); *p=v;p++;v=*p; v+=2; putchar(v); return(0); } Rod Pemberton