класть боб в ящик или вынимать боб из ящика (если там есть боб – и переходить к другой инструкции, если его нет). Но на самом деле она может производить такие же вычисления, которые умеет производить любой другой компьютер.
Начнем с простого сложения. Допустим, вы хотите, чтобы регистровая машина прибавила содержимое одного регистра (скажем, регистра 1) к содержимому другого регистра (регистра 2). Таким образом, если в регистре 1 содержится [3], а в регистре 2 содержится [4], мы хотим, чтобы в итоге программа сделала так, чтобы содержимое регистра 2 стало равняться [7], потому что 3 + 4 = 7. Вот программа, которая справится с этой задачей, написанная на простом языке РПА (регистровое программирование на ассемблере):
Первые две инструкции образуют простой цикл, в рамках которого регистр 1 декрементируется, а регистр 2 инкрементируется снова и снова, пока регистр 1 не опустеет. Это “заметит” блок обработки данных, который в результате сделает переход на шаг 3, останавливающий программу. Блок обработки данных не может сказать, каково содержимое регистра, если только это содержимое не 0. Если снова представить ящики с бобами, можно сказать, что блок обработки данных слеп и не видит, что находится в регистре, пока он не опустеет, потому что отсутствие содержимого он может определить на ощупь. Несмотря на то что, в принципе, он не может сказать, каково содержимое регистров, если задать ему программу 1, он всегда будет прибавлять содержимое регистра 1 (какое бы число ни содержалось в регистре 1) к содержимому регистра 2 (какое бы число ни содержалось в регистре 2), а затем останавливаться. (Вы понимаете, почему так должно происходить всегда? Разберите несколько примеров, чтобы удостовериться.) Вот любопытный способ на это взглянуть: регистровая машина мастерски умеет складывать числа, не зная, какие именно числа она складывает (а также что такое числа и что такое сложение)!
а. Сколько шагов потребуется регистровой машине, чтобы сложить 2 + 5 и получить 7, выполняя программу 1 (считая Кон отдельным шагом)?
б. Сколько шагов потребуется машине, чтобы сложить 5 + 2?
(Какой из этого можно сделать вывод?)[29]
Этот процесс можно изобразить наглядно, построив так называемый граф потока. Каждый кружок обозначает инструкцию. Число в кружке обозначает адрес регистра, с которым необходимо произвести манипуляции (а не содержимое регистра), “+” обозначает инструкцию Инк, а “–” – инструкцию Деп. Программа всегда начинается с α, альфы, и завершается, когда достигает Ω, омеги. Стрелки показывают переход к следующей инструкции. Обратите внимание, что каждая инструкция Деп имеет две исходящих стрелки, одну для направления, в котором двигаться, если декрементировать содержимое регистра возможно, а другую – если невозможно, потому что содержимое регистра 0 (переход на ноль).
Теперь давайте напишем программу, которая просто перемещает содержимое одного регистра в другой регистр:
Вот граф потока:
Обратите внимание, что первый цикл этой программы очищает регистр 5, так что, каким бы ни было его содержимое в самом начале, оно никак не повлияет на то, что окажется в регистре 5 ко второму циклу (циклу сложения, в ходе которого содержимое регистра 4 прибавляется к 0 в регистре 5). Этот начальный шаг называется обнулением регистра и представляет собой весьма употребительную стандартную операцию. Вы постоянно будете использовать ее, чтобы готовить регистры к использованию.
Третья простая программа копирует содержимое одного регистра в другой регистр, оставляя изначальное содержимое нетронутым. Изучите граф потока, а затем саму программу:
Это явно не самый очевидный способ копирования, поскольку мы осуществляем операцию, сначала перемещая содержимое регистра 1 в регистр 3, затем делая копию в регистре 4 и, наконец, перемещая эту копию обратно в регистр 1. Но это работает. Всегда. Каким бы ни было содержимое регистров 1, 3 и 4 в самом начале, когда программа остановится, содержимое регистра 1 останется на месте, а копия этого содержимого – в регистре 3.
Если принцип работы этой программы вам не очевиден, возьмите несколько чашек, чтобы сделать регистры (подпишите номер каждой чашки, ее адрес), и горстку монеток (или бобов) и “вручную смоделируйте” весь процесс. Положите по несколько монеток в каждый из регистров и обратите внимание, сколько именно монеток вы положили в регистр 1 и регистр 3. Если вы будете в точности следовать программе, когда вы закончите, количество монеток в регистре 1 будет таким же, каким оно было изначально, и такое же количество монеток будет лежать в регистре 3. Очень важно, чтобы вы усвоили базовый принцип работы регистровой машины и вам не пришлось больше ломать над ним голову, поскольку мы собираемся использовать этот новый навык в дальнейшем. Выделите несколько минут и станьте регистровой машиной (как актер может стать Гамлетом).
Я замечаю, что некоторые мои студенты совершают простую ошибку: им кажется, что при декрементировании регистра монетку, которую они только вынули из регистра n, нужно положить в какой-нибудь другой регистр. Нет. Декрементированные монетки просто возвращаются в общую кучу, в ваш “бесконечный” запас монеток для использования в этих простых операциях сложения и вычитания.
Научившись перемещать, копировать и обнулять содержимое регистров, мы можем улучшить нашу программу сложения. Программа 1 помещает верный ответ на задачу на сложение в регистр 2, но в процессе уничтожает изначальное содержимое регистров 1 и 2. Возможно, нам нужна более сложная программа сложения, которая сохраняет эти значения для последующего использования, помещая ответ в другой регистр. Попробуем прибавить содержимое регистра 1 к содержимому регистра 2, поместить ответ в регистр 3 и оставить содержимое регистров 1 и 2 нетронутым.
Вот граф потока, показывающий, как этого добиться:
Проанализируем циклы, чтобы понять, что делает каждый из них. Сначала мы обнуляем регистр ответа, регистр 3, а затем обнуляем дополнительный регистр (регистр 4), который станет временным хранилищем, или буфером. После этого мы копируем содержимое регистра 1 в регистры 3 и 4 и перемещаем это содержимое обратно из буфера в регистр 1, восстанавливая его (и в процессе обнуляя регистр 4, чтобы снова использовать его в качестве буфера). Затем мы повторяем эту операцию с регистром 2, фактически прибавляя содержимое регистра 2 к содержимому, которое мы уже переместили в регистр 3. Когда программа останавливается, буфер 4 снова оказывается пуст, ответ находится в регистре 3, а два числа, которые мы складывали, – на своих изначальных местах, в регистрах 1 и 2.
Вот написанная на РПА 13-шаговая программа, которая переводит всю информацию с графа потока на язык, понятный блоку обработки данных:
Я не буду советовать вам вручную смоделировать эту программу, используя чашки и монетки. Жизнь коротка, поэтому, когда вы усвоите все базовые процессы, вам можно будет пользоваться вспомогательным устройством RodRego, регистровой машиной, которую можно скачать по ссылке http://sites.tufts.edu/rodrego/.
Есть версии RodRego для Windows и для Mac. Мы разработали этот инструмент мышления более двадцати лет назад в Мастерской учебных программ, и с тех пор сотни студентов и других заинтересованных людей воспользовались им, чтобы поднатореть в программировании регистровых машин. Вводя программы на РПА, вы можете наблюдать за их исполнением, выбирая режим с цифрами или бобами в регистрах. На той же странице представлена анимированная PowerPoint-презентация, в которой показан путь блока обработки данных по графу потока при совершении, к примеру, операции сложения. Эта анимация позволяет увидеть, как инструкции РПА соотносятся с кружками графа потока.
Теперь обратимся к вычитанию. Вот первый фрагмент графа потока для вычитания содержимого регистра 2 из содержимого регистра 1 и помещения ответа в регистр 4. Можете сказать, что с ним не так?
Такая программа сработает, только если содержимое регистра 1 больше содержимого регистра 2. Но что если это не так? Регистр 1 “обнулится” на середине цикла вычитания, когда вычитание еще не будет закончено. И что тогда? Мы не можем просто велеть компьютеру завершить выполнение программы, поскольку ответ в регистре 4 окажется неверным (0). Мы не можем использовать это обнуление, чтобы начать новый процесс, который сначала возвращается на половину цикла и отменяет временное декрементирование регистра 2. На этом этапе содержимое регистра 2 (а не регистра 1) даст нам верный ответ, если мы интерпретируем его в качестве отрицательного числа, так что вы можете просто переместить это содержимое в регистр 4 (который уже обнулен) и где-нибудь обозначить, что число в ответе отрицательное. Логично зарезервировать для этой задачи отдельный регистр – скажем, регистр 3. В самом начале его необходимо обнулить вместе с регистром 4, а затем поставить в регистре 3 “метку”, определяющую, положительное число в ответе или отрицательное, при условии что 0 означает +, а 1 означает –. Ниже представлен граф потока с комментариями, объясняющими, что происходит на каждом шаге цикла. (Вы можете добавлять такие комментарии в свои программы РПА, ограничивая их знаками #. Они предназначены для вас и других людей; RodRego их просто проигнорирует.)