Т. Пратт, М. Зелковиц - Языки программирования - разработка и реализация (4-е издание_ 2002) (1160801), страница 105
Текст из файла (страница 105)
Например, правило А .-В,!,С,! 0 выполнится только в случае, если будут найдены соответствия г первыми пелями для В, С и О. Любая попытка найти соответствие с подцелью 5цЬсса1, „; по предыдущему алгоритму, где 5цЬооз1,, ~ =!, не увенчается успехом. Таким образом, если для 0 не будет найдено соответствия с первой целью, А также будет ложно, поскольку для С в качестве альтернативы не будет проверяться никакая новая цель. Использование функции! в подходящих местах предупреждает ненужный во многих алгоритмах откат. Откат — зто общая методика программирования, доступная в любом языке, создающем древовидные структуры. Мы можем построить алгоритмы отката во всех языках, описанных в данной книге. Однако в таких языках, как ЫВР, где деревья являкгтся естественным построением встроенного типа данных список, откат реализуется относительно легко. Как мы наблюдали ранее, в языке Рго!оя алгоритм отката является встроенным в сам язык, 8.4.5.
Принцип резолюции Исчисление предикатов сыграло важную роль в развитии языков, особенно языка Рго!ой. В 60-е гг. основным языком научных вычислений был ГОКТКАЬ), а для программ, основанных на логических выводах, преимущественно использовался 1ЛБР. Поскольку в языке с!БР в качестве основ ного типа данных использовалась структура списков, деревья были естественным составным типом данных, которыми оперировали программы 1.!8Р. Если мы представляем правило А В С ~ 0 в языке 1 18Р, то естественной структурой данных будет дерево с корнем 0 и листьями А, В и С. 380 Глава 8. Управление последовательностью действий Предикат Предложение Я=гв В Я=гВ А т В =г Ьгие Ггае=гА т В Я га!ае Я - В о С Агв — Я Ат В~С Это яггпкгго показать путем приведения каждого преднката к дизьюиктивггой нормалыгой форлге (то есть последовательности термов о).
Все термы с отрицанием становятся предпосылками, а термы без отрицания становятся следствиями предложений. Пнже приведена таблица с поясняюгцими примерами. Диаьюиктияиая нормальная форма Предложение С .-.~ Я о В г 0 Я ь В ь С =г 0 Ятзт Сьв Ао Вт Ств Все ато является прямым следствием следующих преобразований: 1. Р =г Оэквивалентно-,Р о О; 2. Р о -Оэквивалептно (Р о О! (закоггДеМоргана). Огруппнроваа ггыесте все термы с отрицанием в дизъюнктнвной нормальной форме для предиката, в соответствии с заковом Де Моргана люжно утверждать, что они эквивалентны отрицанию всех предикатов, объединенных операцией И.
В соответствии с преобразованнслг 1 они становятся предпосылкой в предложении. Рассмотрим любое предложение: Рг г Рг т .. Р. =г Ог г Ог ., О. Применение принципа резолюции для атого общего предиката становится слиш- ком сложным. Но можно рассмотреть случаи, когда и = 1 или п = О. Такие предика- ты носят название хорновых дизыонктов. Они имеют вид Р лР л,.Р„=гОа РглРгл,.Р,, Для доказательства истинности 0 сначала требуется доказать истинность поддеревьев Я, В и С Как говорилось в разделе 84 А при обсуждении алгоритма отката, 115Р является естественным языком для построения таких алгоритмов.
В 1965 г. Робинсон (гтоЬ!пзоп) разработал принцип резолюции, реализация которого в 1972 г. и стала языком Рго!08. Хотя для программирования на языке Рго!08 нет необходимости полностью понимать принцип резолюции, тем не менее его знание помогает понять теорию, лежащую в основе выполнения программ на этом языке. Пусть имеется множество предикатов !Р,, Рг,...). Основной задачей является определить, какую теорему можно генерировать из этих преднкатов. Вообще, если Р и О преднкаты, то является ли теоремой Р ~ О(если Р, то О)? Начнем с замечания, что любой предикат можно записать в форме предложений: Р,лРгл..
Р.=гОгь,.0„ где Р, и О, — термы. Приведем примеры предложений. 8.8. Задачи и упражнения 381 Если поменять местами предпосылки и следствия и заменить =г на; —, получим эквивалентные утверждения; 1) Огг '— Рг л Рг л ... Рг,' 2): — Рг л Рг л .. Р„ а это и есть известные нам предложения языка Рго!ойг. Первое представляет пра- вило, а второе — запрос.
Если рассмотреть случай, когда б) = О, то получим факт языка 1гго!ой Ог: — ггбе или просто 3) Ог Тогда принцип резолюции для хорновых дизъюнктов теперь утверждает: Пусть даи запрос )4г ... Я, и праеизго Ры-Рг ... Р, тогда, селимы уггиг]гицируем С4г и Р„ или, как записьсеалось е разделе 8,43, фо - Рьо, мы получим экеиаалеитные запросы. Если мы унифицируем О, с помощью Рг, то наш исходный запрос эквивалентен одному из следующих: 1) (Рг Р.О, .
0.)о = Р, Р.„,„если Р,было правилом, 2) (Ог .. 0,)а = Рг ... Р..г, если Рг было фактом (ы=О), где Р, = Р„а или Р, = О,а. В конечном счете мы налеемся, что все Р, будут унифициро- ваны фактами из базы данных и приведут к истиие в процессе преобразований, даюгцих результаты по нашему запросу. В этом и заключается суть выполнения программы на языке Рго!ой. Целью про- странства поиска языка Рго!ой является унифипирование Ог ... О., и Рго!ой свобо- ден в выборе любого правила Р из базы данных в качестве гипотезы, с помощью которой он постарается реализовать принцип резолюции. Если это приводит к успе- ху, то а описывает ответы на наш запрос; в противном случае следует постараться использовать альтернативные правила Р' для поиска правильной подстановки.
8.5. Рекомендуемая литература Во многих книгах, упомянутых в главе 1, освещается вопрос управления последовательностьюдействий. В сентябрьском выпуске журналаАСМ Сотриггп)г3игсеуз [3] за 1989 г. напечатано несколько статей, посвященных парадигмам языков программирования, в которых рассмотрены необходимые структуры управления. Формальная связь между структурами управления и формальным доказательством корректности обсуждается в книге Ганнона [43]. Еще одна форма структур управления — таблица решений — описана у Мецнера и Бариеса [81], а в работе Преннера [89] представлена дополнительная информация по алгоритму отката.
8.6. Задачи и упражнения 1. Поясните, что будет происходить при выполнении фрагмента программы, написанной на языке Сл ]гп! 7=1 )иг; гг!г - 0) [рггпггр"сгее: гб 'гб!и".г,)):) е!зе Рг)птй "Та)зе 1б гбгя".!.)):) 382 Глава 8. Управление последовательностью действий 2. 5. 6. 7. 8. 9. Четвертая форма синтаксиса выражений называется обратной польской лрефиксяой записью, которая является обычной польской записью, записанной наоборот. Например, выражение а + 1Ь х с) в префиксной записи будет выглядеть как+ а х Ьс,в постфиксной — какаЬс х +,авобратнойпостфиксной польской записи — как сЬ х а +, Свойства обратной польской префиксной записи аналогичны свойствам обычной постфиксной записи, но иногда она имеет некоторые преимутцества перед обычной постфиксной записью при генерации аффективного машинного кода.
Объясните почему. Принимая во внимание порядок старшинства операций, принятый в языке С, предложите представления в виде дерева для следующих выражений; а) -А-В/С*0/Е! Е+0; б) А*В>С+О! Š— Е; в).АВВ>Сто. Такое же задание выполните, принимая во внимание порядок старшинства операций в языке Рааса!, а затем в 5ша11га1 . Приведите блок-схемы всех первичных программ, состоящих из пяти узлов. Покажите, что для любого п > 1 существует первичная программа, состоящая из л узлов. Одной из основных теоретических предпосылок для замены операторов Во1о на структурные операторы является результат Бема (Во1тш) и Якобини (З асоЬ1п1) [19!. Они доказали, что любая правильная программа может быть написана с помощью последовательностей одних только операторов тт и иЬт1е.
Начертите схему правильной программы с несколькими циклами и ветвями. Запрограммируйте ее, используя операторы до1о, а затем только конструкции т Е и ылт1е. Оцените оба зги варианта с точки зрения простоты их прочтения, понимания и записи. Теорема Бема-Якобини утверждает, что любую блок-схему можно заменить на блок-схему, выполняющую те же функции, но в которой используются только операторы последовательного выполнения, а также тЕ и илт1е. Покажите, что оператор т Е не обязателен, то есть достаточно только оператора иЬ11е.
Синтаксис оператора т Е языка Рааса! следующий; ттт бупево выражение Вьеп оператор етве оператор а на языке Ат!а оператор т Е выглядит следукяцим образом: тт бупево выражение Внеп оператор езве оператор епб тт Поясните относительные достоинства наличия явного указателя на конец оператора, такого как епб т Е в языке Ат)а. Один из операторов цикла на языке Рааса! имеет вид: тог простая переиенная:= начальное зна~ение то конечное значение бо оператор Обсудите достоинства и детали реализации, если: а) начальное значение и конечное значение вычисляются одни раз, когда оператор Хог выполняется первый раз; б) начальное значение и конечное значение вычисляются каждый раз, когда программа начинает очередную итерацию цикла.
8.6. Задачи и упражнения 383 10. Правила языка Рго!оя можно рассматривать как логические предикаты. Правило а: - Ь, с приведет к тому, что а выполнится, если выполнятся и Ь, и с. Таким образом, можно сказать, что а истинно, если истинно условие Ь л с, а) При каких условиях для р, р, г и 5 выполняются следующие правила Рго!оя? х — р..'.а. Х '- Г.5. х :- р,р Х вЂ” Г.5. х: — рлр х - г.!.5.
б) Выполнитезадание(а) сдобавлением правилах:- Уа)) после приведенных двух правил. Что будет, если ато правило поместить первым в базе данных? 11. Правило аррепу) можно определить следующим образом: ! аррепЩХ, У 7):-Х = [). У = Е. аррепщХ У. Х):-Х = [П ) Н). 2 = [П ) и). аррепща.
У, Н). а) покажите, что зто определение равносильно следующему: аррепе[[). Х, Х). аррепЩ [Н)Х). У, [Н)Е)): — аррепГНХ, У, 7). б) сделайте трассировку выполнения запроса аррепй[1, 2 3) [4, 5). Е), чтобы показать, что 2=[1, 2, 0,4, 5) унифицирует запрос аррепе, Глава 9. Управление подпрограммами В нескольких предыдущих главах мы описывали процесс, с помощью которого в языках программирования создаются типы данных и объекты данных этих типов.
Мы рассмотрели, каким образом в программе выполняются последовательности операторов, позволяющие манипулировать такими данными, а также обсудили простые механизмы записей активаций, с помощью которых в языках осуществляется управление ресурсами памяти для различных объявляемых объектов данных. В этой главе мы более подробно рассмотрим взаимодействие подпрограмм и, что важнее, структурированные и эффективные способы обмена данными между подпрограммами. Для большинства программ обычно достаточно простой стековой структуры для управления памятью нри выполнении программы.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
