Логические языки программирования. Основные положения и понятия. Основные отличия от других типов языков программирования.
Логические языки – все операции представлены в виде логических формул. В программе допустимы логические причинно следственные связи. Таким образом логические программы базируются на классической логике и применимы для систем логического вывода.
Высокий уровень машинной независимости
Возможность откатов (возвращение к предыдущей подцели, и отрицательного в результате анализа одного из вариантов в процессе поиска решения)
Специфичность класса решаемых задач.
Сложность эффективной реализации для принятия решения в реальном времени.
Нелинейность структуры программы.
Логическое программирование — это парадигма программирования, в которой программы пишутся не в виде последовательности инструкций, а в виде множества фактов и правил, а процесс выполнения программы сводится к выводу нужных результатов из этого множества.
Объектно-ориентированные языки программирования (ооп). Основные отличия от других концепций языков программирования.
Программа представляет собой описание объектов, их свойств — атрибутов, совокупностей – классов. Отношений между ними, способов их взаимодействия и операциями над объектами (методы). Классы при этом образуют иерархию.
Концептуальная близость к предметной области. Произвольные структуры и назначения.
Поддержка механизма обработки событий, которые изменяют атрибуты объектов, и моделирует их взаимодействие в предметной области.
Использование раннее разработанных библиотек объектов и методов, что снижает трудозатраты и временные затраты.
Объекты классы и методы могут быть полиморфными, что делает программное обеспечение более гибким и универсальным.
Сложность адекватной т.е. непротиворечивой, полной формализации объектной теории, рождает трудности тестирования и верификации созданного программного обеспечения.
Полиморфизм в ооп. Виртуальные функции. Таблицы виртуальных функций.
Полиморфи́зм (от греч. πολὺ- — много, и μορφή — форма) в языках программирования — возможность объектов с одинаковой спецификацией иметь различную реализацию.
Возможность объектов с одинаковой спецификацией иметь различную реализацию.
Предполагает использование одного объекта языка, для выполнения различных действий.
Язык программирования поддерживает полиморфизм, если классы с одинаковой спецификацией могут иметь различную реализацию — например, реализация класса может быть изменена в процессе наследования.
Различают полиморфизм статический и динамический.[ В статическом полиморфизме множественные формы разрешаются на этапе компиляции.
Родовой настраиваемый сегмент – параметризованный шаблон подпрограммы, использующийся для создания различных конкретных экземпляров подпрограммы. ]Динамический полиморфизм – структурная неопределенность остается до этапа выполнения.
Вариантные/неограниченные записи. Одна переменная может иметь значения разных типов. (Вариантная запись – запись, состоящая из фиксированного числа полей, но позволяющая по-разному рассматривать области памяти, занимаемые полями. Предполагается, что в любой момент времени значимо только 1 из полей объединения, в отличие от обычных записей, где все поля существуют одновременно).
Диспетчеризация во время выполнения (динамич диспетчеризация – механизм, посредством которого разрешение обращения к переопределенному методу осуществляется во время выполнения, а не во вр компиляции. Этот полиморфизм поддерживается методом виртуальных функций.
Логические языки программирования: особенности, примеры
Как часто вы сталкивались с непонятным термин «логическое программирование» и не могли понять, что это? Сегодня мы, наконец, решить, с какой из языков программирования логического типа, и рассмотрим примеры таких языков.
Прежде чем начать обзор языков, вы должны сначала знать что это такое и зачем оно нужно. Что такое логическое программирование?
Это подход к программированию, основанный на доказательстве теорем и выводе информации на основе фактов. Результат-это побочный эффект программы. Логическое программирование основано на теории, математической логики, включает в себя раздел дискретной математики и некоторые другие. Каковы различия?
Многие объединяют логических языков программирования функциональные, но имеют некоторые различия, о которых мы ниже и поговорим.
В отличие от функциональных, логических очень подходит для создания искусственного интеллекта. Кроме того, иногда это очень полезно, когда в языке переменные не делятся на входящие и исходящие. И в этих языках, и бывает, что иногда упрощает работу с кодом. Даже в этом случае программы выполняются быстрее и выполняют свои задачи, иногда более эффективно. Основная особенность логических языков программирования заключается в том, что программа-это определенные отношения между элементами.
Тем не менее, есть и недостатки. Не все можно описать с помощью логики, поэтому, в таких программах всегда работают так, как нужно, или не работают вообще. Кому полезно изучать языки программирования логического типа?
Стоит сразу ответить на вопрос: выучить этот язык полезно всем – от студента до человека в возрасте. Потому, что логика языки программирования способны в буквальном смысле заставить наш мозг думать логически. Даже языки, будут очень полезны в создании искусственного интеллекта, или когда вы работаете с данными. Логические языки программирования
Таких языков не так много, и они отличаются между собой. Это говорит лишь о двух, и для начала, с которого началась эра логических языков, и его имя Prolog.
Этот язык был разработан в 1972 году Аллен Преодолеть и это важно, и свежее, и до сегодняшнего дня. Даже если это не самый простой язык в плане синтаксиса, но это очень полезно в понимании логики компьютера. Посмотрите, как выглядит код, который описывает книгу:
книга( ‘Имя’, ‘2009’, ‘Monza’, автор (Первый автор’, ‘По мнению автора’ ) ).
Такое описание является достаточно простой, чтобы понять и проанализировать, что. Вот почему обучение такой язык не будет огромных трудностей и не требует танцев с бубном.
Идем далее проанализировать свои плюсы и минусы.
1. Код легко понять и запомнить.
Как уже упоминалось ранее, код на языке Prolog писал не так уж и сложно. Это довольно простой, в понимании обычного пользователя.
2. Выражения и факты.
Этот язык можно использовать без каких-либо расчетов, полагаясь только на выражение мнений и фактов.
3. Пути, не интересует.
Любой путь к реализации вашей идеи, что вы выбираете, это практически никогда не влияет на результат выполнения программы.
1. Слабые инвестиции.
В связи с тем, что этот язык мало поддерживают в материальном плане – растет очень медленно, маленькими шагами.
2. Невозможность создания сложных программ.
Этот язык не будет, можно использовать без связки с другим, если вы хотите создать более сложные программы с большей функциональностью.
3. Вычислительные операции.
Для расчета, даже в этом случае вам придется использовать другие языки.
Ушел от языка Prolog, Mercury создана, чтобы решить две проблемы, связанные с популярным языком программирования.
Логические языки программирования гораздо меньше, чем с точки зрения производительности важно, типа.
В языках этого типа уходит много времени для отладки программы, так как происходит меньше проверок на ошибки в программе, что иногда возникают проблемы.
Пример кода Mercury:
:- module привет. :- interface. :- import_module я. :- pred main(я. я::ну-нс) is det. :- implementation. main(!Я) :- я.write_string(«Hello, World! «что !Я).
Синтаксис и понимание этого языка, как вы можете заметить, сильно отличается от «Пролога», который является немного сложнее образование, тем не менее, некоторые свои плюсы, позволяют решить проблему «Пролог», это очень полезно. Заключение
Язык программирования-это язык, который управляет выражения и факты, и побочный эффект дает правильный результат работы программы. Эти языки являются очень полезными в создании искусственного интеллекта и работы с данными, однако, редко применяются без сторонних языков программирования. Автор: Владислав Астрахань 14 Августа, 2018
Что такое логическое программирование и зачем оно нам нужно
Если вас всегда терзали мучительные сомнения — что за фигня это Логическое Программирование (ЛП) и вообще зачем оно нужно? То это статья для вас.
Можно по-разному разделить языки программирования на группы (часто их называют парадигмами программирования), например, вот так:
- структурное: программа разбивается на блоки — подпрограммы (изолированные друг от друга), а основными элементами управления являются последовательность команд, ветвление и цикл.
- объектно-ориентированное: задача моделируется в виде объектов, которые отправляют друг другу сообщения. Объекты обладают свойствами и методами. Абстракция. Инкапсуляция. Полиморфизм. Ну в общем, все в курсе.
- функциональное: базовым элементом является функция и сама задача моделируется в виде функции, а, точнее, чаще всего в виде их композиции, если f(.) и g(.) — это функции, то f(g(.)) — это их композиция.
- логическое: вот тут, как правило, начинается феерия — если про первые три написаны сотни статей, книг, обзоров, презентаций и учебников, то здесь мы в лучшем случае видим что-то про Prolog и разработки времён Pink Floyd и Procol Harum (ну хоть с музыкой им тогда повезло) и на этом история заканчивается.
Вот эту оплошность я и собираюсь сегодня исправить.
Важнейший тезис этой статьи:
И вообще последний вам скорее всего не нужен. А вот первое вполне может быть.
Структура статьи:
- Что такое Пролог и почему он вам скорее всего не нужен
- Зачем оно надо, или краткое введение в Answer Set Programming
- Решаем задачи на ASP
- Комбинаторная оптимизация
- Вероятностное ЛП: ProbLog
- ЛП на классической логике FO(.) и IDP
- Sketched Answer Set Programming
- Экспериментальный анализ
- Тестирование и корректность программ
- Заключение
В данной статье (возможно) впервые на русском языке собраны основные аспекты современного логического программирования вместе с объяснением зачем они нужны. Логическое программирование (ЛП) напрямую связано с темой моего PhD (о нем будет отдельный подробный пост). В процессе работы я заметил, что материала на русском языке практически не существует и решил заполнить этот пробел (в русской википедии даже нет статьи про ASP, которую бы стоило написать).
Отдельные части статьи могут быть не связаны с друг другом напрямую, такие какие Sketching и Problog — в некотором смысле это персональный обзор наиболее интересных тем и разработок в области логического программирования. Здесь безусловно не получится покрыть все темы связанные с ЛП — но можно считать, что это первый шаг, чтобы заинтересованный читатель погрузился в тему или представил, что ЛП за зверь такой.
Что такое Пролог и почему он вам скорее всего не нужен
Prolog (Programming in Logic, в оригинале: programmation en logique) был разработан в Марселе в начале 70-х Аленом Колмероэ. В основу языка легла процедурная интерпретация логических выражений Хорна (т.е., как именно можно машинно выполнить) утверждений вида:
Что может быть прочитано как: «если условия b, c, d, . z — выполнены, тогда и «a» должно быть верно.
И, упрощенно говоря (вот тут мы опускаем все технические детали), может быть переписано в виде логического следования:
По сути Сэр Боб Ковальски — — придумал такую вещь: утверждение «a» верно, если мы докажем, что все предпосылки к нему верны. (Кстати, отличный и веселый мужик — еще здоров и сыпет шутками и байками, год назад на конференции в Королевском сообществе в Лондоне он прочитал отличную и временами смешную лекцию по истории Пролога и логического программирования.)
«a» — верно, если я могу: доказать «b», доказать «c» и доказать «d».
Тогда каждая программа — это набор теорем для вывода утверждений, а каждое выражение «доказывается» (внимательный читатель конечно же заметит здесь изоморфизм Карри — Ховарда).
Задача становится чуть веселее, если добавить сюда отрицание. В Прологе оно называется negation as failure и отличается от классического отрицания в логике. В теории это звучит так: если я не смог доказать утверждение «a», то значит оно неверно. В логике такое предположение называется closed world assumption и иногда оно очень даже осмысленно.
Negation as Failure и Closed World Assumption
Представьте себе расписание автобуса 11-го маршрута города Самары, фрагмент:
- 15:15
- 15:45
- 16:15
- 16:45
- 17:15
Вопрос: есть ли автобус в 16:00? Его нет, потому что мы не можем доказать, что он есть согласно расписанию — т.е. расписание обладает полной картиной мира хождения 11-го маршрута в городе Самаре. Отсюда собственно и название closed world assumption — предположение о том, что весь условный мир описан данной программой — всё вне — ложно. Как правило также применяется в базах данных — кстати про них писал тут.
Пролог, как Тьюринг полный язык программирования
Вместе с еще парой интересных операторов (как например cut) из Пролога получается — Тьюринг полный язык — вкратце — если программа на прологе P вычисляет функцию f(x), то найдется программа M на любом другом Тьюринг полном языке, которая тоже вычисляет f(x). Таким образом, если вы можете решить программу на Прологе — значит и на любом другом языке (Python, Java, C, Haskell, etc) можно написать решение. Никаких чакр тут не открывается.
В целом решение задачи на Прологе раскладывается согласно Бобу Ковальски в схему
Хороший пример задачи, которая хорошо формулируется и решается на прологе, — это набор правил, согласно которому выполняется или нет определенное условие. Однако вам самим придется задать алгоритм поиска решения — что является пространством допустимых значений, в каком порядке они обходятся и тд. По сути вы моделируете задачу в виде правил вывода и с помощью правил вывода задаете процедуру поиска решения (порядок правил, cut, переход от значений в списке из тела правило в голову, и тд) и допустимое пространство решений.
Приведем в качестве примера быструю сортировку на прологе — комментарии мои, код из The Art Of Prolog (если у вас возникнет спонтанное желание читать рэп изучать Пролог, то рекомендую именно эту книгу)
Мы видим, что предикат quicksort определен для двух случаев — пустой и непустой список. Нам интересен непустой случай: в нем список [X|Xs], где X — голова списка, т.е., первый элемент (car — для тех, кому кажется, что в этой программе мало скобочек) и Xs — хвост (tail, он же cdr) разбивается на два списка Bigs и Littles — те, кто больше, и те, кто меньше, Х. Затем оба этих списка рекурсивно сортируются и объединяются в финальный выходной список Ys. Как мы видим в целом мы задаем правилами вывода работу всего алгоритма.
Чем хорош пролог? У него хорошо с формальной семантикой — т.е. можно формально показывать свойства (например доказать, что программа выше и правда сортирует числа), хорошо расширяется на вероятностный случай (см. раздел ProbLog) и вообще хорошо расширяется, удобный язык для моделирования логических задач, хорошо подходит для математических работ, для мета-языковых операций и тд.
Вкратце, если вы не пишите научную работу, где вам нужно формально показать свойства поведения программы — скорее всего вам не очень нужен Пролог. Но может быть вам пригодится логическое программирование?
Зачем оно надо, или краткое введение в Answer Set Programming (ASP)
Краткое объяснение, что такое ASP:
Вот тут стоит начать с такой штуки, как декларативное программирование и принцип устойчивости к изменениям (elaboration tolerance principle) от Джона Маккарти (который придумал LISP, повлиял на Алгол и вообще предложил термин «Искусственный Интеллект»).
Что такое декларативный подход? Если вкратце, то мы описываем задачу и её свойства, а не как её решать. В этом случае задача чаще всего представляется в виде:
Где мы регулярно встречаемся с таким подходом? Например, в базах данных SQL — это декларативный язык запросов, а поиском ответа на этот запрос занимается СУБД. Для эффективной работы СУБД придуманы тысячи эффективных алгоритмов, данные хранятся в оптимизированном виде, всюду индексы, методы оптимизации запросов и тд.
Но самое важное, что пользователь видит вершину айсберга: язык SQL. И имея некоторое представление о СУБД пользователь может писать эффективные запросы. Объясним для начала принцип устойчивости к изменениям на простом примере. Допустим, что мы написали простой запрос Q, который считает среднюю зарплату по департаментам компании. Через какое-то время нас попросили немного изменить запрос — например не учитывать в подсчетах менеджмент — нас стала интересовать средняя зарплата технических специалистов. В таком случае, в запрос Q нужно добавить всего лишь условие «role != ‘manager'».
Значит, наш новый запрос Q_updated представляется в виде базового запроса + дополнительное условие. Говоря чуть более обще, мы видим, что
А значит, что когда мы немного меняем условие задачи на какое-то дополнительное условие X, нам необходимо изменить модель (которая моделирует изначальную задачу на каком-то формальном языке — например SQL), добавив дополнительное условие C_X.
Причем тут ASP и Логическое программирование?
- Много материала можно найти на странице профессора Торстена Шауба Штефана Халбоблера
- Подборка видео tutorial: into into ASP, ASP for Knowledge Representation
- Хороший вводный материал от Томаса Айтера: ASP primer
- Книга ASP in Practice — раньше была в свободном доступе (сейчас что-то не вижу прямой ссылки)
В чем принципиальная разница между Прологом и ASP? По сути ASP — это декларативный язык ограничений, т.е., мы задаем пространство перебора в виде специальных ограничений называемых choice rules, например:
Такие правила определяют пространство перебора — буквально читается следующим образом: для каждого X в предикате (читай здесь — во множестве) node, i.e., для каждой вершины X — должен быть верен один — единичка слева от «<" и только один — единичка справа от ">» атом color(X,C), такой что C пришел к нам из множества colors (унарный предикат colors/1).
Одной из главных особенностей ASP является то, что в ограничениях определяется, что НЕ является решением, например — рассмотрим следующее правило:
Ограничения (в научной англоязычной литературе употребляется термин: integrity constraints) — по сути, правила из самого начала статьи — только у них “пустая голова”
empty head: и на самом деле, это сокращение от правил вида:
т.е. если выполняются a_1, … a_n, то выводится “ложь” и моделью это не является.
(еще точнее: false — это синтаксическая конструкция для b :- a_1, …. a_n, not b. — b выводится в предположении, что b неверно — что является противоречием).
На этом закончим теоретический экскурс и посмотрим на правило внимательнее — оно утверждает следующее: если между X и Y есть дуга, цвет Х — это Cx, а цвет Y — это Сy и Cx == Cy, то это НЕ решение.
Кстати говоря, люди знакомые с ASP, скорее всего записали бы это правило так:
Переменные с одинаковым именем внутри одного и того же правила — считаются равными (и скорее всего это поможет на этапе grounding — но это отдельная история).
Перейдем к описанию всей задачи в целом (и еще парочке).
Разбираем пару популярных комбинаторных задач: NP-полных и не очень
Код, описанный здесь, лучше всего запускать в Clasp (где он перед художественной обработкой и написанием комментариев и тестировался).
Мы поговорим о следующих задачах:
- раскраска графа: дан граф, нужно определить можно ли раскрасить его в три цвета так, что никакие две вершины не раскрашены в один и тот же цвет
- черно-белые королевы: на доске n на n, расставить k черных и белых королев, так что никакие две королевы разных цветов не должны бить друг друга
И решим каждую из них с помощью ASP, а заодно и разберем основные приемы моделирования.
Раскраска графа
Нужно раскрасить его вершины в три цвета (красный-синий-зеленый), так чтобы никакие две соседние вершины не были одинакового цвета, либо сказать, что это невозможно.
Выход: 
(картинки взяты отсюда)
Основные конструкции ASP кода мы уже разобрали — пройдемся по остальным элементам: node/1 (node(a). node(b). ) — объявляет множество вершин графа, порядок не важен, edge/2 — объявляет дуги. Такие атомы в ASP (и логическом программировании) называются — фактами, фактически это сокращение от “a :- true.”, а выводится просто из утверждения, которое всегда верны, т.е., атомы задают данные программы.
Черно-белые королевы
Про расстановку королев (включаю эту вариацию) писал раньше подробнее вот здесь.
(здесь максимальное число ферзей, причем на месте крестика можно поставить белого, а на месте точке черного — но не обоих сразу; взято из статьи)
Код приведенный здесь решает, как простую полиномиальную версию расстановки королев, так и NP-полную версию (см. хабра-статью про королев; здесь предполагаем, что результат по сложности для классической версии также распространяется и на эту вариацию).
Разберем код чуть подробнее, следующие правила задают параметры доски — по сути, мы могли бы решать задачу и с большим количеством цветов королев — цвета здесь записаны в виде значений предиката color/1 .
Далее нам нужно объявить пространство поиска:
По сути данное правило читается так: для каждого цвета С, должно быть k и ровно k королев цвета C, причем значение Row и Col должно быть из множества предикатов col/1 и row/1 . Проще говоря, для каждого цвета мы устанавливаем количество корректных (на доске) королев равным k.
Далее мы описываем что не является решением: если мы разного цвета на одной строке, колонке или диагонали:
По сути мы видим, что наш код хорошо раскладывается на две части: пространство поиска (guess) + валидация ответа (check) — в ASP это и называется guess-and-check парадигмой, а весь код хорошо ложится на уравнение Problem = Data + Model — в отличие от SAT, если я поменяю данные — добавлю новых королев, то сами ограничения (правила модели) не изменятся. Вообще мы могли бы переписать эти правила, чтобы они даже цвета принимали в качестве параметра.
Кратко о комбинаторной оптимизации
Суть проста: есть комбинаторная задача, как например поиск цикла Гамильтона (NP-полная задача), но сверху есть доп условие: что-то нужно минимизировать — например вес пути (количество цветов для раскраски графа, максимизировать число королев или цветов королев и тд.) Как правило это дает скачок сложности задачи и делает поиск довольно сложным. У ASP есть стандартный механизм для решения задач комбинаторной оптимизации.
Разберем задачу поиска цикла Гамильтона с оптимизацией веса пути (код из книги Answer Set Solving in Practice. Martin Gebser et al.; комментарии — мои)
По сути мы видим, что задача комбинаторной оптимизации в ASP хорошо раскладывается в декларативное уравнение:
Также в задаче присутствует часть вывода новых фактов (auxiliary inference), которые потом используются в ограничениях. Это также довольно стандартно для программ, написанных на ASP.
Вероятностный Prolog — ProbLog
Prolog хорош тем, что он хорошо расширяется — как язык, в том числе и на вероятностный случай — ProbLog (в шутку я читаю его всегда, как Проблох — референс к его фламандскому происхождению и тому, как его читают авторы) — Probabilistic Prolog.
Теоретические основы вероятностного логического программирования изложены в статье
A Statistical Learning Method for Logic Programs with Distribution Semantics by Taisuke Sato
(Он, кстати, еще в трезвом уме и здравой памяти — выступал на ILP 2015 в Киото — где задавал участникам много интересных и коварных вопросов)
Основные материалы по теме можно найти здесь (там же есть онлайн-редактор и tutorial, статьи и тд)
По сути представьте себе, что теперь правила пролога выводят не факт, а вероятность того, что данный факт верен, например, представим, что у нас есть набор нечестных монет, нечестных потому что вероятность выпадения орла не 0.5, а ну например 0.6 — вопрос какова вероятность выпадения орла, если мы подкинем четыре таких монетки?
В первом правиле мы описываем какие у нас есть случайные величины — это переменные, описывающие выпадение орла (сами факты о монетках — детерминированные), потом мы описываем стохастическую величину — someHeads — выпадение хотя бы одного орла, через имеющиеся у нас вероятностные величины — монетки. И последнее — это запрос: какова вероятность выпадения орла.
По сути ProbLog — это очень удобная система моделирования задач, которые представляются в виде группы правил (например бизнес логики) с вероятностным исходом.
Логическое программирование на классической логике FO(.) и IDP
FO(.) и IDP — это во многом очень схожая система с Answer Set Programming: FO(.) — First Order и (.) — референс к расширениям языка на случай индуктивных определений, агрегации и тд. А IDP — это именно система, которая поддерживает язык FO(.). Здесь и далее мы их не различаем (и вообще это отличие похоже существенно только для авторов — но там как главный идейный создатель FO(.) и IDP Марк Денекер все пять лет моего PhD указывал мне эту разницу, я решил хоть где-то провести различие между ними).
По сути вся разница в том, что вместо правил вывода в духе Пролога мы используем классическую логику. IDP также поддерживает простую систему типов.
(я бы упростил код и захардкодил liesInBlock — код из примеров редактора
Смысл в том, что мы можем использовать классические функции и привычные кванторы существования и всеобщности. Возьмем пример из Судоку: каждое число должно встречаться на каждой строке. Пусть наше решение — это функция solution(row, column) -> <1. 9>, тогда должно быть верно следующее:
Проще говоря, для каждой строки и каждого числа есть такая колонка с, что функция на ней отображает (r, c) в n. Именно это ограничение и записано в полном коде выше.
Sketched Answer Set Programming
Лишь вкратце упомяну эту идею — так как это пример одной из разработок в данной области (тем более, что моя разработка, чтобы и не упомянуть действительно). Научная область, объединяющая логическое программирование (logic programming) и машинное обучение (machine learning), ап называется Inductive Logic Programming. В ней происходит много чего интересного и это отдельная история, здесь же приведем лишь один пример связанный с ASP.
Основано на статье Sketched Answer Set Programming by Sergey Paramonov, Christian Bessiere, Anton Dries, Luc De Raedt
Представим, что вы начали изучать ASP и в качестве задания нужно решить черно белых королев — простым гуглением найдем решение на Constraint Programming языке Essense.
Если вы перепишите это ограничения один-в-один на ASP, то получится следующее:
Что безусловно неверно и будет возвращать Unsatisfiable какую бы строчку мы не убрали. Идея sketching состоит в том, чтобы пометить часть программы как «мы вот тут не уверены, что должно быть» и дать примеры, как должна себя вести программа — «вот это решение, а вот это нет»
Условно, мы не уверены в операторах арифметики и неравенствах, мы пометили их вопросом, и дали примеры, что является решением, а что нет. По ним мы можем восстановить исходную программу (как в начале статьи).
Помимо sketching люди учатся восстанавливать целые программы с нуля по примерам — но это отдельная история.
Экспериментальный анализ
В качестве прототипа решения
ASP — хорош в качестве прототипа решения сложных комбинаторных задач, особенно, если это вариация сложной задачи — например NP-полная версия N-queens — как уже описывал ранее вот здесь.
Что куда эффективнее, например, перебора с возвратом.
В качестве общего решения vs специализированный алгоритм
В свой статье Relational Data Factorization (Paramonov, Sergey; van Leeuwen, Matthijs; De Raedt, Luc: Relational data factorization, Machine Learning, volume 106) мы провели очень подробный анализ общего решения одной проблемы, для частного случая которой есть специализированные алгоритмы и в целом картина вот такая:
Специализированные алгоритмы существенно быстрее — как мы видим слева по синей и красной кривой (такой специализированный алгоритм + формулировка задачи и тд
= год труда ученых) при одинаковом качестве — синяя и красная линия справа — однако, в некоторых задачах можно использовать приближенные методы на базе ASP и пожертвовать качеством для получения выигрыша в скорости — зеленая линия.
Гибридные решения
В определенных ситуациях задача может распасться на две части: базовая формулировка задачи + дополнительные ограничения, в такой ситуации можно использовать связку:
На ряде задач, например в случае с structured frequent pattern mining гибридные решения имеют существенное преимущество в масштабируемости (см. Paramonov, Sergey; Stepanova, Daria; Miettinen, Pauli: Hybrid ASP-based Approach to Pattern Mining, Theory and Practice of Logic Programming, 2018):
Сравнение на синтетическом датасете последовательностей (от авторов другого метода; разница работы на настоящих крупных датасетах несколько порядков — у нас десятки секунды-минуты, у них не получается вычислить все последовательности за ночь вычислений)
Так же для графовых датасетов разница еще существенней, тут сравнивается старый декларативный метод и новый гибридный (логарифмическая шкала)
Отсюда следует, что если у нас есть специализированный алгоритм и дополнительные ограничения, то при определенных условиях их можно соединить для более эффективного и общего решения.
Тестирование и корректность программ
Обычно, научные задачи, особенно комбинаторные, сложно отлаживать и еще сложнее показать их корректность. Отсюда возникают подобные проблемы в духе вот таких:
И в целом, если вы думали, что научный код обычно необычайного качества, покрыт тестами и легко поддерживается, то вот кусочек кода из LCM-k:
Одной из важных особенностей программ с формальной семантикой является доказуемость их корректности, точнее говоря, вы смещаете фокус вопроса корректности на «ASP solver», т.е. систему которая может работать с языком Answer Set Programming. Вы можете показать, что программа и правила математически корректно моделируют вашу задачу — и вопросы по верному выполнению переходят в сообщество разработчиков. У систем, как правило, открытый код — так же они хорошо покрыты тестами и ими пользуются немалая группа юзеров. В среднем, мы достаточно уверены, что с ASP системами все хорошо в плане правильного выполнения кода.
Обычно, когда на свет выходит новый алгоритм (и статья вместе с ним), мы как бы просто верим в часть помеченную «?» на схеме:
В случае с ASP — algorithm и implementation являются одним и тем же (ну если вы не обернете ASP в процедурные вызовы в алгоритме), а значит можно показать формальную корректность самого кода.
Например, это можно использовать в качестве:
- прототипа решения
- baseline алгоритма
- тестирования более быстрой версии на корректность
Заключение
Сегодня мы многое поняли (с) — и прикоснулись к вершине айсберга логического программирования. Тезисно (tl;dr) статья умещается в несколько пунктов:
Введение в логическое программирование (Prolog)
На блоге я публиковал ряд статей по логическому программированию, а также разбирал решения задач на языке Prolog. Недавно я заметил, что из всего этого могла бы получиться полноценная методичка если добавить введение. Введение написано так, чтобы после его прочтения Вы смогли начать программировать на Prolog, более строгой с математической точки зрения материал стоит искать в книгах по ФЛП [2].
Первые языки логической парадигмы программирования были разработаны в середине 20 века как инструменты для автоматического доказательства теорем, при этом в их основе лежал математический аппарат исчисления предикатов [1]. Позже их стали применять в качестве языков программирования общего назначения, при этом языки были дополнены рядом синтаксических конструкций.
Языки логического программирования имеют небольшое распространение, тем не менее их применяют при разработке трансляторов и искусственного интеллекта [2], они могут использоваться для разработки любых десктопных и мобильных приложений [3, 4], а также сайтов [5]. Компания PDC, разрабатывающая Visual Prolog, применяет его при программировании авиационных и медицинских систем (конкретные проекты можно посмотреть на официальном сайте) [6]. Сам я разрабатываю на Prolog инструменты оптимизации программ — это оказалось гораздо удобнее чем на С++, при этом пользуюсь SWI Prolog (поэтому именно на нем написаны все примеры этой статьи).
Если вы когда-либо программировали на императивных языках, таких как Java — то Prolog покажется вам необоснованно запутанным. Императивные языки создавались для вычислительных машин архитектуры фон Неймана, в которой команды для выполнения выбираются последовательно, а циклы и ветвление реализуются посредством специальных команд перехода. В языках логической парадигмы это работает совсем иначе.
Логическая программа состоит из предикатов, представляющими собой функции, вырабатывающие логические значения — любой предикат содержит вычисления, которые могут быть либо истинными, либо ложными. При этом результаты вычисления предикат возвращает только если вычисления истинны. Предикаты состоят из правил (предложений), описывающих вычисления и соединенных между собой логическими операторами И/ИЛИ, при этом логическому И соответствует оператор запятая, а ИЛИ — оператор точка. Программы на языке Prolog могут содержать также переменные (их имена обязательно должны начинаться с большой буквы — этим они отличаются от других объектов), однако одним из базовых в логическом и функциональном программировании является принцип однократного присваивания, в соответствии с которым переменная может получить значение лишь один раз, все остальные попытки присваивания будут работать как проверка на равенство. Следствием принципа однократного присваивания является отсутствия циклических конструкций в Prolog — вместо них везде применяется рекурсия, что не снижает скорость работы программы, т.к. хвостовая рекурсия также эффективна, как и цикл [9].
Для понимания принципов управления вычислениями в prolog, удобно представлять программу в виде дерева как показано на примере вычисления суммы цифр числа.
дерево вычислений prolog (вычисление суммы цифр числа)
Подобное дерево строится во многих интерпретаторах языка Prolog, т.к. выбор операторов для выполнения в программе должен выполняться в порядке обхода дерева слева направо. Розовым цветом я обозначил предикат, состоящий из двух правил, выделенных зеленым цветом. Листья дерева соответствуют операциям, вычисление которых может завершится либо истиной, либо ложью. В операциях, соединенных логическим И все операции должны вернуть истинное значение чтобы результатом стала истина, поэтому если любая из таких операций завершилась ложью — результат может быть получен сразу (без вычисления остальных). Так например, если Number >= 10, то первое правило сразу завершится ложью и управление будет передано второму правилу, т.к. они соединены с помощью логического ИЛИ.
Чуть позже мы еще раз вернемся к примеру с суммой цифр числа, но сначала рассмотрим механизмы поиска с возвратами ( backtracking ) и сопоставления с образцом ( pattern matching ), которые также лежат в основе логического программирования. Рассмотрим их на примере программы вычисления стоимости покраски плоской поверхности.
Поиск с возвратами в prolog
В данном случае программа состоит из двух предикатов:
- colour_cost позволяет получить информацию о цене покраски одного метра квадратного заданным цветом, например красная краска стоит 1000 рублей, а белая — 1030. Мы можем спросить у интерпретатора:
- сколько стоит покраска белой краской?;
- у какой краски цена метра равна 1070 рублям?;
- какие есть варианты покраски? (вывести все цены);
- у каких красок цена метра квадратного ниже 1050 рублей.
В приведенном фрагменте исходного кода предикат colour_cost состоит из трех правил, в качестве аргументов правила используются константы (например red и 1000), значения которых интерпретатор пытается присвоить передаваемым переменным или выполнить сравнение. Так, например, при обработке colour_cost(Color, 1070) выбирается сначала самый левый узел дерева, поэтому переменной Color присваивается значение red, а 1070 сравнивается с 1000 — сравнение возвращает false поэтому результат работы не возвращается и интерпретатор пытается подставить следующий узел дерева (colour_cost(white, 1030)). Такой механизм называется сопоставлением с образцом.
Кроме того видно, что при интерпретации предиката пролог может возвращать несколько вариантов решений — это является следствием работы механизма поиска с возвратами, заключающегося в полном переборе вариантов решений. При поиске интерпретатор обходит узлы дерева слева направо, если какая либо ветвь завершилась успешно (вернула истину) — результат возвращается, после чего поиск по дереву может быть продолжен для получения других вариантов решения. Так например, при интерпретации цели всех вариантов покраски прямоугольника 10 на 5 метров с ценой менее 52000 вызывается colour_cost, который в свою очередь вызывает colour_cost(Colour, ColourCost), а значит инициирует полный перебор вариантов покраски. Для каждого варианта будет рассчитана цена, которая после выхода из функции colour_cost сравнивается с константной 52000. Если сравнение проваливается (оператор возвращает false), интерпретатор пытается найти другое решение путем возврата внутрь colouring_cost, а затем подставит следующий необработанный цвет и его стоимость. Если решение для цели найдено — результат возвращается, однако поиск все равно может быть продолжен.
На механизм поиска с возвратам, а следовательно и на управление вычислениями (порядок выполнения операторов) может влиять оператор отсечения, обозначаемое в языке Prolog восклицательным знаком (вы могли видеть его использование в примере функции вычисления суммы цифр числа). При выполнении оператора отсечения перебор решений ограничивается так, что значения всех узлов, выполненных до отсечения (находящихся в дереве «левее») считаются константами — запрещается возврат к ним для расчета других значений. Мы уже использовали отсечение при вычислении суммы цифр числа — если число меньше десяти, то оно содержит лишь одну цифру, а значит нет смысла в рекурсивной обработке числа, т.е. переходе ко второму правилу. В связи с этим первое правило вычисления суммы содержит отсечение. Другие примеры использования отсечения [8]. Различают красные и зеленые отсечения [10].
Важной особенностью логических языков программирования является наличие встроенной базы данных. В зависимости от диалекта, встроенная БД может хранить либо только факты (предикаты, правила которых не содержат тело — как рассмотренный выше предикат colour_cost), либо произвольные предикаты. Работа с записями базы данных в Prolog происходит точно также, как и с любыми другими предикатами, однако их можно добавлять и удалять во время выполнения встроенными функциями assert и retract, чтобы это стало возможным в Vusial Prolog факты требуется описать в секции database, а в SWI Prolog — описать динамическими [11]:
Тогда добавление записи в базу может быть выполнено командой assert(colour_cost(black, 900)), а удаление — retract(colour_cost(red, Cost)). В остальном работа с ними не изменится. В силу того, что записи базы данных пролога в плане обработки никак не отличаются от других предикатов (обрабатываются в соответствии с механизмом поиска с возвратами) — встроенная база данных имеет существенные отличия от баз данных SQL [12].
Принцип однократного присваивания не позволит изменить значение элемента массива, поэтому базовой структурой данных в логических языках программирования является связный список. При этом изменение элемента списка может реализовываться через удаление старого узла и добавление нового. При обработке списков на Prolog учитывается их рекурсивная природа — любой список из одного или более элемента возможно разделить на первый элемент и другой список, особым видом списка является пустой список. Список может быть задан перечислением элементов в квадратных скобках — [1, 2, 3], для обозначения пустого списка используется конструкция из двух квадратных скобок — []. Основной операцией по работе со списками является разделение списка на голову (первый элемент) и хвост (список из остальных элементов) — обозначается вертикальной чертой: [Head|Tail] = [1, 2, 3] — в результате Head = 1, Tail = [2, 3]. Обработка списка происходит рекурсивно, при этом от исходного списка отделяются первые элементы до тех пор, пока он не станет пустым (такой случай обрабатывается отдельно). Примеры рекурсивной обработки списков [13]. Списки являются тем более важными, что с их помощью в Prolog задаются строки, даже в тех диалектах, где строки не являются списком (например Turbo/Visual Prolog), для обработки их удобно преобразовать в список, т.к. это позволит применять к ним более богатый набор функций [14].
Заключение
Статья призвана объединить и сгруппировать информацию по логическому программированию, размещенную на этом блоге — в связи с этим в ней описано небольшое число примеров, но содержится много ссылок, где такие примеры можно найти. Статья является вводной, поэтому в ней разобраны лишь самые основы языка, но любой желающий читатель без труда найдет больше информации, например по работе с файлами [15]. Кроме того, статья ориентированна на начинающих, я хотел, чтобы после ее прочтения (и беглого просмотра связанных ссылок) неподготовленные читатели смогли писать простые простые программы на языке Prolog — поэтому она не содержит строго математического описания логических языков программирования (которое при желании можно найти в книгах) [2].