Завтра начинается новая трудовая неделя, но у нас для тебя целых две отличные новости. Во-первых, через три дня тебя снова ждут выходные, а во-вторых, сегодня еще не закончилось. Так почему бы не провести время за самой культовой игрой всех времен и народов – «Тетрисом»? В июне этого года игра отметила свое тридцатилетие, и для многих людей эти кирпичи, падающие, как дар небес, стали самыми любимыми компьютерными персонажами. Давай попробуем совместить приятное с полезным и узнать несколько интересных фактов о «Тетрисе».

1.

Саундтреком к этой культовой игре послужили композиции группы «Scooter», сюиты Баха и русская народная песня «Коробейники».

2.

Эндрю Ллойд Уэббер – английский композитор, написавший первое произведение в девять лет, автор некоторых песен из мюзиклов «Призрак оперы», «Иисус Христос – суперзвезда», «Эвита» и «Кошки» – также приложил творческую руку к созданию хита своего времени под названием «Eurodance Tetris».

3.

Термин «синдром Тетриса» появился в 1996 году. Он обозначает галлюцинации после долгого залипания в компьютерные игры. Испытывая подобный «игровой передоз», люди начинают складывать все увиденные линии в подходящие для игры «Tetris» формы.

4.

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

5.

«Тетрис» был создан 6 июня 1984 года при помощи компьютера «Электроника-60». Автор игры, научный работник Академии наук СССР Алексей Пажитнов, получил от государства новый комп и квартиру, так как эта игра стала первой, пробившейся сквозь «Железный занавес». Вплоть до 96-го года прибыль от игры шла только Кремлю, автор же начал получать гонорары лично только после основания «The Tetris Company», приняв на себя обязанности по лицензированию.

6.

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

7.

Игра официально признана произведением искусства, и копия игры 1984 года занимает почетное место в Музее современного искусства на Манхеттене в Нью-Йорке.

8.

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

9.

По данным журнала «Appetite», тягу к обжорству и даже тягу к наркотикам можно ослабить, просто играя в «Tetris». Авторы статьи объясняют это тем, что высокий темп увлекательный игры отвлекает вас от низменных потребностей, но они так же говорят, что лучше играть стоя, потому как сидячий образ жизни вреден для здоровья. Гениально!

10.

Игра была разработана более чем для тридцати различных платформ, переведена на 50 языков, а «Tetris Friends Online Games» не устает хвастаться тем, что в онлайн-версию играют больше миллиона раз в сутки. Копия «Тетриса» из версии Sega Mega Drive, подписанной Пажитновым, была выставлена на продажу в 2011 году за $1 млн.

11.

Эта игра была упомянута аж девять раз в Книге рекордов Гиннеса. Самым нелепым рекордом, связанным с ней, можно смело назвать «самое длительное тюремное заключение благодаря компьютерной игре». Некий Фейз Чопдат отсидел четыре месяца за то, что не выключил игру на борту самолета, даже несмотря на убедительные просьбы проводницы. Видимо, 4 пункт нашей статьи не про этого парня.

Этот проект начался как ответ на вопрос со Stackexchange:

Это теоретическая задача - она не имеет ни простого, ни тривиального ответа.

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

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

Программа должна получать ввод ручным изменением состояния автомата в определённом поколении, представляющим собой прерывание (т.е. перемещение фигуры влево или вправо, поворот, бросание вниз или случайная генерация новой фигуры для размещения на поле). Определённое количество поколений считается временем ожидания. Результат игры показывается где-нибудь в автомате. Полученный результат должен визуально напоминать поле для настоящего «Тетриса».

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

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

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

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

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

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

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

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

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

После того, как конечный код QFTASM «Тетриса» был сгенерирован, следующими шагами были сборка из этого кода в соответствующее ПЗУ, а затем из метапикселей в лежащую в основе игру «Жизнь», на чём наша работа будет закончена.

Запуск «Тетриса»

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

Характеристики игры:

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

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

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

Value motion
1 вращение против часовой стрелки
2 влево
4 вниз (плавное опускание)
8 вправо
16 вращение по часовой стрелке

Система подсчёта очков
Игрок получает бонус за удаление нескольких линий за один ход.

1 ряд = 1 очко
2 ряда = 2 очка
3 ряда = 4 очка
4 ряда = 8 очков

Часть 2: OTCA-метапиксель и VarLife

OTCA-метапиксель

VarLife

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

Примечательные особенности:

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

Функция render-to-gif - моя любимая, потому что на её реализацию ушла куча времени. Было очень здорово, когда я наконец доделал её в семь часов утра. С её помощью можно запросто делиться конструкциями VarLife с другими людьми.

Основная схема VarLife

В целом компьютеру VarLife требуется всего четыре типа клеток! Всего восемь состояний, с учётом состояний «мёртвый»/«живой»:

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

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

Проводники

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

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

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

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

Шлюзы

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

Шлюз AND-NOT (сокращённо ANT) оказался жизненно необходимым компонентом. Этот шлюз передаёт сигнал от A тогда и только тогда, когда нет сигнала от B. То есть «A AND NOT B».

Хотя это не совсем шлюз , но тайл пересечения проводников очень важен и полезен.

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

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

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

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

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

Задержка на 4 такта:

Задержка на 5 тактов:

Задержка на 8 тактов (три отдельных точки входа):

Задержка на 11 тактов:

Задержка на 12 тактов:

Задержка на 14 тактов:

Задержка на 15 тактов (проверятся сравнением с этим):

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

Часть 3: оборудование

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

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

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

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

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

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

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

ПЗУ

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

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

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

SRL, SL, SRA

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

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

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

Это можно реализовать с помощью нескольких шлюзов AND/ANT и мультиплексора.

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

Триггер Set-Reset (SR)

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

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

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

Счётчик считывания

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

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

Очередь считывания

Очередь считывания должна отслеживать, какой из счётчиков считывания отправил входные данные в ОЗУ, чтобы он мог отправить вывод ОЗУ в нужное место. Для этого мы используем несколько SR-триггеров: по одному триггеру на каждый вход. Когда из счётчика считывания передаётся сигнал в ОЗУ, тактовый сигнал разделяется и включает SR-триггер счётчика. Затем вывод ОЗУ проходит вмести с SR-триггером через шлюз AND, а тактовый сигнал из ОЗУ сбрасывает SR-триггер.

АЛУ

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

ОЗУ

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

Метапиксель 22x22 каждого сегмента ОЗУ имеет такую структуру:

Соединив всё ОЗУ, мы получим что-то подобное:

Соединяем всё вместе

С помощью всех этих компонентов и общей архитектуре компьютера, описанной в Части 1, мы можем построить работающий компьютер!

Часть 4: QFTASM и Cogol

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

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

Для справки - компьютер Wireworld использует transport-triggered architecture , в которой единственной инструкцией является MOV , а вычисления выполняются записью/считыванием специальных регистров. Хотя эта парадигма позволяет создать очень простую в реализации архитектуру, результат оказывается на грани применимости: все арифметические/логические/условные операции требуют трёх инструкций. Было очевидно, что мы хотим создать более понятную архитектуру.

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

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

Иллюстрация нашей архитектуры приведена в Части 1.

Работа и операции АЛУ

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

Условные перемещения

Условные перемещения очень важны, они служат для маломасштабного и крупномасштабного управления. «Маломасштабное» - это способность управлять выполнением конкретным перемещением данных, а «крупномасштабное» относится к их использованию в качестве операции условного перехода для передачи управления любому произвольному фрагменту кода. У процессора нет специальных операций перехода, потому что из-за распределения памяти условное перемещение может и копировать данные в обычную ОЗУ, и копировать адрес назначения в счётчик команд (PC). Также мы решили отказаться и от безусловных перемещений, и от безусловных переходов по схожей причине: обе эти операции могут быть реализованы как условные перемещения, в котором условие всегда имеет значение TRUE.

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

Арифметика

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

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

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

Битовые операции

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

Битовый сдвиг

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

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

Конвейер инструкций

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

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

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

Опкод - это 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. Запись результата (при необходимости) предыдущей инструкции в ОЗУ

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

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

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

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

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

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

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

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

00 непосредственная: жёстко заданное значение. (нет считывания из ОЗУ)
01 прямая: считывает данные из этого адреса ОЗУ. (одно считывание из ОЗУ)
10 непрямая: считывает данные из адреса, заданного в этом адресе. (два считывания из ОЗУ)
11 двойная непрямая: считывает данные из адреса, заданного в адресе, заданного этим адресом. (три считывания из ОЗУ)

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

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

4. Вычисление результат

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

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

5. Инкремент счётчика команд

Затем, наконец, считывается, увеличивается и записывается значение счётчика команд.

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

Одиссея по созданию ассемблера для «Тетриса»

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

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

[номер строки] [опкод] [арг1] [арг2] [арг3]; [необязательный комментарий]

Список опкодов

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

MNZ [проверка] [значение] [адрес назначения] – перемещение, если не ноль; задаёт [адрес назначения] для [значения], если [проверка] не равна нолю.
MLZ [проверка] [значение] [адрес назначения] – перемещение, если меньше ноля; задаёт [адрес назначения] [значению], если [проверка] не меньше ноля.
ADD [значение1] [значение2] [адрес назначения] – сложение; сохраняет [значение1] + [значение2] в [адресе назначения].
SUB [значение1] [значение2] [адрес назначения] – вычитание; сохраняет [значение1] - [значение2] в [адресе назначения].
AND [значение1] [значение2] [адрес назначения] – битовое И; сохраняет [значение1] & [значение] в [адресе назначения].
OR [значение1] [значение2] [адрес назначения] – битовое ИЛИ; сохраняет [значение1] | [значение2] в [адресе назначения].
XOR [значение1] [значение2] [адрес назначения] – битовое XOR; сохраняет [значение1] ^ [значение2] в [адресе назначения].
ANT [значение1] [значение2] [адрес назначения] – битовое И-НЕ; сохраняет [значение1] & (![значение2]) в [адресе назначения].
SL [значение1] [значение2] [адрес назначения] – сдвиг влево; сохраняет [значение1] << [значение2] в [адресе назначения].
SRL [значение1] [значение2] [адрес назначения] – логический сдвиг вправо; сохраняет [значение1] >>> [значение2] в [адресе назначения]. Не сохраняет знак.
SRA [значение1] [значение2] [адрес назначения] – арифметический сдвиг вправо; сохраняет [значение1] >> [значение2] в [адресе назначения] с сохранением знака.

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

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

Режим название префикс
0 непосредственный (нет)
1 прямой A
2 непрямой B
3 двойной непрямой C

Пример кода

Числа Фибоначчи в пяти строках:

0. MLZ -1 1 1; начальное значение
1. MLZ -1 A2 3; начало цикла, сдвиг данных
2. MLZ -1 A1 2; сдвиг данных
3. MLZ -1 0 0; конец цикла
4. ADD A2 A3 1; слот задержки перехода, вычисление следующего члена

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

Код Грея:

0. MLZ -1 5 1; начальное значение адреса ОЗУ для записи
1. SUB A1 5 2; начало цикла, определение двоичного числа для преобразования в код Грея
2. SRL A2 1 3; сдвиг вправо на 1
3. XOR A2 A3 A1; XOR и сохранение кода Грея в адресе назначения
4. SUB B1 42 4; берём код Грея и вычитаем 42 (101010)
5. MNZ A4 0 0; если результат не равен нолю (код Грея!= 101010), повторить цикл
6. ADD A1 1 1; слот задержки перехода, инкремент адреса назначения

Эта программа вычисляет код Грея и хранит код в последовательных адресах, начиная с адреса 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(); позволяют компилятору обрабатывать ветвление.
• Одномерные массивы (с арифметикой указателей), которые используются для поля «Тетриса».
• Подпрограммы и стек вызовов. Они используются, чтобы избежать дублироания больших фрагментов кода и для поддержки рекурсии.

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

Вот краткий обзор работы различных особенностей языка:

Токенизация

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

Парсинг

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

Распределение глобальной памяти

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

Конструкции IF-ELSE

Конструкции if-else имеют стандартный для C синтаксис:

Другой код
if (cond) {
первое тело
} else {
второе тело
}
другой код

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

Другой код
проверка условия
условный переход
первое тело
безусловный переход
второе тело (место условного перехода)
другой код (место безусловного перехода)

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

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

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

Другой код
проверка условия
условный переход
тело
другой код (место условного перехода)

Конструкции WHILE

Конструкции while тоже имеют стандартный для C синтаксис:

Другой код
while (условие) {
тело
}
другой код

При преобразовании в QFTASM код имеет такую схему:

Другой код
безусловный переход
тело (место условного перехода)
проверка условия (место безусловного перехода)
условный переход
другой код

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

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

Конструкции DO-WHILE

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

Массивы

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

My alpha; # пустой массив
my beta = {3,2,7,8}; # в первые четыре элемента заранее записываются эти значения

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

15: alpha
16: alpha
17: alpha
18: alpha

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

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

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

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

# рекурсивное вычисление десятого числа Фибоначчи
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); # выполняется подпрограмма, никакого возвращаемого значения не сохраняется

Call pointer = fib(10); # выполняется подпрограмма и возвращается указатель
display = pointer.sum; # доступ к локальной переменной и её присвоение глобальной переменной

Call display = fib(10).sum; # немедленное сохранение возвращаемого значения

Call display += fib(10).sum; # с возвращаемым значением можно также использовать другие виды операторов присвоения

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

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

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

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

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

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

Написание кода «Тетриса» на Cogol

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

Часть 5: сборка, трансляция и будущее

Получив от компилятора ассемблерную программу, мы можем приступить к сборке ПЗУ для компьютера Varlife и трансляции всего в большой паттерн игры «Жизнь»!

Сборка

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

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

Итак, мы сделали «Тетрис», и на этом всё закончено, правда? Ничего подобного. У нас есть для этого проекта и другие цели, над которыми мы работаем:

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

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

Хотя языка Cogol и достаточно рудиментарной реализации «Тетриса», он слишком простой и низкоуровневый для программирования широкого назначения на хорошо читаемом уровне.

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

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

Компилятор из текста в QFTASM был создан на четыре этапа: токенизатор, дерево грамматики, высокоуровневый компилятор и низкоуровневый компилятор.

Токенизатор

Разработка на Python началась с использования встроенное библиотеки токенизатора, то есть этот этап был довольно простым.

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

Дерево грамматики

Дерево грамматики создавалось с расчётом на удобную расширяемость без необходимости изменения исходного кода.

Структура дерева хранится в файле XML, который содержит структуру составляющих дерево узлов и их соединений с другими узлами и токенами.

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

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

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

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

В процессе встраивания внутренние переменные заменяются на те, которые были вызваны. Таким образом это:

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

Превращается в

Int i = __ADD__(3, 3)

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

Временные переменные (scratch variable) и сложные операции

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

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

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

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

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

Счётчик команд
Локальные переменные подпрограммы
Локальные переменные операторов (используются повторно)
Временные переменные
Переменная результата
Указатель стека
Стек
...

Низкоуровневая компиляция

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

sub

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

if и while

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

...
условие
переход к проверке
код
условие
если условие: переход к коду
...

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": , int op(*:rtn))
("call_sub", "__ADD__", , int op(*:i))
("assign", global bool scratch_2, 0)
("call_sub", "__SUB__", , global int scratch_3)
("call_sub", "__MLZ__", , 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
global int

Затем простые инструкции компилируются. Наконец, добавляются номера инструкций, и в результате получается исполняемый код 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 .

Теги:

• тетрис
• игра жизнь
• клеточные автоматы
• conway"s game of life

Добавить метки

В начале июня исполнился 31 год со дня создания одной из самых популярных компьютерных игр в истории человечества - «Тетриса». Спустя год после её появления на свет - 18 июля 1985 года - вышла известнейшая в России игровая платформа Brick Games. Внешне напоминающая современные смартфоны консоль вобрала в себя сразу несколько модификаций «Тетриса» и разошлась многомиллионным тиражом.

К 30-летию появления на свет знаменитой игровой платформы сайт вспоминает историю создания «Тетриса», а также его триумфальный выход из перестроечного СССР на рынки всего мира.

Головоломка в стакане

«Тетрис» был создан в 1984 году сотрудником Вычислительного центра при Академии наук СССР Алексеем Пажитновым. Он трудился над игрой в свободное от основной работы время и хотел, скорее, порадовать себя и своих коллег, чем покорить умы геймеров всего света.

Алексей Пажитнов задумал свою знаменитую игру после знакомства с головоломкой. Фото: www.globallookpress.com

Идея «Тетриса» пришла к Пажитнову в 1984 году, когда он познакомился с головоломкой математика из США Саломона Голомба, которая называлась пентамино. Её суть была в том, чтобы из нескольких фигур сложить одну большую. Разработчик решил создать компьютерный вариант пентамино. При этом, по задумке автора, в его игре нужно было собирать фигурки в стакане в реальном времени. Пажитнов хотел, чтобы фигуры, состоявшие из пяти элементов, переворачивались вокруг собственного центра тяжести. Тогда компьютерам, находившимся в распоряжении Вычислительного центра, этого сделать не удавалось из-за недостатка ресурсов. Разработчик решил сократить количество блоков, из которых состояли фигурки, до четырех. Получился уже тетрамино. Игру Пажитнов назвал «Тетрис», скрестив «тетрамино» и «теннис». За основу программист взял семь фигурок, составивших в дальнейшем классический набор игры. Ни о какой графике на тот момент речи идти не могло, поскольку у компьютера «Электроника-60», на котором создавался «Тетрис», не было монитора, а только дисплей, выводящий буквы и цифры.

Компьютер Электроника-60М - на чуть более ранней модели создавалась игра. Фото: Commons.wikimedia.org / Sergei Frolov

Первая версия игры создавалась на популярном в те времена языке Pascal, так что всё выглядело довольно примитивно. Только через восемь месяцев Пажитнов решил портировать «Тетрис» уже на PC. Опыта работы на персональном компьютере разработчик не имел, поэтому привлек для этой задачи 16-летнего школьника Вадима Герасимова, который был в Вычислительном центре кем-то вроде юного гения. Игру перенесли на PC за четыре дня, еще примерно столько же времени ушло на отладку рабочих процессов. Далее последовала полугодовая работа над цветом и таблицей рекордов. Также прорабатывалась система защиты, чтобы затем можно было доказать авторство. Все это программисты делали в свое свободное время. Позднее коллега Пажитнова Михаил Потемкин портировал игру на компьютер «Электроника» и добавил автоматическую загрузку «мусора», когда в стакане в начале процесса уже были фигурки.

Игра быстро распространилась сперва по Москве, а затем по всему СССР - её копировали на дискетах. На тот момент никакой выгоды её создатели не извлекли, поскольку фактически она принадлежала Вычислительному центру.

Продажа без согласия

Иностранцам «Тетрис» впервые показали в 1986 году. В Москву тогда пожаловали будапештцы из Института проблем кибернетики - с ним сотрудничал Вычислительный центр. Игра зарубежным гостям понравилась, после чего они довольно быстро портировали её на компьютеры Commodore 64 и Apple 2.

Среди гостей был и владелец британской компании Andromeda Software Роберт Штайн, сразу же решивший выкупить права на игру. Он даже успел получить одобрение от Пажитнова, но никаких конкретных сумм не озвучил. Да и переписка из-за «железного занавеса» шла между ними очень долго.

Штайн, полагая, что сделка о покупке советской игры уже практически решена, предложил «Тетрис» своим партнерам из Microsoft. Там эта идея большого восторга не вызвала. На всякий случай представители компании отправили детище Пажитнова американским коллегам из компании Spectrum Holobyte. Там разглядели большой потенциал в «Тетрисе», а Microsoft и Andromeda Software успели подписать контракт о продаже на сумму 3000 фунтов стерлингов и 7-15% от продаж. Сам разработчик «Тетриса» вовсе остался в неведении.

Предприимчивый Штайн хотел как можно быстрее все легализовать, только в СССР ему уже надо было работать с верхушкой Академии наук, а не с Вычислительным центром, и уж тем более не с рядовыми его сотрудниками. Чиновникам все это показалось не особо интересно. В итоге глава Andromeda Software уехал ни с чем.

В Spectrum Holobyte, не подозревая о том, что фактически займутся пиратским распространением, доработали советскую игру. Они добавили «Тетрису» коммунистические зарисовки, портреты известных русских, а в качестве музыкального сопровождения поставили песни «Коробейники» и «Калинку». Игровую механику трогать не стали. К 1987 году готовый коммерческий продукт собирались выпустить в Британии и США, только вот Штайн прав на «Тетрис» получить так и не сумел. В итоге он принял решение вовсе никому ничего не говорить. В 1988 году на Западе состоялся релиз PC-версии игры.

Детище КГБ

Успех проекта был огромен. На Западе новинка разошлась приличными тиражами, «Тетрису» присудили множество премий и наград. Игра могла на целый день парализовать работу офисов, из-за чего ходил слух, что ради ущерба экономике других стран её и разработали в недрах КГБ.

Пажитнов в это время перешел работать в ЭЛОРГ («Электроноргтехника»), которая была закреплена за Академией наук. Этой организации предстояло отстаять международные права на «Тетрис».

В итоге на Штайна надавили, в том числе не без помощи западных СМИ. Он принял условия СССР, подписав контракт. Представители Microsoft в это время попросили главу Andromeda Sofrware приобрести у разработчиков права на консольную и аркадную версию игры, но сами почему-то продали права на аркаду компании Atari, которая впоследствии перепродала игру японской Sega.

Тетрис вышел на Game Boy и заслужил широкую популярность в мире. Фото: www.globallookpress.com

Штайну в переговорах продвинуться не удалось, поскольку он не мог оплатить русским контракт. Но в Японии ждать не стали - там выпустили «Тетрис» двухмиллионным тиражом на PC и NES от Nintendo. Последняя смогла выкупить права через несколько фирм, а затем, договорившись с владельцами прав из СССР, запустить игру на портативной Game Boy, что обеспечивало консоли успех. При этом японская компания выиграла судебный процесс у Microsoft и Atari, которым пришлось довольствоваться только аркадной версией «Тетриса».

Game Boy, в комплекте с которым продавалась игра, не в последнюю очередь благодаря детищу Пажитнова за несколько первых лет разошелся более чем 30-миллионным тиражом, а самих картриджей с игрой было продано около 15 млн. Впоследствии Game Boy стал одной из самых успешных консолей за всю историю электронных развлечений.

В России 1990-х, еще только выстраивающей рыночную экономику, японскую консоль приобрести было не просто. Куда более популярным было впервые выпущенное для стран Европы недорогое устройство Brick Game, основанное на аналоге «Тетриса». Здесь были гонки, а также игры, подобные «змейке» и «танковым боям». В данном случае о соблюдении каких-либо прав на детище советского разработчика, вероятно, речи не шло совсем. Да и появилось устройство впервые в 1985 году, когда до официального релиза «Тетриса» в Европе было еще три года.

В 1990-х именно на этой платформе большинство играло в тетрис. Фото: АиФ-Петербург/ Яна Хватова

Одна игра

Алексей Пажитнов в 1989 году, понимая, что на играх можно делать большие деньги, объединился со старым приятелем Владимиром Похилко и новым другом Хенком Роджерсом, который вел переговоры о продаже «Тетриса» в Японию. Они создали студию AnimaTek, которая занималась разработкой логических игр и вопросами искусственного интеллекта. Некоторые разработки этой компании вошли, к примеру, в мегапопулярную стратегию 1990-х Age of Emires. В перестройку AnimaTek открыла штаб-квартиру в Сан-Франциско, выпустив затем несколько анимационных игр, которые, впрочем, признания не получили. После запуска пары программ для трехмерного моделирования студия канула в Лету.

Алексей Пажитнов со своим бизнес-партнером Хенком Роджерсом. Фото: www.globallookpress.com

Возможность же зарабатывать какие-то проценты с «Тетриса» Пажитнов получает лишь в 1996 году, когда истекает срок первоначальной лицензии. Программист сразу же создал компанию The Tetris Company в сотрудничестве с Роджерсом. TTC зарегистрировал «Тетрис» как торговую марку и с тех пор начал отслеживать законность ее применения.

За свою жизнь Алексей Пажитнов успел создать порядка 13 игр, но ни одна из них так и не приблизилась к ошеломляющей популярности «Тетриса», в который играют уже на протяжении нескольких десятилетий.

То, что началось как развлечение для советского разработчика программного обеспечения в 80-х годах XX века, в итоге быстро распространилось по странам мира. Даже сегодня, спустя десятилетия, игроков по-прежнему притягивает «Тетрис», очаровывая простотой и приятностью игры.

Те, кто играл в «Тетрис», потратив несколько часов вращая и роняя фигуры под гипнотический звук 8-битной песни, могли подумать, что они с ним близко знакомы. Но эта видеоигра, все еще гипнотизирующая миллионы людей всех возрастов, имеет длинную и удивительную историю со множеством сюрпризов. Вот 7 фактов о «Тетрисе»:

1. Его название частично произошло от слова «теннис»

Необычное название «Тетрис» было придумано его изобретателем, разработчиком компьютерных программ и любителем головоломок Алексеем Пажитновым, когда он создал игру в 1984 году. Идею о том, как должны выглядеть игровые элементы он взял из популярной игры-головоломки под названием «пентамино», в котором каждая часть состоит из пяти равных квадратов. Но в игре Пажитнова фигуры были сделаны из четырех квадратов. Придумывая название игры, Пажитнов соединил латинское слово «тетра», означающее числовой префикс «четыре», со словом «теннис», поскольку это была его любимая игра.

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

2. Он вызывал настоящие галлюцинации

Художник-карикатурист и автор графического романа «Тетрис: игры, в которые играют люди» Бокс Браун писал, что люди тратили столько времени перед экранами, играя в «Тетрис», что у них выработался своеобразный побочный эффект - даже после того, как они переставали играть, они все еще видели падающие фигуры, когда закрыли глаза. Некоторые люди даже видели фигуры тетриса в своих снах.

Это явление стало назваться «эффект тетриса», и в последние годы начало относиться и к другим играм, в которые люди играют достаточно долго.

3. В некоторых изображениях в «Тетрисе» был политический протест

В мае 1987-го, 18-летний немецкий летчик по имени Матиас Руст пролетел на легком самолете «Сессна» 500 миль (805 километров) из Финляндии, незаконно пересек границы Советского Союза и приземлился посреди дня на Красной площади.

Какое отношение к этому имеет «Тетрис»?

По словам Брауна, дистрибьюторские компании «Тетриса» в Америке и Великобритании решили включить изображения самолета Руста в графику русских пейзажей. Стоит ли говорить, что трюк Руста в СССР смеха не вызывал. Там он был осужден за «злостное хулиганство, нарушение международных правил полетов и незаконное пересечение границы».

4. Музыка в игре на самом деле песня о любви

Заводная мелодия, которая весело играет, пока игроки вращают и опускают фигурки в «Тетрисе», основана на народной песне XIX века под названием «Коробейники», про ухаживания между крестьянкой и торговцем-разносчиком.

Как же она стала музыкальной темой игры, в которой не было ни романтики, ни персонажей, ни сюжета?

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

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

5. Эта игра может изменить форму мозга

Игра в «Тетрис» утолщает кору головного мозга и может способствовать повышению эффективности познавательной деятельности, по данным исследования, опубликованном в сентябре 2009 года.

Группе из 26 девушек-подростков было поручено играть в «Тетрис» в течение 30 минут каждый день на протяжении трех месяцев. Магнитно-резонансная томография их мозга до и после трехмесячного периода показала утолщение в трех областях головного мозга - одно в левой лобной доле и два в левой височной доле - в то время как у девушек, которые не играли в «Тетрис», никаких изменений в мозге не было.

6. «Тетрис» - произведение искусства

В ноябре 2012 «Тетрис» стал одной из 14 видеоигр приобретенных Музеем современного искусства в Нью-Йорке, в рамках инициативы создать новую категорию произведений искусства в коллекции музея.

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

7. Это была первая видеоигра в космосе

В 1993 году «Тетрис» смело отправилась туда, где ни одна видеоигра раньше не бывала, когда российский космонавт А. Серебров принес свой Game Boy от Nintendo и картридж с «Тетрисом» на борт ракеты Союз ТМ-17 во время экспедиции на космическую станцию «Мир».

Соревнования по игре «Тетрис-онлайн» проводятся по следующим правилам.

1. Каждый участник регистрируется на сайте игры под определённым игровым именем. Имена участников не повторяются.

2. Чемпионат проводится в течение определённого времени. В любой момент этого времени любой зарегистрированный участник может зайти на сайт чемпионата и начать зачётную игру. По окончании игры её результат

(количество набранных очков) фиксируется и заносится в протокол.

3. Участники имеют право играть несколько раз. Количество попыток одного участника не ограничивается.

4. Окончательный результат участника определяется по одной игре, лучшей для данного участника.

5. Более высокое место в соревнованиях занимает участник, показавший лучший результат.

6. При равенстве результатов более высокое место занимает участник, раньше показавший лучший результат.

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

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

Описание входных данных

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

Гарантируется, что количество участников соревнований не меньше 3.

Описание выходных данных

Программа должна вывести имена и результаты трёх лучших игроков по форме,

приведённой ниже в примере.

Пример входных данных:

Пример выходных данных для приведённого выше примера входных

1 место. qwerty (197128)

2 место. Alex (95715)

3 место. Jack (95715)

Пояснение.

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

Ниже приведён код решения на языке Pascal версии 2.6.2. Эффективный по памяти и времени.

var a,a1,a2,a3,i,n:longint;

s,s1,s2,s3:string;

for i:=1 to n do begin

if a>a1 then begin

if s=s1 then begin a1:=a; s1:=s; end

else if s=s2 then begin a2:=a1; s2:=s1; a1:=a; s1:=s end

end else if a>a2 then begin

if s=s2 then begin s2:=s; a2:=a; end

else if (ss1) then begin

end else if a>a3 then begin

if (ss1) and (ss2) then begin

writeln("1 место.",s1," (",a1,")");

writeln("2 место.",s2," (",a2,")");

writeln("3 место.",s3," (",a3,")");

Ниже приведён код решения на языке Pascal версии 2.6.2. Не являющегося эффективным по памяти.

var n, i, j, cnt, p, found, best, first, ind: longint;

name: array of string;

points, num: array of longint;

for i:= 1 to n do

for j:= 1 to cnt do

if s = name[j] then

if found = 0 then

points := -1;

if p > points then

points := p;

num := i;

for i:= 1 to 3 do

for j:= 1 to cnt do

if (points[j] > best) or (points[j] = best) and (num[j] begin

best:= points[j];

writeln(i, " место.", name, " (", points, ")");