Логическое программирование и кому оно нужно
Что это
Логическое программирование основывается на выводе информации, являющейся результатом изучения фактов.Образно говоря, это чем-то похоже на процесс обучения ребенка, когда вам чётко надо задать окружающие объекты, которые трогать «нельзя», остальные же изначально помечаются, как «доступные». Получив ваши наставления ребёнок начинает изучать мир и, сопоставляя данные, принимает решения. В логическом программировании этот принцип повторяется практически в точности, но разумеется в чуть более сложной форме.
Самым известным представителем и пожалуй самым популярным из используемых, является язык Prolog.
Prolog
Раз мы заговорили об этом популярном представителе ветви логического программирования, то остановимся на нём немного подробнее. Он был основан в начале 70-х годов 20 века, когда компьютеры только-только стали доступными для широких масс. С точки зрения построения и синтаксиса это не самый простой язык, но с точки зрения понимания ответных действий машины — почти идеальный. Просто взгляните на код, которым можно описать автомобиль:
auto( ‘Model’, ‘Year’, ‘Engine’, Power( ‘h.p.’, ‘kW’ ) ).
Согласитесь, такую структуру легко понять и идентифицировать параметры, а ведь это едва ли не самое сложное, что можно увидеть в Prolog.
Изначально именно поэтому ему была уготована больше просветительская участь, чем реально полезная. Но со временем Prolog оказался полезен на передовой — в создании искусственного интеллекта и при работе с базами данных. В свежем рейтинге TIOBE Prolog занял весьма достойное 38 место.
Рассмотрим основные плюсы и минусы этого языка.
Операции, совершаемые в логическом программировании всегда понятны;
Результат практически всегда не зависит от выбранного пути реализации;
Может быть использован в качестве невычислительного языка используя только выражения и факты.
Если брать за пример логического языка программирования Prolog, то на лицо невозможность создания комплексных задач. То есть в реальности логический язык может идти дополнением к процедурному, но самостоятельно используется крайне редко;
Из-за недостатка в инвестициях и простом внимании, логические языки слабо развиваются;
Если предстоит иметь дело с вычислительными операциями, то логические языки программирования — не лучший выбор.
Кому изучать
Следуя примеру советских студентов, изучать логическое программирование будет полезно практически всем и в любом возрасте, просто потому, что это здорово развивает умение мыслить поступательно и логически. Плюс, как уже было сказано, если ваша работа так или иначе связана с созданием искусственного интеллекта или хотя бы с данными, то язык Prolog и ему подобные — станут полезным инструментом.
Почитать
Изучение языка, а тем более целого класса языков немыслимо без чтения хороших книг. Вот некоторые из них:
Программирование на языке ПРОЛОГ, Уильям Клоксин — базовый обучающий курс логического и, что важно, практического программирования;
Алгоритмы искусственного интеллекта на языке PROLOG, Иван Братко — занимательная книга, пошагово и достаточно интересно знакомящая читателя с языком Prolog через операции по созданию ИИ;
Problem Solving With Prolog, Джон Стобо — данное творение отличается чуть более углубленной подачей материала, рекомендуется использовать, как 2-3 книгу для изучения Prolog;
The Art Of Prolog: Advanced Programming Techniques, Леон Стерлинг — книга, выпущенная в MIT в далёких 80-х годах, не теряет свою актуальность и сегодня, в основном благодаря большому количеству примеров кода;
From Logic to Logic Programming, Кис Доетс — ещё одно произведение из MIT, но на этот раз про логическое программирование в целом. Уровень подготовки требуется достаточно серьёзный, поэтому подготовьтесь много “гуглить”.
Logic-Based Artificial Intelligence, Джек Минкер — самое старое творение, но при этом одно из самых фундаментальных.
Пару месяцев назад мы с вами бегло обсудили функциональное программирование, а теперь пришло время затронуть ещё один тип — логическое программирование. В некоторой литературе эти два типа часто объединяют, противопоставляя императивному, однако основные принципы всё же различны.
Что это
Логическое программирование основывается на выводе информации, являющейся результатом изучения фактов.Образно говоря, это чем-то похоже на процесс обучения ребенка, когда вам чётко надо задать окружающие объекты, которые трогать «нельзя», остальные же изначально помечаются, как «доступные». Получив ваши наставления ребёнок начинает изучать мир и, сопоставляя данные, принимает решения. В логическом программировании этот принцип повторяется практически в точности, но разумеется в чуть более сложной форме.
Самым известным представителем и пожалуй самым популярным из используемых, является язык Prolog.
Prolog
Раз мы заговорили об этом популярном представителе ветви логического программирования, то остановимся на нём немного подробнее. Он был основан в начале 70-х годов 20 века, когда компьютеры только-только стали доступными для широких масс. С точки зрения построения и синтаксиса это не самый простой язык, но с точки зрения понимания ответных действий машины — почти идеальный. Просто взгляните на код, которым можно описать автомобиль:
auto( ‘Model’, ‘Year’, ‘Engine’, Power( ‘h.p.’, ‘kW’ ) ).
Согласитесь, такую структуру легко понять и идентифицировать параметры, а ведь это едва ли не самое сложное, что можно увидеть в Prolog.
Изначально именно поэтому ему была уготована больше просветительская участь, чем реально полезная. Но со временем Prolog оказался полезен на передовой — в создании искусственного интеллекта и при работе с базами данных. В свежем рейтинге TIOBE Prolog занял весьма достойное 38 место.
Рассмотрим основные плюсы и минусы этого языка.
Операции, совершаемые в логическом программировании всегда понятны;
Результат практически всегда не зависит от выбранного пути реализации;
Может быть использован в качестве невычислительного языка используя только выражения и факты.
Если брать за пример логического языка программирования Prolog, то на лицо невозможность создания комплексных задач. То есть в реальности логический язык может идти дополнением к процедурному, но самостоятельно используется крайне редко;
Из-за недостатка в инвестициях и простом внимании, логические языки слабо развиваются;
Если предстоит иметь дело с вычислительными операциями, то логические языки программирования — не лучший выбор.
Кому изучать
Следуя примеру советских студентов, изучать логическое программирование будет полезно практически всем и в любом возрасте, просто потому, что это здорово развивает умение мыслить поступательно и логически. Плюс, как уже было сказано, если ваша работа так или иначе связана с созданием искусственного интеллекта или хотя бы с данными, то язык Prolog и ему подобные — станут полезным инструментом.
Почитать
Изучение языка, а тем более целого класса языков немыслимо без чтения хороших книг. Вот некоторые из них:
Программирование на языке ПРОЛОГ, Уильям Клоксин — базовый обучающий курс логического и, что важно, практического программирования;
Алгоритмы искусственного интеллекта на языке PROLOG, Иван Братко — занимательная книга, пошагово и достаточно интересно знакомящая читателя с языком Prolog через операции по созданию ИИ;
Problem Solving With Prolog, Джон Стобо — данное творение отличается чуть более углубленной подачей материала, рекомендуется использовать, как 2-3 книгу для изучения Prolog;
The Art Of Prolog: Advanced Programming Techniques, Леон Стерлинг — книга, выпущенная в MIT в далёких 80-х годах, не теряет свою актуальность и сегодня, в основном благодаря большому количеству примеров кода;
From Logic to Logic Programming, Кис Доетс — ещё одно произведение из MIT, но на этот раз про логическое программирование в целом. Уровень подготовки требуется достаточно серьёзный, поэтому подготовьтесь много “гуглить”.
Logic-Based Artificial Intelligence, Джек Минкер — самое старое творение, но при этом одно из самых фундаментальных.
Источник
Введение в логическое программирование (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 рублей.
Примеры запросов о покраске на Prolog
- colouring_cost возвращает стоимость покраски для заданных площади и цвета, при этом для получения стоимости покраски одного метра обращается к предикату colour_cost. Мы можем написать запросы для получения всех возможных вариантов покраски заданной площади или узнать сколько будет стоить покраска определенным цветом:
Примеры запросов о покраске поверхности на Prolog
Примеры запросов о покраске поверхности на Prolog В приведенном фрагменте исходного кода предикат 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].
Источник
