1626435695-d1df5d2e6d953ce7ad4b4ccb5f4f4e30 (844296), страница 44
Текст из файла (страница 44)
Они же анонсировали воаможность трансляции линейных упарпых схем, алгоритм трансляции был позднее предложен Гарландом и Лакхэмом [т02) ГЛАВА 9 ОБОГАЩЕННЫЕ СХЕМ1»1 Стандартные схемы конструируются с привлечением минимального набора программных примитивов иэ внушительного арсенала средств, которыми располагает современный программист. В частности, в этих схемах очень просто устроена память— конечное множество неинтерпретированвых переменных.
Мы же видели в предыдущей главе, к каким трудностям приводит такая простота; в теореме 8.2 именно конечность памяти указана как причина нетранслируемости рекурсивной схемы Я»», а в теореме 8.4 отсутствие интерпретированных переменных типа счетчнков делает построенную стандартную схему неоправданно громоздкой.
Трудно представить себе достаточно содержательную реальную программч без использования таких конструкций, как процедуры, счетчики, массивы, списки и т. д. Эта глава посвшцена расширениям класса стандартных схем, а именно схемам, в которые добавлены выделенные интерпретированные переменные (с заданной областью интерпретации и допустимыми операциями) или »динамические», потенциально бесконечные памяти специальной структуры.
Более конкретно будут рассмотрены схемы со счетчиками (или счетчнковые схемы) и схемы с (одномерными) массивами. Задача состоит в том, чтобы сравнить эти схемы между собой по мощности, а также с рекурсивными и стандартными схемами. Общая цель такого сравнения — выделить »универсальный» класс схем„универсальный в том смысле, что любой из перечисленных нлассов транслируем в этот выделенный. $1.
Классы обогащенных схем 1 1. Счетчики, магазины, массивы. Счетчик — интерпретированная переменная, у которой областью значений является множество целых неотрицательных чисел; начальное значение счетчика равно О. Счетчики входят как переменные только в специальные интерпретированные операторы, которые не содержат »обычных» переменных.
Эти операторы добавляются вместе со счетчиком в базис стандартных схем. Таких интерпретированных операторов три: с:= с + 1 — оператор прибавления единицы; с;= с — 1 — оператор еычитанин единицы; 201 с = Π— условный оператор проверки равенства счетчика нулю. Если значение счетчика равно О, то оператор вычитания единицы не изменяет его, оно остается равным О. Магазин — неянтерпретированная переменная сложной структуры. В процессе выполнения интерпретированной схемы состояние магазина — зто конечный набор алементов (И„И„..., а„) из области интерпретации. Начальное состояние — пустой набор (лзагазии прет).
Значение а„называют верхушкой (непустого) магазина. Магазин входит как переменная только в специальные интерпретированные операторы трех типов: Мг= х — запись в магазин; х:= М вЂ” выборка из гзагазина; М вЂ”.- Я вЂ” усвоений оператор проверки пустоты гзагазина. Здесь М вЂ” магазин; х — обычная переменная. Первый оператор меняет состояние (Из, й,..., и„» магазина М на состояние (д„ а„ ..., И„, Ив.„), где И„„ — значение переменной х.
После выполнения этого оператора элемент И„+ становится новой верхушкой магазина. Второй оператор присваивает переменной х значение, равное верхушке магазина, состояние которогоменяется с (Ы„ дз, ..., й „ й„) на (дм с»з, ..., И„ з), прн этом Ы„, становится новой верхушкой магазина. Если магазин М пуст, то пршюнеиие второго оператора оставляет его пустым, а переменная х не меняет своего значения. Третий оператор в предикат проверки магазина на пустоту; если магазин пуст, то значение предиката М = О равно 1, в противном случае — О. Массив — неннтерпрвтированная переменная сложной структуры.
При выполнении интерпретированной схемы состояние массива — бесконечная последовательность (4, йг, ..., 4, ...) элементов из области интерпретации. Массивы входят только в специальные интерпретированные операторы двух типов: А [е): = х, х:= А [с]„ где А — массив; с — счетчик; [,) — специальные символы; [с) — целое число, равное текущему значению счетчика с. Первый оператор меняет состояние (4, г»з, ... ...,аы, ...) массива А на новое состояние, которое отличается от старого лишь тем, что элемент И~а заменяется на значение переменной х. Второй оператор не меняет состояние массива, а присваивает переменной х значение, равное [е)-му порядковому элементу в состоянии массива.
Начальное состояние массива интерпретированной схемы определяется интерпретацией. Считается, что это — бесконечная последовательность, состоящая иа одного и того же элемента а'из области интерпретацви, т. е. можно начальное значение массива задать так: 1 (А) = а'. Присутствие массивов в схеме требует одновременного введения счетчиков. Ф.й. Примеры обогащенных схем. Добавляя в полный базис стандартных схем счетчики, массивы и магазины, можно обрааовать рааличиые классы обогащенных схем.
Среди них нас в первую очередь интересуют «чистые» классы, которые получены аа счет расширения базиса одним видом дополнительных средств (не считая того, что массивы требуют счетчиков). Так, класс счовнлпяммх слов определяется следующим образом. В полный базис стандартных схем добавляется счетное множество счетчиков, а ко множеству операторов добавляются интерпретированные операторы над счетчиками описанного выше типа.
Клясс лгаоазкнммх схза образован добавлением в базис стандартных схем счетного множества магазинов, а во множество операторов вводятся интерпретированные операторы над магазикамн. Класс схехг с массиоахги — зто расширение класса счетчиковых схем за счет добавления счетного множества массивов и операторов над ними. б г Рас. ВЛ. Стаядортная н обогащенные схема: а — стандартная схема ог.в,. б — счегчяновая стона ог.г, 'г — нагаэяяиоя схема ог.г, г — схема с масса- вами ог. Мы будем наряду с «полными» чистыми классами упоминать н их подклассы (например, класс схем с одним счетчиком), а также «смешанные» классы обогащенных схем (например, класс схем с одним счетчиком и одним магазином). Поэтому целесообразно ввести следующую систему обоаначений классов схем: Р— стандартные; Р (Л) — рекурсивные; У (е) — счетчиковые; Р (М) — магазинные; ,'У (А) — с массивами; У (1с) — с одним счетчиком; т (2с) — с двумя счетчиками; У (2«, 1М) — с двумя счетчиками и одним магазином и т.
д. Понятие интерпретации и интерпретированных схем (программ) переносится на обогащенные схемы естественным образом. Ново- введенные переменные интерпретируются согласно правилам, упомянутым при их определении. Семантика дополнительных операторов также была разъяснена выше. Так как счетчики, магазины и массивы не входят в заключительный оператор, определение функциональной эквивалентности стандартных схем «автоматически» переносится на обогащенные схемы, при этом как на схемы внутри одного класса, так и на схемы из разных классов.
По тем же причинам остаются в силе определение свободяых интерпретаций и теоремы 4 1 — 4.3 о свободных интерпретациях. На рис. 9.1 приведены примеры четырех схем — стандартной 8»л, счетчиковой 8 „магазинной Яв» и схемы с массивами Я, в Все они эквивалентны друг другу и рекурсивной схеме о' из задания 8.6: Р (х), Р (х) = если р (х) то х иначе / (х, Р (у (х))).
(В счетчиковой схеме 8»в использован не упомянутый вьпне оператор пересылки значений счетчиков с:= с,. На самом деле этот оператор — удобное сокращение фрагмента счетчиковых схем, использующего три «базовых» оператора над счетчиками. См. об этом подробнее в следующем параграфе.) 3 а д а н н о 9.1. Покюквто, что схемы Яв,п.
Яв.в. Яв.в. Яв.в в Яв ° зк- 9 2. Проблемы трансляции 2.1. Счетчнковые и рекурсивные схемы. Прн определении счетчика мы ввели три оператора над счетчиками. с:= с+ 1, с:= с — 1 и с = О. Формально в классе счетчнковых схем допускается использование только этих операторов, однако удобнее, по мере надобности, расширять этот «базовый» набор из трех операторов другими операторами над счетчиками, как уже было сделано в случае схемы 8»в. Но мы должны быть уверены, что добавляемые операторы над счетчиками не выведут нас из класса счетчиковых схем (такого, как мы его определили).
Один из способов убедиться в этом — представить вводимый оператор как фрагмент счетчиковой схемы, составленный из базовых операторов. Например, введение в базис класса ~ (с) оператора над счетчиками с:= с, формально меняет определение класса, но получающийся класс схем равномощен классу У (с), так как этот оператор мол«но заменить фрагментом, показанным на рис. 9.2. -д ! ! ! ! ! ! ! 3 а д а н и е 9.2. А. «РасшифруйтЬ» операторы! засылки произвольного чвгла я в счет:чик с:= я, умножения яа чвсло с »= с Х я и деления ва число с »= — «!я 'с помощью трех бааозых операторов. Используйте не более одного дополнительного счетчика.
Б. Покажите, что преднкат с шод! л = О, где п — некоторое число, з ,е шо!д л — остаток от деления счет«зла на я, можно представить через три 'базовых оператора и оден дополнительный счетчик. Т е о р е м а 9Л (Манна — Чандра). Класс счетчиковмх схем не транслируем в класс рекурсивных схем.
Д о к а з а т е л ь с т в о. Счетчиковая схема Юз» на рис. 9.3 'ие имеет эквивалентной рекурсивной схемы. Отметим характерные особенности атой схемы. При любой свободной интерпретации схемы Я з значении счетчика с, во время выполнения программы пробегают некоторый начальный отрезок последовательностн чисел О, д, 2, 3, ... (в зависимости от интерпретации преднкатного символа р). Счетчик с, принимаетпри этом аначения О, д, О, 2, д, О, 3, 2, $, О, ..., а переменная р в условном операторе р (у) пробегает последовательность аначеиий 'а', 'уа', '«а', 'фа', '1ба', 'Яа', ..., '1»'я "'а', где яд н я — текущие аначения счетчиков с и, соответственно, сз.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
