Р.У. Себеста - Основные копцепции языков программирования (2001) (1160794), страница 163
Текст из файла (страница 163)
Вызов и вход могут иметь непосредственное отношение к модели выполнения подпрограммы в импера- 15.6. Основные элементы языка Рго!ой 631 тивном языке, если процессы, подобные с)1ягапсе, рассматриваются как подпрограммы. Два других события свойственны только системам логического программирования. В следуюшем примере трассировки программы удовлетворение цели не приводит к появлению событий повтора или отказа.
Ниже приводится трассировка вычисления значения переменной С)течу Раягапсе: ггасе. 01ягапсе(с)зечу, С]зечу Раягапсе) с(1ягапсе(с)зечу, О)? яреес(с]зечу, 5)? яреес)(с)течу, 105) гаже(спечу, б) ? г1же(спечу, 21] 2205 1я 105*21 с)1ягапсе(с]течу, 2205) (1) 1 Са11: (2) 2 Са11: (2) 2 Ехуг: (3) 2 Са11: (3) 2 Ехаг: (4) 2 Ехуг: (1) 1 Ехаг: С]зечу Раягапсе = 2205 ггасе. 11хея (Захе, Х), 11]сея (с)агс1е, Х) 11хея 11йея 11йея 11)сея 11хея 11)гея 11йея 11хея (3а)се, О)? (3а)се, сйосо1аге) (с(агс1е, с)тосо1аге)? (с)агс1е, с]зосо1аге) (За)се, О)? (Захе, аргусогя) (с)агс1е, арг1согя)? (с)агс1е, арг1согя) (1) 1 Са11: (1] 1 ЕХ1г: (2) 1 Са11: (2) 1 Еа11: (1) 1 йес)о: (1) 1 Ехаг: (3) 1 Са11: (3) 1 Ехаг: Х = аргусогя Вычисления, выполняемые системой языка Рго)оа, можно представить в графическом виде. Рассмотрим каждую цель как яшик с четырьмя портами — вызов, отказ, выход и 632 Глава 15.
Языки логического программирования Символы в трассировке, начинающиеся символом подчеркивания ( ), являются внутренними переменными, используемыми лля хранения в памяти конкретизнруемых переменных. В первой колонке трассировки указывается подцель, подлежащая проверке на соответствие. Например.
в трассировке, приведенной выше, первая строка с обозначением (3) представляет собой попытку конкретизировать временную переменную б значением терма гаже для переменной спечу, где терм г1ве является вторым термам в правой части оператора, описывающего вычисление переменной с(1ягапсе. Во второй колонке указывается глубина вызова процесса сопоставления. В третьей колонке указывается текушее действие. Для иллюстрации бектрекинга рассмотрим следуюший пример, связанный с базой данных, и отслелим составную цель: 11)сея(?ахе, с]зосо1аге). 11хея(3аКе, аргасогя).
11)сея(с)агс1е, 11согасе). 11хея(цагсге, арг1согя). повтор. Управление входит в цель в прямом направлении через порт вызова. Управление также входит в цель в обратном направлении через порт повтора. Управление покилает цель в лвух направлениях: если цель достигнута, управление покидает ее через порт выхода; если цель не достигнута, управление покидает ее через порт отказа. Модель этого примера показана на рис.
15.1. В этом примере управление проходит через каждую подцель дважды. Вторая подцель оказывается недостижимой в первый раз, что приводит к возврату через порт повтора к первой подцепи. Вызов Отказ к ~ваке, х~ Эыхоа ..автор Зивов Отказ ЗзКев Шато е, х) Повтор Пахов Рис.
15.1. Мадевь поязокаулравления для цели 11]геа (1а]те,Х), 11]геа Гс]азс1е, Х) 15.6.У. Списковые структуры До сих пор елинственными структурами данных в языке Рго!Ок, которые мы обсуждали, были атомарные высказывания, более похожие на вызов функции, а не на структуру данных. Атомарные высказывания, которые также называются структурами, в действительности представляют собой вид записей. Другой основной структурой, поллерживаемой языком Рго]оя, является список, подобный списковой структуре, использованной в языке [.]БР. Списки представляют собой последовательность.
состоящую из любого количества элементов, где элементами могут быть атомы. атомарные высказывания или любые другие термы, включая другие списки. Язык Рго!ок для указания списков использует обшепринятый синтаксис. Элементы списка разлеляются запятыми, а список в целом заключается в квадратные скобки. как показано ниже: [арр1е, ргцпе, ахаре, Китяиас] Для обозначения пустого списка используются символы []. Вместо явных функций для построения и разрушения списков язык Рго1оя просто использует специальное обозначение. Символы [Х 1 'т'] обозначают список с головой Х и хвостом у, где голова и хвост соответствуют первому и последнему элементам списка (САй и С[зй в языке [.1БР).
Это похоже на обозначения, используемые в языке НазкеП. 15.6. Основные элементы языка Рго[од Список можно создать с помощью простой структуры, как показано ниже: пеи 11вГ([арр1е, ргцпе, ахаре, Ьлпццаг)). В этой структуре утверждается, что список констант [арр1е, ргипе, огаре, )сшпс)цаг] является новым элементом отношения с именем пеи 11вг (имя, которое мы только что создали).
Этот оператор не связывает список с переменной, имеющей имя пеи 11вг; вместо этого он выполняет тот же вид действий, что и высказывание гва1е (1а)се) Этот оператор утверждает, что список констант [арр1е, ргипе, огаре, )сипк[цаг) является новым элементом списка пеи 11аг. Следовательно, мы могли бы иметь второе высказывание со списком аргументов, например: пеи 11вс ( [аргдсос, ревой, реаг) ) В виде запроса один из элементов списка пеи 11вг можно разбить на две части: голову и хвост с помощью оператора пеи 11вс([иеи Ьдвс Неаг) ) Неи [.Евс Та(1) ) .
Если было указано, что список пеи 11вг состоит из двух частей, как в вышеприведенном примере, то этот оператор конкретизирует переменную неи Ь1вг неас) первым элементом списка (в данном случае арр1е), а переменную Неи Ьзгвг Та11 — хвостом списка (или [ргипе, йгаре, кили)цаг] ). Если этот запрос является частью составной цели, и бектрекинг приводит к новому его вычислению, переменные Иеи Ь1вг Неас) и Уеи (.1вг Та11 могут быть снова конкретизированы значениями аргдсоС и [реас)т, реаг), соответственно, поскольку список [арггсоС, реас)т, реаг] является следующим элементом списка пеи 11вг.
Обозначение, использованное лля разбиения списка на части, можно также использовать и для создания списков из заданных конкретизированных компонентов головы и хвоста, как в следующем примере: [Е1етепс 1 ) )Евс 2) Если переменная Е1ежепг 1 была конкретнзирована значением р1с)с1е, а список ).1вг 2 был конкретизирован значением [реапиг, ргипе, рорсогп], обозначение, приведенное выше, приведет к созданию в данном случае списка [р1с)с1е, реапис, ргцпе, рорсогп]. Как указывалось ранее, обозначение списка, содержащее символ (, является универсальным: оно может обозначать как создание списка, так и его разбиение на части. Кроме того, заметим, что следующие выражения являются эквивалентными. [аргдсог, реасп, реаг ) []] [арг1сос, реас)т ) [реаг]] [аргйсог ) [реасп, реаг]) При работе со списками необходимы такие определенные основные операции, как в языке ЫБР.
В качестве примера этих операций в языке Рго)од рассмотрим определение операции аррепс(, аналогичное такой же функции в языке [.!БР. В данном примере можно увидеть как различия, так и сходство функциональных и декларативных языков программирования. Нам не нужно указывать, как именно система языка Рго!ок должна Глава ] 5.
Языки логического программирования создать новый список из заданных списков; достаточно уточнить характеристики нового списка в терминах заданных списков. Внешне определение операции аррепб в языке Рго)оя очень похоже на версию языка [.]ЯР, и для получения нового списка в процессе резолюции точно так же использ>ется некоторый вид рекурсии. В языке Рго)оя рекурсия вызывается и контролируезся процессом резолюции. Первые два параметра операции аррепб во фрагменте программы, приведенном ниже, представляют собой два списка, подлежащие обьединению, а третий параметр— список, получающийся в результате этого объединения: аррепс)([], Е1яс, Ь1яс).
аррепб([Неаб ! Ьдяс 1], Ейяс 2, [Неаб ! Ейвс 3]) аррепб(Е1яг 1, Ьфяс 2, Ьйвс 3) . Первое высказывание утверждает, что при добавлении пустого списка к любому другому списку результатом является этот другой список. Этот оператор соответствует рекурсивно завершающемуся шагу в функции аррепб языка [.]ЯР. Заметим, что завершающее высказывание помещено до рекурсивного высказывания, поскольку система языка Рго)ой будет сопоставлять два высказывания по порядку, начиная с первого (потому что он использует порядок сначала-вглубь).
Второе высказывание уточняет несколько характеристик нового списка. Оно соответствует рекурсивному шагу в функции языка [.(ЯР. Левая часть предиката утверждает. что первый элемент нового списка совпадает с первым элементом первого из заданных списков, поскольку оба эти элемента имеют имя Неаб. Как только переменная Неаб будет конкретизирована некоторым значением, все вхождения переменной Неаб в цель олновременно будут конкретизированы этим же значением.
Правая часть второго оператора определяет, что хвост результирующего списка (!.1яг 3) образуется путем добавления второго заданного списка [11яг 2) к хвосту первого из заданных списков (11я" 1). Второй оператор в определении операции аррепб можно прочитать след>югцим образом: добавление списка [неаб ! Е1яг 1] к любому списку ' яг 2 образ>ет список [неаб ) е1яг 3],нотолькоеслисписоке1яг 3 создается путемлобавления списка 11яс 1 к списку Ь1яс 2. В языке [.]ЯР это можно было бы записать так: (СОНЯ (САН Г1НЯТ) (АРРЕНО (СОН Г1НЯТ) ЯЕСОНО) ) И в языке Рго)оя, и в языке [.!ЯР результирующий список строится с помощью самой функции аррепб; элементы, взятые из первого списка, добавляются в обратном порядке ко второму списку. Обратная перестановка элементов выполняется путем развертывания рекурсии. Для иллюстрации того, как именно протекает процесс выполнения операции:г:с: ",, рассмотрим следующий оттрассированный пример: сгасе.
аррепб([ЬоЬ, Зо), [1аКе, багсде], Гаж11у]. (1) 1 Са11: аррепб([ЬоЬ, >о], [ЗаКе, багс1е), 10)? (2) 2 Са11: аррепб([>о], (>аКе, багсде], 18)? (3) 2 Са11: аррепб((], [3аКе, багс1е], 25) ? (3) 3 Ех1Г: аррепб([], [ЗаКе, багс1е], [>аКе, багсде]) (2) 2 Ех1г: аррепб([>о), [ЗаКе, багс1е], [>о, ЗаКе, багс[е]) ] 5.6. Основные элементы языка Рга[оа (1) 1 Ехйг: аррепс(( (ЬоЬ, 3о], [За)се, с(агс1е], ЬоЬ, 3о, ?ахе, с(агс1е) ) Гаж11у = (ЬоЬ, 3о, Захе, багс1е] уев В первых двух вызовах, представляюших собой подцепи, список Ыз( ! не пуст.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
