Вот теоретический вопрос - тот, который ни в коем случае не дает простого ответа, даже тривиального.

В игре Жизни Конвея существуют такие конструкции, как метапиксель, которые позволяют Игре Жизни имитировать любую другую систему правил Игры-Жизни. Кроме того, известно, что Игра Жизни завершена по Тьюрингу.

Ваша задача - построить сотовый автомат, используя правила игры жизни Конвея, которые позволят играть в игру тетрис.

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

Ваша программа будет оцениваться по порядку следующим образом (с более низкими критериями, действующими как нарушители связей для более высоких критериев):

• Размер ограничивающего прямоугольника - выигрывает прямоугольный прямоугольник с наименьшей площадью, который полностью содержит данное решение.

• Меньшие изменения на входе - наименьшее количество ячеек (для наихудшего случая в вашем автомате), которые необходимо вручную настроить для побед прерывания.

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

• Начальное количество живых клеток - побеждает меньшее количество.

• Первый пост - предыдущий пост побеждает.

Это началось как квест, но закончилось как одиссея.

Квест на процессор Tetris, 2 940 928 x 10 295 296

Файл шаблона во всей его красе можно найти здесь , просмотреть в браузере здесь .

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

• PhiNotPi
• Эльендия Старман
• К Чжан
• Синий (тин)
• Корова кря (Kritixi Lithos)
• Mego
• Quartata

Мы также хотели бы выразить нашу благодарность 7H3_H4CK3R, Конору О'Брайену и многим другим пользователям, которые приложили усилия для решения этой проблемы.

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

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

Содержание

1. обзор
2. Метапиксели и VarLife
3. аппаратные средства
4. QFTASM и Cogol
5. Сборка, перевод и будущее
6. Новый язык и компилятор

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

Часть 1: Обзор

Основная идея этого проекта - абстракция . Вместо того, чтобы разрабатывать игру «Тетрис» непосредственно в Life, мы постепенно усилили абстракцию в серии шагов. На каждом уровне мы все больше отдаляемся от трудностей жизни и приближаемся к созданию компьютера, который так же легко программировать, как и любой другой.

Во-первых, мы использовали метапиксели OTCA в качестве основы нашего компьютера. Эти метапиксели способны эмулировать любое «похожее на жизнь» правило. Wireworld и компьютер Wireworld послужили важными источниками вдохновения для этого проекта, поэтому мы стремились создать аналогичную конструкцию с метапикселями. Хотя невозможно эмулировать Wireworld с метапикселями OTCA, можно назначить разные метапиксели различным правилам и создать схемы метапикселей, которые функционируют аналогично проводам.

Следующим шагом было создание множества фундаментальных логических элементов, которые послужат основой для компьютера. Уже на этом этапе мы имеем дело с концепциями, аналогичными реальной конструкции процессора. Вот пример шлюза ИЛИ, каждая ячейка в этом изображении фактически является мета-пикселем OTCA. Вы можете видеть, как «электроны» (каждый из которых представляет один бит данных) входят и выходят из шлюза. Вы также можете увидеть все различные типы метапикселей, которые мы использовали на нашем компьютере: B / S в качестве черного фона, B1 / S в синем, B2 / S в зеленом и B12 / S1 в красном.

Отсюда мы разработали архитектуру для нашего процессора. Мы потратили значительные усилия на разработку архитектуры, которая была бы как неэзотерической, так и максимально простой в реализации. В то время как компьютер Wireworld использовал элементарную архитектуру, запускаемую транспортом, в этом проекте используется гораздо более гибкая архитектура RISC с несколькими кодами операций и режимами адресации. Мы создали язык ассемблера, известный как QFTASM (Quest for Tetris Assembly), который руководил конструированием нашего процессора.

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

Вот иллюстрация нашей архитектуры процессора:

Отсюда просто вопрос внедрения тетриса на компьютер. Чтобы помочь в этом, мы работали над несколькими методами компиляции языка более высокого уровня в QFTASM. У нас есть базовый язык, называемый Cogol, второй, более продвинутый язык, находящийся в стадии разработки, и, наконец, у нас есть незавершенный бэкэнд GCC. Текущая программа Tetris была написана в / скомпилирована из Cogol.

После того, как был сгенерирован окончательный код Tetris QFTASM, последними шагами было собрать этот код из соответствующего ПЗУ, а затем из метапикселей в основную Game of Life, завершив нашу конструкцию.

Бегущий тетрис

Для тех , кто хочет играть в тетрис без возиться с компьютером, вы можете запустить исходный код тетриса на переводчике QFTASM . Установите адреса дисплея ОЗУ на 3-32, чтобы просмотреть всю игру. Вот постоянная ссылка для удобства: тетрис в QFTASM .

Особенности игры:

• Все 7 тетромино
• Движение, вращение, мягкие капли
• Линия очищает и забивает
• Предварительный просмотр
• Входные данные игрока вводят случайность

дисплей

Наш компьютер представляет плату Tetris как сетку в своей памяти. Адреса 10-31 отображают табло, адреса 5-8 отображают фрагмент предварительного просмотра, а адрес 3 содержит счет.

вход

Вход в игру осуществляется путем ручного редактирования содержимого адреса ОЗУ 1. Используя интерпретатор QFTASM, это означает выполнение прямой записи в адрес 1. Найдите «Прямая запись в ОЗУ» на странице переводчика. Каждый шаг требует только редактирования одного бита ОЗУ, и этот входной регистр автоматически очищается после того, как входное событие было прочитано.

value     motion
   1      counterclockwise rotation
   2      left
   4      down (soft drop)
   8      right
  16      clockwise rotation

Система баллов

Вы получаете бонус за очистку нескольких линий за один ход.

1 row    =  1 point
2 rows   =  2 points
3 rows   =  4 points
4 rows   =  8 points

Часть 2: OTCA Metapixel и VarLife

OTCA Metapixel

( Источник )

OTCA Metapixel представляет собой конструкцию в игре Конвея жизни , которые могут быть использованы для моделирования любой жизни, как клеточные автоматы. Как говорит LifeWiki (ссылка выше),

Метапиксель OTCA - это элементарная ячейка с периодом 35488 и 2048 × 2048, построенная Брайсом Дью ... У него много преимуществ ... включая способность эмулировать любой жизненный клеточный автомат и тот факт, что при уменьшении масштаба ON и выключенные ячейки легко различить ...

Что жизнь, как клеточные автоматы здесь означает, по существу , что клетки рождаются и клетки выживают в соответствии с тем, сколько из их восьми соседних клеток живы. Синтаксис этих правил следующий: за B следуют номера живых соседей, которые приведут к рождению, затем косая черта, затем S, за которыми следуют номера живых соседей, которые будут поддерживать ячейку в живых. Немного многословно, так что я думаю, что пример поможет. Каноническая Игра Жизни может быть представлена ​​правилом B3 / S23, которое гласит, что любая мертвая клетка с тремя живыми соседями станет живой, а любая живая клетка с двумя или тремя живыми соседями останется живой. В противном случае клетка умирает.

Несмотря на то, что мета-пиксель OTCA является ячейкой 2048 x 2048, он на самом деле имеет ограничивающую рамку из 2058 x 2058 ячеек, причина в том, что он перекрывается пятью ячейками в каждом направлении со своими диагональными соседями. Перекрывающиеся ячейки служат для перехвата планеров, которые излучают сигнал соседям метаклеток о том, что он включен, чтобы они не мешали другим метапикселям и не летали бесконечно. Правила рождения и выживания кодируются в специальном разделе ячеек в левой части метапикселя наличием или отсутствием едоков в определенных положениях вдоль двух столбцов (один для рождения, другой для выживания). Что касается определения состояния соседних ячеек, вот как это происходит:

Поток 9-LWSS затем движется по часовой стрелке вокруг ячейки, теряя LWSS для каждой соседней включенной ячейки, которая вызвала медленную реакцию. Количество отсутствующих LWSS подсчитывается путем определения положения передней LWSS путем сбивания в нее другой LWSS с противоположного направления. Это столкновение высвобождает планеры, которые запускают еще одну или две реакции на приманку, если едоки, которые указывают, что условия рождения / выживания отсутствуют.

Более подробную схему каждого аспекта метапикселя OTCA можно найти на его оригинальном веб-сайте: Как это работает? ,

VarLife

Я построил онлайн-симулятор жизненных правил, в котором вы можете заставить любую клетку вести себя согласно любому жизненному правилу, и назвал его «Вариации жизни». Это имя было сокращено до "VarLife", чтобы быть более кратким. Вот скриншот этого (ссылка на него здесь: http://play.starmaninnovations.com/varlife/BeeHkfCpNR ):

Известные особенности:

• Переключай ячейки между живым / мертвым и раскрашивай доску по другим правилам.
• Возможность запускать и останавливать симуляцию, а также делать один шаг за раз. Также возможно выполнить заданное количество шагов как можно быстрее или медленнее, со скоростью, установленной в полях тиков в секунду и миллисекунд на тик.
• Очистите все живые клетки или полностью сбросьте доску в пустое состояние.
• Можно изменить размеры ячейки и платы, а также включить тороидальную обертку по горизонтали и / или по вертикали.
• Постоянные ссылки (которые кодируют всю информацию в URL) и короткие URL (потому что иногда информации слишком много, но в любом случае они хороши).
• Наборы правил, со спецификацией B / S, цветами и произвольной случайностью.
• И последнее, но не менее важное, рендеринг картинок!

Функция рендеринга в gif мне нравится больше всего потому, что для ее реализации потребовалась тонна работы, поэтому она была очень приятной, когда я наконец-то взломал ее в 7 часов утра, и потому, что с ней очень легко обмениваться конструкциями VarLife с другими. ,

Базовая схема VarLife

В общем, компьютеру VarLife нужны только четыре типа ячеек! Восемь состояний во всех подсчетах мертвых / живых состояний. Они есть:

• B / S (черный / белый), который служит буфером между всеми компонентами, поскольку ячейки B / S никогда не могут быть живыми.
• B1 / S (синий / голубой), который является основным типом ячейки, используемой для распространения сигналов.
• B2 / S (зеленый / желтый), который в основном используется для управления сигналом, гарантируя, что он не будет распространяться обратно.
• B12 / S1 (красный / оранжевый), который используется в нескольких специализированных ситуациях, таких как пересечение сигналов и сохранение части данных.

Используйте этот короткий URL, чтобы открыть VarLife с уже закодированными правилами: http://play.starmaninnovations.com/varlife/BeeHkfCpNR .

Провода

Существует несколько различных конструкций проводов с различными характеристиками.

Это самый простой и самый простой провод в VarLife, полоса синего цвета, окаймленная полосами зеленого цвета.

Короткий URL: http://play.starmaninnovations.com/varlife/WcsGmjLiBF

Этот провод однонаправленный. То есть он убьет любой сигнал, пытающийся двигаться в противоположном направлении. Это также одна ячейка уже, чем основной провод.

Короткий URL: http://play.starmaninnovations.com/varlife/ARWgUgPTEJ

Диагональные провода также существуют, но они не используются вообще.

Короткий URL: http://play.starmaninnovations.com/varlife/kJotsdSXIj

ворота

На самом деле существует множество способов создания каждого отдельного элемента, поэтому я покажу только один пример каждого типа. Этот первый gif демонстрирует вентили AND, XOR и OR соответственно. Основная идея здесь заключается в том, что зеленая ячейка действует как AND, голубая ячейка действует как XOR, а красная ячейка действует как OR, и все остальные ячейки вокруг них просто для правильного управления потоком.

Короткий URL: http://play.starmaninnovations.com/varlife/EGTlKktmeI

Ворота И-НЕ, сокращенно «Ворота АНТ», оказались жизненно важным компонентом. Это строб, который передает сигнал от A тогда и только тогда, когда нет сигнала от B. Следовательно, "A AND NOT B".

Короткий URL: http://play.starmaninnovations.com/varlife/RsZBiNqIUy

Хотя это не совсем ворота , тросовая перемычка по-прежнему очень важна и полезна.

Короткий URL: http://play.starmaninnovations.com/varlife/OXMsPyaNTC

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

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

Чтобы увидеть больше ворот, которые были обнаружены / построены в процессе изучения компонентов схем, ознакомьтесь с этой записью в блоге PhiNotPi: Building Blocks: Logic Gates .

Компоненты задержки

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

Задержка в 4 такта: короткий URL: http://play.starmaninnovations.com/varlife/gebOMIXxdh

Задержка в 5 тиков: короткий URL: http://play.starmaninnovations.com/varlife/JItNjJvnUB

8-тиковая задержка (три разные точки входа): короткий URL: http://play.starmaninnovations.com/varlife/nSTRaVEDvA

11-тиковая задержка: короткий URL: http://play.starmaninnovations.com/varlife/kfoADussXA

12-тиковая задержка: короткий URL: http://play.starmaninnovations.com/varlife/bkamAfUfud

Задержка в 14 тиков: короткий URL: http://play.starmaninnovations.com/varlife/TkwzYIBWln

Задержка в 15 тиков (подтверждено сравнением с этим ): короткий URL: http://play.starmaninnovations.com/varlife/jmgpehYlpT

Ну вот и все для базовых схемных компонентов в VarLife! Смотрите аппаратный пост KZhang для ознакомления с основными схемами компьютера!

Часть 3: Аппаратное обеспечение

Зная наши логические элементы и общую структуру процессора, мы можем приступить к проектированию всех компонентов компьютера.

демультиплексор

Демультиплексор, или демультиплексор, является ключевым компонентом ПЗУ, ОЗУ и АЛУ. Он направляет входной сигнал к одному из множества выходных сигналов на основе некоторых данных данного селектора. Он состоит из 3 основных частей: преобразователь последовательный в параллельный, средство проверки сигнала и разветвитель тактового сигнала.

Начнем с преобразования данных последовательного селектора в «параллельный». Это делается путем стратегического разделения и задержки данных таким образом, чтобы самый левый бит данных пересекал тактовый сигнал в крайнем левом квадрате 11x11, следующий бит данных пересекал тактовый сигнал в следующем квадрате 11x11 и так далее. Хотя каждый бит данных будет выводиться в каждом квадрате 11x11, каждый бит данных будет пересекаться с тактовым сигналом только один раз.

Далее мы проверим, соответствуют ли параллельные данные заданному адресу. Мы делаем это с помощью логических элементов AND и ANT на тактовой частоте и параллельных данных. Однако нам нужно убедиться, что параллельные данные также выводятся, чтобы их можно было снова сравнить. Вот те ворота, которые я придумал:

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

ПЗУ

Предполагается, что ПЗУ принимает адрес в качестве входных данных и отправляет инструкцию по этому адресу в качестве выходных данных. Мы начнем с использования мультиплексора для направления синхросигнала к одной из инструкций. Далее нам нужно сгенерировать сигнал, используя несколько проводов и ИЛИ вентилей. Пересечение проводов позволяет синхросигналу проходить по всем 58 битам инструкции, а также позволяет сгенерированному сигналу (в настоящее время параллельно) перемещаться вниз по ПЗУ для вывода.

Далее нам просто нужно преобразовать параллельный сигнал в последовательные данные, и ПЗУ будет готово.

ПЗУ в настоящее время создается путем запуска скрипта в Golly, который будет переводить код сборки из буфера обмена в ПЗУ.

SRL, SL, SRA

Эти три логических элемента используются для сдвигов битов, и они более сложны, чем ваши обычные AND, OR, XOR и т. Д. Чтобы заставить эти элементы работать, мы сначала задержим тактовый сигнал на соответствующее количество времени, чтобы вызвать «сдвиг». в данных. Второй аргумент, данный этим воротам, определяет, сколько битов нужно сдвинуть.

Для SL и SRL нам нужно

1. Убедитесь, что 12 старших значащих битов не включены (иначе вывод просто равен 0), и
2. Задержка данных правильное количество на основе 4 младших разрядов.

Это выполнимо с кучей вентилей AND / ANT и мультиплексором.

SRA немного отличается, потому что нам нужно скопировать знаковый бит во время смены. Мы делаем это, используя AND для тактового сигнала с битом знака, а затем копируем этот вывод несколько раз с помощью разветвителей провода и вентилей OR.

Set-Reset (SR) защелка

Многие части функциональности процессора зависят от способности хранить данные. Используя 2 красных клетки B12 / S1, мы можем сделать это. Две ячейки могут поддерживать друг друга, а также могут оставаться вместе. Используя некоторые дополнительные схемы set, reset и read, мы можем сделать простую защелку SR.

синхронизатор

Преобразовав последовательные данные в параллельные, а затем установив несколько защелок SR, мы можем сохранить целое слово данных. Затем, чтобы снова получить данные, мы можем просто прочитать и сбросить все защелки и соответственно задержать данные. Это позволяет нам хранить одно (или более) слово данных в ожидании другого, что позволяет синхронизировать два слова данных, поступающих в разное время.

Счетчик чтения

Это устройство отслеживает, сколько раз ему нужно обращаться из ОЗУ. Это делается с помощью устройства, похожего на защелку SR: T-триггер. Каждый раз, когда Т-триггер получает ввод, он меняет состояние: если он был включен, он выключается, и наоборот. Когда триггер T переключается из положения вкл / выкл, он посылает выходной импульс, который может быть подан в другой триггер T, чтобы сформировать 2-битный счетчик.

Чтобы создать счетчик чтения, нам нужно установить счетчик в соответствующий режим адресации с двумя вентилями ANT и использовать выходной сигнал счетчика, чтобы решить, куда направить тактовый сигнал: в АЛУ или в ОЗУ.

Очередь чтения

Очередь чтения должна отслеживать, какой счетчик чтения отправил вход в ОЗУ, чтобы он мог отправить вывод ОЗУ в правильное место. Для этого мы используем несколько защелок SR: одну защелку для каждого входа. Когда сигнал отправляется в ОЗУ со счетчика чтения, тактовый сигнал разделяется и устанавливает фиксатор SR счетчика. Выход ОЗУ затем И с защелкой SR, и тактовый сигнал из ОЗУ сбрасывает защелку SR.

ALU

ALU функционирует аналогично очереди чтения, поскольку использует SR-защелку для отслеживания того, куда отправлять сигнал. Сначала SR-защелка логической схемы, соответствующая коду операции инструкции, устанавливается с использованием мультиплексора. Затем значения первого и второго аргумента обрабатываются AND с помощью защелки SR, а затем передаются в логические схемы. Синхронизирующий сигнал сбрасывает защелку при прохождении, чтобы можно было снова использовать АЛУ. (Большая часть схем отключена, и тонна управления задержками добавлена, так что это выглядит как беспорядок)

баран

Оперативная память была самой сложной частью этого проекта. Это требуется для очень специфического контроля над каждой защелкой SR, в которой хранятся данные. Для чтения адрес отправляется в мультиплексор и отправляется в блоки ОЗУ. Блоки ОЗУ выводят данные, которые они хранят параллельно, которые преобразуются в последовательные и выводятся. Для записи адрес отправляется в другой мультиплексор, записываемые данные преобразуются из последовательного в параллельный, и блоки ОЗУ распространяют сигнал по всей ОЗУ.

Каждый модуль оперативной памяти 22х22 метапикселя имеет следующую базовую структуру:

Собрав всю оперативную память вместе, мы получим что-то похожее на это:

Собираем все вместе

Используя все эти компоненты и общую архитектуру компьютера, описанную в обзоре , мы можем построить работающий компьютер!

Загрузки: - Готовый компьютер Tetris - Сценарий создания ПЗУ, пустой компьютер и основной компьютер поиска

Часть 4: QFTASM и Cogol

Обзор архитектуры

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

Для справки, компьютер Wireworld использовал триггерную архитектуру , в которой MOVвыполнялась единственная инструкция, а вычисления выполнялись путем записи / чтения специальных регистров. Несмотря на то, что эта парадигма приводит к очень простой в реализации архитектуре, результат также не может быть использован на границе: все арифметические / логические / условные операции требуют трех инструкций. Нам было ясно, что мы хотим создать гораздо менее эзотерическую архитектуру.

Чтобы сделать наш процессор простым и повысить удобство использования, мы приняли несколько важных проектных решений:

• Нет регистров. Каждый адрес в ОЗУ обрабатывается одинаково и может использоваться в качестве любого аргумента для любой операции. В некотором смысле это означает, что вся оперативная память может рассматриваться как регистры. Это означает, что нет специальных инструкций по загрузке / хранению.
• В том же духе, отображение памяти. Все, что может быть записано или прочитано, использует единую схему адресации. Это означает, что программный счетчик (ПК) имеет адрес 0, и единственное различие между обычными инструкциями и инструкциями потока управления состоит в том, что инструкции потока управления используют адрес 0.
• Данные последовательны в передаче, параллельны в памяти. Благодаря «электронному» характеру нашего компьютера, сложение и вычитание значительно легче реализовать, когда данные передаются в последовательной форме с прямым порядком байтов (младший значащий бит вначале). Более того, последовательные данные устраняют необходимость в громоздких шинах данных, которые действительно широки и громоздки для правильного времени (чтобы данные оставались вместе, все «полосы» шины должны испытывать одинаковую задержку движения).
• Гарвардская архитектура, означающая разделение между программной памятью (ПЗУ) и памятью данных (ОЗУ). Хотя это снижает гибкость процессора, это помогает оптимизировать размер: длина программы намного больше, чем объем ОЗУ, который нам понадобится, поэтому мы можем разбить программу на ПЗУ и затем сосредоточиться на сжатии ПЗУ , что намного проще, когда это только для чтения.
• 16-битная ширина данных. Это наименьшая сила двоих, которая шире стандартной доски Tetris (10 блоков). Это дает нам диапазон данных от -32768 до +32767 и максимальную длину программы 65536 инструкций. (2 ^ 8 = 256 инструкций достаточно для самых простых вещей, которые мы могли бы сделать для игрушечного процессора, но не для тетриса.)
• Асинхронный дизайн. Вместо того, чтобы иметь центральные часы (или, что то же самое, несколько часов), определяющие синхронизацию компьютера, все данные сопровождаются «тактовым сигналом», который передается параллельно с данными, проходящими вокруг компьютера. Некоторые пути могут быть короче, чем другие, и, хотя это может создать трудности для централизованно-тактовой схемы, асинхронная схема может легко справляться с операциями с переменным временем.
• Все инструкции имеют одинаковый размер. Мы чувствовали, что архитектура, в которой каждая инструкция имеет 1 код операции с 3 операндами (значение-значение-назначение), была наиболее гибкой опцией. Это включает в себя операции с двоичными данными, а также условные перемещения.
• Простая система адресации. Наличие множества режимов адресации очень полезно для поддержки таких вещей, как массивы или рекурсия. Нам удалось реализовать несколько важных режимов адресации с помощью относительно простой системы.

Иллюстрация нашей архитектуры содержится в обзорном посте.

Функциональность и операции ALU

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

Условные ходы

Условные перемещения очень важны и служат как мелким, так и крупномасштабным потоком управления. «Маломасштабный» относится к его способности контролировать выполнение конкретного перемещения данных, в то время как «крупномасштабный» относится к его использованию в качестве операции условного перехода для передачи потока управления любому произвольному фрагменту кода. Выделенных операций перехода не существует, поскольку из-за сопоставления памяти условное перемещение может как копировать данные в обычную оперативную память, так и копировать адрес назначения на ПК. Мы также решили отказаться от как безусловных ходов, так и безусловных переходов по той же причине: оба могут быть реализованы как условный ход с условием, жестко заданным как TRUE.

Мы выбрали два разных типа условных перемещений: «двигаться, если не ноль» ( MNZ) и «двигаться, если ноль меньше» ( MLZ). Функционально MNZозначает проверку того, является ли какой-либо бит в данных единицей, а равно MLZпроверке, имеет ли бит знака 1. Они полезны для равенств и сравнений соответственно. Причина, по которой мы выбрали эти два, вместо других, таких как «переместить, если ноль» ( MEZ) или «переместить, если больше нуля» ( MGZ), заключалась в том, что MEZэто потребовало бы создания ИСТИННОГО сигнала из пустого сигнала, в то время MGZкак это более сложная проверка, требующая знаковый бит будет 0, в то время как по крайней мере еще один бит будет 1.

арифметика

Следующими наиболее важными инструкциями, с точки зрения руководства конструкцией процессора, являются основные арифметические операции. Как я упоминал ранее, мы используем последовательные данные с прямым порядком байтов, причем выбор порядка байтов определяется простотой операций сложения / вычитания. Получив первым младший бит, арифметические единицы могут легко отслеживать бит переноса.

Мы решили использовать представление дополнения 2 для отрицательных чисел, поскольку это делает сложение и вычитание более согласованными. Стоит отметить, что компьютер Wireworld использовал 1 дополнение.

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

Побитовые операции

Наш процессор имеет AND, ORи XORинструкции, которые делают то, что вы ожидаете. Вместо того, чтобы иметь NOTинструкцию, мы решили использовать инструкцию "а не" ( ANT). Сложность NOTинструкции заключается в том, что она должна создавать сигнал из-за отсутствия сигнала, что сложно с клеточными автоматами. ANTИнструкция возвращает 1 , только если первый аргумент бит равен 1 , а второй аргумент бит равен 0. Таким образом, NOT xэквивалентно ANT -1 x(а также XOR -1 x). Кроме того, ANTон универсален и имеет основное преимущество в маскировании: в случае программы Tetris мы используем его для стирания тетромино.

Сдвиг бит

Операции сдвига битов являются наиболее сложными операциями, выполняемыми АЛУ. Они принимают два ввода данных: значение для сдвига и значение для его сдвига. Несмотря на их сложность (из-за разной степени смещения), эти операции имеют решающее значение для многих важных задач, включая множество «графических» операций, связанных с тетрисом. Сдвиги битов также послужат основой для эффективных алгоритмов умножения / деления.

Наш процессор имеет три операции сдвига битов: «сдвиг влево» ( SL), «сдвиг вправо» ( SRL) и «сдвиг вправо» ( SRA). Первые два битовых сдвига ( SLи SRL) заполняют новые биты всеми нулями (это означает, что отрицательное число, сдвинутое вправо, больше не будет отрицательным). Если второй аргумент сдвига находится вне диапазона от 0 до 15, результат, как и следовало ожидать, будет иметь все нули. Для последнего сдвига бит сдвиг SRAбит сохраняет знак ввода и, следовательно, действует как истинное деление на два.

Инструкция по конвейерной обработке

Сейчас самое время поговорить о некоторых мельчайших деталях архитектуры. Каждый цикл ЦП состоит из следующих пяти шагов:

1. Получить текущую инструкцию из ПЗУ

Текущее значение ПК используется для извлечения соответствующей инструкции из ПЗУ. Каждая инструкция имеет один код операции и три операнда. Каждый операнд состоит из одного слова данных и одного режима адресации. Эти части отделены друг от друга, поскольку они читаются из ПЗУ.

Код операции состоит из 4 битов для поддержки 16 уникальных кодов операций, из которых 11 назначены:

0000  MNZ    Move if Not Zero
0001  MLZ    Move if Less than Zero
0010  ADD    ADDition
0011  SUB    SUBtraction
0100  AND    bitwise AND
0101  OR     bitwise OR
0110  XOR    bitwise eXclusive OR
0111  ANT    bitwise And-NoT
1000  SL     Shift Left
1001  SRL    Shift Right Logical
1010  SRA    Shift Right Arithmetic
1011  unassigned
1100  unassigned
1101  unassigned
1110  unassigned
1111  unassigned

2. Записать результат (при необходимости) предыдущей инструкции в ОЗУ

В зависимости от условия предыдущей инструкции (например, значения первого аргумента для условного перемещения) выполняется запись. Адрес записи определяется третьим операндом предыдущей инструкции.

Важно отметить, что запись происходит после извлечения инструкций. Это приводит к созданию интервала задержки ветвления, в котором инструкция сразу после инструкции ветвления (любая операция, которая записывает в ПК) выполняется вместо первой инструкции в целевом объекте ветвления.

В некоторых случаях (например, безусловные переходы) интервал задержки перехода может быть оптимизирован. В других случаях это невозможно, и инструкция после ветки должна оставаться пустой. Кроме того, этот тип интервала задержки означает, что ветви должны использовать цель перехода, которая на 1 адрес меньше, чем фактическая целевая команда, для учета происходящего приращения ПК.

Короче говоря, поскольку вывод предыдущей инструкции записывается в ОЗУ после извлечения следующей инструкции, условные переходы должны иметь пустую инструкцию после них, иначе ПК не будет обновляться должным образом для перехода.

3. Считайте данные для аргументов текущей инструкции из RAM

Как упоминалось ранее, каждый из трех операндов состоит из слова данных и режима адресации. Слово данных составляет 16 бит, такой же ширины, как ОЗУ. Режим адресации - 2 бита.

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

Мы стремились объединить концепции использования жестко закодированных чисел в качестве операндов и использования адресов данных в качестве операндов. Это привело к созданию режимов адресации на основе счетчика: режим адресации операнда - это просто число, представляющее, сколько раз данные должны передаваться по циклу чтения ОЗУ. Это включает немедленную, прямую, косвенную и двойную косвенную адресацию.

00  Immediate:  A hard-coded value. (no RAM reads)
01  Direct:  Read data from this RAM address. (one RAM read)
10  Indirect:  Read data from the address given at this address. (two RAM reads)
11  Double-indirect: Read data from the address given at the address given by this address. (three RAM reads)

После выполнения разыменования три операнда инструкции играют разные роли. Первый операнд обычно является первым аргументом для бинарного оператора, но также служит условием, когда текущая инструкция является условным перемещением. Второй операнд служит вторым аргументом для бинарного оператора. Третий операнд служит адресом назначения для результата инструкции.

Поскольку первые две инструкции служат данными, а третьи служат адресом, режимы адресации имеют несколько разные интерпретации в зависимости от того, в какой позиции они используются. Например, прямой режим используется для чтения данных с фиксированного адреса ОЗУ (так как требуется одно чтение из ОЗУ), но непосредственный режим используется для записи данных на фиксированный адрес ОЗУ (поскольку не требуется чтение из ОЗУ).

4. Подсчитать результат

Код операции и первые два операнда отправляются в АЛУ для выполнения двоичной операции. Для арифметических, побитовых и сдвиговых операций это означает выполнение соответствующей операции. Для условных ходов это означает просто возврат второго операнда.

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

5. Увеличьте счетчик программы

Наконец, счетчик программы читается, увеличивается и записывается.

Из-за позиции приращения ПК между считанной инструкцией и записью инструкции, это означает, что инструкция, которая увеличивает ПК на 1, является недопустимой. Инструкция, которая копирует ПК на себя, вызывает выполнение следующей инструкции дважды подряд. Но, имейте в виду, несколько инструкций для ПК подряд могут вызывать сложные эффекты, включая бесконечный цикл, если вы не обращаете внимание на конвейер инструкций.

Квест для Тетрис Ассамблеи

Мы создали новый язык ассемблера QFTASM для нашего процессора. Этот язык ассемблера соответствует 1-к-1 машинному коду в ПЗУ компьютера.

Любая программа QFTASM написана в виде серии инструкций, по одной на строку. Каждая строка отформатирована так:

[line numbering] [opcode] [arg1] [arg2] [arg3]; [optional comment]

Список кодов операций

Как обсуждалось ранее, компьютер поддерживает одиннадцать кодов операций, каждый из которых имеет три операнда:

MNZ [test] [value] [dest]  – Move if Not Zero; sets [dest] to [value] if [test] is not zero.
MLZ [test] [value] [dest]  – Move if Less than Zero; sets [dest] to [value] if [test] is less than zero.
ADD [val1] [val2] [dest]   – ADDition; store [val1] + [val2] in [dest].
SUB [val1] [val2] [dest]   – SUBtraction; store [val1] - [val2] in [dest].
AND [val1] [val2] [dest]   – bitwise AND; store [val1] & [val2] in [dest].
OR [val1] [val2] [dest]    – bitwise OR; store [val1] | [val2] in [dest].
XOR [val1] [val2] [dest]   – bitwise XOR; store [val1] ^ [val2] in [dest].
ANT [val1] [val2] [dest]   – bitwise And-NoT; store [val1] & (![val2]) in [dest].
SL [val1] [val2] [dest]    – Shift Left; store [val1] << [val2] in [dest].
SRL [val1] [val2] [dest]   – Shift Right Logical; store [val1] >>> [val2] in [dest]. Doesn't preserve sign.
SRA [val1] [val2] [dest]   – Shift Right Arithmetic; store [val1] >> [val2] in [dest], while preserving sign.

Режимы адресации

Каждый из операндов содержит как значение данных, так и ход адресации. Значение данных описывается десятичным числом в диапазоне от -32768 до 32767. Режим адресации описывается однобуквенным префиксом к значению данных.

mode    name               prefix
0       immediate          (none)
1       direct             A
2       indirect           B
3       double-indirect    C 

Пример кода

Последовательность Фибоначчи в пяти строках:

0. MLZ -1 1 1;    initial value
1. MLZ -1 A2 3;   start loop, shift data
2. MLZ -1 A1 2;   shift data
3. MLZ -1 0 0;    end loop
4. ADD A2 A3 1;   branch delay slot, compute next term

Этот код вычисляет последовательность Фибоначчи с адресом ОЗУ 1, содержащим текущий термин. Это быстро переполняется после 28657.

Серый код:

0. MLZ -1 5 1;      initial value for RAM address to write to
1. SUB A1 5 2;      start loop, determine what binary number to covert to Gray code
2. SRL A2 1 3;      shift right by 1
3. XOR A2 A3 A1;    XOR and store Gray code in destination address
4. SUB B1 42 4;     take the Gray code and subtract 42 (101010)
5. MNZ A4 0 0;      if the result is not zero (Gray code != 101010) repeat loop
6. ADD A1 1 1;      branch delay slot, increment destination address

Эта программа вычисляет код Грея и сохраняет код в последовательных адресах, начиная с адреса 5. Эта программа использует несколько важных функций, таких как косвенная адресация и условный переход. Он останавливается, как только 101010получится код Грея , что происходит для входа 51 по адресу 56.

Онлайн переводчик

El'endia Starman создала очень полезного онлайн-переводчика здесь . Вы можете пошагово выполнять код, устанавливать точки останова, выполнять ручную запись в ОЗУ и визуализировать ОЗУ как дисплей.

Cogol

После того как архитектура и язык ассемблера были определены, следующим шагом в «программной» части проекта стало создание языка более высокого уровня, подходящего для тетриса. Таким образом я создал Cogol . Название - это и каламбур на «COBOL», и аббревиатура от «C of Game of Life», хотя стоит отметить, что Cogol является для C тем же, что и наш компьютер для реального компьютера.

Cogol существует на уровне чуть выше ассемблера. Как правило, большинство строк в программе Cogol каждая соответствует одной строке сборки, но есть некоторые важные особенности языка:

• Основные функции включают именованные переменные с присваиваниями и операторы, которые имеют более читаемый синтаксис. Например, ADD A1 A2 3становится z = x + y;с компилятором, отображающим переменные на адреса.
• Циклические конструкции, такие как if(){}, while(){}и do{}while();поэтому компилятор обрабатывает ветвления.
• Одномерные массивы (с арифметикой указателей), которые используются для платы тетриса.
• Подпрограммы и стек вызовов. Они полезны для предотвращения дублирования больших кусков кода и для поддержки рекурсии.

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

Вот несколько кратких обзоров того, как работают различные языковые функции:

лексемизацию

Исходный код токенизируется линейно (однопроходно) с использованием простых правил о том, какие символы могут быть смежными внутри токена. Когда встречается символ, который не может быть смежным с последним символом текущего токена, текущий токен считается завершенным, и новый персонаж начинает новый токен. Некоторые символы (такие как {или ,) не могут быть смежными с любыми другими символами и поэтому являются их собственным токеном. Другие (как >и =) разрешается только быть рядом с другими персонажами в рамках своего класса, и таким образом могут образовывать маркеры , такие как >>>, ==или >=, но не нравится =2. Пробельные символы устанавливают границу между токенами, но сами не включаются в результат. Самый сложный символ для токенизации- потому что он может представлять как вычитание, так и унарное отрицание, и, следовательно, требует некоторого специального случая.

анализ

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

Глобальное распределение памяти

Компилятор присваивает каждой глобальной переменной (слову или массиву) свой собственный адрес (а) ОЗУ. Необходимо объявить все переменные, используя ключевое слово, myчтобы компилятор знал, как выделить для него место. Гораздо круче, чем именованные глобальные переменные, это управление памятью с нуля. Многие инструкции (особенно условные и многие обращения к массиву) требуют временных «чистых» адресов для хранения промежуточных вычислений. Во время процесса компиляции компилятор распределяет и отменяет выделение пустых адресов по мере необходимости. Если компилятору нужно больше чистых адресов, он выделит больше оперативной памяти в качестве чистых адресов. Я полагаю, что для программы типично требовать только несколько чистых адресов, хотя каждый чистый адрес будет использоваться много раз.

IF-ELSE Заявления

Синтаксис для if-elseоператоров является стандартной формой C:

other code
if (cond) {
  first body
} else {
  second body
}
other code

При преобразовании в QFTASM код выглядит следующим образом:

other code
condition test
conditional jump
first body
unconditional jump
second body (conditional jump target)
other code (unconditional jump target)

Если первое тело выполнено, второе тело пропускается. Если первое тело пропущено, второе тело выполняется.

В сборке условный тест обычно представляет собой просто вычитание, и знак результата определяет, следует ли выполнить переход или выполнить тело. MLZИнструкция используется для обработки неравенства , такие как >или <=. Для обработки MNZиспользуется инструкция ==, поскольку она перепрыгивает через тело, когда разница не равна нулю (и, следовательно, когда аргументы не равны). Условные выражения с несколькими выражениями в настоящее время не поддерживаются.

Если elseоператор опущен, безусловный переход также пропущен, и код QFTASM выглядит следующим образом:

other code
condition test
conditional jump
body
other code (conditional jump target)

WHILE Заявления

Синтаксис для whileоператоров также является стандартной формой C:

other code
while (cond) {
  body
}
other code

При преобразовании в QFTASM код выглядит следующим образом:

other code
unconditional jump
body (conditional jump target)
condition test (unconditional jump target)
conditional jump
other code

Условное тестирование и условный переход находятся в конце блока, что означает, что они выполняются повторно после каждого выполнения блока. Когда условие возвращает false, тело не повторяется, и цикл заканчивается. В начале выполнения цикла поток управления перепрыгивает через тело цикла к коду условия, поэтому тело никогда не выполняется, если условие ложно в первый раз.

MLZИнструкция используется для обработки неравенства , такие как >или <=. В отличие от ifоператоров MNZwhile, для обработки используется инструкция !=, поскольку она переходит к телу, когда разница не равна нулю (и, следовательно, когда аргументы не равны).

DO-WHILE Заявления

Единственная разница между whileи do-whileзаключается в том, что do-whileтело цикла изначально не пропускается, поэтому оно всегда выполняется хотя бы один раз. Обычно я использую do-whileоператоры для сохранения пары строк кода сборки, когда я знаю, что цикл никогда не нужно будет пропускать полностью.

Массивы

Одномерные массивы реализованы в виде смежных блоков памяти. Все массивы имеют фиксированную длину в зависимости от их объявления. Массивы объявлены так:

my alpha[3];               # empty array
my beta[11] = {3,2,7,8};   # first four elements are pre-loaded with those values

Для массива это возможное отображение ОЗУ, показывающее, как адреса 15-18 зарезервированы для массива:

15: alpha
16: alpha[0]
17: alpha[1]
18: alpha[2]

Адрес маркированы alphaзаполняется указателем на местоположение alpha[0], поэтому в Thie адрес случае 15 содержит значение 16. alphaПеременная может использоваться внутри кода Cogol, возможно , в качестве указателя стека , если вы хотите использовать этот массив в качестве стека ,

Доступ к элементам массива осуществляется в стандартной array[index]записи. Если значение indexявляется константой, эта ссылка автоматически заполняется абсолютным адресом этого элемента. В противном случае он выполняет некоторую арифметику указателя (просто сложение), чтобы найти нужный абсолютный адрес. Также возможно вложенное индексирование, например alpha[beta[1]].

Подпрограммы и вызов

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

# recursively calculate the 10th Fibonacci number
call display = fib(10).sum;
sub fib(cur,sum) {
  if (cur <= 2) {
    sum = 1;
    return;
  }
  cur--;
  call sum = fib(cur).sum;
  cur--;
  call sum += fib(cur).sum;
}

Подпрограмма объявляется с ключевым словом sub, и подпрограмма может быть размещена в любом месте внутри программы. Каждая подпрограмма может иметь несколько локальных переменных, которые объявлены как часть списка аргументов. Этим аргументам также могут быть заданы значения по умолчанию.

Для обработки рекурсивных вызовов локальные переменные подпрограммы хранятся в стеке. Последняя статическая переменная в ОЗУ - это указатель стека вызовов, а вся память после этого служит стеком вызовов. Когда вызывается подпрограмма, она создает новый кадр в стеке вызовов, который включает все локальные переменные, а также адрес возврата (ПЗУ). Каждой подпрограмме в программе присваивается один статический адрес ОЗУ, который служит указателем. Этот указатель указывает местоположение «текущего» вызова подпрограммы в стеке вызовов. Ссылка на локальную переменную выполняется с использованием значения этого статического указателя плюс смещение, чтобы дать адрес этой конкретной локальной переменной. Также в стеке вызовов содержится предыдущее значение статического указателя. Вот'

RAM map:
0: pc
1: display
2: scratch0
3: fib
4: scratch1
5: scratch2
6: scratch3
7: call

fib map:
0: return
1: previous_call
2: cur
3: sum

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

Существует несколько способов вызова подпрограммы, все из которых используют callключевое слово:

call fib(10);   # subroutine is executed, no return vaue is stored

call pointer = fib(10);   # execute subroutine and return a pointer
display = pointer.sum;    # access a local variable and assign it to a global variable

call display = fib(10).sum;   # immediately store a return value

call display += fib(10).sum;   # other types of assignment operators can also be used with a return value

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

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

Метки отладки

Любому {...}блоку кода в программе Cogol может предшествовать описательная метка из нескольких слов. Эта метка прикрепляется как комментарий в скомпилированном коде сборки и может быть очень полезна для отладки, поскольку она облегчает поиск определенных фрагментов кода.

Оптимизация слотов задержки филиала

Чтобы повысить скорость скомпилированного кода, компилятор Cogol выполняет некоторую действительно базовую оптимизацию слота задержки в качестве заключительного прохода над кодом QFTASM. Для любого безусловного перехода с пустым интервалом задержки ветвления интервал задержки может быть заполнен первой инструкцией в месте назначения перехода, и место назначения перехода увеличивается на единицу, чтобы указывать на следующую инструкцию. Это обычно сохраняет один цикл каждый раз, когда выполняется безусловный переход.

Написание кода тетриса в Cogol

Финальная программа Tetris была написана на Cogol, а исходный код доступен здесь . Скомпилированный код QFTASM доступен здесь . Для удобства здесь приведена постоянная ссылка: Tetris в QFTASM . Поскольку цель состояла в том, чтобы ввести в действие код сборки (а не код Cogol), полученный код Cogol является громоздким. Многие части программы обычно находятся в подпрограммах, но эти подпрограммы на самом деле были достаточно короткими, чтобы дублирование кода сохраняло инструкции надcallзаявления. В конечном коде есть только одна подпрограмма в дополнение к основному коду. Кроме того, многие массивы были удалены и заменены либо эквивалентно длинным списком отдельных переменных, либо множеством жестко закодированных чисел в программе. Окончательный скомпилированный код QFTASM содержит менее 300 инструкций, хотя он лишь немного длиннее, чем сам исходный код Cogol.

Часть 5: Сборка, перевод и будущее

С нашей программой сборки от компилятора пришло время собрать ПЗУ для компьютера Varlife и перевести все в большой шаблон GoL!

сборочный

Сборка программы сборки в ПЗУ выполняется практически так же, как и в традиционном программировании: каждая инструкция преобразуется в двоичный эквивалент, а затем она объединяется в большой двоичный двоичный объект, который мы называем исполняемым файлом. Для нас единственное отличие состоит в том, что двоичный двоичный объект необходимо преобразовать в схемы Varlife и подключить к компьютеру.

К. Чжан написал CreateROM.py , Python-скрипт для Golly, который выполняет сборку и перевод. Это довольно просто: он берет программу сборки из буфера обмена, собирает ее в двоичный файл и переводит этот двоичный файл в схему. Вот пример с простым тестером примитивов, включенным в скрипт:

#0. MLZ -1 3 3;
#1. MLZ -1 7 6; preloadCallStack
#2. MLZ -1 2 1; beginDoWhile0_infinite_loop
#3. MLZ -1 1 4; beginDoWhile1_trials
#4. ADD A4 2 4;
#5. MLZ -1 A3 5; beginDoWhile2_repeated_subtraction
#6. SUB A5 A4 5;
#7. SUB 0 A5 2;
#8. MLZ A2 5 0;
#9. MLZ 0 0 0; endDoWhile2_repeated_subtraction
#10. MLZ A5 3 0;
#11. MNZ 0 0 0; endDoWhile1_trials
#12. SUB A4 A3 2;
#13. MNZ A2 15 0; beginIf3_prime_found
#14. MNZ 0 0 0;
#15. MLZ -1 A3 1; endIf3_prime_found
#16. ADD A3 2 3;
#17. MLZ -1 3 0;
#18. MLZ -1 1 4; endDoWhile0_infinite_loop

Это производит следующий двоичный файл:

0000000000000001000000000000000000010011111111111111110001
0000000000000000000000000000000000110011111111111111110001
0000000000000000110000000000000000100100000000000000110010
0000000000000000010100000000000000110011111111111111110001
0000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000011110100000000000000100000
0000000000000000100100000000000000110100000000000001000011
0000000000000000000000000000000000000000000000000000000000
0000000000000000000000000000000000110100000000000001010001
0000000000000000000000000000000000000000000000000000000001
0000000000000000000000000000000001010100000000000000100001
0000000000000000100100000000000001010000000000000000000011
0000000000000001010100000000000001000100000000000001010011
0000000000000001010100000000000000110011111111111111110001
0000000000000001000000000000000000100100000000000001000010
0000000000000001000000000000000000010011111111111111110001
0000000000000000010000000000000000100011111111111111110001
0000000000000001100000000000000001110011111111111111110001
0000000000000000110000000000000000110011111111111111110001

При переводе на схемы Varlife это выглядит так:

Затем ПЗУ связывается с компьютером, который образует полноценную программу в Varlife. Но мы еще не закончили ...

Перевод на игру жизни

Все это время мы работали над различными уровнями абстракции над основой Game of Life. Но теперь пришло время отодвинуть занавес абстракции и перевести нашу работу в паттерн Game of Life. Как упоминалось ранее, мы используем OTCA Metapixel в качестве базы для Varlife. Итак, последний шаг - преобразовать каждую ячейку в Varlife в метапиксель в Game of Life.

К счастью, Golly поставляется со скриптом ( metafier.py ), который может преобразовывать шаблоны из разных наборов правил в шаблоны Game of Life с помощью OTCA Metapixel. К сожалению, он предназначен только для преобразования шаблонов с одним глобальным набором правил, поэтому он не работает на Varlife. Я написал модифицированную версию, которая решает эту проблему, так что правило для каждого метапикселя генерируется для каждой ячейки для Varlife.

Итак, наш компьютер (с ПЗУ Tetris) имеет ограничивающую рамку 1436 x 5082. Из 7 297 752 ячеек в этом ящике 6 075 811 являются пустым пространством, в результате чего фактическая численность населения составляет 1221 941 человек. Каждую из этих ячеек необходимо преобразовать в метапиксель OTCA, который имеет ограничивающую рамку 2048x2048 и совокупность либо 64 691 (для метапикселя ON), либо 23 920 (для метапикселя OFF). Это означает, что конечный продукт будет иметь ограничивающую рамку 2 940 928 x 10 407 936 (плюс несколько тысяч дополнительных для границ метапикселей) с населением от 29 228 828 720 до 79 048 585 231. С 1 бит на живую ячейку, это между 27 и 74 ГиБ, необходимыми для представления всего компьютера и ПЗУ.

Я включил эти вычисления здесь, потому что я не запустил их перед запуском сценария, и очень быстро исчерпал память на моем компьютере. После панической killкоманды я внес изменение в сценарий метафайера. Каждые 10 строк метапикселей шаблон сохраняется на диск (в виде сжатого файла RLE), и сетка сбрасывается. Это добавляет дополнительное время выполнения к переводу и использует больше дискового пространства, но сохраняет использование памяти в допустимых пределах. Поскольку Golly использует расширенный формат RLE, который включает местоположение шаблона, это не добавляет сложности при загрузке шаблона - просто откройте все файлы шаблонов на одном слое.

К. Чжан построил эту работу и создал более эффективный сценарий метафайера, который использует формат файла MacroCell, который загружается более эффективно, чем RLE, для больших шаблонов. Этот сценарий выполняется значительно быстрее (несколько секунд по сравнению с несколькими часами для исходного сценария метафайера), создает значительно меньший вывод (121 КБ против 1,7 ГБ) и может метафизировать весь компьютер и ПЗУ одним махом без использования большого количества памяти. Он использует тот факт, что файлы MacroCell кодируют деревья, которые описывают шаблоны. Используя пользовательский файл шаблона, метапиксели предварительно загружаются в дерево, и после некоторых вычислений и модификаций для обнаружения соседей можно просто добавить шаблон Varlife.

Файл шаблона всего компьютера и ROM в Game of Life можно найти здесь .

Будущее проекта

Теперь, когда мы сделали тетрис, мы закончили, верно? Даже не близко. У нас есть еще несколько целей для этого проекта, над которыми мы работаем:

• muddyfish и Kritixi Lithos продолжают работу над языком более высокого уровня, который компилируется в QFTASM.
• El'endia Starman работает над модернизацией переводчика QFTASM онлайн.
• quartata работает над бэкэндом GCC, что позволит компилировать автономный код C и C ++ (и, возможно, другие языки, такие как Fortran, D или Objective-C) в QFTASM через GCC. Это позволит создавать более сложные программы на более привычном языке, хотя и без стандартной библиотеки.
• Одним из самых больших препятствий, которые мы должны преодолеть, прежде чем мы сможем добиться большего прогресса, является тот факт, что наши инструменты не могут генерировать независимый от позиции код (например, относительные переходы). Без PIC мы не можем делать какие-либо ссылки, и поэтому мы упускаем преимущества, которые дает возможность ссылаться на существующие библиотеки. Мы работаем над тем, чтобы найти способ правильно сделать ПОС.
• Мы обсуждаем следующую программу, которую мы хотим написать для компьютера QFT. Прямо сейчас Понг выглядит как хорошая цель.

Часть 6: новый компилятор для QFTASM

Хотя Cogol достаточно для элементарной реализации Tetris, он слишком прост и слишком низок для программирования общего назначения на легко читаемом уровне. Мы начали работу над новым языком в сентябре 2016 года. Прогресс в освоении языка был медленным из-за трудностей с пониманием ошибок и реальной жизни.

Мы создали язык низкого уровня с синтаксисом, аналогичным Python, включая простую систему типов, подпрограммы, поддерживающие рекурсию и встроенные операторы. Компилятор из текста в QFTASM создавался в 4 этапа: токенайзер, грамматическое дерево, компилятор высокого уровня и компилятор низкого уровня.

Токенизатор

Разработка была начата с использованием Python с использованием встроенной библиотеки токенизаторов, что означает, что этот шаг был довольно простым. Требовалось всего несколько изменений в выводе по умолчанию, включая удаление комментариев (но не комментариев #include).

Грамматическое дерево

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

Древовидная структура хранится в файле XML, который включает в себя структуру узлов, которые могут составлять дерево, и то, как они составлены с другими узлами и токенами.

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

Сгенерированные токены затем анализируются по правилам грамматики, так что выходные данные формируют дерево элементов грамматики, таких как subs и generic_variables, которые, в свою очередь, содержат другие элементы грамматики и токены.

Компиляция в код высокого уровня

Каждая функция языка должна быть в состоянии скомпилировать в конструкции высокого уровня. К ним относятся assign(a, 12) и call_subroutine(is_prime, call_variable=12, return_variable=temp_var). Такие функции, как встраивание элементов, выполняются в этом сегменте. Они определены как operators и отличаются тем, что они вставляются каждый раз, когда используется оператор, такой как +или %. Из-за этого они более ограничены, чем обычный код - они не могут использовать ни свой собственный оператор, ни какой-либо оператор, который полагается на определенный.

В процессе встраивания внутренние переменные заменяются вызываемыми. Это в действительности превращает

operator(int a + int b) -> int c
    return __ADD__(a, b)
int i = 3+3

в

int i = __ADD__(3, 3)

Это поведение, однако, может быть вредным и подверженным ошибкам, если входная переменная и выходные переменные указывают на одно и то же место в памяти. Чтобы использовать «более безопасное» поведение, unsafeключевое слово регулирует процесс компиляции таким образом, что дополнительные переменные создаются и копируются в и из встроенных по мере необходимости.

Переменные скретча и сложные операции

Математические операции, такие как, a += (b + c) * 4не могут быть рассчитаны без использования дополнительных ячеек памяти. Компилятор высокого уровня решает эту проблему, разделяя операции на разные секции:

scratch_1 = b + c
scratch_1 = scratch_1 * 4
a = a + scratch_1

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

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

Структура ОЗУ

Program counter
Subroutine locals
Operator locals (reused throughout)
Scratch variables
Result variable
Stack pointer
Stack
...

Компиляция низкого уровня

Единственное , что компилятор низкий уровень имеет дело с которыми sub, call_sub, return, assign, ifи while. Это значительно сокращенный список задач, которые легче переводить в инструкции QFTASM.

sub

Это находит начало и конец именованной подпрограммы. Компилятор низкого уровня добавляет метки, а в случае mainподпрограммы добавляет инструкцию выхода (переход к концу ПЗУ).

if а также while

Как whileи ifпереводчики низкого уровня довольно просты: они получают указатели на их условия и прыгать в зависимости от них. whileциклы немного отличаются тем, что они скомпилированы как

...
condition
jump to check
code
condition
if condtion: jump to code
...

call_sub а также return

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

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

Когда встречается returnоператор, верхняя часть стека отрывается, и счетчик программы устанавливается на это значение. Значения для локальных объектов вызывающей подпрограммы выталкиваются из стека в их предыдущую позицию.

assign

Присвоение переменных - самая простая вещь для компиляции: они принимают переменную и значение и компилируются в одну строку: MLZ -1 VALUE VARIABLE

Назначение целей прыжка

Наконец, компилятор определяет цели перехода для меток, прикрепленных к инструкциям. Определяется абсолютное положение меток, а затем ссылки на эти метки заменяются этими значениями. Сами метки удаляются из кода и, наконец, номера команд добавляются в скомпилированный код.

Пример пошаговой компиляции

Теперь, когда мы прошли все этапы, давайте пройдем процесс фактической компиляции для реальной программы, шаг за шагом.

#include stdint

sub main
    int a = 8
    int b = 12
    int c = a * b

Хорошо, достаточно просто. Это должно быть очевидно , что в конце программы, a = 8, b = 12, c = 96. Во-первых, давайте включим соответствующие части stdint.txt:

operator (int a + int b) -> int
    return __ADD__(a, b)

operator (int a - int b) -> int
    return __SUB__(a, b)

operator (int a < int b) -> bool
    bool rtn = 0
    rtn = __MLZ__(a-b, 1)
    return rtn

unsafe operator (int a * int b) -> int
    int rtn = 0
    for (int i = 0; i < b; i+=1)
        rtn += a
    return rtn

sub main
    int a = 8
    int b = 12
    int c = a * b

Хорошо, немного сложнее. Давайте перейдем на токенизатор и посмотрим, что получится. На этом этапе у нас будет только линейный поток токенов без какой-либо формы структуры.

NAME NAME operator
LPAR OP (
NAME NAME int
NAME NAME a
PLUS OP +
NAME NAME int
NAME NAME b
RPAR OP )
OP OP ->
NAME NAME int
NEWLINE NEWLINE
INDENT INDENT     
NAME NAME return
NAME NAME __ADD__
LPAR OP (
NAME NAME a
COMMA OP ,
NAME NAME b
RPAR OP )
...

Теперь все токены проходят через синтаксический анализатор и выводят дерево с именами каждого из разделов. Это показывает структуру высокого уровня, прочитанную кодом.

GrammarTree file
 'stmts': [GrammarTree stmts_0
  '_block_name': 'inline'
  'inline': GrammarTree inline
   '_block_name': 'two_op'
   'type_var': GrammarTree type_var
    '_block_name': 'type'
    'type': 'int'
    'name': 'a'
    '_global': False

   'operator': GrammarTree operator
    '_block_name': '+'

   'type_var_2': GrammarTree type_var
    '_block_name': 'type'
    'type': 'int'
    'name': 'b'
    '_global': False
   'rtn_type': 'int'
   'stmts': GrammarTree stmts
    ...

Это грамматическое дерево устанавливает информацию для анализа высокоуровневым компилятором. Он включает в себя информацию, такую ​​как типы структуры и атрибуты переменной. Затем грамматическое дерево берет эту информацию и присваивает переменные, необходимые для подпрограмм. Дерево также вставляет все строки.

('sub', 'start', 'main')
('assign', int main_a, 8)
('assign', int main_b, 12)
('assign', int op(*:rtn), 0)
('assign', int op(*:i), 0)
('assign', global bool scratch_2, 0)
('call_sub', '__SUB__', [int op(*:i), int main_b], global int scratch_3)
('call_sub', '__MLZ__', [global int scratch_3, 1], global bool scratch_2)
('while', 'start', 1, 'for')
('call_sub', '__ADD__', [int op(*:rtn), int main_a], int op(*:rtn))
('call_sub', '__ADD__', [int op(*:i), 1], int op(*:i))
('assign', global bool scratch_2, 0)
('call_sub', '__SUB__', [int op(*:i), int main_b], global int scratch_3)
('call_sub', '__MLZ__', [global int scratch_3, 1], global bool scratch_2)
('while', 'end', 1, global bool scratch_2)
('assign', int main_c, int op(*:rtn))
('sub', 'end', 'main')

Далее, низкоуровневый компилятор должен преобразовать это высокоуровневое представление в код QFTASM. Переменным назначаются места в оперативной памяти, например:

int program_counter
int op(*:i)
int main_a
int op(*:rtn)
int main_c
int main_b
global int scratch_1
global bool scratch_2
global int scratch_3
global int scratch_4
global int <result>
global int <stack>

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

0. MLZ 0 0 0;
1. MLZ -1 12 11;
2. MLZ -1 8 2;
3. MLZ -1 12 5;
4. MLZ -1 0 3;
5. MLZ -1 0 1;
6. MLZ -1 0 7;
7. SUB A1 A5 8;
8. MLZ A8 1 7;
9. MLZ -1 15 0;
10. MLZ 0 0 0;
11. ADD A3 A2 3;
12. ADD A1 1 1;
13. MLZ -1 0 7;
14. SUB A1 A5 8;
15. MLZ A8 1 7;
16. MNZ A7 10 0;
17. MLZ 0 0 0;
18. MLZ -1 A3 4;
19. MLZ -1 -2 0;
20. MLZ 0 0 0;

Синтаксис

Теперь, когда у нас есть простой язык, нам нужно написать небольшую программу. Мы используем отступы, как это делает Python, разделяя логические блоки и поток управления. Это означает, что пробелы важны для наших программ. У каждой полной программы есть mainподпрограмма, которая действует точно так же, как main()функция в C-подобных языках. Функция запускается в начале программы.

Переменные и типы

Когда переменные определяются в первый раз, им необходимо иметь связанный с ними тип. В настоящее время определены типы intи boolс синтаксисом для определенных массивов, но не компилятор.

Библиотеки и операторы

stdint.txtДоступна библиотека с названием, которая определяет основные операторы. Если это не включено, даже простые операторы не будут определены. Мы можем использовать эту библиотеку с #include stdint. stdintопределяет операторы, такие как +, >>и даже *и %, ни один из которых не является прямым кодом операции QFTASM.

Язык также позволяет напрямую вызывать коды операций QFTASM __OPCODENAME__.

Добавление в stdintопределяется как

operator (int a + int b) -> int
    return __ADD__(a, b)

Который определяет, что +делает оператор, если ему даны два intс