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

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

Что это

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

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

Логические элементы И, ИЛИ Часть 1

Prolog

Раз мы заговорили об этом популярном представителе ветви логического программирования, то остановимся на нём немного подробнее. Он был основан в начале 70-х годов 20 века, когда компьютеры только-только стали доступными для широких масс. С точки зрения построения и синтаксиса это не самый простой язык, но с точки зрения понимания ответных действий машины — почти идеальный. Просто взгляните на код, которым можно описать автомобиль:

auto( ‘Model’, ‘Year’, ‘Engine’, Power( ‘h.p.’, ‘kW’ ) ).

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

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

Рассмотрим основные плюсы и минусы этого языка.

1. Операции, совершаемые в логическом программировании всегда понятны;
2. Результат практически всегда не зависит от выбранного пути реализации;
3. Может быть использован в качестве невычислительного языка используя только выражения и факты.

1. Если брать за пример логического языка программирования Prolog, то на лицо невозможность создания комплексных задач. То есть в реальности логический язык может идти дополнением к процедурному, но самостоятельно используется крайне редко;
2. Из-за недостатка в инвестициях и простом внимании, логические языки слабо развиваются;
3. Если предстоит иметь дело с вычислительными операциями, то логические языки программирования — не лучший выбор.

Кому изучать

Следуя примеру советских студентов, изучать логическое программирование будет полезно практически всем и в любом возрасте, просто потому, что это здорово развивает умение мыслить поступательно и логически. Плюс, как уже было сказано, если ваша работа так или иначе связана с созданием искусственного интеллекта или хотя бы с данными, то язык 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, Джек Минкер — самое старое творение, но при этом одно из самых фундаментальных.

Источник: gb.ru

Статья Введение в основные принципы логического программирования [часть 1]

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

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

Отступление от 5h3ll:

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

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

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

• Imperative : в этой парадигме используются операторы для изменения состояния программы, что позволяет учитывать побочные эффекты.
• Functional : эта парадигма рассматривает вычисления как оценку математических функций и не позволяет изменять состояния или изменяемые данные.
• Declarative : это способ программирования, при котором вы пишете свои программы путем описывания, что именно вы хотите сделать, а не как вы хотите это сделать. Вы выражаете логику базовых вычислений без явного описания потока управления.
• Object Oriented : в этой парадигме код группируется в программе таким образом, что каждый объект отвечает за себя. Объекты содержат данные и методы, которые определяют, каким именно образом происходят изменения.
• Procedural : в этой парадигме код группируется по функциям, и каждая функция отвечает за определенную последовательность шагов.
• Symbolic : в этой парадигме используется особый стиль синтаксиса и грамматики, с помощью которого программа может изменять свои собственные компоненты, рассматривая их как простые данные.
• Logic : в этой парадигме вычисления рассматриваются как автоматическое обоснование базы данных знаний, состоящей из фактов и правил.

Например, мы хотим вычислить сумму 23, 12 и 49:

Процедура будет выглядеть следующим образом:

23 + 12 + 49 => (2 + 1 + 4 + 1)4 => 84

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

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

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

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

23 : 13 , 21 декабря 2020 г.

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

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

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

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

Всякий человек смертен. Сократ — человек. Следовательно, Сократ смертен.

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

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

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

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

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

Так, теперь стоит успокоиться и разобраться, что же произошло. Вначале мы записали т. н. факты, то есть знания нашей программы о мире. В нашем случае ей известно лишь то, что Платон, Сократ и Аристотель — люди. Но что за странная запись «human(‘Socrates’).» и почему это выглядит как функция? На самом деле «human» и «mortal» — предикаты от одной переменной.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник: news.myseldon.com