Использование структур
Структуры данных являются мощным средством программирования в Прологе. Они позволяют организовать различные фрагменты информации в единые логические единицы, что дает возможность использовать информацию, не думая о деталях ее действительного представления. Широкое применение структур – это также средство представления структурных объектов (баз данных) и управления ими. Использование структур делает Пролог и естественным языком запросов к базе данных.
Структура данных в Прологе задается на составной области определения (третий способ указания Domains).
Рассмотрим ряд примеров с использованием структур.
20. База данных "Семья". Каждая семья состоит, с точки зрения логики, из трех объектов: мужа, жены и детей. Поскольку количество детей в разных семьях может быть разным, то их целесообразно представить в виде списка, состоящего из произвольного числа элементов. Каждого члена семьи в свою очередь можно представить структурой, состоящей из четырех компонент: имени, фамилии, даты рождения и работы. Информация о работе – это либо "не работает", либо указания кода работы и оклада.
Ясно, что для описания такой базы данных понадобится сложная область определения. Введем следующие структуры, соответствующие соответственно дате рождения члена семьи (число, месяц, год) и работе :
Domains
data=dat(integer,string,integer)
work=worker(string,integer);notwork
Тогда основная структура, соответствующая описанию каждого члена семьи, может выглядеть таким образом:
memfam=mem(string,string,data,work)
Информацию о семьях можно занести в базу данных с помощью следующих предложений:
family(mem(jon,kelly,dat(17,may,1950),worker(bbz,15000)),
mem(bony,kelly,dat(29,may,1951),notwork)),
[mem(pat,kelly,dat(5,april,1983),notwork),
mem(liz,kelly,dat(10,april,1960),notwork)).
family(mem(bob,rob,dat(14,may,1930),worker(pla,12000)),
mem(sally,rob,dat(5,october,1931),worker(plt,11000)),[ ]). % нет детей
Теперь из такой базы данных уже можно извлекать информацию. Так, в запросах к базе данных можно ссылаться на всех kelly с помощью терма:
goal family(mem(_,kelly,_,_),_,_).
Символы подчеркивания обозначают различные анонимные переменные, значения которых нас не интересуют.
Можно найти все семьи с тремя детьми при помощи выражения:
goal family(X,_, [_,_,_]).
Чтобы найти имена и фамилии всех женщин, имеющий по крайней мере трех детей, можно задать вопрос:
goal family(_, mem(Name,Fam,_,_),[_,_,_|_]).
Главным моментом в этих примерах является то, что указывать интересующие нас объекты можно не только по их содержимому, но и по их структуре, т.е. иметь результат в виде целой структуры или в виде отдельных элементов структур.
Можно также создать набор процедур, который делал бы взаимодействие с базой данных более удобным. Такие процедуры являлись бы частью пользовательского интерфейса. Вот некоторые из них:
husband(X):–family(X,_,_). % X – ìóæ
vife(X):–family(_,X,_). % X – жена
child(X):–family(_,_,Children), % X – ребенок
member(X,Children).
exist(X):–husband(X); vife(X); child(X). % X – любой член семьи
dohod(mem(_,_,_,worker(_,D)),D). % D – доход работающего
dohod(mem(_,_,_,notwork),0). % 0 – доход неработающего
Этими процедурами можно воспользоваться, например, в следующих запросах к базе данных:
1) найти имена и фамилии всех людей из базы данных:
Goal exist(mem(Nam,Fam,_,_)).
2) Найти всех работающих жен:
Goal vife(mem(Nam,Fam,_,worker(_,_))).
3) Найти фамилии людей, чей доход меньше чем 8000:
Goal exist(Man), dohod(Man,D), D<8000.
21. Задача "Ханойская башня". Имеется три стержня А,В,С. На стержне А лежит N дисков пирамидой, сужающейся кверху. Надо переместить диски со стержня А на стержень C, используя промежуточный стержень B и соблюдая законы:
1) диски можно перемещать с одного стержня на другой по одному;
2) нельзя класть больший диск на меньший;
3) при переносе дисков с одного стержня на другой можно использовать промежуточный третий стержень, на котором диски должны находиться тоже только в виде пирамиды.
Если в программе использовать рекурсивную процедуру, то программа становится удивительно маленькой: два рекурсивных вызова процедуры и оператор вывода результатов перемещения дисков.
Собственно "перемещению" диска соответствует оператор вывода, указывающий, с какого стержня на какой переместить диск. Основным рабочим предикатом является рекурсивный предикат move. Базовое правило этой рекурсии: если диск один, то переместить его с левого стержня на правый. Иначе, переместить N-1 диск с левого диска на средний промежуточный, переместить один диск с левого стержня на правый и затем переместить N-1 диск со среднего стержня на правый, используя левый стержень как промежуточный.
domains
loc = right; middle; left
predicates
hanoi(integer)
move(integer, loc, loc, loc)
inform(loc, loc)
clauses
hanoi(N) :– move(N, left, middle, right). % Запуск программы
move(1, A, _, C) :– inform(A, C), !. % Переместить один диск
move(N, A, B, C) :– % Переместить N дисков
N1=N-1, move(N1, A, C, B),
inform(A, C), move(N1, B, A, C).
inform(Loc1, Loc2) :– write("\nMove a disk from ", Loc1, " to ", Loc2).
Goal hanoi(10). % Перемещаем 10 дисков