Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 164
Текст из файла (страница 164)
Поэтому эти вызовы создают рекурсивные выювы из правой части второго оператора. Левая часть второго оператора лействительно указывает аргументы для рекурсивных вызовов, или целей, удаляя, таким образом, по одному элементу из первого списка на каждом шаге. Когда первый список станет пустым при вызове, или в подцепи, текушая конкретизация правой части второго оператора совпадет с первым оператором. В результате значение пустого списка, добавленного ко второму исходному списку-параметру, будет возврашено в качестве третьего параметра.
При успешных выходах, соотвествуюших успешным сопоставлениям, элементы, которые были удалены из первого списка, добавляются к результирующему списку Гап11у. Когда происходит выход из первой цели, процесс завершается, и выводится результирующий список. Высказывания аррепс( можно также использовать лля операций работы со списками, подобных приведенной ниже.
Результат этой операции мы предлагаем читателю определить самостоятельно. Заметим, что операция 11яг ор 2 должна иметь в качестве первого параметра список, в качестве второго параметра — значение, а результатом этой операции является значение, которым конкретизируется второй параметр. 11яс оо 2([], [)) ° 11яг ор2 ( [неас( ) та11), Ыяг): — 11яг ор 2 (та11, неяи1с), аррепс((Неяп1Г, (Неас(], Е1ят).
стасе. гечетяе([а, Ь, с], ()] Ь, с„', 6]? с], 65636)? 65646)? 65656)? []) [с], 65646) '? [с], [с]) (с]) [Ь], 65636) ? ) Са11 2 Сз11 3 Са1' 4 Са11 4 Ех1г 4 Са11 4 Ехдг 3 Ехдг 3 Са11 течегяе([а, гечетяе([Ь, гечегяе([с] гечегяе([), течегяе([], аррепс(([], аррепс(([], течегяе((с] аррепс(([с], (1) (2) (3) (41 (4) (5) (5) (3) (6) 636 Глава ! 5. Языки логического программирования Как может определить читатель. операция 11яг ор 2 заставляет систему языка Рго(оя конкретизировать свой второй параметр списком.
состоящим из элементов списка, являющегося ее первым параметром. но взятых в обратном порялке. Например, (11яг ор 2 [арр1е, стапеле, дгаре), 0) конкретизирует переменную О списком (цгаре, огапое, арр1е!. Еше раз отметим, что. хотя языки Е)БР и Рго)оя коренным образом отличаются друг от друга, схожие операции могут использовать схожие подходы. При операции обратной перестановки элементов списка и операция 11яс ор 2 в языке Рго)ой, и функция гечегяе в языке Е)5Р включают в себя условие завершения рекурсии вместе с основным процессом добавления обратной перестановки хвоста списка (с(эн) к голове списка [САН) для образования результируюшего списка.
Ниже приводится трассировка этого процесса, который теперь называется тече г яе: (1 = [с, Ь, а) Предположим, что нам нужно определить, принадлежит ли заданный элемент заданному списку. Прямое определение этой операции в языке Рго!од имеет вил: вевЬег(Е1евепг, [Е1евепг ( ) ) . вевЬег(Е1евепс, [ ( Едят)) : — вевЬег(Е1евепс, Ыяс). Символ подчеркивания обозначает "безымянную" переменную: она используется тогда, когда нам безразлично, что ее конкретизация может быть получена путем унификации. Первый оператор из приведенных выше достигается, если переменная Е1евепг является головой списка либо изначально, либо после нескольких рекурсий.
выполненных с помощью второго оператора. Второй оператор достигается, если переменная Е1евепс принвллежит хвосту списка. Рассмотрим следующие оттрассированные примеры: Стасе. вевЬег(а, [ (1] 1 Са11: (2) 2 Са11: (3] 3 Са11: (4) 4 Са11: (4) 4 Га11: (3) 3 Га11: (2) 2 Га11: (1) 1 Га11: )(с Ь, с, с(]). вевЬег (а, вевЬег (а, вевЬег(а, вевЬег(а, вевЬег(а, веп1Ьег(а, вевЬег(а, вевЬег(а, с, сП)? [с, с(] )? (с)) )? (1)? [)) [с(] ) [с, с(] ) [Ь, с, с))) вевЬег(а, [Ь, с, В)). (1] 1 Са11: вевЬег (а, (2) 2 Са11: вевЬег(а, (2) 2 Ехдс: вевЬег(а, (1) 1 Ехдг: вевЬег(а, уея [Ь, а, сП)? [а, с]) ? [а, с]) [Ь, а, с)) ] 5.6.
Основные элементы языка Рго]оя 637 (7) 4 Са11: (7) 4 Ех1С: (б) 3 Ехуг: (2) 2 ЕхЕС: (8) 2 са11: (9] 3 Са11: (10) 4 Са11 (10) 4 Ехуг (9) 3 Ех1С: (8) 2 Ех1С: (1) 1 Ехдс: аррепс(([], аррепс)([], аррепс(([с) гечегяе([Ь аррепс(([с, аррепс(([Ь] аррепс([) аррепс(([] аррепс(([Ь] аррепс(([с, геЬтегяе([ [Ь], (Ь), [Ь) с], Ь], [а] [а] [а] [а] с(), а, Ь, 25)? [Ь) ) [с,Ь]) [Ь, с]) [а], б)? 32)? 39)? [а)) [Ь, а]) [а), [с, Ь, а]) с), [с, Ь, а]) 15.7. Недостатки языка Рго!о9 При использовании языка Рго!ой в качестве языка логического программирования возникает несколько проблем.
Несмотря на то что этот язык является полезным инструментом, его нельзя назвать ни чистым, ни совершенным языком логического программирования. 1$.7.1. Управление порядком выполнения резолюции Язык Рго1оя в целях эффективности позволяет пользователю управлять порядком сопоставления образцов во время резолюции. В чистой среде логического программирования порядок сопоставлений, осуществляемых во время процесса резолюции, является недетерминированным, и все сопоставления могут происходить параллельно. Однако, поскольку система языка Рго1ок выполняет сопоставления в одном и том же порядке— начиная с начала базы данных и с левой части цели заданной цели, — пользователь может существенно увеличить эффективность, упорядочив базу данных для оптимизации конкретного приложения.
Например, если пользователь знает, что определенные правила достигаются чаще других, во время конкретного "выполнения" программы, то программу можно сделать более эффективной, поместив эти правила в начало базы данных. Медленное выполнение программ — не единственный негативный результат определенного пользователем порядка выполнения программы, написанной на языке Рго!оа.
Очень легко написать операторы в форме, приводящей к бесконечным циклам и тотальному отказу программы. Рассмотрим следующую форму рекурсивного оператора: б1Х, У): — ~!г, У), о!Х, г). Поскольку в языке Рго!ой принят порядок выполнения операций слева-направо сначала- вглубь. независимо от предназначения оператора, это может привести к бесконечному циклу. В качестве примера такого рода операторов рассмотрим следующий: апсеясог(Х,Х). апсеягог !Х, У) : - апсеясог !Е, У), рагепг(Х, Е) . При попытке удовлетворить первую подцель правой части второго высказывания система языка Рго1ок конкретизирует переменную 2, чтобы сделать отношение апсеяСог истинным.
Затем она пытается удовлетворить зту новую подцель, переходя к правой части определения отношения апсеягог и повторяя тот же самый процесс, что приводит к бесконечной рекурсии. Эта частная проблема идентична проблеме рекурсивного синтаксического анализа от частного к общему с левой рекурсией в грамматическом правиле, обсужденной в главе 3. Как это было в случае с грамматическими правилами синтаксического анализа, простое изменение порядка следования термов в правой части приведенного выше высказывания на противоположный исключает эту проблему. Однако простое изменение порядка следования термов не должно быть критически важным для правильности работы программы. Кроме всего прочего, возможность программиста не заботиться о порядке выполнения операторов предположительно является одним из преимуществ логического программирования.
В дополнение к тому, что пользователь может управлять базой данных и порядком удовлетворения подцелей, язык Рго1оа позволяет использовать некоторые явные средства управления бектрекингом. Это осуществляется с помощью оператора отсечения, ко- 63з Гдово 15. Языки логического программирования торый обозначается знаком восклицания (! ). Оператор отсечения в действительности является целью, а не оператором.
В качестве цели он всегда достигается немедленно. но он не может быть удовлетворен снова с помощью бектрекинга. Таким образом, побочный эффект оператора отсечения состоит в том, что подпели его левой части в составной цели не могут быть удовлетворены снова с помощью бектрекинга. Рассмотрим цель а, Ь, !, с, с). Если и цель а, н цель Ь достигаются, а цель с — нет, то вся цель не лостигается. Эту цель можно было бы использовать, если бы было известно, что цель с никогда не достигается, поскольку в этом случае пытаться вновь удовлетворить цели а или Ь вЂ” пусзая трата времени.
Цель оператора отсечения, таким образом, заключается в том. чтобы позволить пользователю сделать программу более эффективной, сообщив системе, когда не следует пытаться повторно удовлетворить цели, которые предположительно не могут дать результата в завершенном доказательстве. В качестве примера использования оператора отсечения рассмотрим правила вевЬег из раздела 15.6.7, которые повторяются ниже. вевЬег(Е1евепг, (Е1евепс ! ]). вевЬег(Е1евепг, [ ) 11вг] ): — вевЬег(Е1евепг, Ейвг) Если аргумент правила вевЬег, являющийся списком, представляет собой множество, то он может удовлетворяться только однажды (множество не содержит повторяющихся элементов).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
