Логическое программирование

Продолжаем рассказ о создании мульти-парадигменного языка программирования, поддерживающего декларативный логический стиль для описания модели предметной области. Прошлые публикации находятся здесь и здесь. Теперь пришло время для описания основных особенностей и требований к языку описания модели предметной области. Но для начала сделаем небольшой обзор наиболее популярных языков представления знаний. Это довольно обширная область, имеющая давнюю историю и включающая ряд направлений логическое программирование, реляционное исчисление, технологии семантической паутины, фреймовые языки. Я хочу сравнить такие языки как Prolog, SQL, RDF, SPARQL, OWL и Flora, выделить те их особенности, которые были бы полезны в проектируемом мульти-парадигменном языке программирования.

Prolog.

Начнем с логического программирования и языка Prolog. Знания о предметной области представляются в нем в виде набора фактов и правил. Факты описывают непосредственные знания. Факты о клиентах (идентификатор, имя и адрес электронной почты) и счетах (идентификатор счета, клиента, дата, сумма к оплате и оплаченная сумма) из примера из прошлой публикации будут выглядеть следующим образом
client(1, "John", "john@somewhere.net").
bill(1, 1,"2020-01", 100, 50).
Правила описывают абстрактные знания, которые можно вывести из других правил и фактов. Правило состоит из головы и тела. В голове правила нужно задать его имя и список аргументов. Тело правила представляет собой список предикатов, соединенных логическими операциями AND (задается запятой) и OR (задается точкой с запятой). Предикатами могут служить факты, правила или встроенные предикаты, такие как операции сравнения, арифметические операции и др. Связь между аргументами головы правила и аргументами предикатов в его теле задается с помощью логических переменных если одна и та же переменная стоит на позициях двух разных аргументов, то значит, что эти аргументы идентичны. Правило считается истинным тогда, когда истинно логическое выражение тела правила. Модель предметной области можно задать в виде набора ссылающихся друг на друга правил:
unpaidBill(BillId, ClientId, Date, AmoutToPay, AmountPaid) :- bill(BillId, ClientId, Date, AmoutToPay, AmountPaid), AmoutToPay < AmountPaid.
debtor(ClientId, Name, Email) :- client(ClientId, Name, Email), unpaidBill(BillId, ClientId, _, _, _).
Мы задали два правила. В первом мы утверждаем, что все счета, у которых сумма к оплате меньше оплаченной суммы, являются неоплаченными счетами. Во втором, что должником является клиент, у которого есть хотя бы один неоплаченный счет.
Синтаксис Prolog очень простой: основной элемент программы правило, основные элементы правила это предикаты, логические операции и переменные. В правиле внимание сфокусированно на переменных они играют роль объекта моделируемого мира, а предикаты описывают их свойства и отношения между ними. В определении правила debtor мы утверждаем, что если объекты ClientId, Name и Email связанны отношениями client и unpaidBill, то они также будут связаны и отношением debtor. Prolog удобен в тех случаях, когда задача сформулирована в виде набора правил, утверждений или логических высказываний. Например, при работе с грамматикой естественного языка, компиляторами, в экспертных системах, при анализе сложных систем, таких как вычислительная техника, компьютерные сети, объекты инфраструктуры. Сложные, запутанные системы правил лучше описать в явном виде и предоставить среде исполнения Prolog разбираться с ними автоматически.

Prolog основан на логике первого порядка (с включением некоторых элементов логики высшего порядка). Логический вывод выполняется с помощью процедуры, называемой SLD резолюция (Selective Linear Definite clause resolution). Упрощенно ее алгоритм представляет собой обход дерева всех возможных решений. Процедура вывода находит все решения для первого предиката тела правила. Если текущий предикат в базе знаний представлен только фактами, то решениями являются те из них, которые соответствуют текущим привязкам переменных к значениям. Если правилами то потребуется рекурсивная проверка их вложенных предикатов. Если решений не найдено, то текущая ветвь поиска завершается неудачей. Затем для каждого найденного частичного решения создается новая ветвь. В каждой ветви процедура логического вывода выполняет привязку найденных значений к переменным, входящим в состав текущего предиката, и рекурсивно выполняет поиск решения для оставшегося списка предикатов. Работа завершается, если достигнут конец списка предикатов. Поиск решения может войти в бесконечный цикл в случае рекурсивного определения правил. Результатом работы процедуры поиска является список всех возможных привязок значений к логическим переменным.
В примере выше для правила debtor правило резолюции сначала найдет одно решение для предиката client и свяжет его с логическими переменными: ClientId = 1, Name = John, Email = john@somewhere.net. Затем для этого варианта значений переменных будет выполнен поиск решения для следующего предиката unpaidBill. Для этого потребуется сначала найти решения для предиката bill при условии, что ClientId = 1. Результатом будут привязки для переменных BillId = 1, Date = 2020-01, AmoutToPay = 100, AmountPaid = 50. В конце будет выполнена проверка AmoutToPay < AmountPaid во встроенном предикате сравнения.

Семантические сети.

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

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

RDF.

Семантическая паутина (semantic web) это попытка построить глобальную семантическую сеть на базе ресурсов Всемирной паутины путём стандартизации представления информации в виде, пригодном для машинной обработки. Для этого в HTML-страницы дополнительно закладывается информация в виде специальных атрибутов HTML тэгов, которая позволяет описать смысл их содержимого в виде онтологии набора фактов, абстрактных понятий и отношений между ними.
Стандартным подходом для описания семантической модели WEB ресурсов является RDF (Resource Description Framework или Среда Описания Ресурсов). Согласно ней все утверждения должны иметь форму триплета субъект предикат объект. Например, знания о понятии Кит будут представлены следующим образом: Кит является субъектом, живет в предикатом, Вода объектом. Весь набор таких утверждений можно описать с помощью ориентированного графа, субъекты и объекты являются его вершинами, а предикаты дугами, дуги предикатов направлены от объектов к субъектам. Например, онтологию из примера с животными можно описать в следующем виде:
@prefix : <...some URL...>
@prefix rdf: <http://www.w3.org/1999/02/rdf-schema#>
@prefix rdfs: <http://www.w3.org/2000/01/22-rdf-syntax-ns#>
:Whale rdf:type :Mammal;
:livesIn :Water.
:Fish rdf:type :Animal;
:livesIn :Water.
Такая форма записи называется Turtle, она предназначена для чтения человеком. Но то же самое можно записать и в XML, JSON форматах или с помощью тэгов и атрибутов HTML документа. Хоть в Turtle нотации предикаты и объекты можно сгруппировать вместе по субъектам для удобства чтения, но на семантическом уровне каждый триплет независим.
RDF удобен в тех случаях, когда модель данных сложна и содержит большое количество типов объектов и связей между ними. Например, Wikipedia предоставляет доступ к содержимому своих статей в RDF формате. Факты, описанные в статьях структурированы, описаны их свойства и взаимные отношения, включая факты из других статей.

RDFS

RDF модель представляет собой граф, по умолчанию никакой дополнительной семантики в нем не заложено. Каждый может интерпретировать заложенные в графе связи как посчитает нужным. Добавить в него некоторые стандартные связи можно с помощью RDF Schema набора классов и свойств для построения онтологий поверх RDF. RDFS позволяет описать стандартные отношения между понятиями, такие как принадлежность ресурса некоторому классу, иерархию между классами, иерархию свойств, ограничить возможные типы субъекта и объекта.
Например, утверждение
:Mammal rdfs:subClassOf :Animal.
задает, что Млекопитающее является подклассом понятия Животное и наследует все его свойства. Соответственно, понятие Кит также можно отнести к классу Животное. Но для этого нужно указать, что понятия Млекопитающее и Животное являются классами:
:Animal rdf:type rdfs:Class.
:Mammal rdf:type rdfs:Class.
Так же предикату можно задать ограничения на возможные значения его субъекта и объекта. Утверждение
:livesIn rdfs:range :Environment.
указывает, что объектом отношения живет в всегда должен быть ресурс, относящийся к классу Окружающая среда. Поэтому мы должны добавить утверждение о том, что понятие Вода является подклассом понятия Окружающая среда:
:Water rdf:type :Environment.
:Environment rdf:type rdfs:Class
RDFS позволяет описать схему данных перечислить классы, свойства, задать их иерархию и ограничения их значений. А RDF наполнить эту схему конкретными фактами и задать отношения между ними. Теперь мы можем задать вопрос к этому графу. Сделать это можно на специальном языке запросов SPARQL, напоминающем SQL:
SELECT ?creature
WHERE {
?creature rdf:type :Animal;
:livesIn :Water.
}
Этот запрос вернет нам 2 значения: Whale и Fish.

Пример из предыдущих публикаций со счетами и клиентами можно реализовать приблизительно следующим образом. С помощью RDF можно описать схему данных и наполнить ее значениями:
:Client1 :name "John";
:email "john@somewhere.net".
:Client2 :name "Mary";
:email "mary@somewhere.net".
:Bill_1 :client :Client1;
:date "2020-01";
:amountToPay 100;
:amountPaid 50.
:Bill_2 :client :Client2;
:date "2020-01";
:amountToPay 80;
:amountPaid 80.
Но вот абстрактные понятия, такие как Должник и Неоплаченные счета из первой статьи этого цикла, включают в себя арифметические операции и сравнение. Они не вписываются в статичную структуру семантической сети понятий. Эти понятия можно выразить с помощью SPARQL запросов:
SELECT ?clientName ?clientEmail ?billDate ?amountToPay ?amountPaid
WHERE {
?client :name ?clientName;
:email ?clientEmail.
?bill :client ?client;
:date ?billDate;
:amountToPay ?amountToPay;
:amountPaid ?amountPaid.
FILTER(?amountToPay > ?amountPaid).
}
Секция WHERE представляет собой список шаблонов триплетов и условий фильтрации. В триплеты можно подставлять логические переменные, имя которых начинается с символа "?". Задача исполнителя запроса найти все возможные значения переменных, при которых все шаблоны триплетов содержались бы в графе и выполнялись условия фильтрации.
В отличии от Prolog, где на основе правил можно конструировать другие правила, в RDF запрос не является частью семантической сети. На запрос нельзя ссылаться как на источник данных для другого запроса. Правда у SPARQL есть возможность представить результаты запроса в виде графа. Так что можно попробовать объединить результаты запроса с исходным графом и новый запрос выполнить на объединенном графе. Но такое решение будет явно выходить за рамки идеологии RDF.

OWL.

Важным компонентом технологий семантической паутины является OWL (Web Ontology Language) язык описания онтологий. С помощью словаря RDFS можно выразить только самые базовые отношения между понятиями иерархию классов и отношений. OWL предлагает гораздо более богатый словарь. Например, можно задать, что два класса (или две сущности) являются эквивалентными (или различными). Такая задача часто встречается при объединении онтологий.
Можно создавать составные классы на основе пересечения, объединения или дополнения других классов:

• При пересечении все экземпляры составного класса должны относиться и ко всем исходным классам. Например, Морское млекопитающее должно быть одновременно и Млекопитающим и Морским жителем.
• При объединении составной класс включает в себя все экземпляры исходных классов. Например, можно задать, что класс Животное является объединением классов Хищник, Травоядное и Всеядное. Все экземпляры этих классов будут заодно и Животными.
• При дополнении к составному классу относится все, что не относится к исходному. Например, класс Хладнокровное дополняет класс Теплокровное.
• Так же можно создавать классы на основе перечислений. Можно указать, что экземпляр составного класса обязательно должен быть экземпляром только одного из исходных классов.
• Можно задавать наборы непересекающихся классов если экземпляр относится к одному из них, то одновременно он не может относиться к остальным классам из набора.

Такие выражения, позволяющие связать понятия между собой, называются конструкторами.
OWL также позволяет задавать многие важные свойства отношений:

• Транзитивность. Если выполняются отношения P(x, y) и P(y, z), то обязательно выполняется и отношение P(x, z). Примерами таких отношений являются Больше-Меньше, Родитель-Потомок и т.п.
• Симметричность. Если выполняется отношение P(x, y), то обязательно выполняется и отношение P(y, x). Например, отношение Родственник.
• Функциональная зависимость. Если выполняются отношения P(x, y) и P(x, z), то значения y и z должны быть идентичными. Примером является отношение Отец у человека не может быть два разных отца.
• Инверсия отношений. Можно задать, что если выполняется отношение P1(x, y), то обязательно должно выполняться еще одно отношение P2(y, x). Примером таких отношений являются отношения Родитель и Потомок.
• Цепочки отношений. Можно задать, что если А связан неким свойством с В, а В с С, то А (или С) относится к заданному классу. Например, если у А есть отец В, а у отца В свой отец С, то А приходится внуком С.

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

Сейчас OWL является фактически стандартным средством для построения онтологий. Этот язык лучше подходит для построения больших и сложных онтологий чем RDFS. Синтаксис OWL позволяет выразить больше разных свойств понятий и отношений между ними. Но и вводит ряд дополнительных ограничений, например, одно и то же понятие нельзя одновременно объявить и как класс и как экземпляр другого класса. Онтологии в OWL жестче, более стандартизированы и, соответственно, более читабельны. Если RDFS это всего лишь несколько дополнительных классов поверх RDF графа, то OWL имеет другую математическую основу дескрипционную логику. Соответственно, становятся доступны и формальные процедуры логического вывода, позволяющие извлекать новую информацию из OWL онтологий, проверять их согласованность и отвечать на вопросы.

Дескрипционная или описательная логика (descriptive logic) является фрагментом логики первого порядка. В ней допустимы только одноместные (например, принадлежность понятия к классу), двухместные предикаты (наличие у понятия свойства и его значения), а также конструкторы классов и свойства отношений, перечисленные выше. Все остальные выражения логики первого порядка в дескрипционной логике отброшены. Например, допустимыми будут утверждения, что понятие Неоплаченный счет относится к классу Счет, понятие Счет имеет свойства Сумма к оплате и Оплаченная сумма. Но вот сделать утверждение, что у понятия Неоплаченный счет свойство Сумма к оплате должно быть больше свойства Оплаченная сумма уже не получится. Для этого понадобится правило, которое будет включать предикат сравнения этих свойств. К сожалению, конструкторы OWL не позволяют сделать это.
Таким образом, выразительность дискрипционной логики ниже, чем у логики первого порядка. Но, с другой стороны, алгоритмы логического вывода в дескрипционной логике гораздо быстрее. Кроме того, она обладает свойством разрешимости решение гарантированно может быть найдено за конечное время. Считается, что на практике такого словаря вполне достаточно для построения сложных и объемных онтологий, и OWL это хороший компромисс между выразительностью и эффективностью логического вывода.

Также стоит упомянуть SWRL (Semantic Web Rule Language), который сочетает возможность создания классов и свойств в OWL с написанием правил на ограниченной версии языка Datalog. Стиль таких правил такой же, как и в языке Prolog. SWRL поддерживает встроенные предикаты для сравнения, математических операций, работы со строками, датами и списками. Это как раз то, чего нам не хватало для того, чтобы с помощью одного простого выражения реализовать понятие Неоплаченный счет.

Flora-2.

В качестве альтернативы семантическим сетям рассмотрим также такую технологию как фреймы. Фрейм это структура, описывающая сложный объект, абстрактный образ, модель чего-либо. Он состоит из названия, набора свойств (характеристик) и их значений. Значением свойства может быть другой фрейм. Также у свойства может быть значение по умолчанию. К свойству может быть привязана функция вычисления его значения. В состав фрейма также могут входить служебные процедуры, в том числе обработчики таких событий так создание, удаление фрейма, изменение значения свойств и др. Важным свойством фреймов является возможность наследования. Дочерний фрейм включает в себя все свойства родительских фреймов.
Система связанных фреймов формирует семантическую сеть, очень похожую на RDF граф. Но в задачах создания онтологий фреймы были вытеснены языком OWL, который сейчас является фактическим стандартом. OWL более выразителен, имеет более продвинутое теоретическое основание формальную дискрипционную логику. В отличии от RDF и OWL, в которых свойства понятий описываются независимо друг от друга, в фреймовой модели понятие и его свойства рассматриваются как единой целое фрейм. Если в моделях RDF и OWL в вершинах графа находятся имена понятий, а в ребрах их свойства, то во фреймовой модели в вершинах графа расположены понятия со всеми их свойствами, а в ребрах связи между их свойствами или отношения наследования между понятиями.
В этом фреймовая модель очень близка модели объектно-ориентированного программирования. Они во многом совпадают, но имеют разную сферу применения фреймы направлены на моделирование сети понятий и отношений между ними, а ООП на моделирование поведения объектов, их взаимодействия между собой. Поэтому в ООП доступны дополнительные механизмы скрытия деталей реализации одного компонента от других, ограничения доступа к методам и полям класса.

Современные фреймовые языки (такие как KL-ONE, PowerLoom, Flora-2) комбинируют составные типы данных объектной модели с логикой первого порядка. В этих языках можно не только описывать структуру объектов, но и оперировать этими объектами в правилах, создавать правила, описывающие условия принадлежности объекта заданному классу и т.д. Механизмы наследования и композиции классов получают логическую трактовку, которая становится доступна для использования процедурам логического вывода. Выразительность этих языков выше, чем у OWL, они не ограничены двухместными предикатами.
В качестве примера попробуем реализовать наш пример с должниками на языке Flora-2. Этот язык включает в себя 3 компонента: фреймовую логику F-logic, объединяющую фреймы и логику первого порядка, логику высших порядков HiLog, предоставляющую инструменты для формирования высказываний о структуре других высказываний и мета-программирования, и логику изменений Transactional Logic, позволяющую в логической форме описывать изменения в данных и побочные эффекты (side effects) вычислений. Сейчас нас интересует только фреймовая логика F-logic. Для начала с ее помощью объявим структуру фреймов, описывающих понятия (классы) клиентов и должников:
client[|name => \string,
email => \string
|].
bill[|client => client,
date => \string,
amountToPay => \number,
amountPaid => \number,
amountPaid -> 0
|].
Теперь мы можем объявить экземпляры (объекты) этих понятий:
client1 : client[name -> 'John', email -> 'john@somewhere.net'].
client2 : client[name -> 'Mary', email -> 'mary@somewhere.net'].
bill1 : bill[client -> client1,
date -> '2020-01',
amountToPay -> 100
].
bill2 : bill[client -> client2,
date -> '2020-01',
amountToPay -> 80,
amountPaid -> 80
].
Символ '->' означает связь атрибута с конкретным значением у объекта и значение по умолчанию в объявлении класса. В нашем примере поле amountPaid класса bill имеет нулевое значение по умолчанию. Символ ':' означает создание сущности класса: client1 и client2 являются сущностями класса client.
Теперь мы можем объявить, что понятия Неоплаченный счет и Должник являются подклассами понятий Счет и Клиент:
unpaidBill :: bill.
debtor :: client.
Символ '::' объявляет отношение наследования между классами. Наследуется структура класса, методы и значения по умолчанию для всех его полей. Осталось объявить правила, задающие принадлежность к классам unpaidBill и debtor:
?x : unpaidBill :- ?x : bill[amountToPay -> ?a, amountPaid -> ?b], ?a > ?b.
?x : debtor :- ?x : client, ?_ : unpaidBill[client -> ?x].
В первом высказывании утверждается, что переменная ?х является сущностью класса unpaidBill, если она является сущностью класса bill, и значение ее поля amountToPay больше значения amountPaid. Во втором, что ?х относится к классу unpaidBill, если она относится к классу client и существует хотя бы одна сущность класса unpaidBill, у которой значение поля client равно переменной ?х. Эта сущность класса unpaidBill будет связана с анонимной переменной ?_, значение которой в дальнейшем не используется.
Получить список должников можно с помощью запроса:
?- ?x:debtor.
Мы просим найти все значения, относящиеся к классу debtor. Результатом будет список всех возможных значений переменной ?x:
?x = client1

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

SQL

Напоследок рассмотрим основные особенности синтаксиса SQL. В прошлой публикации мы говорили, что SQL имеет логическую теоретическую основу реляционное исчисление, и рассмотрели реализацию примера с должниками на LINQ. В плане семантики SQL близок к фреймовым языкам и ООП модели в реляционной модели данных основным элементом является таблица, которая воспринимается как единое целое, а не как набор отдельных свойств.
Синтаксис SQL прекрасно соответствует такой ориентации на таблицы. Запрос разбит на секции. Сущности модели, которые представлены таблицами, представлениями (view) и вложенными запросами, вынесены в секцию FROM. Связи между ними указываются с помощью операций JOIN. Зависимости между полями и другие условия находятся в секциях WHERE и HAVING. Вместо логических переменных, связывающих аргументы предикатов, в запросе мы оперируем полями таблиц напрямую. Такой синтаксис описывает структуру модели предметной области более наглядно по сравнению с линейным синтаксисом Prolog.

Каким я вижу стиль синтаксиса языка моделирования.

На примере со неоплаченными счетами мы можем сравнить такие подходы как логическое программирование (Prolog), фреймовую логику (Flora-2), технологии семантической паутины (RDFS, OWL и SWRL) и реляционное исчисление (SQL). Их основные характеристики я свел в таблицу:

Теперь нужно подобрать математическую основу и стиль синтаксиса для языка моделирования, предназначенного для работы со слабоструктурированными данными и интеграцией данных из разрозненных источников, который бы сочетался с объектно-ориентированными и функциональными языками программирования общего назначения.
Наиболее выразительными языками является Prolog и Flora-2 они основаны на полной логике первого порядка с элементами логики высших порядков. Остальные подходы являются ее подмножествами. За исключением RDFS он вообще не связан с формальной логикой. На данном этапе полноценная логика первого порядка мне видится предпочтительным вариантом. Для начала я планирую остановиться на нем. Но и ограниченный вариант в виде реляционного исчисления или логики дедуктивных баз данных тоже имеет свои преимущества. Он обеспечивает большую производительность при работе с большими объемами данных. В будущем его стоит рассмотреть отдельно. Дескрипционная логика выглядит слишком ограниченной и неспособной выразить динамические отношения между понятиями.
С моей точки зрения, для работы со слабоструктурированными данными и интеграции разрозненных источников данных фреймовая логика подходит больше, чем Prolog, ориентированный на правила, или OWL, ориентированный на связи и классы понятий. Фреймовая модель описывает структуры из объектов в явном виде, фокусирует на них внимание. В случае объектов с большим количеством свойств фреймовая форма гораздо более читабельна, чем правила или триплеты субъект-свойство-объект. Наследование также является очень полезным механизмом, позволяющим значительно сократить объем повторяющегося кода. По сравнению с реляционной моделью фреймовая логика позволяет описать сложные структуры данных, такие как деревья и графы, более естественным образом. И, самое главное, близость фреймовой модели описания знаний к модели ООП позволит интегрировать их в одном языке естественным образом.
У SQL я хочу позаимствовать структуру запроса. Определение понятия может иметь сложную форму и его не помешает разбить на секции, чтобы подчеркнуть его составные части и облегчить восприятие. Кроме того, для большинства разработчиков синтаксис SQL довольно привычен.

Итак, за основу языка моделирования я хочу взять фреймовую логику. Но поскольку целью является описание структур данных и интеграция разрозненных источников данных я попробую отказаться от синтаксиса, ориентированного на правила, и заменить его на структурированный вариант, позаимствованный у SQL. Основным элементом модели предметной области будет понятие (concept). В его определение я хочу включить всю информацию, необходимую для извлечения его сущностей (entities) из исходных данных:

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

Определение понятия будет напоминать SQL запрос. А вся модель предметной области будет иметь форму взаимосвязанных понятий.

Получившийся синтаксис языка моделирования я планирую показать в следующей публикации. Для тех, кто хочет познакомиться с ним уже сейчас, есть полный текст в научном стиле на английском языке, доступный по ссылке:
Hybrid Ontology-Oriented Programming for Semi-Structured Data Processing

Ссылки на предыдущие публикации:
Проектируем мульти-парадигменный язык программирования. Часть 1 Для чего он нужен?
Проектируем мульти-парадигменный язык программирования. Часть 2 Сравнение построения моделей в PL/SQL, LINQ и GraphQL

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

Во-первых, понятие, которое строится путем трансформации родительских понятий.
Во-вторых, объектно-ориентированный стиль подразумевает наследование значит понадобится механизм, позволяющий создавать понятие путем наследования атрибутов и отношений родительских понятий, расширяя или сужая их.
В-третьих, я считаю, что будет полезным механизм, позволяющий задать отношения между равноправными понятиями без разделения на дочернее и родительские понятия.
А теперь приступим к подробному рассмотрению основных типов понятий компоненты моделирования.

Начнем с фактов.

Факты представляют собой описание конкретных знаний о предметной области в виде именованного набора пар ключ-значение:
fact <имя факта> {
<имя атрибута> : <значение атрибута>
...
}
Например:
fact product {
name: Cabernet Sauvignon,
type: red wine,
country: Chile
}

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

Понятия.

Понятие представляет собой структуру, описывающую абстрактную сущность и основанную на других понятиях и фактах. Определение понятия включает в себя имя, списки атрибутов и дочерних понятий. А также логическое выражение, описывающее зависимости между его (дочернего понятия) атрибутами и атрибутами родительских понятий, позволяющие вывести значение атрибутов дочернего понятия:
concept <имя понятия> <псевдоним понятия> (
<имя атрибута> = <выражение>,
...
)
from
<имя родительского понятия> <псевдоним родительского понятия> (
<имя атрибута> = <выражение>
...
),

where <выражение отношений>
Пример определения понятия profit на основе понятий revenue и cost:
concept profit p (
value = r.value c.value,
date
) from revenue r, cost c
where p.date = r.date = c.date

Определение понятия похоже по форме на SQL запрос, но вместо имени таблиц нужно указывать имена родительских понятий, а вместо возвращаемых столбцов атрибуты дочернего понятия. Кроме того, понятие имеет имя, по которому к нему можно обращаться в определениях других понятий или в запросах к модели. Родительским понятием может быть как непосредственно понятие, так и факты. Выражение отношений в секции where это булево выражение, которое может включать логические операторы, условия равенства, арифметические операторы, вызовы функций и др. Их аргументами могут быть переменные, константы и ссылки на атрибуты как родительских так и дочернего понятий. Ссылки на атрибуты имеют следующий формат:
<псевдоним понятия>.<имя атрибута>
По сравнению с фреймовой логикой в определении понятия его структура (атрибуты) объединена с отношениями с другими понятиями (родительские понятия и выражение отношений). С моей точки зрения это позволяет сделать код более понятным, так как вся информация о понятии собрана в одном месте. А также соответствует принципу инкапсуляции в том смысле, что детали реализации понятия скрыты внутри его определения. Для сравнения небольшой пример на языке фреймовой логики можно найти в прошлой публикации.
Выражение отношений имеет конъюнктивную форму (состоит из выражений, соединенных логическими операциями AND) и должно включать условия равенства для всех атрибутов дочернего понятия, достаточные для определения их значений. Кроме того, в него могут входить условия, ограничивающие значения родительских понятий или связывающие их между собой. Если в секции where будут связаны между собой не все родительские понятия, то механизм логического вывода вернет все возможные комбинации их значений в качестве результата (аналогично операции FULL JOIN языка SQL).
Для удобства часть условий равенства атрибутов может быть вынесена в секции атрибутов дочернего и родительских понятий. Например, в определении понятия profit условие для атрибута value вынесено в секцию атрибутов, а для атрибута date оставлено в секции where. Также можно перенести их и в секцию from:
concept profit p (
value = r.value c.value,
date = r.date
) from revenue r, cost c (date = r.date)
Такой синтаксический сахар позволяет сделать зависимости между атрибутами более явными и выделить их из остальных условий.

Понятия соответствуют правилам в Prolog но имеют немного другую семантику. Prolog делает акцент на построении логически связанных высказываний и вопросам к ним. Понятия же в первую очередь предназначены для структурирования входных данных и извлечения информации из них. Атрибуты понятий соответствуют аргументам термов Prolog. Но если в Prolog аргументы термов связываются с помощью переменных, то в нашем случае к атрибутам можно непосредственно обращаться по их именам.

Поскольку список родительских понятий и условия отношений разнесены по отдельным секциям, логический вывод будет немного отличаться от такового в Prolog. Опишу в общем виде его алгоритм. Вывод родительских понятий будет выполнен в том порядке, в котором они указаны в секции from. Поиск решения для следующего понятия выполняется для каждого частичного решения предыдущих понятий так же, как и в SLD резолюции. Но для каждого частичного решения выполняется проверка истинности выражения отношений из секции where. Поскольку это выражение имеет форму конъюнкции, то каждое подвыражение проверяется отдельно. Ели подвыражение ложно, то данное частичное решение отвергается и поиск переходит к следующему. Если часть аргументов подвыражения еще не определена (не связана со значениями), то его проверка откладывается. Если подвыражением является оператор равенства и определен только один из его аргументов, то система логического вывода найдет его значение и попытается связать его с оставшимся аргументом. Это возможно, если свободным аргументом является атрибут или переменная.
Например, при выводе сущностей понятия profit сначала будут найдены сущности понятия revenue, и, соответственно, значения его атрибутов. После чего равенство p.date = r.date = c.date в секции where даст возможность связать со значениями атрибуты date и других понятий. Когда логический поиск доберется до понятия cost, значение его атрибута date будет уже известно и будет является входным аргументом для этой ветви дерева поиска. Подробно рассказать об алгоритмах логического вывода я планирую в одной из следующих публикаций.
Отличие от Prolog заключается в том, что в правилах Prolog все является предикатами и обращения к другим правилам и встроенные предикаты равенства, сравнения и др. И порядок их проверки нужно указывать явным образом, например, сначала должны идти два правила а затем равенство переменных:
profit(value,date) :- revenue(rValue, date), cost(cValue, date), value = rValue cValue
В таком порядке они и будут выполнены. В компоненте моделирования же предполагается, что все вычисления условий в секции where являются детерминированными, то есть не требуют рекурсивного погружения в следующую ветвь поиска. Поскольку их вычисление зависит только от их аргументов, они могут быть вычислены в произвольном порядке по мере связывания аргументов со значениями.

В результате логического вывода все атрибуты дочернего понятия должны быть связаны со значениями. А также выражение отношений должно быть истинно и не содержать неопределенных подвыражений. Стоит заметить, что вывод родительских понятий не обязательно должен быть успешным. Допустимы случаи, когда требуется проверить неудачу выведения родительского понятия из исходных данных, например, в операциях отрицания. Порядок родительских понятий в секции from определяет порядок обхода дерева решений. Это дает возможность оптимизировать поиск решения, начав его с тех понятий, которые сильнее ограничивают пространство поиска.
Задача логического вывода найти все возможные подстановки атрибутов дочернего понятия и каждую из них представить в виде объекта. Такие объекты считаются идентичными если совпадают имена их понятий, имена и значения атрибутов.

Допустимым считается создание нескольких понятий с одинаковым именем, но с разной реализацией, включая различный набор атрибутов. Это могут быть разные версии одного понятия, родственные понятия, которые удобно объединить под одним именем, одинаковые понятия из разных источников и т.п. При логическом выводе будут рассмотрены все существующие определения понятия, а результаты их поиска будут объединены. Несколько понятий с одинаковыми именами аналогичны правилу в языке Prolog, в котором список термов имеет дизъюнктивную форму (термы связаны операцией ИЛИ).

Наследование понятий.

Одними из наиболее распространенных отношений между понятиями являются иерархические отношения, например род-вид. Их особенностью является то, что структуры дочернего и родительского понятий будут очень близки. Поэтому поддержка механизма наследования на уровне синтаксиса очень важна, без нее программы будут переполнены повторяющимся кодом. При построении сети понятий было бы удобно повторно использовать как их атрибуты, так и отношения. Если список атрибутов легко расширять, сокращать или переопределять некоторые из них, то с модификацией отношений дело обстоит сложнее. Поскольку они представляют собой логическое выражение в конъюнктивной форме, то к нему легко прибавить дополнительные подвыражения. Но удаление или изменение может потребовать значительного усложнения синтаксиса. Польза от этого не так очевидна, поэтому отложим эту задачу на будущее.
Объявить понятие на основе наследования можно с помощью следующей конструкции:
concept <имя понятия> <псевдоним понятия> is
<имя родительского понятия> <псевдоним родительского понятия> (
<имя атрибута> = <выражение>,
...
),
...
with <имя атрибута> = <выражение>, ...
without <имя родительского атрибута>, ...
where <выражение отношений>
Секция is содержит список наследуемых понятий. Их имена можно указать напрямую в этой секции. Или же указать полный список родительских понятий в секции from, а в is псевдонимы только тех из них, которые будут наследоваться:
concept <имя понятия> <псевдоним понятия> is
<псевдоним родительского понятия>,

from
<имя родительского понятия> <псевдоним родительского понятия> (
<имя атрибута> = <выражение>
...
),

with <имя атрибута> = <выражение>, ...
without <имя родительского атрибута>, ...
where <выражение отношений>
Секция with позволяет расширить список атрибутов наследуемых понятий или переопределить некоторые из них, секция without сократить.

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

Рассмотрим несколько примеров использования механизма наследования. Наследование позволяет создать понятие на основе уже существующего избавившись от тех атрибутов, которые имеют смысл только для родительского, но не для дочернего понятия. Например, если исходные данные представлены в виде таблицы, то ячейкам определенных столбцов можно дать свои имена (избавившись от атрибута с номером столбца):
concept revenue is tableCell without columnNum where columnNum = 2
Также можно преобразовать несколько родственных понятий в одну обобщенную форму. Секция with понадобится для того, чтобы преобразовать часть атрибутов к общему формату и добавить недостающие. Например, исходными данными могут быть документы разных версий, список полей которых менялся со временем:
concept resume is resumeV1 with skills = 'N/A'
concept resume is resumeV2 r with skills = r.coreSkills
Предположим, что в первой версии понятия Резюме не было атрибута с навыками, а во второй он назывался по-другому.
Расширение списка атрибутов может потребоваться во многих случаях. Распространенными задачами являются смена формата атрибутов, добавление атрибутов, функционально зависящих от уже существующих атрибутов или внешних данных и т.п. Например:
concept price is basicPrice with valueUSD = valueEUR * getCurrentRate('USD', 'EUR')
Также можно просто объединить несколько понятий под одним именем не меняя их структуру. Например, для того чтобы указать, что они относятся к одному роду:
concept webPageElement is webPageLink
concept webPageElement is webPageInput
Или же создать подмножество понятия, отфильтровав часть его сущностей:
concept exceptionalPerformer is employee where performanceEvaluationScore > 0.95

Возможно также множественное наследование, при котором дочернее понятие наследует атрибуты всех родительских понятий. При наличии одинаковых имен атрибутов приоритет будет отдан тому родительскому понятию, которое находится в списке левее. Также можно решить этот конфликт вручную, явно переопределив нужный атрибут в секции with. Например, такой вид наследования был бы удобен, если нужно собрать в одной плоской структуре несколько связанных понятий:
concept employeeInfo is employee e, department d where e.departmentId = d.id

Наследование без изменения структуры понятий усложняет проверку идентичности объектов. В качестве примера рассмотрим определение exceptionalPerformer. Запросы к родительскому (employee) и дочернему (exceptionalPerformer) понятиям вернут одну и ту же сущность сотрудника. Объекты, представляющие ее, будут идентичны по смыслу. У них будет общий источник данных, одинаковый список и значения атрибутов, на разное имя понятия, зависящее от того, к какому понятию был выполнен запрос. Поэтому операция равенства объектов должна учитывать эту особенность. Имена понятий считаются равными, если они совпадают или связаны транзитивным отношением наследования без изменения структуры.

Наследование это полезный механизм, позволяющий выразить явным образом такие отношения между понятиями как класс-подкласс, частное-общее, множество-подмножество. А также избавиться от дублирования кода в определениях понятий и сделать код более понятным. Механизм наследования основан на добавлении/удалении атрибутов, объединении нескольких понятий под одним именем и добавлении условий фильтрации. Никакой специальной семантики в него не вкладывается, каждый может воспринимать и применять его как хочет. Например, построить иерархию от частного к общему как в примерах с понятиями resume, price и webPageElement. Или, наоборот, от общего к частному, как в примерах с понятиями revenue и exceptionalPerformer. Это позволит гибко подстроиться под особенности источников данных.

Понятие для описания отношений.

Было решено, что для удобства понимания кода и облегчения интеграции компоненты моделирования с ООП моделью, отношения дочернего понятия с родительскими должны быть встроены в его определение. Таким образом, эти отношения задают способ получения дочернего понятия из родительских. Если модель предметной области строится слоями, и каждый новый слой основан на предыдущем, это оправдано. Но в некоторых случаях отношения между понятиями должны быть объявлены отдельно, а не входить в определение одного из понятий. Это может быть универсальное отношение, которое хочется задать в общем виде и применить к разным понятиям, например, отношение Родитель-Потомок. Либо отношение, связывающее два понятия, необходимо включить в определение обоих понятий, чтобы можно было бы найти как сущности первого понятия при известных атрибутах второго, так и наоборот. Тогда, во избежание дублирования кода отношение удобно будет задать отдельно.
В определении отношения необходимо перечислить входящие в него понятия и задать логическое выражение, связывающее их между собой:
relation <имя отношения>
between <имя вложенного понятия> <псевдоним вложенного понятия> (
<имя атрибута> = <выражение>,
...
),
...
where <логическое выражение>
Например, отношение, описывающее вложенные друг в друга прямоугольники, можно определить следующим образом:
relation insideSquareRelation between square inner, square outer
where inner.xLeft > outer.xLeft and inner.xRight < outer.xRight
and inner.yBottom > outer.yBottom and inner.yUp < outer.yUp
Такое отношение, по сути, представляет собой обычное понятие, атрибутами которого являются сущности вложенных понятий:
concept insideSquare (
inner = i
outer = o
) from square i, square o
where i.xLeft > o.xLeft and i.xRight < o.xRight
and i.yBottom > o.yBottom and i.yUp < o.yUp

Отношение можно использовать в определениях понятий наряду с другими родительскими понятиями. Понятия, входящие в отношения, будут доступны извне и будут играть роль его атрибутов. Имена атрибутов будут соответствовать псевдонимам вложенных понятий. В следующем примере утверждается, что в HTML форму входят те HTML элементы, которые расположены внутри нее на HTML странице:
сoncept htmlFormElement is e
from htmlForm f, insideSquareRelation(inner = e, outer = f), htmlElement e
При поиске решения сначала будут найдены все значения понятия htmlForm, затем они будут связаны со вложенным понятием outer отношения insideSquare и найдены значения его атрибута inner. А в конце будут отфильтрованы те значения inner, которые относятся к понятию htmlElement.

Отношению можно придать и функциональную семантику использовать его как функцию булева типа для проверки, выполняется ли отношение для заданных сущностей вложенных понятий:
сoncept htmlFormElement is e
from htmlElement e, htmlForm f
where insideSquareRelation(e, f)
В отличие от предыдущего случая, здесь отношение рассматривается как функция, что повлияет на порядок логического вывода. Вычисление функции будет отложено до того момента, когда все ее аргументы будут связаны со значениями. То есть, сначала будут найдены все комбинации значений понятий htmlElement и htmlForm, а затем отфильтрованы те из них, которые не соответствуют отношению insideSquareRelation. Более подробно об интеграции логической и функциональной парадигм программирования я планирую рассказать в одной из следующих публикаций.

Теперь пришло время рассмотреть небольшой пример.

Определений фактов и основных видов понятий достаточно, чтобы реализовать пример с должниками из первой публикации. Предположим, что у нас есть два файла в формате CSV, хранящих информацию о клиентах (идентификатор клиента, имя и адрес электронной почты) и счетах (идентификатор счета, идентификатор клиента, дата, сумма к оплате, оплаченная сумма).
А также имеется некая процедура, которая считывает содержимое этих файлов и преобразовывает их в набор фактов:
fact cell {
table: TableClients,
value: 1,
rowNum: 1,
columnNum: 1
};
fact cell {
table: TableClients,
value: John,
rowNum: 1,
columnNum: 2
};
fact cell {
table: TableClients,
value: john@somewhere.net,
rowNum: 1,
columnNum: 3
};

fact cell {
table: TableBills,
value: 1,
rowNum: 1,
columnNum: 1
};
fact cell {
table: TableBills,
value: 1,
rowNum: 1,
columnNum: 2
};
fact cell {
table: TableBills,
value: 2020-01-01,
rowNum: 1,
columnNum: 3
};
fact cell {
table: TableBills,
value: 100,
rowNum: 1,
columnNum: 4
};
fact cell {
table: TableBills,
value: 50,
rowNum: 1,
columnNum: 5
};

Для начала дадим ячейкам таблиц осмысленные имена:
concept clientId is cell where table = TableClients and columnNum = 1;
concept clientName is cell where table = TableClients and columnNum = 2;
concept clientEmail is cell where table = TableClients and columnNum = 3;
concept billId is cell where table = TableBills and columnNum = 1;
concept billClientId is cell where table = TableBills and columnNum = 2;
concept billDate is cell where table = TableBills and columnNum = 3;
concept billAmountToPay is cell where table = TableBills and columnNum = 4;
concept billAmountPaid is cell where table = TableBills and columnNum = 5;

Теперь можно объединить ячейки одной строки в единый объект:
concept client (
id = id.value,
name = name.value,
email = email.value
) from clientId id, clientName name, clientEmail email
where id.rowNum = name.rowNum = email.rowNum;

concept bill (
id = id.value,
clientId = clientId.value,
date = date.value,
amountToPay = toPay.value,
amountPaid = paid.value
) from billId id, billClientId clientId, billDate date, billAmountToPay toPay, billAmountPaid paid
where id.rowNum = clientId.rowNum = date.rowNum = toPay.rowNum = paid.rowNum;

Введем понятия Неоплаченный счет и Должник:
concept unpaidBill is bill where amountToPay > amountPaid;
concept debtor is client c where exist(unpaidBill {clientId: c.id});

Оба определения используют наследование, понятие unpaidBill является подмножеством понятия bill, debtor понятия client. Определение понятия debtor содержит вложенный запрос к понятию unpaidBill. Подробно механизм вложенных запросов мы рассмотрим позже в одной следующих публикаций.
В качестве примера плоского понятия определим также понятие Долг клиента, в котором объединим некоторые поля из понятия Клиент и Счет:
concept clientDebt (
clientName = c.name,
billDate = b.date,
debt = b. amountToPay b.amountPaid
) from unpaidBill b, client c(id = b.client);

Зависимость между атрибутами понятий client и bill вынесена в секцию from, а зависимости дочернего понятия clientDebt в секцию его атрибутов. При желании все они могут быть помещены в секцию where результат будет аналогичным. Но с моей точки зрения текущий вариант более краток и лучше подчеркивает назначение этих зависимостей определять связи между понятиями.

Теперь попробуем определить понятие злостного неплательщика, который имеет как минимум 3 неоплаченных счета подряд. Для этого понадобится отношение, позволяющее упорядочить счета одного клиента по их дате. Универсальное определение будет выглядеть следующим образом:
relation billsOrder between bill next, bill prev
where next.date > prev.date and next.clientId = prev.clientId and not exist(
bill inBetween
where next.clientId = inBetween.clientId
and next.date > inBetween.date > prev.date
);
В нем утверждается, что два счета идут подряд, если они принадлежат одному клиенту, дата одного больше даты другого и не существует другого счета, лежащего между ними. На данном этапе я не хочу останавливаться на вопросах вычислительной сложности такого определения. Но если, например, мы знаем, что все счета выставляются с интервалом в 1 месяц, то можно его значительно упростить:
relation billsOrder between bill next, bill prev
where next.date = prev.date + 1 month and next.clientId = prev.clientId;

Последовательность из 3х неоплаченных счетов будет выглядеть следующим образом:
concept unpaidBillsSequence (clientId = b1.clientId, bill1 = b1, bill2 = b2, bill3 = b3)
from
unpaidBill b1,
billsOrder next1 (next = b1, prev = b2)
unpaidBill b2
billsOrder next2 (next = b2, prev = b3)
unpaidBill b3;
В этом понятии сначала будет найдены все неоплаченные счета, затем для каждого из них с помощью отношения next1 будет найден следующий счет. Понятие b2 позволит проверить, что этот счет является неоплаченным. По этому же принципу с помощью next2 и b3 будет найден и третий неоплаченный счет подряд. Идентификатор клиента вынесен в список атрибутов отдельно, чтобы в дальнейшем облегчить связывание этого понятия с понятием клиентов:
concept hardCoreDefaulter is client c where exist(unpaidBillsSequence{clientId: c.id});

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

Краткие выводы.

Итак, я предложил три основных вида понятий компоненты моделирования гибридного языка:

• понятия, созданные на основе трансформации других понятий;
• понятия, наследующие структуру и отношения других понятий;
• понятия, задающие отношения между другими понятиями.

Эти три вида понятий имеют разную форму и назначение, но внутренняя логика поиска решений у них одинакова, различается только способ формирования списка атрибутов.
Определения понятий напоминают SQL запросы как по форме, так и по внутренней логике исполнения. Поэтому я надеюсь, что предложенный язык будет понятен разработчикам и иметь относительно низкий порог входа. А дополнительные возможности, такие как использование понятий в определениях других понятий, наследование, вынесенные отношения и рекурсивные определения позволят выйти за рамки SQL и облегчат структурирование и повторное использование кода.

В отличии от языков RDF и OWL, компонента моделирования не делает различия между понятиями и отношениями все является понятиями. В отличии от языков фреймовой логики фреймы, описывающие структуру понятия, и правила, задающие связи между ними, объединены вместе. В отличии от традиционных языков логического программирования, таких как Prolog основным элементом модели являются понятия, имеющие объектно-ориентированную структуру, а не правила, имеющие плоскую структуру. Такой дизайн языка может быть не так удобен для создания масштабных онтологий или набора правил, но зато гораздо лучше подходит для работы со слабоструктурированными данными и для интеграции разрозненных источников данных. Понятия компоненты моделирования близки к классам ООП модели, что должно облегчить задачу включения декларативного описания модели в код приложения.

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

Полный текст в научном стиле на английском языке доступен по ссылке: papers.ssrn.com/sol3/papers.cfm?abstract_id=3555711

Ссылки на предыдущие публикации:
Проектируем мульти-парадигменный язык программирования. Часть 1 Для чего он нужен?
Проектируем мульти-парадигменный язык программирования. Часть 2 Сравнение построения моделей в PL/SQL, LINQ и GraphQL
Проектируем мульти-парадигменный язык программирования. Часть 3 Обзор языков представления знаний

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

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

А сейчас я предлагаю окунуться в некоторые нюансы логического программирования. Поскольку язык компоненты моделирования имеет декларативную логическую форму, то придется решить такие проблемы, как определение семантики оператора отрицания, внедрение элементов логики высших порядков и добавление возможности работы с логическими переменными. А для этого придется разобраться с такими теоретическими вопросами как предположение об открытости/замкнутости мира, отрицание как отказ, семантикой стойких моделей (stable model semantics) и обоснованной семантикой (well-founded semantics). А также с тем, как реализованы возможности логики высших порядков в других языках логического программирования.

Начнем с логических переменных.

В большинстве языков логического программирования переменные используются как символическое обозначение (placeholder) произвольных высказываний. Они встречаются на позициях аргументов предикатов и связывают предикаты между собой. Например, в следующем правиле языка Prolog переменные играют роль объектов X и Y, связанных между собой отношениями: brother, parent, male и неравенством:
brothers(X,Y) :- parent(Z,X), parent(Z,Y), male(X), male(Y), X\=Y.
В компоненте моделирования роль аргументов термов в первую очередь играют атрибуты понятий:
concept brothers (person1, person2) FROM
parent p1 (child = person1),
parent p2 (child = person2),
male(person: person1),
male(person: person2)
WHERE p1.parent = p2.parent AND person1 != person2
К ним можно обращаться по имени напрямую, как в языке SQL. Хоть предлагаемый синтаксис и выглядит более громоздко по сравнению с Prolog, но в случае большого количества атрибутов такой вариант будет удобнее, так как он подчеркивает структуру объекта.

Но в некоторых случаях все-таки было бы удобно объявить логическую переменную, которая бы не входила в состав атрибутов ни одного из понятий, но в то же время использовалась в выражении отношений. Например, если подвыражение имеет сложный вид, то можно разбить его на составные части связав их с логическими переменными. Также если подвыражение используется несколько раз, то можно объявить его только один раз связав его с переменной. И в дальнейшем использовать переменную вместо выражения. Для того, чтобы отличить логические переменные от атрибутов понятия и переменных компоненты вычислений, примем решение, что имена логических переменных должны начинаться с символа $.
В качестве примера можно разобрать понятие, задающее принадлежность точки кольцу, которое описывается внешним и внутренним радиусами. Расстояние от точки до центра кольца можно рассчитать один раз, связать с переменной и сравнить ее с радиусами:
relation pointInRing between point p, ring r
where $dist <= r.rOuter
and $dist >= r.rInner
and $dist = Math.sqrt((p.x r.x) * (p.x r.x) + (p.y r.y) * (p.y r.y))
При этом само это расстояние несет вспомогательную роль и в состав понятия входить не будет.

Отрицание.

Теперь рассмотрим более сложный вопрос реализацию оператора отрицания в рамках компоненты моделирования. Системы логического программирования обычно включают кроме оператора булева отрицания еще и правило отрицания как отказа. Оно позволяет вывести not p в случае неудачи выведения p. В разных системах представления знаний как смысл, так и алгоритм правила вывода отрицания может отличаться.

Для начала необходимо ответить на вопрос о характере системы знаний с точки зрения ее полноты. В системах, придерживающихся предположения об открытости мира, база знаний считается неполной, поэтому утверждения, отсутствующие в ней, считаются неизвестными. Утверждение not p можно вывести только в том случае, если в базе знаний в явном виде хранится утверждение о том, что p ложно. Такое отрицание называется сильным. Отсутствующие утверждения считаются неизвестными, а не ложными. Примером системы знаний, использующей такое предположение, является семантическая паутина (Semantic WEB). Это общедоступная глобальная семантическая сеть, формируемая на базе Всемирной паутины. Информация в ней по определению неполна она оцифрована и переведена в машиночитаемую форму далеко не в полном объеме, разнесена по разным узлам и постоянно дополняется. Например, если в Википедии в статье о Тиме Бернерсе-Ли, создателе всемирной паутины и авторе концепции семантической паутины, ничего не сказано о его кулинарных предпочтениях, то это не значит, что у него их нет, просто статья неполна.

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

Полные базы знаний имеют свои преимущества. Во-первых, нет необходимости кодировать неизвестную информацию достаточно двухзначной логики (истина, ложь) вместо трехзначной (истина, ложь, неизвестно). Во-вторых, можно объединить оператор булева отрицания и проверку выводимости высказывания из базы знаний в один оператор отрицания как отказ (negation as failure). Он вернет истину не только, если хранится утверждение о ложности высказывания, но также если в базе знаний нет о нем сведений вообще. Например, из
правила
p < not q
будет выведено, что q ложно (поскольку нет утверждения, что оно истинно), а p истинно.

К сожалению, семантика отрицания как отказа не так очевидна и сложнее, чем кажется. В разных системах логического программирования его смысл имеет свои особенности. Например, в случае циклических определений:
p not q
q not p
классическая SLDNF резолюция (SLD + Negation as Failure), применяемая в языке Prolog, не сможет завершиться. Вывод утверждения p нуждается в выводе q, а q в p, процедура вывода попадет в бесконечный цикл. В Prolog такие определения считаются не допустимыми, а база знаний не согласованной.
В то же время для нас эти утверждения не составляют проблемы. Интуитивно мы понимаем эти два правила как утверждение, что p и q имеют противоположные значения, если одно из них будет истинным, то второе ложным. Поэтому желательно, чтобы оператор отрицания как отказа умел работать с подобными правилами, чтобы конструкции логических программ были более естественными и понятными для человека.
Кроме того, согласованность базы знаний не всегда достижима. Например, иногда определения правил специально отделяют от фактов, чтобы один и тот же набор правил можно было бы применить к разным наборам фактов. В этом случае нет гарантии, что правила будут согласованы со всеми возможными наборами фактов. Также иногда допустима и несогласованность правил самих по себе, например, если они составляются разными экспертами.

Наиболее известными походами, позволяющими формализовать логический вывод в условиях циклических определений и несогласованности программы, являются Семантика устойчивых моделей (Stable model semantics) и Обоснованная семантика (Well-founded semantics).
Правило логического вывода с семантикой стойких моделей исходит из предположения, что некоторые операторы отрицания в программе можно проигнорировать, если они не согласуются с остальной частью программы. Поскольку таких согласованных подмножеств исходного набора правил может быть несколько, то, соответственно и вариантов решений может быть несколько. Например, в определении выше логический вывод можно начать с первого правила (p not q), отбросить второе (q not p) и получить решение {p, not q}. А затем проделать тоже и для второго и получить {q, not p}. Общим решением будет объединенный набор альтернативных решений. Например, из правил:
person(alex)
alive(X) person(X)
male(X) person(X) AND NOT female(X)
female(X) person(X) AND NOT male(X)
мы можем вывести два варианта ответа: {person(alex), alive(alex), male(alex)} и {person(alex), alive(alex), female(alex)}.
Обоснованная семантика исходит из тех же предположений, но стремится найти одно общее частичное решение, удовлетворяющее всем альтернативным согласованным подмножествам правил. Частичное решение означает, что значения истина или ложь будут выведены только для части фактов, а значения остальных останутся неизвестными. Таким образом, в описании фактов в программе используется двухзначная логика, а в процессе вывода трехзначная. Для рассмотренных выше правил значения обоих высказываний p и q будут неизвестны. Но, например, для
p not q
q not p
r s
s
можно с уверенностью вывести, что r и s истинны, хоть p и q остаются неизвестными.
Например, из примера с alex мы можем вывести {person(alex), alive(alex)}, в то время как утверждения male(alex) и female{alex} останутся неизвестными.

В языке SQL операторы булева отрицания (NOT) и проверки выводимости (NOT EXISTS) разделены. Эти операторы применяются к аргументам разного типа: NOT инвертирует булево значение, а EXISTS/NOT EXISTS проверяет результат выполнения вложенного запроса на пустоту, поэтому объединять их не имеет смысла. Семантика операторов отрицания в SQL очень проста и не рассчитана на работу с рекурсивными или сложными несогласованными запросами, при особой сноровке SQL запрос можно отправить в бесконечную рекурсию. Но сложные логические конструкции явно выходят за рамки традиционной сферы применения SQL, поэтому в изощренной семантике операторов отрицания он не нуждается.

Теперь попробуем разобраться с семантикой операторов отрицания компоненты моделирования проектируемого гибридного языка.
Во-первых, компонента моделирования предназначена для интеграции разрозненных источников данных. Они могут быть очень разнообразными и иметь как полный, так и неполный характер. Поэтому операторы проверки выводимости однозначно нужны.
Во-вторых, форма понятий компоненты моделирования гораздо ближе к запросам SQL, чем к правилам логического программирования. Понятие тоже имеет сложную структуру, поэтому смешение в одном операторе булева отрицания и проверки выводимости понятия не имеет смысла. Булево отрицание имеет смысл применять только к атрибутам, переменным и результатам вычисления выражений они могут быть как ложными, так и истинными. К понятию применить его сложнее, оно может состоять из разных атрибутов и не ясно, какой из них должен отвечать за ложность или истинность понятия целиком. Выводимым из исходных данных может быть понятие целиком, а не отдельные его атрибуты. В отличие от SQL, где структура таблиц фиксирована, структура понятий может быть гибкой, понятие может вообще не иметь требуемого атрибута в своем составе, поэтому понадобится еще и проверка существования атрибута.
Поэтому имеет смысл ввести отдельные операторы для каждого вида отрицаний, перечисленных выше. Ложность атрибутов можно проверить с помощью с помощью традиционного булева оператора NOT, содержит ли понятие атрибут с помощью встроенной функции DEFINED, а результат выведения понятия из исходных данных с помощью функции EXISTS. Три отдельных оператора более предсказуемы, понятны и просты в использовании, чем комплексный оператор отрицания как отказа. При необходимости их можно объединить в один оператор тем или иным способом, имеющим смысл для каждого конкретного случая.
В-третьих, на данный момент компонента моделирования видится инструментом для создания небольших онтологий прикладного уровня. Ее языку вряд ли потребуется особенная логическая выразительность и изощренные правила вывода, способные справиться с рекурсивными определениями и логической несогласованностью программы. Поэтому реализация сложных правил вывода на основе семантики стойких моделей или обоснованной семантики выглядит не целесообразной, по крайней мере на данном этапе. Классической SLDNF резолюции должно быть достаточно.

А теперь рассмотрим несколько примеров.
Понятию можно придать негативный смысл, если определенные его атрибуты имеют значение, указывающее на это. Отрицание атрибутов позволяет явным образом найти такие его сущности:
concept unfinishedTask is task t where not t.completed
Функция проверки неопределенности атрибута будет удобна, если сущности понятия могут иметь разную структуру:
concept unassignedTask is task t where not defined(t.assignedTo) or empty(t.assignedTo)
Функция проверки выводимости понятия незаменима при работе с рекурсивными определениями и иерархическими структурами:
concept minimalElement is element greater
where not exists(element lesser where greater.value > lesser.value)
В этом примере проверка на существование меньшего элемента выполнена в виде вложенного запроса. Подробно создание вложенных запросов я планирую рассмотреть в следующей публикации.

Элементы логики высшего порядка.

В логике первого порядка переменные могут соответствовать только множествам объектов и появляться только на позициях аргументов предикатов. В логике высшего порядка они могут соответствовать также и множествам отношений и появляться на позиции имен предикатов. Другими словами, логика первого порядка позволяет сделать утверждение, что некое отношение верно для всех или некоторых объектов. А логика высшего порядка описать отношение между отношениями.
Например, мы можем сделать утверждения, что некоторые люди являются братьями, сестрами, детьми или родителями, дядями или тетями и т.п.:
Brother(John, Joe).
Son(John, Fred).
Uncle(John, Alex).
Но чтобы сделать утверждение о родственных отношениях, в логике первого порядка нам нужно перечислить все утверждения выше, объединив их с помощью операции OR:
X,Y(Brother(X, Y) OR Brother(Y, X) OR Son(X, Y) OR Son(Y, X) OR Uncle(X, Y) OR Uncle(Y, X) Relative(X, Y)).
Логика второго порядка позволяет сделать утверждение о других утверждениях. Например, можно было бы напрямую указать, что отношения между братьями, сестрами, родителями и детьми, дядями и племянниками являются родственными отношениями:
RelativeRel(Brother).
RelativeRel(Son).
RelativeRel(Uncle).
X,Y(R(RelativeRel(R) AND (R(X, Y) OR R(Y, X))) Relative(X, Y)).
Мы утверждаем, что если для каждого X и Y существует некое отношение R, которое является отношением между родственниками RelativeRel, и X и Y удовлетворяют этому отношению, то X и Y являются родственниками. Аргументами отношений могут быть другие отношения, и переменные могут быть подставлены на место имен отношений.
Логика третьего порядка позволяет строить высказывания о высказываниях о высказываниях, и так далее, логика высшего порядка о высказываниях любого уровня вложенности. Логика высшего порядка гораздо более выразительна, но и намного сложнее. На практике системы логического программирования поддерживают только некоторые ее элементы, которые в основном ограничиваются использованием переменных и произвольных выражений на позициях предикатов.

В языке Prolog элементы такой логики реализованы с помощью нескольких встроенных мета-предикатов, аргументами которых являются другие предикаты. Основным из них является предикат call, который позволяет динамически добавить предикаты в список целей текущего правила. Его первый аргумент трактуется как цель, а остальные как ее аргументы. Prolog найдет в базе знаний предикаты, соответствующие первому аргументу и добавит их в текущий список целей. Пример с родственниками будет выглядеть следующим образом:
brother(john, jack).
sister(mary, john).
relative_rel(brother).
relative_rel(sister).
relative(X, Y) :- relative_rel(R), (call(R, X, Y); call(R, Y, X)).
Также Prolog поддерживает предикаты findall(Template, Goal, Bag), bagof(Template, Goal, Bag), setof(Template, Goal, Set) и др., которые позволяют найти все решения цели Goal, соответствующие шаблону Template и унифицировать (связать) их список с результатом Bag (или Set). В Prolog есть встроенные предикаты current_predicate, clause и др. для поиска предикатов в базе знаний. Также можно манипулировать предикатами и их атрибутами в баз знаний добавлять, удалять и копировать их.

Язык HiLog поддерживает логику высшего порядка на уровне синтаксиса. Вместо специальных мета-предикатов он позволяет напрямую использовать произвольные термы (например, переменные) на позиции имен предикатов. Правило для определения родственников примет вид:
relative(X, Y) :- relative_rel(R), (R(X, Y); R(Y, X)).
Такой синтаксис более декларативен, краток, понятен и естественен по сравнению с Prolog. В то же время HiLog остается синтаксическим вариантом Prolog, так как все синтаксические конструкции HiLog могут быть преобразованы выражения логики первого порядка с использованием мета-предикатов call.
Считается, что HiLog обладает синтаксисом высшего порядка, но семантикой первого порядка. Это значит, что при сравнении переменных, представляющих правила или функции, учитываются только их имена, но не реализация. Существуют также языки, поддерживающие семантику высшего порядка, например -Prolog, которые позволяют вовлечь в процесс логического вывода также и реализацию правил и функций. Но такая логика и ее алгоритмы вывода значительно сложнее.

Теперь перейдем к функционалу логики высшего порядка компоненты моделирования. Для большинства практических задач, связанных с мета-программированием, должно быть достаточно возможностей Prolog и HiLog. HiLog обладает более естественным синтаксисом, поэтому именно его имеет смысл взять за основу. Чтобы можно было использовать произвольные выражения на позициях имен понятий и их атрибутов и отличать их от перемменных, вызовов функций и других конструкций введем специальный оператор динамического указания имен:
< выражение >
Он позволяет вычислить значение выражения и использовать его как имя понятия, его псевдоним или имя атрибута в зависимости от контекста. Если этот оператор стоит на месте имени понятия в секции FROM и значение его выражения определено, то будут найдены все понятия с указанным именем и для них выполнен логический поиск:
concept someConcept ( ) from conceptA a, <a.conceptName> b where
Если значение выражения не определено, например, выражение представляет собой логическую переменную, не связанную со значением, то процедура найдет все подходящие понятия и свяжет значение переменной с их именами:
concept someConcept is <$conceptName> where
Можно сказать, что в контексте секции FROM оператор указания имени имеет логическую семантику.
Также оператор < > можно использовать и секции WHERE на позиции псевдонима понятия или имени атрибута:
concept someConcept ( ) from conceptA a, conceptB b where conceptB.<a.foreignKey> = a.value ...
Выражения в секции WHERE являются детерминированными, то есть они не задействуют логический поиск для нахождения неизвестных значений своих аргументов. Это значит, что выражение conceptB.<a.foreignKey> = a.value будет вычислено только после того, как будут найдены сущности понятия a, и его атрибуты foreignKey и value связаны со значениями. Поэтому можно сказать, что в контексте секции FROM оператор указания имени имеет функциональную семантику.

Рассмотрим некоторые возможные варианты применения логики высшего порядка.
Самый очевидный примером, где будет удобна логика высшего порядка, является объединение под одним именем всех понятий, удовлетворяющих некоторым условиям. Например, имеющих определенные атрибуты. Так понятием point можно считать все понятия, в состав которых входят координаты x и y:
concept point is <$anyConcept> a where defined(a.x) and defined(a.y)
Логический поиск свяжет переменную $anyConcept со всеми объявленными именами понятий (естественно, за исключением самого себя), которые обладают атрибутами координат.

Более сложным примером будет объявление общего отношения, применимого ко многим понятиям. Например, транзитивного отношения родитель-потомок между понятиями:
relation ParentRel between <$conceptName> parent, <$conceptName> child
where defined(parent.id) and defined(child.parent) and (
parent.id = child.parent or exists(
<$conceptName> intermediate where intermediate.parent = parent.id
and ParentRel(intermediate, child)
))
Переменная $conceptName используется во всех трех понятиях родителя, потомка и промежуточного объекта, что означает, что их имена должны совпадать.
Логика высшего порядка открывает возможности для обобщенного (generic) программирования в том смысле, что можно создать обобщенные понятия и отношения, которые можно применить к множеству понятий, удовлетворяющих заданным условиям, не привязываясь к их конкретным именам.

Также динамическая подстановка имен будет удобна в тех случаях, когда атрибуты одного понятия являются ссылками на имена других понятий или их атрибутов, или когда исходные данные содержат не только факты, но и их структуру. Например, исходные данные могут включать описание схем XML документов или таблиц в базе данных. Исходные данные также могут включать дополнительную информацию о фактах, например, типы данных, форматы или значения по умолчанию, условия валидации или некие правила. Также исходные данные могут описывать модель чего-либо, а компонента моделирования будет ответственна за построение метамодели. Работа с текстами на естественном языке также предполагает, что исходные данные будут включать не только высказывания, но и высказывания о высказываниях. Во всех этих случаях логики первого порядка будет недостаточно и необходим более выразительный язык.
В качестве простого примера рассмотрим случай, когда данные включают в себя некие объекты, а также правила валидации атрибутов этих объектов в виде отдельной сущности:
fact validationRule {objectName: someObject, attributeName: someAttribute, rule: function(value) {...}}
Результаты валидации можно описать следующим понятием:
concept validationRuleCheck (
objectName = r.objectName,
attributeName = r.attrName,
result = r.rule(o.<r.attrName>)
) from validationRule r, <r.objectName> o
where defined(o.<r.attrName>)

Логика высшего порядка отрывает довольно интересные возможности для обобщенного и мета-программирования. Мы смогли рассмотреть только ее общую идею. Эта область достаточно сложна и требует отдельных тщательных исследований в будущем. Как с точки зрения выбора удобного дизайна языка, так и вопросов его производительности.

Выводы.

В процессе работы над компонентой моделирования пришлось разобраться с довольно специфичными вопросами логического программирования, такими как работа с логическими переменными, семантикой оператора отрицания и элементами логики высшего порядка. Если с переменными все оказалось довольно просто, то в вопросах реализации оператора отрицания и логики высшего порядка единого устоявшегося подхода нет, и существует несколько решений, имеющих свои особенности, достоинства и недостатки.
Я постарался выбрать такое решение, которое было бы простым для понимания и удобным на практике. Монолитный оператор отрицания как отказа я предпочел разбить на три отдельных оператора булева отрицания, проверки выводимости понятия и существования атрибута у объекта. При необходимости эти три оператора можно скомбинировать и получить семантику отрицания, необходимую для каждого конкретного случая. Для правила вывода отрицания я решил взять за основу стандартную SLDNF резолюцию. Хоть она и не способна справиться с несогласованными рекурсивными высказываниями, но она гораздо проще в понимании и реализации, чем более изощренные альтернативы, такие как семантика стойких моделей или обоснованная семантика.
Логика высшего порядка понадобится для обобщенного и мета-программирования. Под обобщенным программированием я подразумеваю возможность строить новые понятия на основе широкого множества дочерних понятий, не привязываясь к конкретным именам последних. Под мета-программированием я подразумеваю возможность описывать структуру одних понятий с помощью других понятий. В качестве образца для элементов логики высшего порядка компоненты моделирования я решил взять язык HiLog. Он обладает гибким и удобным синтаксисом, позволяющим использовать переменные на позициях имен предикатов, а также простой и понятной семантикой.

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

Полный текст в научном стиле на английском языке доступен по ссылке: papers.ssrn.com/sol3/papers.cfm?abstract_id=3555711

Ссылки на предыдущие публикации:
Проектируем мультипарадигменный язык программирования. Часть 1 Для чего он нужен?
Проектируем мультипарадигменный язык программирования. Часть 2 Сравнение построения моделей в PL/SQL, LINQ и GraphQL
Проектируем мультипарадигменный язык программирования. Часть 3 Обзор языков представления знаний
Проектируем мультипарадигменный язык программирования. Часть 4 Основные конструкции языка моделирования

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

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

В области работы с данными неоспоримым лидером является язык SQL. Некоторые его возможности, оказавшиеся очень удобными на практике, такие как агрегация, позже перекочевали в логическое программирование. Поэтому будет полезным позаимствовать из SQL как можно больше возможностей и для компоненты моделирования. В этой статье я хочу показать, как в определения понятий можно встроить вложенные запросы, внешние соединения (outer join) и агрегацию. Также расскажу о еще одном типе понятий, которое описывается с помощью функции, генерирующей объекты (сущности) в алгоритмическом стиле не прибегая к логическому поиску. И покажу, как с его помощью можно использовать массивы объектов в качестве родительских понятий по аналогии с SQL операцией UNNEST, преобразовывающей коллекции в табличный формат и позволяющей соединить их с другими таблицами в секции FROM.

Анонимные определения понятий

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

Иногда нужно немного модифицировать понятие, выбрать отдельные его атрибуты, отфильтровать значения. Если эта модификация нужна только в одном месте, то тогда создавать отдельное понятие с уникальным именем не имеет смысла. Такая ситуация часто встречается, когда понятия являются аргументами функций, например, таких как exists, find или findOne, выполняющих проверку выводимости понятия, нахождения всех или только первого объекта (сущности) понятия. Здесь можно провести аналогию с анонимными функциями в функциональных языках программирования, которые часто применяются в качестве аргументов таких функций как map, find, filter и др.

Рассмотрим синтаксис определения анонимного понятия. В целом он соответствует синтаксису определения обычного понятия за исключением того, что в некоторых случаях можно опустить списки атрибутов и имя дочернего понятия. Если анонимное понятие используется как аргумент функции exists, то его имя и список атрибутов не важны, достаточно проверить, что есть хоть какой-то результат. В функциях find и findOne может не понадобиться имя понятия, если результат вывода используется не как цельное понятие, а только как набор атрибутов в ассоциативном массиве. Если атрибуты не указаны, то по умолчанию применяется механизм наследования и атрибуты будут унаследованы у родительских понятий. Если не указано имя понятия, то оно будет сгенерировано автоматически.

Попробуем пояснить выше написанное с помощью нескольких примеров. С помощью функции exists можно проверить выводимость или не выводимость вложенного понятия:

concept freeExecutor is executor e where not exists (task t where t.executor = e.id and t.status in ('assigned', 'in process'))

В данном примере анонимное понятие:

(task t where t.executor = e.id and t.status in ('assigned', 'in process'))

на самом деле представляет собой понятие, наследующее все атрибуты понятия task:

(concept _unanimous_task_1 as task t where t.executor = e.id and t.status in ('assigned', 'in process'))

Функция find позволяет вернуть в виде списка все значения понятия, которые затем могут быть связаны с атрибутом:

concept customerOrdersThisYear is customer c with orders where c.orders = find((id = o.id, status = o.status, createdDate = o.createdDate, total = o.total) from order o where o.customerId = c.id and o.createdDate > '2021-01-01')

В данном примере мы расширяем понятие customer списком заказов, которые представляют собой объекты, содержащие выбранные атрибуты понятия order. Мы указали список атрибутов анонимного понятия, а его имя пропущено.

Условия в секции where анонимного понятия могут включать атрибуты других родительских или дочернего понятий, в данном случае это c.id. Особенностью анонимных понятий является то, что все подобные внешние переменные и атрибуты должны быть обязательно связаны со значениями на момент запуска поиска решений. Таким образом объекты анонимного понятия могут быть найдены только после нахождения объектов понятия customer.

Внешние соединения

Анонимные определения понятий можно использовать и в секции from, где они будут представлять родительские понятия. Более того, в определение анонимного понятия можно перенести часть условий, связывающих его с другими понятиями, что будет иметь особый эффект. Эти условия будут проверены на этапе поиска решения анонимного понятия и не будут влиять на процесс логического вывода дочернего понятия. Здесь можно провести аналогию между условиями в секции where анонимного понятия и условиями в секции JOIN ON языка SQL.

Таким образом, анонимные понятий могут быть использованы для реализации аналога внешних соединений (left outer join) языка SQL. Для этого понадобится три вещи.

1. Во-первых, заменить нужное родительское понятие анонимным понятием на его основе и перенести в него все связи с остальными родительскими понятиями.
2. Во-вторых, указать, что неудача вывода этого понятия не должна приводить к автоматической неудаче вывода всего дочернего понятия. Для этого нужно пометить это родительское понятие с помощью ключевого слова optional.
3. А в-третьих, в секции where дочернего понятия можно проверить, существуют ли решения данного анонимного понятия.

Разберем небольшой пример:

concept taskAssignedTo (task = t, assignee = u, assigneeName) from task t, optional (user where id = t.assignedTo) u where assigneeName = if(defined(u), u.firstName + ' ' + u.lastName, 'Unassigned') 

Атрибуты понятия taskAssignedTo включают в себя объекты задачи, ее исполнителя и отдельно имя исполнителя. Родительскими понятиями являются task и user, причем значение последнего может быть пустым, если задача еще не имеет исполнителя. Оно обвернуто в определение анонимного понятия, перед которым стоит ключевое слово optional. Процедура логического вывода сначала найдет объекты понятия task, затем на основе user создаст анонимное понятие, связав его с конкретным значением атрибута assignedTo понятия task. Ключевое слово optional указывает процедуре вывода, что в случае неудачи вывода этого понятия, его объект будет связан со специальным значением UNDEFINED. А проверка результата его вывода на уровне дочернего понятия позволяет атрибуту assigneeName задать значение по умолчанию. Если ключевое слово optional не было бы указано, то неудача вывода анонимного понятия привела бы к неудаче текущей ветви поиска дочернего понятия. И такой вариант был бы аналогичен внутреннему объединению (inner join) языка SQL.

Поскольку условия в секции where анонимного понятия включают атрибут assignedTo другого родительского понятия task, то поиск объектов понятия user возможен только после связывания объектов task со значениями. Их нельзя поменять местами:

from optional (user where id = t.assignedTo) u, task t 

Поскольку на начальном этапе значение t.assignedTo будет неизвестным, то создать определение анонимного понятия не получится.

Если в SQL порядок таблиц в секции from не имеет значения, то в Prolog порядок предикатов в правиле однозначно определяет последовательность обхода дерева решений. То же можно сказать и о компоненте моделирования, правило вывода которой основано на SLD резолюции, используемой в Prolog. В ней результат вывода объектов левого понятия определяет ограничения для вывода объектов правого. Из-за этого, к сожалению, не получится реализовать операции right outer join и full outer join таким же естественным образом. Поскольку мощность множества результатов правого родительского понятия может быть больше, чем левого, то в них потребуется вывод в противоположном направлении от правого понятия к левому. К сожалению, особенности выбранной процедуры логического вывода накладывают свои ограничения на функциональность языка. Но операцию full outer join можно сэмулировать соединив внутреннее, левое и правое объединения:

concept outerJoinRelation( concept1Name, concept2Name, concept1Key,concept2Key,concept1 = c1,concept2 = c2) from <concept1Name> c1, <concept2Name> c2where c1.<concept1Key> = c2.<concept2Key>;concept outerJoinRelation(concept1Name, concept2Name, concept1Key,concept2Key,concept1 = c1,concept2 = null) from <concept1Name> c1where not exists( <concept2Name> c2 where c1.<concept1Key> = c2.<concept2Key>);concept outerJoinRelation(concept1Name, concept2Name, concept1Key,concept2Key,concept1 = null,concept2 = c2) from <concept2Name> c2where not exists( <concept1Name> c1 where c1.<concept1Key> = c2.<concept2Key>);

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

Агрегирование

Агрегирование является неотъемлемой частью как реляционной алгебры, так и логического программирования. В языке SQL секция GROUP BY позволяет сгруппировать строки, имеющие одинаковые ключевые значения, в итоговые строки. Она позволяет удалить повторяющиеся значения и обычно используется с агрегатными функциями, такими как sum, count, min, max, avg. Для каждой группы строк агрегатные функции возвращают ординарное значение, рассчитанное на основе всех строк этой группы. В логическом программировании агрегирование имеет более сложную семантику. Это связано с тем, что в некоторых случаях рекурсивного определения правил SLD резолюция попадает в бесконечный цикл и не способна завершиться. Как и в случае отрицания как отказа проблему рекурсии в операции агрегации решают с помощью семантики стойких моделей или хорошо обоснованной семантики. Об этих подходах я попытался кратко рассказать в предыдущей статье. Но поскольку семантика компоненты моделирования должна быть как можно проще, то стандартная SLD резолюция более предпочтительна. А проблему избегания бесконечной рекурсии лучше решить путем переформирования связей между понятиями.

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

concept <имя понятия> <псевдоним понятия> (<имя атрибута> = <выражение>,... )group by <имя атрибута>, ... from <имя родительского понятия> <псевдоним родительского понятия> (<имя атрибута> = <выражение> ,...),...where <выражение отношений>

Секция group by, так же, как и в SQL, содержит список атрибутов, по которым выполняется группировка. Выражение отношений также может включать функции агрегации. Выражения, содержащие такие функции будут считаться неопределенными, пока не будут найдены значения всех родительских понятий и выполнена группировка. После этого их значения могут быть вычислены для каждой группы, связаны с атрибутами и/или использованы для фильтрации групп. При таком отложенном подходе к вычислениям и проверке условий нет необходимости в секции HAVING, отделяющей условия фильтрации до и после группировки. Среда исполнения сделает это автоматически.

Основными функциями агрегации являются count, sum, avg, min, max. Назначение функций можно понять из их названия. Поскольку компонента моделирования умеет естественным образом работать c составными типами данных, то также можно добавить функцию, возвращающую сгруппированные значения в виде списка. Назовем ее group. Ее входным аргументом является выражение. Функция возвращает список результатов вычисления этого выражения для каждого элемента группы. Комбинируя ее с другими функциями можно реализовать любую произвольную функцию агрегации. Функция group будет удобнее, чем такие SQL функции как group_concat или json_arrayag, которые часто используются в качестве промежуточного шага для получения массива значений поля.

Пример группировки:

concept totalOrders (customer = c,orders = group(o),ordersTotal = sum(o.total)) group by customerfrom customer c, order o where c.id = o.customerId and ordersTotal > 100

Атрибут orders будет содержать список всех заказов пользователя, ordersTotal общую сумму всех заказов. Условие ordersTotal > 100 будет проверено уже после выполнения группировки и вычисления функции sum.

Понятие, определенное с помощью функции

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

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

concept <имя понятия> (<имя атрибута>, ... )by <функция генерации объектов>

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

Теперь поговорим о функции генерации объектов. Очевидно, что на вход она должна получать запрос исходные значения атрибутов. Поскольку эти значения могут быть как заданы, так и нет, для удобства их можно поместить в ассоциативный массив, который и будет входным аргументом функции. Также будет полезно знать, в каком режиме запущен поиск значений понятия найти все возможные значения, найти только первое или только проверить существование решения. Поэтому режим поиска добавим в качестве второго входного аргумента.

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

В качестве примера рассмотрим понятие, описывающее временные интервалы. Предположим, нам нужно разбить рабочий день на 15-и минутные интервалы. Мы можем сделать это с помощью довольно простой функции:

concept timeSlot15min (id, hour, minute) by function(query, mode) {var timeSlots = [];var curId = 1;for(var curHour = 8; curHour < 19; curHour += 1) {for(var curMinute = 0; curMinute < 60; curMinute += 15) {timeSlots.push({id: curId,hour: curHour,minute: curMinute;});curId++;}}return timeSlots.iterator();}

Функция возвращает итератор для всех возможных значений 15-и минутного интервала времени за рабочий день. Ее можно использовать, например, для поиска свободных временных интервалов, которые еще не забронированы:

concept freeTimeSlot is timeSlot15min s where not exists (bookedSlot b where b.id = s.id)

Функция не проверяет результат вычислений на соответствие запросу query, это будет сделано автоматически при преобразовании массива атрибутов в сущности. Но при необходимости поля запроса можно использовать для оптимизации функции. Например, сформировать запрос к базе данных на основе полей запроса к понятию.

Понятие через функцию соединяет в себе логическую и функциональную семантики. Если в функциональной парадигме функция вычисляет результат для заданных значений входных аргументов, то в логической парадигме нет разделения на выходные и входные аргументы. Могут быть заданы значения только части аргументов, причем в любой комбинации, и функции необходимо найти значения оставшихся аргументов. На практике реализовать такую функцию, способную выполнять вычисления в любом направлении, не всегда возможно, поэтому имеет смысл ограничить возможные комбинации свободных аргументов. Например, объявить, что некоторые аргументы обязательно должны быть связаны со значениями перед вычислением функции. Для этого пометим такие атрибуты в определении понятия ключевым словом required.

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

concept expScale (value, position, required limit) by function(query, mode) {return {_curPos = 0,_curValue = 1,next: function() {if(!this.hasNext()) {return null;}var curItem = {value: this._curValue, position: this._curPosition, limit:  query.limit};this._curPos += 1;this._curValue = this._curValue * Math.E;return curItem;},hasNext: function() {return query.limit == 0 || this._curPos < query.limit; }}}

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

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

Развертывание вложенных коллекций (Flattening nested collections)

Некоторые диалекты SQL, умеющие работать с данными в объектной форме, поддерживают такую операцию как UNNEST, которая преобразует содержимое коллекции в табличный формат (набор строк) и добавляет получившуюся таблицу в секцию FROM. Обычно она используется, чтобы объекты со вложенными структурами сделать плоскими, другими словами, развернуть или сгладить (flatten) их. Примерами таких языков являются BigQuery и SQL++.

Предположим, мы храним информацию о пользователях в виде JSON объекта:

[ {"id":1,"alias":"Margarita","name":"MargaritaStoddard","nickname":"Mags","userSince":"2012-08-20T10:10:00","friendIds":[2,3,6,10],"employment":[{"organizationName":"Codetechno","start-date":"2006-08-06"},{"organizationName":"geomedia","start-date":"2010-06-17","end-date":"2010-01-26"}],"gender":"F"},{"id":2,"alias":"Isbel","name":"IsbelDull","nickname":"Izzy","userSince":"2011-01-22T10:10:00","friendIds":[1,4],"employment":[{"organizationName":"Hexviafind","startDate":"2010-04-27"}]}, ]

Объекты пользователей хранят в себе вложенные коллекции со списками друзей и местами работы. Извлечь вложенную информацию о местах работы пользователя склеив ее с данными о пользователе, взятыми из верхнего уровня объекта, можно с помощью запроса на SQL++:

SELECT u.id AS userId, u.name AS userName, e.organizationName AS orgNameFROM Users u UNNEST u.employment eWHERE u.id = 1;

Результатом будет:

[ {"userId": 1,"userName": "MargaritaStoddard","orgName": "Codetechno"}, {"userId": 1,"userName": "MargaritaStoddard","orgName": "geomedia"} ]

Более подробно эта операция рассмотрена здесь.

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

Поскольку полное определение понятия через функцию слишком громоздко для использования в качестве анонимного понятия:

concept conceptName(attribute1, attribute2, ...) by function(query, mode) {...}

нужно найти способ его сократить. Во-первых, можно избавиться от заголовка определения функции с параметрами query и mode. На позиции родительского понятия аргумент mode всегда будет равен найти все значения понятия. Аргумент query всегда будет пуст, так как зависимости от атрибутов других понятий можно встроить в тело функции. Ключевое слово concept тоже можно выкинуть. Таким образом получаем:

conceptName(attribute1, attribute2, ...) {}

Если имя понятия не важно, то его можно опустить, и оно будет сгенерировано автоматически:

(attribute1, attribute2, ...) {}

Если в будущем удастся создать компилятор, который сможет вывести список атрибутов из типа объектов, возвращаемых функцией, то и список атрибутов можно будет откинуть:

{}

Итак, пример с пользователями и их местами работы в виде понятия будет выглядеть следующим образом:

concept userEmployments (userId = u.id,userName = u.name,orgName = e.orgName) from users u, {u.employment.map((item) => {orgName: item.organizationName}).iterator()} e

Решение получилось немного многословным, но зато универсальным. В то же время, если никакого преобразования объектов вложенной коллекции не требуется, то его можно заметно упростить:

concept userEmployments (userId = u.id,userName = u.name,orgName = e. organizationName) from users u, {u.employment.iterator()} e

Выводы

Данная статья была посвящена двум вопросам. Во-первых, переносу в компоненту моделирования некоторых возможностей языка SQL: вложенных запросов, внешних объединений, агрегирования и объединений со вложенными коллекциями. Во-вторых, введением в компоненту моделирования двух новых конструкций: анонимных определений понятий и понятий, определенных через функцию.

Анонимное понятие это сокращенная форма определения понятия, предназначенная однократного для использования в качестве аргументов функций (find, findOne и exists) или в качестве вложенного определения понятия в секции where. Его можно рассматривать как аналог анонимных определений функций в языках функционального программирования.

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

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

Итак, в этой и двух предыдущих статьях я описал основные понятия и элементы компоненты моделирования гибридного языка программирования. Но, прежде чем перейти к вопросам интеграции компоненты моделирования с компонентой вычислений, реализующей функциональный или объектно-ориентированный стиль программирования, я решил посвятить следующую статью возможным вариантам ее применения. С моей точки зрения компонента моделирования имеет преимущества перед традиционными языками запросов, в первую очередь SQL, и может найти применение сама по себе без глубокой интеграции с компонентой вычислений, что я и хочу продемонстрировать на нескольких примерах в следующей статье.

Полный текст в научном стиле на английском языке доступен по ссылке: papers.ssrn.com/sol3/papers.cfm?abstract_id=3555711

Ссылки на предыдущие публикации:

Проектируем мультипарадигменный язык программирования. Часть 1 Для чего он нужен?
Проектируем мультипарадигменный язык программирования. Часть 2 Сравнение построения моделей в PL/SQL, LINQ и GraphQL
Проектируем мультипарадигменный язык программирования. Часть 3 Обзор языков представления знаний
Проектируем мультипарадигменный язык программирования. Часть 4 Основные конструкции языка моделирования
Проектируем мультипарадигменный язык программирования. Часть 5 Особенности логического программирования

Лаборатория языковых инструментов совместная инициатива JetBrains и математико-механического факультета СПбГУ.

Сотрудники лаборатории исследуют:

• формализацию и верификацию семантики языков программирования в контексте слабых моделей памяти;
• логическое и реляционное программирование;
• теорию формальных языков и ее применения;
• метапрограммирование, специализацию и частичные вычисления;
• формальную верификацию и применение SMT-решателей.

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



Прошедшие доклады:













Ближайший доклад 2 ноября сделает Антон Трунов по теме Неразличимые доказательства: по определению, но без аксиомы К. Присоединяйтесь в 17:30 в Google Meet по ссылке.


Чтобы получать анонсы наших семинаров:

• вступите в Google группу,
• вступите в Vk группу лаборатории,
• или добавьте себе календарь семинаров.