1.8. ЯЗЫК ВЫСОКОГО УРОВНЯ — УПРОЩЕННЫЙ АЛГОЛ

Наши основные меры сложности определяются в терминах операций для РАМ, РАСП и машин Тьюринга, но мы, вообще говоря, не хотим описывать алгоритмы в терминах столь простых машин, да в этом и нет необходимости. Для того чтобы нагляднее описывать алгоритмы, мы введем некоторый язык высокого уровня, называемый Упрощенным Алголом.

Программу на Упрощенном Алголе можно перевести непосредственно в программу для РАМ или РАСП. Фактически это была бы

в точности роль транслятора с Упрощенного Алгола. Нас, однако, не будут интересовать детали перевода Упрощенного Алгола в конкретные программы для РАМ или РАСП. Для наших целей нужно рассматривать лишь время и память, необходимые для выполнения команд, соответствующих операторам на Упрощенном Алголе.

Упрощенный Алгол отличается от всех принятых языков программирования тем, что он разрешает использовать любой тип математических предписаний, если только их значения понятны, а перевод в команды РАМ или РАСП очевиден. Этот язык не имеет также фиксированного набора типов данных. Переменные могут представлять целые числа, слова и массивы. Дополнительные типы данных — множества, графы, списки, очереди и т. п. — можно вводить по мере необходимости. Формальные описания типов данных по возможности избегаются. Тип данных какой-то переменной и ее область действия должны быть ясны либо по ее названию, либо по контексту.

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

Программа на Упрощенном Алголе — это оператор одного из следующих типов:

(см. скан)

(см. скан)

Дадим обзор каждого из этих операторов.

1. Оператор присваивания

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

2. В if-операторе

условием, следующим за может быть любое выражение, принимающее значение true или false. Если это условие имеет значение true, то надо выполнять оператор, стоящий за then. В противном случае надо выполнять оператор, стоящий за else (если else есть). Вес -оператора равен сумме весов, требуемых для вычисления значения и проверки его, и веса оператора, стоящего сразу за then, или оператора, стоящего за else, в зависимости от того, какой из них выполнялся на самом деле.

3. Назначение

и repeat оператора

состоит в организации цикла. В -операторе вычисляется значение условия, идущего после Если оно истинно (принимает значение то выполняется оператор, стоящий после Этот процесс повторяется до тех пор, пока условие не станет ложным. Если вначале это условие было истинным, то выполнение оператора должно в конце концов привести это условие к значению чтобы закончилось выполнение -оператора. Для вычисления веса -оператора суммируются веса всех проверок условия и всех выполненных операторов.

repeat-оператор трактуется аналогично, но только теперь оператор, стоящий за выполняется перед проверкой условия.

4. В for-операторе

"исходное значение", "размер шага" и "заключительное значение" являются выражениями. В случае когда размер шага положителен, "переменная" (называемая индексом) полагается равной значению выражения для исходного значения. Если оно больше заключительного значения, то выполнение оператора заканчивается. В противном случае выполняется оператор, стоящий после значение переменной увеличивается на величину шага и сравнивается с заключительным значением. Процесс повторяется до тех пор, пока значение переменной не превзойдет заключительное значение. Случай, когда размер шага отрицателен, трактуется аналогично с той лишь разницей, что окончание происходит, когда значение переменной становится меньше заключительного значения. Вес -оператора должен быть очевиден в свете предшествующего анализа -оператора.

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

5. Любой оператор можно переделать в помеченный оператор, написав перед ним метку, за которой стоит двоеточие. Главное назначение метки — создание цели для -оператора. Меткам не приписывается никакого веса.

6. goto-оператор

указывает, что дальше выполняется оператор с данной меткой. Этот оператор не может стоять внутри блока типа 7, если сам -оператор не находится в том же блоке. Вес равен 1. goto-оператора следует применять изредка, ибо, вообще говоря, они затрудняют понимание программы. Основное применение goto-оператора - это выход из -операторов.

7. Последовательность операторов, отделенных друг от друга точками с запятыми и заключенных между выделенными словами begin и образует оператор, который называется блоком. Так как блок является оператором, его можно применять всюду, где предусмотрено применение оператора. Обычно программа будет блоком. Вес блока равен сумме весов операторов, составляющих блок.

8. Процедуры. В Упрощенном Алголе процедуры можно определять и впоследствии вызывать. Процедуры определяются оператором определения процедур

Список параметров — это последовательность фиктивных переменных, называемых формальными параметрами. Например, следующий оператор определяет процедуру-функцию

Аргументы х и у являются формальными параметрами.

Процедуры используются одним из двух способов. Один .способ — в качестве функции. После того как процедура-функция описана, к ней можно обратиться в некотором выражении, вызывая ее имя с нужными аргументами. В этом случае последним оператором, выполняемым в данной процедуре, должен быть -оператор (86). Этот оператор приводит к вычислению значения выражения, следующего за выделенным словом и окончанию выполнения процедуры. Значением функции будет значение этого выражения. Например,

приводит к тому, что А получает значение 5. Выражения и 7 называются фактическими параметрами этого обращения к данной процедуре.

Второй способ применения процедуры состоит в вызове ее с помощью оператора вызова процедуры (8в). Этот оператор есть, по существу, имя процедуры, за которым идет список фактических параметров. Оператор вызова процедуры может изменить и

(обычно изменяет) данные (значения переменных, массивов и т. д.) вызываемой программы. В определении вызываемой таким способом процедуры геturn-оператор не нужен. Завершение выполнения последнего оператора процедуры завершает и выполнение оператора ее вызова. Например, следующий оператор определяет процедуру

ВЗАИМОЗАМЕНА

Для обращения к этой процедуре можно было написать оператор вызова процедуры, такой, как

Обмен информацией между процедурами можно осуществлять двумя способами. Во-первых, с помощью глобальных переменных. Мы предполагаем, что глобальные переменные неявно описаны в некоторой универсальной области. В этой области есть подобласть, в которой определены процедуры.

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

9. Смысл и -оператора очевиден. Вес -оператора равен 1. Вес -оператора на 1 больше веса вычисления значения выражения, стоящего за выделенным словом

10. cotntnent-оператор позволяет вставлять замечания, облегчающие понимание программы, и имеет вес 0.

11 В дополнение к операторам общепринятых языков программирования мы включили под именем "произвольные" любые операторы, благодаря которым алгоритм можно понять легче, чем эквивалентную последовательность стандартных операторов языка программирования. Такие операторы используются в ситуациях, когда детали реализации либо несущественны, либо очевидны или когда желательно дать описание на языке еще более высокого уровня. Приведем примеры обычно используемых "произвольных" операторов:

Например,

означает, что если то стоящий дальше оператор следует выполнять так, как он записан, а если то выполнять этот оператор, предварительно поменяв в нем end местами.

Реализация таких операторов в терминах общепринятых языков программирования или команд РАМ не вызывает затруднений, но она очень утомительна. Приписывание весов операторам такого типа зависит от контекста, в котором оказывается данный оператор. Дальнейшие примеры операторов такого рода не раз встретятся нам в этой книге в программах на Упрощенном Алголе.

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

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

УПРАЖНЕНИЯ

(см. скан)

(см. скан)

(см. скан)

Замечания по литературе

РАМ и РАСП получили формальную трактовку у Шепердсона, Стерджиса [1963], Элгота, Робинсона [1964] и Хартманиса [1971]. В изложении большей части результатов о РАМ и РАСП в этой главе мы следуем работе Кука, Рекхау [1973].

Идея машины Тьюринга принадлежит Тьюрингу [1936]. Более подробное изложение этого понятия можно найти у Минского [1967] и Хопкрофта, Ульмана [1969]; это же касается и ответа к упр. 1.8. Изучение временной сложности машин Тьюринга было начато Хартманисом, Стирнзом [1965], а емкостной сложности — Хартманисом, Льюисом, Стирнзом [1965] и Льюисом, Стирнзом, Хартманисом [1965] 1). Начиная с работы Блюма [1967], делались попытки трактовать вычислительную сложность с гораздо более абстрактной точки зрения. Обзоры можно найти у Хартманиса, Хопкрофта [1971] и Бородина [1973а].

Рабии [1972] предложил одно интересное обобщение понятия дерева решений.