Пример 4.5

Рассмотрим следующую программу на Прологе:

отец(а,b).

отец(b,c).

отец(c,d).

предок(Х,Y) :- отец(Х,Y). /* 1-е правило X,Y */

предок(Х,Y) :-

отец(X,Z), /* 2-е правило, 1-я цель: Х,Z,*/

предок(Z,Y). /* 2-е правило, 2-я цель:",Z,Y.*/

Последовательность выполнения операций следующая:

1-е правило: a,b

X=a,Y=b

1-е правило: b,c

X=b,Y=c

1-е правило: c,d

X=c,Y=d

2-е правило 1-я цель: а,b

1-е правило: b,c

2-е правило 2-я цель: b,c

X=a,Y=c

2-е правило 1-цель: b,c

1-е правило: c,d

2-е правило 2-я цель: c,d

2-е правило 2-я цель: b,d

X=a,Y=d

На запрос

!, отец(X,Y), отец(Y,Z) получим

X=a, Y=b, Z=c

X=b, Y=c, Z=d

На запрос

отец(Х,Y),!,отец(Y,Z)

получим

X=a, Y=b, Z=c

Предикат "ложь". В Прологе имеется встроенный пре­дикат "fail", который всегда указывает на ложь, т.е. на тупик в процессе анализа целей. Этот предикат полезен в том случае, когда необходимо получить все решения некоторой более ран­ней цели, прежде чем переходить к анализу последующих це­лей (обычно Пролог находит первое решение первой цели, а затем последующих целей). Вопрос заключается в том, как пройти к последующим целям, если предикат "fail" системати­чески осуществляет возврат. Например, на запрос отец(Х,Y), write(X,Y), nl, fail, мать(Z,Y). высвечиваются имена всех отцов и нет возможности достичь предиката "мать". Это можно сде­лать с помощью логической операции ИЛИ, используя кото­рую можно сказать: ИЛИ имеется следующий факт "отец" ИЛИ осуществляется переход к следующей цели".

Обработка списков и строк символов

Список в Прологе представляется множеством элемен­тов, разделенных запятой и ограниченных квадратными скоб­ками.

Так, X = [a,b,c,d] является списком из четырех элементов.

Для разделения списка на части используется предикат "|" (вертикальная черта). Этот предикат разделяет список на голову и хвост. Головой списка может быть его первый эле­мент, тогда хвост списка есть подсписок, состоящий из всего списка за исключением его первого элемента. Так, если X=[a,b,c,d] и X=[Y|Z], то Y=a и Z=[b,c,d]. Заметим, что в слу­чае списка, состоящего из одного элемента, Х=[а] и X=[Y|Z], тогда Y=a и Z=[]-пустой список, который обозначают откры­вающей и закрывающей квадратными скобками. Поскольку список делится на части, то его можно составлять из отдель­ных частей. Так, например, из одного элемента и списка мож­но получить новый список.

Пусть: 1) Х=а, Y=[b,c,d] и Z=[X|Y], тогда Z=[a,b,c,d] и 2) Х=а, Y=b, тогда Z=[a|b], а не Z=[a,b]. В первом случае Y - спи­сок, а во втором Y - элемент. Таким образом, соединение двух элементов дает список, состоящий из элемента и подсписка, а не из двух элементов.

Далее в этом параграфе рассмотрим процедуры работы со списками. Во многих случаях, чтобы упростить изложение, будем приводить только часть clauses Пролог-программ.

Принадлежность элемента списку. Предположим, что имеется список наименований деталей велосипеда: руль, рама, колесо, седло, и нужно определить, содержится ли некоторая деталь, например "седло", в данном списке.

Очевидно, что если элемент принадлежит списку, то он либо совпадает с головой списка, либо находится в его хвосте. Следовательно, прежде всего необходимо сравнить искомый элемент с головой заданного списка. В случае несовпадения аналогичные действия рекурсивно повторяются для списка-хвоста. Поиск завершается неудачей, если достигнут конец исходного списка.

Принадлежность элемента Х списку Y можно записать в виде предиката "принадлежит(Х,Y)". Для определения истин­ности этого предиката требуется проверить два условия. Пер­вое состоит в проверке совпадения Х с головой списка X, что записывается на языке Пролог следующим образом:

принадлежит(Х,[Х|_]).

Для обозначения хвоста списка здесь используется ано­нимная переменная "_". Данный факт можно записать в виде правила:

принадлежит(Х,[Y|_]) :- X = Y.

Для определения принадлежности элемента Х хвосту списка будем использовать тот же предикат "принадлежит", в чем и заключается суть рекурсии. На Прологе это записывает­ся правилом

принадлежит(Х,[_|Y]) :- принадлежит(Х,Y).

что означает: "X является элементом списка, если Х является элементом хвоста списка". В качестве головы списка применя­лась анонимная переменная, так как ее имя значения не имеет.

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

Теперь можно написать программу:

принадлежит(Х,[Х|_]). принадпежит(Х,[_|Z) :- принадлежит(Х,Z).

На запрос

принадлежит(седло,[руль,рама,колесо,седло])

следует утвердительный ответ

Выбор n-го элемента списка. Для выбора n-го элемен­та списка достаточно указать, что первый элемент списка име­ет номер 1, т.е. на языке Пролог это выглядит следующим об­разом:

n(1 ,Элемент,[Элемент|_]).

Затем нужно определить рекурсивное правило, которое расчленяет список на элементы,. параллельно вычитая из за­данного номера единицу до тех пор, пока не выполнится гра­ничное условие, т.е. счетчик станет равным единице (первое правило). Сказанное описывается следующим правилом:

n(М, Элемент, [_|Список]) :- Счетчик = N - 1, n(Счетчик, Элемент, Список).

На запрос

n(3,X,[a,b,c,d,e])

получаем

Х=с

Приведем полную программу:

n(l, E, [E|_]).

n(N,E,[_|L]) :- C = N – 1, n(C, E, L).

Рассмотрим последовательность действий, выполняе­мых интерпретатором с целью получения решения. Здесь 3 - запрос, Н - найдено правило, У - унификация.

З n(З,E,[a,b,c,d]).

Н n(l,E,[E|_]). ошибка унификации

З n(З,E,[a,b.c,d]).

Н n(N,E,[_|L]) :- C = N - l, n(C,E,L).

У n(З,E,[a|b,c,d] :- 2 = З - l, n(2,E,[b,c,d])).

З n(2,E,[b,c,d]).

H n(l ,E,[E|_]). ошибка унификации: 2 !

З n(2,E,[b,c,d]).

H n(N,E,[_|L]) :- С = N - 1, n(С,Е, L).

У n(2,E,[b,c,d]) :- 1 = 2 - 1 ,n(1 ,E,[c,d]).

З n(l,E,[c,d]).

H n(l,E,[E|_]). успех: 1=1

У n(l,c,[c|d]).

следовательно, n(l, c,[c,d])

следовательно, n(2,c,[b,c,d])

следовательно, n(3,c,[a,b,c,d])

solution: E = c

Соединение двух списков. Как отмечалось выше, соедине­ние двух списков с целью получения третьего осуществляется с помощью предиката " | ". Так, если

Х = [а,b,с], Y = [d,e,f] и Z = [X]Y], то Z=[a,b,c,d,e,f].

Процедуру присоединения списка Х к списку Y для по­лучения списка Z интерпретатор рассматривает следующим образом:

присоединить [а, b, с] к [d, e, f], чтобы иметь [a,b,c,d,e,f]

это значит

присоединить [b,с] к [d,e,f], чтобы иметь [b,c,d,e,f]

это значит

присоединить [с] к [d,e,f], чтобы иметь [c,d,e,f]

это значит

присоединить [] к [d,e,f], чтобы иметь [d,e,f] (A)

значит присоединить [ ] к [d,e,f], получая [d,e,f|

значит присоединить [с] к [d,e,f|, получая [c,d,e,f]

значит присоединить [b,с] к [d,e,f], получая [b,c,d,e,f]

значит присоединить [а,b,с] к [d,e,f], получая [a,b,c,d,e,f]

Строка (А) выражает факт соединения пустого списка с некоторым списком L, в результате чего получается список L. Это записывается так:

присоединить ([ ],L,L).

В строках, предшествующих строке А, удаляют голову первого списка и присоединяют ко второму, чтобы получить третий список:

присоединить ([X|L1],L2, [X|L3]) :- присоединить(L1,L2,L3).

Функция присоединения является важной и в Прологе называется append. Напишем программу:

append([ ], L, L).

append([X|Ll], L2, [X|L3]) :- append(Ll,L2,L3).

На запрос append([a,b,c], [d,e,f], L) получим L = [a,b,c,d,e,f].

На запрос append(L, [d,e,f|, [a,b,c,d,e,f]) получим L = [a,b,c].

На запрос append([a,b,c], L, [a,b,c,d,e,f]) получим L = [d,e,f].

Другими словами, функция append позволяет составлять и расчленять список. Так, на запрос append(Ll, L2, [a,b,c,d])

получим

L1	L2
[ ]	[a,b,c,d]
[a]	[b,c,d]
[a,b]	[c,d]
[a,b,c]	[d]
[a,b,c,d]	[ ]

Здесь находятся все возможные списки, с помощью ко­торых можно сформировать третий список.

Выбор наименьшего и наибольшего элементов спи­ска. Можно сказать, что наименьший элемент списка, состоя­щего из одного элемента, является этим элементом, т.е.

меньший([Х], X).

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

меньший([Х], X).

меньший([Х, Y|Z], R) :- X <= Y, меньший([Х|Z], R); X > Y, меньший([Y|Z], R).

Здесь сравниваются два первых элемента списка и меньший из элементов добавляется к оставшемуся подсписку.

На запрос меньший([b,c,a,e], X) получим Х=[а].

Выбор наибольшего элемента списка производится ана­логично, только нужно заменить знак ">" знаком "<" и наобо­рот.

Удаление элемента

Удаление элемента Х из списка L можно запрограммировать в виде отношения

удалить( X, L, L1)

где L1 совпадает со списком L, у которого удален элемент X. Отношение удалить можно определить аналогично отношению принадлежности. Имеем снова два случая:

(1) Если Х является головой списка, тогда результатом удаления будет хвост этого списка.

(2) Если Х находится в хвосте списка, тогда его нужно удалить оттуда.

удалить( X, [X | Хвост], Хвост).

удалить( X, [Y | Хвост], [ Y | Хвост1] ) :-

удалить( X, Хвост, Хвост1).

как и принадлежит, отношение удалить по природе своей недетерминировано. Если в списке встречается несколько вхождений элемента X, то удалить сможет исключить их все при помощи возвратов. Конечно, вычисление по каждой альтернативе будет удалять лишь одно вхождение X, оставляя остальные в неприкосновенности. Например:

?- удалить( а, [а, b, а, а], L].

L = [b, а, а];

L = [а, b, а];

L = [а, b, а];

nо (нет)

При попытке исключить элемент, не содержащийся в списке, отношение удалить потерпит неудачу.

Отношение удалить можно использовать в обратном направлении для того, чтобы добавлять элементы в список, вставляя их в произвольные места. Например, если мы хотим во все возможные места списка [1, 2, 3] вставить атом а, то мы можем это сделать, задав вопрос: "Каким должен быть список L, чтобы после удаления из него элемента а получился список [1, 2, 3]?"

?- удалить( а, L, [1, 2, 3] ).

L = [а, 1, 2, 3];

L = [1, а, 2, 3];

L = [1, 2, а, 3];

L = [1, 2, 3, а];

nо (нет)

Вообще операция по внесению Х в произвольное место некоторого списка Список, дающее в результате БольшийСписок, может быть определена предложением:

внести( X, Список, БольшийСписок) :-

удалить( X, БольшийСписок, Список).

В принадлежит1 мы изящно реализовали отношение принадлежности через конк. Для проверки на принадлежность можно также использовать и удалить. Идея простая: некоторый Х принадлежит списку Список, если Х можно из него удалить:

принадлежит2( X, Список) :-

удалить( X, Список, _ ).

3. 2. 5. Подсписок

Рассмотрим теперь отношение подсписок. Это отношение имеет два аргумента - список L и список S, такой, что S содержится в L в качестве подсписка. Так отношение

подсписок( [c, d, e], [a, b, c, d, e, f] )

имеет место, а отношение

подсписок( [c, e], [a, b, c, d, e, f] )

нет. Пролог-программа для отношения подсписок может основываться на той же идее, что и принадлежит1, только на этот раз отношение более общо (см. рис. 3.4).

Рис. 3. 4. Отношения принадлежит и подсписок.

Его можно сформулировать так:

S является подсписком L, если

(1) L можно разбить на два списка L1 и L2 и

(2) L2 можно разбить на два списка S и L3.

Как мы видели раньше, отношение конк можно использовать для разбиения списков. Поэтому вышеприведенную формулировку можно выразить на Прологе так:

подсписок( S, L) :-

конк( L1, L2, L),

конк( S, L3, L2).

Ясно, что процедуру подсписок можно гибко использовать различными способами. Хотя она предназначалась для проверки, является ли какой-либо список подсписком другого, ее можно использовать, например, для нахождения всех подсписков данного списка:

?- подсписок( S, [а, b, с] ).

S = [ ];

S = [a];

S = [а, b];

S = [а, b, с];

S = [b];

. . .

3. 2. 6. Перестановки

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

?- перестановка( [а, b, с], Р).

Р = [а, b, с];

Р = [а, с, b];

Р = [b, а, с];

. . .

Рис. 3. 5. Один из способов построения перестановки списка [X | L].

Программа для отношения перестановка в свою очередь опять может основываться на рассмотрении двух случаев в зависимости от вида первого списка:

(1) Если первый список пуст, то и второй список должен быть пустым.

(2) Если первый список не пуст, тогда он имеет вид [Х | L], и перестановку такого списка можно построить так, как Это показано на рис. 3.5: вначале получить список L1 - перестановку L, а затем внести Х в произвольную позицию L1.

Два прологовских предложения, соответствующих этим двум случаям, таковы:

перестановка( [ ], [ ]).

перестановка( [X | L ], Р) :-

перестановка( L, L1),

внести( X, L1, Р).

Другой вариант этой программы мог бы предусматривать удаление элемента Х из первого списка, перестановку оставшейся его части - получение списка Р, а затем добавление Х в начало списка Р. Соответствующая программа такова:

перестановка2( [ ], [ ]).

перестановка2( L, [X | Р] ) :-

удалить( X, L, L1),

перестановка2( L1, Р).

Поучительно проделать несколько экспериментов с нашей программой перестановки. Ее нормальное использование могло бы быть примерно таким:

?- перестановка( [красный, голубой, зеленый], Р).

Как и предполагалось, будут построены все шесть перестановок:

Р = [ красный, голубой, зеленый];

Р = [ красный, зеленый, голубой];

Р = [ голубой, красный, зеленый];

Р = [ голубой, зеленый, красный];

Р = [ зеленый, красный, голубой];

Р = [ зеленый, голубой, красный];

nо (нет)

Приведем другой вариант использования процедуры перестановка:

?- перестановка( L, [а, b, с] ).

Наша первая версия, перестановка, произведет успешную конкретизацию L всеми шестью перестановками. Если пользователь потребует новых решений, он никогда не получит ответ "нет", поскольку программа войдет в бесконечный цикл, пытаясь отыскать новые несуществующие перестановки. Вторая версия, перестановка2, в этой ситуации найдет только первую (идентичную) перестановку, а затем сразу зациклится. Следовательно, при использовании этих отношений требуется соблюдать осторожность