Краткие теоретические сведения.

Работа со списками. Список – это специальный вид сложного терма, состоящий из головы списка и хвоста списка, гдеголова – элемент списка, а хвост рекурсивно определяется как остаток списка. Элементами списка могут быть любые объекты, в т. ч. тоже списки.

Синтаксически список задается следующим образом: [X|Y], где X – это голова списка, Y – хвост. При построении списков необходимо наличие константного символа, чтобы рекурсия не была бесконечной. Этот "пустой список" будем обозначать знаком [].

Точное описание списка в виде фрагмента программы имеет вид:

list([]).

tist([X|Y]):-list(Y).

Декларативная интерпретация: списком является либо пустой список либо значение функции соединения на паре, хвост которой – список.

Например, список [а,Ь,с] является примером терма [X|Y] при подстановке {X=a,Y=[b,c]}.

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

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

1) из факта, ограничивающего рекурсию и описывающего операцию для пустого списка;

2) из рекурсивного правила, определяющего операцию над списком, состоящим из головы и хвоста (в голове правила), через операцию над хвостом (в подцели).

В процессе вычисления цели Пролог проводит перебор вариантов в соответствии с установленным порядком. Цели выполняются последовательно, одна за другой, а в случае неудачи происходит откат к предыдущей цели (baсktracing).

Однако для повышения эффективности выполнения программы часто требуется вмешаться в перебор, ограничить его, исключить некоторые цели. Для этого в Пролог введена специальная конструкция cut – "отсечение", обозначаемая как "!" (Читается "cut", "кат"). Cut подсказывает Прологу "закрепить" все решения, предшествующие появлению его в предложении. Это означает, что если требуется бэктрекинг, то он приведет к неудаче (fail) без попытки поиска альтернатив.

Пример действия cut. Пусть база данных выглядит следующим образом:

data(one).

data (two).

data(three).

Процедура для проверки:

cut_test_a(X):-data(X).

cut_test_a(‘last clouse’)

Цель:?- cut_test_a(X),nl,write(X).

one;

two;

three;

‘last clouse’;

no.

Теперь поставим cut в правило:

cut_test_b(X):-data(X),!.

cut_test_b(‘last clouse’)

Цель:?- cut_test_b(X),nl,write(X).

one;

no.

Происходит остановка бэктрекинга для левого data и родительского:

cut_test_b(X)..

Теперь поместим cut между двумя целями:

cut_test_c(X,Y):-data(X),!,data(Y).

cut_test_c(‘last clouse’)

Теперь бэктрекинг не будет для для левого data и родительского cut_test_b(X), но будет для правого data,стоящего после!.

?- cut_test_с(X,Y),nl,write(X,Y).

one-one;

one-two;

one-tree;

no

Введение отсечения повышает эффективность программы, сокращая время перебора и объем памяти, не влияет на декларативное чтение программы. После изъятия отсечения декларативный смысл не измениться – такое применение отсечения называют «зеленым отсечением». «Зеленые отсечения» лишь отбрасывают те пути вычисления, которые не приводят к новым решениям. Бывают «красные отсечения», при их изъятии меняется декларативный смысл программы.

Формальное описание действия отсечения. Рассмотрим предложение Н:-В1, В2,….., Вm,!,….,Bn. Это предложение активизируется, когда некоторая цель G будет сопоставляться с Н. Тогда G называют целью-родителем. Если В1, В2,..., Вm выполнены, а после! (например, в Bi, i>m) произошла неудача и требуется выбрать альтернативные варианты, то для B1, В2,..., Вm такие альтернативы больше не рассматриваются ч все выполнение окончится неудачей. Кроме того, G будет связана с головой Н и другие предложения процедуры во внимание не принимаются. Т.е. отсечение в теле предложения отбрасывает все предложения, расположенные после этого предложения. Формально действие отсечения описывается так: пусть цель-родитель сопоставляется с головой предложения, в теле которого содержится отсечение. Когда при просмотре целей тела предложения встречается в качестве цели отсечение, то такая цель считается успешной и все альтернативы принятым решениям до отсечения отбрасываются, а любая попытка найти новые альтернативы на промежутке между целью-родителем и он оканчиваются неудачей.

Процесс поиска возвышается к последнему выбору, сделанному перед сопоставлением цели-родителя.

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

Следует избегать двух ошибок:

отсечения путей вычисления, которые нельзя отбрасывать;

неотсечения тех решений, которые должны были быть отброшены.

Рассмотрим программу:

В.

D.

А:-В,С. (1)

C:-D,!,E. (2)

E:-F,G,H. (3)

?А.

Говорят, что дизъюнкт (1) «порождает» дизъюнкт (2), так как в правой части (1) есть литера С и эта же литера – в левой части (2). Аналогично дизъюнкт (2) «порождает» дизъюнкт (3). Если (3) неудачен, то в (2) выполнится отсечение: дизъюнкт (2) также считается неудачным, восстанавливается «родительская среда» (1), делается попытка найти альтернативное решение для В. Если, бы (2) имело вид С:-D,Е., то при неудаче в (3) была бы сделана попытка найти альтернативное решение для D.

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

Рассмотрим некоторые стандартные операции над списками:

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

member(X,[X|Y]).)

member(X,[_|Y]):-member(X,Y).

Декларативный аспект программы:

X является элементом списка, если в соответствии с первым предложением X -голова списка, или в соответствии со вторым предложением X - элемент хво­ста.

Процедурный аспект программы:

для определения того, является ли X элементом списка, нужно определить, сов­падает ли X с головой списка и если не совпадает, искать X в хвосте списка.

Таким образом, member(X,Y) - отношение принадлежности к списку.

Например, member(4,[4,6,7]) - да.

member(8,[4,5,7,8,9])?

Работает второе правило. Список разбирается до тех пор, пока факт не бу­дет истинен. Затем список собирается в обратном порядке.

2. Вывод элементов списка.

Первое правило: остановится, когда исчерпаны все элементы списка.

Второе правило: вывести элемент списка и работать далее с хвостом спи­ска.

append([]).

append([X|Y]):-write(X),append(Y).

Например, append([3,6,8,10])?

Факт ложен - работает второе правило:

[3,6,8,10] 3 [6,8,10]

[6,8,10] 6 [8,10]

[8,10] 8 [10]

[10] 10 []

Факт истинен - список собирается путем присоединения головы списка к хвосту согласно левой части правила - [3,6,8,10].

3. Рассмотрим фрагмент программы, выражающей отношение между спи­сками и числами. Предикат leng(L,N) истинен, если список L содержит N эле­ментов.

leng([],0).

leng([X|L),N):-leng(L,N1),N=Nl+1.

Например, leng([3,4,5,7],Y)?

Факт ложен - работает второе правило.

[3,4,5,7], [4,5,7],

[4,5,7], [5 7],

[5,7], [7],

[7], [],

Факт истинен. Правило работает следующим образом:

[7],1 1=1

[5,7],2 2=2

[4,5,7],3 3=3

[3,4,5,7],4 4=4

Таким образом, Y=4.

4. Не менее важной операцией над списками является операция соедине­ния двух списков для получения третьего. Определим предикат списка через три аргумента:

список(L1,L2,LЗ)

если L1 - пустой список, то результатом добавления L1 к L2 будет список L3.

На Прологе можно записать:

spicok([],LI,L1).

В противном случае формируется список L3, голова которого совпадает с годовой списка L1. Если первый аргумент отношения не пуст, то он имеет го­лову и хвост, и записывается это так:

[X|L1]

Таким образом можно показать соединение списка [X|L1] с произвольным списком L2, результат - список L3.

На Прологе можно записать так:

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

Если посмотреть на "spisok" с декларативной точки зрения, то мы, таким образом, описали отношение между тремя списками. Эти отношения сохраняются и в том случае, если известны L1 и L3, a L2 - нет, или известен только L3.

5. Добавление элемента к списку.

Наиболее простой способ добавить элемент в список - это вставить его в самое начало так, чтобы он стал его новой головой. Если X - это новый элемент, а список, в который X добавляется, - L, тогда результирующий список - просто [X|L].

Таким образом, чтобы добавить новый элемент в начало списка, не надо никакой процедуры. В явном виде это можно представить фактом:

добавить(Х,L,[Х|L]).

6. Выделение подсписка.

Это отношение имеет два аргумента - список L и список S, такой, что S содержится в L в качестве подсписка. Так отношение подсписок ([c,d,e],[a,b,c,d,e,f]) имеет место, а отношение подсписок([с,е],[а,b,с,d,e,f]) - нет.

Подсписок можно сформулировать так:

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

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

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

На Прологе это можно записать следующим образом:

podspisok(S,L):-spisok(L1,L2,L3),spisok(S,L3,L).

Фрагмент программы будет иметь вид:

spicok([],L1,Ll).

spisok([X|L1],L2,[X|L3]):-spisok(L1,L2,L3).

podspisok(S,L):-spisok(L1,L2,L),spisok(S,L3,L).

Например, podspisok([2,3],[ 1,2,3])?

7. Удаление элемента списка.

Для удаления элемента из списка требуются три аргумента: удаляемый элемент X, список LI, в который может входить X, и список L2, из которого удалены все вхождения элемента X.

Имеем два случая:

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

этого списка.

Процедурный аспект программы:

del([X|L],X,L).

Декларативный подход к фрагменту: "Удаление X из списка [X|L] приводит к L, если удаление X из L приводит к L1". Подходящим правилом является

del([X|L],X,L):-del(L,X,Ll).

Условие совпадения головы списка и удаляемого элемента задано с по­мощью общей переменной в заголовке правила;

2) если X находится в хвосте списка, тогда его нужно удалить оттуда:

del([Y|L],X,Y|L1):-del(L,X,L1).

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

Например, del([3,5,3,5,7,3],3,Y)?

Y=[5,3,5_t7,3]

Y=[3,5,5,7,3]

Y=[З,5,З,5,7]

Декларативное понимание: «Удаление X из списка [Y|L] равно [Y|L1], если X отлично от Y и удаление X из L приводит к L1». В отличие от предыдущего правила условие неравенства головы списка и удаляемого элемента явно задано в теле правила.

del([Y|L],X,Y|L1):-X<>Y,del(L,X,L1).

Исходный случай задается непосредственно. Из пустого списка не удаляется ничего, результатом будет также пустой список. Это выражается фактом

del([],X,[]).

Полный фрагмент программы имеет вид:

del([],X,[]).

del([X|L],X,L):-del(L,X,L1).

del([ Y|L],X,Y|L1):-del(L,X,L 1).

Значение программы содержит примеры, в которых удаляемый элемент вообще не входит в исходный список, - например, выполнено del([l,2,3],4,[1,2,3]). Существуют приложения, в которых это нежелательно. Определим отношение dell(X,L,Ll), в котором случай списка, не содержащего элемент X, рассматривается следующим образом:

dell([X|L],X,L).

dell([Y|L],X,[Y|L1]):-dell(L,X,L1).

Декларативное понимание программы: «Выделение элемента X из списка [X|L] приводит к L или выделение X из списка [Y|L] приводит к [Y|L1], если выделение X из списка L приводит к L1». Это отношение используется как вспомогательное отношение для программы сортировки списков.

8. Добавление элемента без дублирования.

Чтобы добавить элемент в голову списка, достаточно использовать

add(X,L,[X|L]).

Но если возникает необходимость добавлять только при отсутствии эле­мента, то можно добавить правило:

add(X, L, L):-member(X,L),!,add(X,L,[X|L]).

Вопрос?-add(a, [b,с], L). L=[a, b, c]

?-add(b, [b, c], L). L=[b, c]

Если отсечение убрать, то

?-add(b, [b, c], L). L=[b, c]; L=[b, b, c]

Таким образом, при изъятии отсечения изменился декларативный смысл программы - отсечение «красное».

⇐ Предыдущая12345678910Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: