Проектируем мультипарадигменный язык программирования. Часть 5 — Особенности логического программирования

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

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

А сейчас я предлагаю окунуться в некоторые нюансы логического программирования. Поскольку язык компоненты моделирования имеет декларативную логическую форму, то придется решить такие проблемы, как определение семантики оператора отрицания, внедрение элементов логики высших порядков и добавление возможности работы с логическими переменными. А для этого придется разобраться с такими теоретическими вопросами как предположение об открытости/замкнутости мира, отрицание как отказ, семантикой стойких моделей (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, преобразовывающей массивы в табличный формат).

Полный текст в научном стиле на английском языке доступен по ссылке.

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

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