1.5 Задание на лабораторную работу

Необходимо описать предметную область «родственные отношения». Для этого задайте в качестве фактов следующие отношения между объектами предметной области:

• parents(X, Y) – X является родителем Y;

• man(X) – X мужчина;

• woman(X) –X женщина.

Например,

parents(tom, ellen).

man(tom).

woman(ellen).

Определите в качестве правил (используя отношения parents, man, woman) следующие отношения:

• sister(X, Y) – X является сестройY;

• brother(X, Y) – X является братом Y;

• father(X, Y) – X является отцом Y;

• mother(X, Y) – X является матерью Y;

• grandfather(X, Y) – X является дедушкой Y;

• grandmother(X, Y) – X является бабушкой Y.

1.6 Контрольные вопросы

1. Назовите основные программные секции программы на VisualProlog.

2. Назовите основные принципы поиска с возвратом.

3. Сформулируйте алгоритм унификации.

4. Дайте понятие переменной в языке Пролог.

5. Определите отношение aunt(X, Y) – «X является тетей Y» через отношения parents и sister.

Лабораторная работа №2 Рекурсия и итерация в языке Пролог

2.1 Цель работы

Изучить возможности использования рекурсивных и итерационных алгоритмов в языке Пролог.

2.2 Теоретические сведения

Рекурсия и итерация

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

Управление поиском с возвратом

Для реализации повторных вычислений в традиционных языках существует ряд операторов (for, while, repeat). Однако в языке Пролог отсутствуют их аналоги. Пролог позволяет только два вида повторений: возврат, в котором осуществляется поиск нескольких решений в одном запросе и рекурсию, в которой процедура вызывает сама себя. Для управления поиском с возвратом используются два встроенных предиката:

1. fail (неудача) – осуществляет вынужденное неудачное завершение выполнение предиката и, таким образом, инициирует процесс возврата.

2. Cut или ! (отсечение) – используется для предотвращения поиска с возвратом.

Предикат repeat обеспечивает дополнительную возможность для порождения множественных решений в процессе возврата. Этот предикат можно определить следующим образом:

repeat.

repeat :- repeat.

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

В качестве примера использования предиката repeat рассмотрим следующую программу:

predicates

repat

typewriter

clauses

repeat.

repat :- repeat.

typewriter :- repeat, readchar(C), write(C),

char_int(C, 13).

В этой программе вводимые пользователями символы (предикат readchar) отображаются на экране (предикат write) до тех пор, пока пользователь не нажмет клавишу enter. Для порождения новых решений в процессе возврата (т.е. для обеспечения ввода пользователем новых символов до нажатия клавиши enter) используется предикат repeat.