Определение отношений в программе

В настоящей главе вводятся основные понятия логического программирования и базовые понятия языка Пролог. Рассматриваются примеры определения отношений в программе на языке Пролог. Показывается, как использовать интерпретатор PIE для написания программ на языке Пролог, а также как создавать консольные приложения в системе Visual Prolog. Описываются основные разделы программы в языке Visual Prolog.

1.1. Понятие логической программы

Логическая программа — это последовательность предложений, описывающих отношения между элементами, или объектами, некоторой задачи. Объекты представляются термами. Термы определяются индуктивно — это константы, переменные или выражения вида $$f(t_1,t_2,\dots,t_m)$$, где $$f$$ — функциональный символ, а $$t_1,t_2,\dots,t_m$$ — термы. Термы без переменных называются основными, или замкнутыми термами. Отношения описываются с помощью предикатов. Выражения вида $$p(t_1,t_2,\dots,t_n)$$, где $$p$$ — имя предиката, а $$t_1,t_2,\dots,t_n$$ — термы, называются атомарными формулами. Атомарная формула или ее отрицание называется литералом.

Предложение логической программы имеет вид:

$$A_1\A_2\\dots \A_k\to A_0$$,

где $$\$$ — знак конъюнкции, $$\to$$ — знак импликации, $$A_0$$ — атомарная формула, а $$A_1, A_2,\dots, A_k$$ — литералы. На языке Пролог такое предложение записывается следующим образом:

$$A_0:- A_1, A_2, \dots, A_k$$.

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

$$заголовок :- тело$$ .

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

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

Рассмотрим программу

млекопитающее("слон").
млекопитающее("зебра").

животное("страус").
животное("уж").
животное(X):- млекопитающее(X).

С помощью фактов определяются безусловные отношения. Отношению "млекопитающее" принадлежат элементы "слон" и "зебра". В программе они представлены константами. Соответственно, область истинности предиката млекопитающее имеет вид: {слон, зебра}.

Правило выражает импликацию

$$\forall x(млекопитающее(x)\to животное(x))$$.

Областью истинности предиката животное является множество {страус, уж, слон, зебра}.

Вопросы бывают частные и общие, простые и составные. Частные вопросы помогают выяснить, верно ли, что заданные элементы принадлежат отношению:

$$?- животное("зебра")$$.

В ответе на частный запрос отмечается истинность или ложность цели.

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

$$?- животное(Z)$$.

Ответом на запрос является множество значений переменных, при которых формула цели является истинной.

Простые вопросы состоят из одной цели, составные — из нескольких, их называют подцелями. В составных вопросах подцели соединяются знаками конъюнкции "," или знаками дизъюнкции ";" (см. упр. 2). В первом случае запрос называется конъюнктивным, во втором — дизъюнктивным. Значения переменных в подцелях, разделенных знаками дизъюнкции, не связаны между собой.

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

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

В языке Visual Prolog комментарий до конца строки начинается со знака %. Между знаками /* и */ можно заключать комментарии произвольной длины.

Всюду ниже обозначение $$p/n$$ используется для указания арности отношения или предиката: предикат $$p$$ имеет арность $$n$$.

1.2. Декларативная семантика логической программы

В классическом случае все $$A_i$$ в правиле >$$A_1\A_2\\dots \A_k\to A_0$$ являются атомарными формулами, так что правило представляет собой хорновский дизъюнкт, т. е. дизъюнкт, содержащий не более одного положительного литерала:

$$\urcorner A_1\vee \urcorner A_2\vee \dots \vee \urcorner A_k \vee A_0$$.

Поэтому логическое программирование в узком смысле называют программированием на хорновских дизъюнктах.

Декларативная семантика рассматривает предложения классической логической программы как аксиомы, совокупность аксиом образует теорию. Цель программы — это теорема, которую нужно доказать. Декларативная семантика программы отвечает на вопрос, что делает программа.

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

Подстановкой термов вместо переменных называется множество $$\theta$$ пар термов вида $$x = t$$, где $$x$$ — переменная, а $$t$$ — терм, не содержащий переменную $$x$$. Иногда вместо равенств используются обозначения $$x | t$$ или $$t | x$$.

Если $$A$$ — формула, то выражение $$A \theta$$ обозначает формулу, полученную из формулы A заменой всех вхождений переменной $$x$$ на терм $$t$$ для всех равенств x = t, имеющихся в подстановке $$\theta$$.

Например, если $$A = животное(X)$$, $$\theta = \{X = слон\}$$, то $$A\theta = животное(слон)$$.

Правило $$B_0:- B_1, B_2, \dots, B_k$$, которое получается из правила $$A_0:- A_1, A_2,\dots, A_k$$ с помощью переименования переменных, называется вариантом исходного правила. Оно совпадает с формулой $$(A_0:- A_1, A_2, \dots, A_k)\theta$$ для некоторой подстановки $$\theta$$, состоящей из равенств $$x = y$$, где $$y$$ — переменная, не входящая в исходное правило.

Например, правило $$животное(A):- млекопитающее(A)$$ является вариантом правила $$животное(X):- млекопитающее(X)$$.

Правило $$B_0:- B_1, B_2, \dots, B_k$$, которое не содержит переменных и получается из правила $$A_0:- A_1, A_2,\dots, A_k$$ с помощью некоторой подстановки $$\theta$$, называется основным примером исходного правила.

Например, правило $$животное(слон):- млекопитающее(слон)$$ является основным примером правила $$животное(X):- млекопитающее(X)$$. В этом случае $$\theta = \{X = слон\}$$.

Эрбранов универсум логической программы — это множество $$U$$ термов, построенных индуктивно из констант и функциональных символов, входящих в программу (если в программе не содержится констант, то берется какая-нибудь произвольная константа).

Для рассматриваемой программы $$U = \{слон, зебра, страус, уж\}$$.

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

В нашем примере B = {млекопитающее(слон), млекопитающее(зебра), млекопитающее(страус), млекопитающее(уж), животное(слон), животное(зебра), животное(страус), животное(уж)}.

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

Моделью I логической программы называется такая интерпретация этой программы, что для каждого основного примера $$B_0:- B_1, B_2, \dots, B_n$$,правила $$A_0:- A_1, A_2,\dots, A_n$$ выполняется: если $$B_1, \dots, B_n \in I$$, то $$B_0 \in I$$, для всех правил программы.

Например, моделью является сам эрбранов базис.

Модель минимальна, если никакое ее собственное подмножество моделью не является. Очевидно, что пересечение двух моделей является моделью. Минимальная модель является пересечением всех моделей.

Из определения следует, что факты принадлежат произвольной модели. Из правила $$животное(X):- млекопитающее(X)$$ следует, что в любую модель нашей программы входят цели $$животное(слон)$$ и $$животное(зебра)$$. Таким образом, минимальная модель программы имеет вид:

I0 = {млекопитающее(слон), млекопитающее(зебра), животное(страус), 
животное(уж), животное(слон), животное(зебра)}

1.3. Приложение Prolog Inference Engine

Приложение Prolog Inference Engine (PIE) входит в собрание примеров Visual Prolog Examples, которые поставляются вместе с системой Visual Prolog (). Оно представляет собой интерпретатор реализации языка Пролог, синтаксис которой близок к реализации Эдинбургского Пролога. Для запуска приложения необходимо открыть проект в среде разработки Visual Prolog. Для этого нужно запустить файл vip.exe, выбрать команду меню Project > Open, нажать кнопку Browse… окна Visual Prolog Environment (рис. 1.1) и открыть файл Visual rolog Examples\pie\pie.vipprj. После этого следует выбрать команду меню Build > Execute (см. замечание в конце главы). В дальнейшем можно сразу запускать Exe-файл приложения PIE.

Информация об открываемых (и вновь созданных) проектах отображается в окне Visual Prolog Environment. Открывать проекты повторно можно прямо из списка проектов.

В следующей программе определяются предикаты летает/1, животное/1 и птица/1.

летает("синица").            % факты 
летает("лебедь").
летает("аэроплан").

животное("лебедь").
животное("синица").
животное("тигр").

птица("пингвин").
птица("страус").
птица(X):- животное(X), летает(X).      % правило

?- птица(A).              % запрос

Упражнение 1.

Поставьте курсор после знака точки и нажмите клавишу Enter (рис. 1.2). Ответ на запрос появится в этом же окне.

Для имен переменных в PIE следует использовать буквы латинского алфавита, для предикатов и констант можно использовать кириллицу. На языке Visual Prolog можно использовать кириллицу и для имен переменных.

В следующей программе в виде фактов определяются отношения "родитель", "супруг", "мужчина" и "женщина". С их помощью в виде правил определяются отношения "отец" и "мать".

родитель("Иван", "Мария").
родитель("Анна", "Мария").
родитель("Мария", "Павел").
родитель("Мария", "Петр").

супруг("Иван", "Анна").
супруг("Павел", "Юлия").

мужчина("Иван").
мужчина("Павел").
мужчина("Петр").

женщина("Мария").
женщина("Анна").
женщина("Юлия").

отец(F, C):- 
    родитель(F, C),
    мужчина(F).

мать(M, C):-
    родитель(M, C),
    женщина(M).

Упражнение 2.

Запустите в PIE программу "Родственные отношения" (см. листинг 1.2). Задайте следующие вопросы программе:

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

1.4. Создание консольных приложений

Для того чтобы создать консольное приложение в системе Visual Prolog следует войти в среду разработки и выбрать команду меню Project > New. В открывшемся диалоговом окне Project Settings в поле Project Name следует вписать имя проекта (например, chapter1), в поле Project Kind следует указать Console application. После нажатия кнопки Finish или Next создается проект (рис. 1.3) (при нажатии кнопки Next появляется окно установки дополнительных параметров).

Построить проект можно с помощью команды меню Build > Build (или кнопки B панели инструментов), скомпилировать — команды Build > Compile (или кнопки C панели инструментов). Всякий раз, когда система будет спрашивать о добавлении директивы include <…>, можно просто отвечать Add All.

Факты базы данных поместим в отдельный модуль. Для этого выделим корень дерева проекта и выберем команду меню File > New In New Package. Появится окно Create Project Item. Cлева выберем элемент Text File, в поле Name напишем имя family, а в поле Parent Directory впишем слово Exe (рис. 1.4).

Нажмем кнопку Create. В результате в директории Exe проекта будет создан файл family.txt. Этот файл можно открыть из дерева проекта.

Откроем файл и поместим в него факты базы данных (см. листинг 1.3).

clauses
    parent("Иван", "Мария").
    parent("Анна", "Мария").
    parent("Мария", "Павел").
    parent("Мария", "Петр").
    parent("Мария", "Елизавета").

    spouse("Иван", "Анна").
    spouse("Павел", "Юлия").

    male("Иван").
    male("Павел").
    male("Петр").

    female("Мария").
    female("Анна").
    female("Елизавета").
    female("Юлия").

Код программы, приведенной ниже (листинг 1.4), нужно поместить в файл main.pro (в имплементацию класса main).

Язык Visual Prolog — типизированный, поэтому предикаты необходимо объявлять. В объявлении предиката указывается его имя, ставится знак двоеточия, а затем в круглых скобках через запятую перечисляются имена доменов (типов данных) аргументов:

class facts - relatives
    parent: (string Родитель, string Ребенок).

Словом relatives обозначено имя базы данных. В объявлениях предикатов можно использовать комментарии специального вида. Слова Родитель и Ребенок в этом объявлении обозначают комментарии. Компилятор их игнорирует. Такие комментарии пишутся в одно слово с прописной буквы.

Предикаты объявляются в разделах class facts (если определяются только в виде фактов) или class predicates, а определяются в разделе clauses. Цель программы формулируется в разделе goal, который находится в файле main.pro. Обычно в разделе goal только вызывается некоторый предикат, который используется для составления запросов. В данном примере и всюду далее таким предикатом является run.

Раздел open имплементации класса main следует изменить следующим образом:

open core, console

После добавления имени класса в раздел open предикаты этого класса можно использовать без указания имени этого класса, например, вместо console::write писать просто write. Предикат write используется для вывода на печать своих аргументов, которых может быть произвольное конечное число.

class facts - relatives
    parent: (string Родитель, string Ребенок).
    spouse: (string Муж, string Жена).
    male: (string).
    female: (string).

class predicates
    father: (string Отец, string Ребенок) nondeterm anyflow.
    mother: (string Мать, string Ребенок) nondeterm (o,o).
clauses
    father(X, Y):-
        parent(X, Y),
        male(X).

    mother(X, Y):-
        parent(X, Y),
        female(X).

    run():-
        init(),
        file::consult("family.txt", relatives),
        father(X, Y),
            write("отец - ", X, ", ребенок - ", Y), nl,
        fail;
        mother(X, Y),
            write("мать - ", X, ", ребенок - ", Y), nl,
        fail;
        if father("Иван", "Петр") then 
            write("\nИван является отцом Петра")
        else 
            write("\nИван не является отцом Петра")
        end if, 
        _ = readLine().

Вывод решений для запроса, например для цели $$?- father(X, Y)$$, организуется с помощью предиката fail. Этот предикат имеет значение ложь. Он вынуждает программу вернуться для поиска других решений. Его можно заменить любым ложным условием, например, 0 = 1. Когда перебор заканчивается, выполняется переход к подцели, стоящей после знака дизъюнкции ";". Для задания частного вопроса используется конструкция if-then-else-end if.

Ключевое слово nondeterm в объявлении предиката означает, что область истинности этого предиката может содержать более одного элемента или не содержать ни одного (см. п. 3.4). Ключевое слово anyflow означает, что некоторые аргументы предиката могут быть как входными, так и выходными. Последовательность (o,o) означает, что оба аргумента предиката — выходные, они возвращают некоторые значения (см. п. 3.5).

Предикат init инициализирует консоль, предикат consult загружает факты базы данных из файла в оперативную память. Программа обращается с ними так же, как если бы они были приведены в разделе clauses, вместе с другими предложениями.

Для ввода и вывода в консоли используются буфер ввода и буфер вывода, соответственно. Предикат clearInput очищает буфер ввода, предикат clearOutput очищает буфер вывода. Предикат readLine считывает содержимое буфера ввода в строку (string) и при этом полностью очищает содержимое этого буфера. В данном случае программа просто ожидает ввода любого символа.

Как создавать консольные приложения, описано также в [15] (дополнительно см. пример Visual Prolog Examples > _tutorial > family 1).

1.5. Основные разделы программы

В языке Visual Prolog используются следующие разделы программы [15]:

Раздел goal может быть только один в проекте, он располагается в файле main.pro.

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

Кроме этого, имеются разделы supports, resolve, inherits, delegates, predicates from и другие.

1.6. Создание модулей

В дальнейшем рекомендуется для каждой главы создавать отдельный консольный проект, а для каждого примера — отдельный модуль (рис. 1.5).

Для того чтобы создать модуль, следует выделить корень дерева проекта и выбрать команду (всплывающего) меню New In New Package. В открывшемся диалоговом окне Create Project Item необходимо выбрать в левом поле раздел Class (см. рис. 1.4), убрать флажок из поля Create Interface, ввести в поле Name имя модуля (ex1) и нажать на кнопку Create. В декларации класса (файл ex1.cl) нужно объявить предикат run, с помощью которого будет указываться цель:

predicates
    run: ().

Раздел open имплементации класса (файл ex1.pro) должен иметь вид:

open core, console

Раздел goal проекта (файл main.pro) нужно изменить следующим образом:

goal
    mainExe::run(main::run),
    ex1::run().

Для построения и компиляции пакета используются команды Build и Compile.

Перед именем предиката (домена, функтора, свойства или константы) объявленного в декларации класса, вне имплементации этого класса указывается имя этого класса: пишется имя класса, ставится двойное двоеточие, а затем вводится имя предиката. Для запуска программы используются команды меню Build > Run in Window или Build > Execute (или кнопка E панели инструментов).

Замечание. Если используется незарегистирированная версия Personal Edition, то при выполнении любой команды меню Build появляется окно, предлагающее активировать код лицензии. Для продолжения — выполнения команды — достаточно нажать кнопку Cancel. Код лицензии выдается при регистрации системы. Регистрация бесплатна. После активации кода указанное окно больше не появляется. Остается окно с предупреждением о возможности использования ознакомительной версии только некоммерческим образом.

Упражнения

add(o, X, X).
add(s(X), Y, s(Z)):- add(X, Y, Z).