Smallfuck/Brainfuck or how I discovered how to translate code to circuitssteemCreated with Sketch.

in #programming5 years ago (edited)

Smallfuck or how I discovered how to translate code to circuits

Yesterday I played around with a brainfuck derivate called smallfuck and even wrote an interpreter in around an hour.

The funny thing is that Smallfuck can be translated to brainfuck by just substituting brainfuck instructions with many small fuck instructions.

Here's a list which does the trick:

+ >[>]*<[*<]>>>>>>>>>[*]<<<<<<<<<
- >>>>>>>>>*<<<<<<<<*[>*]<[<]>>>>>>>>>[*]<<<<<<<<<
< <<<<<<<<<
> >>>>>>>>>
[ >>>>>>>>>*<<<<<<<<*[>*]<[<]>>>>>>>>>[*<<<<<<<<[>]*<[*<]
] >>>>>>>>>*<<<<<<<<*[>*]<[<]>>>>>>>>>]<[*<]

And then I was thinking how to build actually a Smallfuck CPU ...

and now the secret or code to circuit

Actually you gotta use flipflops for the variables and yes a flipflop can only store one bit so your code or program will be limited to booleans but - hey! it already started with a brainfuck derivate so what else to expect.

I used logical formula in my emulation of circuits and they do quite a good job in emulating it and I decided not to care much about all those technical details or but(t)s.

FlipFlops can be set and unset and I decided to use the SR-Switch with NORs as that required just two lines.

   q=!(r||nq);
   nq=!(s||q);

So if the R and S inputs are both off the stored value does not change.

I used clock signals for emulating the execution of lines of code or in other words, different clock signals are necessary to run the program.

In the program I tried to translate to circuit I just used two lines or for the clock signals : clk0 and clk1

I had to use on while-loop just for emulating state change but I could have done with recursion or setInterval in JavaScript as well.

Branching or ifs are realized with logical AND and the desired condition.

Actually you do not need more than one loop in any program, as multiple nested loops can be emulated with branching.

Ooops! I guess, that's pretty much it ... However as understanding is just dropping in like a leaking water pipe I think we all could enjoy a sample.

A Sample of translating a simple program to logical circuits

Here's a simple JavaScript program which adds two numbers 3 and 2.

   var a=3,b=2,r=c=0;
   do{
    r=a^b;
    c=(a&b)<<1;
    a=r;
    b=c;
   }while(c>0);
   console.log(r);

Variable r ist the result and c is for the carries. It calculates and copies r and c to the input variables a and b until c is zero.

the translation to Circuits by utilizing 12 flipflops

I guess you'll have a WTF!-moment now or probably not.

var aq0,aq1,aq2,an0,an1,an2,as0,as1,as2,ar0,ar1,ar2;
var bq0,bq1,bq2,bn0,bn1,bn2,bs0,bs1,bs2,br0,br1,br2;
var cq0,cq1,cq2,cn0,cn1,cn2,cs0,cs1,cs2,cr0,cr1,cr2;
var rq0,rq1,rq2,rn0,rn1,rn2,rs0,rs1,rs2,rr0,rr1,rr2;
var clk0=true,clk1=false;

//setting A-flipflops to 011 and B-flipflops to 010
as2=false;as1=true;as0=true;ar2=!as2;ar1=!as1;ar0=!as0;
bs2=false;bs1=true;bs0=false;br2=!bs2;br1=!bs1;br0=!bs0;
//A- and B-flipflops 
 aq0=!(ar0||an0);an0=!(as0||aq0);
 aq1=!(ar1||an1);an1=!(as1||aq1);
 aq2=!(ar2||an2);an2=!(as2||aq2);
 bq0=!(br0||bn0);bn0=!(bs0||bq0);
 bq1=!(br1||bn1);bn1=!(bs1||bq1);
 bq2=!(br2||bn2);bn2=!(bs2||bq2);
 //setting c0-flipflop to 0
 cs0=false;cr0=true;
 cq0=!(cr0||cn0);cn0=!(cs0||cq0);

while(!clk1){
 //doing calculation if clk0 is on
 rs0=(aq0!=bq0)&&clk0;rr0=(!rs0)&&clk0;
 rs1=(aq1!=bq1)&&clk0;rr1=(!rs1)&&clk0;
 rs2=(aq2!=bq2)&&clk0;rr2=(!rs2)&&clk0;
 cs0=cr0=false;
 cs1=(aq0&&bq0)&&clk0;cr1=(!cs1)&&clk0;
 cs2=(aq1&&bq1)&&clk0;cr2=(!cs2)&&clk0;
 //copying R- and C- to A- and B-flipflops if clk0 is off
 as0=rq0&&!clk0;ar0=(!rq0)&&!clk0;
 as1=rq1&&!clk0;ar1=(!rq1)&&!clk0;
 as2=rq2&&!clk0;ar2=(!rq2)&&!clk0;
 bs0=cq0&&!clk0;br0=(!cq0)&&!clk0;
 bs1=cq1&&!clk0;br1=(!cq1)&&!clk0;
 bs2=cq2&&!clk0;br2=(!cq2)&&!clk0;
 //THOSE FLIPFLOPS NEED TO RUN TWO CYCLES TO STABILIZE 
 //got me a hard time as I could not find the error 
 //R- and C-flipflops
 rq0=!(rr0||rn0);rn0=!(rs0||rq0);
 rq1=!(rr1||rn1);rn1=!(rs1||rq1);
 rq2=!(rr2||rn2);rn2=!(rs2||rq2); 
 cq0=!(cr0||cn0);cn0=!(cs0||cq0);
 cq1=!(cr1||cn1);cn1=!(cs1||cq1);
 cq2=!(cr2||cn2);cn2=!(cs2||cq2); 
  //A- and B-flipflops 
 aq0=!(ar0||an0);an0=!(as0||aq0);
 aq1=!(ar1||an1);an1=!(as1||aq1);
 aq2=!(ar2||an2);an2=!(as2||aq2);
 bq0=!(br0||bn0);bn0=!(bs0||bq0);
 bq1=!(br1||bn1);bn1=!(bs1||bq1);
 bq2=!(br2||bn2);bn2=!(bs2||bq2);
 //R- and C-flipflops
 rq0=!(rr0||rn0);rn0=!(rs0||rq0);
 rq1=!(rr1||rn1);rn1=!(rs1||rq1);
 rq2=!(rr2||rn2);rn2=!(rs2||rq2); 
 cq0=!(cr0||cn0);cn0=!(cs0||cq0);
 cq1=!(cr1||cn1);cn1=!(cs1||cq1);
 cq2=!(cr2||cn2);cn2=!(cs2||cq2); 
  //A- and B-flipflops 
 aq0=!(ar0||an0);an0=!(as0||aq0);
 aq1=!(ar1||an1);an1=!(as1||aq1);
 aq2=!(ar2||an2);an2=!(as2||aq2);
 bq0=!(br0||bn0);bn0=!(bs0||bq0);
 bq1=!(br1||bn1);bn1=!(bs1||bq1);
 bq2=!(br2||bn2);bn2=!(bs2||bq2); 
 //output test values
 console.log('clk0 '+clk0);
 console.log(`A ${aq2} ${aq1} ${aq0}`);
 console.log(`B ${bq2} ${bq1} ${bq0}`);
 console.log(`R ${rq2} ${rq1} ${rq0}`);
 console.log(`C ${cq2} ${cq1} ${cq0}`);
 console.log('---');
 //changing clock signals 
 clk0=!clk0;
 clk1=(!cq2)&&(!cq1)&&clk0;
}

my Smallfuck Interpreter

   
// smallfuck understands following commands: <>[]*
// < decrement data pointer , > increment data pointer
// [ while value under data pointer is not equal to 0 
// ] end of previous while loop 
// * switch bit , 1 to 0 , 0 to 1 
// smallfuck works with bits instead of bytes like brainfuck
// the interpreter just uses 256 byte of memory

function smallfuck(code){
 var MAXMEM=256;
 var core=new Array(MAXMEM).fill(false);
 // ip ... instruction pointer
 // dp ... data pointer
 var ip=dp=0;
  
 while(ip<code.length){  
  switch(code[ip]){
   case '<': if(dp>=0)
              {--dp;
               ++ip;
              }
             else
              {return 'memory error in line '+ip;}
             break;
   case '>': if(dp<MAXMEM)
              {++dp;
               ++ip;
              }
             else
              {return 'memory error in line '+ip;}
             break;
   case '[': var closedBracket=findRightClosedBracket();
             if(!(closedBracket<MAXMEM)){return 'non closing while or ] missing';}
             if(core[dp]){++ip;}             
             else{ip=closedBracket+1;}
             break;
   case ']': var openBracket=findRightOpenBracket();
             if(openBracket<0){return 'non open while bracket or [ missing';}
             ip=openBracket;
             break;
   case '*': core[dp]=!core[dp];
             ++ip;
             break;
   default: return 'unknown instruction in line '+ip;
  }
 }

 function findRightClosedBracket(){
  var i=ip;
  var skip=1;
  var found=false;
  do
   {++i;
    if(code[i]=='['){++skip;console.log('[ '+skip);}
    if(code[i]==']'){--skip;console.log('] '+skip);} 
    if((code[i]==']')&&(skip==0)){found=true;}
   }
  while((i<MAXMEM)&&!found);
  console.log('fRCB '+i);
  return i;
 }

 function findRightOpenBracket(){
  var i=ip;
  var skip=1;
  var found=false;
  do
   {--i;
    if(code[i]=='['){--skip;console.log('[ '+skip);}
    if(code[i]==']'){++skip;console.log('] '+skip);} 
    if((code[i]=='[')&&(skip==0)){found=true;}
   }
  while((i>=0)&&!found);
  console.log('fROB '+i);
  return i;
 }
 
 return core;
}