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

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

Структура данных в Турбо-Прологе задается на составной области определения (третий способ указания Domains).

Рассмотрим ряд примеров с использованием структур.

1.База данных "Семья". Каждая семья состоит, с точки зрения логики, из трех объектов: мужа, жены и детей. Поскольку количество детей в разных семьях может быть разным, то их целесообразно представить в виде списка, состоящего из произвольного числа элементов. Каждого члена семьи в свою очередь можно представить структурой, состоящей из четырех компонент: имени, фамилии, даты рождения и работы. Информация о работе - это либо "не работает", либо указания кода работы и оклада.

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

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)),

[]). %нет детей у них

. . .

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

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.

Примеры.

12.6.1 Рассмотрим пример программы и проанализируем понятие отката на примере данных о спортивных увлечениях, содержащей следующие факты:

plays(tom,football) /* Том играет в американский футбол*/

plays(john,soccer) /*Джон играет в европейский футбол*/

plays(john,volleyball) /* Джон играет в волейбол*/

plays(tom,basketball) /* Том играет в баскетбол*/

plays(tom,volleyball) /* Том играет в волейбол */

plays(john,baseball) /* Джон играет в бейсбол*/

Задача программы определить в какую игру одновременно играют Джон и Том. Утверждение цели следующее:

plays(john,G),plays(tom,G).

Заметьте, что эта цель есть связка двух подцелей. Каждая подцель содержит переменную G. Задача заключается в нахождении значения для G, удовлетворяющего обеим подцелям. Чтобы вычислить первую подцель plays(john,G), Турбо-Пролог ищет в базе данных сопоставимое утверждение.

Первый объект утверждения lays(john,soccer) сопоставим с первым объектом первой подцели, так что подцель успешно вычисляется и переменная G получает значение soccer. Существуют другие утверждения для plays, которые могут быть использованы для вычисления этой же подцели. Поэтому Турбо-Пролог должен сохранить след этих утверждений на случай неуспешного вычисления второй подцели со значением G равным soccer. Для этого внутренние унификационные подпрограммы устанавливают указатель отката на точку, с которой могут быть продолжены усилия по вычислению первой подцели.

Теперь Турбо-Пролог пытается вычислить вторую подцель. Так как G имеет значение soccer, то эта подцель есть plays(tom,soccer). Турбо-Пролог просматривает базу данных в поиске утверждения, сопоставимого с этой подцелью. Сопоставимых утверждений нет, поэтому подцель неуспешна.

Так как вторая подцель вычислена неуспешно, то Турбо-Пролог вновь должен начать просмотр с первой подцели. После того, как попытка вычислить вторую подцель оказалась неуспешной, переменная G освобождается и Турбо-Пролог снова начинает поиск утверждения для вычисления подцели plays(john,G).

Если бы цель в этом примере была внутренней, то процесс вычисления остановился бы после первого ее успешного вычисления. Однако цель здесь внешняя, поэтому процесс повторяется до тех пор, пока не будут найдены все успешные способы вычисления цели.

Но информация, содержащаяся в данных утверждениях, дает только одно допустимое значение для G, которое удовлетворяет обеим подцелям, т.е. результат вычисления подцели есть G=volleyball.

12.6.2Рассмотрим пример программы использования метода ОО.

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

Domains

person = symbol

Predicates

child(person)

show_some_of_them

make_cut(person)

Goal

write("Мальчики и девочки"),

nl, nl,

show_some_of_them

Clauses

child("Tom ").

child("Beth ").

child("Jeff ").

child("Sarah ").

child("Larry ").

child("Peter ").

child("Diana ").

child("Judy ").

child("Sandy ").

show_some_of_them :-

child(Name),

write(" ", Name), nl,

make_cut(Name),!.

make_cut(Name) :-

Name="Diana".

Предположим, что необходимо выдать список имен до имени Diana включительно. Предикат cut выполнит отсечение в указанном месте. Предикат fail используется для продолжения откатов и доступа к последовательности имен базы данных до элемента с именем Diana.

Таким образом, поставленную задачу выполняет соответствующая комбинация предикатов cut и fail. Эта комбинация называется методом отката и отсечения (ОО). Программа, формирующая список имен детей демонстрирует этот метод. В программе об именах предикатом базы данных является child(person).

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

show_them_all :-

child(Name),

write(" ", Name), nl,

fail.

Оно основано на методе ОПН. При этом для того, что бы использовать предикат cut, необходимо определить некоторое условие, которое может быть и простым, как в нашем примере, и очень сложным. В данном случае достаточным является условие Name=Diana. Правило, определяющее, это условие имеет вид:

make_cut(Name) :-

Name="Diana".

Это правило с последующим предикатом cut (!) образует правило make_cut (сделать отсечение). Теперь выполнение программы будет неуспешным, а откаты будут повторяться до тех пор, пока Name не окажется равным Diana. В этот момент результат выполнения правила make_cut будет успешным, что в свою очередь, вызовет выполнение предиката cut. Таким образом, комбинируя правила отсечения с методом ОПН, можно получить ОО-правило:

show_some_of_them :-

child(Name),

write(" ", Name), nl,

make_cut(Name),!.

make_cut(Name) :-

Name="Diana".

Вы можете изменить выдачу программы, изменив имя объекта в условии отсечения. Например, Nameѕth, выдает список имен до имени Beth включительно. Этот способ использования ОО-метода называется методом ранжированного отсечения.

12.6.3Рассмотрим пример программы использования метода ОПР.

Метод обобщенного правила рекурсии (ОПР) проиллюстрируем на примере программы генерации ряда чисел.

write_number(8).

write_number(Number) :-

Number < 8,

write(Number), nl,

Next_Number = Number + 1,

write_number(Next_number).

Программа начинается с попытки вычислить подцель write_number(1). Сначала программа сопоставляет подцель с первым правилом write_number(8). Так как 1 не равно 8, то сопоставление неуспешно.

Программа вновь пытается сопоставить подцель, но уже с головой правила write_number(Number). На этот раз сопоставление успешно вследствие того, что переменной Number присвоено значение 1. Программа сравнивает это значение с 8; это условие выхода. Так как 1 меньше 8, то подправило успешно. Следующий предикат выдает значение, присвоенное Number. Переменная Next_Number получает значение 2, а значение Number увеличивается 1.

12.6.4Использования рекурсии.

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

Нижеприведенная программа использует правило рекурсии для вычисления суммы ряда целых чисел от 1 до 7:

S(7) = 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28 или

S(7) = 7 + 6 + 5 + 4 + 3 + 2 + 1 = 28

Правило рекурсии выполняет вычисления по обычной схеме сложения:

1 Начальное значение

+ 2 Следующее значение

3 Частичная сумма

+ 3 Следующее значение

6 Частичная сумма….

...

Тогда часть программы, использующая правило рекурсии будет иметь вид:

sum_series(1,1). /* сумма ряда */

sum_series(Number,Sum) :-

Number > 0,

Next_number = Number - 1,

sum_series(Next_number, Partial_Sum),

Sum = Number + Partial_Sum.

Данное правило имеет 4 компоненты и одно дополнительное нерекурсивное правило. Здесь последняя компонента правила рекурсии - это правило Sum с Partial_Sum (частичная сумма) в качестве переменной. Это правило не может быть выполнено до тех пор, пока Partial_Sum не получит некоторого значения.

А сама программа использования рекурсивного предиката для нахождения суммы S(N) ряда, где N - положительное целое число, при N=7 будет иметь вид:

Domains

number, sum = integer

Predicates

sum_series(number, sum)

Goal

sum_series(7,Sum),

write("Сумма ряда:"),nl,nl,

write(" S(7) = ", Sum), nl.

Clauses

sum_series(1,1). /* сумма ряда */

sum_series(Number,Sum) :-

Number > 0,

Next_number = Number - 1,

sum_series(Next_number, Partial_Sum),

Sum = Number + Partial_Sum.

Программа Сумма ряда 1 начинается с попытки выполнить подцель sum_series(7,Sum). Сначала программа пытается сопоставить подцель с подправилом sum_series(1,1). Сопоставление неудачно. Затем она пытается сопоставить подцель с sum_series(Number,Sum).

На этот раз сопоставление завершается успешно с присвоением переменной Number значения 7. Затем программа сравнивает значение Number, которое равно 7, с 0, т.е. проверяется условие выхода. Так как 7 больше 0, то сопоставление успешно, программа переходит к следующему подправилу.

Для этого подправила переменной Next_number присвоено значение 6, т.е. значение Number - 1. Затем правило вызывает само себя в виде sum_series(6,Partial_Sum). Следующим подправилом является правило Sum, содержащее свободную переменную Partial_Sum. Так как только что был вызван рекурсивный процесс, то правило Sum не может быть вызвано.

Теперь программа пытается сопоставить неизменяемое правило sum_series(1,1) с sum_series(6,Partial_Sum). Процесс сопоставления неуспешен, поскольку несопоставим ни один из параметров. В результате программа переходит к следующему правилу с головой sum_series(Number,Sum), присваивая переменной Number значение 6.

Этот циклический процесс сопоставления продолжается до тех пор, пока не будет получено sum_series(1,Partial_Sum). Теперь это правило сопоставляется с sum_series(1,1), а Partial_Sum приписывается значение 1. При сопоставлении правила с головой правила переменная Sum получает значение 1. Так как сопоставление продолжается дальше, то Next_number получает значение 0 (1-1). При следующем цикле сопоставления переменная Number получает значение 0. Во время сопоставления с условием выхода правило оказывается неуспешным, и сопоставление "прыгает" к правилу Sum.

Во время процесса сопоставления переменная Partial_Sum была свободна, а программа запоминала значения Number для последующего использования. Но это правило продолжает означивать переменную Sum, присваивая ей последовательно значения 1, 3, 6, 10, 15, 21 и 28. Конечное значение Sum есть 28.

Примером рекурсивных вычислений является известный алгоритм вычисления факториала. Hа Прологе эта программа может иметь такой вид:

Domains

N,F=real

Predicates

factorial(N,F)

Clauses

factorial(1,1).

factorial(N,R):- N>0, N1=N-1,

factorial(N1,R1), R=R1*N.

Goal

factorial(8,F),write(F).

При каждом вызове дизъюнкта factorial генерируются новые переменные, которые действуют всегда только на своем уровне вложенности, пока не встретится условие прекращения вычислений. Только после этого на обратном пути прохождения рекурсии определяются результаты, которые передаются вверх.