CPU Design: The Esoteric Language LMCode

Part I
Part II
Part III
Part IV
Part V

The fourth part of the cycle is devoted to creating an interpreter of a certain esoteric language LMCode, which is based on the architecture of Little Man Computer , which can be found in previous articles.

• Let the INP command match ,
• OUT command matches .
• ADD command corresponds to +
• SUB command corresponds to -
• STA command matches ~
• LDA team corresponds ^

We write a program that loads a number from an input device into a battery, stores a number in memory, adds a number from memory to a battery (doubles the number), and outputs a double number to an output device.
')
On the LMC assembler, this program will look like this (the initial cell will be 20)

INP STA 20 ADD 20 OUT 

In LMCode, this program will look like , ~ +.
In our LMCode machine, the code memory and data memory are separated (Harvard architecture), we create the command_mem line to load the LMCode code. The command_mem string will represent the command memory. We will also create an array of data data_mem that will represent the data memory.

Let's load the program ~ + in the command_mem .

 #include <stdio.h> int main(void) { int i=0; //    int j=0; //    int acc = 0; // char command_mem[100] = ",~+."; //  int data_mem[10]={0}; //   while (command_mem[i] != '\0') { if (command_mem[i]==',') //     scanf("%d", &acc); if (command_mem[i]=='+') //    data_mem acc=acc+data_mem[j]; //   if (command_mem[i]=='~') //     data_mem[j]=acc; //    if (command_mem[i]=='.') //       printf("Output: %d",acc); i++; //    } //    printf("\n"); //    for (int k = 0; k<10; k++) printf("%d ", data_mem[k]); return 0; } 

When loading the number 123 into the input device, we get the number 246 .
You can check in oline ide ideone.com

Add commands for

• go to the next cell >
• go to previous cell <

When processing the > symbol , we will increase the j index of the data_mem data array

 if(command_mem[i]=='>') j++; 

When processing the symbol < we will reduce the index j of the data array data_mem

 if(command_mem[i]=='<') j--; 

To jump forward with the team ? We will make the transition to the label !
For this we will skip all the characters between ? and !

 if(command_mem[i]=='?') { while(command_mem[i] != '!' ) { i++; } } 

For comparison, we write a program in which the number 5 is entered in five cells in a row

 #include <stdio.h> int main(void) { int i=0; //    int j=0; //    int acc = 0; // char command_mem[100] = ",~>~>~>~>~"; //  int data_mem[10]={0}; //   while (command_mem[i] != '\0') { if (command_mem[i]==',') //     scanf("%d", &acc); if (command_mem[i]=='+') //    data_mem acc=acc+data_mem[j]; //   if (command_mem[i]=='~') //     data_mem[j]=acc; //    if (command_mem[i]=='.') //       printf("Output: %d",acc); if(command_mem[i]=='>') //     j++; if(command_mem[i]=='<') //     j--; if(command_mem[i]=='?') { //    ! while(command_mem[i] != '!') i++; } i++; //    } //    printf("\n"); //    for (int k = 0; k<10; k++) printf("%d ", data_mem[k]); return 0; } 

As a result, we obtain an array of 5 5 5 5 5 0 0 0 0 0
ideone.com

and the same program, in which several steps forward are skipped by the unconditional jump command , ~> ~?> ~> ~> ~!

Get an array of 5 5 0 0 0 0 0 0 0 0
ideone.com

Add the pzflag flag

The flag will be raised only if the number in the battery is greater than or equal to zero.

  if(acc>=0){ pzflag=1;} else { pzflag=0;} 

Moving forward by the condition pzflag == 1 will be done with the commands { and }

 if(command_mem[i]=='{') && (pzflag==1){ while(command_mem[i] != '}' ) i++; } 

We write a program that displays the maximum number (out of two possible).

To skip the steps of loading numbers into memory, initialize these numbers
data_mem [0] = 3 and data_mem [1] = 5

 #include <stdio.h> int main(void) { int i=0; //    int j=0; //    int acc = 0; int pzflag = 1; //  acc>=0 char command_mem[100] = "^>-{^?}<^!."; //  int data_mem[10]={0}; data_mem[0]=3; //   data_mem[1]=5; while ( command_mem[i] != '\0') { if(command_mem[i]==',') //     scanf("%d", &acc); if(command_mem[i]=='+') //    data_mem acc=acc+data_mem[j]; //   if(command_mem[i]=='-') //   data_mem acc=acc-data_mem[j]; //   if(command_mem[i]=='>') //      j++; if(command_mem[i]=='<') //     j--; if(command_mem[i]=='~') //     data_mem[j]=acc; //    if(command_mem[i]=='^') //    data_mem acc=data_mem[j]; //   if(command_mem[i]=='.') { //       printf("Output: %d",acc); printf(" "); }; if(command_mem[i]=='?') { //    ! while(command_mem[i] != '!') i++; } if (command_mem[i]=='{' && pzflag==1) { //    acc>=0 while(command_mem[i] != '}') i++; } if(acc>=0){ //  ,  acc>=0 pzflag=1; } else { pzflag=0; } i++; //    } //    printf("\n"); //    for (int k = 0; k<10; k++) printf("%d ", data_mem[k]); return 0; } 

ideone.com

To jump back, add the variable pz_prev .

If the current character is { , then “raise the flag” pz_prev

 if (command_mem[i]=='}') pz_prev=1; 

If the label } precedes the command { , then you must jump back

 if (command_mem[i]=='{' && pzflag==1 && pz_prev==1) { while(command_mem[i] != '}') i--; } 

We write a program that displays even numbers from 10 to 0 .

Load the numbers 10 and 2 into the data_mem array, then, while the number in acc is greater than or equal to zero, we will subtract 2 from 10 and display the result

 #include <stdio.h> int main(void) { int i=0; //    int j=0; //    int acc = 0; int pzflag = 1; //  acc>=0 int pz_prev=0; //     acc>=0 char command_mem[100] = "}^.>-<~{"; //     10  0 int data_mem[10]={0}; data_mem[0]=10; //   data_mem[1]=2; while ( command_mem[i] != '\0') { if(command_mem[i]==',') //     scanf("%d", &acc); if(command_mem[i]=='+') //    data_mem acc=acc+data_mem[j]; //   if(command_mem[i]=='-') //   data_mem acc=acc-data_mem[j]; //   if(command_mem[i]=='>') //      j++; if(command_mem[i]=='<') //      j--; if(command_mem[i]=='~') //     data_mem[j]=acc; //    if(command_mem[i]=='^') //    data_mem acc=data_mem[j]; //   if(command_mem[i]=='.') { //       printf("Output: %d",acc); printf(" "); }; if (command_mem[i]=='}') //  ? pz_prev=1; if(command_mem[i]=='?') { //    ! while(command_mem[i] != '!') i++; } if (command_mem[i]=='{' && pzflag==1 && pz_prev==0) { //   while(command_mem[i] != '}') //   acc>=0 i++; } if (command_mem[i]=='{' && pzflag==1 && pz_prev==1) { //   while(command_mem[i] != '}') //   acc>=0 i--; } if(acc>=0){ //  ,  acc>=0 pzflag=1;} else { pzflag=0;} //printf("i=%d",i);printf(" "); i++; //    } //    printf("\n"); //    for (int k = 0; k<10; k++) printf("%d ", data_mem[k]); return 0; } 

ideone.com

In order to multiply two numbers A and B , it is necessary A to add B to A times.

In the loop at each iteration, we will subtract from A a unit, and, while A is not zero, add B to B.

LMCode program } >>> ^ <+> ~ <<< ^> - <~ {>>> ^. multiplies the numbers A + 1 and B , i.e. one factor must be deliberately reduced by one.

This happens because the cycle will end only when the acc is -1 .

For example, multiply 5 by 5 .

To do this, first place the necessary values ​​in the data_mem

  data_mem[0]=4; data_mem[1]=1; data_mem[2]=5; 

ideone.com

Add unconditional transitions back .

To do this, add the variable prev .

Also add transitions forward / backward by the condition acc = 0 . For such transitions, create a flag zflag and a variable z_prev .

Transitions by the condition zflag == 1 will be performed by the commands (s )
Multiply 5 and 5 using the unconditional transition and the transition by the condition zflag == 1 .

Pre-put the necessary values ​​in data_arr

  data_arr[0]=5; data_arr[1]=1; data_arr[2]=5; 

LMCode-program ! >>> ^ <+> ~ <<< ^> - <~ (?) >>> ^. corresponds to the assembler program

  INP STA 20 INP STA 21 INP STA 22 LDA 23 ADD 22 STA 23 LDA 20 SUB 21 STA 20 BRZ 14 BRA 06 LDA 23 OUT HLT 

C code

 #include <stdio.h> int main(void) { int i=0; //    int j=0; //    int acc = 0; int pzflag = 1; //  acc>=0 int zflag =1; //  acc==0 int pz_prev=0; //     acc>=0 int z_prev=0; //     acc==0 int prev=0; //    char command_mem[100] ="!>>>^<+>~<<<^>-<~(?)>>>^."; int data_mem[10]={0}; data_mem[0]=5; //   data_mem[1]=1; data_mem[2]=5; while ( command_mem[i] != '\0') { if(command_mem[i]==',') //     scanf("%d", &acc); if(command_mem[i]=='+') //    data_mem acc=acc+data_mem[j]; //   if(command_mem[i]=='-') //   data_mem acc=acc-data_mem[j]; //   if(command_mem[i]=='>') //      j++; if(command_mem[i]=='<') //      j--; if(command_mem[i]=='~') //     data_mem[j]=acc; //    if(command_mem[i]=='^') //    data_mem acc=data_mem[j]; //   if(command_mem[i]=='.') { //       printf("Output: %d",acc); printf(" "); }; if (command_mem[i]=='}') //  ? pz_prev=1; if (command_mem[i]==')') //  ? z_prev=1; if (command_mem[i]=='!') //  ? prev=1; //    if (command_mem[i]=='?' && prev==0) { while(command_mem[i] != '!') i++; } //    if (command_mem[i]=='?' && prev==1) { while(command_mem[i] != '!') i--; } //     acc=0 if (command_mem[i]=='(' && zflag==1 && z_prev==0) { while(command_mem[i] != ')') i++; } //     acc=0 if (command_mem[i]=='(' && zflag==1 && z_prev==1) { while(command_mem[i] != ')') i--; } //     acc>=0 if (command_mem[i]=='{' && pzflag==1 && pz_prev==0) { while(command_mem[i] != '}') i++; } //     acc>=0 if (command_mem[i]=='{' && pzflag==1 && pz_prev==1) { while(command_mem[i] != '}') i--; } //  if(acc>=0){ pzflag=1;} else { pzflag=0;} if(acc==0){ zflag=1;} else { zflag=0;} //printf("i=%d",i);printf(" "); i++; //    } //    printf("\n"); //    for (int k = 0; k<10; k++) printf("%d ", data_mem[k]); return 0; } 

ideone.com

In general, the flags could not be created, but instead immediately checked, what is the number in the battery.

Check how the Fibonacci numbers are calculated.

 #include <stdio.h> int main(void) { int i=0; //    int j=0; //    int acc = 0; int pzflag = 1; //  acc>=0 int zflag =1; //  acc==0 int pz_prev=0; //     acc>=0 int z_prev=0; //     acc==0 int prev=0; //    char command_mem[100] ="}>>^>+.~<+.~<<^>-<~{"; int data_mem[10]={0}; data_mem[0]=5; //   data_mem[1]=1; data_mem[2]=1; while ( command_mem[i] != '\0') { if(command_mem[i]==',') //     scanf("%d", &acc); if(command_mem[i]=='+') //    data_mem acc=acc+data_mem[j]; //   if(command_mem[i]=='-') //   data_mem acc=acc-data_mem[j]; //   if(command_mem[i]=='>') //      j++; if(command_mem[i]=='<') //      j--; if(command_mem[i]=='~') //     data_mem[j]=acc; //    if(command_mem[i]=='^') //    data_mem acc=data_mem[j]; //   if(command_mem[i]=='.') { //       printf("Output: %d",acc); printf(" "); }; if (command_mem[i]=='}') //  ? pz_prev=1; if (command_mem[i]==')') //  ? z_prev=1; if (command_mem[i]=='!') //  ? prev=1; //    if (command_mem[i]=='?' && prev==0) { while(command_mem[i] != '!') i++; } //    if (command_mem[i]=='?' && prev==1) { while(command_mem[i] != '!') i--; } //     acc=0 if (command_mem[i]=='(' && zflag==1 && z_prev==0) { while(command_mem[i] != ')') i++; } //     acc=0 if (command_mem[i]=='(' && zflag==1 && z_prev==1) { while(command_mem[i] != ')') i--; } //     acc>=0 if (command_mem[i]=='{' && pzflag==1 && pz_prev==0) { while(command_mem[i] != '}') i++; } //     acc>=0 if (command_mem[i]=='{' && pzflag==1 && pz_prev==1) { while(command_mem[i] != '}') i--; } //  if(acc>=0){ pzflag=1;} else { pzflag=0;} if(acc==0){ zflag=1;} else { zflag=0;} //printf("i=%d",i);printf(" "); i++; //    } //    printf("\n"); //    for (int k = 0; k<10; k++) printf("%d ", data_mem[k]); return 0; } 

ideone.com

The article about the LMCode language on esolang.org is here.