В программе Блуп это выражается следующим образом:
ОПРЕДЕЛИТЬ ПРОЦЕДУРУ «ДВА-В-СТЕПЕНИ-ТРИ-В-СТЕПЕНИ»[N]:
БЛОК 0:НАЧАЛО
ЯЧЕЙКА(О)<=1;
ЦИКЛ N РАЗ;
БЛОК 1: НАЧАЛО
ЯЧЕЙКА(О)<= 3 * ЯЧЕЙКА(О);
БЛОК 1:КОНЕЦ;
ЯЧЕЙКА(1) <= 1;
ЦИКЛ ЯЧЕЙКА(О) РАЗ:
БЛОК 2:НАЧАЛО
ЯЧЕЙКА(1)<= 2 * ЯЧЕЙКА(1);
БЛОК 2:КОНЕЦ;
ВЫХОД <= ЯЧЕЙКА(1);
БЛОК 0:КОНЕЦ.
Условности языка Блуп
Умение читать программу, написанную на компьютерном языке, и понимать, что она делает, приходит со временем. Но надеюсь, что этот алгоритм достаточно прост, чтобы его можно было понять без особого труда. В нем определяется процедура, имеющая одно входное значение — N; выходом этой процедуры будет искомая величина.
Данное определение процедуры имеет блочную структуру; это означает, что некоторые его порции должны рассматриваться как единицы, или блоки. Все действия в блоке выполняются как одно целое. Каждый блок пронумерован (внешний блок получает номер 0) и ограничен НАЧАЛОМ и КОНЦОМ. В нашем примере в БЛОКЕ 1 и БЛОКЕ 2 было всего по одной инструкции, но вскоре мы будем иметь дело с более длинными блоками. Инструкция ЦИКЛ означает, что нужно повторить несколько раз блок, следующий ниже. Как вы видели выше, блоки могут быть вставлены один в другой.
Стратегия этого алгоритма ничем не отличается от той, которую я описал выше. Сначала вы берете вспомогательную переменную под названием ЯЧЕЙКА(0); для начала, вы придаете ей значение 1 и затем, исполняя цикл, вы несколько умножаете ее на 3 и повторяете это ровно N раз. Потом вы повторяете ту же процедуру для ЯЧЕЙКИ(1): придаете ей значение 1 и умножаете на 2 ровно ЯЧЕЙКА(0) раз; после этого вы останавливаетесь. Наконец, вы придаете выходу значение, полученное вами для ЯЧЕЙКИ(1). Именно эта величина достигает внешнего мира — это единственное действие процедуры, заметное извне.
Необходимо отметить кое-что относительно нотации. Прежде всего, значение указывающей налево стрелки следующее:
Вычислить выражение справа, взять результат и придать это значение ЯЧЕЙКЕ (или ВЫХОДУ) слева.
Таким образом, команда ЯЧЕЙКА(1) <= 3 * ЯЧЕЙКА(1) означает что вы должны утроить величину ЯЧЕЙКИ(1). Каждую ЯЧЕЙКУ можно представить как отдельное слово в памяти компьютера. Единственная разница между ЯЧЕЙКОЙ и настоящим словом заключается в том, что последнее может содержать только целые числа до определенного конечного предела, в то время как в ЯЧЕЙКЕ может храниться сколь угодно большое натуральное число.
Каждая процедура в Блупе, будучи вызванной, производит определенную величину — а именно, величину переменной под названием ВЫХОД. В начале выполнения любой процедуры мы предполагаем, что при отсутствии дополнительных указаний ВЫХОДОМ будет 0. (Подобное предположение называется выбором по умолчанию, или стандартным выбором.) Благодаря этому, даже если процедура не установит никакого иного ВЫХОДА, мы тем не менее всегда будем знать его величину.
Команды ЕСЛИ и разветвление
Давайте теперь посмотрим на другую процедуру, которая покажет нам некоторые черты Блупа, делающие эту программу более общей. Каким образом можно найти значение M-N, если мы умеем только складывать? Трюк состоит в том, чтобы прибавлять различные числа к N до тех пор, пока мы не получим таким образом М. Но что, если М меньше N? Что, если нам нужно отнять 5 от 2? В области натуральных чисел ответа на этот вопрос нет. Но мы хотим, чтобы наша процедура Блуп все равно дала бы нам ответ — скажем, 0. Вот процедура Блупа, которая выполняет вычитание:
ОПРЕДЕЛИТЬ ПРОЦЕДУРУ «ВЫЧИТАНИЕ»[M,N]:
БЛОК 0: НАЧАЛО
ЕСЛИ M < N, ТО;
ВЫЙТИ ИЗ БЛОКА 0;
ПОВТОРИТЬ ЦИКЛ НЕ БОЛЬШЕ ЧЕМ M + 1 РАЗ;
БЛОК 1:НАЧАЛО
ЕСЛИ ВЫХОД + N = M, ТО:
ПРЕРВАТЬ ЦИКЛ 1;
ВЫХОД <= ВЫХОД + 1;
БЛОК 1:КОНЕЦ;
БЛОК 0:КОНЕЦ.
Здесь мы предполагаем, что ВЫХОД начинается с нуля. Если М меньше N, то вычитание становится невозможным, и мы сразу перескакиваем к БЛОКУ 0; в таком случае, ответ равняется 0. Именно это означает строчка ВЫЙТИ ИЗ БЛОКА 0. Но если М не меньше N, то мы пропускаем эту строчку и выполняем следующую команду (здесь это повторение цикла). Так работают в Блупе команды типа ЕСЛИ.
Итак, мы входим в ЦИКЛ 1, называющийся так потому, что он предлагает нам повторить БЛОК 1. Мы пробуем добавить к N сначала 0, затем 1, 2 и т. д., пока не находим числа, дающего в результате М. В этот момент мы ПРЕРЫВАЕМ цикл, в котором мы находимся, то есть переходим к команде, сразу следующей за КОНЦОМ этого цикла. В данном случае, мы попадаем к команде БЛОК 1: КОНЕЦ. Это последняя команда нашего алгоритма. ВЫХОД теперь содержит правильный ответ.
Заметьте, что у нас есть две различных команды, позволяющие нам перепрыгнуть вниз: ВЫЙТИ и ПРЕРВАТЬ. Первая относится к блокам, вторая — к циклам. ВЫЙТИ ИЗ БЛОКА н означает перейти к его последней строчке, в то время как ПРЕРВАТЬ ЦИКЛ н значит перепрыгнуть к строчке, сразу следующей за последней строчкой БЛОКА N. Это различие важно только тогда, когда вы находитесь внутри цикла и хотите его продолжить — но при этом хотите выйти из соответствующего блока; это исполняет команда ВЫЙТИ.
Заметьте также, что слова НЕ БОЛЬШЕ ЧЕМ теперь находятся перед верхней границей цикла; это говорит нам, что цикл может быть прерван до того, как достигнута его верхняя граница.
Автоматическое создание блоков
Остается объяснить две важные особенности Блупа. Первая из них состоит в том, что однажды определенная процедура может быть вызвана при определении следующих процедур. Она рассматривается в таком случае как нечто целое, как основной шаг. Эту черту Блупа можно назвать автоматическим созданием блоков. Это сравнимо с тем, как хороший фигурист выучивает новые движения: вместо длинной последовательности основных мускульных действий, он повторяет ранее выученные движения, которые, в свою очередь, состоят из ранее выученных движений — и так далее. Возможно, что нам придется отступить на несколько уровней, пока мы не придем к уровню «основных мускульных действий». Так же, как репертуар движений фигуриста, репертуар петель и прыжков Блупа растет очень быстро.
Тесты в Блупе
Другая важная черта Блупа — это то, что выходом некоторых процедур в нем может быть ДА или НЕТ вместо числового значения. Такие процедуры являются не функциями, но тестами. Чтобы указать на эту разницу, в конце названия теста ставится вопросительный знак. Кроме того, стандартным выбором ВЫХОДА здесь, разумеется, будет не 0, а НЕТ.
Давайте посмотрим, как работают эти черты Блупа в алгоритме, проверяющем, какие числа являются простыми.
ОПРЕДЕЛИТЬ ПРОЦЕДУРУ «ПРОСТОЕ?» [N]:
БЛОК 0:НАЧАЛО
ЕСЛИ N = О, ТО:
ВЫЙТИ ИЗ БЛОКА 0;
ЯЧЕЙКА(0) <= 2;
ПОВТОРИТЬ ЦИКЛ НЕ БОЛЕЕ ЧЕМ МИНУС [N,2] РАЗ:
БЛОК 1: НАЧАЛО
ЕСЛИ ОСТАТОК [N, ЯЧЕЙКА(0)] = 0, ТО;
ВЫЙТИ ИЗ БЛОКА 0;
ЯЧЕЙКА(0)<= ЯЧЕЙКА(0) +1;
БЛОК 1: КОНЕЦ;
ВЫХОД <= ДА;
БЛОК 0: КОНЕЦ.
Заметьте, что в этом алгоритме я вызвал две процедуры: МИНУС и ОСТАТОК. (Имеется в виду, что последняя была определена раньше; вы можете попробовать найти ее определение сами.) Этот тест на простоту чисел работает, перебирая один за другим потенциальные множители N, начиная с двух и кончая не более чем N-1. Если при делении N на любое из этих чисел остаток равняется нулю, то мы перескакиваем к концу алгоритма, поскольку на этой стадии ВЫХОД еще стандартный — НЕТ. Только если N не делится ни на одно из этих чисел, оно сможет пройти весь ЦИКЛ 1; тогда мы придем к команде ВЫХОД <= ДА, и после ее выполнения процедура будет закончена.
Программы Блупа содержат цепи процедур
Мы только что видели, как определяются процедуры в Блупе; однако, определение процедуры — лишь часть программы. Программа состоит из цепи определений процедур, каждая из которых вызывает определенные ранее процедуры. За этим может следовать один или несколько вызовов определенных таким образом процедур. Таким образом, примером полной программы Блупа было бы определение процедуры ДВА В СТЕПЕНИ ТРИ В СТЕПЕНИ, с последующим вызовом
ДВА В СТЕПЕНИ ТРИ В СТЕПЕНИ [2].
результатом чего было бы 512.
Если у вас есть только цепь определений процедур, то ни одна из них не исполняется; для этого необходим некий вызов, вводящий специфические числовые величины. Только тогда процедуры начинают действовать. Это напоминает мясорубку, ждущую, чтобы в нее заложили порцию мяса — или, скорее, целую цепь мясорубок, связанных таким образом, что каждая из них получает сырье от предыдущих. Сравнение с мясорубками, возможно, не слишком аппетитно; однако в случае программ Блупа это понятие очень важно. Такие программы мы будем называть «программами без вызова». Пример подобной программы показан на рис. 72.
