Абсолютный эзотерический минимум

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

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

Согласно некоторым источникам, OISC (one-instruction set computer) или URISC (ultimate reduced instruction set computer) — теоретическая архитектура процессора, которая поддерживает одну единственную инструкцию, обладая при этом полнотой по Тьюрингу (т.е так или иначе приводима к машине Тьюринга, которая позволяет выполнять любую существующую компьютерную программу, т.к так или иначе все современные компьютеры эквивалентны машине Тьюринга). Также, можно сказать, что это до предела доведенный случай RISC-архитектуры с одной единственной возможной инструкцией.

Как ни странно, теоретических моделей OISC существует очень большое количество, но мы остановимся на одной из них, модели под кодовым названием SUBLEQ.

SUBLEQ-процессор (subtract and branch if less than or equal to zero) в своих инструкциях использует три операнда, которые мы условно назовем a, b и c. Этот процессор берет значение из ячейки памяти, адрес которой хранит операнд a, и значение из ячейки памяти, адрес которой хранит b; затем вычитает одно из другого, и если результат получается меньший или равный нулю, то происходит переход на следующую инструкцию по адресу, который хранится в переменной c.

Этот принцип можно более наглядно отобразить с помощью гипотетической инструкции subleq с теми же тремя операндами примерно так:

    subleq a, b, c   ; Mem[b] = Mem[b] - Mem[a]
                     ; if (Mem[b] ≤ 0) goto c

Квадратные скобки, в данном случае, обозначают взятие значения по адресу памяти (синтаксис такой же как и в ассемблере, хотя существует и альтернативная, Си-нотация, в которой могут сбить с толку указатели).

И тогда, построение гипотетического SUBLEQ-процессора с 10 000 ячеек памяти сводится к следующему коду на D:

import std.stdio;

class Subleq
{
	private
	{
		short[10_000] memory;
		short ip; 
	}

	this()
	{
		memory = 0;
		ip = 0;
	}

	void set(short index, short value)
	{
		memory[index] = value;
	}

	short get(short index)
	{
		return memory[index];
	}

	void run()
	{
		while (ip >= 0)
		{
			short a = memory[ip++], b = memory[ip++], c = memory[ip++];
			if (a < 0)
			{
				// do nothing
				write;
			}
			else if (b < 0)
			{
				write(cast(char) memory[a]);
			}
			else if ((memory[b] -= memory[a]) <= 0)
			{
				ip = c;
			}
			
		} 
	}
}

Но… Для полноты экспериментов, в SUBLEQ-процессоре есть две специализированные «ячейки памяти» (точнее, специальные адреса памяти), которые служат для ввода/вывода — это как раз те случаи, когда в переменные a или b попало отрицательное значение (я думаю, вы следите за кодом). При этом, я отключил возможность в процессор ввести данные со внешнего источника, что наверное, не помешает вшим экспериментам (код ведь учебный и ваши правки поощряются).

А теперь давайте проведем занятный эксперимент…

Вы наверно не знали, но существует компилятор из C-подобного языка (почти C, не хватает лишь немного из стандартной библиотеки), который транслирует C-подобный код в SUBLEQ-инструкции (которые, кстати, представляют собой наборы из трех чисел, операндов a, b, c). И мы воспользуемся данным компилятором, чтобы не мучаться с выведением команд и скомпилируем простой код, выводящий Hello world в терминал, для чего нам потребуется онлайн-версия компилятора (называется Higher Subleq) и некоторый код на D.

Онлайн-компилятор Higher Subleq можно найти здесь, вместе с интересующим нас примером Hello world. Для этого переходим на страничку компилятора и в выпадающем списке выбираем Hello world! (HSQ), после чего нажимаем на кнопку HSQ -> SQ (перевод Higher Subleq в SUBLEQ) и получаем в окне программы набор чисел, который нужно скопировать в любой текстовой файл с расширением *.sq.

Далее, работаем с кодом на D, который выглядит примерно так:

void main()
{
	import std.algorithm;
	import std.conv;
	import std.file;
	import std.range;
	import std.string;
	
	Subleq subleq = new Subleq;

	(cast(string) std.file.read(`<путь_к_текстовому_файлу с кодом SUBLEQ>`))
										.splitLines
										.join(" ")
										.split(" ")
										.filter!(a => (a != " ") && (a != ""))
										.map!(a => to!short(a.strip))
										.enumerate
										.each!(a => subleq.set(cast(short) a[0], a[1]));
	
	subleq.run;	
}

Сначала, код импортирует необходимый минимум из стандартной библиотеки, после чего происходит создание экземпляра класса SUBLEQ-процессора. После этого, полученный текстовой файл с кодом SUBLEQ (тот самый из онлайн-компилятора) считывается в одну строку для последующей обработки, которая разрезает файл на строки, а затем склеивает их в одну строку через пробельный символ. Таким образом, получается набор чисел в единственной строке и при этом числа разделены только пробелом, что дает возможность разбить полученный их поток на набор чисел. Так как набор чисел еще является строковым массивом, то отфильтровываем его от пустых и пробельных строк, которые помешают конверсии строки в число, а после этого выполняем саму конверсию, не забывая очистить строку от начальных и конечных пробелов. Теперь, после всех этим манипуляций пронумеруем полученный массив числовых данных начиная от нуля с помощью enumerate и затем, с помощью алгоритма each, запишем в ячейки процессора SUBLEQ полученные в предыдущем шаги инструкции.

Результат тестирования прост и понятен — жизнеутверждающая надпись Hello world в терминале, однако, вот вам результат вычисления факториала 5 в Higher Subleq:

На этом все, а более подробно с темой SUBLEQ можно ознакомится на сайте Олега Мазонки, который и создал компилятор Higher Subleq вместе с рядом занимательных примеров для него.

P.S: Представьте себе, что можно сделать, имея FPGA — можно прямо в железе это воплотить ! Более того, я сам сделал SUBLEQ-процессор на FPGA (на IceStick), а какие-то умельцы из Туманного Альбиона вообще внутри FPGA создали целый SUBLEQ-суперкомпьютер !

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