Использование структур: примеры
Структуры данных вместе с сопоставлением, автоматическими возвратами и арифметикой представляют собой мощный инструмент программирования. В этой главе мы расширим навыки использования этого инструмента при помощи следующих учебных программных примеров: получение структурированной информации из базы данных, моделирование недетерминированного автомата, планирование маршрута поездки и решение задачи о расстановке восьми ферзей на шахматной доске. Мы увидим также, как в Прологе реализуется принцип абстракции данных.
Получение структурированной информации из базы данных
Это упражнение развивает навыки представления структурных объектов данных и управления ими. Оно показывает также, что Пролог является естественным языком запросов к базе данных.
База данных может быть представлена на Прологе в виде множества фактов. Например, в базе данных о семьях каждая семья может описываться одним предложением. На рис. 4.1 показано, как информацию о каждой семье можно представить в виде структуры. Каждая семья состоит из трех компонент: мужа, жены и детей. Поскольку количество детей в разных семьях может быть разным, то их целесообразно представить в виде списка, состоящего из произвольного числа элементов. Каждого члена семьи в свою очередь можно представить структурой, состоящей из четырех компонент: имени, фамилии, даты рождения и работы. Информация о работе — это либо "не работает", либо указание места работа и оклада (дохода). Информацию о семье, изображенной на рис. 4.1, можно занести в базу данных с помощью предложения:
|
|
|
семья( членсемьи( том, фокс, дата( 7, май, 1950),
работает( bbс, 15200) ),
членсемьи( энн, фокс, дата( 9, май, 1951), неработает),
[членсемьи( пат, фокс, дата( 5, май, 1973), неработает),
членсемьи( джим, фокс, дата( 5, май, 1973), неработает) ] ).
Рис. 4.1. Структурированная информация о семье.
Тогда база данных будет состоять из последовательности фактов, подобных этому, и описывать все семьи, представляющие интерес для нашей программы.
В действительности Пролог очень удобен для извлечения необходимой информации из такой базы данных. Здесь хорошо то, что можно ссылаться на объекты, не указывая в деталях всех их компонент. Можно задавать только структуру интересующих нас объектов и оставлять конкретные компоненты без точного описания или лишь с частичным описанием. На рис. 4.2 приведено несколько примеров. Так, а запросах к базе данных можно ссылаться на всех Армстронгов с помощью терма
семья( членсемьи( _, армстронг, _, _ ), _, _ )
Символы подчеркивания обозначают различные анонимные переменные, значения которых нас не заботят. Далее можно сослаться на все семьи с тремя детьми при помощи терма:
|
|
|
семья( _, _, [ _, _, _ ])
Чтобы найти всех замужних женщин, имеющих по крайней мере троих детей, можно задать вопрос:
?- семья( _, членсемьи( Имя, Фамилия, _, _ ), [ _, _, _ | _ ]).
Главным моментом в этих примерах является то, что указывать интересующие нас объекты можно не только по их содержимому, но и по их структуре. Мы задаем одну структуру и оставляем ее аргументы в виде слотов (пропусков).
Рис. 4.2. Описания объектов по их структурным свойствам: (а) любая семья Армстронгов; (b) любая семья, имеющая ровно трех детей; (с) любая семья, имеющая по крайней мере три ребенка. Структура (с) дает возможность получить имя и фамилию жены конкретизацией переменных Имя и Фамилия.
Можно создать набор процедур, который служил бы утилитой, делающей взаимодействие с нашей базой данных более удобным. Такие процедуры являлись бы частью пользовательского интерфейса. Вот некоторые полезные процедуры для нашей базы данных:
муж( X) :- % X - муж
семья( X, _, _ ).
жена( X) :- % X - жена
семья( _, X, _ ).
ребенок( X) :- % X - ребенок
семья( _, _, Дети),
принадлежит( X, Дети).
принадлежит( X, [X | L ]).
принадлежит( X, [Y | L ]) :-
принадлежит( X, L).
|
|
|
существует( Членсемьи) :-
% Любой член семьи в базе данных
муж( Членсемьи);
жена( Членсемьи);
ребенок( Членсемьи).
дата рождения( Членсемьи( _, _, Дата, _ ), Дата).
доход( Членсемьи( _, _, _, работает( _, S) ), S).
% Доход работающего
доход( Членсемьи( _, _, _, неработает), 0).
% Доход неработающего
Этими процедурами можно воспользоваться, например, в следующих запросах к базе данных:
• Найти имена всех людей из базы данных:
?- существует( членсемьи( Имя,Фамилия, _, _ )).
• Найти всех детей, родившихся в 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.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-м элементом списка Список.
Дата добавления: 2018-05-01; просмотров: 582; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!