Основные средства языка логического программирования Пролог

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

Программирование на Прологе включает в себя следующие этапы [5]:

1) объявление фактов о объектах и отношениях между ними;

2) определение правил взаимосвязи объектов и отношений между ними;

)   формулировка вопроса об объектах и отношениях между ними.

Основными составляющими программы на Прологе являются ….

Факты - это предикат с аргументами-константами, обозначающие отношения между объектами или свойства объектов, именованные этими константами. Факты в программе считаются всегда и безусловно истинными и таким образом служат основой доказательства, происходящего при выполнении программы [14].

Правила - это хорновские фразы с одной или несколькими переменными и с заголовком. Правила имеют форму <голова правила>:-<список подцелей>, где знак ":-" читается «если», а список подцелей состоит из отдельных подцелей, разделенных запятой, читаемой как «и». Правила позволяют определить новые отношения между объектами на основе уже объявленных с помощью фактов. В качестве аргументов в предикатах правила могут использоваться константы и переменные. На переменные в правилах действуют кванторы общности, поэтому правила концентрированно и лаконично выражают конструкции логического вывода [14]. Правила в Прологе часто бывают рекурсивными, т.е. использующими себя в своем определении.

Вопрос - отправная точка логического вывода, происходящего при выполнении программы [14].

В каждой процедуре должен быть принят порядок правил, или порядок предложений. Кроме того, в теле каждого предложения должен быть определён порядок целей. Порядок правил определяет порядок поиска решений. Изменение порядка правил в процедуре приводит к перестановке ветвей в любом дереве поиска цели, использующей данную процедуру. Обход дерева поиска происходит в глубину. Поэтому перестановка ветвей дерева изменяет порядок обхода дерева и порядок нахождения решений [24].

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

Пусть дана некоторая программа и цель G, тогда, в соответствии с декларативной семантикой, можно утверждать, что:

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

(1) в программе существует предложение С, такое, что

(2) существует такая его конкретизация I, что

(а) голова I совпадает с G и

(b) все цели в теле I истинны.

Эти определения можно распространить на вопросы следующим образом. В общем случае вопрос к Пролог-системе представляет собой список целей, разделенных запятыми. Список целей называется истинным (достижимым), если все цели в этом списке истинны (достижимы) при одинаковых конкретизациях переменных. Значения переменных получаются из наиболее общей конкретизации [3].

Процедурная семантика определяет, как пролог-система отвечает на вопросы. Ответить на вопрос - это значит удовлетворить список целей. Этого можно добиться, приписав встречающимся переменным значения таким образом, чтобы цели логически следовали из программы. Можно сказать, что процедурная семантика Пролога - это процедура вычисления списка целей с учетом заданной программы. «Вычислить цели» это значит попытаться достичь их.

Автор Братко И. [1] называет эту процедуру "Вычислить". Как показано на рисунке, входом и выходом этой процедуры являются:

входом - программа и список целей,

выходом - признак успех/неуспех и подстановка переменных.

 

 

Смысл двух составляющих выхода такой:

(3) Признак успех/неуспех принимает значение «да», если цели достижимы, и «нет» - в противном случае. Будем говорить, что «да» сигнализирует об успешном завершении и «нет» - о неуспехе.

(4) Подстановка переменных порождается только в случае успешного завершения; в случае неуспешного подстановка отсутствует.

Чтобы вычислить список целевых утверждений

 

G1, G2, …, Gm

 

процедура вычислить делает следующее:

· Если список целей пуст - завершает работу успешно.

· Если список целей не пуст, продолжает работу, выполняя (описанную далее) операцию «ПРОСМОТР».

· ПРОСМОТР: Просматривает предложения программы от начала к концу до обнаружения первого предложения С, такого, что голова С сопоставима с первой целью G1. Если такого предложения обнаружить не удается, то работа заканчивается неуспехом.

Если С найдено и имеет вид

 

H:- B1, …,Bn.

 

то переменные в С переименовываются, чтобы получить такой вариант С’ предложения С, в котором нет общих переменных со списком G1, …, Gm. Пусть С’ - это

 

H’:- B1’, …, Bn’.

 

Сопоставляется G1 c H’; пусть S - результирующая конкретизация переменных. В списке целей G1, G2, …, Gm, цель G1 заменяется на список B1’, …, Bn’, что порождает новый список целей:

 

B1’, …, Bn’,G2, …, Gm.

 

(Заметим, что, если С факт, тогда n=0, и в этом случае новый список целей оказывается короче, нежели исходный; такое уменьшение списка целей может в определенных случаях превратить его в пустой список, а следовательно, - привести к успешному завершению.)

Переменные в новом списке целей заменяются новыми значениями, как это предписывает конкретизация S, что порождает еще один список целей

 

B1’’, …, Bn’’, G2’, …, Gm’

 

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

Этот просмотр продолжается, начиная с предложения, непосредственно следующего за предложением С (С - предложение, использовавшееся последним) и делается попытка достичь успешного завершения с помощью другого предложения.

Всякий раз, как рекурсивный вызов процедуры вычислить приводит к неуспеху, процесс вычислений возвращается к ПРОСМОТРУ и продолжается с того предложения С, которое использовалось последним. Поскольку применение предложения С не привело к успешному завершению, пролог-система должна для продолжения вычислений попробовать альтернативное предложение. В действительности система аннулирует результаты части вычислений, приведших к неуспеху, и осуществляет возврат в ту точку (предложение С), в которой эта неуспешная ветвь начиналась. Когда процедура осуществляет возврат в некоторую точку, все конкретизации переменных, сделанные после этой точки аннулируются. Такой порядок обеспечивает систематическую проверку Пролог-системой всех возможных альтернативных путей вычисления до тех пор, пока не будет найден путь, ведущий к успеху, или же до тех пор, пока не окажется, что все пути приводят к неуспеху.

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

) Для остановки механизма возвратного поиска используется предикат! - gut ("отсечение" или "замораживание"). При этом сохраняются значения переменных, которые они получили к данному моменту [3]. Отсечение следует применять в тех случаях когда:

· необходимо указать, что найдено нужное правило для целевого утверждения;

· требуется немедленно прекратить доказательство согласованности конкретного целевого утверждения, не пытаясь найти для него решения (в этом случае используется конъюнкция отсечения с предикатом fail);

· необходимо прекратить порождение альтернативныхрешений механизмом возврата.

Смысл механизма отсечения можно сформулировать так:

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

) Абстрактные типы данных (АТД) - типы данных, рассматриваемые независимо от способов их представления или реализации средствами языка программирования. АТД определяются множеством значений и совокупностью опреаций, которые могут выполняться над значениями данного типа [3]. Примерами АТД являются строки и массивы.

Список представляет собой упорядоченную последовательность данных. Его также можно представить в виде структуре, имеющей два компонента: заголовок (голова) и остаток (хвост). В частности, если список состоит из одного элемента, то ео хвост - пустой список. Таким образом, список имеет рекурсивную составную структуру данных. Рекурсивное определение выглядит так:

пустой список является списком;

объект, имеющий голову и хвост, является списком, если его хвост список.

Основные операции для работы сос списками - отделение головы от хвоста, конструирование нового списка из заданных головы и хвоста и проверка списка на пустоту.

) Внутренние базы данных

Различают статистическую и динамическую внутренние базы данных. Первая представляется в программе в виде фактов (в разделе clauses). Вторая состоит из фактов, которые добавляются и удаляются в оперативной памяти во время выполнения программы (утверждения динамической базы данных формируются в виде предикатов в разделе database) [3].

В случае, если необходимо не просто получить последовательность решений какого-либо целевого утверждения, полученных из внутренней базы данных (статистической или динамической), а обработать сразу все решения как часть единой составной структуры данных, используется встроенный предикат findall. У предиката findall три аргумента: имя переменной-параметр, который нужно собрать в список; имя предиката, из которого надо собрать значения; и список значений, собранных с помощью метода поиска с возвратом.

Таким образом, процедурная семантика Пролога моделирует недетерминированный выбор редуцирующего правила с помощью последовательного поиска и механизма возврата [13]. Следовательно, Пролог для решения логических задач применяет только метод формального перебора списка подцелей.