Русский
Русский
English
Статистика
Реклама

Prolog

Перевод Слышали о языке Prolog?

27.10.2020 16:17:12 | Автор: admin
Prolog это один из тех языков, которые программисты обычно изучают в самом начале карьеры (например в школе или в институте). Его, правда, забывают почти сразу же после того, как изучили.

Почему? Ну, лично я виню в этом индустрию разработки ПО. Я работаю в этой сфере последние 17 лет. Я участвовал в самых разных проектах, связанных с веб-разработкой и с большими данными (а именно, это были крупные интернет-площадки, ETL-конвейеры и прочее подобное). Суть в том, что за всё это время я не увидел ни одной строчки кода, написанной на Prolog.



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

Это заставило меня задуматься о том, насколько подобное заявление соответствует действительности.

Конечно, не может быть такого, чтобы совсем никто уже не пользовался этим языком. Хочу сразу сказать, что я не из тех программистов, которые изучали Prolog в университете. Я никогда не видел этого языка в расписании занятий. А узнал я о нём несколько лет назад, прочтя книгу Семь языков за семь недель (кстати, я полагаю, что эту книгу нужно обязательно прочитать каждому программисту). Одним из языков, о которых идёт речь в этой книге, был Prolog. И там, определённо, был раскрыт потенциал этого языка. Я снова задался вопросом о том, почему этим языком больше никто не пользуется.

Учитывая то количество разных языков программирования или фреймворков, которые каждую неделю появляются в различных сферах разработки ПО, можно предположить, что ИТ-экосистема постоянно меняется и весьма динамична. Но это не совсем так. На самом деле, если об этом поразмыслить, то можно понять, что здесь всё не так уж и непостоянно. В ИТ-индустрии присутствуют большие объёмы процедурного программирования, тут есть некоторое количество декларативного программирования, довольно много объектно-ориентированного программирования. А недавно (под недавно я понимаю последние несколько лет) заметным стало ещё и функциональное программирование. Существуют и другие парадигмы разработки ПО, но, если верить результатам исследования Stack Overflow 2020 года, десятка самых популярных языков программирования выглядит так, как показано на следующем рисунке.


Самые популярные языки программирования по данным исследования StackOverflow

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

  • Процедурное программирование: Python, Bash, PHP, JavaScript.
  • Объектно-ориентированное программирование: Python, C#, TypeScript, PHP, C++, Java.
  • Функциональное программирование: Python, JavaScript.
  • Декларативное программирование: SQL.

HTML/CSS я в этот список не включил. Как известно, поиск ответа на вопрос о том, считать ли их настоящими языками программирования, способен привести к бессмысленным спорам, а мне не хотелось бы устраивать тут словесную войну.

Но я не отступаю от своего изначального вопроса. А где же разработчики, занимающиеся логическим программированием? Где те специалисты, которые реально пользуются языком Prolog? Ведь этого языка даже нет в результатах исследования. Можете сами в этом убедиться.

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

Кто пользуется языком Prolog?


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

Общие сведения о Prolog


Prolog это язык логического программирования. Это означает, что программы на этом языке пишут в декларативном стиле (в противовес использования императивного стиля, применяемого в других распространённых языках). Тут используются такие понятия, как отношения, факты, правила. Они применяются при написании программ. Описав набор фактов и набор правил, можно строить запросы.

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

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

Давайте, например, поиграем в игру. Представим, что у нас имеются следующие магические числа: 1, 2, 4, 5. Нужно найти все решения задачи, суть которой заключается в поиске пар чисел, сумма которых будет равняться некоему заданному числу. Например, условие этой задачи можно описать так:

Учитывая то, что 1 - магическое числоУчитывая то, что 2 - магическое числоУчитывая то, что 4 - магическое числоУчитывая то, что 5 - магическое числоНайти пары чисел, сумма которых равняется 6.

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

Но решение этой задачи на Prolog, в сущности, представляет собой вышеприведённый фрагмент псевдокода. Чтобы этот код заработал, нужно лишь его переписать:

magicNumber(1).magicNumber(2).magicNumber(4).magicNumber(5).?- magicNumber(X), magicNumber(Y), plus(X, Y, 6)

Первые четыре строчки этого кода равносильны утверждениям о том, какие именно числа являются магическими. А потом мы просто говорим так: Переменные X и Y это вышеописанные магические числа. Сумма каких пар этих чисел равняется 6?.

Вот результаты работы этой программы:

1, 52, 45, 14, 2

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

Если вы хотите ознакомиться с другими примерами применения Prolog для решения подобных задач загляните сюда. Тут вы найдёте много интересного.

Теперь, учитывая мощь, которую даёт нам Prolog, подумаем о том, как вам ей воспользоваться, и о том, почему вы до сих пор не пишете на Prolog.

Какие современные задачи можно успешно решать, используя Prolog?


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

Одной из важнейших задач из сферы искусственного интеллекта является использование шаблонов при обработке естественного языка. Тут Prolog показывает себя во всей красе. И учтите, что технологии искусственного интеллекта применимы и для решения многих других важных задач. Я лишь говорю о том, что Prolog крайне полезен при решении задач определённого вида.

Учитывая это, подумаем о том, где именно Prolog способен принести наибольшую пользу. Где его можно применить? Итак, если вам приходится решать задачи, связанные с логическим программированием в ограничениях, тогда вам, возможно, захочется поближе познакомиться с Prolog. Это, например, задачи, связанные с планированием (которые, если вы ещё не пробовали их решать, весьма сложны), с проверкой цифровых схем, с управлением транспортными потоками.

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

Проекты, в которых применяется Prolog


Я собираюсь найти ответ на вопрос о том, где именно используется Prolog, с самого начала работы над статьёй.

Учитывая имеющиеся у меня данные, можно с уверенностью говорить о том, что существуют группы программистов, которые пишут на Prolog, и о том, что об этих группах знают немногие, так как то, чем они занимаются, не представлено некими широко известными проектами. А даже если Prolog-программисты работают над чем-то достаточно популярным, они не кричат об этом на каждом углу, так как на Prolog обычно пишут лишь небольшие части неких систем. Тем не менее, вот несколько примеров:

  • TerminusDB. Это RDF-база данных, управляемая моделями, поддерживающая контроль версий, дающая, при работе с большими объёмами данных, возможности, сопоставимые с возможностями Git. Она основана на Prolog. Эта база данных поддерживает стандартный RESTful API, позволяющий взаимодействовать с ней.
  • IBM Watson. Так оно и есть в недрах одного из главных проектов IBM используется Prolog. Конечно, этот проект нельзя назвать полностью основанным на Prolog, как TerminusDB, но в Watson используются возможности этого языка. Может, вы знаете об этом, может нет, но Watson создавался как помощник для экспертов, предназначенный для упрощения нахождения определённых данных или для поиска ответов на простые вопросы. Все заговорили о Watson после того, как эта система победила чемпионов телешоу Jeopardy!. Команда IBM использовала Prolog для разбора текстов на естественном языке и для перевода вопросов, задаваемых людьми, в форму, понятную Watson.
  • GeneXus. Эта low-code-платформа применяет Prolog для трансформации описаний нужного функционала в код приложений. Речь идёт о том, что программа сама пишет программы. Эта платформа поддерживает множество языков программирования, в частности Java, Ruby, C#, Objective-C.

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

Кстати, если поискать по слову prolog на GitHub, можно найти около 7000 репозиториев, в описании которых Prolog назван одним из используемых в них языков. Это позволяет сделать вывод о том, что многие пытаются писать на Prolog. Проблема тут, по моему мнению, в том, что многие из тех, кто пробовал Prolog, не довели свои проекты до состояния коммерчески успешных и широко известных (или хотя бы просто известных) продуктов.

Итоги


Давайте вернёмся к тому, с чего мы начинали. Действительно ли Prolog это язык, который учат только для того чтобы тут же забыть?

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

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

Что вы думаете о Prolog? Пользовались ли вы им? Собираетесь ли попробовать этот язык?



Подробнее..

Доказательное программирование

01.04.2021 22:22:46 | Автор: admin

Внимание!


  • Содержание данной статьи никак не связано с докладом академика А. П. Ершова "Научные основы доказательного программирования" 1984г.


  • Статья содержит утверждения, способные вызвать вспышки гнева и неконтролируемой агрессии. За последствия автор статьи ответственности не несет!


  • В тексте упоминаются следующие языки программирования: Java, Swift, Kotlin, Scala, Go, Haskell и др.


  • Эта статья антитезис. Автор ставит вопросы, но не считает своим долгом на все из них дать ответы.



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


И вот тут невольно возникает вопрос: не обошла ли медицина другую, казалось бы, не менее прогрессивную индустрию разработки программного обеспечения? Ок, у врачей есть этика, primum non nocere ("главное, не навреди"). Но разработчик не врач, и вроде как его это не касается или касается? Всегда ли разработчик выбирает лучшее решение для своего клиента? Не преследует ли время от времени разработчик какие-то свои цели (освоить новую технологию, попробовать новую либу, язык программирования и т.п.), о чем клиенту лучше не знать? Испытывает ли разработчик угрызения совести в связи с этим? Или это норма рынка? Ведь индустрия не стоит на месте, и если разработчик проигнорирует новомодное решение, то рискует не попасть на набирающий ход поезд под названием "мейнстрим"?


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


Давайте разбираться! На конкретных примерах.


"Чудесное" воскрешение Kotlin


Kotlin отечественный продукт, созданный в недрах небезызвестной российской компании JetBrains. Зачем действительно был создан этот язык, знает, видимо, только часть сотрудников этой компании, но можно пофантазировать. Какой программист не хочет создать свой язык? Вопрос риторический. В JetBrains тоже нашлись энтузиасты. Но мы знаем, что в этой компании проходимцев нет, все товарищи исключительно умные и образованные. В свои ряды они абы кого не берут. Если они создали язык и сказали, что язык крутой, и это то, что вам нужно, значит так оно и есть! Ребятам можно верить или нет?


Есть в JetBrains такой чувак (собирательный образ), который когда-то открыл для себя DSL. И в голову ему пришла "гениальная" идея, которая до этого, несомненно, не приходила в голову никому: не надо выбирать язык под задачу, вместо этого надо сделать язык для создания языков, и тогда разработчик сам будет создавать такой язык, который ему нужен для решения конкретной задачи! Бинго! Придумано сказано, сказано сделано. Сначала была статья, из которой уже было ясно, что перспектив у затеи немного, но это точно не было ясно чуваку из JetBrains. Если вы поняли, о каком продукте идет речь, то могли заметить: автор, задним числом все умные, а ты тогда это знал? Вы не поверите! На самом деле (философы, кстати, не любят эту фразу) это было бы понятно любому, кто читал анонс JetBrains и при этом имел достаточный опыт "полевой работы". Проблема кажется очевидной. Но не господам из знаменитой компании, которые уж точно знают, что программисту нужно, а что нет.


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


Но чувак из JetBrains слишком умен, чтобы ошибаться. Он уж точно знает, что это взлетит. Создается команда разработчиков, и они начинают пилить очередной, но, конечно же, уникальный инструмент для создания языков программирования MPS. Прошло 10 лет. Если вы посещали конференции с участием JetBrains, то могли обратить внимание на изобилие продуктов, которые компания продвигает. На любой вкус. Только MPS вы там не увидите, т.к. он стыдливо спрятан в стол. Нет, продукт существует и по сей день. И даже есть одна, кажется европейская, компания, которая до сих пор им пользуется. Большая, надо сказать, компания. Может поэтому продукт еще жив.


Но чувак из JetBrains не успокаивается он делает выводы. К сожалению, не те, которые следовало бы. Гений решает впасть в другую крайность не менее гениальную, чем первая. Теперь, говорит он, я сделаю один язык, но по-гениальному универсальный. Который заменит все остальные. Потому что новый язык будет лучшим и самым правильным. В нем будет все удобно, все продумано. Гении иначе не умеют. Другие языки создавались лузерами. Наш их всех победит! Создается команда идейных разработчиков, и они начинают пилить очередной, но, конечно же, уникальный язык программирования, и гений из JetBrains с оптимизмом смотрит в будущее.


Язык почти готов, публикуются анонсы. И тишина. Вроде новый же язык! Почему за ним не выстроилась очередь?! Может дело в том, что примерно в это же время увесистую дверь комьюнити разработчиков с ноги открыла "всплывшая" невесть откуда Scala (о ней чуть позже), которая очаровала своими возможностями, и Kotlin растворился в сиянии новой игрушки программистов? Казалось, что новенький продукт JetBrains идет к катастрофе.


Но гений из JetBrains не может ошибаться! Он понимает, что Kotlin появился слишком рано, его время еще не пришло. В конце концов, когда разрабы наиграются со Scala, они оценят всю гениальность отечественного языка. У Kotlin еще все впереди! И он не ошибся. Помощь пришла откуда не ждали.


Изначально Kotlin эксплуатировал инфраструктуру Java, что позволило быстро вывести его на рынок. Java же известна не только как "банковский язык", на котором написано, пожалуй, большинство современных решений для этой отрасли, но и как основной язык разработки для самой популярной мобильной ОС. Главный ее конкурент ОС от Apple требовал от разработчиков использования мумии под названием Objective C. Изначальный выбор этого языка понятен, но гениев из Apple (а там такие тоже есть!) таки пристыдили достаточно, чтобы они выкатили комьюнити более современный язык. Swift выглядел очень модно! Особенно по сравнению с трупом, который приходилось использовать до этого. Google должна была ответить на вызов!


Так случилось, что Google к тому времени уже какое-то время сотрудничала с JetBrains, которая на базе замечательной (без шуток) Idea помогла запилить Anroid Studio не менее замечательный (тоже без шуток) инструмент! И вот так оказалось, что у JetBrains есть подходящий язык. И выглядит он, что характерно, модно, как и Swift. Java-то уж 30 лет! Старье! А тут такой красавец! Нужно было действовать решительно. В итоге Kotlin получил титул основного языка разработки приложений для Android. Вот он звездный час гения из JetBtains! Теперь-то разработчики от него никуда не денутся! Признание! Google переписывает все свои доки, дублируя примеры на отечественном языке программирования. Более того, примеры на Kotlin становятся основными. Разработчики IT-гиганта, попавшие под чары "нового" языка, начали строить планы по использованию встроенного в него конструктора DSL для Постойте! Что? Конструктор DSL? Встроен? Как? Опять?


История эта обрывается на настоящем моменте. В итоге миллионы мобильных разработчиков получили новый язык, на который многие из них начали переходить по настоянию Google. Что же дает нам этот чудесный образец творчества лучших инженеров из Санкт-Петербурга? Да примерно ничего! Точнее, шанс уйти в минус. Получить дополнительные затраты на создание и, что важно, на поддержку своих продуктов. Сам язык, если присмотреться, несет в себе больше проблем, чем решений. Почему? Да потому-что сложность разработки не уменьшается от замены языка на другой язык того же типа. Сложность разработки, как правило, заключается в самой задаче, которую надо решить. И, чем сложнее задача, тем сложнее и дороже ее решение. То, что на одном языке код выглядит немного короче, чем на другом, мало что меняет. Послушайте доклады инженеров из JetBrains. На что они делают упор? На то, что код на Kotlin будет "намного" меньше, чем, скажем, на Java. Только вот они как-то не задумываются над простым вопросом: а за чей счет банкет? За счет чего ушли те "лишние" строки кода Java? Не пропала ли из кода какая-нибудь полезная информация, которую раньше можно было бы просто прочесть, но теперь о ней надо догадываться по косвенным признакам? Не задумывались ли гении из JetBrains о том, что хитрый вывод типов, который проделывает созданный ими несомненно гениальный компилятор, нужно будет проделывать каждый раз и разработчикам, которые будут читать "пожатый" код, тратя на это лишнее время?


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


IT-рынок захлебывается в потоке новомодных языков, которые скоро перестанут друг от друга отличаться. Каждый новый язык по словам их создателей "уникален" и "современен". Приводится масса причин, почему разработчик должен выбрать именно этот язык. Но так ли обстоят дела, как то декларируется? Действительно ли новый язык, новая библиотека, новый фреймфорк, новая СУБД решат больше проблем, чем добавят? Будут ли они эффективней, чем ранее разработанные инструменты, которые уже используются и по которым уже есть какая-то экспертиза?


Пока отложим эти вопросы и двинемся дальше...


Свидетели Scala


Вы когда-нибудь общались с представителем "секты свидетелей" Scala? Он на вас будет смотреть свысока, даже если на 30 см ниже ростом. Потому что он познал. А вы не познали. Он "так может", а вы и "ваш язык" нет. За его запятой может прятаться вселенная, а за вашим "плюсиком" ну максимум конкатинация строк. Какая банальность! Его код это высокоинтеллектуальный ребус для таких же просветленных, как он сам. На самом деле это ребус даже для него самого, но он от этого лишь получает удовольствие. А вы со "своим языком" такого удовольствия лишены. Вы обречены писать банальности с использованием предопределенного набора банальных операторов. И символы, которые вы пишете, не имеют никакой дополнительной высокоинтеллектуальной нагрузки Кажется, что разработчики Scala попытались запихать в язык все, что смогли вспомнить. И если что-то не запихивалось, раздвигали и запихивали. Трудно сказать, чего там нет. И, казалось бы, вот Ну что еще нужно? Безграничные возможности для самовыражения!


Говорят, что "ажиотаж" вокруг Scala подутих в 2017-2018гг. Как по мне, ажиотажа, собственно, никогда и не было. Был интерес, было любопытство. Короткий период. Год-два. Но да, некоторые смельчаки не заметили подвоха и погрузились в Scala по пояс. Возможно, в их вселенной какой-то ажиотаж и был. Но большинство поматросило модную штучку и оставило в покое. А те, кто влез, те да Те влипли по-полной. Но признаться в этом себе невероятно сложно. Сложно признавать подобные ошибки. Лучше сказать, что язык замечательный, это программисты плохие. Не доросли. Не доучились. Низкий IQ. Язык для избранных. На конференции свидетель Scala показывает слайд с парой строк, выглядящих как обычное арифметическое выражение. Но по хитрому прищуру докладчика все понимают, что здесь есть второе дно. И что эти две строки надо "читать". И дальше он с упоением рассказывает, как именно. Почему он так сделал? Потому что может! Потому что язык так может.


Согласно индексу TIOBE за март 2021, Scala и Kotlin находятся на соседних строчках. Считаю, замечательное соседство! Индустрия в безопасности, ее иммунная система справилась с недугом и миновала пропасть, по краю которой прошла. Да, есть потери. Scala поглотила слабых духом и оставила за собой шлейф из начатых проектов, от которых не просто будет избавиться. Но ничего. Поглощенным поможет реабилитация, а проекты рано или поздно умрут своей смертью. Все как обычно. Все имеет начало и конец.


А есть ли что-то подобное в фарме? Когда-то фенобарбитал можно было купить без рецепта, сейчас же во многих странах его вообще нет запретили (основное действующее вещество "Корвалола"). Стволовые клетки колют как витамины, но уже многие знают, чем это может обернуться. В 30-е годы прошлого века Кюри толкали свою радиоактивную косметику "Tho-Radia" в итоге она была признана "ядовитой". Детокс-терапия клизма, диета, "очищение" очень модно (не запрещено)!


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


В индустрии разработки пока ничего такого нет. Нам выкатывают нечто, что выглядит соблазнительно, и в итоге, в лучшем случае с небольшими потерями, мы проходим сложный период, движемся дальше. Но так бывает не всегда. Мириады неоновых вывесок с рекламой самых новых технологий и решений обволакивают неподготовленный ум начинающего программиста и запускают свои щупальца в его новые проекты. Да и опытный программист может быть усыплен очаровательным пением коварных IT-сирен. Все ли из того, что вы задействовали в своем проекте, вам действительно нужно? Или это дань моде, когда страх "отстать" не оставляет вам выбора? Действительно ли ваш выбор продиктован личным опытом? Возможно ли иметь качественный личный опыт, например на рынке разработки мобильных приложений, когда Google меняет правила игры раз в несколько месяцев?


Ну вот, опять! Вопросы, вопросы...


Сверхновый GO


Вот уж где создатели языка определенно постарались. Go, по сравнению с Kotlin, это действительно большая работа. За простотой синтаксиса скрывается целая сеть сложных компромиссов. Несомненно, назвать этот язык чьим-то клоном никак нельзя. Современный, продуманный, легко читаемый. Последнее, при таком синтаксическом аскетизме, кажется невероятным достижением разработчиков. Чудо чудесное, не иначе!


Не слишком ли все хорошо? Что-то здесь не так, что-то мы упускаем, что-то ускользает от нашего взора. Вот! Кажется я вижу чьи-то торчащие уши! Взять тесты. Почему здесь так много комментариев? Как это? Они интерпретируются? Это что, значит, в комментах спрятан еще один язык? Дополнительный синтаксис, которого как бы нет? Но он как бы не подходит под утверждение "ничего лишнего", так что там ему и место нечего портить стройный язык всякой второстепенной чепухой! На самом деле (опять эта нефилософская фразочка) тут нет вины разработчиков: причина такого решения в самой природе тестов и общей проблеме всех современных мейнстримовых языков. Но это тема отдельной статьи. Сейчас не об этом. Так что здесь я разработчиков не виню они сделали все, как принято. Хотя осадочек таки есть Эх!


Легенда гласит, что инженеры Google создавали язык для внутренних нужд и что он должен был быть достаточно простым и доступным даже слесарям из хозгруппы. Если это так, то многое становится понятным. Иначе сложно представить, что еще могло заставить разработчиков языка так поступить с одной из базовых концепций ООП. Когда я приношу домой новый телевизор, к нему прилагается пульт. Когда я сажусь на водительское место в авто, там уже есть органы управления. Я не ношу их с собой, как и не покупаю телевизор к уже имеющемуся у меня пульту. К новому телефону продается чехол, который выпускают специально под данный девайс, а не наоборот. Что же с инженерами Google не так? Почему они делают это с нами? Где чертов пульт?!


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


Что же подсказывает нам доказательная медицина? Следует ли нам избавиться от традиционных методов лечения, когда врач изучает все, что касается человеческого организма (анатомию, физиологию, биохимию), и при этом знает лекарственные вещества, оставить хирургов, а обычных терапевтов заменить кабинками "Instant Doctor", которые будут следовать доказанному протоколу лечения и использовать только средства с доказанной эффективностью? Насколько все можно упростить? Реальность такова, что доказательство эффективности различных химических веществ мероприятие крайне недешевое и доступно только Большой Фарме. А те не будут тратить деньги на лекарства, на которых они не смогут сорвать куш. Так что большинство лекарств существующему стандарту эффективности не будут соответствовать никогда. Эффективность парацетамола не доказана, и никто не знает, почему он делает то, что делает. Но помогает же!


Разработчики Kotlin забыли (или никогда не знали), почему в Java нет перегрузки операторов. Создатели Scala вообще об этом не задумывались. А инженеры из Google по какой-то причине решили, что их интерпретация основ ООП поистине революционна. Это те самые случаи, когда новым выглядит хорошо забытое старое. Смущает то, что нет какого-либо серьезного анализа этих языков, наоборот Интернет переполнен исключительно хвалебными отзывами. Т.е. ни о попытке как-то подтвердить эффективность навязываемого инструмента, ни и о банальной критике этих решений и речи нет. В чем причина?


Можно взглянуть на все с другой стороны. Не нравится, не ешь. Дай рынку насытиться! Изобилие это хорошо! Есть конкуренция, есть выбор. И кажется, что все так, выбор есть, но можем ли мы правильно выбрать? И всегда ли этот выбор действительно есть? Какова цена ошибки? Каким требованиям должен соответствовать язык программирования в вашем случае? Каким стандартам соответствует выбранный язык? Только тем, которые сформулировали сами создатели языка? Очень надежно! Или он просто вам понравился? Вы хотите его изучить, потому что коллеги о нем все время говорят, хвалят и все такое? А знает ли об этом ваш заказчик? Готов ли он оплачивать ваше обучение?


Вы выбрали новую СУБД, которая только появилась на рынке. Но исследовал ли кто-то ее надежность? Кто авторитетно может это исследование подтвердить? Вы? Ваш коллега? Он знает, как проводить такие исследования? Точно? Или исследование будет перенесено в продакшн и, конечно, оплачено ничего не подозревающим клиентом? Не стоит ли вспомнить здесь об этике? Ведь в данный момент для этого клиента вы олицетворяете все программистское сообщество, и если дискредитируете свою работу, то вы дискредитируете тем самым все сообщество, перекладывая стоимость своих ошибок на него, как это делают создатели разного рода новых инструментов и языков программирования. Без контроля, без сертификации, под честное слово.


Ну и напоследок...


Альтернативная медицина


Опять провал, опять ничего не выходит. Ошибки лезут из всех щелей. Паника. Что же делать? Как все исправить? Как сделать так, чтобы все работало с первого раза, а объем проблем перестал нарастать, словно снежный ком? Надо начать все сначала, время еще есть, но где гарантия, что результат будет другим?.. Что это за сладкий шепот в левом ухе? Кажется, он что-то пытается сказать! Шепот: "Функциональный язык". Что? Шепот: "Выбери функциональный язык забей на постылую императивщину, пора сменить парадигму". О чем это он? Ну-ка ну-ка, Интернет Так-так-так. Ого! Какая интересная концепция! Шепот, где же ты был раньше? Наконец-то решение найдено, теперь все заработает с пол-оборота! Но что-то терзает душу молодого разработчика, что-то не дает покоя что же опять не так?


Мы нашли вашу кучу, проектов на Haskell в ней не было.


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


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


А верно ли вообще ставить вопрос таким образом? Действительно ли есть из чего выбирать? Возьмем функциональный Haskell, который позиционируется как язык общего назначения. Что бы это ни значило, тот же самый ярлык несут на себе такие монстры, как C++, Java, С#. Может ли Haskell составить им конкуренцию на этом поле? Вот реально? В теории несомненно. Но на практике, как говорится, не тратьте свое время. Хотя такой язык, несомненно, достоин того, чтобы с ним познакомиться в свободное от работы время. Что же с ним не так?


Придется совершить каминг-аут: я обожаю Prolog! Как и Haskell, он относится к семейству декларативных языков. Это когда вы не говорите машине, как именно нужно что-то сделать, не указываете последовательность действий, которые следует совершить, а устанавливаете некие границы и формулируете задачу, т.е. что нужно сделать, при этом на вопрос как пытается ответить уже сам компилятор. И это, казалось бы, хорошо. Но все меняется в тот момент, когда программа начинает делать что-то не то. Не то, что от нее ожидали. Возникает закономерное желание понять: почему она поступила именно так? И вот здесь выясняется, что любой императивный язык буквально "ткнет пальцем" в место в коде, где проявилась проблема и откуда ее можно локализовать. С декларативными языками иначе. Там нет привычного нам стека выполнения, который однозначно бы мапился на код. В случае с Prolog он может совершить миллион сопоставлений, прежде чем ошибка даст о себе знать. Это как если бы ваш стектрейс состоял из миллиона строк и в какой-то одной из этих строк что-то пошло не так, что-то не сошлось, какое-то правило не сработало.


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


Как же ориентироваться в этом океане технологий? Может, есть в нем тихие гавани, которые помогут найти решение? Взять HTML. Это не просто язык, это промышленный аппликационный стандарт. Т.е. речь не о стандарте, описывающем сам язык, а о стандарте для браузеров, которые обязаны его поддерживать. Ни анархии тебе, ни конкуренции. И кажется, что всех все устраивает. Его неизменный попутчик JavaScript при всей своей убогости тоже стандарт; лишь 10 лет назад разработчики браузеров договорились о том, чтобы заложить первый кирпич в фундамент куда более продуманной технологии WebAssembly. Чуть хуже дела обстоят в мобильной разработке. Тут таких стандартов, к сожалению, нет. Хотя попытки их внедрить таки имеют место быть. От унылой Cordova, до новенького Flutter. Но без поддержки всех участников рынка эти попытки обречены. Отрасль, скорее, идет в обратную сторону: Huawei выкатывает свою собственную ОС, и, учитывая размер рынка Китая, игнорировать ее, похоже, не получится.


Разработчики же прочих платформ в большинстве своем не накладывают никаких ограничений на используемые технологии (Apple не в счет), но и не делают попыток о чем-то договориться. Пожалуй, Microsoft достигла наибольших успехов с C#, рождение которого стало итогом войны с Sun Microsystems за право вносить изменения в стандарт Java. Microsoft добилась впечатляющих успехов в продвижении своего детища, но так и не смогла сдвинуть Java с ее пьедестала. Может, в будущем? Кто знает.


Способно ли развитие стандартизации изменить ситуацию? Или не стоит ничего менять, и так хорошо? Или не хорошо? Кажется, что спрос есть. Пример EJB, который канул в лету вместе с Sun, показывает, что на самом деле (вот опять) движение в эту сторону возможно и рынок готов его поддержать. Но неудача EJB могла быть неверно интерпретирована, что и привело к топтанию на месте. А может быть, у затеи изначально не было шансов? Как бы то ни было, при всем разнообразии решений то и дело вываливающихся на и без того переполненный рынок, кажется, что ситуация напоминает настоящий застой. Парадокс или кризис? Или все ок, и думать тут особо не о чем? Как воспринимать все это изобилие? Как новые игрушки, с которыми интересно повозиться (за чей-то счет, естественно), или как пилюли, эффективность которых должна быть подтверждена? Как воспринимать эти "игрушки" в руках коллег (в широком смысле), результаты игр которых разгребать потом придется вам? Может быть, новая этика?


Вопросы, вопросы, вопросы...


Я все сказал
Подробнее..

Из песочницы Проектируем мульти-парадигменный язык программирования. Часть 1 Для чего он нужен?

29.09.2020 12:13:11 | Автор: admin
Хабр это замечательное место, где можно смело делиться своими идеями (даже если они и выглядят безумно). Хабр видел много самодельных языков программирования, расскажу и я о своих экспериментах в этой области. Но мой рассказ будет отличаться от остальных. Во-первых, это будет не просто язык программирования, а гибридный язык, сочетающий в себе несколько парадигм программирования. Во-вторых, одна из парадигм будет довольно необычной она будет предназначена для декларативного описания модели предметной области. А в-третьих, сочетание в одном языке декларативных средств моделирования и традиционных объектно-ориентированного или функционального подходов способно породить новый оригинальный стиль программирования онтологически-ориентированное программирование. Я планирую раскрыть в первую очередь теоретические проблемы и вопросы, с которыми я столкнулся, и рассказать не только о результате, но и о процессе создания дизайна такого языка. Будет много обзоров технологий и научных подходов, а также философских рассуждений. Материала очень много, придется разбить его на целую серию статей. Если вас заинтересовала такая масштабная и сложная задача, приготовьтесь к долгому чтению и погружению в мир компьютерной логики и гибридных языков программирования.

Вкратце опишу основную задачу


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

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

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

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

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


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

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

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

Почему я считаю декларативный стиль программирование недооцененным


Попробую обосновать свою точку зрения.

Для этого рассмотрим, что из себя может представлять программное решение. Ее основные компоненты это: клиентская часть (десктоп, мобильные, web приложения); серверная часть (набор отдельных сервисов, микросервисов или монолитное приложение); системы управления данными (реляционные, документо-ориентированные, объектно-ориентированные, графовые базы данных, сервисы кэширования, поисковые индексы). Программному решению приходится взаимодействовать не только с людьми пользователями. Частой задачей является интеграция с внешними сервисами, предоставляющими информацию через API. Так же источниками данных могут быть аудио и видеодокументы, тексты на естественном языке, содержимое web-страниц, журналы событий, медицинские данные, показания датчиков и т. п.

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

Задача связывания содержимого базы данных с объектами приложения тоже не так проста. Если структура таблиц в хранилище соответствует структуре понятий на уровне приложения, то можно воспользоваться ORM технологией. Но для более сложных случаев чем доступ к записям по первичному ключу и CRUD операций приходится выделить отдельный слой логики работы с базой данных. Обычно схема базы данных имеет максимально общую форму, так, что с ней могут работать разные сервисы. Каждый из которых отображает эту схему данных на свою объектную модель. Структура приложения становится еще более запутанной, если приложение работает не с одним хранилищем данных, а с несколькими, разного типа, загружает данные из сторонних источников, например, через API других сервисов. В этом случае необходимо создать унифицированную модель предметной области и отобразить на нее данные из разных источников.
В некоторых случаях модель предметной области может иметь сложную многоуровневую структуру. Например, при составлении аналитических отчетов одни показатели могут строиться на основе других, которые в свою очередь будут источником для построения третьих и т. д. Также входные данные могут иметь слабоструктурированную форму. Эти данные не имеют строгой схемы как, например, у реляционной модели данных, но все же содержат какую-либо разметку, позволяющую выделить из них полезную информацию. Примерами таких данных могут быть ресурсы семантической паутины, результаты парсинга WEB-страниц, документы, журналы событий, показания датчиков, результаты предварительной обработки неструктурированных данных, таких как тексты, видео и изображения и т.п. Схема данных этих источников будет строиться исключительно на уровне приложения. Там же будет и код, преобразующий исходные данных в объекты бизнес-логики.

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

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


Предположим, у нас есть 2 CSV файла. В первом файле:

В первой колонке хранится идентификатор клиента.
Во второй дата.
В третьей выставленная сумма счета,
В четвертой сумма оплаты.

Во втором файле:
В первой колонке хранится идентификатор клиента.
Во второй имя.
В третьей адрес электронной почты.

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

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

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

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

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

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

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

Сначала мы объявляем факты с содержимым таблиц в формате: ID таблицы, строка, колонка, значение:

cell(Table1,1,1,John). 

Затем дадим имена каждой из колонок:

clientId(Row, Value) :- cell(Table1, Row, 1, Value).

После чего можно объединить все колонки в одно понятие:

bill(Row, ClientId, Date, AmountToPay, AmountPaid) :- clientId(Row, ClientId), date(Row, Date), amountToPay(Row, AmountToPay), amountPaid(Row, AmountPaid).unpaidBill(Row, ClientId, Date, AmountToPay, AmountPaid) :- bill(Row, ClientId, Date, AmountToPay, AmountPaid),  AmountToPay >  AmountPaid.debtor(ClientId, Name, Email) :- client(ClientId, Name, Email), unpaidBill(_, ClientId, _, _, _).

И так далее.

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

Как же нам совместить основной функциональный или объектно-ориентированный язык разработки с декларативной природой модели предметной области?


Наиболее известным подходом является предметно-ориентированное проектирование (Domain-Driven Design). Эта методология облегчает создание и реализацию сложных моделей предметной области. Она предписывает, чтобы все понятия модели были выражены в коде явным образом в слое бизнес логики. Понятия модели и реализующие их элементы программы должны быть как можно ближе к друг другу и соответствовать единому языку, понятному как программистам, так и экспертам по предметной области.

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

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

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

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

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

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

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

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

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

04.11.2020 12:10:51 | Автор: admin
Продолжаем рассказ о создании мульти-парадигменного языка программирования, поддерживающего декларативный логический стиль для описания модели предметной области. Прошлые публикации находятся здесь и здесь. Теперь пришло время для описания основных особенностей и требований к языку описания модели предметной области. Но для начала сделаем небольшой обзор наиболее популярных языков представления знаний. Это довольно обширная область, имеющая давнюю историю и включающая ряд направлений логическое программирование, реляционное исчисление, технологии семантической паутины, фреймовые языки. Я хочу сравнить такие языки как 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 во встроенном предикате сравнения.

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


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

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 Логика первого порядка На правила Системы, основанные на правилах, сопоставление с образцом.
RDFS Граф На связи между понятиями Схема данных WEB ресурса
OWL Дескрипционная логика На связи между понятиями Онтологии
SWRL Урезанная версия логики первого порядка как у Datalog На правила поверх связей между понятиями Онтологии
Flora-2 Фреймы + логика первого порядка На правила поверх структуры объектов Базы данных, моделирование сложных систем, интеграция разрозненных данных
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
Подробнее..

Проектируем мульти-парадигменный язык программирования. Часть 4 Основные конструкции языка моделирования

26.11.2020 14:19:49 | Автор: admin
Продолжаем рассказ о создании мульти-парадигменного языка программирования, сочетающего декларативный стиль с объектно-ориентированным и функциональным, который был бы удобен при работе со слабоструктурированными данными и интеграции данных из разрозненных источников. Наконец-то после введения и обзоров существующих мульти-парадигменных технологий и языков представления знаний мы добрались до описания той части гибридного языка, которая ответственна за описание модели предметной области. Я назвал ее компонентой моделирования.
Компонента моделирования предназначена для декларативного описания модели предметной области в форме онтологии сети из экземпляров данных (фактов) и абстрактных понятий, связанных между собой с помощью отношений. В ее основе лежит фреймовая логика гибрид объектно-ориентированного подхода к представлению знаний и логики первого порядка. Ее основной элемент понятие, описывающее моделируемый объект с помощью набора атрибутов. Понятие строится на основе других понятий или фактов, исходные понятия назовем родительскими, производное дочерним. Отношения связывают значения атрибутов дочернего и родительских понятий или ограничивают их возможные значения. Я решил включить отношения в состав определения понятия, чтобы вся информация о нем находилась по возможности в одном месте. Стиль синтаксиса для определений понятий будет похож на 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 Обзор языков представления знаний
Подробнее..

Роль логического программирования, и стоит ли планировать его изучение на 2021-й

22.12.2020 00:22:49 | Автор: admin

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

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

"Мда" - думаете Вы, и этим все сказано. Сложно! И тут наш отважный герой должен бы был перейти по второй ссылке, но я позволю себе сделать небольшую вставку, описав главное действующее лицо: Вы, по моей задумке, новичок в программировании, а даже если и нет, то точно не знакомы с логическим его обличием. Если же читатель уже несколько (или даже много) искушен знаниями в этой области, то рекомендую прочитать статью Что такое логическое программирование и зачем оно нам нужно, раз уж в вас горит интерес и любопытство к теме, а изучение материала ниже оставьте менее опытным коллегам.

Итак, пришло время второй ссылки. Что это будет? Статья на Хабре? Может быть статья на ином ресурсе? Прочитав пару первых абзацев на разных сайтах, вы, скорее всего, мало что поймете, так как, во-первых, материал обычно ориентирован на знающего читателя, во-вторых, хорошей и понятной информации по теме не так много в русскоязычном интернете, в-третьих, там почему-то постоянно речь идёт о некоем "прологе" (речь о языке программирования Prolog, разумеется), но сам язык, кажется, использует мало кто (почётное 35 место в рейтинге TIOBE). Однако наш герой не теряет мотивации и, спустя некоторое время, натыкается на эту самую статью, желая, все-таки понять:

  • Что такое логическое программирование

  • Какова история его создания и фундаментальные основы (серьезно, какому новичку это может быть интересно?)

  • Зачем и где его применяют

  • Стоит ли лично вам его изучать

Что ж, постараюсь ответить просто и понятно, обходя страшные термины и не вспоминая исторических личностей.

Что такое логическое программирование

В школе на уроках информатики многие, если не все, слышали про Pascal (а кто-то даже писал на нем). Многие также могли слышать про Python, C/C++/C#, Java. Обычно программирование начинают изучать именно с языков из этого набора, поэтому все привыкли, что программа выглядит как-то так:

НачатьКоманда1Команда2Если УСЛОВИЕ  Команда3Иначе  Команда4Закончить

Этот яркий, но малоинформативный пример призван показать, что обычно команды выполняются одна за другой, причем мы ожидаем, что следующие инструкции (команды) могут использовать результат работы предыдущих. Также мы можем описывать собственные команды, код которых будет написан подобным образом. Остановимся на том, что как завещал Фон Нейман, так компьютер и работает. Машина глупа, она делает то, что скажет программист, по четкому алгоритму, последовательно выполняя инструкции. Не может же, в конце концов, компьютер, подобно мыслящему живому существу, делать выводы, строить ассоциативные ряды Или может?

Давайте устроимся поудобнее рядом со своим компьютером и порассуждаем о жизни и смерти вместе с Аристотелем:

Всякий человек смертен.

Сократ - человек.

Следовательно, Сократ смертен.

Звучит логично. Но есть ли способ научить компьютер делать выводы как Аристотель? Конечно! И вот тут мы вспомним о Prolog-e, который так часто мелькает при поиске информации о логическом программировании. Как несложно догадаться, Prolog (Пролог) является самым популярным чисто логическим языком программирования. Давайте рассуждения об этом языке оставим на следующие разделы статьи, а пока что продемонстрируем "фишки" логических языков, используя Пролог.

Напишем небольшую программу, где перечислим, кто является людьми (ограничимся тремя) и добавим правило "всякий человек смертен":

% Всё, что после знака процента в строке - комментарииhuman('Plato'). % Платон - человекhuman('Socrates'). % Сократ - тоже человекhuman('Aristotle'). % Конечно, человеком был и Аристотель% ...и др. философыmortal(X) :- human(X). % Читаем так: "X смертен, если X - человек"

Что ж, давайте спросим у компьютера, смертен ли Сократ:

?- mortal('Socrates').true.

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

Так, теперь стоит успокоиться и разобраться, что же произошло. Вначале мы записали т. н. факты, то есть знания нашей программы о мире. В нашем случае ей известно лишь то, что Платон, Сократ и Аристотель - люди. Но что за странная запись "human('Socrates')." и почему это выглядит как функция? На самом деле "human" и "mortal" - предикаты от одной переменной. Да, тут уже пошли термины, но постараюсь объяснять их просто и понятно для тех, кто привык к императивному нормальному программированию.

Логическое программирование основано на логике предикатов. Предикатом называется (и здесь я позволю себе вольность) функция от нуля или более переменных, возвращающая значение логического типа (истина (true) или ложь (false)). Факт - это предикат с определенным набором параметров и заведомо известным значением.

% слова с большой буквы Prolog считает переменными, поэтому их следует заключать в кавычкиlike('Petya', 'Milk'). % программа знает, что Петя любит молокоgood('Kesha'). % Кеша хорошийnumber_of_sides('Triangle', 3). % у треугольника три вершиныlike('Misha', X). % не является фактом, так как значение переменной X не определено

Помимо фактов в логической программе присутствуют правила вывода. В данном случае это "mortal(X) :- human(X).". Набор правил вывода - это знания нашей программы о том, как выводить (искать/подбирать) решение. Правила записываются следующим образом:

a(X,Y,Z) :- b(X), c(Y,Z), d().

Предикат a от трех аргументов вернет истину, если удастся доказать истинность предикатов b, c и d. Читаются правила справа налево следующим образом: "Если b от X истинно И c от X, Y истинно И d истинно, то a от X, Y, Z истинно".

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

% Опишем набор фактов о том, кто что обычно ест на завтрак в семье Петиeat(father, cheese).eat(father, apple).eat(father, melon).eat(mother, meat).eat(sister, meat).eat('Petya', cheese).eat(brother, orange).

Теперь начнём делать запросы к программе (всё те же предикаты):

?- eat(father, apple). % ест ли отец яблокиtrue.?- eat(father, meat).  % ест ли отец мясоfalse.?- eat(sister, X). % что ест сестраX = meat.?- eat(X, cheese). % кто ест сырX = father ;X = 'Petya'.?- eat(X, Y). % кто что естX = father,Y = cheese ;X = father,Y = apple ;X = father,Y = melon ;X = mother,Y = meat ;X = sister,Y = meat ;X = 'Petya',Y = cheese ;X = brother,Y = orange.

Как видите, очень удобно. Стало быть, первым и очевидным применением логического программирования (об эффективности поговорим ниже) является работа с базами данных. Мы можем достаточно естественным образом описывать запросы, комбинируя предикаты, причем научить писать такие запросы можно даже человека, совершенно не знакомого с логическим программированием.

Какие задачи и как можно решать с помощью логического программирования

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

d(X,X,1) :- !. % производная X по X = 1d(T,X,0) :- atomic(T). % производная константы = 0d(U+V,X,DU+DV) :- d(U,X,DU), d(V,X,DV). % производная суммы = сумме производныхd(U-V,X,DU-DV) :- d(U,X,DU), d(V,X,DV). d(-T,X,-R) :- d(T,X,R).d(C*U,X,C*W) :- atomic(C), C\=X, !, d(U,X,W). % производная константы, умноженной на выражение = константе на производную от выраженияd(U*V,X,Vd*U+Ud*V) :- d(U,X,Ud), d(V,X,Vd). % производная произведенияd(U/V,X,(Ud*V-Vd*U)/(V*V)) :- d(U,X,Ud), d(V,X,Vd). 

Запустим:

?- d((x-1)/(x+1),x,R).   R =  ((1-0)*(x+1)-(1+0)*(x-1))/((x+1)*(x+1)).

Пусть производная получилась довольно громоздкой, но мы и не ставили цель её упростить. Главное, из примера видно, что правила вывода производной на Prolog-е описываются очень близким образом к их математическому представлению. Чтобы сделать подобное на привычных языках программирования, пришлось бы вводить понятие дерева выражений, описывать каждое правило в виде функции и т. д. Тут же мы обошлись 8-ю строками. Но здесь важно остановиться и задуматься: компьютер не начал работать как-то иначе, он все ещё обрабатывает последовательности команд. Стало быть, те самые деревья, которые где-то все-таки должны быть зашиты, чтобы программа работала, действительно присутствуют, но в неявном виде. Деревья эти именуют "деревьями вывода", именно они позволяют подбирать нужные значения переменных, перебирая все возможные варианты их значений (существует механизм отсечения, который является надстройкой над логической основой языка, но не будем об этом).

Давайте на простом примере рассмотрим, что из себя представляет перебор, а затем то, чем он может быть опасен.

speciality(X,tech_translator) :- studied_languages(X), studied_technical(X). % X - технический переводчик, если изучал языки и технические предметыspeciality(X,programmer) :- studied(X,mathematics), studied(X, compscience). % X - программист, если изучал математику и компьютерные наукиspeciality(X,lit_translator) :- studied_languages(X), studied(X,literature). % X - литературный переводчик, если изучал языкиstudied_technical(X) :- studied(X,mathematics). % X изучал технические предметы, если изучал математикуstudied_technical(X) :- studied(X,compscience). % ...или компьютерные наукиstudied_languages(X) :- studied(X,english). % X изучал языки, если изучал английскийstudied_languages(X) :- studied(X,german). % ...или немецкийstudied(petya,mathematics). % Петя изучал математикуstudied(petya,compscience). % ...компьютерные наукиstudied(petya,english). % ...и английскиstudied(vasya,german). % Вася изучал немецкийstudied(vasya,literature). %...и литературу

Спросим, кто из ребят, известных компьютеру - технический переводчик:

?- speciality(X,tech_translator).X = petya ;X = petya ;false.

Агато есть Петя, Петя и ложь Что-то не так, подумает программист и попробует разобраться. На самом деле, перебирая все варианты значений X, Пролог пройдёт по такому дереву:

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

Представим, что перед нами в ячейках расположены три чёрных и три белых шара (как на картинке выше), которые требуется поменять местами. За один ход шар может или передвинуться в соседнюю пустую клетку, или в пустую клетку за соседним шаром ("перепрыгнуть" его). Решать будем поиском в ширину в пространстве состояний (состоянием будем считать расположение шаров в ячейках). Суть этого метода заключается в том, что мы ищем все пути длины 1, затем все их продления, затем продления продлений и т. д., пока не найдем целевую вершину (состояние). Почему поиск в ширину? Он первым делом выведет самый оптимальный путь, то есть самый короткий. Как может выглядеть код решения:

% Обозначения: w - белый шар, b - чёрный, e - пустая ячейкаis_ball(w). % w - шарis_ball(b). % b - шарnear([X,e|T],[e,X|T]) :- is_ball(X). % если фишка рядом с пустой ячейкой, то можно переместитьсяnear([e,X|T],[X,e|T]) :- is_ball(X).jump([X,Y,e|T],[e,Y,X|T]) :- is_ball(X), is_ball(Y). % если за соседним шаром есть пустая ячейка, то можно переместитьсяjump([e,Y,X|T],[X,Y,e|T]) :- is_ball(X), is_ball(Y).% предикат перемещения. Мы или рассматриваем первые элементы списка, или убираем первый элемент и повторяем операциюmove(L1,L2) :- near(L1,L2). move(L1,L2) :- jump(L1,L2).move([X|T1],[X|T2]) :- move(T1,T2).% предикат продления текущего пути. Если из состояния X можно перейти в состояние Y и% Y не содержится в текущем пути, то Y - удачное продлениеprolong([X|T],[Y,X|T]) :- move(X,Y), not(member(Y,[X|T])).% Первый аргумент - очередь путей, второй - целевое состояние, третий - результат, то есть найденный путьbdth([[X|T]|_],X,R) :- reverse([X|T], R). % Поиск в ширину нашел решение, если первый элемент пути совпадает с целью (путь наращивается с начала, так что перевернем результат)bdth([P|QI],Y,R) :- bagof(Z,prolong(P,Z),T), append(QI,T,QO), !, bdth(QO,Y,R). % Ищем все возможные продления первого пути и кладём в очередь, рекурсивно запускаем поискbdth([_|T],Y,R) :- bdth(T,Y,R). % Если продлений на предыдущем шаге не нашлось, то есть bagof вернул false, убираем первый путь из очередиbsearch(X,Y,R) :- bdth([[X]],Y,R). % Удобная обёртка над предикатом bdth% Предикат, который решает нашу задачу и выводит результат и длину найденного пути на экранsolve :- bsearch([w,w,w,e,b,b,b],[b,b,b,e,w,w,w],P), write(P), nl, length(P, Len), write(Len), nl.

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

Со стороны улучшения алгоритма можно предложить использовать поиск в глубину. Но как же, он ведь не даст оптимального результата? Сделаем просто: ограничим глубину поиска. Так мы точно не забьём стек и, возможно, получим ответ. Поступим так: проверим, есть ли пути длины 1, затем длины 2, затем длины 4 и т. д. Получим так называемый поиск с итерационным заглублением:

% Первый аргумент - текущий путь, второй - целевое состояние, третий - результат, то есть найденный путьdpth_id([X|T],X,R,0) :- reverse([X|T], R). % Успешное окончание поискаdpth_id(P,Y,R,N) :- N > 0, prolong(P,P1), N1 is N - 1, dpth_id(P1,Y,R,N1). % Если счётчик >0, то уменьшаем его и продолжаем поиск рекурсивноgenerator(1). % Изначально предикат вернет 1generator(N) :- generator(M), N is M + 1. % Рекурсивно получаем 2, 3, 4 и т. д.isearch(X,Y,R) :- generator(D), dpth_id([X],Y,R,D). % Удобная обертка, которая будет вызывать поиск от каждого натурального значения глубины.

Во-первых, здесь стоит обратить внимание, что мы не используем очереди, а также внешних предикатов (кроме reverse, но он для красоты). Это потому, что поиск в глубину естественен для Пролога (ищите картинку с деревом выше). Во-вторых, пусть мы и делаем вроде как "лишние" действия, то есть для каждого нового значения глубины проходим по всем путям заново, мы практически не теряем в скорости относительно поиска в ширину (может в несколько раз, но не на порядок), при этом значительно экономим память. В-третьих, мы наконец-то получаем ответ, и это самое главное. Приводить его не буду, так как он займет много места, но для интриги оставлю вам его длину: 16.

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

near([w,e|T],[e,w|T]).near([e,b|T],[b,e|T]).jump([w,X,e|T],[e,X,w|T]) :- is_ball(X).jump([e,X,b|T],[b,X,e|T]) :- is_ball(X).

Хм, код стал даже проще. Запустив мы убедимся, что поиск (оба варианта), во-первых, работает, во-вторых, работает быстро, в-третьих, работает быстро и выводит результат. Это успех. Мало того, что мы решили задачку, только что был создан самый настоящий искусственный интеллект. Программа получает входные данные и желаемый результат, а затем сама ищет, как его достигнуть. Да, это однозначно успех.

Зачем и где применяют логическое программирование

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

  • Анализ естественного языка: Пример с производной - классический пример разбора выражений. Но если мы заменим арифметические операторы, переменные и числа на слова, добавим правила, скажем, английского языка, то сможем получить программу, разбирающую текст на структурные элементы. Занимательно, что одновременно мы получим и программу, способную генерировать текст. Но если логическое программирование можно удобно и эффективно использовать для анализа и разбора текста, то в задачах генерации качественного текста скорее придется обращаться к нейросетям. Тут важно отметить, что рассуждая об анализе и генерации предложений нельзя не упомянуть сложность решения подобных задач. Человек при составлении и восприятии текста ориентируется не только на набор слов и их значений, но и на свою картину мира. К примеру, если в базе лежит факт "Миша починил Маше компьютер", то на вопрос "Разбирается ли Миша в компьютерах?" программа не сможет ответить, не смотря даже на то, что решение вроде как "на поверхности". Именно из-за низкой скорости и особенностей использования на чисто логических языках не занимаются тем, что мы ждем увидеть, загуглив "нейросети" (поиск котиков на картинке, например, не для Пролога). Но вот задачи синтаксического разбора, текстовой аналитики и т. п. на логических языках решать очень даже комфортно.

  • Поиск решений: Задача с Петей и Васей, а также задача с шарами - примеры поиска решений. Представим, что у нас есть набор знаний о некоторой системе и нам нужно понять, можно ли тем или иным путем её взломать (обойти защиту). Это можно достаточно лаконичным образом описать на логических языках и запустить процесс поиска решений. Помимо переборных задач, хорошо будут решаться те, где требуются логические рассуждения (анализ кода или, опять же, естественного текста).

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

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

Стоит ли планировать его изучение на 2021-й

Тут оставлю своё субъективное мнение, разделённое на две части:

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

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

И здесь остаётся лишь пожелать продуктивного 2021-го года!

Подробнее..

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

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

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

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

Проблема логических языков программирования

09.01.2021 22:17:27 | Автор: admin
Некоторое время назад я писал про Интернациональное программирование на естественных языках, в которой попытался представить достойную цель для абстрактного язык программирования, попробовав примерить на него роль связующего звена между миром программистов с компьютерами и не программистов.

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

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

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

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

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

Эта проблема называется Комбинаторный взрыв экспоненциальная зависимость времени работы алгоритма от количества входных данных. И есть как минимум два решения этой проблемы.



Подходы к написания программ


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

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

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

Именно к декларативному стилю относится язык Пролог, да и все остальные логические языки программирования. К декларативному стилю написания программ следует относить и язык структурированных запросов (SQL).

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

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

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

Именно в этом случае и начинается экспоненциальный рост времени выполнения алгоритма. И начиная с определенного порога, время ожидания ответа становится неприемлемым для реального использования. Это и означает Комбинаторный взрыв, резкий (взрывной) рост времени выполнения алгоритма при увеличении размера входных данных.

Проблема поиска решений


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

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

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

Масштабирование производительности


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

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

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

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

Поиск обобщенного решения


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

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

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

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

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

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

Область не решаемых задач


Как вы считает, а реально ли создать язык логического программирования, который бы сам умел автоматизировать поиск решений для задач подобных классов? Или хотя бы имел в своем арсенале встроенные механизмы для автоматизации подобной деятельности?
Подробнее..

Проектируем мультипарадигменный язык программирования. Часть 6 Заимствования из SQL

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

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

В области работы с данными неоспоримым лидером является язык 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 Особенности логического программирования
Подробнее..

AI на минималках 2 Генератор стихов на Prolog

30.01.2021 00:09:39 | Автор: admin

AI на минималках 2: Генератор стихов на Prolog


Мемная картинка


На картинке четверостишье, сгенерированное моей программой.


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


Кто хочет научится писать стихи и познакомиться с Prolog, прошу под кат.


Как научиться писать стихи за 10 минут


Проще всего учиться на примерах великих поэтов. Возьмём классическое стихотворение Тютчева с расставленными ударениями:


Люблю грозу в начале мая, 9
Когда весенний, первый гром, 8
Как бы резвяся и играя, 9
Грохочет в небе голубом. 8


Гремят раскаты молодые, 9
Вот дождик брызнул, пыль летит, 8
Повисли перлы дождевые, 9
И солнце нити золотит. 8


С горы бежит поток проворный, 9
В лесу не молкнет птичий гам, 8
И гам лесной, и шум нагорный 9
Всё вторит весело громам. 8


Ты скажешь: ветреная Геба, 9
Кормя Зевесова орла, 8
Громокипящий кубок с неба, 9
Смеясь, на землю пролила 8


Сразу видно, что стих состоит из нескольких четверостиший, в каждом из которых рифмуются строки одинаковой четности. Заметим, что ударные и безударные слоги чередуются в определённом порядке: _'_'_'_'_ (нижнее подчёркивание означает безударный, а кавычка ударный слог). Такой ритмический рисунок называется размером стиха. Размер состоит из стоп, в каждой стопе ровно один ударный слог. У Тютчева размер двухсложный, с первым безударным, вторым ударным слогом. Такой размер называется ямбом. Есть и другие размеры, например хорей с ударением на первом слоге. Повторение одного размера в четверостишье задаёт стиху ритм, без которого даже с рифмой четверостишье будет звучать как проза.


Системы рифмовки тоже могут быть разные. У Тютчева рифмовка перекрёстная, ещё бывают кольцевая (рифмуются первая с последней и вторая с третьей строки) и смежная (первая со второй, третья с четвёртой).


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


Дело было вечером,
Делать было нечего.


Получается примерно следующий алгоритм написания стихов:


  1. Выберите о чём будет стих. Часто через стихи поэты передают чувства.
  2. Напишите первый черновой вариант, пока без рифмы и ритма.
  3. Подгоните каждую строчку под определённый размер. Важно соблюдать ритмический рисунок.
  4. Зарифмуйте строчки по определённой системе.
  5. Отшлифуйте получившийся текст.
  6. Стих готов!

С практикой вам станет проще рифмовать слова и соблюдать ритм:


Шёл поэт по улице, 7
Кутался в пальто. 5
Всё пройдёт, забудется, 7
Время решето. 5


Обратите внимание, ритмический рисунок совпадает у рифмующихся строчек. У второй и четвёртой хорей получается как бы "рваным", но ритм от этого не страдает.


Введение в Prolog


Теперь сформулируем правила, которым должны удовлетворять четыре строки в четверостишье:


  1. Строчки грамматически корректны, т.е. не нарушают правила русского языка.
  2. Строки рифмуются по определённой системе, возьмём перекрёстную.
  3. У рифмующихся строк совпадает ритмический рисунок.

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


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


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


Prolog можно рассматривать как некую СУБД или экспертную систему, в которой есть знания, и из этих знаний можно делать логические выводы с помощью правил. Знания выражают в виде фактов (предикатов) о внешнем мире. Например, вот так можно записать факт того, что Сократ смертен:


человек(сократ).смертен(Х) :- человек(Х).

Слова в Prolog бывают либо атомами (сократ), либо предикатами (человек), либо переменными (Х). Атомы это некоторые объекты, предикаты это свойства объектов или отношения между ними. Переменные должны начинаться с заглавной буквы, атомы и предикаты с прописной. Предложения должны оканчиваться точкой. В Prolog нет ограничений на латиницу, поэтому слова можно писать и на русском. Первая строчка выражает факт того, что Сократ человек. Вторая моделирует условие "каждый человек смертен". Части импликации разделяются знаком :- и меняются местами.


Теперь если открыть любой интерпретатор Prolog (на маке есть SWI-Prolog), то появится консоль со знаком ?-. Это экспертный режим, где можно задавать вопросы СУБД и получать ответы. Сохранив скрипт в файле socrates.pl и загрузив его командой [socrates]., мы сможем спросить является ли Сократ
смертным:


?- смертен(сократ).true.

Система логически вывела нам факт смертности Сократа. Но это ещё далеко не всё, попробуйте вместо Сократа подставить переменную:


?- смертен(Неизвестно).Неизвестно = сократ.

Prolog сам подобрал единственно возможное значение переменной "Неизвестно". Пролог следует т.н. гипотезе закрытого мира (closed-world assumption) всё, чего нет в базе считается неверным:


?- смертен(аристотель).false.

Хотя Аристотель был таким же человеком, но в нашей программе это не отражено, поэтому Prolog выводит false.


"Хорошо, и как же на этом программировать?" спросите вы. Здесь Пролог очень схож с функциональными языками, где программы определяются рекурсивно. Рассмотрим как вычислить последовательность Фибоначчи. Определим отношение fib(n, f_n), означающее что $n$-ное число Фибоначчи равно $f_n$:


fib(0, 1).fib(1, 1).fib(N, F) :- N #> 1,             M #= N - 1,             K #= M - 1,             F #= G + P,             fib(M, G),             fib(K, P).

Первые две строки задают известный факт, что первый и второй элемент последовательности равны 1. Затем идёт рекурсивное определение, которое можно прочесть так: "Отношение между двумя числами fib(N, F) верно только в том случае, когда N больше единицы, M равно N - 1, K равно M - 1, а F равно сумме G и P, которые находятся в отношениях fib(M, G) и fib(K, P)". Запятые тут означают логическое "И". Операторы сравнения #> и #= нестандартны для Пролога, они находятся в библиотеке CLPFD, идущей вместе с дистрибутивом SWI-Prolog. Эта библиотека "чинит" недостатки стандартных числовых отношений вроде =, > и т.д. Чтобы использовать библиотеку, нужно сразу после старта REPL консоли набрать ?- use_module(library(clpfd)).


Теперь откроем swipl, загрузим скрипт и введём ?- fib(10, X). Пролог выведет X = 89. То есть он подобрал первое значение переменной X, которое удовлетворяет этому отношению. Если нажать клавишу ';', то выйдет false, так Пролог говорит, что других значений X он найти не может. Теперь классный момент: введём ?- fib(X, 13). Пролог выдаст X = 6. То есть так можно вычислять еще и обратную функцию. Мы получили две программы по цене одной!


Ещё интересно как работают списки в Prolog. У списка есть голова (первый элемент) и хвост (остальные). Синтаксис такой: Список = [Голова | Хвост]. Например, если Список = [1, 2, 3, 4], то Голова = 1, а Хвост = [2, 3, 4]. Это разделение очень полезно при рекурсивном определении отношений. Вот так можно закодить отношение freq(E, L, F) которое выполняется когда элемент E входит в список L ровно F раз:


freq(_, [], 0).freq(Element, [Head|Tail], F) :- Head #= Element,                     F #= P + 1,                     freq(Element, Tail, P),                     !.freq(Element, [Head|Tail], F) :- Head #\= Element,                     freq(Element, Tail, F),                     !.

Сначала как обычно выполняется базовый случай: в пустом списке частота любого элемента равна нулю. Роль "любого элемента" здесь играет переменная "_". В Прологе так обозначаются "свободные" переменные, встречающиеся только один раз. Затем рассматривается два случая когда голова списка равна подсчитываемому элементу и когда нет. В первом случае инкрементируется счётчик вхождений элемента в массив. Затем Пролог продолжает рекурсивно пробовать удовлетворять freq. Если запросить ?- freq([1, 2, 2, 3], 2, X), то интерпретатор построит примерно такую цепочку равенств для нахождения правильного значения Х:


X #= X1, Tail = [2, 2, 3]X1 #= X2 + 1, Tail = [2, 3]X3 #= X4 + 1, Tail = [3]X5 #= X6, Tail = []Последний вызов: freq(_, [], 0), X6 #= 0.

Развёртывая равенства получим X #= 2.


Восклицательный знак здесь играет важную роль. Это т.н. "cut operator", который обрезает дерево поиска интерпретатору. Он говорит "если интерпретатор дошел до меня, то не нужно пробовать удовлетворить другой вариант freq". Из-за этого у Х будет только одно возможное значение.


Комбинаторный поиск в Prolog


Prolog идеально подходит для комбинаторного перебора. Нужно только закодировать правила, которым подчиняются перебираемые объекты, и запустить интерпретатор. Рассмотрим классическую задачу генерации всех магических квадратов 3 на 3. Магическим называется квадрат, в котором все числа положительны и различны, а суммы в каждом столбце, строке и диагонали совпадают. Пример:


A|B|C   2|7|6-|-|-   -|-|-D|E|F = 9|5|1-|-|-   -|-|-G|H|I   4|3|8

Каким правилам подчиняются числа в квадрате?


  1. В квадрате 3х3 ровно 9 чисел.
  2. Каждое число целое и строго положительное.
  3. Все числа различны.
  4. Есть 7 равенств, выполняющие условие "магичности" квадрата.

С помощью библиотеки CLPFD можно очень легко закодировать эти правила в Прологе:


magic([A, B, C, D, E, F, G, H, I]) :- Vars = [A, B, C, D, E, F, G, H, I],                                    Vars ins 1..100,                                    all_different(Vars),                                    A + D + G #= B + E + H,                                    B + E + H #= C + F + I,                                    C + F + I #= A + B + C,                                    A + B + C #= D + E + F,                                    D + E + F #= G + H + I,                                    G + H + I #= A + E + I,                                    A + E + I #= C + E + G,                                    label(Vars).

Отношение magic определяет 9 различных переменных из интервала [1, 100] с семью равенств. Функция label позволяет назначить конкретные значения этим переменным. Если запустить ?- magic(S). то интерпретатор Пролога будет последовательно выводить все возможные магические квадраты 3х3.


Вернёмся к нашей оригинальной задаче: генерации стихотворений. Стихотворение состоит из четверостиший. Четверостишие определяется следующими правилами:


  1. Строчки грамматически корректны, т.е. не нарушают правила русского языка.
  2. Строки рифмуются по определённой системе, возьмём перекрёстную.
  3. У рифмующихся строк совпадает ритмический рисунок.

Всё, что нужно сделать это корректно закодировать это правила на Прологе. Самое сложное здесь это первое правило. Грамматическая корректность это довольно непростое требование, грамматика русского языка очень богата, у нас есть спряжения, морфология, и проч. Поэтому я решил взять конкретные шаблоны, которые наверняка будут грамматически корректны. Все слова в настоящем времени и мужского рода:


Нечётные строчки: Прил Сущ Нар ГлагПример: Жёлтый жираф тихо спит, Маленький заяц быстро бежитЧётные строчки: Нар Глаг СущПример: Громко поёт соловей, Быстро играет музыкант

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


Как это кодировать? Очень просто вначале составляется словарь наподобие такого:


наречие(ушло, 1).наречие(хило, 1).наречие(хорошо, 3).прилагательное(кроткий, 1).прилагательное(дохлый, 1).прилагательное(фирменный, 1).глагол(ценит, 1).глагол(читает, 2).глагол(касается, 2).существительное(бык, 1).существительное(слон, 1).существительное(укротитель, 3).

Второй аргумент указывает на порядковый номер ударного слога. В слове "кроткий", ударение падает на первый слог, а в слове "укротитель" на третий. Эта информация пригодится когда мы будет строить ритмический рисунок строчки.


Затем определяется предикат предложение:


предложение([А, Б, В, Г]) :- прилагательное(А, _),                           существительное(Б, _),                           наречие(В, _),                           глагол(Г, _).

И похожий предикат для чётных строчек. Тогда Пролог будет генерировать корректные предложения запросом ?- предложение(П).


Теперь ко второму правилу рифмовки. Как определить что два слова рифмуются? Рифмуются слова, у которых ударение падает на тот же слог и у которых окончания похожи (зрелый спелый, бедный каретный, новый здоровый). Есть такое понятие парные буквы, наверняка вы ещё их в школе проходили. Вот несколько таких пар:


(а, я).(б, п).(в, ф).(и, ы).(с, ц).

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


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

Чтобы закодировать такое правило надо сначала определить все омофонные пары:


омофон_пара(а, я).омофон_пара(б, п).омофон_пара(в, ф).омофон_пара(г, к).омофон_пара(д, т).омофон_пара(ж, ш).омофон_пара(з, с).омофон_пара(ч, щ).омофон_пара(и, ы).омофон_пара(е, э).омофон_пара(у, ю).омофон_пара(я, а).омофон_пара(п, б).омофон_пара(ф, в).омофон_пара(к, г).омофон_пара(т, д).омофон_пара(ш, ж).омофон_пара(с, з).омофон_пара(щ, ч).омофон_пара(ы, и).омофон_пара(э, е).омофон_пара(ю, у).омофон_пара(н, м).омофон_пара(м, н).омофон_пара(ц, с).омофон_пара(с, ц).

Затем определить предикат "похожие_по_звучанию(Слово1, Слово2)", который выполняется когда слова 1 и 2 отличаются не более чем на омофонные пары:


похожие_по_звучанию([], []).похожие_по_звучанию([Б1|К1], [Б2|К2]) :- Б1 = Б2, похожие_по_звучанию(К1, К2).похожие_по_звучанию([Б1|К1], [Б2|К2]) :- омофон_пара(Б1, Б2), похожие_по_звучанию(К1, К2).

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


Зная всё это, написать предикат "рифмуется(Слово1, Слово2)" не составляет труда:


рифмуется(С1, С2) :- ударение(С1, У1),                     ударение(С2, У2),                     индекс_гласной(С1, У1, И1),                     индекс_гласной(С2, У2, И2),                     atom_chars(С1, Буквы1),                     atom_chars(С2, Буквы2),                     length(Буквы1, Д1),                     length(Буквы2, Д2),                     Д1 - И1 #= Д2 - И2, % ударение на тот же слог                     slice(Буквы1, И1, Д1, Окончание1),                     slice(Буквы2, И2, Д2, Окончание2),                     похожие_по_звучанию(Окончание1, Окончание2),                     С1 \= С2.

Предикат atom_chars позволяет разбить слово на составляющие его буквы, а slice вычленяет ударное окончание из обеих слов. Обратите внимание на последнее требование: C1 \= C2, оно нужно чтобы одно и то же слово не генерировалось при запросе ?- рифмуется(Слово1, Слово2).


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


Например, у строки "Люблю грозу в начале мая" шаблон будет "бубубубуб", т.е. чистый ямб. Хорей будет выглядеть наоборот "убубубуб".


По каждой строчке в стихе можно строить такие шаблоны. Совпадением ритмического рисунка будет совпадение шаблонов. Как строить такие шаблоны? Нужно каждое слово в строке разбить на слоги, ударный слог записать как "у", остальные как "б" и повторить для всех слов.


Я не буду здесь приводить полный код этой процедуры, при желании вы можете ознакомиться с кодом всего проекта в открытом репозитории


Приведу только конечный вид предиката "стих", по которому можно генерировать четверостишия:


стих([П1, Щ1, Н1, Г1], [Н2, Г2, Щ2], [П3, Щ3, Н3, Г3], [Н4, Г4, Щ4], Р1, Р2, Р3, Р4) :-    прилагательное(П1, _),    существительное(Щ1, _),    наречие(Н1, _),    глагол(Г1, _),    ритм_предложения([П1, Щ1, Н1, Г1], Р1),    наречие(Н2, _),    Н1 \= Н2,    глагол(Г2, _),    Г1 \= Г2,    существительное(Щ2, _),    Щ1 \= Щ2,    ритм_предложения([Н2, Г2, Щ2], Р2),    прилагательное(П3, _),    П1 \= П3,    существительное(Щ3, _),    Щ1 \= Щ3,    Щ2 \= Щ3,    наречие(Н3, _),    Н2 \= Н3,    Н1 \= Н3,    глагол(Г3, _),    Г2 \= Г3,    Г1 \= Г3,    ритм_предложения([П3, Щ3, Н3, Г3], Р3),    рифмуется(Г1, Г3),    наречие(Н4, _),    Н1 \= Н4,    Н3 \= Н4,    Н2 \= Н4,    глагол(Г4, _),    Г1 \= Г4,    Г3 \= Г4,    Г2 \= Г4,    существительное(Щ4, _),    Щ1 \= Щ4,    Щ3 \= Щ4,    Щ2 \= Щ4,    ритм_предложения([Н4, Г4, Щ4], Р4),    рифмуется(Щ2, Щ4).классика(Стих) :- стих(А, Б, В, Г, хорей, рваный_хорей, хорей, рваный_хорей), Стих = [А, Б, В, Г].

Здесь включены все три правила стихосложения (грамматическая корректность, рифма, ритм) и ещё добавлены условия на различность X \= Y чтобы слова не повторялись.


Наконец, можно проверить как это всё работает если набрать ?- классика(Стих).


Что дальше?


Понятно, что всё описанное это только proof of concept, можно и дальше развивать эту тему. Например, добавить ещё слов в словарь, расширить грамматику, чтобы она включала разные времена и роды слов. Можно также определить новые шаблоны стихотворений, отличных от классики, да и вообще поле для экспериментов тут очень богатое.


Надеюсь вам понравилась статья и вы узнали что-то новое. Ссылка на репозиторий проекта: prolog-poetry. Там же есть полная инструкция по запуску.

Подробнее..

Logical FizzBuzz

14.06.2020 04:13:33 | Автор: admin

Привет, абстрагирующимся. Прочитав эту статью, задумался, а как представлять эту задачу языком Пролог? Попробую выразить свое, затянувшееся, субботнее отношение к этой пятничной задаче, с помощью доступных декларативных формулировок.
В реализации на Скала, я увидел операцию "(value % n)" и пояснение, что значения value,n -это: type class "Integral" требующий от типа "T" возможности вычислять остаток от деления и иметь значение "zero".
Это меня подтолкнуло, на такую мысль, а может абстрагируемся еще больше, и отбросим арифметические операции этого "интэграл", может рассмотрим глубже идею натуральных чисел, сейчас попробую продемонстрировать и получить реализацию...


Это представляли еще в Древней Греции, натуральное число N это 0 или следующее за ним натуральное число, результат функции p(N).
Записывать можно так N0= 0,
потом N1=p(0), и далее N2=p(p(0)) вот такой ряд натуральных чисел, от 0 и далее следующее и следующее значение:


Изображаю это на Прологе:


natural(0).natural(N+1):-natural(N).

если выполнить такую цель, получим бесконечность ответов:


?-natural(X).X=0;X=0+1;X=0+1+1: .... ну и тд.

От этого, пользы большой не извлечь, а как часть объяснения годится, значения переменной X являются структурами, в Прологе есть инфиксные операции, которые могут соединить значения между собой, вместо громоздкой записи p(p(p..(p(0)..))), просто соединим символы знаком "+": 0+1+1+1+1 это просто такое символьное выражение, почти строка, а можно бы записать и как: zero plus one plus one.
Вот так, можно объявлять свой знак операции:


:-op(600, yfx, plus). %op(+Precedence, +Type, :Name) natural(zero).natural(N plus one):-natural(N).

Будут такие представления чисел:


?- natural(X).X = zero ;X = zero plus one ;X = zero plus one plus one ; ...

Далее, полезно будет сформулировать следующую проблему, как выражать сложение или вычитание над двумя такими натуральными числами?,
вот оно:


add(0, X, X).add(X+1, Y, Z+1):- add(X, Y, Z).

Теперь можно решить вот такие цели для сложения:


?- add(0+1,  0+1+1, X).X=0+1+1+1

И вот такой вопрос, превратится в вычитание натуральных чисел:


?- add(X,  0+1+1+1,  0+1+1+1+1).X=0+1

Можно получать все возможные натуральные слагаемые, составившие определенное значение:


?- add(X, Y, 0+1+1+1+1).X=0, Y=0+1+1+1+1;X=0+1, Y=0+1+1+1;X=0+1+1, Y=0+1+1;.. и тд.

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


В задаче, на вход поступят числа, записанные как целые, арабские, и если не отменять это условие и не просить пользователя передавать на вход, только что показанные структуры, реализую такое правило:


int_natural(0,0).int_natural(X, Y+1):- X0 is X-1,  int_natural(X0, Y).

оно сможет конвертировать целое число в его "натуральное" представление:


?- int_natural(6,X).X=0+1+1+1+1+1+1 

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


mul(0, X, 0).mul(X+1, Y, Z):- mul(X, Y, Z1), add(Z1, Y, Z).

это можно использовать и для обратной операции для деления:


?- mul(0+1+1, 0+1+1, X).X=0+1+1+1+1?- mul(0+1+1, X, 0+1+1+1+1).X=0+1+1

Вот так, сформулирую остаток от деления:


rem(X, X, 0).rem(X, Y, R) :- add(X1,Y,X), rem(X1,Y,R),!.rem(X, _, X):-!.

тут и отсечение (!) заранее установленно, что бы не шокировать читателей функцией обратной к "остатку от деления", это, наверное, операция "следующее число, не кратное на одну величину остатка", типа так:


?- rem(X, 0+1+1+1, 0+1).X = 0+1+1+1+1 ;X = 0+1+1+1+1+1+1+1 ;X = ... + ... + 1+1+1+1+1+1+1+1+1 ... и тд.

"Прямое" использование этого правила вот:


?- rem(0+1+1+1+1, 0+1+1, X).X = 0.?- rem(0+1+1+1+1, 0+1+1+1, X).X = 0+1. 

FizzBuzz


Отлично, всю задачу сформулировать теперь можно таким видом:


fizz_buzz(N, fizzbuzz) :- rem(N, 0+1+1+1, 0), rem(N, 0+1+1+1+1+1, 0),!.fizz_buzz(N, fizz) :- rem(N, 0+1+1+1, 0),!.fizz_buzz(N, buzz) :- rem(N, 0+1+1+1+1+1, 0),!.fizz_buzz(N, N).

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


?- int_natural(5, N),!, fizz_buzz(N, X).N = 0+1+1+1+1+1,X = buzz.?- int_natural(15, N),!, fizz_buzz(N, X).N = ... + ... + 1+1+1+1+1+1+1+1+1,X = fizzbuzz.

или по условию, на выходе получаем тоже число:


?- int_natural(4, N),!, fizz_buzz(N, X).N = X, X = 0+1+1+1+1.

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


fizz_buzz2(IN, R) :-once(int_natural(IN,N)),                    once(rem(N, 0+1+1+1, 0) -> F=fizz; F=''),                    once(rem(N, 0+1+1+1+1+1, 0) -> B=buzz; (F\='')->B=''),                    atom_concat(F,B,R),!.fizz_buzz2(N, N).

В этом варианте сразу переводим входное целое число и компонуем выходное значение из частей, если это потребовалось. Встроенное правило once(Goal), выполняет цель только один раз, для исключения возвратов и зацикливаний.
Вот такие примеры:


?- fizz_buzz2(2, X).X = 2.?- fizz_buzz2(15, X).X = fizzbuzz.

Обработку ряда чисел, можно получить отобразив собрав все решения, указанной цели в один список, для этого используем встроенный мета-предикат findall():


?- findall(X, (between(1, 10, N), fizz_buzz2(N, X)), Result).Result = [1, 2, fizz, 4, buzz, fizz, 7, 8, fizz|...].

Вот тут, можно попробовать.


Для заключения


Пролог, это любопытная возможность переносить в "символы" условия задач, это система опирающаяся на логику предикатов и встроенные процедуры автоматического доказательства теорем. Формулировка проблемы, при удачном выражении, позволяет находить решение для самой задачи, а также сразу иметь решение "обратной" к ней проблеме. А может вот таким вопросом, увидим, какие числа, приводят к fizz: ?- fizz_buzz(N, fizz).

Подробнее..

Навеянное Prolog-ом коммерческое решение пробыло больше 10 лет в эксплуатации

03.11.2020 14:09:04 | Автор: admin
Для большинства программистов которые хотя бы слышали про Prolog это только странный артефакт из времён когда компьютеры были размером с динозавров. Некоторые сдали и забыли в институте. И лишь узкие как листочек A4 специалисты сталкивались с чем-то подобным в современном мире. Так уж получилось, что далёком 2003-ем году я использовал некоторые решения подчерпнутые из Prolog-а, в коммерческих играх на Flash и больше десятилетия они радовали французов. Причём применил я это полудекларативное решение не потому что прочитал книжку Братко и впечатлился, а потому что это было реально нужно нашему проекту. Я до сих пор регулярно порываюсь воспроизвести то решение на современном уровне, потому что оно очень много где было бы полезным в современном игрострое, но, к сожалению, каждый раз находятся дела поважнее В общем об этом всём и расскажу.


Скриншот той самой флэшовой игры до сих пор приветствует вас на сайте toox.com/jeux/jeux-de-cartes/coinche

Постановка задачи и её актуальность


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

В принципе, так как игра идёт в закрытую, люди готовы простить роботам мелкие просчёты и альтернативную одарённость. В основном потому что карт робота не видят. Под игрока с симака, под вистуза с туза и тому подобные простые правила, которые я вытряхнул из нашего французского заказчика позволили сделать минимально приемлемого кидателя карт. Он был нафигчен за неделю прямо на if-ах. С другой стороны игра идёт двое на двое, очки считаются для пары, и вполне естественно игрок не хочет, чтобы его тупой напарник заходил со второго короля, то есть имея на руках короля и ещё какую-то мелкую карту делал ход в эту масть, вместо того чтобы дать противнику сыграть туза, пропустив его мелкой картой и забрать следующий ход в эту масть своим королём. (На самом деле в этих играх вторая по старшинству карта 10, но тут и дальше я буду говорить в понятных русским терминах). Но если туз по какой-то причине вышел из игры, а у вас Дама и ещё что-то мелкое, то это же почти как второй король. Особенно если предварительно прорядить козырей. А ещё вы, например, играете не в Белот, где используется 32 карты, а в Таро, в которой игра идёт колодой в 78 карт, (той самой, по которой некоторые гадают). И там в некоторых случаях забрать взятку может даже не третья дама, а четвёртый валет. В общем всё это порождает такое количество граничных случаев, что тупой болванчик на if-ах становится уже как-то совсем неприемлемо сложным. И вот на этом месте я сказал: Ба! Да я же начитался Братко и впечатлился! Дальше я на несколько дней сбежал из офиса, сел с ноутбуком в кафешке и спустя несколько дней породил нечто.

Основные идеи


На чём, декларативно говоря основан Пролог? На фактах, например:

мама('Галя', 'Ира').мама('Ира', 'Алиса').

и на термах, или правилах, например если А мама Б, то А девочка:

девочка(А) :- мама(А, Б).

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

предок(A, B) :- мама(A, B).предок(А, В) :- предок(А, С), предок(С, В).

А потом ты такой Спрашиваешь:

?- предок (X, 'Алиса')

А страшно логичный Пролог тебе и отвечает:

X = 'Ира'X = 'Галя'

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

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

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

Вот хотелось бы как-то похоже формулировать правила игры, но конечно не буквально. Имея определённый опыт отладки программ на Прологе я совершенно не горел желанием сталкиваться этой отладкой и этими накладными расходами у себя на проде.

Общие хотелки


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

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

Получившийся в итоге синтаксис бибилотеки Logrus


Щаз будет очень много синтаксиса.

1) В рантайме дерево решения хранится в виде некоторых классов, но первое, что я к нему приделал, как только оно заработало Import и Export в JSON. Оказалось, что это удобно ещё и потому, что если у вас не сильно поменялась страктура данных обновление правил можно накатить из файлом без перекомпиляции. Запись в виде JSON оказалось на столько удобной, что на одном из следующих проектов программисты когда торопились иногда вместо того чтобы писать нормальную команду делали просто state.AplayJSON("..."); и в нём нужное действие вставляли в виде JSON строки. На производительности это, конечно, сказывалось не очень хорошо, но если не регулярно и только в ответ на нажатие пользователя, то не страшно Всё дальше я буду иллюстрировать сразу JSON-ами. JSON-ы воспроизвожу примерно и по памяти, потому что шибко давно дело было. Строго говоря, JSON не гарантирует порядок следования нод в объекте, но большинство библиотек все-же его соблюдают, и здесь и далее порядок нод активно используется.

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

[{"condition":{}, "action":{}}, {"condition":{}, "action":{}}]

3) В каждом правиле содержится условие это шаблон дерева, возможно содержащий переменные. Система поищет совпадает ли дерево состояния с шаблоном при каких-нибудь значениях переменных. И если найдёт такую конкретизацию вызовет действие. Например:

{"condition":{    "player":{        "$X":{"gold" : "<20", "name":"$NAME"}    }},    "action":{}}

Такая конструкция будет означать, что для того чтобы было вызвано действие в дереве должна иметься на верхнем уровне нода player в которой одна или несколько дочерних нод, в каждой из которых есть поля gold со значением меньше 20 и name. Если такое условие будет выполнено, то будет вызвано действие, причём в качестве входных данных ему будут переданы в переменной X ключ ноды, а в переменной NAME имя игрока. Если подходящих нод и соотвественно возможных конкретизаций окажется несколько, то действие вызвано будет несколько раз с каждой из найденных конкретизаций на входе.

4) Первоначально там всё было чуть-чуть менее гибко, но потом Valyard, которого многие знают по многочисленным выступлениям на конференциях про Unity, прикрутил нам синтаксический анализатор, разбирающий арифметические выражения в шустрое дерево решений и гибкость окончательно расцвела буйным цветом.

5) C $ начинаются имена переменных. Они могут встречаться как в виде ключа, такого как $X и тогда будет выбрано несколько конкретизаций, в виде значения листа, такого как $NAME, могут вставляться в арифметические выражения: например так: {gold: "< $X * 10"}И тогда использоваться для проверки условий, проверку пройдёт только те игроки, у которых золота больше чем их порядковый номер умноженный на 10, и наконец Они могут непосредственно вычисляться в каком-нибудь выражении, например так:{gold: "$X = 3 + $this"} где $this это значение текущей точки в которой вызвано вычисление. Прохождение этого узла конкретезирует значение переменной $X как 3+количество золота у игрока. Из возможностей, которые приходили в голову не реализована была только одна переменная не может впервые встречаться в правой части арифметического выражения, это будет ошибка, к моменту использования в качестве аргумента она уже должна быть конкретизирована одним из нескольких других способов.

6) Переменная в выражении может встречаться сколько угодно раз, при этом первое упоминание её конкретизирует, а следующие будут проверкой на равенство. Например такая конструкция возьмёт первого игрока, проверит его на наличие денег, потом поищет другого игрока для которого первый бы был целью. Если не найдет, откатится к точке конкретизиции X выберет следующего игрока, проверит на деньги и так далее пока не переберёт все допустимые варианты X и Y. Поменяв строки местами программист изменит порядок проверок, но не конечный результат:

{ "player":{    "$X":{"gold":">20"},    "$Y":{"target":"$X"}}}

7) Действие также представляет из себя шаблон дерева, могущий содержать переменные и арифметические выражения, и дерево состояния игры будет изменено так чтобы ему соответствовать. Например этот шаблон, назначит игроку X противника в виде игрока Y, но если бы по какой-то причине игрока Y не существовало он был бы создан. А игрок superfluous вообще будет удалён. На момент создания игры со скриншота признаком удаления было значение null, но потом я заменил его на зарезервированное слово, на случай если кому-то потребуется по ключу вставить пустое значение. В целом принцип, думаю, понятен, и смысл совершаемых с игрой действий в основном тоже.

{    "condition":{    "player":{        "$X":{"gold":">20"},        "$Y":{"target":"$X"}}},    "action":{        "$X":{"target":"$Y"},        "superfluous":"@remove"}}

8) Действием также может являться не шаблон дерева, а массив в свою очередь правил. Каждое из них будет проверяться не с нуля, а именно с той первоначальной конкретизацией, с которой было вызвано действие. То-есть там может быть целая группа правил, и все они будут использовать переменную X.

{    "condition":{        "player":{            "$X":{}, "$Y":{"target":"$X"}}},    "action":[        {"condition":{}, "action":{}},        {"condition":{}, "action":{}}]}

9) Дочернее правило может применяться не от корня дерева состояния, а от какой-то точки, достигнутой в ходе применения действия. В этом случае все условия и все действия будут использовать эту точку в качестве корня. Выглядит это примерно так:

{    "condition":{        "player":{            "$X":{}, "$Y":{"target":"$X"}}},    "action":{        "$X":{"@rules":[            {"condition":{}, "action":{}},            {"condition":{}, "action":{}}]}}

10) Повторение правила могло быть задано в качестве ещё одной ноды, этим достигалась, если надо, рекурсия ограниченной глубины. Но на практике такое решение обычно не было необходимым. Его можно использовать так же чтобы повторять пачку правил сколько нужно, поместив его в action:

{    "condition":{},    "action":{},    "repeat":5}

11) Дерево правил можно было грузить из нескольких файлов JSON, их древовидная структура просто накладывалась одна на другую. Это было удобно чтобы разбить правила на отдельные осмысленные блоки. Наверное полезен был бы и какой-нибудь Include, сейчас уже не помню как у нас оно было устроено.

12) Логирование! Любое правило могло иметь ноду "@log":true, что приводило к тому, что это правило начинало очень подробно срать в лог описанием процесса решения. Какие конкретизации пробуем, какие ветки рассуждений пресекаются и почему. Логирование было иерархическое, то есть вложенное правило могло быть "@log":false и всё что происходит в нём и ниже в лог не попадёт. В идеале я бы хотел чтобы эту ноду можно было оставляь вообще у любом месте дерева условий, чтобы смотреть только на происходящее в одном уровне шаблона, но такое расширение я так, кажется, и не доделал. Возможно отладка и без него проходила нормально, поэтому его и откладывали на когда-нибудь.

13) Типизация. Игрушка была на столько старой, что некоторые из нынешних программистов тогда ещё не родились. Написана она была на языке ActionScript2, в котором была динамическая типизация и наследование через прототипы доступное прямо в рантайме. Из современных языков которые на слуху, так устроен только Python. Однако к данной идее прикрутить типизацию не представляет особой сложности. Я бы сделал это используя ключевой символ ':' например так: "$X:int" однако тут может возникнуть хитрость если первое вхождение переменной не имело никого указанного типа. А кроме того может возникнуть путаница с тернарным оператором.

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

14) Одна и та же нода могла проверяться не одним, а несколькими условиями. Например такое условие сначала проверяло, что денег больше 20, а потом конкретизировало переменную в которой это количество денег представлено. Служебный символ '@' если он расположен не в начале строки означал повторных вход в ноду, идущий дальше идентификатор повторного входа никак не пригодился. Возможно служебный символ использовался и какой-то другой, но ничего, по-моему, не мешает тому чтобы использовать этот:

{    "player":{        "$X":{"gold":"<20", "gold@cnt":"$COUNT"}    }}

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

{    "_":"$SUM=$A+$B",    "_@check":"@SUM <20"}

16) Раз есть проход проверки вверх по дереву, потребовался и спуск вниз, делающийся через ключевое слово "@parent". Читаемости это, конечно, не прибавляло, но обойтись без этого никак не получалось. Тут, конечно, прямо напрашивается какой-то аналог функции path который бы переадресовывал на указанное место в дереве, но я не помню, успел я его реализовать его в итоге или нет:

{    "condition":{        "player":{            "$X":{}, "$Y":{"target":"$X"}}},    "action":{        "$X":{"rules":[            {                "condition":{                    "@parent":{"@parent":{"":""}}            }        ]},    }}

17) У действия появилась возможность непосредственно подёргать какой-нибудь метод класса. Это такой пинок под дых читаемости, и я бы предпочёл какой-нибудь аналог #include, но уж как есть, из песни слов не выкинешь. Интересно, смогу ли я без этого обойтись на практике если реанимирую библиотеку сейчас на C#?

18) У правила появилась дополнительная настройка повторять действие не для всех найденных конкретизаций, а только для первой. Не помню сейчас как называлась, но зачем-то этот костыль был полезен для каких-то правил.

Результаты использования


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

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

Конечно по скорости выполнения это всё заметно уступало мешанине if-ов, особенно в реализации на AS2 с его прототипами и динамическими объектами, но не на столько, чтобы это нельзя было выкатить в прод.

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

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

Когда-нибудь я соберу волю в горсть и сделаю современный ремейк Logrus-а под C# и Unity3d, например для гексагональной стратегички, о которой мечтаю. Но это будет не сегодня, сегодня я пойду спать. Долг по распространению идей, которые стоят того чтобы их распространять успешно выполнен.

В заключение пара анекдотов


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

А вот тоже другой случай. Звонит как то наш Себастьян Перейра к менеджеру и говорит, что они тут чудом смогли прорваться в телевизор и скоро нас с нашим сайтом покажут по телевизору. Через 8 часов примерно. Так что вы там сделайте чтобы он работал понадёжнее На часах 2 января Не важно какое время И вот Вовчик берёт такси, начинает по общагам и квартирам собирать программистов совершенно в состоянии размазни, и свозить их в офис. Я в тот день впервые вы жизни увидел нашего сисадмина. До этого момента он всё делал исключительно удалённо. И вот мы каждый подкрутили кто что мог. Я, в частности выломал всю эту систему поставив на её место назад пачку if-ов и вот сидим мы, смотрим на график посещаемости и вдруг видим как он начинает переть вверх. Где-то на отметке x15 сервак грохнулся. Но админ сказал, что всё хорошо, упал аккуратно, сейчас сам поднимется. За тот день сервак падал ещё трижды.
Подробнее..

Что за X? Что за ABAP? Древние языки, про которые интересно слушать, но не дай бог на них писать

19.11.2020 18:06:36 | Автор: admin

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

Но почти в каждой компании в этот момент найдется человек со взглядом на сотню ярдов в пустоту, который будет вспоминать, как 10 лет назад в своем НИИ ШМИИ ИПИАН Меловой период его заставляли переписывать гигантскую систему с Лиспа на Си. И у всех в этот момент пробежит холодок по спине потому что никто не застрахован от рефакторинга чего-нибудь древнего и страшного.

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

Здесь мы собрали вместе людей, которые писали на Prolog, Forth, ABAP и X++, и дали им выговориться.


Что это за языки

Вагиф, Prolog

В незапамятные времена с 1985 по 1990 год я пользовался языком Prolog.

Я учился в МИЭМе (ныне часть ВШЭ), и ходил на группу прикладной логики. Там заинтересовался символьными вычислениями, попробовал Lisp, но Prolog особенно привлек меня своей декларативностью описываешь правила предметной области, а дальше все идет как бы само.

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

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

Тогда казалось, что мы решим все задачи.

Лиза, ABAP

Я SAP-разработчик и пишу на ABAP. Это проприетарный язык, по синтаксису тот же COBOL. Он используется собственно в SAP SE и компаниях, занимающихся разработкой и консалтингом для бизнес-приложений и промежуточного ПО SAP. Конкретно я пишу модули SAP ERP, их расширения и все такое.

Фил, X++

У меня был Язык X++. Это внутренний ЯП Microsoft, который они сделали специально для своего ERP-проекта Axapta, потому что нужен был язык, в котором можно было писать SQL-запросы прямо в коде, с компайл-тайм чеками и полной поддержкой синтаксиса и фич базы. Язык, конечно, достаточно отсталый. При этом он работает на .NET, а туллинг ему сделали почти как у C#.

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

Василий, Forth

Я начинал работать в конторе, которая занималась всякой автоматизацией на микроконтроллерах. Местные деды (в самом лучшем значении этого слова люди зарабатывали внедрением своих разработок на заводах по всей стране) начинали кодить на древних МК, еще когда их делал Intel, и происходило все это на ассемблере. Им чем-то не угодил C, и они очень вдохновились идеей Форта. Поэтому я и угодил в разработку на этом языке.


Каково на них писать

Лиза, ABAP: У нас просто древнейшие тулзы. Я начинала работу с платформы SAP NetWeaver, очень не хватало всех этих подсветочек и прочих свистелок из более популярных IDE, вроде той же Intellij IDEA. Пока не привыкла, казалось, что пишешь в блокноте.

Интерфейс тоже древний. Есть новые темы, но они не очень удобные, поэтому я обхожусь без них. В целом, SAP GUI причина боли меня как маковода, но всё же одно из самых удобных мест для разработки под SAP, пусть и умирающее. Модные ребята сейчас переходят на VS Code, адекватные на Eclipse, я до сих пор сижу в чём начинала.

Главное удобство языка нативная поддержка SQL, хотя и было бы странно ее отсутствие.

Фил, X++: Первое что бросилось в глаза невероятно уродский синтаксис и кодстайл. Это было в 2015-ом, а они там на полном серьезе фигачили всякие префиксы в стиле field-db-name. X++ был во многом похож на C#, только огромного количества привычных фич просто не было, а вещи, которые в том же C# автоматизируются на раз-два, здесь приходилось топить в тоннах бойлерплейта.

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

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

А при миграции на другую архитектуру достаточно переписать только базовый минимум. И все ваши любовно наработанные годами библиотеки (словари в реальности Форта) остаются с вами. Можно даже сделать свой процессор на FPGA с личной системой команд и запустить на нем Форт. Некоторые пункты и по современным меркам звучат неплохо.

Вагиф, Prolog: Хорошая иллюстрация программирования на Прологе вычисление производной в символьном виде. Математики говорят, что, в отличие от интегрирования, дифференцировать можно научить даже лошадь. Лошадь может и можно научить, но попробуйте написать программу символьного дифференцирования на Си. На Прологе такая программа занимает столько же строк, сколько есть правил дифференцирования, т.е. укладывается в одну страницу. Это все выглядело многообещающе, и мы другом и коллегой всерьез занялись идеей написания медицинской экспертной системы на Прологе. У нас несколько лет был небольшой кабинет в институте эндокринологии там мы писали базу знаний, собирая эти знания у местных врачей. Врачи толком не понимали, что из этого может получиться, но заражались нашим энтузиазмом и полагались на нас. Так к 1990 году родилась экспертная система Эндокрин, приказавшая долго жить, когда ее создатели уехали работать в другую страну.


Худший опыт, который стал уроком

Василий, Forth: Для обучения Форту нам показали пару примеров и дали в руки книгу Броуди по основам языка. Она запомнилась мне картинкой про swap эта психотравма навсегда со мной:

Потом потребовалось написать приложение мониторинга под Винду, и почему-то так получилось, что надо писать под WinAPI что тогда было нормально, но не на Форте.

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

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

Вагиф, Prolog: О причинах заката Пролога многое написано, они примерно те же, что и причины неудачи японского проекта пятого поколения. Вычислительные ресурсы переоценили, символьные вычисления переоценили.

Вместе с тем язык обладал очень интересным подходом к поиску решений по правилам, пробегаясь по множеству возможных решений вперед и назад (так называемый backtracking). К нему по-прежнему возвращаются, есть нынешние версии думаю, в основном для исследовательских целей. Есть SWI-Prolog, я читал об использовании его для анализа человеческой речи. Есть разработанный в Австралии язык Mercury под .NET, фактически на базе Пролога. Для ранних версий дотнета (под Моно) разрабатывался язык P# Пролог, транслируемый в C#.

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

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

Конечно, язык с очень узкой сферой применения не может тягаться с мультитулами вроде C# или Java, поэтому количество ярых фанатов ABAP стремится к нулю. Но умрет он только со смертью платформы, а платформа слишком много где используется и тесно вплетена в процессы корпораций вроде Johnson & Johnson, Mercedes-Benz и им подобных, переходить на что-то новое очень дорого и пока нецелесообразно.

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

Фил, X++: Я работал с истинными фанатами этой технологии такие, знаете, старички, для которых вся молодежь формошлепы, которые только либы дергать умеют. Дай им волю, они переписали бы все свои проекты на хранимки. Для меня было странно, что они так хорошо разбираются в перформансе, но при этом не могут писать нормальный код такой, который смог бы понять обычный разраб, а не такой задрот как они. У меня неплохо получалось закрывать задачи, но я чувствовал, что учусь вещам, которые нигде не буду применять и быстро свалил.

Заодно с тех пор зарекся работать на очень старых проектах это камни, которые никогда не оживут.


Спасибо за помощь со статьей пацанам из Мы обречены, посмотрите их подкаст.

Подробнее..

Категории

Последние комментарии

  • Имя: Макс
    24.08.2022 | 11:28
    Я разраб в IT компании, работаю на арбитражную команду. Мы работаем с приламы и сайтами, при работе замечаются постоянные баны и лаги. Пацаны посоветовали сервис по анализу исходного кода,https://app Подробнее..
  • Имя: 9055410337
    20.08.2022 | 17:41
    поможем пишите в телеграм Подробнее..
  • Имя: sabbat
    17.08.2022 | 20:42
    Охренеть.. это просто шикарная статья, феноменально круто. Большое спасибо за разбор! Надеюсь как-нибудь с тобой связаться для обсуждений чего-либо) Подробнее..
  • Имя: Мария
    09.08.2022 | 14:44
    Добрый день. Если обладаете такой информацией, то подскажите, пожалуйста, где можно найти много-много материала по Yggdrasil и его уязвимостях для написания диплома? Благодарю. Подробнее..
© 2006-2024, personeltest.ru