Создаем виртуальный Forth-процессор

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

Новый импульс я получил после того, как наткнулся на нечто интересное и действительно захватывающее…

Как-то давно я интересовался забавным языком программирования под названием Forth.

Данный язык программирования славится тем, что имеет крайне простую грамматику (описание ее предельно просто), а также Forth известен еще как и один из успешных стековых языков программирования. Более того, этот язык программирования интересен еще как язык промежуточного типа — его транслятор, не является ни компилятором, ни интерпретатором, а занимает некое среднее положение (данный факт, хотя и несколько сомнителен, но определенно интересен). Именно, такое сочетание весьма любопытных свойств мотивировало меня на попытку написания своего Forth-транслятора, причем настолько, что я захотел изучить ряд реализаций и просто немного почитать о данном языке…

Моя попытка реализации Forth-транслятора не привела к успеху, поскольку у меня в голове так и не сложился целостный подход к его алгоритму, и не было ключевой идеи о том, как будет разбираться код на Forth и во что он будет транслироваться. В бесчисленных пробах и ошибках, я начал отчаиваться, просеивая разного рода и качества материал, и тут внезапно я натыкаюсь на очень интересную статью про Forth-процессор! И вот тут я реально загорелся идеей своего виртуального процессора на D!

Я читал статью про J1 — Forth-процессор, который написан на Verilog (занимает около 200 строчек кода) и который является стековым процессором. Данный процессор устроен весьма просто: два стека, способные поместить в себя 33 (стек данных) и 32 (стек возвратов) 16-разрядных элемента, небольшая память под 16-разрядные беззнаковые числа. Никаких внутренних регистров, никакого запутанного АЛУ, никакого скрытого кэша!

J1, как процессор, поддерживает несколько различных типов инструкций и они также являются очень простыми. Всего инструкций, которые понимает J1, 5: загрузка литерала (т.е. числового беззнакового 16-разрядного значения) в стек данных, переход на заданный адрес в памяти, условный переход на заданный адрес в памяти, вызов процедуры по заданному адресу памяти и инструкции АЛУ (т.е. арифметико-логического устройства).

Инструкции для процессора представляют собой 16-разрядные числа без знака, в которых конкретные биты, как флаги, указывают тип команды процессора. Выглядят инструкции следующим образом:

Схема взята из той самой статьи Forth CPU. Что это такое? (Часть 1)
Схема взята из той самой статьи «Forth CPU. Что это такое? (Часть 1)»

Схема понимается достаточно просто:

  • Литерал (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

Добавить комментарий