Недавно мне пришла в голову мысль взяться за старое, а именно, продолжить исследовать возможность написания собственного транслятора под собственный язык программирования. Но, первая моя попытка создания собственного языка программирования потерпела крах: я, к сожалению, потерял часть первоначального проекта по созданию лисп-подобного языка, а начинать с нуля после публикации статьи про создание языка было бы бессмысленно.
Новый импульс я получил после того, как наткнулся на нечто интересное и действительно захватывающее…
Как-то давно я интересовался забавным языком программирования под названием Forth.
Данный язык программирования славится тем, что имеет крайне простую грамматику (описание ее предельно просто), а также Forth известен еще как и один из успешных стековых языков программирования. Более того, этот язык программирования интересен еще как язык промежуточного типа — его транслятор, не является ни компилятором, ни интерпретатором, а занимает некое среднее положение (данный факт, хотя и несколько сомнителен, но определенно интересен). Именно, такое сочетание весьма любопытных свойств мотивировало меня на попытку написания своего Forth-транслятора, причем настолько, что я захотел изучить ряд реализаций и просто немного почитать о данном языке…
Моя попытка реализации Forth-транслятора не привела к успеху, поскольку у меня в голове так и не сложился целостный подход к его алгоритму, и не было ключевой идеи о том, как будет разбираться код на Forth и во что он будет транслироваться. В бесчисленных пробах и ошибках, я начал отчаиваться, просеивая разного рода и качества материал, и тут внезапно я натыкаюсь на очень интересную статью про Forth-процессор! И вот тут я реально загорелся идеей своего виртуального процессора на D!
Я читал статью про J1 — Forth-процессор, который написан на Verilog (занимает около 200 строчек кода) и который является стековым процессором. Данный процессор устроен весьма просто: два стека, способные поместить в себя 33 (стек данных) и 32 (стек возвратов) 16-разрядных элемента, небольшая память под 16-разрядные беззнаковые числа. Никаких внутренних регистров, никакого запутанного АЛУ, никакого скрытого кэша!
J1, как процессор, поддерживает несколько различных типов инструкций и они также являются очень простыми. Всего инструкций, которые понимает J1, 5: загрузка литерала (т.е. числового беззнакового 16-разрядного значения) в стек данных, переход на заданный адрес в памяти, условный переход на заданный адрес в памяти, вызов процедуры по заданному адресу памяти и инструкции АЛУ (т.е. арифметико-логического устройства).
Инструкции для процессора представляют собой 16-разрядные числа без знака, в которых конкретные биты, как флаги, указывают тип команды процессора. Выглядят инструкции следующим образом:
Схема понимается достаточно просто:
- Литерал (literal). 15-бит устанавливается в 0, все остальные биты занимает само число, которое будет загружено в стек данных.
- Безусловный переход (jump). Три старших бита устанавливаются в 0, остальные биты занимает число, которое указывает адрес перехода.
- Условный переход (conditional jump). 2 старших бита установлены в 0, 13 бит установлен в 1, остальные биты занимает число, указывающее адрес перехода. Переход на адрес будет осуществлен только в том случае, если на вершине стека данных лежит 0.
- Вызов процедуры (call). 15-ый бит установлен в 0, 14-ый — в 1, 13-ый бит установлен в 0, остальные биты занимает число, указывающее адрес, по которому расположена процедура.
- Инструкции АЛУ (АЛУ). Вот тут остановимся подробнее ниже.
Инструкции АЛУ также представляют собой 16-разрядные беззнаковые числа, но имеют больше значимых битовых полей, по сравнению, с другими командами:
- Бит 15. Установлен в 0.
- Биты 14 и 13. Установлены в 1.
(таким образом, формируется префикс-указание команды АЛУ) - Бит 12 (флаг R->PC и RPC). Если установлен а 1, то число с вершины стека возвратов будет скопировано в процессорный счетчик команд.
- Биты с 11 по 8. Содержит число, указывающее тип команды АЛУ.
- Бит 7 (флаг T->N и TN). Если установлен в 1, то элемент с вершины стека данных копируется в элемент под вершиной.
- Бит 6 (флаг T->R и TR). Если установлен в 1, то элемент с вершины стека данных копируется на вершину стека возвратов.
- Бит 5 (флаг N->[T] и NTI). Если установлен в 1, то элемент под вершиной стека данных копируется в память по адресу, который представлен числом, лежащим на вершине стека данных.
- Бит 4. Не используется. Всегда 0, но можно использовать для увеличения количества команд АЛУ в своих версия J1.
- Биты 3 и 2 (флаг rstack). Содержат число, на которое смещается указатель стека возвратов при выполнении инструкций. Если это число — 1, тогда указатель увеличивается на 1; если число 2, то указатель уменьшается на 1.
- Биты 1 и 0 (флаг dstack). Содержат число, на которое смещается указатель стека данных при выполнении инструкций. Если это число — 1, тогда указатель увеличивается на 1; если число 2, то указатель уменьшается на 1.
Для понимания команд АЛУ введем обозначения: T — вершина стека данных, N — элемент под вершиной стека данных, R — вершина стека возвратов, depth — текущая глубина стека. Тогда, коды операций АЛУ с обозначениями самих операций дают следующую картину:
Операции АЛУ в J1 | |
Код операции | Операция |
| 0 | T (вершина стека) |
| 1 | N (элемент под вершиной стека) |
| 2 | T + N |
| 3 | T & N |
| 4 | T | N |
| 5 | T ^ N |
| 6 | ~T |
| 7 | N == T |
| 8 | N < T |
| 9 | N >> T |
| 10 | T — 1 |
| 11 | R (вершина стека возвратов) |
| 12 | [T] (чтение из памяти по адресу T) |
| 13 | N << T |
| 14 | depth (глубина стека) |
| 15 | Nu < T (беззнаковое сравнение) |
Данный процессор мы реализуем в виде класса, который будет содержать внутри себя всю основную логику работы процессора J1. При необходимости вы сможете подогнать его под себя.
Сначала импортируем модуль, в котором содержится все необходимое для конвертации типов, а также для удобства объявим некоторые псевдонимы:
import std.conv : to; // 16-разрядное беззнаковое целое alias int16 = short; // 16-разрядное беззнаковое целое alias uint16 = ushort;
После этого объявим внутри класса ряд перечислений, которые будут использованы для распознавания типов инструкций J1 и для выделения по маскам аргументов инструкций, а также укажем ряд переменных внутреннего состояния процессора:
enum RAM_SIZE = 32_768;
// стек данных
uint16[33] dataStack;
// стек вызовов
uint16[32] returnStack;
// память
uint16[RAM_SIZE] RAM;
// указатель на вершину стека данных
int16 dataPointer;
// указатель на вершину стека вызовов
int16 returnPointer;
// счетчик инструкций
uint16 programCounter;
// маски для различения типов инструкций j1
enum J1_INSTRUCTION : uint16
{
JMP = 0x0000,
JZ = 0x2000,
CALL = 0x4000,
ALU = 0x6000,
LIT = 0x8000
};
// маски для различения аргументов инструкций j1
enum J1_DATA : uint16
{
LITERAL = 0x7fff,
TARGET = 0x1fff
};
Теперь рассмотрим самую важную часть логики процессора — исполнение команд АЛУ:
// исполнение команд АЛУ
auto executeALU(uint16 instruction)
{
uint16 q;
uint16 t;
uint16 n;
uint16 r;
// вершина стека
if (dataPointer > 0)
{
t = dataStack[dataPointer];
}
// элемент под вершиной стека
if (dataPointer > 0)
{
n = dataStack[dataPointer - 1];
}
// предыдущий адрес возврата
if (returnPointer > 0)
{
r = returnStack[returnPointer - 1];
}
// увеличить счетчик инструкций
programCounter++;
// извлечение кода операции АЛУ
uint16 operationCode = (instruction & 0x0f00) >> 8;
// опознание операций
switch (operationCode)
{
case 0:
q = t;
break;
case 1:
q = n;
break;
case 2:
q = to!uint16(t + n);
break;
case 3:
q = t & n;
break;
case 4:
q = t | n;
break;
case 5:
q = t ^ n;
break;
case 6:
q = to!uint16(~to!int(t));
break;
case 7:
q = (t == n) ? 1 : 0;
break;
case 8:
q = (to!int16(n) < to!int16(t)) ? 1 : 0; break; case 9: q = n >> t;
break;
case 10:
q = to!uint16(t - 1);
break;
case 11:
q = returnStack[returnPointer];
break;
case 12:
q = RAM[t];
break;
case 13:
q = to!uint16(n << t);
break;
case 14:
q = to!uint16(dataPointer + 1u);
break;
case 15:
q = (n < t) ? 1 : 0;
break;
default:
break;
} // код действия с указателем на стек данных // (+1 - увеличить указатель, 0 - не трогать, -1 уменьшить (= 2 в двоичном коде))
uint16 ds = instruction & 0x0003; // код действия с указателем на стек возвратов // (+1 - увеличить указатель, 0 - не трогать, -1 уменьшить (= 2 в двоичном коде))
uint16 rs = (instruction & 0x000c) >> 2;
switch (ds)
{
case 1:
dataPointer++;
break;
case 2:
dataPointer--;
break;
default:
break;
}
switch (rs)
{
case 1:
returnPointer++;
break;
case 2:
returnPointer--;
break;
default:
break;
}
// флаг NTI
if ((instruction & 0x0020) != 0)
{
RAM[t] = n;
}
// флаг TR
if ((instruction & 0x0040) != 0)
{
returnStack[returnPointer] = t;
}
// флаг TR
if ((instruction & 0x0080) != 0)
{
dataStack[dataPointer-1] = t;
}
// флаг RPC
if ((instruction & 0x1000) != 0)
{
programCounter = returnStack[returnPointer];
}
if (dataPointer >= 0)
{
dataStack[dataPointer] = q;
}
}
Исполнение основных команд процессора:
auto execute(uint16 instruction)
{
// опознать тип инструкции
uint16 instructionType = instruction & 0xe000;
// операнд над которым осуществляется инструкция
uint16 operand = instruction & J1_DATA.TARGET;
// распознать конкретную инструкцию процессора
switch (instructionType)
{
// безусловный переход
case J1_INSTRUCTION.JMP:
programCounter = operand;
break;
// переход на адрес, если на вершине стека 0
case J1_INSTRUCTION.JZ:
if (dataStack[dataPointer] == 0)
{
programCounter = operand;
}
dataPointer--;
break;
// передать управление на адрес
case J1_INSTRUCTION.CALL:
returnPointer++;
returnStack[returnPointer] = to!uint16(programCounter + 1);
programCounter = operand;
break;
// выполнить инструкцию АЛУ
case J1_INSTRUCTION.ALU:
executeALU(operand);
break;
// положить на стек литерал
case J1_INSTRUCTION.LIT:
operand = instruction & J1_DATA.LITERAL;
dataPointer++;
dataStack[dataPointer] = operand;
programCounter++;
break;
default:
break;
}
}
Исполнение программы из памяти, считаем что число 0 — это команда остановки исполнения:
void executeProgram()
{
while (RAM[programCounter] != 0)
{
execute(RAM[programCounter]);
print;
}
}
Теперь, можно испытать процессор, для этого напишем круговую перестановку элементов стека в 16-ричных кодах J1 и загрузим ее в J1:
void main()
{
J1_CPU j1 = new J1_CPU;
uint16[32_768] ram = new uint16[32_768];
ram[0] = 0x4003; // call 3 вызвать подпрограмму по адресу 3
ram[1] = 0x8008; // push 8 положить 8 на стек
ram[2] = 0x0000; // halt остановить программу
ram[3] = 0x8001; // push 1 положить 1 на стек
ram[4] = 0x8002; // push 2 положить 2 на стек
ram[5] = 0x8003; // push 3 положить 8 на стек
ram[6] = 0x6146; // >r скопировать вершину стека данных в стек возвратов
ram[7] = 0x6180; // swap поменять местами два верхних элемента стека данных
ram[8] = 0x6b89; // r> поместить вершину стека возвратов в стек данных
ram[9] = 0x7180; // swap поменять местами два верхних элемента стека данных
j1.setMemory(ram);
j1.executeProgram();
j1.print;
}
Результат:
[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] [1, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] [1, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] [1, 2, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] [2, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] [2, 1, 3, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] [2, 3, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] [2, 3, 1, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] [2, 3, 1, 8, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
В качестве бонуса прилагаю описание реализации некоторых команд Forth в J1:
И, собственноручно полученная таблица 16-ричных кодов для этих и некоторых других команд Forth:
noop 0x6000 add 0x6202 xor 0x6502 and 0x6302 or 0x6402 invert 0x6600 = 0x6702 < 0x6802 u< 0x6f02 swap 0x6180 dup 0x6081 drop 0x6102 over 0x6181 nip 0x6002 >r 0x6146 r> 0x6b89 r>> 0x6bc9 r@ 0x6b81 @ 0x6c00 ! 0x6022 0x6102 dsp 0x6e81 lshift 0x6d02 rshift 0x6902 1- 0x6a00 2r> 0x6b89 0x6b89 0x6180 2>r 0x6180 0x6146 0x6146 2r@ 0x6b89 0x6b89 0x6181 0x6181 0x6146 0x6180 dup@ 0x6c81 dup>r 0x6044 2dupxor 0x6581 2dup= 0x6781 !nip 0x6022 2dup! 0x6020 up1 0x6001 down1 0x6002 copy 0x6100 unloop 0x6008 0x6008 exit 0x7008 ; 0x6048
J1 — занятный процессор, который годится отнюдь не только для забавного изучения программирования на нестандартной архитектуре, также это интересный процессор для виртуальных машин и для некоторых проектов электронных устройств (вы удивитесь, но процессор существует в железе, и не только для FPGA-плат, он также доступен в шилде GameDuino, как сопроцессор!). Помимо этого, можно реализовать свой простой ассемблер для данного процессора или написать целый транслятор Forth для него, и использовать J1 как исполнитель байткода!
Полный исходный код проекта находится тут: https://github.com/LightHouseSoftware/j1_cpu