Управление вычислениями.

1. Основные средства управления.

2. Средства Prolog’a в программировании.

(1). Основными средствами управления процессом вычислений в Prolog являются стандартные предикаты fail (неуспех) и ! (отсечение). Назначение этих предикатов и методы их использования рассмотрим на примере программы

domains

st = student (fam, pr, oc)

fam, pr = symbol

num, oc = integer

g= gr (num, st)

predicates

Kurs_22 (g)

Если теперь после компиляции программы в качестве внешней цели ввести запрос: Kurs_22 (х) находит х решений, то в диалоговом окне будет выведена информация:

(1) X = gr (261, student(“Петров П.П.”,”тех.ср.”,5)).

X = gr (261, student(“Иванов И.И..”,”ОС”, 5)).

Т.е. будут найдены все варианты решений, т.к. в запросе не задано ограничений на значение переменной х.

Если теперь любой из этих запросов сделать внутренним, т.е. записать в разделе goal, откомпилировать и выполнить программу, то кроме сообщения

Press the SPACE for…

В диалоговом окне не будет результатов, т.к. мы не задали предикатов вывода значений результата внутреннего запроса. Изменим внутренний запрос

goal

Kurs_22(x), write (x)

Здесь для вывода значений переменной х после сопоставления используется системный предикат write(…). Результаты такого запроса будут помещены в диалоговое окно в виде (1). Т.е. будет найдено первое подходящее решение.

Если теперь не меняя запроса изменить порядок, предложенный в программе, например, поменять местами первое со вторым, то результат будет другим:

gr (261, student (“Иванов И.И..”,”ОС”,5)).

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

Один из них – использовать свойства Prolog выполнять поиск альтернативного решения. При неудачной попытке – применения текущего Prolog выполнит откат до ближайшей альтернативы. Восстанавливает первоначальные условия поиска и процесс начинается заново с найденной новой альтернативой.

Для организации таких вычислений в языке есть специальный предикат, который всегда завершается неуспехом и вызывает откат до ближайшей альтернативы (fail). Для целей перебора всех альтернативных фактов в примере и выводе их на экран, в состав первоначальной программы введём нульместный предикат show и правила вида:

Show: -kurs_22(x), write (x), fail.

Для этого в раздел predicates добавим строку show, в разделе clauses поместим строку:

Show: -kurs_22(x), write (x), fail.

Зададим так же внутреннюю цель вида

goal

show

В этом случае на экран будут выведены все f альтернативных решений – после нахождения первого, переменная х будут означена константой первого факта, полученное значение переменной х сопоставляется аргументу предиката Write (x), который выведет его на экран, после чего выполняется предикат fail, который завершается неуспехом и Prolog выполнит откат до ближайшего недетерминированного предиката (т.е. имеющего несколько вариантов правил), а в нашем случае предикат kurs_22(x), будет выбран второй факт, выполнено сопоставление и т.д. до тех пор, пока не будут перебраны все альтернативы.

Предписать Prolog выполнять откат можно не только с помощью предиката (fail). Любой неуспешно завершённый предикат вызывает откат до ближайшей альтернативы (стоящего от него левее в теле правила). Продемонстрируем это на нашем примере:

Пусть необходимо получить и вывести на экран информацию о студентах, пересдавших экзамен по дисциплине «Программирование». Изменим предикат Show:

show: -kurs_22(gr(x, student(Y, Z, K))).

Z = “Программирование”,

write (“Группа –”, X, “Студент –”, Y, “Оценка –”, K)

nl

fail

Тогда для внутреннего запроса:

goal

show

На экране будет выведено:

Группа – 261 Студент – Петров П.Р. Оценка – 5

Группа – 262 Студент – Жигорев С.И. Оценка – 3

Т.о., сравнение Z=”Программирование” выполняет двоякую роль: с одной стороны, это фильтр, который не допускает выполнение предиката WRITE(…), при неуспешном сравнении, а с другой стороны – вызывает из-за неуспешного сравнения откат до ближайшей альтернативы. При этом если бы не было предиката fail, то было бы получено только первое решение – fail обеспечивает перебор всех альтернатив. Предикат nl является стандартным, он выполняет переход на следующую строку при выводе информации на экран.

В Turbo Prolog имеются средства, с помощью которых можно заблокировать поиск с возвратом. Для этих целей служит специальный предикат, который называется отсечением (cut) и обозначается «!». Для демонстрации его использования в нашем примере добавим предикат отсечения в правило show:

show: -kurs_22(gr(x, student(Y, Z, K))).

Z = “Программирование”,!,

write (“Группа –”, X, “Студент –”, Y, “Оценка –”, K)

nl

fail

Тогда для внутреннего запроса:

goal

show

на экране будет выведена информация:

Группа – 261 Студент – Петров П.Р. Оценка – 5

В данном варианте после успешного сравнения Z = ”Программирование”, предикат ! прекращает поиск после формирования условия «неуспех» предикатом fail. Т.о., использование в правиле предиката отсечения означает, что в дальнейшем не будет производиться перебор других аргументов предикатов, использованных в этом правиле до знака отсечения, после формирования признака неуспеха любым из предикатов, стоящем в правиле правил предиката !.

Введём в правила ещё один предикат:

kurs_22(gr (A, student (B, C, D))),

который зависит от других переменных – это принципиально. Предикат show будет следующим:

show: -kurs_22(gr(X, student(Y,Z,K)))

Z = “Программирование”,!,

Kurs_22(gr (A, student (B, C, D))), D = 3, B = Z,

WRITE (“Группа - ”, A, “Студент - ”, B, “Оценка - ”, D),

После внутреннего запроса show, на экран будет выведена информация в виде:

Группа – 262 Студент – Жигорев С.И. Оценка – 3

Отметим, что часть правила после отсечения ! осуществляет полный перебор всех фактов программы, начиная с первого с помощью фильтра D = 3, B = Z, а при его выполнении – с помощью fail.

Другими словами, отсечение ограничивает распространение аргументов для подпора новых значений возврата (Бектринга) из-за неудачи. Отсечение применяется так же для ускорения вычислений путём отбрасывания избыточных ветвей вычислений.

Замечания:

1. Ранее были показаны отличия выполнения внутреннего (описанного в goal) и внешнего (вводимого через приглашение системы в диалоговом окне) запросов. Теперь мы можем сказать, что перебор всех альтернативных решений для внешнего запроса обеспечивается автоматическим присоединением к нему системой Turbo Prolog стандартного предиката fail.

2. Наличие в программе раздела goal позволяет после компиляции логической программы получить логический модуль программы и использовать его независимо от среды программирования Turbo Prolog.