Материал: Волченков Логическое программирование язык пролог 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