Автоматическое создание блоков
Остается объяснить две важные особенности Блупа. Первая из них состоит в том, что однажды определенная процедура может быть вызвана при определении следующих процедур. Она рассматривается в таком случае как нечто целое, как основной шаг. Эту черту Блупа можно назвать автоматическим созданием блоков. Это сравнимо с тем, как хороший фигурист выучивает новые движения: вместо длинной последовательности основных мускульных действий, он повторяет ранее выученные движения, которые, в свою очередь, состоят из ранее выученных движений — и так далее. Возможно, что нам придется отступить на несколько уровней, пока мы не придем к уровню «основных мускульных действий». Так же, как репертуар движений фигуриста, репертуар петель и прыжков Блупа растет очень быстро.
Тесты в Блупе
Другая важная черта Блупа — это то, что выходом некоторых процедур в нем может быть ДА или НЕТ вместо числового значения. Такие процедуры являются не функциями, но тестами. Чтобы указать на эту разницу, в конце названия теста ставится вопросительный знак. Кроме того, стандартным выбором ВЫХОДА здесь, разумеется, будет не 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.
Блуп — язык для определения предсказуемо конечных вычислений. Стандартное название функций, которые можно просчитать на Блупе, — примитивно-рекурсивные функции; стандартное название свойств, которые можно обнаружить с помощью тестов на Блупе, — примитивно-рекурсивные предикаты. Так, функция 23n — примитивно-рекурсивная функция, а утверждение «n — простое число» — примитивно-рекурсивный предикат.
Интуиция подсказывает нам, что свойство Гольдбаха — примитивно-рекурсивное; чтобы сделать это яснее, я приведу определение процедуры Блупа, которая показывает, как можно проверить наличие или отсутствие этого свойства:
ОПРЕДЕЛИТЬ ПРОЦЕДУРУ «ГОЛЬДБАХ?» [N]:
БЛОК 0: НАЧАЛО
ЯЧЕЙКА(О) <= 2;
ПОВТОРИТЬ ЦИКЛ НЕ БОЛЬШЕ N РАЗ;
БЛОК 1: НАЧАЛО
ЕСЛИ {ПРОСТОЕ? [ЯЧЕЙКА(О)]
И ПРОСТОЕ? [МИНУС [N, ЯЧЕЙКА(0)]]},
ТОГДА:
БЛОК 2:НАЧАЛО
ВЫХОД 2: <= ДА;
ВЫЙТИ ИЗ БЛОКА 0;
БЛОК 2: КОНЕЦ
ЯЧЕЙКА(0) <= ЯЧЕЙКА(0) + 1;
БЛОК 1:КОНЕЦ;
БЛОК 0: КОНЕЦ.
Как обычно, мы предполагаем, что выходом будет НЕТ, если не доказано обратное, и мы просто ищем при помощи «грубой силы» такие пары чисел, которые в сумме дают N. Если они оба — простые числа, то мы выходим из внешнего блока; в противном случае, мы пробуем снова, пока не исчерпаем все возможности.
(Внимание: тот факт, что свойство Гольдбаха — примитивно-рекурсивное, не означает, что вопрос «все ли числа обладают свойством Гольдбаха» прост. Это далеко не так!)
Рис. 72. Структура программы без вызова в Блупе. Чтобы такая программа была самодостаточная, каждое определение процедуры может вызывать только те процедуры, определенные выше него.
Предлагаемые упражнения
Сможете ли вы написать похожую процедуру Блупа, которая проверяла бы наличие у числа свойства Черепахи (или Ахилла)? Попытайтесь! Если вам это не удается, то только лишь потому, что вы не знаете, какой будет верхняя граница? Возможно ли, что существует какое-то фундаментальное препятствие, вообще не позволяющее формулировать подобные алгоритмы в Блупе? А что, если задать те же вопросы касательно свойства интересности, определенного в Диалоге?
Ниже я привожу некоторые функции и свойства; попробуйте определить для каждого из них, является ли оно примитивно-рекурсивным (то есть, программируемым на Блупе). Для этого вы должны будете хорошенько подумать, какой тип операций потребуется для соответствующих вычислений и можно ли определить потолок для всех циклов данной процедуры.
ФАКТОРИАЛ [N] = N! (ФАКТОРИАЛ ОТ N)
(например, ФАКТОРИАЛ [4] = 24)
ОСТАТОК [M.N] = остаток после деления М на N
(например, ОСТАТОК [24,7] = 3)
ЦИФРА π [N] = N-ная цифра π после запятой
(например, ЦИФРА π [1] = 1,
ЦИФРА π [2] = 4,
ЦИФРА π [1 000 000] = 1)
ФИБО[М] = N-ное число ряда Фибоначчи
(например, ФИБО [9] = 34)
ПРОСТОЕ ЧИСЛО ЗА [N] = наименьшее простое число, следующее за N
(например, ПРОСТОЕ ЧИСЛО ЗА [33] = 37)
СОВЕРШЕННОЕ [N] = N-ное «совершенное» число, такое как, например, 28, чьи множители в сумме дают само это число: 28 =1+2+4+7+14
(например, СОВЕРШЕННОЕ [2] = 28)
ПРОСТОЕ? [N] = ДА если N простое число, в противном случае, НЕТ.
СОВЕРШЕННОЕ [N]? = ДА если N совершенное число, в противном случае, НЕТ.
ОБЫКНОВЕННОЕ? [А, В, С, N] = ДА, если A N+ В N= С N верно; в противном случае, НЕТ.
(например, ОБЫКНОВЕННОЕ ? [3, 4, 5, 2] = ДА,
ОБЫКНОВЕННОЕ ? [3, 4, 5, 3] = НЕТ)
ПЬЕР? [А,В,С] = ДА, если A N+ В N= С N верно для N > 1; в противном случае, НЕТ.
(например, ПЬЕР? [3, 4, 5] = ДА,
ПЬЕР? [1,2,3] = НЕТ)
