§ 4. Первичные алгоритмы

Предположим, что задан некоторый формальный язык, назовем его L, и некоторое число операций, причем среди них есть и такие, которые применимы к предложениям языка L. Предположим, что, кроме того, задано некоторое число предикатов, представляющих собой утверждения о конструкциях. Язык L будем называть языком операндов.

Пусть, кроме языка L, задан еще один язык L*, пред­ложения которого называются записями первичного алгорит­ма. Язык L* очень прост. Его можно задать с помощью нотации Бекуса. Применяемые при этом формулы могут иметь вид

<Запись первичного алгоритма> ::== <приказ> | <Запись первичного алгоритма> <приказ>

Эта формула означает, что запись первичного алгоритма есть строка, образованная из приказов.

Следующая формула разъясняет приказ (их бывает два вида):

<приказ> ::= <условный приказ> | <безусловный приказ>

Мы могли бы и далее продолжить описание предложений языка L*, пока не дошли бы до перечня букв — алфавита этого языка.

Но формальное описание языка занимает много места и не очень подходит для чтения, хотя и обладает наибольшей возможной точностью. Опишем язык L* на русском языке, лишь изредка прибегая к формулам Бекуса. Каж­дый безусловный приказ состоит из расположенных друг за другом метки, разделителя-1, знака действия, раздели-теля-2, безусловной отсылки и разделителя-3. Его струк­тура может быть передана так:

<метка> <разделитель-1> <знак действия> <разделитель-2> <безусловная отсылка> <разделитель-3>

Условный приказ вместо знака действия имеет знак условия, может иметь другие внутренние разделители и вместо безусловной отсылки имеет условную отсылку. Его структура такова:

<метка> <разделитель-4> <знак условия> <разделитель-5> <условная отсылка> <разделитель-3>

Будем считать, что структура безусловной отсылки такая же, как и метки:

<безусловная отсылка> ::= <метка>

Условная отсылка представляет собой две метки, разде­ленные разделителем-6. Ее структура имеет вид

<метка> <разделитель-6> <метка>

У нас ничего не сказано о таких метатерминах, как разделители, метки, знаки действий и знаки условий. Мы их не определили умышленно, чтобы по приведенной схеме можно было строить разные языки.

Заметим только, что все эти элементы приказов явля­ются словами в алфавите языка L*. Но эти слова должны удовлетворять некоторым условиям. Они должны быть та­кими, чтобы каждый приказ расчленялся на них единствен­ным способом.

Предположим теперь, что мы выбрали алфавит языка L* и определили каждый из классов морфем (метки, 6 видов разделителей, столько знаков действия, сколько не­логических операций, и столько знаков условий, сколько предикатов). Теперь мы имеем вполне конкретный язык, предложениями которого являются вполне конкретные записи первичных алгоритмов. Но предложения языка L* пока что не имеют никакого смысла. Давайте наделим их семантикой и сделаем это по следующему правилу.

Правило выполнения первичного алгоритма.

1. Найти первый приказ в записи первичного алгоритма. Перейти к п. 2.

2. Определить, является ли приказ безусловным или условным. В первом случае перейти к п. 3; во втором — к п. 5.

3. Найти в приказе знак действия. Выполнить отвечаю щую ему операцию над преобразуемым объектом. Безуслов­ную отсылку принять за отсылку. Перейти к п. 4.

4. Найти в записи алгоритма, двигаясь от его начала к концу, приказ, метка которого одинакова с выбранной отсылкой. Вернуться к п. 2.

5. Найти в приказе знак условия. Определить, удовле­творяет ли ему преобразуемый объект. Если да, то перейти к п. 6, если нет, то перейти к п. 7.

6. Первую из меток, входящих в состав условной от­сылки данного приказа, принять за отсылку. Перейти к п. 2.

7. Вторую из меток, входящую в состав условной от­сылки данного приказа, принять за отсылку. Перейти к п. 2.

Хотя правило выполнения первичного алгоритма напи­сано на естественном языке, но оно является совершенно точным при условии, что задан набор действий и условий. Для формулировки этого правила выбран такой подъязык русского языка, который, по существу, является формаль­ным.

Теперь наш язык L* наделен семантикой. Будем этот наделенный семантикой язык называть первичным алгорит­мическим языком. Его наделенные смыслом предложения называются первичными алгоритмами.

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

Забегая вперед, будем иметь в виду, что первичные алгоритмы являются алгоритмами. Если читателя удивляет такое заявление (например, потому, что это будто бы сама собой разумеется: ведь слова «первичный алгоритм» уже значат, что это алгоритм), то автор приведет пример из другой области: «морская свинка» совсем не «свинка».