DRAKON.SU

Книгу и диссер прочитал в один присест. Впечатление — сильное!
Жаль, что не знал раньше.

Одна из замечательных идей языка УТОПИСТ — программирование путём постановки задачи:
1. Строим модель задачи, в которой есть: алгоритмы, структура данных, уравнения.
2. Задаём некоторые входные данные (строго в соответствии со структурой данных).
3. Даём команду: рассчитать такие-то выходные данные (опять в соответствии со структурой).

Пример:

Строим модель квадратного уравнения.
В модели будет следующая структура данных:
- коэффициенты: a, b, c,
- количество корней n,
- дискриминант d,
- корни: x1, x2.
В модели будут также алгоритмы расчёта n, d, x1 и x2.

Задаём коеффициенты: a, b, c.
Даём команду:
- определить количество действительных корней уравнения n;
- рассчитать значения корней x1 и x2.

Это УТОПИСТ.
А вот суть диссертации: давайте ограничим количество выходных переменных в каждом алгоритме модели до одной. Это упростит генерацию кода.

Я пошёл ещё дальше: а давайте ограничим количество алгоритмов, которыми можно получить значение каждой переменной модели, до одного.
Одна переменная — один алгоритм. Это упростит генерацию кода ещё больше.
Конечно, получается всего лишь огрызок УТОПИСТа. Но даже обрезанный наполовину, УТОПИСТ сохраняет огромную убойную силу.
Вот описание модели.
Стуктура данных (набор переменных):

Вот алгоритмы расчёта переменных:

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


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

А в чём преимущество по отношению к языкам Prolog, Haskell, Idris?

пока действительно неясно в чем преимущество перед Prolog тем же который тоже совершенно сам найдет решение если оно имеется

Языков Haskell и Idris не знаю. Комментировать не буду.

ПРОЛОГ знаю.
ПРОЛОГ имеет машину по перебору. То есть это поиск в глубину без проверки узлов на предыдующие посещения.
Это хороший алгоритм, но скажем... он не везде...

Хотите более практичную машину правил? Берите ДРАКОН-nools. Там Rete, без шуток.

Оригинальный УТОПИСТ — это не машина правил, это синтезатор кода. То есть он производит дополнительную работу во время компиляции, а не во время выполнения.

Реализация УТОПИСТА в среде DRAKON Editor настолько урезана, что генератор кода там тривиален.
Тем не менее, польза от него есть. Вы когда пишете обычную процедурную или функциональную программу, вы сообщаете компилятору больше, чем он должен знать.
А тут некоторая часть избыточного кода не нужна.
Меньше тупого кода — это меньше ошибок. (Хотя некоторым нравится на клавиатуре печатать.)

По-моему, это новое слово. А может, это я нуб.
Дорогие форумчане, укажите иностранные аналоги. PROLOG и Mercury не предлагать.

Как программировать на ДРАКОН-УТОПИСТе

1. Разработать модель задачи.
- Определить набор входных переменных.
- Определить набор выходных переменных.
- Для выходных переменных задать алгоритмы расчёта.
- По необходимости, создать промежуточные переменные.
- Задать алгоритмы расчёта промежуточных переменных.

Важное правило:
Алгоритм расчёта переменной задаётся как "чистая" (pure) функция.
Она может читать переменные задачи и возвращать значение.
Запись в объект задачи из этой функции запрещён!

2. Создать объект задачи.

3. Записать входные данные во входные переменные.

4. Прочитать выходные данные из выходных переменных. Всё посчитается само.

Если честно, то я уж тогда Drools возьму. nools уже не поддерживается, а исходная библиотека Drools ушла далеко вперёд.
Одно только insertLogical чего стоит.

Если не хотите сравнивать с Haskell, то давайте сравним с dataflow programming
То же самое, что и УТОПИСТ?

Да! Очень похоже. ДРАКОН-УТОПИСТ — это и есть data flow, только саму диаграмму рисовать не надо. Она сама складывается. В кубике уже написано, откуда стрелочки приходят. Стало быть, меньше байндинга.
Оригинальный УТОПИСТ, он круче:
1. Он не только стрелки проводит, но и if then else вставляет, где надо, и циклы.
2. Он сами кубики может создавать: выводит функции из уравнений.

Где-то в соседней теме про формальные методы верификации была ссылка на проект Termite:
http://ssrg.nicta.com.au/projects/TS/drivers/synthesis/

, где представлена методология синтеза системы на основе теории игр (поиск оптимальной траектории системы (с учётом огромного количества возможных состояний), понимая её обобщённо как систему переходов). В данном случае -- технология инкрементального (постепенного, частичного) построения программ -- драйверов устройств.
По ссылке все основные материалы, включая описание алгоритмов. В дополнение, любопытный обзор инструментария:
The First Reactive Synthesis Competition (SYNTCOMP 2014)

Видимо, в целом методологию можно определить как основанную на "теории интерфейсов" -- публикации ниже вне рамок проекта Termite выше, однако некоторые авторы принимали в нём участие:
Interface-based design

"Модальные" расширения:
A Modal Interface Theory for Component-based Design

Чуть конкретнее насчёт временных и ресурсных ограничений:
Resource Interfaces
Timed Interfaces

Имхо, неудобство языков для правил -- далеко не главная проблема применимости экспертных систем. Но это другая тема.

А рядом с "ПРИЗ" и "концептуальным программированием" был представлен и "проект-потомок" -- CoCoViLa -- в дополнение о запросе "аналогов":
viewtopic.php?f=140&t=5581&start=60#p100266

Там для продукционных правил предлагается вариант таблиц решений. В данном случае есть особенность -- некая "двумерность" для условий:
http://cocovila.github.io/files/documen ... avel_2.pdf
http://cocovila.github.io/files/documen ... oc_1.7.pdf

Вообще-то, вариантов составления таблиц решений много всяких разных, ниже некоторые из них можно сопоставить в контексте решения одной и той же задачи:
https://dmcommunity.org/challenge/challenge-jan-2016/

В этой статейке можно взглянуть на "линейные бинарные графы" представления сложных логических формул (в данном случае -- целая методика отображения переходов в автоматах):
http://is.ifmo.ru/papers/_2010_02_25_danilov.pdf

Выше -- неплохие альтернативы или дополнения к схемам (и тексту).

Вот, создал JavaScript package для мини-УТОПИСТа без ДРАКОНа.

npm install mini_utopist

https://github.com/stepan-mitkin/mini_utopist

Но удобнее, конечно, с ДРАКОНом.

По-моему, вы неправильно поняли ПРИЗ/УТОПИСТ.

Почитал книгу, и по сути они предлагают "функциональное программирование" + "символическое решение уравнений".
Вы всё-таки начните не с npm, а с примера какой-нибудь реальной задачи.

Вот пример из исходной книги о ПРИЗ:


Это ниразу не dataflow programming.
Это символьные вычисления, когда система должна либо аналитически, либо численно решить уравнения.

С точки зрения "формулировки задач", да, это может быть "удобно". Ещё бы. Не надо думать как вычислять.

Но практически -- фиг-с-маслом оно что-то решит. Ну не сможет оно автоматически вывести формулу квадратного уравнения.

Вот вы в своём npm примере так расписали "алгоритм решения квадратного уравнения".
Внимание, вопрос: чем он лучше простого кода, где все вычисления последовательны?
Грубо говоря:


Я могу сказать чем ваш код "addProperty" плох:
1) Совершенно пропадают типы данных. Иными словами, если "функция discriminant" вернёт строку, а не число, то об этом вообще никак невозможно будет узнать.
2) Код "через addProperty" занимает гораздо больше места. Его сложнее понимать и отлаживать. В Дракон варианте будет ещё хуже.
3) Пример явно игрушечный. Нужно смотреть на задачу, где "суперутопист" будет сиять, а простые подходы хромать. Тогда можно поговорить-обсудить. Сейчас же видно, что на этой задаче ПРИЗ вообще никак не нужен.

PS. Раз говорите, что не знакомы с Haskell, то рекомендую познакомиться. Например, https://www.ohaskell.guide/
Ну или LISP/Clojure.
Это функциональные языки, там "нельзя менять состояние при вычислении функций" (это язык гарантирует), значения сами собой кэшируются и т.п.

Вот пример "квадратного уравнения":



Вызвается оно так (ну и возвращает либо ошибку, либо список корней):


Более того, можно сделать функцию, которая решает линейные уравнения:

Т.е. мы объявляем, что "функцую linsolve" можно вычислить, если 1-ым аргументом в quadsolve передать 0.

Это гораздо круче УТОПИСТов и прочих ПРИЗов.

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

Я начал с реальной задачи. А именно, я переложил на УТОПИСТские модели процесс пересадки лианы в ДРАКОН-схеме. Это сложная задача.
Не хотел засорять форум этими деталями.



В книге содержится несколько идей.
Какие именно идеи меня сразили наповал?

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

Можно это любить, или не любить. Не важно. Хорошее или плохое, это изобретение объективно существует.

2. Генерация кода из модели. В УТОПИСТЕ речь идёт только о выводе функций из уравнений.
Но сама идея идёт гораздо дальше. Об этом я напишу в другое время.

Рассмотрим непосредственную выгоду первой идеи (уменьшение связующего кода).

Вот традиционная функциональная форма:


Вот та же задача, записанная в нотации УТОПИСТа


Во втором примере:
1. Отсутствует вызов quad_discr a b c
2. Функции radix и delta не имеют аргументов.
3. Не указано, что сначала нужно посчитать delta, потом radix, потом корни.

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

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

Порядок выполнения как раз нужен в программах типа "введите a, введите b, введите c, ваш ответ такой-то".


Вообще говоря, современный подход предполагает, что "глобальные переменные это зло".
Вы же наоборот радуетесь от того, что "функция получает аргументы из глобальной области видимости".
Я, конечно, понимаю, что вы больше про то, что "функция получает аргумент из того места где она была вызвана" и что, якобы, "глобальных переменных может не быть".
Но при "автоматическом непойми-каком связывании" получится, что "система обнаружит, что функция delta может вычислить D из a, b и c". Но эта система же никак не понимает смысл a b c? Может, программист вообще не квадратное уравнение имел ввиду, а просто имена совпали. В итоге, имена переменных совпали, а система уже вызвала delta и т.п. Кому такое нужно?



О, да, сэкономили целую строку кода! Сразу видно, что технология нужная. Шутка.
Этот "сэкономленный" вызов quad_discr решал понятную задачу. Он описывал на каких именно данных вычисляется функция (см ниже).


Встречный вопрос: а почему тогда у функции quadsolve аргументы появились?
Где логика?

Ну и ещё вопрос: как решить сразу 2 квадратных уравнения?
Допустим, у меня (каким-то образом) возникли переменные a,b,c, a1,b1,c1.
Ну и хочу я решить два квадратных уравнения, а в результат вывести частное корней.
Вы же говорите, что "delta" не имеет аргументов. Значит решить a1,b1,c1 "автоматическим связыванием" не получится.
Что, добавлять ещё одну функцию delta1=b1*b1-4*a1*c1 ?
Ну и какой тогда смысл в этом автоматическом связывании?


Где же оно, это безумие?

Давайте такой пример посмотрим.
Дано: "файл с цифрами по-английски" (one two five one ...). Нужно: заменить слова на цифры (1 2 5 1 ...)

Решение на Haskell (см https://stackoverflow.com/a/7833652/1261287 ):

words разделяет строку на слова (делает список из слов). mapM_ применяет функцию (print . english) к списку.

Имена переменных вообще нигде не фигурируют. Где же обещанный безумный объём связывающего кода?
Материал по теме называется pointfree notation

Уважаемый, Владимир!

Спасибо вам за плодотворную дискуссию.
Вы помогаете мне объяснять материал. И вы помогаете мне лучше понять суть данной идеи. И Haskell. ))

Вот мои уточнения, основанные на ваших замечаниях.

1. Функции, которые рассчитывают значения переменных модели, читают данные из других переменных модели.
Не из глобальной области видимости! То есть глобальных переменных тут нет.
Аналогия: метода класса читают поля класса.

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

3. УТОПИСТ и ДРАКОН взаимно дополняют друг друга. Они могут работать и по отдельности. Но вместе веселей!

Ну начинается... "из переменных модели", хотя это, якобы, не переменные, а постоянные т.к. изменение состояния запрещено.

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

Если же в "безпараметрные" функции выносить только совсем простое (ну, которое, якобы, не требует тестирования), то тогда это сужает область применимости и смысла от технологии не остаётся.

Получается, вас порадовало "ООП, в котором private методы вызываются сами собой в нужном порядке"?

Так как алгоритмы модели представляют собой чистые функции, тестировать их легко.
1. Кладём нужные значения в переменные модели, которые читает функция.
2. Читаем значение из той переменной, алгоритм которой мы хотим проверить.
3. Сравниваем фактическое значение с ожидаемым.

Ну и чем это отличается, скажем, от вызова функций системного API (формируем блок параметров, кладём туда нужное и вызываем системную функцию)?
Это минимум два шага назад по сравнению с обычным вызовом функции с параметрами!

Это не проблема. Функции получаются сами.

Допустим, у нас есть модель уравнения Quadric, которая имеет переменную roots.
Чтобы получить значение roots, пишем

myRoots = Quadric.roots(a, b, c)

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

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

Соответственно, компилятор сделает мне 15 функций из одной модели.