Пролог с математической точки зрения

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

Для примера рассмотрим известный силлогизм Аристотеля:

Все люди смертны. Сократ-человек. Следовательно, Сократ - смертен

Более формально:

(Все люди смертны = Для любого X: X - человек => X смертен)

"Х: Х - человек ÞХ – смертен

Сократ - человек

Сократ смертен

На Прологе это будет выглядеть так:

смертен(X):- человек(X).

человек(сократ).

?- смертен(сократ)

Да

ФОРМАЛИЗМ ЯЗЫКА ПРОЛОГ

Итак, подытожим вышеизложенное. С формальной точки зрения Пролог-программа состоит из предложений. Каждое предложение заканчивается точкой. Предложения Пролога состоят из головы и тела. Тело – список целей, разделенных запятыми. Запятые обозначают операцию конъюнкции.

Предложения Пролога бывают трех типов: факты, правила и вопросы.

Факты содержат утверждения, которые всегда истинны. Факт – это предложение, у которого тело пустое.

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

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

 

ПЕРЕМЕННЫЕ

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

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

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

 

МЕХАНИЗМ ПОИСКА РЕШЕНИЯ

Каким же образом работает система? Когда задается вопрос, интерпретатор Пролога начинает последовательно проверять (доказывать) истинность всех составляющих его коньюнктов. Проверяя очередной коньюнкт, система начинает просмотр имеющейся базы данных и правил. С каждым из выбираемых фактов и правил Пролог сначала пытается сопоставить доказываемое утверждение.

Сопоставление термов. Все объекты данных в Прологе синтаксически представляют собой термы. Термы сопоставимы, если:

они идентичны;

можно конкретизировать переменные терма таким образом, чтобы они стали идентичными.

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

 

РЕКУРСИВНЫЕ ПРАВИЛА

В Прологе нет циклов. Все итерационные процедуры осуществляются с помощью рекурсии. Кроме того, рекурсия играет, естественно, и самостоятельную роль. Например, можно определить отношение "предок" (предок в самом общем смысле) следующим образом:

предок(X,Z):- родитель(X,Z).

предок(X,Z):- родитель(X,Y), предок(Y,Z).

Повторение. Организовать циклические вычисления можно с помощью простого предиката repeat:

repeat.

repeat:- repeat.

Первое правило всегда истинно. Оно необходимо для создания точки возврата, когда сработает рекурсивный repeat. Следовательно, нам достаточно заставить систему перейти к альтернативному варианту, и мы тогда получим бесконечный цикл. Например, предикат echo будет запрашивать пользователя ввод строки, выводить ее на экран. И продолжаться это будет до тех пор, пока пользователь не введет строку " quit ":

echo:-     repeat,

write("Введите строку (quit-выход)"),

readln(S),

S=" quit".

Дело в том, что в последней строке происходит сравнение введенной строки со строкой " quit ". Если строки не совпадают, то система вернется к предыдущей альтернативной точке. Таковой является предикат repeat (недаром их у нас два варианта). Система пробует очередной вариант его выполнения и тем самым попадает в бесконечную рекурсию – в бесконечный цикл. А вот если строки совпадут, то тогда выполнение предиката echo будет считаться успешным.

Приведем еще один пример применения рекурсивного правила. Следующий предикат вычисляет сумму ряда:

sum(1,1).

sum(N,Sum):-

N>0,

Next = N-1,

sum(Next,Sum2),

sum = N+Sum2.

 

СПИСКИ

Очень важной структурой в Прологе является список – некий аналог массива. Все списки однородные, т.е. состоят из элементов одного типа – только чисел, только строк и т.п.

Очень характерно, как определяет списки сам Пролог. В Прологе список – это структура, состоящая из головы и хвоста. Голова – это один элемент. Хвост – это список. Список может и не содержать элементов. Тогда он называется пустым списком. Правила определения списка могут выглядеть так:

 

Список ® []

Список ® Голова, Хвост

Голова ® элемент

Хвост ® Список

Список задается перечислением его элементов, заключенным в квадратные скобки. Разделение списка на голову и хвост происходит указанием специального разделителя – символа '|'.

Примеры списков:

[1,3,8,1,6], [a, b, ec ], ["абв", "где", "жз"]

 

При этом в списке [1,3,8,1,6] голова – это элемент 1, а хвост – это список [3,8,1,6]:

[ 1 |    3, 8, 1, 6 ]

^{голова                хвост}

Знание того, как определяется список в Прологе, позволяет понять, как пишутся предикаты для работы с ними. Например, предикат, распечатывающий список, может выглядеть так:

print_list([]):-!.

print_list([H|Tail]):-

write(H),

print_list (Tail).

Другим примером может служить замечательный предикат append. Это – удивительный предикат. Он столь же прост, сколько и универсален. Если разобраться, как он работает, то можно считать, что вы как минимум наполовину знаете устройство Пролога. Выглядит он весьма просто:

append([],L,L).

append([H|A],B,[H|C]):- append(A,B,C).

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

 

goal

s([1,2,3,4]).

clauses

 

append([],L,L).

append([H|A],B,[H|C]):- append(A,B,C).

 

print_list([]):-!.

print_list([H|Tail]):- write(H), print_list (Tail).

 

s(S):- append(L1,L2,S),

print_list(L1),

print_list(L2),

fail.

s(_):-!.

 

О том, что такое! и fail, будет сказано ниже.

УПРАВЛЕНИЕ ПОИСКОМ

Откат после неудачи. Предикат fail всегда заканчивается неудачей. Вместо него можно было бы использовать какое-нибудь априорно ложное утверждение (например, 1=2), однако с ним программа выглядит элегантнее. Следующий предикат выводит на экран все имеющиеся имена.

show_all:-

name(X),

fail.

name("Петров ").

name("Иванов").

name("Сидоров").

Если бы не fail, то выполнение предиката закончилось бы выводом одного-единственного имени. Правило выдачи на экран “эха”, использующее уже знакомый repeat, но уже в бесконечном цикле, выглядит так:

echo:-

repeat,

readln(S),

write(S),

fail.

Здесь fail служит для того, чтобы реализовать откат после неудачи. Еще раз отметим, что откат происходит к repeat, т.к. в нем существует как минимум две возможности реализации repeat. Это правило порождает бесконечное число точек возврата.

 

Отсечение. Иногда бывает необходимо ограничить круг поиска, т.е. заставить систему "забыть" о существовании альтернативных вариантов – точек возврата. Фактически речь идет о задаче отсечения ненужных результатов. Этой цели служит предикат cut или '!' (в Прологе вообще любят все сокращать – вместо and – запятая, вместо cut – восклицательный знак, вместо or – точка с запятой ';'). Пользоваться этим предикатом нужно очень осторожно. А лучше стараться не пользоваться вовсе (во всяком случае без крайней необходимости). Этот предикат всегда истинен. Он отсекает все точки возврата, находящиеся до него (иными словами, этот предикат очищает стек точек возвратов).

 

Примеры использования предиката cut:

show_somebody:-

name(X),

make_cut(X),

!.

make_cut(X):- X="anon ymous".

echo:-

repeat,

readln(S),

write(S),

check(X),!.

check(S):- S="stop".

check(_):- fail.

БИБЛИОГРАФИЧЕСКИЙ СПИСОК

Донован Дж. Системное программирование /Пер.с англ. -М.:Мир, 1975. –540с.

Грис Д. Конструирование компиляторов для цифровых вычислительных машин /Пер.с англ. -М.:Мир, 1975.

Ахо А., Ульман Дж. Теория синтаксического анализа, перевода и компиляции. В 2-х томах. Том 1. М.:Мир, 1978. -616с.

Керниган Б.В., Пайк Р. UNIX - универсальная среда программирования /Пер.с англ. Березко, Иващенко. Под ред. М.И.Белякова -М.:"Финансы и статистика", 1992. -304 с.

Р.Хантер. Проектирование и конструирование компиляторов. -М.:Финансы и статистика, 1984.