Feedback for New Interpreter

Projects General Guidance
1

Here is my "BETA" version of an interpreter.
No documentation yet sorry. :frowning: .
Fibonacci 6000 times is completed in 68460 microseconds unoptimized.

EDIT: It is currently running on a UNO.

Please do not distribute this without my permission.

Here is the code.

// ==================================================================
// BC256 --Byte Code 256-- INSTRUCTIONS (1.0) "BETA"
// ==================================================================
#define PAUSE_CODE
#define PIN_CTRL
#define ANLG_CTRL    // Adds an extra micros? unknown reason
#define EXTRA_MATH

enum {
  STOP = 0,
  MOVr = 1, // => reg=reg
  MOVb = 2, // => reg=byte
  PRINT = 3, // => Serial.println(reg)
  ADDr = 4, // => reg+=reg
  ADDb = 5, // => reg+=byte
  SUBr = 6, // => reg-reg
  SUBb = 7, // => reg-=byte
  MULr = 8, // => reg*=reg
  MULb = 9, // => reg*=byte
  DIVr = 10, // => reg/=reg
  DIVb = 11, // => reg/=byte
  MODr = 12, // => reg%=reg
  MODb = 13, // => reg%=byte
  SWAP = 14, // => reg<->reg
  BEGr = 15, // => loop reg
  BEGb = 16, // => loop byte
  LOOP = 17, // => loop end
  PUSH = 18, // => mem=reg
  POP = 19, // => reg=mem
  PSHALL = 20, // mem=all regs
  POPALL = 21, // alls regs=mem
  JMPe = 22, // jump to address if =
  JMPl = 23, // jump to address if <
  JMPg = 24, // jump to address if >
  JMPle = 25, // jump to address if <=
  JMPge = 26, // jump to address if >=
  JMPne = 27, // jump to address if !=
  INCR = 28, // reg++
  DECR = 29, // reg--
#ifdef PAUSE_CODE
  HALTr = 30, // pause reg milliseconds
  HALTb = 31, // pause byte milliseconds
  HLTMr = 32, // pause reg microseconds
  HLTMb = 33, // pause byte microseconds
#endif
#ifdef PIN_CTRL
  DDRBr = 34, // DDRB = reg
  DDRBb = 35, // DDRB = byte
  DDRCr = 36, // DDRC = reg
  DDRCb = 37, // DDRC = byte
  DDRDr = 38, // DDRD = reg
  DDRDb = 39, // DDRD = byte
  PORTBr = 40, // PORTB = reg
  PORTBb = 41, // PORTB = byte
  PORTCr = 42, // PORTC = reg
  PORTCb = 43, // PORTC = byte
  PORTDr = 44, // PORTD = reg
  PORTDb = 45, // PORTD = byte
  BPIN = 46, // reg = PINB
  CPIN = 47, // reg = PINC
  DPIN = 48, // reg = PIND
#ifdef ANLG_CTRL
  ANLGOr = 49, // Analog out reg
  ANLGOb = 50, // Analog out byte
  ANLGIN = 51, // reg = analog in
#endif
#endif
#ifdef EXTRA_MATH  
  RSHFTr = 52, // reg>>=reg
  RSHFTb = 53, // reg>>=byte
  LSHFTr = 54, // reg<<=reg
  LSHFTb = 55, // reg<<=byte
  ANDr = 56, // reg&=reg
  ANDb = 57, // reg&=byte
  ORr = 58, // reg|=reg
  ORb = 59, // reg|=byte
  XORr = 60, // reg^=reg
  XORb = 61, // reg^=byte
  NOTr = 62, // reg=~reg
#endif
};

const byte program[] PROGMEM = {
  MOVb, 0, 1,         // A=1
  MOVb, 1, 1,         // B=1
  MOVb, 5, 24,        // ??=24 ==:9
  
  PUSH, 4,            // mem=?
  PUSH, 5,            // mem=??
  
  MOVb, 5, 250,       // ??=250 == :16
  
  ADDr, 0, 1,         // A=A+1
  SWAP, 0, 1,         // B=A & A=B

  INCR, 4,            // ?++
  JMPl, 0, 16,         // ?<?? jump to byte 16

  POP, 5,            // ?=mem
  POP, 4,            // ??=mem
  INCR, 4,            // ?++
  JMPl, 0, 9,         // ?<?? jump to byte 9
  
  STOP,               // Program end
};

byte pRAM[1536];
byte regs[11]; // A = [0], B = [1], C = [2], D = [3], ? = [4], ?? = [5], sp = [6], lpt = [7], lpa = [8], lpa = [9], lpc = [10]
int progaddr = 0;
byte a = 0, b = 0, c = 0, instr = 0;

unsigned long time;

void setup() {
  randomSeed(analogRead(6));
  Serial.begin(9600);
  for (int load = 0; load < sizeof(program); load++) {
    pRAM[load] =  pgm_read_byte_near(program+load);
  }
  time = micros();
  BC256();
  Serial.println(micros()-time);
}

void loop() {
  
}

// ==================================================================
// BC256 --Byte Code 256-- INTEPRETER (1.0) "BETA"
// ==================================================================
void BC256() {
  #define nxtc() pRAM[progaddr++]
  static void* labels[]= {&&instr_0,&&instr_1,&&instr_2,&&instr_3,&&instr_4,&&instr_5,&&instr_6,&&instr_7,&&instr_8,&&instr_9,&&instr_10,&&instr_11,&&instr_12,&&instr_13,&&instr_14,&&instr_15,&&instr_16,&&instr_17,&&instr_18,&&instr_19,&&instr_20,&&instr_21,&&instr_22,&&instr_23,&&instr_24,&&instr_25,&&instr_26,&&instr_27,&&instr_28,&&instr_29,
  #ifdef PAUSE_CODE
    &&instr_30,&&instr_31,&&instr_32,&&instr_33,
  #endif
  #ifdef PIN_CTRL
    &&instr_34,&&instr_35,&&instr_36,&&instr_37,&&instr_38,&&instr_39,&&instr_40,&&instr_41,&&instr_42,&&instr_43,&&instr_44,&&instr_45,&&instr_46,&&instr_47,&&instr_48,
  #ifdef ANLG_CTRL
    &&instr_49,&&instr_50,&&instr_51,
  #endif
  #endif
  #ifdef EXTRA_MATH 
    &&instr_52,&&instr_53,&&instr_54,&&instr_55,&&instr_56,&&instr_57,&&instr_58,&&instr_59,&&instr_60,&&instr_61,&&instr_62 
  #endif
  };
  #define doinstr() {goto *(labels[instr]);}

run_prog:
  instr = nxtc();
  doinstr();

    instr_0: // => End program
      return;
      goto run_prog;
    instr_1: // => Mov reg <- reg
      a = nxtc();
      b = nxtc();
      regs[a] = regs[b];
      goto run_prog;
    instr_2: // => Mov reg <- byte
      a = nxtc();
      b = nxtc();
      regs[a] = b;
      goto run_prog;
    instr_3:
      a = nxtc();
      Serial.println(regs[a]);
      goto run_prog;
    instr_4: // => Add reg += reg
      a = nxtc();
      b = nxtc();
      regs[a] += regs[b];
      goto run_prog;
    instr_5: // => Add reg += byte
      a = nxtc();
      b = nxtc();
      regs[a] += b;
      goto run_prog;
    instr_6: // => Sub reg += reg
      a = nxtc();
      b = nxtc();
      regs[a] -= regs[b];
      goto run_prog;
    instr_7: // => Sub reg += byte
      a = nxtc();
      b = nxtc();
      regs[a] -= b;
      goto run_prog;
    instr_8: // => Mul reg *= reg
      a = nxtc();
      b = nxtc();
      regs[a] *= regs[b];
      goto run_prog;
    instr_9: // => Mul reg *= byte
      a = nxtc();
      b = nxtc();
      regs[a] *= b;
      goto run_prog;
    instr_10: // => Div reg /= reg
      a = nxtc();
      b = nxtc();
      regs[a] /= regs[b];
      goto run_prog;
    instr_11: // => Div reg /= byte
      a = nxtc();
      b = nxtc();
      regs[a] /= b;
      goto run_prog;
    instr_12: // => Mod reg %= reg
      a = nxtc();
      b = nxtc();
      regs[a] %= regs[b];
      goto run_prog;
    instr_13: // => Mod reg %= byte
      a = nxtc();
      b = nxtc();
      regs[a] %= b;
      goto run_prog;
    instr_14: // => Swap reg <-> reg
      a = nxtc();
      b = nxtc();
      c = regs[a];
      regs[a] = regs[b];
      regs[b] = c;
      goto run_prog;
    instr_15: // => Loop reg
      a = nxtc();
      regs[7] = regs[a];
      regs[8] = progaddr;
      regs[9] = 0;
      goto run_prog;
    instr_16: // => Loop byte
      a = nxtc();
      regs[7] = a;
      regs[8] = progaddr >> 8;
      regs[9] = progaddr & 0xFF;
      regs[10] = 0;
      goto run_prog;
    instr_17: // => Loop end
      regs[10]++;
      if (regs[10] < regs[7]) {progaddr = word(regs[8], regs[9]);}
      goto run_prog;
    instr_18: // => Push reg
      a = nxtc();
      b = 1535 - regs[6];
      pRAM[b] = regs[a];
      regs[6]++;
      regs[a] = 0;
      goto run_prog;
    instr_19: // => Pop reg
      regs[6]--;
      a = nxtc();
      b = 1535 - regs[6];
      regs[a] = pRAM[b];
      goto run_prog;
    instr_20: // => Push all
      a = 1535 - regs[6];
      for (byte pshlp = 0; pshlp < 11; pshlp++) {if (pshlp != 6) {pRAM[a-pshlp] = regs[pshlp]; regs[pshlp] = 0;}}
      regs[6] += 11;
      goto run_prog;
    instr_21: // => Pop all
      a = 1536 - regs[6];
      for (byte poplp = 0; poplp < 11; poplp++) {if (poplp != 4) {regs[10-poplp] = pRAM[a+poplp];}}
      regs[6] -= 11;
      goto run_prog;
    instr_22: // => Jmp equal
      a = nxtc();
      b = nxtc();
      if (regs[4] == regs[5]) {progaddr = word(a, b);}
      goto run_prog;
    instr_23: // => Jmp less then
      a = nxtc();
      b = nxtc();
      if (regs[4] < regs[5]) {progaddr = word(a, b);}
      goto run_prog;
    instr_24: // => Jmp greater then
      a = nxtc();
      b = nxtc();
      if (regs[4] > regs[5]) {progaddr = word(a, b);}
      goto run_prog;
    instr_25: // => Jmp less or equal then
      a = nxtc();
      b = nxtc();
      if (regs[4] <= regs[5]) {progaddr = word(a, b);}
      goto run_prog;
    instr_26: // => Jmp greater or equal then
      a = nxtc();
      b = nxtc();
      if (regs[4] >= regs[5]) {progaddr = word(a, b);}
      goto run_prog;
    instr_27: // => Jmp not equal
      a = nxtc();
      b = nxtc();
      if (regs[4] != regs[5]) {progaddr = word(a, b);}
      goto run_prog;
    instr_28: // => Increase reg by one
      a = nxtc();
      regs[a]++;
      goto run_prog;
    instr_29: // => Decrease reg by one
      a = nxtc();
      regs[a]--;
      goto run_prog;
#ifdef PAUSE_CODE
    instr_30: // => Delay millis reg
      a = nxtc();
      delay(regs[a]);
      goto run_prog;
    instr_31: // => Delay millis byte
      a = nxtc();
      delay(a);
      goto run_prog;
    instr_32: // => Delay micros reg
      a = nxtc();
      delayMicroseconds(regs[a]);
      goto run_prog;
    instr_33: // => Delay micros byte
      a = nxtc();
      delayMicroseconds(a);
      goto run_prog;
#endif
#ifdef PIN_CTRL
    instr_34: // => DDRB reg
      a = nxtc();
      DDRB = regs[a];
      goto run_prog;
    instr_35: // => DDRB byte
      a = nxtc();
      DDRB = a;
      goto run_prog;
    instr_36: // => DDRC reg
      a = nxtc();
      DDRC = regs[a];
      goto run_prog;
    instr_37: // => DDRC byte
      a = nxtc();
      DDRC = a;
      goto run_prog;
    instr_38: // => DDRD reg
      a = nxtc();
      DDRD = regs[a];
      goto run_prog;
    instr_39: // => DDRD byte
      a = nxtc();
      DDRD = a;
      goto run_prog;
    instr_40: // => PORTB reg
      a = nxtc();
      PORTB = regs[a];
      goto run_prog;
    instr_41: // => PORTB byte
      a = nxtc();
      PORTB = a;
      goto run_prog;
    instr_42: // => PORTC reg
      a = nxtc();
      PORTC = regs[a];
      goto run_prog;
    instr_43: // => PORTC byte
      a = nxtc();
      PORTC = a;
      goto run_prog;
    instr_44: // => PORTD reg
      a = nxtc();
      PORTD = regs[a];
      goto run_prog;
    instr_45: // => PORTD byte
      a = nxtc();
      PORTD = a;
      goto run_prog;
    instr_46: // => PINB reg
      a = nxtc();
      regs[a] = PINB;
      goto run_prog;
    instr_47: // => PINC reg
      a = nxtc();
      regs[a] = PINC;
      goto run_prog;
    instr_48: // => PIND reg
      a = nxtc();
      regs[a] = PIND;
      goto run_prog;
#ifdef ANLG_CTRL
    instr_49: // => Analog out reg
      a = nxtc();
      analogWrite(regs[0], regs[a]);
      goto run_prog;
    instr_50: // => Analog out byte
      a = nxtc();
      analogWrite(regs[0], a);
      goto run_prog;
    instr_51: // => Analog in reg
      a = nxtc();
      regs[a] = analogRead(regs[0]);
      goto run_prog;
#endif
#endif
#ifdef EXTRA_MATH
    instr_52: // => Right shift reg reg
      a = nxtc();
      b = nxtc();
      regs[a] >>= regs[b];
      goto run_prog;
    instr_53: // => Right shift reg byte
      a = nxtc();
      b = nxtc();
      regs[a] >>= b;
      goto run_prog;
    instr_54: // => Left shift reg reg
      a = nxtc();
      b = nxtc();
      regs[a] <<= regs[b];
      goto run_prog;
    instr_55: // => Left shift reg byte
      a = nxtc();
      b = nxtc();
      regs[a] <<= b;
      goto run_prog;
    instr_56: // => And reg &= reg
      a = nxtc();
      b = nxtc();
      regs[a] &= regs[b];
      goto run_prog;
    instr_57: // => And reg &= byte
      a = nxtc();
      b = nxtc();
      regs[a] &= b;
      goto run_prog;
    instr_58: // => Or reg |= reg
      a = nxtc();
      b = nxtc();
      regs[a] |= regs[b];
      goto run_prog;
    instr_59: // => Or reg |= byte
      a = nxtc();
      b = nxtc();
      regs[a] |= b;
      goto run_prog;
    instr_60: // => Xor reg ^= reg
      a = nxtc();
      b = nxtc();
      regs[a] ^= regs[b];
      goto run_prog;
    instr_61: // => Xor reg ^= byte
      a = nxtc();
      b = nxtc();
      regs[a] ^= b;
      goto run_prog;
    instr_62: // => Not reg ~= byte
      a = nxtc();
      regs[a] = ~regs[a];
      goto run_prog;
#endif
}
1 Like
2

Nice effort to reinvent the wheel!
But is the goto really needed?
Why not

while (!endProgram) {
    blabla;
}
3

@build_1971
Thanks!,
And because the code has to return to that address from all different locations.

e.g.
label "instr_1:" needs to pick up the next instruction after it.

Not sure what you mean otherwise.

label "run_prog:" should really be called next_instr, for next instruction.

4

Why "goto?
Why not switch/case?

5

he goto version turned out have more performance then the switch/case.
But I do have the switch/case one.:wink:

6

As an aside this is the faster method for the fib(6000).
The one that did the 68460 microseconds benchmark.
The other one only did 90048 microseconds unoptimized.

const byte program[] PROGMEM = {
  MOVb, 0, 1,         // A=1
  MOVb, 1, 1,         // B=1
  
  BEGb, 24,           // Loop till 24   -----
  PUSH, 7,            // Push loop till reg |
  PUSH, 8,            // Push loop address  |
  PUSH, 9,            // Push loop counter  |
  PUSH, 10,           // Push loop counter  |
  BEGb, 250,          // Loop till 250  --- |
                      //                  | |
  ADDr, 0, 1,         // A=A+1            | |
  SWAP, 0, 1,         // B=A & A=B        | |
                      //                  | |
  LOOP,               // Loop end       <-- |
  POP, 10,            // Pop loop counter   |
  POP, 9,             // Pop loop counter   |
  POP, 8,             // Pop loop address   |
  POP, 7,             // Pop loop till reg  |
  LOOP,               // Loop end       <----
  
  STOP,               // Program end
};

The "#defines" are if you want a lighter version.

I try to have comments to explain things. :smile:
Thanks.

7

If you want performance, why not code in assembler, or C/C++?

8

I don't have experience for that, plus other posts on this forum discourage it.
In the way it won't necessarily speed it up.

Maybe in a few years time......

9

No, I mean, why don't you code your benchmark in assembler or C++, if performance is the objective?

You're going to be limited in the size of interpreted code, so just leave it in flash memory, but if you're determined to use RAM, hint, "memcpy_P"

10

I suggest you read this: https://www.arduino.cc/en/terms-conditions , I think section 5 is particularly relevant.

3 Likes
11

Anything to be gained by having the register array and the program counter local to the interpreter function?

12

Thanks @PerryBebbington for the terms-conditions.
Will remember.

@anon56112670
Implemented memcpy_P, code below.

void setup() {
  randomSeed(analogRead(6));
  Serial.begin(9600);
  memcpy_P(pRAM, program, sizeof(program));
  
  time = micros();
  BC256();
  Serial.println(micros()-time);
}

No, I myself don't know why this isn't in the interpreter function and was considering moving it inside the function.

13

I'm a little puzzled about how a BEGr and a BEGb are handled.
BEGr looks like it will encounter problems...later

14

Here is a code update.
BC256-1_0.ino (13.5 KB)

I moved all but register array as this slowed down speed.
Also register array wouldn't work for me in the function,
however your suggestion has sped it up by ~14 milliseconds. :hugs:

15

Because you forgot to zero it?

16

BEGr and BEGb are handled as follows below.

Say BEGr, 0, is called this points to regs[0] is the maxium number achieved by the loop.
We then copy regs[0] into regs[7].
Afterwards we save the program address to regs[8] and regs[9].
Then when we meet LOOP we increment regs[10] by one and compare if it's less or equal to regs[7].
The process is the same for BEGb except the value copied into regs[7] is a byte.

regs[10] has to be set to 0 manually, a bug I realized when explaining the procedure. :wink:

Pls report any other problems.

17

I already knew the problem, you just had to explain it to your rubber duck. :wink:

You asked for feedback, so...

One of the key advantages of an interpreted language are lost if you have to compile it to run it.
(I assume that this is a test-bed, and that the interactive part of program entry and running is under development, however this is likely to be much more complex than the interpreter, further eating into the limited RAM)

Another advantage would be that the interpreter should insulate the user from the underlying software and hardware, but it would be simple to write an interpreted program that could crash the interpreter, because accesses to and from the "regs" array are unchecked.

18

I think I'll allow the user to manually set regs[10] so they can count from something other than 0, like 23 or 10.

You no rubber duck, you have been very helpful to the project.
As an aside the uno does this in c++ in about 4152 microseconds.
Making the interpreter roughly ~18 times slower.
Don't really know how to calculate the actual interpreter instruction speed for a proper comparison.

Yes, it is I might wind the pRAM variable to 1280 bytes, to fit it all.

Thanks for the feedback.

19

Made any projects with the interpreter?

20

@anon56112670
Created basic interactive part of the interpreter.
Here is the code.

const byte program[] PROGMEM = {
  'A','=','1','0',
  'B','=','A',
  'B','+','A',
  'A','+','2','0',
  'B','-','A',
  'A','-','3','0',
  'B','*','A',
  'A','*','4','0',
  'B','/','A',
  'A','/','5','0',
  'B','%','A',
  'A','%','6','0',
  'A','_','B',
  'B','>','A',
  'A','<','7','0',
  'B','&','A',
  'A','&','8','0',
  'B','|','A',
  'A','|','9','0',
  'B','^','A',
  'A','^','1','0','0',
  'B','?','A',
  'A','?','1','1','0',
  'S',
};

byte pRAM[1280];

byte regs[11]; // A = [0], B = [1], C = [2], D = [3], ? = [4], ?? = [5], sp = [6], lpt = [7], lpa = [8], lpa = [9], lpc = [10]

unsigned long time;

void setup() {
  randomSeed(analogRead(6));
  Serial.begin(9600);
  memcpy_P(pRAM, program, sizeof(program));
  
  time = IBC256();
  for (int lp = 0; lp < time; lp++) {
    Serial.print(pRAM[lp]); Serial.print(",");
  }
  Serial.println();
  Serial.println(time);
}

void loop() {
  
}

// ==================================================================
// BC256 --Byte Code 256-- INTERACTIVE (1.0) "BETA"
// ==================================================================
bool isReg(byte byteisreg) {return (byteisreg >= 'A' and byteisreg <= 'K');}
bool isNum(byte byteisreg) {return (byteisreg >= '0' and byteisreg <= '9');}

int IBC256() {
  int progaddr = 0, interaddr = 0;
  byte a = 0, b = 0, c = 0;
  #define nxtc() pRAM[progaddr++]

  while(pRAM[progaddr] != 0) {
    c = nxtc();
    if (isReg(c)) {
      c = nxtc();
      a = pRAM[progaddr-2] - 'A';
      if (isReg(nxtc())) {
        b = pRAM[progaddr-1] - 'A';
        if (c == '=') {pRAM[interaddr++] = MOVr;}
        else if (c == '+') {pRAM[interaddr++] = ADDr;}
        else if (c == '-') {pRAM[interaddr++] = SUBr;}
        else if (c == '*') {pRAM[interaddr++] = MULr;}
        else if (c == '/') {pRAM[interaddr++] = DIVr;}
        else if (c == '%') {pRAM[interaddr++] = MODr;}
        else if (c == '_') {pRAM[interaddr++] = SWAP;}
        else if (c == '>') {pRAM[interaddr++] = RSHFTr;}
        else if (c == '<') {pRAM[interaddr++] = LSHFTr;}
        else if (c == '&') {pRAM[interaddr++] = ANDr;}
        else if (c == '|') {pRAM[interaddr++] = ORr;}
        else if (c == '^') {pRAM[interaddr++] = XORr;}
        else if (c == '?') {pRAM[interaddr++] = RNDr;}
      } else {
        b = 0;
        progaddr--;
        while (isNum(pRAM[progaddr])) {
          b *= 10; 
          b += nxtc() - '0';
        }
        if (c == '=') {pRAM[interaddr++] = MOVb;}
        else if (c == '+') {pRAM[interaddr++] = ADDb;}
        else if (c == '-') {pRAM[interaddr++] = SUBb;}
        else if (c == '*') {pRAM[interaddr++] = MULb;}
        else if (c == '/') {pRAM[interaddr++] = DIVb;}
        else if (c == '%') {pRAM[interaddr++] = MODb;}
        else if (c == '>') {pRAM[interaddr++] = RSHFTb;}
        else if (c == '<') {pRAM[interaddr++] = LSHFTb;}
        else if (c == '&') {pRAM[interaddr++] = ANDb;}
        else if (c == '|') {pRAM[interaddr++] = ORb;}
        else if (c == '^') {pRAM[interaddr++] = XORb;}
        else if (c == '?') {pRAM[interaddr++] = RNDb;}
      }
      pRAM[interaddr++] = a;
      pRAM[interaddr++] = b;
    }
    if (c == 'S') {
      pRAM[interaddr++] = STOP;
    }
  }
  return interaddr;
}

Any thought on it?