4 СЕМАНТИЧЕСКАЯ ХАРАКТЕРИСТИКА ЯЗЫКОВ ПРОГРАММИРОВАНИЯ
(продолжение)
подчеркивается явно либо потому, что оно=Т, либо потому, что мы исходим из предположения, что оператор присваивания никогда не будет запущен в начальных состояниях, не принадлежащих области определения выражения
Е.Естественным обобщением оператора присваивания является излюбленное некоторыми программистами так называемое "одновременное присваивание". В этом случае возможна одновременная замена для нескольких^азличкыхпеременных. Оператор одновременного присваивания обозначается списком различных переменных), подлежащих замене (эти переменные разделяются запятыми), слева от знака присваивания и столь же протяженным списком выражений (также разделяемых запятыми) справа от знака присваивания. Итак, разрешается писать
В иной записи эта операция выглядела бы более громоздкой. Легкость реализации одновременного присваивания и возможность с его помощью избегать некоторой избыточности записи являются причинами популярности таких операторов. Заметим, что если списки становятся слишком длинными, то получаемая программа становится весьма неудобочитаемой.
Истинный любитель НФБ расширит свой синтаксис, обеспечив две различные формы для оператора присваивания, следующим образом:
(оператор присваивания) ::={переменная) := (выражение)!
(переменная), (оператор присваивания), (выражение)
Это так называемое "рекурсивное определение", поскольку одна из альтернативных форм для синтаксической единицы, именуемой "оператор присваивания" (а именно вторая форма), содержит в качестве одного из своих компонентов снова эту же синтаксическую единицу, именуемую "оператор присваивания", т. е. ту самую синтаксическую единицу, которую мы определяем! На первый взгляд такое циклическое определение выглядит ужасающе, но после более внимательного изучения мы можем убедиться в том, что, по крайней мере с синтаксической точки зрения, в этом нет ничего неправильного. Например, поскольку, согласно первой альтернативе,
допускает разбор вида
ж1, (оператор присваивания),
Е2а следовательно, согласно второй альтернативе, также является оператором присваивания. Однако с семантической точки зрения это отвратительно, потому что получается, что
Е2 ассоциируется с х\ вместо того, чтобы ассоциироваться с х2.В сравнении с двухоператорным языком, содержащим только "пропустить" и "отказать", наш язык с оператором присваивания выглядит значительно более богатым: уже нет какой бы то ни было верхней границы для числа различных примеров синтаксической единицы "оператор присваивания". Но он все же явно недостаточен для наших целей; нам нужна возможность строить более
изощренные программы, более сложные конструкции. Для построения потенциально сложных конструкций мы пользуемся схемой, которую можно рекурсивно описать так:
(конструкция) ::= (простая конструкция)|
(правильная композиция записей вида: (конструкция))
Для того чтобы эта схема могла принести хоть какую-нибудь пользу, необходимо выполнение двух условий: в нашем распоряжении должны иметься "простые конструкции", чтобы было с чего начать, и, кроме того, мы должны знать, как строить "правильные композиции". Введенные раньше операторы можно взять в качестве простых конструкций; оставшаяся часть этой главы посвящена именно процессу правильной композиции некоей новой конструкции из заданных конструкций. Новая конструкция в свою очередь может выступать в роли части еще более сложного составного объекта.
После того, как объект был образован композицией частей, мы можем рассматривать его двумя способами. Во-первых, мы можем считать его "нераздельным целым", воспринимая его свойства в большей или меньшей степени как магические (или принимая их на веру или как постулаты). При таком подходе существенны только свойства конструкции; не имеет никакого значения, каким образом она образована из своих частей. С такой точки зрения любые две конструкции, обладающие одинаковыми свойствами, эквивалентны. Или же мы рассматриваем конструкцию как "составной объект", образованный так, что мы можем понять, почему она обладает объявленными свойствами. При этом мы воспринимаем части как "малые" нераздельные целые, для которых принимаются в расчет только их общие свойства. Второй подход вносит ясность в то, что мы понимаем под "композицией". Композиция должна определять, как свойства целого следуют из свойств частей.
После этих общих замечаний вернемся к нашим конкретным конструкциям, свойства которых, как мы считаем, выражаются их преобразователями предикатов. Точнее говоря, если заданы две конструкции 51 и S2, чьи преобразователи предикатов известны, можем ли мы представить себе правило вывода нового преобразователя предикатов из двух заданных? Если да, то мы можем считать результирующий преобразователь предикатов описанием свойств составного объекта, построенного специальным образом из частей 51 и S2.
Одним из простейших способов получения новой функции из двух заданных является так называемая "функциональная композиция", т. е. предоставление значения одной функции в качестве аргумента для другой. Составной объект, соответствующий такому преобразователю предикатов, принято обозначать через "SI; S2", и мы определяем
что при желании можно рассматривать как семантическое определение точки с запятой.
Замечание.
Из того факта, что преобразователи предикатов для 51 и S2 обладают свойствами 1—4 из предыдущей главы, можно заключить, что и определенный выше преобразователь предикатов для "51; 52" также обладает этими четырьмя свойствами. Например, поскольку для 51 и 52 справедлив закон исключенного чуда:
Читателю предоставляется в качестве упражнения проверить, что остальные три свойства тоже сохраняются. (
Конец замечания.)Перед тем как продолжить наши рассуждения, убедимся в том, что этим формальным описанием семантики точки с запятой охватывается наше интуитивное представление о ней (если оно у нас есть!), т. е. что составная конструкция "51; 52" может быть реализована но правилу "сначала запустить конструкцию 51 и по окончании ее работы запустить 52". В самом деле, в нашем определении wp("51; 52",
К) мы представляем Д-постусловие для составной конструкции — как постусловие к преобразователю предикатов для 52, и этим отражается то, что общая работа конструкции "51; 52" может закончиться с окончанием работы 52. Соответствующее слабейшее предусловие для 52, т. е. wp(52, R), представляется как постусловие к преобразователю предикатов для 51; тем самым мыявно отождествляем начальное состояние для S2
с конечным состоянием для 51. Однако именно так и бывает, если работа 51 непосредственно предшествует во времени запуску 52.Чтобы удостовериться в этом, рассмотрим пример. Пусть "51; 52" представляет собой
т.е мы можем гарантировать выполнение отношения R между конечными значениями а и
Ъ при условии, что первоначально то же отношение выполняется между а + Ьи(а + Ь)*Ь соответственно.И наконец, поскольку функциональная композиция обладает свойством ассоциативности, то не имеет значения, будем ли мы разбирать "SI; S2; S3" как "[SI; S2]; S3" или же как "S1;[S2;S3]". Иначе говоря, мы имеем полное право трактовать точку с запятой как символ сочленения; поэтому не возникает никакой неопределенности, когда мы выписываем операторный список вида "5i; 52; 5з; ...; 5
И", и мы будем без стеснения поступать так, когда для этого представятся подходящие случаи.Упражнение.
Проверьте, что конструкции
До введения точки с запятой мы могли писать только однооператорные программы; с помощью точки с запятой мы обрели способность писать программы в виде сочленения из
п, (п > 0) операторов: "5i; 52? 5з; ...; Sn". Если исключить промежуточную незавершенность, выполнение каждой программы всегда означает временную последовательность выполнений п операторов, сначала 5i, потом 52 и так далее до Sn включительно. Однако из нашего примера игры на листе картона, реализующей алгоритм Евклида, мы знаем, что должны уметь описывать более широкий класс "правил игры": всякая игра будет состоять из последовательности перемещений, где каждое перемещение имеет вид либо "ж := ж — у", либо "у '.= у — ж", но способ чередования этих перемещений во времени и даже их общее число будут изменяться от игры к игре; он зависит от начального положения фишки, он зависит от начального состояния системы. Если точка с запятой является единственным нашим средством для составления нового целого из заданных частей, то мы не в состоянии этого выразить, и поэтому нам необходимо искать нечто новое.Пока точка с запятой остается единственным имеющимся в нашем распоряжении средством соединения, единственным обстоятельством, при котором происходит запуск одной из составляющих конструкций Si (г > 1), являются правильное завершение работы (лексикографически) предшествующей конструкции. Чтобы добиться нужной нам гибкости, необходимо обеспечить возможность запуска той или иной (под) конструкции в зависимости от текущего состояния системы. Для этого мы введем — в два этапа — понятие "охраняемой команды", синтаксис которой задается следующим образом:
(охраняющий заголовок) ::= (логическое выражение) —>•
(оператор)
(охраняемая команда) ::= (охраняющий заголовок)!; (оператор)}
где фигурные скобки "{" и "}" следует читать так: "сопровождается любым числом (быть мозкет, нулем) экземпляров содержимого скобок".
(Другой вариант синтаксиса охраняемой команды мозкет выглядеть так:
(список операторов) ::= (оператор)!; (оператор)} (охраняемая команда) ::= (логическое выражение) —>• (список операторов)
Однако по причинам, которые не должны нас теперь интересовать, я предпочитаю синтаксис, в котором вводится понятие охраняющего заголовка).
В этом сочетании логическое выражение, предшествующее стрелке, называется "предохранителем". Идея состоит в том, что следующий за стрелкой список операторов будет выполняться лишь при том условии, что обеспечена начальная истинность значения соответствующего предохранителя. Предохранитель позволяет нам избежать выполнения списка операторов при тех первоначальных обстоятельствах, когда это полнение оказалось бы нежелательным или (если употребляются частично определенные операции) невозможным.
Истинность значения предохранителя является необходимым предварительным условием для выполнения охраняемой команды как целого; это условие, разумеется, не является достаточным, поскольку тем или иным способом — с двумя такими способами мы встретимся — до него еще должна дойти потенциальная "очередь". Именно поэтому охраняемая команда не рассматривается как оператор: оператор безоговорочно выполняется, когда наступает его очередь, а охраняемая команда мозкет использоваться в качестве строительного блока для оператора. Если говорить точнее, мы предложим два различных способа составления оператора из набора охраняемых команд.
После некоторого осмысливания рассмотрение набора охраняемых команд представляется вполне естественным. Предположим, что нам требуется построить конструкцию, такую, чтобы при условии, что начальное состояние удовлетворяет Q, конечное состояние удовлетворяло R. Предположим далее, что нам не удается найти единый список операторов, который выполнял бы эту работу в любых случаях. (Если бы такой список операторов существовал, то мы именно его бы и использовали и не возникло бы потребности в охраняемых командах.) Однако нам мозкет удасться найти несколько списков операторов, каждый из которых будет выполнять нужную работу для некоего подмножества возможных начальных состояний. К каждому из этих списков операторов мы можем присоединить в качестве предохранителя логическое выражение, характеризующее то подмножество, для которого этот список подходит, и если у нас имеется вполне достаточный набор предохранителей, такой, что из истинности Q всегда логически следует истинность значения хотя бы одного предохранителя, то для каждого начального состояния, удовлетворяющего Q, мы располагаем конструкцией, которая переведет систему в состояние, удовлетворяющее условию R, причем этой конструкцией служит одна из охраняемых команд, чей предохранитель имел начальное значение "истина". Чтобы выразить это, определим сначала
(набор охраняемых команд) ::= (охраняемая команда){[](охраняемая команда)}
где символ "[]" выступает в роли разделителя вариантов, в остальном не упорядоченных. Один из способов формирования оператора из набора охраняемых команд состоит в том, чтобы включить такой набор в пару скобок "if .. .fi", при этом наш синтаксис для синтаксической категории, именуемой "оператор", пополняется следующей формой:
(оператор) ::= if (набор охраняемых команд) fi
Таким образом, мы получаем возможность объединить несколько охраняемых команд в новую конструкцию. Мы можем представить себе работу, которая произойдет после запуска этой конструкции, следующим образом. Выбирается одна из охраняемых команд, чей предохранитель является истинным, и запускается ее список операторов.
Прежде чем мы перейдем к изложению формального описания семантики нашей новой конструкции, уместно сделать три замечания.
1. Предполагается, что все предохранители определены; если это не так, т. е. вычисление какого-то предохранителя мозкет принести к работе без правильного завершения, то допускается, что и вся конструкция не сможет правильно завершить свою работу.
2. Вообще говоря, наша конструкция приведет к недетерминированности при тех начальных состояниях, для которых истинны значения более чем одного предохранителя, поскольку остается
неопределенным, какой из соответствующих списков операторов будет тогда выбираться для запуска. Никакой недетерминированности не возникает, если все предохранители попарно исключают друг друга.
3. Если начальное состояние таково, что ни один из предохранителей не является истиной, то мы встречаемся с начальным состоянием, для которого не подходит ни один из вариантов, а следовательно, и вся конструкция в целом. Запуск при таком начальном состоянии приведет к отказу.
Замечание.
Если мы допускаем также и пустой набор охраняемых команд, то оператор "if-fi" семантически эквивалентен нашему прежнему оператору "отказать". (Конец замечания.)(В следующем формальном определении слабейшего предусловия для конструкции if-fi мы ограничимся случаем, когда все предохранители являются полностью определенными функциями. Если это не так, то нужно переписать выражение с использованием символа cand при дополнительном требовании, чтобы начальное состояние принадлежало области определения всех предохранителей.) Обозначим через "IF" оператор 1
Э. Дейкстра. "Дисциплина программирования"
29и через "IF" оператор, получаемый путем заключения того же набора охраняемых команд в пару скобок "if ... fi". Если условия
Н^(К) задаются в видеЗдесь интуитивно мы понимаем Hk(R) следующим образом: это слабейшее предусловие, такое, что конструкция do-od завершит свою работу после не более чем k выборок охраняемых команд, причем система останется в конечном состоянии, удовлетворяющем постусловию R.
При k = О требуется, чтобы конструкция do-od завершила работу, не производя выборки какой-либо охраняемой команды, т. е. не допускается существования какого-либо предохранителя с истинным значением, что и выражено вторым логическим сомножителем. При этом начальная истинность
R очевидным образом является необходимым условием для конечной истинности R, что и выражено первым логическим сомножителем.При k > О нам нужно различать два случая: либо ни один из предохранителей не имеет истинного значения, но тогда должно выполняться условие R, и это приводит нас ко второму логическому слагаемому; либо хотя бы один предохранитель является истиной, и тогда события развиваются так, как при однократном запуске оператора "IF" (в начальном состоянии, которое не может привести к немедленному отказу вследствие отсутствия истинных значений предохранителей). Однако после такого выполнения, при котором производилась выборка одной охраняемой команды, нам необходима гарантия попадания в состояние, такое, чтобы потребовалось не более чем (k
— 1) дальнейших выборок для достижения завершения работы в конечном состоянии, удовлетворяющем R. В соответствии с нашим определением, таким постусловием для этого оператора "IF" служит H/.-i(R).Согласно последней строке, определяющей wp(-DO, R), должно существовать такое значение k, чтобы потребовалось не более чем k выборок для обеспечения завершения работы в конечном состоянии, удовлетворяющем постусловию R.
Замечание.
Если мы допускаем также и пустой набор охраняемых команд, то в силу сказанного оператор "do od" семантически эквивалентен нашему прежнему оператору "пропустить". (Конец замечания.)
Здесь интуитивно мы понимаем Hk(R) следующим образом: это слабейшее предусловие, такое, что конструкция do-od завершит свою работу после не более чем k выборок охраняемых команд, причем система останется в конечном состоянии, удовлетворяющем постусловию R.
При k = О требуется, чтобы конструкция do-od завершила работу, не производя выборки какой-либо охраняемой команды, т. е. не допускается существования какого-либо предохранителя с истинным значением, что и выражено вторым логическим сомножителем. При этом начальная истинность
R очевидным образом является необходимым условием для конечной истинности R, что и выражено первым логическим сомножителем.При k > О нам нужно различать два случая: либо ни один из предохранителей не имеет истинного значения, но тогда должно выполняться условие R, и это приводит нас ко второму логическому слагаемому; либо хотя бы один предохранитель является истиной, и тогда события развиваются так, как при однократном запуске оператора "IF" (в начальном состоянии, которое не может привести к немедленному отказу вследствие отсутствия истинных значений предохранителей). Однако после такого выполнения, при котором производилась выборка одной охраняемой команды, нам необходима гарантия попадания в состояние, такое, чтобы потребовалось не более чем (k
— 1) дальнейших выборок для достижения завершения работы в конечном состоянии, удовлетворяющем R. В соответствии с нашим определением, таким постусловием для этого оператора "IF" служит H/.-i(R).Согласно последней строке, определяющей wp(-DO, R), должно существовать такое значение k, чтобы потребовалось не более чем k выборок для обеспечения завершения работы в конечном состоянии, удовлетворяющем постусловию R.
Замечание.
Если мы допускаем также и пустой набор охраняемых команд, то в силу сказанного оператор "do od" семантически эквивалентен нашему прежнему оператору "пропустить". (Конец замечания.)
