В одной из статей, я упоминал про то, что в нашем мире, в принципе, могли бы существовать и получить распространение процессоры с довольно минималистичной архитектурой и скромным набором команд, которого вполне бы хватило на реализацию наших задумок, и хоть мы написали и эмулятор такого процессора и даже собственный ассемблер, но это был всего лишь скромный эксперимент. Более того, этот эксперимент повторялся уже много раз различными энтузиастами, однако, лишь немногие сумели пойти дальше и поставить перед собой очевидный вопрос: а сколько команд необходимо, чтобы реализовать мощный процессор и притом, способный обеспечить нужный минимум для запуска наших программ ?
В этой небольшой статье, которую я обещал для нашей группе ВКонтакте, я попытаюсь ответить на этот вопрос и покажу некоторые собственные наработки.
Согласно некоторым источникам, 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-суперкомпьютер!