Использование структур

Структуры данных являются мощным средством программирования в Прологе. Они позволяют организовать различные фрагменты информации в единые логические единицы, что дает возможность использовать информацию, не думая о деталях ее действительного представления. Широкое применение структур – это также средство представления структурных объектов (баз данных) и управления ими. Использование структур делает Пролог и естественным языком запросов к базе данных.

Структура данных в Прологе задается на составной области определения (третий способ указания 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 дисков