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

шаге, а на роль 2-го участника – дизъюнкт, полученный из какой-

либо аксиомы.

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

человек(Сократ) грек(Y) человек(Y)

nil

Рис. 1.3. Графическое представление стратегии линейной резолюции

На рис. 1.3 представлен процесс, который идёт «без препятствий», а результат представляется в виде линейного «дерева».

Но не всегда бывает всё так «удачно»: часто на определённом шаге доказательства нельзя найти аксиому – подходящую кандидатуру на роль «правой ветки» очередного «куста». При этом говорят, что процесс доказательства «зашёл в тупик».

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

На рис. 1.4 представлен процесс, который содержит выход из «тупика» и альтернативный выбор другой аксиомы (дизъюнкта D8 вместо дизъюнкта D4) для применения правила резолюции.

21

7. Язык Пролог

Место и время появления на свет языка Пролог: Марсель (Франция), 1970-е годы. Автором считается А. Колмероэр [2, 3].

В Прологе реализованы описанные выше принципы: представление утверждений в виде дизъюнктов Хорна и стратегия линейной резолюции.

Таким образом, в Прологе мы имеем дело не с «чистым» исчислением предикатов первого порядка, а с ограниченной его «частью». Но это является достоинством, а не недостатком Пролога. Указанное ограничение сделало Пролог мощным и, главное, удобным для широкого пользователя средством программирования, с помощью которого стало возможным быстрое и эффективное решение разнообразных задач синтаксического анализа, распознавания образов, искусственного интеллекта. Более того, в Пролог для удобства программирования и повышения эффективности решения задач были введены средства, которые ничего общего с логическим программированием не имеют. К ним относятся разнообразные операторы ввода-вывода данных, преобразования структур данных,

22

управления процессом логического вывода и т.д. Есть в нём даже средства, «слегка» выводящие этот язык за пределы логики первого порядка, использующие, например, предикат call(P), аргумент которого не терм, а ППФ. Это, разумеется, не позволяет говорить о Прологе как о логической системе «первого порядка».

Иглавное, на взгляд автора, отличие Пролога от ЯИП-1П заключается в следующем. В Прологе конъюнкция предикатов (атомарных формул), входящих в состав утверждений Хорна, конъюнкцией, по существу, не является! Дело в том, что в Прологе имеет значение порядок записи «логических сомножителей», чего, разумеется, не должно быть в «чистом» языке исчисления предика-

тов. Это связано с так называемой процедурной семантикой Пролога (в отличие от декларативной семантики ЯИП-1П). Эта семантика предполагает рассмотрение отдельных атомарных формул (предикатов) как процедур, зачастую имеющих входные и выходные параметры. Причём, может быть так (и, чаще всего, так и бывает), что выходной параметр одной процедуры является входным для другой. И о какой коммутативности «логического умножения» можно при этом говорить? Но именно процедурная семантика позволяет рассматривать Пролог как универсальный язык программирования, с помощью которого, в принципе, можно решить любую задачу, решаемую с помощью таких традиционных языков программирования, как Паскаль, Си, Бейсик.

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

илогических свойств той проблемной области, в которой решается данная задача. Сокращённо этот принцип формулируется так: «Не как, а что».

Рассмотрим особенности нотации Пролога, сравнив записи утверждений Хорна на Прологе и на ЯИП-1П. И поясним характерную для Пролога терминологию. Утверждения (дизъюнкты) ЯИП-

23

1П и соответствующие им утверждения Пролога (так называемые клозы) представлены в табл. 1.1.

Связка «если»

Из таблицы видно, что вместо импликации в Прологе используется инверсная запись: вместо связки «логически следует» ( ) используется связка «если» (двоеточие и тире). Создатели нотации Пролога справедливо полагали, что такая запись логических формул более свойственна стилю человеческого мышления. 40-летний опыт использования Пролога доказал их правоту.

Терм в Прологе Терм в Прологе понимается шире, чем в исчислении предика-

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

В Прологе терм – это единственная (с точки зрения синтаксиса) структура данных!

Особо следует выделить термы, которые семантически интерпретируются как отношения в проблемной области. Эти термы называются предикатами. (В терминологии ЯИП-1П это атомарные формулы). Синтаксически предикат Пролога определяется спецификацией, включающей имя предиката (предикатную букву в терминологии ЯИП-1П) и арность предиката (целое положительное число). Записывается спецификация так: p/n.

24

Лекция 2

Синтаксис и семантика языка Пролог

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

ции. Даются определения понятий «сопоставление структур» (pattern matching) и «автоматический возврат» (backtracking). Приво-

дятся примеры логического вывода – доказательства выполнимости или невыполнимости целевого утверждения (возможности или невозможности приведения его к пустому множеству подцелей).

1. Терм в Прологе

В предыдущей лекции было отмечено, что в ЯИП-1П входят такие синтаксические структуры как терм, атомарная формула и ППФ. В Прологе снято различие между этими понятиями на синтаксическом уровне. Считается, что каждая из этих структур является термом.

Хотя на синтаксическом уровне все термы «равноправны», с точки зрения их интерпретации – это не так. Есть термы, которые интерпретируются как атомарные формулы ЯИП-1П. В Прологе они называются предикатами. Очевидно, что с их помощью описываются отношения в той области интерпретации, с которой связана решаемая задача. Но есть и термы, используемые для «хранения» данных и являющиеся аргументами предикатов. Такие термы аналогичны термам ЯИП-1П.

25

На рис. 2.1 показано дерево классификации термов Пролога.

Рис. 2.1 Виды термов в языке Пролог

Рассмотрим примеры представителей всех классов, которые соответствуют «висячим вершинам» этого дерева.

Атомоподобные термы:

атомы: a, banana, Иванов_Иван_Иванович;

целые числа: 0, 25, 32767; десятичные числа: 3.1415, 0.5e-20;

строки: ’Email: ngvolchenkov@yandex.ru’, ’A & B => C’.

Переменные: _, _X, List25.

Структуры в форме со скобками: предок(Иван, Марья), p(a, b, q(c, d, e), f, g, h).

Структуры в бесскобочной форме: not A, Сократ человек,

X is A + 25.

Списки (пустой список: [], непустые списки: [H | T], [a, b, c]).

У каждого терма, в частности, у каждой структуры и, в частности, у каждого предиката есть две синтаксические характеристики: имя и арность (число аргументов).

Пример 2.1. Рассмотрим 4 терма: больше(X, 25); X is (2+3)*6; Сократ человек; p(a, b, q(c, d, e), f, g, h).

26

У1-го терма имя больше, арность 2, аргументы X и 25.

У2-го терма имя is, арность 2, аргументы X и (2+3)*6.

У3-го терма имя человек, арность 1, аргумент Сократ.

У4-го терма имя p, арность 6, аргументы a, b, q(c, d, e), f, g, h.

Пример 2.2. Пусть в данной области интерпретации Иван – отец Петра, Пётр – отец Сергея. Пусть атомы Иван, Пётр и Сергей соответствуют перечисленным лицам, а предикаты father(Иван, Пётр) и father(Пётр, Сергей) – перечисленным отношениям.

Можно рассмотреть другой терм с тем же именем, но только с одним аргументом: father(X). Он соответствует не предикату, а функции, возвращающей значение Иван или Пётр в зависимости от значения переменной X. Тогда допустимым с точки зрения Пролога будет следующий предикат: father(father(father(Сергей)), Пётр). Его значением будет истина.

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

Но есть решение этой проблемы: любой функциональный терм f(t1, …, tn), значением которого является r, можно заменить предикатом, имеющим большее число (n+1) аргументов: f(t1, …, tn, r).

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

По определению список – это:

Либо пустой список – атом, для обозначения которого используется специальная комбинация из двух скобок: [].

Длина такого списка равна 0;

Либо непустой список – структура без имени с двумя аргументами: Head и Tail. Первый аргумент («голова» списка) – это терм произвольного вида. Второй аргумент («хвост» списка) –

это список. Для обозначения непустого списка используется структура вида [Head | Tail].

Длина непустого списка равна длине его «хвоста» плюс 1.

Данное определение рекурсивное. Очевидно, что, согласно этому определению список – это правоассоциативное бинарное дерево, число вершин которого может быть любым. Чаще всего, это дерево изображают «растущим вниз» (рис. 2.2).

27

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

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

запросом к базе данных Пролога. Он имеет вид

?– R.

(Здесь R – последовательность предикатов C1, …, Cm, которые называются подцелями.)

Почему отрицание теоремы имеет такой вид?

В Прологе отрицание теоремы – это отрицание утверждения, которое на ЯИП-1П выглядит так:

X1 X2 … Xn R(X1, X2, … Xn),

где X1, X2, … Xn – переменные, входящие в состав ППФ R. Отрицание указанной формулы в исчислении предикатов эквива-

лентно формуле

X1 X2 … Xn R(X1, X2, … Xn).

(Отрицание существования есть всеобщность отрицания.)

Эту формулу можно представить в видеR(X1, X2, … Xn) false

(отбросив знаки квантора всеобщности) или в виде

R(X1, X2, … Xn) false,

а это и есть целевой клоз:

?– R(X1, X2, …, Xn).

И ещё одна особенность программ на Прологе. Иногда в начале программы (перед первым определением) ставятся директивы –

утверждения, напоминающие правила без левой части:

:– D1.

…

:– Dm.

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

Директивы располагаются перед определениями предикатов, а запрос к базе данных – в конце программы (или, обычно, в отдель-

29

ном окне, называемом консолью). Таким образом, структура Про- лог-программы имеет вид, показанный на рис. 2.3.

3. Структура определения предиката

Утверждения каждого определения предиката – это факты, имеющие спецификацию p/n, или правила, левые части которых имеют ту же спецификацию.

Пример 2.3. Рассмотрим определение предиката ancestor/2. Будем считать, что этот предикат используется только для поиска предков какого-нибудь человека, то есть, второй аргумент этого предиката в целевом утверждении должен быть атомом, а не переменной. Допустим, что в нашей базе данных все значения переменных – это имена людей. Примем также (без доказательства!), что все люди произошли от Адама (даже Ева – «из адамова ребра»).

30