Использование надрезов (snip)

Надрез обозначается открывающей скобкой [! и закрывающей скобкой !]. Например, для правила

цель:- подцель1,[! подцель2,подцель3!],подцель4.

действие надреза распространяется на подцели подцель2 и подцель3, расположенные между этими двумя скобками.

Snip аналогичен cut, однако отличается от него тем, что если после бектрекинга управление передастся snip, весь предикат неуспешным не будет. Бектрекинг лишь "пропустит" те подцели, которые находятся внутри snip и продолжится для подцелей, которые расположены раньше snip [7].

Отличие надреза от отсечения:

Для cut если E неуспешна, бектрекинг попадает на cut и весь предикат A неуспешен, в отличие от ситуации со snip. Для snip, если подцель Е неуспешна, то бектрекинг попадает на подцель B.

Надрезы целесообразно использовать в случаях, когда нужно ограничить бектрекинг для исключения ненужного поиска, но отсечение не требуется.

УПРАЖНЕНИЕ. Вообще говоря, надрезы не реализованы в SWI-Prolog. Используя отсечение, реализуйте надрез (т.е. «заморозьте» точки возврата только для предикатов, которые должны быть внутри надреза). Одна из реализаций может быть представлена в виде схемы (по результату равносильна вышеприведённой схеме надреза):

A:-B, T, E.

T:-C, D,!.

b(2). %(1)

b(3). %(2)

c(2). %(3)

c(3). %(4)

d(4). %(5)

d(5). %(6)

e(10). %(7)

e(11). %(8)

e(12). %(9)

a(X,Y,Z,W):-b(X),[! c(Y), d (Z)!],e(W). %(10)

a(X,X,X,X):-d(X). %(11)

/* В SWI-Prolog надрез можно реализовать через

отсечение следующим образом: */

a(X,Y,Z,W):-b(X),f(Y,Z),e(W).

a(X,X,X,X):-d(X).

f(Y,Z):-C(Y),d(Z),!.

2?- a(X,Y,Z,W).

X = 2,Y = 2,Z = 4,W = 10; X = 2,Y = 2,Z = 4,W = 11;

X = 2,Y = 2,Z = 4,W = 12; X = 3,Y = 2,Z = 4,W = 10;

X = 3,Y = 2,Z = 4,W = 11; X = 3,Y = 2,Z = 4,W = 12;

X = 4,Y = 4,Z = 4,W = 4; X = 5,Y = 5,Z = 5,W = 5.

Как видно из примера надрез «замораживает» предикаты c(Y) и d(Z) в строке (10). Поэтому при получении вывода с использованием этой строки значения переменных Y, Z при поиске всех альтернативных решений не меняются – для c(Y) и d(Z) не ищется других альтернатив, кроме как c(2) и d(4) соответственно.

ЗАДАНИЕ 4.7

Используйте базу данных из задания 1.6 лабораторной работы 1. Добавьте факты для каждого животного X

животное(X).

Для исключения повторения названия животных на запросы

"Кто живет хотя бы (ровно) в двух средах обитания?"

можно использовать надрез

цель(X):- животное(X),[!живет(X,Y),живет(X,Z),Y\=Z!].

СПИСКИ

ЦЕЛЬ: Знакомство с понятием списка и операциями над списками.

Список

- это упорядоченная последовательность элементов. Элементами списка могут быть любые термы Пролога. Удобной формой записи списков является так называемое списочное обозначение. В данном обозначении каждый элемент списка отделяется от соседнего запятой, а весь набор элементов заключается в квадратные скобки, например, [a,b,c,d].

Фактически список - это структура с функтором ‘ '/2 (точка с арностью 2). Согласно этому определению, список состоит из первого элемента и хвоста, который представляет собой список из остальных элементов.

Пустой список - это список, не содержащий ни одного элемента, он обозначается [].

Примеры.

N	элементы списка	запись со скобками	запись с функтором ‘ ’
	a	[a]	‘ ’(a, [])
	a b c	[a,b,c]	‘ ’(a, ‘ ’(b, ‘ ’(c,[])))
	[a]	[[a]]	‘ ’(‘ ’(a,[]),[])
	[]	[[]]	‘ ’ ([],[])
	[a] [b,c]	[[a],[b,c]]	‘ ’(‘ ’(a,[]), ‘ ’(b, ‘ ’(c,[])))

Список унифицируется с другим списком, если попарно унифицируются их элементы.

Список может делиться на "голову" и "хвост" с помощью операции отделения головы, которая обозначается вертикальной чертой (|), т.е. [Голова|Хвост]. Голова - фиксированное количество элементов. Хвост - список из оставшихся элементов списка. Чаще всего используется голова, состоящая из одного элемента.

В виде дерева список [X|Y] изображается следующим образом:

Примеры сопоставления списков со списком [Голова|Хвост]

N	Список	Голова	Хвост
	[a]	a	[]
	[a,b,c]	a	[b,c]
	[[a]]	[a]	[]
	[]	не сопоставляется	не сопоставляется
	[a|[c,d]]	a	[c,d]

Список [1,2|[3,4]] равен списку [1,2,3,4]. При сопоставлении со списком [X,Y|Z] получим X=1, Y = 2 и Z = [3,4].

В SWI/PROLOG имеется особый вид списков - символьные списки. Символьный список - это фактически последовательность целых чисел, соответствующих ASCII-коду символов. Символьные списки заключаются в двойные кавычки. Следующие три списка являются сопоставимыми:

"abc" [ 97, 98, 99 ] '.'(97,'.'(98,'.'(99),[])))

ПРОГРАММА 1 Разделение списка на голову и хвост.

write_list([]).

write_list([H|T]):- /* разделение списка на голову и хвост, */

write(H), nl, /* печать головы, пропуск строки */

write_list(T)./*рекурсивный вызов предиката от оставшегося списка*/

ЗАДАНИЕ 5.1

Запустите программу 1, посмотрите результат для списка [1,2,a,3].

ПРОГРАММА 2.Конкатенация и разбиение списков.

append([],List,List).

append([X|L1],List2,[X|L3]):-append(L1,List2,L3).

ЗАМЕЧАНИЕ. Предикат append /3 является встроенным в SWI-Prolog.

Используя предикат append(X,Y,Z), осуществите склейку списков [1,2,3] и [4,5], вычитание списка [4,5] из [1,2,3,4,5]) и "разбиение" списка на две части в режиме трассировки.

ЗАДАНИЕ 5.2

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

· Определение длины списка.

(Длина пустого списка равна 0.

Длина непустого списка равна длине его хвоста плюс 1.)

· Определение принадлежности элемента к списку.

(Элемент принадлежит списку, если он - его голова. Элемент принадлежит списку, если он принадлежит хвосту списка.)

· Поиск суммы элементов числового списка.

· Поиск максимального и минимального элементов числового списка с использованием одной рекурсии.

· Инверсия списка.

ЗАДАНИЕ 5.3

Напишите программу сортировки числового списка методом "пузырька".

6. МОДИФИКАЦИЯ УТВЕРЖДЕНИЙ ПРОГРАММЫ.
РАБОТА С БАЗОЙ ДАННЫХ.

ЦЕЛЬ. Научиться работать с динамическими базами знаний.

Встроенные предикаты asserta/1 и assert/1 позволяют добовлять

новые утверждения в базу данных Пролога (в начало и в конец

соответственно), а retract/1 - удалять утверждение, заголовок

которого унифицируется с аргументом. Например, можно составить запрос, который опрашивает пользователя о знании языков:

язык(итальянский).

язык(немецкий).

язык(японский).

язык(французский).

язык(английский).

?- write('Введите Ваше имя '),

read(Имя),

язык(Яз),

write('Знаете ли Вы '), write(Яз),

write(' язык'),nl,

read(да),

assert(владеет(Имя,Яз)),fail.

Часто используется предикат retractall/1, удаляющий из базы данных все предложения, заголовки которых унифицируются с аргументом.

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

%член(_Фамилия,_Возраст,_Данные_об_уплате)

:-dynamic(член/3).

член('Иванов',15,уплачено).

член('Иванов',33,не_уплачено).

член('Хромов',40,не_уплачено).

Конструкция:-dynamic(член/3) необходима для того, чтобы возможно было изменять базу фактов, связанную с предикатом член/3 с помощью предиката assert во время выполнения. Для безвозвратной отмены действия предиката dynamic используют предикат compile_predicates(List_of_nameArity). После использования этого предиката факты указанные в аргументе не могут быть изменены динамически до конца программы (пример использования: compile_predicates(член/3)).

Размер взноса не указывается, он определяется по возрасту:

взнос(Возраст,рублей(1)):-Возраст<18.

взнос(Возраст,рублей(2)):-Возраст>=18.

Рассмотрим некоторые операции над базой данных.Внести сведения о новом члене организации:

пополнить_состав(Член):-assert(Член).

Выдать на терминал сведения о членстве в организации:

выдать_сведения(член(Фамилия,Возраст,Данные_об_уплате)):-

член(Фамилия,Возраст,Данные_об_уплате),

взнос(Возраст,Сумма),

write(член(Фамилия,Возраст,Сумма,Данные_об_уплате)),nl,fail.

выдать_сведения(_).

Удалить сведения о членах организации:

сократить_состав(Член):-retractall(Член).

Внести данные о том, что член организации уплатил членский взнос:

запись_об_уплате(член(Фамилия,Возраст)):-

retract(член(Фамилия,Возраст,не_уплачено)),

assert(член(Фамилия,Возраст,уплачено)).

ЗАДАНИЕ 6.1

Выполните следующие запросы к программе

?-пополнить_состав(член('Пронин',45,уплачено)).

?-пополнить_состав(член('Сидоров',27,не_уплачено)).

?-пополнить_состав(член('Данилов',12,не_уплачено)).

?-пополнить_состав(член('Иванов',15,уплачено)).

?-пополнить_состав(член('Иванов',33,не_уплачено)).

?-пополнить_состав(член('Хромов',40,не_уплачено)).

?-выдать_сведения(_).

ЗАДАНИЕ 6.2

Внесем данные о том, что Хромов оплатил взнос и просмотрим

содержание всей базы и отдельно список должников, а затем исключим всех,кто не уплатил взнос, выполнив запросы:

?-запись_об_уплате(член('Хромов',40)),выдать_сведения(_).

?-выдать_сведения(член(_,_,не_уплачено)).

?-сократить_состав(член(_,_,не_уплачено)),выдать_сведения(_).

Предикат выдать_сведения/1 пример применения вынуждаемого возврата для получения всех возможных вариантов согласования цели. При этом результат, выводимый на экран, уничтожается механизмом возвратов из памяти программы, но его можно накапливать, используя побочный эффект действия предикатов assert/1 и retract/1. Это накопление реализуется процедурами действия над счетчиком:

установить_счетчик(Имя,Начало):-

retractall(счетчик(Имя,_)),

assert(счетчик(Имя,Начало)).

увеличить_счетчик(Имя,Прирост):-

retract(счетчик(Имя,Значение)),

Новое_значение is Значение+Прирост,

assert(счетчик(Имя,Новое_значение)).

сбросить_счетчик(Имя,Значение):-

retract(счетчик(Имя,Значение)).

Для иллюстрации рассмотрим процедуру, подсчитывающую число членов клуба:

подсчет_членов(член(Фамилия,Возраст,Данные_об_уплате),_):-

установить_счетчик(число_членов,0),

член(Фамилия,Возраст,Данные_об_уплате),

увеличить_счетчик(число_членов,1),

fail.

подсчет_членов(_,Счетчик):-

сбросить_счетчик(число_членов,Счетчик).

Если программа предназначена для получения ряда значений при помощи одного из встроенных предикатов чтения входных данных, то такой подход использовать уже нельзя, так как read/1 и другие читают новое значение только при первом вызове и не делают этого при возврате. Эту трудность можно преодолеть, добавив в программу определение предиката repeat/0 - согласуемого всегда, в том числе и при возвратах:

repeat.

repeat:-repeat.

Используем этот прием для определения процедуры меню:

меню:-repeat,

nl,nl,write(' МЕНЮ'),nl,

write('1. Сведения о членах клуба.'),nl,

write('2. Посчитать количество членов.'),nl,

write('3. Добавить запись о члене клуба.'),nl,

write('0. ВЫХОД'),nl,nl,

write('Введите номер пункта меню '),

read(Х),

обработать(Х).

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

обработать(0):-!.

обработать(Х):-пункт(Х),fail.

пункт/1 выполняет соответствующую операцию

пункт(1):-nl,write('Состав клуба:'),

nl,выдать_сведения(_),!.

пункт(2):-nl,подсчет_членов(член(_,_,_),Число),

write('Количество членов клуба = '),

write(Число),nl,!.

пункт(3):-nl,write('Введите данные нового члена клуба '),nl,

write('Фамилия '),read(Фамилия),

write('Возраст '),read(Возраст),

write('Отметка об уплате взноса '),read(Данные_об_уплате),

пополнить_состав(член(Фамилия,Возраст,Данные_об_уплате)),!.

пункт(_):-write('Такой пункт неопределен!'),nl,!.

ЗАДАНИЕ 6.3

Запустите программу, выполнив запрос:

?-меню.

ЗАМЕЧАНИЕ. В случае ввода нескольких слов для одного запроса от предиката read/1 или в случае если ввод начинается с заглавной буквы стоит заключать вводимую последовательность символов в апострофы. Причина в том, что предикат read(X) считывает терм из текущего потока ввода и унифицирует его с термом X.

ЗАДАНИЕ 6.4

Сохраните текст программы под новым именем. Добавьте пункты удаления члена клуба и внесения отметки об уплате взноса (обратите внимание, что для этого необходимо ввести фамилию и возраст члена клуба). А также удаления неплательщиков. Добавьте пункт меню о текущем количестве членов клуба не сдавших взносы.

ЗАДАНИЕ 6.5

Самостоятельно напишите динамическую базу данных "Деканат", содержащую информацию о сроках и результатах сдачи экзаменов студентами по нескольким предметам, например: математике, физике, информатике. Количество предметов и число студентов, сдававших экзамены может динамически меняться. Напишите меню для работы с ней. Ваша программа должна предоставлять возможность добавлять записи о сдаче, пересдаче экзаменов; получения ведомости; получения списка неуспевающих; операции отчисления, среднего балла по предмету, получения стипендии по результатам всех экзаменов и т.д.

ПРИЛОЖЕНИЕ 1. ТИПЫ ДАННЫХ SWI/PROLOG

ПЕРЕМЕННЫЕ

Именем переменной может быть любая последовательность латинских и русских букв и цифр, начинающаяся с прописной буквы или символа подчеркивания "_"; это может быть также одиночный символ подчеркивания "_", представляющий анонимную (безымянную) переменную.

ПРИМЕРЫ переменных:

Balloon X _0039 _ A1

Свободная (не имеющая значения) переменная может унифицироваться с любым термом, при этом она может конкретизироваться значением (в случае константы или сложного терма), либо связываться с другой переменной. Для связанной переменной в сопоставлении используется ее значение. Анонимная переменная значения не получает, с ней всегда возможно сопоставление.