Основные шаги в языке Блуп
Мы займемся здесь поисками натуральных чисел с различными свойствами. Чтобы мы могли говорить о длине поиска, нам необходимо определить некие основные шаги, из которых состоит каждый поиск. Тогда мы сможем измерять длину поиска количеством шагов. Вот некоторые шаги, которые можно считать основными:
сложение двух натуральных чисел;
умножение двух натуральных чисел;
определение равенства двух чисел;
определение того, какое из двух чисел больше.
Петли и верхние границы
Если мы попытаемся сформулировать некий тест, — например, на простоту чисел, — в терминах таких шагов, мы вскоре увидим, что нам необходимо включить в него управляющую структуру — описание того, в каком порядке надо действовать: когда надо отойти назад и попытаться сделать что-то снова, или пропустить несколько шагов, или остановиться и т. п.
Любой алгоритм — описание того, как выполнить определенное задание — обыкновенно состоит из смеси (1) набора конкретных операций и (2) контрольных высказываний. Таким образом, разрабатывая наш язык для описания предсказуемо длинных вычислений, мы должны включить в него также основные контрольные структуры. Отличительное свойство Блупа — это ограниченное количество его контрольных структур. В нем нельзя совершать произвольные шаги или повторять группы шагов до бесконечности. Практически единственная контрольная структура Блупа — это ограниченные петли: набор команд, которые можно повторять снова и снова, но лишь ограниченное число раз; это число называется верхней границей, или потолком петли. Если потолок данной петли 300, то она может быть выполнена 0,7 или 300 раз — но не 301.
Программист не должен вводить в программу точной величины всех верхних границ; в действительности, он может и не знать этого заранее. Вместо этого, каждый потолок может быть вычислен до того, как программа начинает выполнять соответствующую петлю. Например, если вы собираетесь вычислить величину 2 3 n, у вас будут две петли. Сначала вы подсчитаете 3 n; для этого вам придется применить умножение n раз. Затем вы возьмете полученное число и возведете два в эту степень. Таким образом, верхняя граница второй петли — результат вычислений, произведенных вами в первой петле.
В программе Блуп это выражается следующим образом:
ОПРЕДЕЛИТЬ ПРОЦЕДУРУ «ДВА-В-СТЕПЕНИ-ТРИ-В-СТЕПЕНИ»[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. Это различие важно только тогда, когда вы находитесь внутри цикла и хотите его продолжить — но при этом хотите выйти из соответствующего блока; это исполняет команда ВЫЙТИ.
Заметьте также, что слова НЕ БОЛЬШЕ ЧЕМ теперь находятся перед верхней границей цикла; это говорит нам, что цикл может быть прерван до того, как достигнута его верхняя граница.
