Насосы интуиции и другие инструменты мышления

упражнение 1

а. Сколько шагов потребуется регистровой машине, чтобы сложить 2 + 5 и получить 7, выполняя программу 1 (считая Кон отдельным шагом)?

б. Сколько шагов потребуется машине, чтобы сложить 5 + 2?

(Какой из этого можно сделать вывод?)[29]

Этот процесс можно изобразить наглядно, построив так называемый граф потока. Каждый кружок обозначает инструкцию. Число в кружке обозначает адрес регистра, с которым необходимо произвести манипуляции (а не содержимое регистра), “+” обозначает инструкцию Инк, а “–” – инструкцию Деп. Программа всегда начинается с α, альфы, и завершается, когда достигает Ω, омеги. Стрелки показывают переход к следующей инструкции. Обратите внимание, что каждая инструкция Деп имеет две исходящих стрелки, одну для направления, в котором двигаться, если декрементировать содержимое регистра возможно, а другую – если невозможно, потому что содержимое регистра 0 (переход на ноль).

Теперь давайте напишем программу, которая просто перемещает содержимое одного регистра в другой регистр:

программа 2: MOVE [4,5]

Вот граф потока:

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

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

программа 3: COPY [1,3]

Это явно не самый очевидный способ копирования, поскольку мы осуществляем операцию, сначала перемещая содержимое регистра 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-шаговая программа, которая переводит всю информацию с графа потока на язык, понятный блоку обработки данных:

программа 4: ADD [1,2,3] без разрушения

Я не буду советовать вам вручную смоделировать эту программу, используя чашки и монетки. Жизнь коротка, поэтому, когда вы усвоите все базовые процессы, вам можно будет пользоваться вспомогательным устройством 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 их просто проигнорирует.)

упражнение 2

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

б. Что происходит, когда программа пытается вычесть 3 из 3 или 4 из 4?

в. Какая возможная ошибка предотвращается обнулением регистра 3 перед попыткой вычитания на шаге 3 вместо шага 4?

Умея складывать и вычитать, мы легко можем разработать программы для умножения и деления. Чтобы умножить n на m, нужно просто прибавить n к самому себе m раз. Мы можем запрограммировать компьютер сделать это, используя один регистр как счетчик, который считает от m до 0, осуществляя одну операцию декрементирования по завершении каждого цикла сложения.

упражнение 3

а. Нарисуйте граф потока (и напишите РПА-программу) для умножения содержимого регистра 1 на содержимое регистра 3, поместив ответ в регистр 5.

б. (По желанию)[30] Используя копирование и перемещение, улучшите программу умножения, созданную в задаче а: когда она закончит работу, изначальное содержимое регистра 1 и регистра 3 восстановится, так что вы сможете легко проверить исходные данные и ответы на правильность по завершении программы.

в. (По желанию) Нарисуйте граф потока и напишите РПА-программу, которая изучает содержимое регистра 1 и регистра 3 (не разрушая их!) и записывает адрес (1 или 3) регистра с большим содержимым в регистр 2 или помещает 2 в регистр 2, если содержимое регистров 1 и 3 равно. (После выполнения этой программы содержимое регистра 1 и регистра 3 должно остаться неизменным, а регистр 2 должен показывать, равно ли их содержимое, а если нет, то в каком из регистров содержимое больше.)

Деление можно выполнять подобным образом, снова и снова вычитая делитель из делимого и считая, сколько раз мы можем провести эту операцию. Остаток – при наличии – можно поместить в специальный регистр для остатка. Но здесь обязательно нужно ввести важную меру предосторожности: на ноль делить нельзя (или можно?), поэтому перед началом деления необходимо провести простую проверку делителя, попробовав его декрементировать. Если его получилось декрементировать, нужно один раз его инкрементировать (чтобы восстановить его исходное значение), а затем провести деление. Если же в регистре ноль, после неудачной попытки декремента нужно поднять тревогу. Можно сделать это, зарезервировав регистр для метки ошибка: 1 в регистре 5 может означать “тревога! Меня только что попросили поделить на ноль!”.

Ниже представлен граф потока для деления содержимого регистра 1 на содержимое регистра 2, помещения ответа в регистр 3 и остатка в регистр 4 и резервирования регистра 5 для “сообщения об ошибке” (1 означает “меня попросили поделить на ноль”).

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

секрет 1. Компетентность без понимания. Нечто – например, регистровая машина – может точно выполнять арифметические действия, не понимая, что делает.

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

Как вы теперь видите, эффективность регистровой машины объясняется существованием инструкции Деп, декремент-или-переход. Только эта инструкция позволяет компьютеру “замечать” (вроде как замечать) что-то в мире и использовать свои наблюдения для выбора следующего шага. Фактически существованием этой команды условного перехода объясняется эффективность всех компьютеров с хранимой в памяти программой, на что Ада Лавлейс обратила внимание еще в девятнадцатом веке, когда написала блестящий комментарий к описанию аналитической машины Чарльза Бэббиджа, которая стала прототипом всех компьютеров[31].

Когда вы наловчитесь собирать программы по частям, это станет для вас обычным делом. Однажды написав арифметические программы, мы можем использовать их снова и снова. Допустим, мы пронумеруем их: ADD станет операцией 0, SUBTRACT – операцией 1, MULTIPLY – операцией 2 и так далее. COPY может стать операцией 5, MOVE – операцией 6 и т. д. Теперь мы сможем использовать регистр, чтобы хранить в нем инструкцию, обозначая ее присвоенным номером.

упражнение 4 (по желанию)

Нарисуйте граф потока и напишите РПА-программу, которая превращает регистровую машину в простой карманный калькулятор, следующим образом:

а. Используйте регистр 2 для операции:

0 = ADD

1 = SUBTRACT

2 = MULTIPLY

3 = DIVIDE

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

(Таким образом, 3 0 6 будет означать 3 + 6; 5 1 3 будет означать 5–3; 4 2 5 будет означать 4 * 5; а 9 3 3 будет означать 9 ÷ 3.) Затем поместите результаты операции в регистры 4–7, используя регистр 4 для знака (где 0 означает +, а 1 означает –), регистр 5 для численного ответа, регистр 6 для возможного остатка в случае деления, а регистр 7 для сообщения об ошибке ввода (либо требовании делить на ноль, либо неопределенной операции в регистре 2).

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

секрет 2. Что именно обозначает число в регистре, определяет созданная нами программа.

Используя уже созданные структурные элементы, можно конструировать более сложные операции. Если запастись терпением, можно нарисовать граф потока и написать программу для возведения в квадрат – SQUARE – числа из регистра 7, или программу для вычисления среднего – FIND THE AVERAGE – содержимого регистров 1–20, или программу для разложения на множители – FACTOR – содержимого регистра 6 и помещения 1 в регистр 5, если 5 – искомый простой множитель, или программу сравнения – COMPARE – содержимого регистра 3 и регистра 4 и помещения большего содержимого в регистр 5, если только – UNLESS – оно не ровно в два раза больше, потому что в таком случае необходимо поместить метку в регистр 7. И так далее.

Особенно полезна программа, которая будет осуществлять поиск – SEARCH – по содержимому регистров, чтобы проверить, есть ли среди них регистр с конкретным содержимым, и поместить адрес этого регистра в регистр 101. (Как она будет работать? Поместите искомое число – TARGET – в регистр 102, а копию искомого числа – в регистр 103. Обнулите регистр 101, а затем, начиная с регистра 1, вычитайте содержимое регистров из содержимого регистра 103 [после инкрементирования регистра 101], ища нулевую разность. Если регистр 1 не дал нулевой разницы, переходите к регистру 2 и так далее. Если в каком-либо из регистров найдется искомое число, остановите программу; адрес этого регистра окажется в регистре 101.) Благодаря примитивной “чувствительности”, заключенной в инструкции Деп, – ее способности “замечать” нули, когда она пытается декрементировать регистр, – “глаза” регистровой машины можно обратить на нее саму, чтобы она изучала собственные регистры, перемещала между ними содержимое и меняла операции в зависимости от того, что и где она обнаруживает.

секрет 3. Поскольку число в регистре может означать что угодно, регистровая машина, в принципе, может быть сконструирована таким образом, чтобы “замечать” что угодно, или “отличать” любой признак либо черту, которую можно связать с числом – или несколькими числами.

К примеру, черно-белое изображение – любое черно-белое изображение, включая изображение этой страницы, – может быть представлено в виде огромного количества регистров, по одному регистру на пиксель, где 0 означает белую точку, а 1 – черную. Теперь напишите для регистровой машины программу, которая будет искать среди тысяч изображений изображение прямой черной горизонтальной линии на белом фоне. (Не пытайтесь сделать это на самом деле. Жизнь коротка. Просто более или менее живо представьте весь сложный и трудоемкий процесс, который справится с этой задачей.) Сконструировав – в воображении – определитель горизонтальных линий, определитель вертикальных линий и определитель полуокружностей, представьте, как скомпоновать эти фрагменты с несколькими другими полезными распознавателями (возможно, их понадобятся десятки) и написать программу, которая будет находить (заглавную) букву “А” в сотнях разных шрифтов! Программы оптического распознавания символов (OCR) – один из относительно недавних триумфов компьютерного программирования – могут сканировать печатные страницы и достаточно точно преобразовывать их в текстовый файл (в котором каждый буквенный или численный символ представлен числом в кодировке ASCII, так что по тексту можно осуществлять поиск, а также подвергать его другим чудесам текстовой обработки, не используя ничего, кроме арифметики.) Может ли программа OCR читать? Не то чтобы. Она не понимает, что видит. Она вроде как читает, и это удивительно полезная способность, которую можно добавить в нашу богатую коллекцию структурных элементов.

секрет 4. Поскольку число может означать что угодно, оно может означать инструкцию или адрес.

Числом в регистре можно обозначать инструкцию, например ADD, SUBTRACT, MOVE или SEARCH, и адреса (регистров в компьютере), поэтому мы можем хранить всю последовательность инструкций в ряде регистров. Если наша основная программа (программа А) велит машине переходить от регистра к регистру, выполняя содержащиеся в регистре инструкции, тогда в эти регистры можно поместить и вторую программу, программу Б. Когда машина начинает выполнение программы А, первым делом она обращается к регистрам, которые велят ей выполнять программу Б, что машина и делает. Это означает, что можно раз и навсегда поместить программу А в центральный блок обработки данных регистровой машины, зарезервировав для нее ряд регистров (она может стать “встроенной программой”, вшитой в ПЗУ – постоянное запоминающее устройство), а затем использовать программу А, чтобы запускать программы Б, В, Г и так далее, в зависимости от того, какие числа мы помещаем в обычные регистры. Устанавливая программу А на нашу регистровую машину, мы превращаем эту машину в компьютер с хранимой в памяти программой.

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

86, 92, 84, 29, 08, 50, 28, 54, 90, 28, 54, 90

одним большим и длинным числом:

869284290850285490285490

Это число одновременно представляет собой уникальное “имя” программы, программы Б, и саму программу, которая пошагово выполняется программой А. Вот другая программа:

28457029759028752907548927490275424850928428540423

и третья:

8908296472490284952498856743390438503882459802854544254789653985,