Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #30066

Re: Brainfuck in ANS Forth

Show all headers | View raw

On Fri, 02 May 2014 18:04:31 -0400, Mark Wills <markwills1970@gmail.com>  
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 <stdio.h>
#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

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

Brainfuck in ANS Forth Mark Wills <markwills1970@gmail.com> - 2014-05-01 08:31 -0700
  Re: Brainfuck in ANS Forth "Alex McDonald" <blog@rivadpm.com> - 2014-05-01 18:54 +0100
    Re: Brainfuck in ANS Forth Mark Wills <markwills1970@gmail.com> - 2014-05-01 15:20 -0700
  Re: Brainfuck in ANS Forth "Rod Pemberton" <dont_use_email@xnothavet.cqm> - 2014-05-01 16:08 -0400
    Re: Brainfuck in ANS Forth Mark Wills <markwills1970@gmail.com> - 2014-05-01 15:22 -0700
    Re: Brainfuck in ANS Forth "Elizabeth D. Rather" <erather@forth.com> - 2014-05-01 12:31 -1000
      Re: Brainfuck in ANS Forth Mark Wills <markwills1970@gmail.com> - 2014-05-02 01:09 -0700
        Re: Brainfuck in ANS Forth Hans Bezemer <the.beez.speaks@gmail.com> - 2014-05-02 14:18 +0200
          Re: Brainfuck in ANS Forth Mark Wills <markwills1970@gmail.com> - 2014-05-02 09:06 -0700
            Re: Brainfuck in ANS Forth Mark Wills <markwills1970@gmail.com> - 2014-05-02 15:04 -0700
              Re: Brainfuck in ANS Forth "Rod Pemberton" <dont_use_email@xnothavet.cqm> - 2014-05-02 22:37 -0400
                Re: Brainfuck in ANS Forth Hans Bezemer <the.beez.speaks@gmail.com> - 2014-05-03 12:02 +0200
                Re: Brainfuck in ANS Forth "Rod Pemberton" <dont_use_email@xnothavet.cqm> - 2014-05-03 09:21 -0400
                Re: Brainfuck in ANS Forth Mark Wills <markwills1970@gmail.com> - 2014-05-06 08:14 -0700
                Re: Brainfuck in ANS Forth "Rod Pemberton" <dont_use_email@xnothavet.cqm> - 2014-05-06 16:53 -0400
                Re: Brainfuck in ANS Forth Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2014-05-22 22:13 +0100
                Re: Brainfuck in ANS Forth Coos Haak <chforth@hccnet.nl> - 2014-05-23 15:27 +0200
                Re: Brainfuck in ANS Forth Gerry Jackson <gerry@jackson9000.fsnet.co.uk> - 2014-05-26 21:38 +0100
        Re: Brainfuck in ANS Forth Assad Ebrahim <assad.ebrahim@alum.swarthmore.edu> - 2014-05-03 22:59 +0100
          Re: Brainfuck in ANS Forth all2001@spambog.com (Wolfgang Allinger) - 2014-05-03 19:39 -0400
  Re: Brainfuck in ANS Forth Ian Osgood <iano@quirkster.com> - 2014-06-16 15:35 -0700

csiph-web