lekcii2 (Лекции), страница 7

Полученная таким образом составная инструкция может быть использована всюду, где дозволяется простая инструкция. В настоящее время, когда параллельное выполнение, многопроцессорность и многозадачность реальны и доступны, нельзя не упомянуть и о параллельной композиции. Композируемые элемент| л в этом случае выполняются параллельно и независимо, что должно отражаться в форме записи: вместо точки с запятой для разделения параллельно выполняемых Ветвей могут использоваться знаки !! Или П. 3.1.4 Охраняемые инструкции Во многих задачах не существует единого списка инструкций, выполняющих требуемые вычисления во всех случаях. Рассмотрим простой пример.

Пусть требуется вычислить значение функции ( х при х<0; х+х при х>0 Очевидно, что выражение, которое необходимо использовать для вычисления значения функции, зависит от значения аргумента,. Было бы желательно организовать вычисления следующим образом: о присвоить перегиепной Х значение переменной х; о если х > О, то прибавить х2 к 1: о если же х ( О, то инструкцию, по которой осугдествляется прибавление х,пропу- 2 стить. таким образом, надо иметь возможность разрешать или запрещать выполнение той или иной инструкции в зависимости от выполнения определенных условий. Инструкцию, выполнение которой зависит от текущето состояния вычислительной системы, будем называть ахумьнлемой. Охрана инструкции осуществляется предохраагителем, Общий вид предохранителя (логическое выражение>? Логическое выражение принимает одно из двух возможных значений -- И (Исгпина'~ или Л (дожь).

Если логическое выражение принимает значение И (истина), то инструкция, непосредственно записанная за символом ?, выполняется. В противном случае инструкция, следующая за символом ?, пе выполняется (пропускается). В простейшем случае предохранитель используется для охраны инструкции присваивания, входящей в композицию, в следующей форме: <логическое выражение> ? <инструкция присваивания> Если логическое выражение принимает значение И, .то выполняется инструкция присваивания, следующая за предохранителем. В н1зо"тинном случае зта инструкция пропускается. С использованием охраняемой инструкции программа для вычисления значения функции может быть записана следующим образом: 1:=Х; Х>0 ? 1:=1+Х~Х; ЕЖВ Предохранитель используется в двух других составных инструкциях: ветвлении и цик- ле.

130 3.1.5 Обобщенная инструкция ветвления Инструкцию ветвления (1Г-Е1) определим следующим образом: 1Е <предохранитель1> <охраняемая инструкция1> П <предохранитель2> <охраняемая инструкция2> П <предохранитель > <охраняемая инструкция > Е1 Символы 1Е и Р1 играют роль открывающей и закрывающей скобок инструкции ветвления, символ П играет роль разделителя охраняемых инструкций, входящих в состав ветвления. По инструкции ветвления из списка, охраняемых инструкций, заключенных в скобки 1Р— У1, должна, быть выбрана одна и только одна, инструкция (для выполнения), и причем та, предохранитель которой принимает значение И (истица).

С использованием инструкции встьления программа для вычисления значения функции (см. и, 3.3.2) может быть записана следующим обра:юм: ВЕС1Х 1Р Х > 0 '? ?':= Х:, Ц Х (О '?,?:= Л Х*Х; Е1; ЕЛ'й Правила выполнения инструкции ветвления следующие: с Одноврелсенно и независимо вычисляются все предохранители. с Среди вычисленных предохранителей инструкции ветвления должен быть >готя бы один, приниманлций значение И. Если среди предохранителей инструкции ветвления нет ни одного, принимающего значение И, то происходит ОТКАЗ вЂ” выполнение программы прекращается (аварийно!). Таким образом, отсутствие среди предохранителей инструкции 1Е Р1 предохранителя, приниманлцего в момент выполнения инструкции значение И, воспринимается как грубая ошибка периода выполнения, препятствующая дальнейшему хоть сколько-нибудь осмысленному выполнению программы.

Дело в том, что при планировании ветвления программист должен позаботиться о «полноте» системы предикатов в охраняемых инструкциях, и предусмотреть дополнительную ветвь, отрицающую все предикаты. о Допускается, чтобы среди предохранителей инструкции ветвления было более одного предохранителя, принимающего значение И при выполнении инструкции 1Г-Р1. При этом не предполагается,, что охраняемые инструкции каким-либо образом упорядочены. Следовательно. если среди предохранителей инструкции 1Е Е1 окажется, например, два предохранителя, принимающих значение И (истина), то вьсбор инструкции для выполнения осуществляется недетерминированпым образом и не опредаляется порядком записи охраняемых инструкций в инструкции 1Г Р1. Недетерминированное ветвление, 131 вооощс гово«>я, неа.п ори гмичпо и От«>ажае Г Го Г фак Г ч! О >л«>О! раммис>у Все рави(> по какой из открыл>шихся ветвей действительно произошло ветвление.

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

Дейкстры. Например, двузвеннос ветвление 1Р р? я1П пот р? я2Е1 в Паскале и Си реализуются практически одинаково: 11'(р) я«Д; е1яе я2«); Ы р ФЬел! э1 е1яе а2; а многозвеннь>й переклкп>>!тель (избыточный по теорем! Н»>йыа-Д>какл>пи>ли-Миллса): 1Р е = е1 ? я1 П е = е2 ? я2 е = еп ? яп П $Ч записывается на этих языках несколько по-разному: Естественно, здесь все детерминировано. Пользуясь конкретными вариантами инструкции ветвления, необходимо внимательно изучать их особенности и не только по описанию стандарта языка. Например, в Паскале в случае несовпадения текущего варианта ни с одной из предусмотренных меток вместо благородного и шумного отказа от неудачного ветвления втихую происходит продолжение работы программы.

Исправление такой ситуации веткой, вылн>лпяемой по умолчанию (о««леглг>яе или е1ае), увы, не стандартизовано. В С~С вЂ”,+ есть стандартная опциональная метка с«егап1с, которая получает управление в случае, когда не сработал ни один из саяе»ов. 3.1.6 Обобщенная инструкция цикла Пусть требуется вычислить значение «'(и) = и! для заданного значения и,. Посгавим целью составить программу вычисления и! для любого задаваемого значения и,. Очевидно, что саяе е оГ е1: я1; е2 : Б2; сп: яп; епс1; ялл йсЬ(е) ( е1: я1Ц; Ьгеа1с; <2: я2Ц; Ьгеа1с; еп: яп1); э!'О можно сдю!аг'ь по сг)ецу)ощиы соотнопюниям: при и=О ~(п) =1; при !'>О ~г=12,...,п) ~Я= ~(г,' — 1)*г, даю)цим правила вычисления каждого последующего значения функции через предыдущее. Следовательно, программа должна содержать: определение начального значения функции г (О) и завершение вычисления, если и = О: последовательное умножение значения функции на г = 1, 2,..., п до тех пор, пока !' < п, где п, — задаваемое зн)п)ение.

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

Такой инструкцией является инструкция цикла, которую мы определим для общего случая следующим образом: 1ЭО <предохранитель! > <охраняемая инструкция! > П <предохранитель2> <охраняемая инструкция2> П <предохранитель,„> <охраняемая инструкция > О1Э Что русскому хорошо, то немцу смерть Русская пословица Несмотря на, то, что инструкция цикла 1ЭΠ— О1Э внешне похожа на инструкцию ветвления, правила выполнения этой инструкции опреде.тяются иначе; о Если среди предохранителей инструкции ИО О1Э один и только один принимает значение И, то соответствующая охраняемая инструкция выполняется, и после этого вновь осуществляется одновременная и независимая проверка всех, предохранителей инструкций цикла.

Следует обратить внимание па то, что охраняемой инструкцией может бытгыа>мпозиция или ветвление,. о Количество предохранителей, принимающих значение И, также моа)сепг, бь)ть более одного. В этом случае не предполагается, что охраняемые инструкции упорядочены и выбор инструкции для вьпюлнения очередного повторения цикла осуществляется вне связи с порядком их написания в инструкции 1ЭΠ— О1Э, т.

е, недетерминированным образом. о Если среди предохранителей инструкции РΠ— ОР нет ни одного, принимающего значение И, то, в о!пгг)гнив от ветпвлетля, выполнение инструкции заканчивается естественным образом в связи с отсутствием инструкции, открытой для продолжения работы цикла. о Выполнение каждой охраняемой инструкции должно приводить к изменению аргументов предохранителей. В противном случае выполнение инструкции 1ЭО-О1Э может никогда не закончиться, яВОр? я ОП или так 11ая := сгпе ВО х1ая ? я ОП с1о аД; Мп1е (р); гер еаза ппй1 по$ р; Лекция 18 3.2 Типы данных 3.2.1 Определение типа данных Тип данных -- это множество изображений (слов над некоторым алфавитом), для которых определено правило их интерпреташси, позволяющее каждому изображению сопоставить его значение, и лсножестпво атрибутов, которые позволяют одному или нескольким элементам типа данных сопоставить либо изображения данных того же типа, либо изображения данных другого типа.

В частности, к атрибутам типа данных относятся минимальное и максималыюе значения, количество значений типа, операции, отношения и функции, определенные над значениями этого типа. Т. е. определение типа имеет теоретико-множественный и алгебраический аспекты. Интерпретация задается с помснцьн) отображс;ния: 135 где И' — - множество изображений, а Л вЂ” множество значений. В отличие от человека машина не может непосредственно работать ни с абстрактными математическими объектами, такими как числа, множества, логические значения и литеры,. ни с предмс тами,прсдставляющими их материальные физические реализации (счетными палочками, оловянными литерами из типографской кассы, карточками, кубиками и прочими суррогатами из набора первоклассника). Машина всегда работает со словами небольшой и фиксированной длины, представляющими собой допустимые значения, которые по отношению к тем абстрактным объектам являются изображениями.