Теория направленных отношений [1,2] является одним из подходов конструктивного построения таких формальных объектов, как функции, предикаты, программы, семантические сети и т.д. В рамках этого подхода, каждый из объектов может быть построен из базовых объектов путем операций композиции и оператора наименьшей фиксированной точки. Существуют различные версии языков программирования, в которых нашел отражение данный подход. Как и в любом языке программирования в этих языках встроен минимально-необходимый набор базовых объектов для описания любой предметной области. Кроме этого присутствуют конструкции для описания базовых объектов, спроектированных пользователем. В каждом из таких объектов заложены методы построения и вычисления, которые могут быть описаны как инструментом рассматриваемых языком, так и языками процедурного программирования.

Пусть D? ? , D^*W , где D^(i)W D? D? ...? D i-раз , D^(0)W {l } , где l — пустой кортеж.

Определение. Направленным отношением (d-отношением) называется график соответствия из D^* в D^* .

Последовательная композиция.

R_1· R₂={(a ,b ) | $ g ((a ,g )I R₁ & (g ,b )I R₂) } . Параллельная композиция.

R₁#R₂={(a _{1a 2},b _{1b 2}) | (a ₁,b ₁)I R₁ & (a ₂,b ₂)I R₂) }. Объединение d-отношений.

R_1E R₂={(a ,b ) | (a ,b )I R₁ U (a ,b )I R₂) }.

Оператор наименьшей фиксированной точки. Пусть X₁,X₂,...,X_n — переменные , r₁,r₂,...,r_m — константные отношения , t ₁,t ₂,...,t _n — термы, построенные путем композиции переменных и констант с помощью операций · , # , E по следующим правилам :

• X_i — терм, i=1,2,...,n ;
• r_i — терм, i=1,2,...,m ;
• Если t ? и t ? ? — термы, то (t ? · t ? ? ),(t ? #t ? ? ),(t ? E t ? ? ) — термы ;

Определение. Оператор наименьшей фиксированной точки как способ композиции отношений r₁,r₂,...,r_m синтаксически определяется как система:

{X_i=t _i(X1,X2,...,Xn,r1,r2,...,rm), i=1,2,...,n (1)

В общем случае, система (1) является рекурсивной и в интерпретации задает первый компонент кортежа d-отношений X₁^min,X₂^min,...,X_n^min , являющегося минимальной фиксированной точкой для системы уравнений (1), т.е.

{X_i^min = [ X_j^min / Xj | j=1,2,...,n]t _i, i=1,2,...,n (2)

и для всякого другого кортежа d-отношений X₁’,X₂’,...,X_n’ такого что X_i’= [ X_j^min / Xj | j=1,2,...,n] t _i , i=1,2,...,n выполнено X_i^min I X_i’ , i=1,2,...,n.

Определение. Базисом B элементов назовем тройку (A ,m ? ,m ? ? ), где A — конечное множество сортов элементов; m ? :A {0,1,2,...}, m ? ? :A {0,1,2,...} — задают арность элементов RI A , m ? (R) — количество входов , m ? ? (R) — количество выходов элемента сорта R .

Определение. Сетью S арности (m,n), m? 0, n? 0 в базисе элементов B называется пятерка (P,I,O,E,G), где P — конечное множество точек сети S; I — кортеж входных точек сети S, II P^*, |I|=m; O — кортеж выходных точек сети S, OI P^*, |O|=n; EI A ? P^* — множество элементов сети S такое, что для всех e? (R,q)I E: |q|=m ? (R)+m ? ? (R). Если e=(R,q? q? ? )I E и |q? |=m ? (R), |q? ? |=m ? ? (R), то e называется элементом сети сорта R, где q? — кортеж его входных точек, q? ? — кортеж выходных точек. GI P? P — граф семантического различия точек сети S (задает неравенство принимаемых ими в интерпретации или при вычислениях значений).

Определение. Сетевой КСГ (КССГ) называется четверка (B_T,B_H,a,P), где B_TC B_H=? ,

B_T — терминальный базис;

B_H — нетерминальный базис;

a — аксиома , aI B_H;

P — непустое множество правил порождения сетей (подстановок) вида: b_i® S_i, где b_iI B_H, S_i — сеть в базисе B_TE B_H.

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

Напомним, что (m,n)-арное d-отношение R(x₁,x₂,...,x_m)= (y₁,y₂,...,y_n)¹ в общем случае устанавливает неоднозначное соответствие из D₁'? D₂'? ...? D_m' в D₁"? D₂"? ...? D_n" , причем x_i и y_j пробегают значения D_i' и D_j" соответственно.

В общем виде запрос на вычисление R может быть сформулирован как требование для заданных значений некоторых входных переменных R (множество этих переменных может быть пустым) вычислить значения других (неозначенных) переменных, так что образованная таким образом пара кортежей — кортеж значений для входных переменных (заданных и вычисленных) и кортеж значений выходных переменных (также заданных и вычисленных) образуют пару кортежей, принадлежащую графику d-отношения R.

В логической форме запрос — это вычисление формулы $ z_1$ z₂...$ z_k (R(x₁,x₂,...,x_m)=(y₁,y₂,...,y_n)), т.е. вычисление z₁,z₂,...,z_k таких, для которых формула принимает значение "истина" (здесь z₁,z₂,...,z_k — неозначенные входные и выходные переменные R).

1. Однозначность конструкторов по входам (функциональность), которая выражается равенством · (c_i#c_i) = c_i· .
2. Однозначность по выходам (функциональность обратного конструктора): (c_i#c_i)· = c_i· .
3. Тотальность конструктора: c_{i ·} = .
4. Ортогональность различных конструкторов: (c_i#c_j)· =? .
5. Если в сети существует цикл, состоящий только из конструкторов, то такая сеть удаляется, т.е. интерпретируется как пустое d-отношение.

Известно [2], что для того, чтобы вычисление d-отношения осуществлялось корректно, ни одна из возникших возможностей редуцирования любой из порождаемых сетей не должна откладываться на неопределенное время. Кроме того, возможность одновременного редуцирования нескольких (при желании всех) сетей, порожденных на любом шаге вычислений, открывает большую свободу для выбора стратегии вычислений и их распараллеливания. С другой стороны, неоднозначность выбора правил редукции сетей, множественный характер их возможного применения, наконец большая вычислительная сложность самого алгоритма организации вычислительного процесса требуют при создании интерпретатора для языка направленных отношений уделять особое внимание стратегиям вычислений, которые оптимизируют как сам процесс, так и используемые вычислительные ресурсы. Многие аспекты этой проблемы в том числе применительно к параллельной реализации подобных вычислительных процессов на параллельных распределенных системах достаточно подробно обсуждались в [5].

Более сложной с точки зрения реализации, но более эффективной является стратегия, использующая независимость нетерминальных элементов в определении КССГ G.

Определение. Нетерминалы R’ и R" в задании грамматики G не зависимы, если [R']C [R"]=? (пусто).

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

1. Кутепов В.П. Фальк В.Н. Функциональные системы: теоретический и практический аспекты, Кибернетика №1 1979
2. Кутепов В.П. Фальк В.Н. Направленные отношения: теория и приложения, Техническая кибернетика, №4, №6, 1994
3. Стерлинг Л. Шапиро Э. Искусство программирования на языке Пролог: англ. — М . : Мир 1990.
4. Вагин В.Н.,Головина Е.Ю.,Оськин Ф.Ф. Модели и методы представления знаний в CASE-технологии.- Интеллектуальные системы. Том 2 выпуск 1-4. М.: Издательский центр РГГУ, 1997 с.115-134.
5. Кутепов В.П. Об интеллектуальных компьютерах и больших компьютерных системах нового поколения. Известия академии наук, Теория и системы управления, №5, 1996.