Артемьева И.Л., Тютюник М.Б. Тютюнник Модель модульного языка декларативных конфлюэнтных продукций с ограниченными кванторами. // Искусственный интеллект, 2007, № 3, с. 374-382

УДК 004.8+004.032.24


И.Л. Артемьева, М.Б. Тютюнник

Институт автоматики и процессов управления ДВО РАН, г. Владивосток

artemeva@iacp.dvo.ru, michaelhuman@gmail.com
Россия


Модель модульного языка декларативных конфлюэнтных продукций с ограниченными кванторами

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


Введение

Системы продукций (или системы, основанные на правилах) широко используются при создании систем, основанных на знаниях (СОЗ) [1]. Совокупность правил описывает метод решения прикладной задачи, реализуемый СОЗ. Для записи правил обычно используется терминология, принятая в предметной области и задаваемая ее онтологией [2], что позволяет получить понятный пользователю метод решения задачи. Опыт использования систем продукций для создания программных систем показал необходимость развития таких языков в нескольких направлениях: развитие используемых типов данных, наличие модулей, добавление средств для компактной записи правил.

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

Работа выполнена при финансовой поддержке ДВО РАН в рамках программы № 14 Президиума РАН, проект 06-I-П14-052.


Модель модульного языка декларативных конфлюэнтных продукций. Синтаксис

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

Синтаксис термов. Термом является предметный символ (константа ПО) - имя n; переменная v; термы, обозначенные I, R, S, Æ; {t1,t2,...,tk}, где t1,t2,...,tk (k Î Nat - множеству натуральных чисел) - термы; I[t1,t2], R[t1,t2], где t1 и t2 - термы; t1 ¤ t2, где t1 и t2 - термы, «¤» Î {+, -, *, /,È, Ç, \}; m(t), где t – терм; (Z (v : t1) t2) (кванторный терм), где Z Î {+, *,È, Ç} – знак операции, v – переменная (индекс операции), t1 – терм, задающий область значений v, t2 – терм (тело обобщенной операции), содержащий индекс операции v; jota(v : t) f – йота-операция, где v – переменная, f – формула, содержащая индекс операции v; f(t1,...,tk) - функциональный терм, где t1,...,tk (k Î Nat) – термы (аргументы функционального терма).

Синтаксис формул. Формулами являются: p(t1,...,tk) – атомная формула, где p – предикатный символ, t1,...,tk (k Î Nat) – термы (аргументы атомной формулы); Øp(t1,...,tk) – отрицательная атомная формула;t1 @ t2, где t1 и t2 – термы, «@» Î {=, ¹, >, <, £, ³, Ì, Í, Ï, Î}; f1 @ f2 – логическое выражение, где «@» Î {&, V}; (Zn (v : t) f) - обобщенная формула, где Zn Î {&, V} – знак обобщенной операции, v – переменная (индекс операции), t – терм-множество, задающий область значений v, f – формула (тело обобщенной операции), содержащая индекс операции v.

Синтаксис правил. Правила состоят из префикса и тела правила. Префикс есть последовательность описаний переменных (v1:t1)(v2:t2)...(vm:tm), где (vi:ti) - описание переменной, vi - переменная, ti - терм для всех i=1,...,m. Терм t1 не содержит свободных переменных. Для i=2,..., m свободными переменными терма ti могут быть только переменные v1, v2,...,vi-1. Последовательность описаний может быть пустой. Все переменные v1, v2,..., vm попарно различны.

Любая свободная переменная, входящая в тело предложения, должна быть описана в его префиксе. Если переменная является связанной в теле предложения, то она не может входить в префикс этого предложения.

Правила (продукции) в модели декларативных продукций – это выражения двух видов (будем обозначать множество всех правил вида (1) R’, а множество правил виде (2) - R’’):

(1) (префикс) P(X) ® S1(X1)&…&Sk(Xk),

где k Î Nat, P(X) – формула, которая содержит, по крайней мере, один предикатный символ, или функциональный терм, S1(X1), …, Sk(Xk) – атомные формулы и функциональные термы, X, X1, …, Xk – векторы термов.

Каждое правило должна удовлетворять основному условию на переменные:

V({S1(X1), …, Sn(Xn)}) È V(P(X)) Í V(префикс),

где V(O) - множество переменных, входящих в O (O может быть любой конструкцией). Часть продукции до символа «→» будем называть условием продукции, а часть после символа «→» - ее следствием. Условие правила является логическим выражением, составленным из соотношений, функциональных термов, атомных формул и обобщенных формул по правилам, приведенным ниже. Элементом конъюнкции следствия может быть атомная формула и функциональный терм.

(2) (префикс) P(X) ® NameMod(S1, …, Sk) – правило – вызов модуля, где

P(X) - формула, которая содержит по крайней мере один предикатный символ, или функциональный терм, NameMod(S1, …, Sk) – имя модуля, X – вектор термов, S1, …, Sk – атомные формулы и функциональные термы.

Схемы. Назовем схемой конструкцию вида:

(3) NameSch([.КОНСТ]w1, [.КОНСТ]w2, …, [.КОНСТ]wn): rule, где

NameSch – имя схемы, w1, w2, …, wn – переменные, n Î Nat, rule Î R’. Переменные w1, w2, …, wn являются формальными параметрами схемы. Тело схемы представляет собой правило и должно содержать формальные параметры. Запись «[.КОНСТ]» означает, что «.КОНСТ» может отсутствовать.

Пусть V(префикс) – множество переменных, входящих в правило вида (1), тогда {w1, w2, …, wn} Í V(префикс).

Конкретизации схем. Определим понятие «конкретизация схемы». Каждая конкретизация схемы в МДПО имеет вид:

(4) NameSch(zw1, zw2, …, zwn), где

NameSch – имя схемы, которое совпадает с именем той схемы, для которой определена конкретизация, zw1, zw2, …, zwn – термы, n Î Nat. Термы zw1, zw2, …, zwn являются фактическими параметрами схемы.

Все конкретизации схем образуют множество правил R’’’ модели декларативных продукций с обобщенными операциями.


Модель модульного языка декларативных конфлюэнтных продукций. Семантика

Семантика термов и формул. Семантика термов и формул определяет значения термов и формул, а также условия, при которых эти значения существуют.

Будем предполагать, что на множестве имен задана функция a, значение которой для каждого имени есть интерпретация этого имени. Значения термов и формул будут определены относительно функции интерпретации a и произвольной допустимой подстановки q значений вместо всех свободных переменных терма или формулы. Обозначим Ja,q(t)- значение терма t для функции интерпретации a и допустимой подстановки q, Ja,q(f) значение формулы f для функции интерпретации a и допустимой подстановки q, q(v) - значение переменной v при подстановке q.

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

1. Ja,q(n) = a(n), где n – имя; Ja,q(n) не зависит от q;

2. Ja,q(v) = q(v), где v - переменная;

3. Ja,q(I), Ja,q(R)? Ja,q(S) – соответственно множество всех целых или вещественных чисел или бесконечное множество всех возможных имен, Ja,q(I) не зависит от a и q;

4. Ja,q(Æ) - пустое множество; Ja,q(Æ) не зависит от a и q;

5. Ja,q({t1,t2,...,tk}) = {Ja,q(t1), Ja,q(t2), ..., Ja,q(tk)}, т.е. значение этого терма есть множество, элементами которого являются Ja,q(t1), Ja,q(t2),..., Ja,q (tk); терм имеет значение, если для функции интерпретации a и подстановки q имеют значения термы t1, t2,..., tk;

6. Ja,q(I[t1,t2]) (Ja,q(R[t1,t2])) есть множество всех целых (вещественных) чисел, не меньших Ja,q(t1) и не больших Ja,q(t2); терм имеет значение, если Ja,q(t1) и Ja,q(t2) являются числами и имеет место Ja,q(t1)£Ja,q(t2);

7. Ja,q(t1 ¤ t2) = Ja,q(t1) ¤ Ja,q(t2), где «¤» Î {+, -, *, /}; терм имеет значение, если Ja,q(t1) и Ja,q(t2) являются числами;

8. Ja,q(t1 ¤ t2) = Ja,q(t1) ¤ Ja,q(t2), где «¤» Î {È, Ç, \}; терм имеет значение, если Ja,q(t1) и Ja,q(t2) являются множествами;

9. Ja,q(m(t)) - мощность множества Ja,q(t); терм имеет значение, если Ja,q(t) является конечным множеством;

10. Ja,q(+ (v:t1) t2) = , т.е. Ja,q(+(v:t1) t2) равно сумме значений Ja,q(t2), при условии, что связанная переменная v пробегает все элементы множества Ja,q(t1); терм имеет значение, если Ja,q(t1) является множеством, а Ja,q(t2) - числом при замене переменной v любым элементом множества Ja,q(t1);

11. Ja,q(* (v:t1) t2) = , т.е. Ja,q(+ (v:t1) t2) равно произведению значений Ja,q(t2), при условии, что связанная переменная v пробегает все элементы множества Ja,q(t1); терм имеет значение, если Ja,q(t1) является множеством, а Ja,q(t2) - числом при замене переменной v любым элементом множества Ja,q(t1);

12. Ja,q(È (v:t1) t2) = , т.е. Ja,q(È (v:t1) t2) равно объединению значений Ja,q(t2), при условии, что связанная переменная v пробегает все элементы множества Ja,q(t1); терм имеет значение, если Ja,q(t1) является множеством, а Ja,q(t2) - множеством при замене переменной v любым элементом множества Ja,q(t1);

13. Ja,q (Ç((v:t1) t2) = т.е. Ja,q (Ç (v:t1) t2) равно пересечению значений Ja,q(t2), при условии, что связанная переменная v пробегает все элементы множества Ja,q(t1); терм имеет значение, если Ja,q(t1) является множеством, а Ja,q(t2) - множеством при замене переменной v любым элементом множества Ja,q(t1).

13. Ja,q(jota (v:t) f) равно тому элементу множества Ja,q(t), при подстановке которого вместо переменной v значение Ja,q(f) есть истина; терм имеет значение, если значение Ja,q(t) является множеством, а его элемент, при подстановке которого вместо v значение Ja,q(f) есть истина, является единственным;

14. Ja,q(f(t1,t2,...,tk)) = j(Ja,q(t1),Ja,q(t2),...,Ja,q(tk)) - значение функции j, которая есть интерпретация имени Ja,q(f) (т.е. j = a(Ja,q(f))), от аргументов Ja,q(t1),...,Ja,q(tk); заметим, что если t' - терм, такой, что Ja,q(t') = <Ja,q(t1),Ja,q(t2),...,Ja,q(tk)>, то Ja,q(f(t'))=Ja,q(f(t1,t2,...,tk));

Значения формул определяются следующим образом:

1. Ja,q(p(t1,...,tk)) = r(Ja,q(t1),Ja,q(t2),...,Ja,q(tk)) - значение предиката r, который есть интерпретация имени Ja,q(p) (т.е. r=a(Ja,q(p))) от аргументов Ja,q(t1),..., Ja,q(tk);

2. Ja,q(Øp(t1,...,tk)) = Ør(Ja,q(t1),Ja,q(t2),...,Ja,q(tk)) - значение предиката r, который есть интерпретация имени Ja,q(p) (т.е. r=a(Ja,q(p))) от аргументов Ja,q(t1),..., Ja,q(tk);

3. Ja,q(t1 @ t2) = Ja,q(t1) @ Ja,q(t2), где «@» Î {=, ¹, >, <, £, ³, Ì, Í, Ï, Î}; формула имеет значение, если для функции интерпретации a и подстановки q термы t1 и t2 имеют значения;

4. Ja,q(f1 @ f2) = Ja,q(f1) @ Ja,q(f2), где «@» Î {&, V}; формула имеет значение, если для функции интерпретации a и подстановки q имеют значения формулы f1 и f2;

5. Ja,q(& (v : t) f) =Ja,q(f), т.е. значение формулы истина тогда и только тогда, когда все значения Ja,q(f) есть истина при условии, что связанная переменная v пробегает все элементы множества Ja,q(t); формула имеет значение, если Ja,q(t) является множеством, и для функции интерпретации a и подстановки q формула f имеет значение при замене переменной v любым элементом множества Ja,q(t1);

6. Ja,q(V (v : t) f) =Ja,q(f), т.е. значение формулы истина тогда и только тогда, когда хотя бы одно из значений Ja,q(f) есть истина при условии, что связанная переменная v пробегает все элементы множества Ja,q(t); формула имеет значение, если Ja,q(t) является множеством, и для функции интерпретации a и подстановки q формула f имеет значение при замене переменной v любым элементом множества Ja,q(t1);

7. Ja,q(t1 Î t2) Û Ja,q(t1) Î Ja,q(t2), т.е. значение формулы t1 Î t2 есть истина тогда и только тогда, когда значение Ja,q(t1) принадлежит множеству Ja,q(t2); формула имеет значение, если для функции интерпретации a и подстановки q терм t1 имеет значение, а Ja,q(t2) является множеством;

8. t1 Ï t2, где t1 и t2 - термы; Ja,q(t1 Ï t2) Û Ja,q(t1) Ï Ja,q(t2), т.е. значение формулы t1 Ï t2 есть истина тогда и только тогда, когда значение Ja,q(t1) не принадлежит множеству Ja,q(t2); формула имеет значение, если для функции интерпретации a и подстановки q терм t1 имеет значение, а Ja,q(t2) является множеством;

9. t1Ìt2, где t1 и t2 - термы; Ja,q(t1Ìt2)ÛJa,q(t1)ÌJa,q(t2), т.е. значение формулы t1 Ì t2 есть истина тогда и только тогда, когда множество Ja,q(t1) является собственным подмножеством множества Ja,q(t2); формула имеет значение, если Ja,q(t1) и Ja,q(t2) являются множествами;

10. t1Ít2, где t1 и t2 - термы; Ja,q(t1Ít2)ÛJa,q(t1)ÍJa,q(t2), т.е. значение формулы t1Ít2 есть истина тогда и только тогда, когда множество Ja,q(t1) является подмножеством множества Ja,q(t2); формула имеет значение, если Ja,q(t1) и Ja,q(t2) являются множествами.

Описания имен. Имена объектов являются терминами предметной области. Описание имен объектов имеет вид: <Name, S, C>, где Name – имя объекта, S – описание сорта имени, C – описание определенности объекта.

Описание задает предметные, предикатные или функциональные имена. К предметным именам отнесем имена объектов, имеющих сорт I, R, S (множества целых и вещественных чисел, множество имен), сорт «интервалы» (значением является пара <x1, x2>, где x1, x2 Î I (или x1, x2 Î R), x1 < x2), сорт «множества» (значением является множество {x1, x2, …, xk}, где xi принадлежит I, или R, или S, i Î {1, 2, …, k}). К предикатным именам отнесем имена объектов, сорт которых представляет собой декартово произведение сортов аргументов. Сорта аргументов определяются кортежем <А1, А2, …, Ak>, причем Аi (i Î {1, 2, …, k}) равно I, R или S. Предикатное имя обозначает некоторое отношение между объектами. Одноместное отношение рассматривается как множество объектов, многоместное – отношение между несколькими объектами, которые принадлежат множествам, задаваемым описаниями аргументов данного отношения. Описание функционального имени задает сорта его аргументов <А1, А2, …, Ak> и сорт результата. Функциональное имя обозначает функцию, которая сопоставляет некоторому набору объектов (аргументов функции) ее результат.

Описание определенности объекта C задает тип объекта (точный либо недоопределенный), а для предикатов и функций также описывает тип неопределенности. Характеристики неопределенности задают способ вычисления значений в процессе вывода и могут иметь значение «первый» или «второй». Если функция или предикат имеет первый тип неопределенности, то в процессе вывода добавляются новые кортежи значений аргументов и результата. В этом случае предикат рассматривается как функция, у которой область значений совпадает с множеством логических значений. Предполагается, что значение предиката определено только для тех кортежей аргументов, которые уже добавлены в процессе вывода. Если функция или предикат имеет второй тип неопределенности, то на момент начала вычислений уже задана совокупность вариантов значений, процесс вычисления данного объекта состоит в исключении вариантов. Если объект, имеющий предметное имя, имеет тип «недоопределенный», то на момент начала вычислений уже задана совокупность вариантов значений, процесс вычисления данного объекта состоит в исключении вариантов.

Семантика правил. Префикс правила определяет множество допустимых подстановок вместо свободных переменных этого правила. Пусть префикс правила имеет вид (v1:t1)(v2:t2)...(vm:tm), тогда множество допустимых подстановок есть множество всех подстановок вида q=(v1/c1,...,vm/cm), где c1 Î Jaq1(t1), c2 Î Jaq2(t2),..., cmÎJaqm(tm), q1 - пустая подстановка, q2 =(v1/c1),...,qm=(v1/c1,...,vm-1/cm-1). Правило имеет смысл, если Jaq1(t1), Jaq2(t2),..., Jaqm(tm) - такие множества, что множество допустимых подстановок правила конечно.

1. Если r º P(X) ® S1(X1)&…&Sn(Xn) – тело правила вида (1), то Ja,q(r) = Ja,q(P(X)) ® Ja,q(S1(X1))&…& Ja,q(Sn(Xn));

2. Если r º P(X) ® NameMod(S1, …, Sn) – тело правила вида (2), то Ja,q(r) = Ja,q(P(X)) ® Ja,q(NameMod(S1, …, Sn)). Вычисление значения данного вида правил состоит в вычислении значений формул и функциональных термов S1, …, Sn, вычисление которых происходит в модуле NameMod.

Семантика схем и конкретизаций схем. Схема правила является аналогом описания процедуры в алгоритмической языке, а конкретизация – аналогом вызова этой процедуры. Параметры схемы, тем самым, являются формальными параметрами, а параметры конкретизации – фактическими параметрами. Значение правила, входящего в схему, определяется при некоторой конкретизации, то есть при замене формальных параметров фактическими. При этом, если в списке формальных параметров при описании некоторого параметра присутствует «.КОНСТ», то имени формального параметра схемы соответствует имя фактического параметра конкретизации, иначе если ключевое слово не указано, то имени формального параметра соответствует значение этого параметра.

Если ss º NameSch([.КОНСТ]w1, [.КОНСТ]w2, …, [.КОНСТ]wn): rule – схема вида (3), rr º NameSch(zw1, zw2, …, zwn) – конкретизация схемы вида (4), q = {v1/c1, …, vm/cm} – допустимая подстановка, то Ja,q(rr) = Ja,qÈ{w1/zw1,…,wn/zwn} (rule).

Описание модуля. Модулем будем называть конструкцию вида:

<NameMod, GlobD, LocD, R>, где NameMod – имя модуля, GlobD – множество описаний глобальных имен, LocD - множество описаний локальных имен и схем, R = R’ È R’’ È R’’’ – множество правил. При этом GlobD ¹ Æ, а LocD может быть Æ. Множество описаний глобальных имен состоит из описания формул, являющихся по сути формальными аргументами модуля в том случаем, если этот модуль вызывается из другого. Информация о глобальных объектах требуется для выполнения модуля и может быть получена из файла или вызвавшего модуля, также она может быть передана за пределы модуля (например, в файл или в другой модуль) после его выполнения.

Множество описаний локальных имен и схем задают переменные, формулы и схемы, использующиеся только в пределах данного модуля. Все глобальные и локальные имена различны между собой. При этом пересечение глобальных имен двух модулей будут непусты, если один модуль вызывает другой модуль: GlobDNameMod1 Ç GlobDNameMod2 = {S1, …, Sk}, где NameMod1 – модуль, который содержит вызов модуля NameMod2(S1, …, Sk), описание имен глобальных объектов (формул и функциональных термов) S1, …, Sk должно полностью совпадать.

Множество правил логического модуля R составляет совокупность правил R’ вида (1), правил R’’ с вызовами модуля вида (2) и множества R’’’ конкретизаций (4). Каждое из множеств R’, R’’, R’’’ может быть пустым, но при этом их объединение пустым быть не может.

Процесс логического вывода

Процесс логического вывода (ПЛВ) на модели декларативных продукций определяется как исчисление с входом. Начальное состояние (dS) ПЛВ формируется в результате ввода исходных данных задачи. Каждое следующее состояние ПЛВ получается из предыдущего в результате применения некоторого правила, конкретизации схемы или вызова модуля.

Введем обозначения:

- q = {v1/c1, …, vm/cm} – допустимая подстановка;

- K – база правил (конечное множество правил); r – правило;

- H – рабочая среда ПЛВ – множество всех конечных множеств атомарных формул с константами;

- di – текущее состояние ПЛВ (или состояние ПЛВ на i-том шаге), di Î H.

- dN – новое состояние ПЛВ, которое получается из d после применения правила r;

- Jdi(F, q) – значение формулы F, получаемое в результате применения к ней подстановки q в состоянии dI;

- p(Jdi(t1,t2,...,tk, q)) – атомная формула, получаемая в результате выполнения подстановки q в вектор термов t1,t2,...,tk в состоянии di;

- d(NameMod(S1, …, Sk)) – состояние ПЛВ, полученное в результате вычисления модуля NameMod, состоит из множества формул и функциональных термов S1, …, Sk с константами;

- L(d) – множество всех возможных подстановок, сформированных на основе d.

Применимость правил определяется следующими правилами вывода. Если r1 – правило вида (1), то

ПВ1: $ r1 Î K & q Î L(d) & Jdi(P(X), q) = истина & ($ i1, …, ik S1i(Jdi(X1i, q)) Ï di & … & Smi(Jdi(Xmi, q)) Ï di & m £ k) Þ dN = di Ä {S1i(Jdi(X1i, q)), …, Smi(Jdi(Xmi, q))}, где Ä º È - операция объединения состояний среды, если S1i, …, Smi – объекты первого типа неопределенности, и Ä º /¢ - операция частичного исключения вариантов, если один из объектов из множества S1i, …, Smi является объектов второго типа неопределенности.

Если r2 – правило вида (2), то

ПВ2: $ r2 Î K & q Î L(d) & Jdi(P(X), q) = истина & d(NameMod(S1, …, Sk)) Ï di Þ dN = di È d(NameMod(S1, …, Sk)).

Процесс логического вывода завершается, если достигнуто такое состояние dE (конечное состояние), в котором правило вывода оказывается неприменимым ни при какой подстановке q и ни при каком правиле r Î K.


Заключение

В работе определена модель декларативных продукций как исчисление с входом порождающей модели. Данная модель обогащена средствами более компактной записи метода решения задач. С одной стороны, это кванторные конструкции, с другой схемы конкретизации схем и вызовы логических модулей. Все это позволяет получить понятный пользователю метод решения прикладной задачи в терминах предметной области. Конфлюентность системы продукций позволяет реализовать процесс логического вывода на многопроцессорных ЭВМ. Исследования схем распараллеливания вывода описаны в работах [4-6].

Литература

  1. Гаврилова Т.А., Хорошевский В.Ф. Базы знаний интеллектуальных систем. - Спб.: Питер, 2001.

  2. Клещев А.C., Артемьева И.Л. Необогащенные системы логических соотношений // НТИ. Сер. 2. - 2000. - № 7. - С.18-28.

  3. Клещев А.С., Артемьева И.Л. Математические модели онтологий предметных областей. Часть 1. Существующие подходы к определению понятия «онтология» // Научно–техническая информация, сер. 2. - 2001. - № 2. - с. 20–27.

  4. Артемьева И.Л., Тютюнник М.Б. Схемы распараллеливания вычислений для системы конфлюэнтных продукций // Информатика и системы управления. – 2005. - № 2(8). - C. 102-112.

  5. Артемьева И.Л., Тютюнник М.Б. Методы распараллеливания вычислений для системы параллельного программирования на основе декларативных продукций // Тр. II междунар. конф. "Параллельные вычисления и задачи управления". М.: ИПУ РАН, 2004. - С. 727-737.

  6. Тютюнник М.Б. Использование информационного графа при распараллеливании вычислений для системы конфлюэнтных продукций. // Информатика и системы управления. – 2006. - № 1(11). - C. 181-192.