Материал: Волченков Логическое программирование язык пролог 2015

Переменная Y остаётся свободной – это означает, что она связана квантором всеобщности.

Есть и другой ответ – его тоже можно найти с помощью той же программы: «У каждого человека есть и другой дедушка – это отец матери». Для этого достаточно «попросить» Пролог это сделать с помощью знака «;»:

| ?- дедушка(X, Y).

X= отец(отец(Y)) ,

Y= _ ;

X= отец(мать(Y)) ,

Y= _

| ?-

Ввод знака «;» после получения первого ответа на запрос означает, что мы вынуждаем Пролог совершить так называемый «возврат» к тому месту только что сработавшей программы, где был возможен иной путь продолжения её работы. В частности, Пролог уже на первом шаге мог бы вместо первого правила кода 2.2 взять второе правило. Логический вывод пошёл бы другим путём и привел бы к альтернативному результату, что и происходит в действительности.

Как было отмечено ещё в 1-й лекции, это свойство логического вывода свойственно стратегии линейной резолюции вообще и Прологу в частности. Для понятия «автоматический возврат» в логическом программировании используется также термин backtracking.

Следует отметить, что в данном примере возврат не автоматический, а принудительный: он инициируется пользователем нажатием клавиши со знаком «;». Забегая вперёд, заметим, что вместо этого все альтернативные решения задачи можно получить с помощью встроенного (системного) предиката Пролога setof/3 (или bagof/3).

Например:

| ?- setof(X, дедушка(X, Y), L).

X = _ ,

Y = _ ,

L = [отец(мать(Y)),отец(отец(Y))]

36

| ?- bagof(X, дедушка(X, Y), L).

X = _ ,

Y = _ ,

L = [отец(отец(Y)),отец(мать(Y))]

Предикат setof отличается от предиката bagof тем, что убирает из списка решений повторяющиеся решения (дубликаты) и выстраивает решения в лексикографическом (алфавитном) порядке.

На следующем примере демонстрируется графическая интерпретация такого рода возврата.

Пример 2.7. Рассмотрим пример 1.7 из 1-й лекции «(1) Если всем людям свойственно ошибаться, (2) если Сократ – грек и (3) если все греки – люди, то (4) Сократу свойственно ошибаться». (Утверждения 1 – 3 аксиомы, а утверждение 4 – теорема.)

Программа на Прологе для решения задачи примера 1.7 выгля-

дела бы так:

Код 2.3

ошибается(X) :– человек(X). грек(Сократ).

человек(X) :– грек(X). ?– ошибается(Сократ).

Немного усложним задачу. Иначе сформулируем аксиомы:

(1)все греки люди, (2) все римляне люди,

(3)Буцефал – лошадь, (4) Сократ – грек,

(5)Платон – грек, (6) все лошади смертны,

(7)все люди смертны.

Ипо-другому сформулируем теорему:

(8)«Найти смертного грека». Или, говоря иначе: «Существует ли смертный грек и, если это так, то кто он?»

Рассмотрим Пролог-программу:

Код 2.4

человек(X) :– грек(X). человек(X) :– римлянин(X).

лошадь(Буцефал). грек(Сократ). грек(Платон).

37

смертен(X) :– лошадь(X). смертен(X) :– человек(X).

?– смертен(X), грек(X).

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

? – грек(Сократ).

Рис. 2.5. Пример логического вывода для цели ?– смертен(X), грек(X).

«Квадратиком» на рис. 2.5 обозначен успех логического вывода. Побочным эффектом является «означивание» переменной:

X=Сократ.

На рисунке стрелки, ведущие вверх из «тупика», демонстрируют «откат» (автоматический возврат).

38

Пример 2.8. Рассмотрим ту же базу данных Пролога, что и в примере 2.7. Но запрос к базе данных пусть будет другим: «Найти смертного римлянина» (а не грека!).

Автор обращается к слушателям (или читателям) с предложением самостоятельно построить граф логического вывода для этого запроса. Логический вывод должен дать на данный запрос отрицательный ответ: «Смертного римлянина не существует». Можно ли трактовать такой ответ, как свидетельство некоего «изъяна» логического программирования? Ведь отсутствие информации не есть отрицательная информация! Но это не «изъян», а принципиальная особенность всякой системы «с ограниченным миром», коей, в частности, является любая программа на Прологе в совокупности с интерпретирующей её Пролог-системой.

Добавление к базе данных программы примера 2.7 единственного утверждения римлянин(Цезарь). приведёт к появлению вместо отрицательного ответа на запрос ?– смертен(X), римлянин(X). («Существует ли смертный римлянин?») положительного ответа: yes, X=Цезарь. («Да, и этим римлянином является Цезарь»).

39

Лекция 3

Основы программирования на Прологе

В данной и следующей лекциях обсуждаются основные механизмы и приёмы программирования на Прологе, если рассматривать его не только как декларативный язык логического программирования, но и как универсальный процедурный язык программирования. Прежде всего, перечисляются встроенные предикаты Пролога – по существу, встроенные булевские процедуры, если пользоваться аналогией с традиционными алгоритмическими языками. Рассматриваются различные категории встроенных предика-

тов: 1) для арифметических вычислений, 2) для обеспечения ввода и вывода данных, 3) для управления процессом поиска ответов на запросы, 4) для преобразования структур данных, 5) для проверки типов термов. Кроме встроенных предикатов, рассматриваются примеры определений пользовательских предикатов, которые могут понадобиться при решении задач самых разных классов.

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

1.Встроенные предикаты Пролога для «арифметических» вычислений

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

40