Пролог берет свое начало от логики предикатов. В основу Пролога положены хорновские предложения исчисления предикатов (см. § 4.1.8). Программист определяет необходимые факты и правила, а Пролог использует дедуктивный вывод, реализуемый на основе принципа резолюции, для выдачи ответов на вопросы пользователя. Такой подход к решению задач представляет собой полную противоположность программированию на традиционных языках. В ходе программирования на Прологе программист не указывает “как решается задача”, а указывает “что решается”. Поэтому написание программы на Прологе сводится к составлению декларативных спецификаций предметной области, выраженных дизъюнктами Хорна.
Существуют различные версии языка Пролог: Quinteс-Prolog, MicroProlog, Arity-Prolog, Prolog2, Expert-Prolog, Turbo-Prolog, MProlog и др.
Первая эффективная реализация Пролога была создана в Эдинбургском университете в 1977 для ЭВМ DEC-10. Данная версия языка является фактическим стандартом. В дальнейшем изложении будем придерживаться синтаксиса этой версии языка Пролог.
Пролог содержит множество встроенных предикатов, обеспечивающих выполнение операций с файлами, построения графических изображений, воспроизведения звуков, управления цветом и т.п. Ограничимся рассмотрением минимального числа встроенных предикатов, необходимых для работы с базами знаний и выполнения операций ввода-вывода.
6.2. Основные понятия языка
Программа на Прологе есть совокупность утверждений, являющихся дизъюнктами Хорна. В конце утверждения ставится точка. Существуют два типа утверждений: факты и правила. Факт представляет собой истинное утверждение. Факт на Прологе представляется в виде предиката. Например, утверждение “Игорь – отец Святослава” записывается на Прологе в следующей форме:
отец(´Игорь´,´Святослав´).
Здесь отец – это имя предиката, а аргументы 'Игорь' и 'Святослав' представляют собой символьные константы. Символьные константы должны начинаться со строчной буквы или заключаться в одинарные кавычки. Имена предикатов могут начинаться с любой буквы. Однако следует помнить, что предикаты Отец( ) и отец( ) будут разными предикатами во многих реализациях Пролога.
В Прологе используется соглашение, позволяющее отличать имена конкретных объектов (констант) от имен переменных. Имя, начинающееся
Язык Пролог
311
с прописной буквы или символа подчеркивания, рассматривается как переменная. Так, X,Y, T34, X+Y, _a, _132 – это имена переменных.
Правило – представляет собой утверждение, которое истинно при некоторых условиях. Например, утверждение “X – дед Y” истинно при условии, что Х – это отец Z, а Z – это родитель Y. На Прологе это правило запишется в виде
дед(X,Y): – отец (X,Z), родитель(Z,Y).
Правило должно заканчиваться точкой. Правило состоит из заголовка (головы) и тела. Заголовок и тело соединяются знаком “: – ”, который соответствует импликации “ ”. Запятая, записанная в теле правила, соответствует логической связке “и”. Приведенное выше правило интерпретируется следующим образом: “если верно отец(X,Z) и родитель(Z,Y), то верно дед(X,Y)”. Заголовок правила представляет факт, для определения которого предназначено правило. В рассматриваемом случае – это дед(X,Y). Данный факт будет иметь место, если будут верными утверждения, образующие тело правила, которые называют условиями.
В теле правила можно использовать логические связки “или”, которые обозначаются точкой с запятой. Например,
родитель(X,Y): – отец(X,Y); мать(X,Y).
Иными словами, X является родителем Y, если Х – это отец или мать лица Y. В приведенных правилах использовались переменные X, Y, Z, каждое вхождение которых в правило соответствует одному и тому же объекту. Однако при повторном использовании правила этим переменным могут быть сопоставлены уже другие объекты.
Факты и правила образуют базу данных. Рассмотрим пример:
/*Факт: Иван – отец Сергея */ /* Факт: Иван – отец Анны */ /*Факт: Мария – мать Сергея */
/*Правило: О и М являются родителями ребенка Р, если О является отцом Р и М является мамой Р */
родители(О,М,Р ): – отец(О,Р), мать(М,Р).
Когда база данных создана, можно обращаться к ней с вопросами. Например: “Является ли Иван отцом Сергея?” Для этого необходимо ввести следующее целевое утверждение:
? – отец('Иван','Сергей').
312
Глава 6
Обращение с вопросом к пролог-системе инициирует процедуру поиска в базе данных. Пролог ищет факты, сопоставимые с фактом целевого утверждения. При этом выполняется процедура унификации (см. § 4.1.4). Два факта сопоставимы, если совпадают имена предикатов, и соответствующие аргументы попарно сопоставимы. В рассматриваемом случае Пролог находит в базе данных факт отец('Иван','Сергей'), сопоставимый с целевым утверждением. Обнаружив этот факт, Пролог система ответит Yes (да).
К рассмотренной базе данных можно обращаться и с другими вопросами. Например, ответом на вопрос
? – отец('Сергей','Иван').
будет No (нет), так как в базе данных нет факта, сопоставимого с вопросом. На вопрос
? – отец('Иван',P). / * Кто дети Ивана? */
пролог-система выдаст ответ Р='Сергей'. Если ввести с терминала знак “;”, то пролог-система продолжит поиск, и получит второе значение Р='Анна'. Если еще раз ввести точку с запятой, то пролог-система вернет значение No. Можно задать и более сложный вопрос: “Кто родители Сергея?”:
? – родители(О,М,'Сергей').
В результате получим
О='Иван'; М='Мария'; No.
В данном случае было использовано правило. При этом попытка доказательства целевого утверждения
родители(О,М,'Сергей')
была заменена доказательством двух новых подцелей отец(О,'Сергей') и мать(М,'Сергей'). В результате было выяснено, что первая подцель достижима, если О='Иван', вторая подцель достижима, если М='Мария'. Следовательно, целевое утверждение верно при указанных значениях переменных.
В общей форме правило можно записать следующим образом
Р: – Р1, Р2, …, Рn,
где Р,Р1,Р2, …,Рn – элементарные (атомарные) формулы. Атомарная формула имеет вид
Р(t1, t2,…, tn),
Язык Пролог
313
где Р – предикатный символ; t1, t2,…, tn – множество термов, являющихся аргументами атомарной формулы.
Терм может быть константой, переменной или составным термом
(структурой). Константы языка Пролог подразделяются на числа и атомы. Примеры числовых констант: -1, 176.5, 0.29е–3.Некоторые реализации Пролога не поддерживают работу с вещественными числами. Атомы языка Пролог представляют символьные константы, которые или начинаются строчной буквой, или заключаются в одинарные кавычки, или состоят из специальных символов. Примеры атомов:
сергей 'Сергей' x400
'Иван Петров' <-->
===>
Имена переменных в Прологе начинаются с заглавных букв или символа подчеркивания “_”. Областью действия переменной является утверждение. В пределах утверждения одно и то же имя принадлежит одной переменной. Два утверждения могут использовать одно имя переменной различным образом. Переменные, которым присвоены значения, называются конкретизированными. Существуют также анонимные переменные, то есть переменные без имени. Анонимные переменные обозначаются символом подчеркивания. Например, отец('Иван', _ ). Это означает, что нас не интересует, какие подстановки будут выполняться в анонимную переменную. Анонимные переменные используются в тех случаях, когда имя переменной несущественно. Вывести на печать значение анонимной переменной невозможно. Каждая анонимная переменная уникальна, т.е. отличается от всех других анонимных переменных в утверждении.
Константы и переменные образуют элементарные объекты языка Пролог. Все, что не может быть отнесено к переменной или константе, на-
зывается составным термом или структурой.
Структура (или составной терм) является объектом, состоящим из нескольких компонент. Структура состоит из атома, который называется функтором, и последовательности термов, которые рассматриваются в качестве компонент структуры. Компоненты структуры разделяются запятыми и заключаются в круглые скобки. Функтор записывается перед скобками. Например, следующая структура имеет функтор f и три компоненты:
f(T1,T2,T3).
314
Глава 6
Функтор f объединяет термы T1, T2, и T3 в структуру. Число компонент структуры называется арностью. Так, структура f имеет арность 3. Отметим, что атом можно рассматривать как структуру арности 0.
Структуры можно изображать в виде деревьев. Корнем дерева является функтор структуры, а ветви, выходящие из корня представляют собой компоненты. Введем иерархическую структуру, представляющую информацию о некотором сотруднике:
Структура сотрудник содержит вложенные подструктуры: имя, адрес, телефон. В свою очередь, подструктура адрес состоит из двух подструктур: улица и город. Данную структуру можно представить в виде дерева, изображенного на рисунке 6.1. Корень дерева называется главным функтором структуры.
Рисунок 6.1 – Представление структуры в виде дерева
Таким образом, все структурные объекты Пролога это деревья, представляемые в программе составными термами, компонентами которых являются другие термы. Следовательно, синтаксически все объекты данных в Прологе представляют собой термы. Например, введенные выше структуры f и сотрудник – это термы.
Одной из основных операций, выполняемых над термами в ходе доказательства целевого утверждения, является сопоставление. Два терма сопоставляются по следующим правилам:
а) если термы X и Y – константы, то они сопоставимы, только когда одинаковы;
Язык Пролог
315
б) если терм Х представлен константой или структурой, а терм Y – не конкретизированной переменной, то термы Х и Y сопоставимы, и Y принимает значение Х;
в) если термы Х и Y – структуры, то они сопоставимы, когда у них совпадают главные функторы и арность, а также сопоставимы соответствующие компоненты структуры.
Возможность сопоставления двух термов проверяется с помощью оператора “=”. Так, сопоставление
? – отец('Иван',P) = отец(О,'Сергей').
закончится успехом при О='Иван' и Р='Сергей'.
Пролог находит наиболее общий унификатор термов (НОУ). В качестве примера рассмотрим вопрос:
При достижении первой цели пролог-система выполнит следующие подстановки: Х=О, Р='Сергей'. Здесь можно унифицировать переменные Х и О бесконечным числом способов. Однако пролог-система находит наиболее общий унификатор Х=О. В этом случае переменные Х и О называют сцепленными. После достижения второй цели, значения переменных будут сле-
дующими Х='Иван', P='Сергей'.
При рассмотрении пролог-программы полезно выделять два уровня ее смысла: декларативный и процедурный. Декларативный смысл прологпрограммы связан с отношениями, объявленными (декларируемыми) в программе, он определяет, достижимо ли целевое утверждение, и при каких значениях переменных оно будет верным. Процедурный смысл определяет, как пролог-система обрабатывает отношения пролог-программы, каким образом пролог-система отвечает на вопросы.
Важным преимуществом языка Пролог является наличие встроенного механизма доказательства истинности целевых утверждений, основанного на принципе резолюции (см. §4.1.4). Поэтому программирование на Прологе в значительной степени сводится к декларации отношений предметной области, а не к определению алгоритмов выполнения тех или иных операций. Поиск решения в пролог-системах протекает в автоматическом режиме, использующем принцип резолюции и принцип возврата к альтернативным вариантам возможных решений. Наличие указанных встроенных механизмов позволяет программисту сосредоточиться больше на декларативном смысле программы и не отвлекаться на особенности вычислительного процесса. Считается, что такой декларативный подход делает программирование на Прологе более легким, чем на традиционных алгоритмических языках [53].
316
Глава 6
Вместе с тем программист не может полностью игнорировать особенности вычислительного процесса, если требуется обеспечить эффективную реализацию программ. Для более точного понимания процедурного смысла пролог-программы строят деревья вывода. Рассмотрим пример:
d(X,Y): – c(X, Y).
/*1*/
d(X,Y): – b(Y, X).
/*2*/
c(X,Y): – a(X), b(X, Y).
/*3*/
c(0,0).
/*4*/
a(a1).
/*5*/
a(a2).
/*6*/
a(a3).
/*7*/
b(a1,1).
/*8*/
b(a1,2).
/*9*/
b(a2,3).
/*10*/
? – d(X,Y).
/*11*/
Процесс доказательства целевого утверждения d(X, Y) можно представить в виде дерева вывода, изображенного на рисунке 6.2.
Рисунок 6.2 – Дерево вывода
Каждая ветвь дерева вывода описывает один шаг программы, а узел, находящийся в конце ветви, определяет то целевое утверждение (простое или сложное), которое должно быть доказано после определенного числа шагов выполнения. Корень дерева содержит исходное целевое утверждение. Ветви, идущие от корня, определяют последовательность шагов выполнения, с помощью которых может быть найдено решение для целевого
Язык Пролог
317
утверждения. В конце пути, представляющем успешно завершенную последовательность выполнения, фигурирует пустое условие, обозначаемое на рисунке квадратом. Существуют такие последовательности шагов выполнения, которые заканчиваются неудачей (fail).
Согласно определениям 1 и 2, вычисление d(X,Y) сводится либо к вычислению с(Х,Y), либо b(Y,X). Поэтому из вершины ? – d(X,Y) выходят две альтернативные ветви, соединяющие вершину ? – d(X,Y) с вершинами ? –
с(X,Y) и ? – b(X,Y). Вершины ? – с(X,Y) и ? – b(X,Y) выступают в качестве новых подцелей. Подцель ? – с(X,Y) достижима, если достижимы подцели а(X) и b(X,Y) (определение 3) или с(0,0). Доказательство истинности подцели ? – а(X), b(X,Y) предполагает проверку выполнимости условия а(Х), а затем и b(X,Y). Условие а(Х) выполнимо при следующих подстановках: Х=а1, Х=а2, Х=а3 (определения 5, 6, 7). Следовательно, данное условие порождает три варианта возможных продолжений дерева вывода. При Х=а1 прологсистема проверяет выполнимость условия ? – b(X,Y). Данное условие выполнимо при следующих подстановках Y=1 и Y=2 (определение 8, 9). Таким образом, вычисление b(а1,Y) порождает две ветви. Пролог-система строит сначала левую ветвь (рисунок 5.13) и выдает в качестве ответа на вопрос ? – d(X,Y) значения переменных Х=а1 и Y=1. Если пользователь введет с клавиатуры команду “;”, то пролог-система выполнит построение правой ветви условия b(а1,Y) и выведет на дисплей новые значения переменных Х=а1 и Y=2. Ввод с клавиатуры команды “;” заставляет прологсистему выполнить построения альтернативной ветви дерева вывода. При этом дерево строится по правилу сверху вниз и слева направо. Определения размещаются в узлах дерева в порядке их записи в программе (сверху вниз).
Очередной ввод команды “;” заставит пролог-систему выполнить возврат к точке выбора, в которой остались нереализованные варианты выполнения. При возврате происходит автоматическое стирание подстановок, которые были сделаны в переменные после соответствующей точки выбора. В рассматриваемом случае возврат произойдет к точке выбора различных вариантов реализации условия а(Х). Так как вариант Х=а1 уже опробован, пролог-система выберет подстановку Х=а2. В конечном итоге это приведет к ответу: Х=а2, Y=3. После очередного ввода команды “;” опять произойдет возврат и будет опробована ветвь Х=а3. В этом случае проверка выполнимости условия b(a3,Y) завершится неудачей (fail), так как в базе данных нет ни одного утверждения сопоставимого с b(a3,Y). Неудача автоматически заставит пролог-систему осуществить возврат к возможным точкам выбора вариантов выполнения тех или иных условий. Так как все варианты выполнения условия а(Х) уже опробованы, то пролог-система вернется к альтернативному варианту выполнения условия с(Х,Y) и выпол-
318
Глава 6
нит подстановки Х=0 и Y=0 (определение 4). После этого у пролог-системы останется в запасе ветвь, соответствующая определению 2.
Если будут опробованы все варианты этой ветви, и пользователь введет команду “;”, то пролог-система ответит “No”. В конкретном примере это означает, что больше нет вариантов доказательства целевого утверждения.
В заключение еще раз отметим, что пролог-программа содержит утверждения трех типов: факты, правила и вопросы. Факты представляют собой утверждения, которые являются всегда верными. Правила – это утверждения, истинность которых зависит от некоторых условий. Вопросы позволяют выяснить, какие утверждения являются истинными. Утверждения Пролога – это предложения Хорна, которые на Прологе записываются в виде головы и тела. При этом факт – это предложение, содержащее только голову. Вопросы содержат только тело. Правила имеют голову и тело.
Простые объекты Пролога – это атомы, числа, переменные. Структуры используются для представления сложных объектов, состоящих их нескольких компонент. Структуры образуются с помощью функторов и характеризуются именем и арностью. Структуры естественным образом отображаются в виде деревьев. Поэтому Пролог можно рассматривать как язык обработки деревьев [7].
Пролог программы имеют двойную семантику: декларативную и процедурную. Декларативная семантика касается отношений, определенных в программе. Процедурная семантика определяет порядок выполнения шагов программы. Точное понимание процедурой семантики является весьма важным для правильного выполнения программы.
6.3. Операторы
Выше рассмотрены основные объекты пролог-программы, среди которых были введены структуры. Структура состоит из термов, которые называются компонентами, и функтора. Компоненты структуры записываются в круглых скобках и разделяются запятыми, главный функтор представляется в виде атома, который записывается перед списком компонент. Например, +(1, 2) или +(1, -(7, 2)). Во втором примере компонентом структуры с главным функтором, обозначенным знаком “+”, является структура –(7,
2).
Возможна более удобная операторная запись структур, арность которых равна одному или двум. Для этого необходимо объявить главный функтор структуры одноместным или двуместным оператором. При этом компоненты структуры записываются как аргументы оператора.
Язык Пролог
319
Так, если “+” и “–”объявить операторами, то структуры +(1, 2) и +(1, -(7, 2)) можно записать в более удобной форме арифметических выражений:
1+2. 1+(7-2).
Программист может определить новые операторы в программе с помощью директивы
Здесь <приоритет> – аргумент, определяющий приоритетный номер оператора. Приоритет задается целым числом и обычно находится в пределах от 1 до 1200 (зависит от реализации языка). Чем выше приоритет оператора, тем меньше его приоритетный номер. Аргумент <спецификатор> определяет тип оператора и его ассоциативность. Различают три типа операторов: инфиксные (оператор располагается между двумя своими аргументами, например Х+1), префиксные (оператор располагается перед единственным аргументом, например –1), постфиксные (оператор располагается после единственного аргумента, например Х+). Ассоциативность определяет порядок интерпретации выражения, в котором встречается оператор. Применяют следующие виды спецификаторов:
–инфиксные операторы: xfx, yfx, xfy;
–префиксные операторы: fx, fy;
–постфиксные операторы: xf, yf.
Вэтой форме записи спецификаторов приняты следующие соглаше-
ния:
f – обозначает оператор, объявляемый с помощью директивы ор;
x, y – аргументы оператора, которые могут быть простыми или структурными.
Если аргумент является простым или заключен в круглые скобки, то его приоритет равен нулю. Если аргумент структурный, то его приоритет равен приоритету его главного функтора. В записи спецификаторов x обозначает аргумент, приоритет которого выше, чем приоритет оператора f, а y – аргумент, приоритет которого выше или равен приоритету оператора f.
Пролог имеет ряд встроенных операторов, некоторые из которых перечислены в таблице 6.1. Если оператор объявлен со спецификатором yfx, то он является левоассоциативным. Например, выражение a*b*c интерпретируется как (a*b)*c, а не как a*(b*c). Действительно, во втором случае приоритет структуры b*c не выше, чем приоритет оператора “ * ”. Это противоречит объявлению оператора “ * ” со спецификатором yfx. Поэтому верной является первая интерпретация.
