CPU Design: Эзотерический язык LMCode / forpes.ru

Главная
CPU Design: Эзотерический язык LMCode

CPU Design: Эзотерический язык LMCode +14

25.10.2018 19:43

demsp 4 2000 Источник

Часть I
Часть II
Часть III
Часть IV

Эта статья посвящена созданию интерпретатора некого эзотерического языка LMCode, в основе которого лежит архитектура Little Man Computer. О Little Man Computer можно прочитать в предыдущих статьях.

Пусть команде INP соответствует ,
команде OUT соответствует .
команде ADD соответствует +
команде SUB соответствует —
команде STA соответствует ~
команде LDA соответствует ^

Напишем программу, которая загружает число из устройства ввода в аккумулятор, сохраняет число в памяти, прибавляет число из памяти к аккумулятору (удваивает число), и выводит удвоенное число в устройство вывода.

На ассемблере LMC эта программа будет выглядеть так (начальной ячейкой пусть будет 20)

 INP
 STA 20
 ADD 20 
 OUT

На языке LMCode эта программа будет выглядеть как ,~+.
В нашей LMCode-машине память кодов и память данных разделены (гарвардская архитектура), создадим строку command_mem для загрузки LMCode-кода. Строка command_mem будет представлять память команд. Также создадим массив данных data_mem, который будет представлять память данных.

Загрузим в 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;
}

При загрузке в устройство ввода числа 123 получаем число 246.
Проверить можно в oline ide ideone.com

Добавим команды для

перехода к следующей ячейке >
перехода к следующей ячейке <

При обработке символа > будем увеличивать индекс j массива данных data_mem

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

При обработке символа < будем уменьшать индекс j массива данных data_mem

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

Для прыжка вперёд по команде ? будем осуществлять переход на метку !
Для этого будем пропускать все символы между ? и !

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

Для сравнения напишем программу, в которой число 5 вносится в пять ячеек подряд

#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;
}

В итоге получим массив 5 5 5 5 5 0 0 0 0 0
ideone.com

и ту же самую программу, в которой несколько шагов вперёд пропускаются командой безусловного перехода ,~>~?>~>~>~!

Получим массив 5 5 0 0 0 0 0 0 0 0
ideone.com

Добавим флаг pzflag

Флаг будет поднят, только если число в аккумуляторе больше или равно нулю.

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

Переход вперёд по условию pzflag == 1 будем осуществлять командами { и }

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

Напишем программу, которая выводит максимальное число (из двух возможных).

Чтобы пропустить шаги по загрузке чисел в память, инициализируем эти числа
data_mem[0]=3 и 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

Для прыжка назад добавим переменную pz_prev.

Если текущим символом является {, то «поднимаем флаг» pz_prev

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

Если метка } предшествует команде {, значит надо совершать прыжок назад

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

Напишем программу, которая выводит чётные числа с 10 до 0.

Загрузим числа 10 и 2 в массив data_mem, далее, пока число в acc больше или равно нулю, будем от 10 отнимать 2 и выводить результат

#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

Для того, чтобы перемножить два числа A и B, необходимо A раз к B прибавить B.

Будем в цикле на каждой итерации вычитать из A единицу, и, пока А не ноль, прибавлять В к В.

LMCode-программа }>>>^<+>~<<< ^>-<~{>>>^. перемножает числа А+1 и В, т.е. один множитель необходимо заведомо уменьшить на единицу.

Так происходит потому, что цикл завершится только тогда, когда в acc окажется -1.

Например, умножим 5 на 5.

Для этого предварительно поместим необходимые значения в data_mem

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

ideone.com

Добавим безусловные переходы назад.

Для этого добавим переменную prev.

Также добавим переходы вперёд/назад по условию acc=0. Для таких переходов создадим флаг zflag и переменную z_prev.

Переходы по условию zflag == 1 будем осуществлять командами ( и )
Перемножим 5 и 5 используя безусловный переход и переход по условию zflag == 1.

Предварительно поместим необходимые значения в data_arr

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

LMCode-прогамме !>>>^<+>~<<<^>-<~(?)>>>^. соответствует ассемблерная прогамма

 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

Код на Си

#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

Вообще, флаги можно было не создавать, а вместо них сразу проверять, чему равно число в аккумуляторе.

Проверим, как вычисляются числа Фибоначчи.

#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

Комментарии (4)

Sabubu
26.10.2018 08:59
#19284291
+1
Можно, я покритикую код и дам советы по улучшению? Раз уж вы его опубликовали.

Код пишется для людей, и надо стараться, чтобы он был простой и логичный, легко читался. У вас это требование не выполняется.

Во-первых, код раскособочило, то ли из-за отсутствия выравнивания, то ли из-за использования табуляции. В первом случае стоит отформатировать код средствами вашей IDE либо вручную, во втором — сделать замену табов на пробелы

Во-вторых, переменным надо давать понятные, осмысленные имена, вроде:
```
int profit = income - expense;
int mem_used = thread.owner_process.memory_table.get_total_size();
```
Смотрите, как читабельно: прибыль равна доход минус расход. Хороший код так и выглядит, как читабельный текст.

У вас же названия переменных ничего не говорят:

— data_arr — любая переменная хранит данные, потому слово data ничего не значит. arr тоже не добавляет смысла. Советую взять осмысленное название, вроде memory или virtual_memory
— pzf — вообще хрен расшифруешь. Если это флаг, то стоит подумать над названием получше и добавить подробный комментарий с описанием перед переменной.

Избегайте ничего не говорящих слов вроде var, val, tmp, data, array.

Названия i и j не годятся, так как у вас большой объем кода и надо постоянно прокручивать его в начало, чтобы посмотреть, что они значат.

Также, вместо портянки if/else лучше использовать switch().

Комментариев в коде явно не хватает, хотя бы для переменных.

> while(str_arr[i] != '}' )
> i++;
Тут ошибка, возможен потенциально бесконечный цикл с крашем программы при выходе за границу выделенной вирт. памяти.

Этот код встречается часто и стоит вынести его в отдельную функцию seek_char() с проверкой на конец строки.

Пока, к сожалению, код нечитабелен. Вы потратили много времени на подготовку и написание статьи, будет жалко, если из-за плохого кода ваши усилия пропадут зря. Советую исправить.

demsp Автор
26.10.2018 10:41
#19284849
Названия i и j не годятся

Также, вместо портянки if/else лучше использовать switch().

Согласен, но для шаблона я использовал код интерпретатора Brainfuck из Википедии.

> while(str_arr[i] != '}' )
> i++;
Тут ошибка, возможен потенциально бесконечный цикл с крашем программы при выходе за границу выделенной вирт. памяти.

Но тут программист сам уже должен следить за тем, чтобы скобки/переходы были правильно расставлены.
Спасибо.
1. domix32
  26.10.2018 13:48
  #19286195
  То есть бесконечная «компиляция» вас устраивает?

ay8910
27.10.2018 19:24
#19291523
Предыдущие части почему то не открываются…

CPU Design: Эзотерический язык LMCode +14

Комментарии (4)

Sabubu

demsp Автор

domix32

ay8910