Иван Братко - Программирование на языке Пролог для искусственного интеллекта
• Найти всех детей, родившихся в 1981 году:
?- ребенок( X), датарождения( X, дата( _, _, 1981) ).
• Найти всех работающих жен:
?- жена( членсемьи( Имя, Фамилия, _, работает( _, _ ))).
• Найти имена и фамилии людей, которые не работают и родились до 1963 года:
?- существует членсемьи( Имя, Фамилия, дата( _, _, Год), неработает) ),
Год < 1963.
• Найти людей, родившихся до 1950 года, чей доход меньше, чем 8000:
?- существует( Членсемьи),
датарождения( Членсемьи, дата( _, _, Год) ),
Год < 1950,
доход( Членсемьи, Доход),
Доход < 8000.
• Найти фамилии людей, имеющих по крайней мере трех детей:
?- семья( членсемьи( _, Фамилия, _, _ ), _, [ _, _, _ | _ ]).
Для подсчета общего дохода семья полезно определить сумму доходов людей из некоторого списка в виде двухаргументного отношения:
общий( Список_Людей, Сумма_их_доходов)
Это отношение можно запрограммировать так:
общий( [], 0). % Пустой список людей
общий( [ Человек | Список], Сумма) :-
доход( Человек, S),
% S - доход первого человека
общий( Список, Остальные),
% Остальные - сумма доходов остальных
Сумма is S + Остальные.
Теперь общие доходы всех семей могут быть найдены с помощью вопроса:
?- семья( Муж, Жена, Дети),
общий( [Муж, Жена | Дети], Доход).
Пусть отношение длина подсчитывает количество элементов списка, как это было определено в разд. 3.4. Тогда мы можем найти все семьи, которые имеют доход на члена семьи, меньший, чем 2000, при помощи вопроса:
?- семья( Муж, Жена, Дети),
общий( [ Муж, Жена | Дети], Доход),
длина( [ Муж, Жена | Дети], N),
Доход/N < 2000.
Упражнения4.1. Напишите вопросы для поиска в базе данных о семьях.
(а) семей без детей;
(b) всех работающих детей;
(с) семей, где жена работает, а муж нет,
(d) всех детей, разница в возрасте родителей которых составляет не менее 15 лет.
4.2. Определите отношение
близнецы( Ребенок1, Ребенок2)
для поиска всех близнецов в базе данных о семьях.
4.2. Абстракция данных
Абстракцию данных можно рассматривать как процесс организации различных фрагментов информации в единые логические единицы (возможно, иерархически), придавая ей при этом некоторую концептуально осмысленную форму. Каждая информационная единица должна быть легко доступна в программе. В идеальном случае все детали реализации такой структуры должны быть невидимы пользователю этой структуры. Самое главное в этом процессе - дать программисту возможность использовать информацию, не думая о деталях ее действительного представления.
Обсудим один из способов реализации этого принципа на Прологе. Рассмотрим снова пример с семьей из предыдущего раздела. Каждая семья — это набор некоторых фрагментов информации. Все эти фрагменты объединены в естественные информационные единицы, такие, как "член семьи" или "семья", и с ними можно обращаться как с едиными объектами. Предположим опять, что информация о семье структурирована так же, как на рис. 4.1. Определим теперь некоторые отношения, с помощью которых пользователь может получать доступ к конкретным компонентам семьи, не зная деталей рис. 4.1. Такие отношения можно назвать селекторами, поскольку они позволяют выбирать конкретные компоненты. Имя такого отношения-селектора будет совпадать с именем компоненты, которую нужно выбрать. Отношение будет иметь два аргумента: первый — объект, который содержит компоненту, и второй — саму компоненту:
отношение_селектор(Объект, Выбранная_компонента)
Вот несколько селекторов для структуры семья:
муж( семья( Муж, _, _ ), Муж).
жена( семья( _, Жена, _ ), Жена).
дети( семья( _, _, СписокДетей ), СписокДетей).
Можно также создать селекторы для отдельных детей семьи:
первыйребенок( Семья, Первый) :-
дети( Семья, [Первый | _ ]).
второйребенок( Семья, Второй) :-
дети( Семья, [ _, Второй | _ ]).
...
Можно обобщить этот селектор для выбора N-го ребенка:
nребенок( N, Семья, Ребенок) :-
дети( Семья, СписокДетей),
n_элемент( N, СписокДетей, Ребенок)
% N-й элемент списка
Другим интересным объектом является "член семьи". Вот некоторые связанные с ним селекторы, соответствующие рис. 4.1:
имя( членсемьи( Имя, _, _, _ ), Имя).
фамилия( членсемьи( _, Фамилия, _, _ ), Фамилия).
датарождения( членсемьи( _, _, Дата), Дата).
Какие преимущества мы можем получить от использования отношений-селекторов? Определив их, мы можем теперь забыть о конкретном виде структуры представления информации. Для пополнения и обработки этой информации нужно знать только имена отношений-селекторов и в оставшейся части программы пользоваться только ими. В случае, если информация представлена сложной структурой, это легче, чем каждый раз обращаться к ней в явном виде. В частности, в нашем примере с семьей пользователь не обязан знать, что дети представлены в виде списка. Например, предположим, мы хотим сказать, что Том Фокс и Джим Фокс принадлежат к одной семье и что Джим — второй ребенок Тома. Используя приведенные выше отношения-селекторы, мы можем определить двух человек, назовем их Человек1 и Человек2, и семью. Следующий список целей приводит к желаемому результату:
имя( Человек1, том), фамилия( Человек1, фокс),
% Человек1 - Том Фокс
имя( Человек2, джим), фамилия( Человек1, фокс),
% Человек2 - Джим Фокс
муж( Семья, Человек1),
второйребенок( Семья, Человек2)
Использование отношений-селекторов облегчает также и последующую модификацию программ. Представьте себе, что мы захотели повысить эффективность программы, изменив представление информации. Все, что нужно сделать для этого, — изменить определения отношений-селекторов, и вся остальная программа без изменений будет работать с этим новым представлением.
Упражнение4.3. Завершите определение отношения nребенок, определив отношение
n_элемент( N, Список, X)
которое выполняется, если X является N-м элементом списка Список.
4.3. Моделирование недетерминированного автомата
Данное упражнение показывает, как абстрактную математическую конструкцию можно представить на Прологе. Кроме того, программа, которая получится, окажется значительно более гибкой, чем предполагалось вначале.
Недетерминированный конечный автомат — это абстрактная машина, которая читает символы из входной цепочки и решает, допустить или отвергнуть эту цепочку. Автомат имеет несколько состояний и всегда находится в одном из них. Он может изменить состояние, перейдя из одного состояния в другое. Внутреннюю структуру такого автомата можно представить графом переходов, как показано на рис. 4.3. В этом примере S1, S2, S3 и S4 — состояния автомата. Стартовав из начального состояния (в нашем примере это S1), автомат переходит из состояния в состояние по мере чтения входной цепочки. Переход зависит от текущего входного символа, как указывают метки на дугах графа переходов.
Рис. 4.3. Пример недетерминированного конечного автомата.
Переход выполняется всякий раз при чтении входного символа. Заметим, что переходы могут быть недетерминированными. На рис. 4.3 видно, что если автомат находится в состоянии S1, и текущий входной символ равен а, то переход может осуществиться как в S1, так и в S2. Некоторые дуги помечены меткой пусто, обозначающей "пустой символ". Эти дуги соответствуют "спонтанным переходам" автомата. Такой переход называется спонтанным, потому что он выполняется без чтения входной цепочки. Наблюдатель, рассматривающий автомат как черный ящик, не сможет обнаружить, что произошел какой-либо переход.
Состояние S3 обведено двойной линией, это означает, что S3 — конечное состояние. Про автомат говорят, что он допускает входную цепочку, если в графе переходов существует путь, такой, что:
(1) он начинается в начальном состоянии,
