Как стать автором
Обновить

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

Время на прочтение 16 мин
Количество просмотров 3.3K
Всего голосов 10: ↑9 и ↓1 +8
Комментарии 23

Комментарии 23

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

К языку здесь требование простое — нужно легко и логично увязать некую сложную конструкцию со спецификой отдельных не во всём укладывающихся в неё элементов. То есть язык должен предлагать средства расширения модели без компромиссов с его логикой и производительностью. Здесь «язык» это среда исполнения плюс синтаксис. И средства расширения не должны приводить к потере понимания модели. Если после расширения ориентирование в модели требует длительного повторного изучения кучи связей, то такой подход к расширению очень неудобен вытекающими из него множественными ошибками, которые сложно выявлять на этапе проектирования.

Как эта проблема решается у вас?

Я бы копал в сторону среды исполнения, которая должна сама находить противоречия в модели. У вас этого, похоже, нет, и не предвидится. Поэтому и язык, со всеми его интересными моментами, останется в одном ряду с существующими, хотя возможно будет удобнее на каких-то отдельных задачах.
Да, если логику высшего порядка использовать необдуманно, то можно легко выстрелить себе в ногу. Как с точки зрения запутанности кода, так и производительности.
Я предполагаю, что логика высшего порядка будет полезна в тех случах когда нужно определить общие отношения между понятиями, не привязываясь к их имени. Например, родитель-потомок, больше-меньше, геометрические отношения, отношения во времени и т.п. В большинстве случаев такие отношения будут использоваться не сами по себе, а совместно с другими понятиями. Например, отношение ParentRel можно использовать для поиска каких-нибудь вложенных элементов:
concept NestedElements (parent = e1, child = e2) from Element e1, ParentRel r(parent = e1, child = e2), Element e2 where ...
Сначала будет найдет элемент e1, это позволит связать название понятия в отношении ParentRel с «Element», а затем найти все вложенные элементы и отфильтровать нужные из них. Также это отношение можно применить и к другим понятиям, например, к иерархиям подразделений в компании. На мой взгляд, к дополнительной сложности, запутанности и излишнему росту связей подобные конструкции приводить не должны.
Это можно считать аналогом generic классов в ООП модели. В которой, например, контейнеры списков можно применить к любому одержимому не привязываясь к конкретным его классам.

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

Я бы копал в сторону среды исполнения, которая должна сама находить противоречия в модели.

Да, пока этой задачей я не занимался. Но это интересная тема. Надеюсь, я когда-нибудь смогу до нее добраться.

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


( ( A & B ) = Absurd )=>( A ^ B )
Что касается семантики стойких моделей, то утверждения p ← not q и q ← not p рассматриваются не как абсурдные, а как дополняющие друг друга. Оператор отрицания в Stable model semantics понимается так же утверждения по умолчанию в Default logic. То есть
not q понимается не как безусловное отрицание, а как некое дополнительное подтверждение остальных правил, которое имеет смысл, только если оно согласуется с ними.
Например, в
male(X) ← person(X) AND NOT female(X)
female(X) ← person(X) AND NOT male(X)
NOT female(X) и NOT male(X) это дополнительные утверждения, которые можно отбросить, если они противоречат остальным правилам. Т.е., если мы знаем, что male(alex) истинно, то not female(alex) можно проигнорировать. И эти правила трансформируются в утверждения, что все люди по умолчанию мужчины, кроме тех, про кого точно известно, что они женщины (так же и наоборот).

Какая-то сомнительная индукция получается. Суть-то не в операторе отрицания, противоречие может получиться и без него:


( ( мужчина(x) & женщина(x) ) = Absurd )=>( мужчина(x) ^ женщина(x) )

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

Про бесполых существ в этих формулах ничего не говорится. Если вообще нет фактов, о том, какого пола Х, то в Stable Model Semantic делается вывод, что возможны оба варианта, Х может быть как мужчиной, так и женщиной. Бесполых существ надо вводить в формулы отдельно:
male(X) ← person(X) AND NOT female(X) AND NOT neutral(X)
female(X) ← person(X) AND NOT male(X) AND NOT neutral(X)
neutral(X) ← person(X) AND NOT male(X) AND NOT female(X)

Вот эти вот "and not" можно выводить автоматически из противоречия.

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

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

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

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

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

Я тут рассказывал, почему 4 значения необходимо и достаточно для оперирования любыми выражениями: https://habr.com/ru/post/522578/


С меньшим числом значений становится невозможно выразить истинность некоторых типов утверждений.

relative(X, Y) :- relative_rel(R), (R(X, Y); R(Y, X)).

Было бы куда наглядней иметь такой синтаксис:


( ( X R Y | Y R X ) & relative_rel R )=> X relative Y
Да, согласен. Особенно для одно и двумерных отношений. Но для большего количества аргументов надо что-то придумывать: R(X, Y, Z) =>?

В этом случае имя получается составным, как в ObjectiveC:


X foo Y bar Z === foo-bar( X, Y, Z )

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

А что вы имеете в виду под платфомой для языка программирования? Реализацию? Компиляторы, отладчики, IDE и прочую инфраструктуру?

именно, всё вот это к примеру на веб-страничке. чтобы юзернейм пришел, запустил и программирует)

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

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

Например, можно вместо вашего выбора JavaScript, который никому не интересен в плане сложной работы с данными (целевая аудитория — формошлёпы и верстальщики), компилировать в байткод JVM или .Net. Тогда появляется возможность, добавив к с интаксису довольно простую конструкцию вызова стороннего байткода, автоматически использовать все имеющиеся библиотеки для JVM или .Net. И обратно — разработчики Java или .Net получат возможность использовать ваш синтаксис для подготовки решений по сложной обработке данных.

Но от вас здесь требуется тот самый компромисс — согласиться на компиляцию в байткод и предоставить синтаксис для вызова чужих библиотек. Возможно, проще будет компилировать в Java (раз вы уже компилируете в JS), это тоже выход. А в идеале, могла бы быть некая библиотека, которая позволяла встраивать ваш язык в программу например на Java, хотя бы в виде загрузки строк с текстом программы, интерпретируемым вашим интерпретатором по команде из Java (что выглядит просто в реализации, но требует знания Java или другого языка, куда вы бы захотели встроить своё решение).

Но повторюсь — это всё требует от вас действий, которые вы весьма вероятно не захотите сделать. Ваш академический интерес к языку подсказывает именно такой вариант. Здесь нужен кто-то молодой да шустрый, не обременённый знаниями, ну и готовый работать на энтузиазме. Поэтому я уже сообщал об очень ограниченных ожиданиях в отношении вашего начинания.
Ну почему же, я очень открыт к компромиссам и вижу несколько потенциальных вариантов реализации языка. Вариант с JVM очень интересен. О возможных вариантах применения языка на практике и его реализации я планирую написать отдельную статью.
А JS я выбрал только в качестве proof of concept, чтобы проверить свои идеи по интеграции логической и имеперативной компонент на практике. Просто потому, что это один из самых простых и быстрых вариантов в реализации.
Зарегистрируйтесь на Хабре , чтобы оставить комментарий

Публикации

Истории