Для чего нужен пролог
Prolog — удивительный язык программирования
— Чем же он удивительный? Я знаю пару десятков языков и для меня не проблема изучить еще один новый, я просто уже не вижу необходимости.
Пролог — уникален. Это единственный язык представляющий парадигму декларативного программирования; это язык, который имеет сотни различных имплементаций, но они все равно называются Prolog, добавляя лишь префиксы и суффиксы к названию; это живой язык в котором не происходит никаких существенных изменений более 20 лет; это, наверное, единственный настолько популярный язык программирования, который не имеет применения в реальном программировании. Почему же Prolog?
Пролог — уникален по своей природе, он появился благодаря счастливому совпадению (таинственному устройству мира). Когда-то в 60-х годах очень бурно развивалась теория автоматического доказательства теорем и Робинсоном был предложен алгоритм резолюций, который позволял доказать любую верную теорему (вывести из аксиом) за конечное время (за какое не известно). Как оказалось позже, это наилучшее решение общей задачи, невозможно доказать теорему за ограниченное число операций. Простыми словами, алгоритм представляет собой обход (в общем случае бесконечного) графа в ширину, естественно, что предсказуемость работы алгоритма практически равно 0, соответственно для Языка Программирования — это абсолютно не подходит. И в этот момент Кальмэроу нашел блестящее сужение задачи, благодаря которому доказательство некоторых теорем выглядело как процедурное исполнение программы. Стоит отметить, что класс доказуемых теорем достаточно широк и очень хорошо применим для класса программируемых задач. Вот так в 1972 появился Prolog.
В этой статье я попытаюсь рассказать о Prolog как инструменте решения общих логических задач. Этот топик будет интересен тем, кто уже владеет синтаксисом Prolog и хочет понять его изнутри, а также тем, кто абсолютно не владеет синтаксисом языка, но хочет понять его «изюминку» не тратя лишнее время на изучение синтаксических конструкций.
Главной чертой Prolog является то, что его можно легко читать, но очень тяжело писать, что принципиально отличается от всех mainstream языков, которые так и говорят писать стало еще легче еще один шаг и можно будет писать на планшете, перетягивая рабочие модули как друзей в Google+, от этого все мы знаем очень сильно страдает само качество кода. Вроде бы каждая строчка понятна, но как система работает за гранью понимания даже для разработчиков, как говорится наиндусили. Мне кажется во всех книгах по обучению Prolog, делают одну и ту же ошибку, начиная рассказ о фактах, отношениях, запросах и у человека складывается отношение к языку как к Экспертной Системе или Базе Данных. Гораздо важнее научится правильно читать программы и почитать так с десяток 🙂
Как правильно читать программы на прологе
Читать программы очень просто, так как в языке очень мало специальных символов и ключевых слов и они легко переводятся на естественный язык. Главная ошибка программиста, что он хочет сразу представить как программа работает, а не прочитать, что программа описывает, поэтому мне кажется обучить незатуманенный мозг обычного человека, гораздо проще чем програмиста.
Понятия
Программа
Программа — это набор правил, вида Если условие1 и условие2 и… то верно условие. Формально эти правила объединяются через И, но противоречие получить невозможно, так как в Прологе отсутствует логическое отрицание, а в связке То может присутствовать только один предикат (условие).
Как видно имя переменной имеет область видимости — это правило. Математически верно, правило звучит: для любой переменной — «Число», если оно простое и нечетное, то оно простое_нечетное. Аналогично, можно перефразировать так: Если существует «Число», что оно нечетное и простое, то оно нечетно_простое. Поэтому имя переменной очень важно! Если в левой части (до :- ) заменить Число на Число2, то правило поменяет смысл: Для любого Число2 и Число, если Число — простое и нечетное, то Число2 — простое нечетное. Получается все числа простые_нечетные! Это самая распространенная ошибка в Прологе.
Пример — совершенные числа
Программа — как набор определений
Данный способ чтения широко применяется, так как позволяет объединять предикаты в однородные группы и помогает понять, в каком же порядке интерпретатор раскручивает предикаты, для того, чтобы
проверить истинность некоторого утверждения. Например, очевидно, что если предикат не имеет ни одного определения, то доказать истинность утверждения с ним невозможно. В примере № 1 не имеет определения предикат «делится_на».
Интересный факт, что в Прологе нет ни циклов, ни присвоения переменных, ни объявления типов, а если вспомнить еще про термы и отсечение, то язык становится алгоритмически полным.
Термы
С точки зрения программирования терм можно объяснить гораздо проще: терм — это объект с набором атрибутов, атрибуты могут быть другими термами или константами или переменными (то есть не определены). Главное отличие, все объекты в Prolog immutable, то есть менять атрибуты в них нельзя, зато есть специальное состояние — переменная.
Пример — целочисленная арифметика
Как Prolog понимает предикаты и как доказывает утверждения
Конечно чтение программ, помогает ощутить стиль Пролог, но не делает понятным для чего и как данные определения могут использоваться. Полноценной программой, примеры приведенные выше, назвать нельзя так как не хватает входной точки. Входной точкой в Пролог является запрос, аналог запроса к базе данных SQL или аналог вызова главной функции в функциональном программировании. Примеры запросов: нат(Число) — найти натуральное число, плюс(0, 0, Результат) — найти результат сложения 0 и 0 в переменной Результат, нат(0) — проверить является ли 0 натуральным числом и др.
Конечно, результаты запросов не трудно предсказать из логических соображений, но крайне важно понять, как программа их получила. Все-таки Пролог не черный ящик, а язык программирования, и в отличие от базы данных, где строится SQL-план и запрос может выполняться по-разному на разных Базах данных, Пролог имеет вполне определенный порядок выполнения. Дело в том, что в Базе данных мы вполне знаем какой ответ мы хотим получить исходя из данных в таблице, к сожалению глядя на Пролог программы достаточно сложно сказать, какие утверждения логически выводимы, поэтому понять как работает Пролог интерпретатор гораздо проще.
Рассмотрим на примере запроса плюс(0, 0, Результат) :
1. Находим совпадение (своеобразный pattern-matching, резолюция) данного запроса с левой частью одно из правил. Для данного запроса плюс(0, Число, Число). Соотнесем поочередно все аргументы запроса с правилом и получим: 0 = 0, 0 = Число, Результат = Число. В этих уравнениях участвуют 2 переменные (Число и Результат), решив их мы получаем, что Число = Результат = 0. Так как у данного правила нет условий, мы получили ответ на заданный вопрос. Ответ: да и Результат = 0.
Запрос нат(Число) :
1. Находим 1-е совпадение с правилом, правило нат(0), решая уравнения по соответствию, проще говоря находя резолюцию, мы получаем Число = 0. Ответ: да и Число = 0.
Грамотное составление правил на языке Пролог, очень сложная штука, но если их составить компактно, то можно получать не только прямые ответы и решения, но и обратные.
Пример запроса плюс(Число, Число, Число): ответ да, Число = 0.
Пример запроса плюс(0, 0, 0): ответ нет, при первой же попытке все резолюции не выполняются.
Пример запроса плюс(Число, Число, число(Число)): ответ да, Число = 1. Решение уравнения X + X = X + 1.
Попробуйте провести вывод для умножить(Число, число(0), число(0)), для этого потребуется 2 раза заносить в стек переменные и вычислять новый запрос. Суть Пролог машины такова, что вы можете отказаться от 1-го результата, тогда Пролог вернется к предыдущему состоянию и продолжит вычисление. Например запрос нат(Число), сначала применит 1-е правило и выдаст 0, а затем применит 2-е правило + 1-е правило и выдаст число(0), можно повторить и получить бесконечную последовательность всех натуральных чисел. Другой пример, запрос плюс(Число, число(0), Число2), будет выдавать последовательность всех пар решения уравнения X + 1 = Y.
Заключение
К сожалению, разумный размер топика, не дал мне подобраться к главной теме, а именно к решению сложных логических задач на языке Пролог, не обладая стратегией их решения. Большие куски кода на Прологе могут отпугнуть не только начинающих, но даже опытных программистов. Цель данной статьи показать, что программы на Прологе могут простым образом читаться на естественном языке, а также исполняться простейшим интерпретатором.
Главная особенность Пролога — это не черный ящик и не библиотека, который решает сложные логические задачи, в Mathematica можно ввести алгебраическое уравнение и она выдаст решение, но последовательность выполняемых шагов — неизвестна. Пролог не может решать общие логические задачи (у него отсутствует логическое «или» и «отрицание»), иначе бы его вывод был недетерминированный как линейной резолюции. Пролог — это золотая середина, между простым интерпретатором и машиной для доказательства теорем, сдвиг в любую сторон приводит к потери одного из свойств.
В следующей статье я бы хотел рассказать, как решаются задачи сортировки, о последовательности переливаний, Miss Manners и другие известные логические задачи. Для тех, кто почувствовал себя неудовлеторенным хочу предложить следующую задачу (решившему первым приз):
Написать предикат, который бы генерировал, бесконечную последовательность натуральных чисел, начиная с 3. Это должны быть стандартные числа в Прологе, операции над которыми выполняются при помощи предиката is: X is 3 + 1 => X=4.
Слышали о языке Prolog?
Prolog — это один из тех языков, которые программисты обычно изучают в самом начале карьеры (например — в школе или в институте). Его, правда, забывают почти сразу же после того, как изучили.
Почему? Ну, лично я виню в этом индустрию разработки ПО. Я работаю в этой сфере последние 17 лет. Я участвовал в самых разных проектах, связанных с веб-разработкой и с большими данными (а именно, это были крупные интернет-площадки, ETL-конвейеры и прочее подобное). Суть в том, что за всё это время я не увидел ни одной строчки кода, написанной на Prolog.
Теперь расскажу о том, что случилось на прошлой неделе. Это был совершенно обычный вторник, я проводил собеседование с начинающим программистом. Когда я спросил его о том, на каких ещё языках программирования он может писать, он ответил так: «Я учил Prolog в университете, но им уже никто не пользуется».
Это заставило меня задуматься о том, насколько подобное заявление соответствует действительности.
Конечно, не может быть такого, чтобы совсем никто уже не пользовался этим языком. Хочу сразу сказать, что я — не из тех программистов, которые изучали Prolog в университете. Я никогда не видел этого языка в расписании занятий. А узнал я о нём несколько лет назад, прочтя книгу «Семь языков за семь недель» (кстати, я полагаю, что эту книгу нужно обязательно прочитать каждому программисту). Одним из языков, о которых идёт речь в этой книге, был Prolog. И там, определённо, был раскрыт потенциал этого языка. Я снова задался вопросом о том, почему этим языком больше никто не пользуется.
Учитывая то количество разных языков программирования или фреймворков, которые каждую неделю появляются в различных сферах разработки ПО, можно предположить, что ИТ-экосистема постоянно меняется и весьма динамична. Но это не совсем так. На самом деле, если об этом поразмыслить, то можно понять, что здесь всё не так уж и непостоянно. В ИТ-индустрии присутствуют большие объёмы процедурного программирования, тут есть некоторое количество декларативного программирования, довольно много объектно-ориентированного программирования. А недавно (под «недавно» я понимаю последние несколько лет) заметным стало ещё и функциональное программирование. Существуют и другие парадигмы разработки ПО, но, если верить результатам исследования Stack Overflow 2020 года, десятка самых популярных языков программирования выглядит так, как показано на следующем рисунке.
Самые популярные языки программирования по данным исследования StackOverflow
Если присмотреться к этому списку, то можно распределить языки, входящие в него, по следующим группам:
Но я не отступаю от своего изначального вопроса. А где же разработчики, занимающиеся логическим программированием? Где те специалисты, которые реально пользуются языком Prolog? Ведь этого языка даже нет в результатах исследования. Можете сами в этом убедиться.
Поэтому мой вопрос о том, используется ли всё ещё Prolog, остаётся открытым. А если окажется, что этим языком всё ещё пользуются — мне хотелось бы узнать о том, кто и для чего.
Кто пользуется языком Prolog?
Прошу вас поверить мне на слово: языком Prolog всё ещё пользуются. Просто не так широко, как другими, более популярными языками. У такого положения дел есть серьёзные причины. Прежде чем мы об этом поговорим, хочу, на всякий случай, рассказать о том, что это за язык — Prolog.
▍Общие сведения о Prolog
Prolog — это язык логического программирования. Это означает, что программы на этом языке пишут в декларативном стиле (в противовес использования императивного стиля, применяемого в других распространённых языках). Тут используются такие понятия, как «отношения», «факты», «правила». Они применяются при написании программ. Описав набор фактов и набор правил, можно строить запросы.
Это, определённо, отличается от того, как пишут «обычные» программы, но, если достаточно хорошо разобраться с Prolog, можно понять, что подобный подход значительно упрощает решение некоторых задач.
В ходе разработки программы на Prolog начинают с описания желаемого состояния некоей системы (с предикатов, фактов), а потом предлагают Prolog попытаться достичь этого состояния.
Конечно, прочитав условие этой задачи, мы можем решить её в уме, но если нужно решить её с помощью какого-нибудь из самых распространённых языков программирования, придётся реализовывать некий алгоритм. В ходе его работы будут проверены все возможные пары чисел и найдены результаты их сложения. Программа решит задачу, сообщив о тех парах, сумма которых равняется заданному числу.
Но решение этой задачи на Prolog, в сущности, представляет собой вышеприведённый фрагмент псевдокода. Чтобы этот код заработал, нужно лишь его переписать:
Первые четыре строчки этого кода равносильны утверждениям о том, какие именно числа являются «магическими». А потом мы просто говорим так: «Переменные X и Y — это вышеописанные магические числа. Сумма каких пар этих чисел равняется 6?».
Вот результаты работы этой программы:
Программу можно усложнить для того чтобы избавиться от вариантов решения задачи, где одни и те же числа просто меняются местами, но полагаю, что этот пример достаточно хорошо подходит для демонстрации возможностей логического программирования. Для того чтобы научиться видеть задачи с такой точки зрения нужно время. Дело в том, что программист, при таком подходе, не решает задачу. Он всего лишь описывает правила, по которым работает некая система (то есть, в нашем случае, то, какие числа являются «магическими»), а потом описывает то, что хочет получить в результате решения задачи. То, что находится между описанием задачи и желаемого результата, то есть то, что составляет процесс решения задачи, описываемый в других языках самим программистом, тут выполняется средствами самого языка.
Если вы хотите ознакомиться с другими примерами применения Prolog для решения подобных задач — загляните сюда. Тут вы найдёте много интересного.
Теперь, учитывая мощь, которую даёт нам Prolog, подумаем о том, как вам ей воспользоваться, и о том, почему вы до сих пор не пишете на Prolog.
▍Какие современные задачи можно успешно решать, используя Prolog?
Я вполне понимаю то, насколько бесполезным всё это может выглядеть, например, для человека, который занимается фронтенд-разработкой, или для того, кто создаёт программы для платформы Node.js. Это нормально. Ведь не каждый язык создавался как универсальный, подходящий для решения самых разных задач. Все об этом знают. Но есть одна область, в которой логическое программирование может найти применение и способно очень хорошо себя в ней показать. Это — распознавание шаблонов.
Одной из важнейших задач из сферы искусственного интеллекта является использование шаблонов при обработке естественного языка. Тут Prolog показывает себя во всей красе. И учтите, что технологии искусственного интеллекта применимы и для решения многих других важных задач. Я лишь говорю о том, что Prolog крайне полезен при решении задач определённого вида.
Учитывая это, подумаем о том, где именно Prolog способен принести наибольшую пользу. Где его можно применить? Итак, если вам приходится решать задачи, связанные с логическим программированием в ограничениях, тогда вам, возможно, захочется поближе познакомиться с Prolog. Это, например, задачи, связанные с планированием (которые, если вы ещё не пробовали их решать, весьма сложны), с проверкой цифровых схем, с управлением транспортными потоками.
Если вернуться к технологиям искусственного интеллекта, то Prolog может пригодиться тому, кто занимается задачами из сферы логического программирования с множеством ответов, или из сферы обработки естественных языков. В эту небольшую статью не поместится пример использования Prolog для решения подобных задач, учитывая то, что для понимания этого примера нужны глубокие знания в определённой предметной области, и то, что я не являюсь экспертом в Prolog-программировании. Поэтому я прошу вас поверить мне на слово. А если вас всё это заинтересовало — здесь вы можете найти рассказ об обработке естественных языков с использованием Prolog.
▍Проекты, в которых применяется Prolog
Я собираюсь найти ответ на вопрос о том, где именно используется Prolog, с самого начала работы над статьёй.
Учитывая имеющиеся у меня данные, можно с уверенностью говорить о том, что существуют группы программистов, которые пишут на Prolog, и о том, что об этих группах знают немногие, так как то, чем они занимаются, не представлено некими широко известными проектами. А даже если Prolog-программисты работают над чем-то достаточно популярным, они не кричат об этом на каждом углу, так как на Prolog обычно пишут лишь небольшие части неких систем. Тем не менее, вот — несколько примеров:
Кстати, если поискать по слову «prolog» на GitHub, можно найти около 7000 репозиториев, в описании которых Prolog назван одним из используемых в них языков. Это позволяет сделать вывод о том, что многие пытаются писать на Prolog. Проблема тут, по моему мнению, в том, что многие из тех, кто пробовал Prolog, не довели свои проекты до состояния коммерчески успешных и широко известных (или хотя бы просто «известных») продуктов.
Итоги
Давайте вернёмся к тому, с чего мы начинали. Действительно ли Prolog — это язык, который учат только для того чтобы тут же забыть?
Я совершенно уверен, что это не так. Prolog — это отличный мощный инструмент. Поэтому для того чтобы продуктивно им пользоваться нужно запастись определённым объёмом знаний. А к этому стремятся далеко не все программисты. Писать на этом языке — значит поменять взгляд на решение задач, выйти из привычной сферы ООП и попасть в мир декларативного программирования. Но если так и сделать, если дать этому языку шанс, он может стать одним из самых любимых инструментов того, кто его освоит. Prolog, учитывая ограниченное количество областей, в которых он применяется, способен сильно повлиять на карьеру того, кто знает этот язык.
Лично у меня никогда не возникало возможности использовать Prolog в своей обычной работе. Но я вижу потенциал этого языка, вижу как много задач можно, при правильном подходе, решить с его помощью. Подобных задач, на самом деле, так много, что я время от времени с интересом поглядываю на этот язык.
Что вы думаете о Prolog? Пользовались ли вы им? Собираетесь ли попробовать этот язык?
Что такое пролог и эпилог? Где это применяется?
Значения слов «пролог» и «эпилог» необходимо понимать, готовясь к ЕГЭ по русской и зарубежной литературе. К сожалению, школьникам не всегда удается получить необходимые знания на уроках или из учебника.
Мы постараемся объяснить содержание этих понятий в максимально простой и доступной форме.
Пролог – это слово, заимствованное из греческого языка, где «prologos» обозначает «вступление». Так называется вводная часть литературного или музыкального произведения, в том числе театральной пьесы или музыкально-сценической постановки.
В прологе могут излагаться события, предшествующие основной сюжетной линии произведения, излагается художественное кредо писателя, мотивация написания им данного произведения и т.д. Музыкальный пролог предваряет основную часть пьесы и служит вступлением, предназначенным вызвать интерес слушателей.
Эпилог – слово, также заимствованное из греческого. «Еpilogos» означает «послесловие». Это завершающая часть произведения, которая отделена от основного текста и представляет собой краткое описание дальнейшей судьбы действующих лиц.
Литературоведы различают эпилог и собственно послесловие, которое может содержать отвлеченные рассуждения и обобщения автора, тогда как в эпилоге всего лишь окончательно завершаются сюжетные линии произведения.
В структуре литературного произведения пролог занимает важное место, поскольку подготавливает читателя к восприятию основного содержания книги. 
Пролог, в отличие от предисловия, пишется всегда самим автором, и его содержание может быть любым – от рассуждений на отвлеченные темы и исторических экскурсов до изложения предыстории событий, которые описаны в его произведении либо причин, по которым книга появилась на свет.
Пролог присутствовал еще в античных трагедиях и служил для пояснения фабулы произведения: излагал суть мифа или легенды, легшей в его основу. Литература девятнадцатого столетия значительно расширила функции пролога, а в дальнейшем развила его многочисленные формы. Это и мотивация содержания книги, и побудительные мотивы автора для ее написания, и историческая канва, на которой развивается сюжет.
В современных произведениях пролог нередко представляет собой отрывок, на первый взгляд, не связанный с основным действием и дающий предпосылки к возникновению завязки сюжета, либо вовсе играет концептуальную роль, излагая этические либо философские проблемы, легшие в основу сюжетной линии.
Кроме того, роль пролога сегодня заключается и в том, чтобы возбудить интерес читателя, заставив его приобрести книгу.
Первоначально эпилог был заключительной частью древнегреческой трагедии. Он представлял собой монолог одного из героев, который объяснял зрителям суть произошедших событий и просил публику быть снисходительной к актерам и к поступкам действующих лиц. 
С развитием жанров художественной литературы, в частности, романа, появилась необходимость в изложении краткого пересказа судьбы героев по окончании драматических событий, описанных в романе, жизни их потомков и второстепенных участников драмы.
Эпилог подводит точку под историей, рассказанной автором и удовлетворяет интерес читателей, у которых перипетии сюжета и судеб героев вызывают искренний эмоциональный отклик.
Эпилог не является обязательной частью любого произведения. От послесловия он отличается тем, что пишется обязательно автором книги и содержит только краткое изложение событий, без философских обобщений, морализаторства и прочих отвлеченных рассуждений.
Пролог в музыкальном произведении служит вступительной частью, подготавливающей слушателей и зрителей (если это опера, балет или оперетта) к восприятию основной части произведения.
Музыкальный пролог может исполняться солистом, оркестром или хором. Иногда с течением времени он может приобрести значение отдельного произведения и исполняться самостоятельно.
Эпилог, или раздел, завершающий музыкальное произведение, характерен в основном для музыкально-сценических жанров – оперы, оперетты или балета. 
Характерным примером является эпилог оперы «Иван Сусанин» М.Глинки, который представляет собой массовую сцену оплакивания гибели Сусанина, которое затем переходит в мощный величественный хор – знаменитое «Славься».