Для чего нужен пролог язык программирования
PROLOG для программистов
Язык логического программирования PROLOG (далее – ПРОЛОГ) большинству программистов представляется чем-то запутанным и малопригодным для практического применения. В то же время, Интернет основан на символьной информации, поэтому практически все современные программисты сталкиваются с необходимостью обрабатывать символьные структуры данных, а ведь для этого и предназначен язык логического программирования ПРОЛОГ. Этот язык – идеальный для работы с символьными структурами, текстовыми файлами и для построения интеллектуальных программ.
После многолетней работы с ПРОЛОГом, столкнулся с новомодным Haskell, о котором все авторы гордо говорят – «высокий порог вхождения». По-моему, «высота» этого порога образовалась в результате запутанного синтаксиса и нагромождения встроенных процедур. Еще один источник этой «высоты» — высокомерие авторов многочисленных руководств, которые написаны так, будто читатель никогда программ не писал.
Сразу захотелось назад, к «родному» ПРОЛОГу – простому и понятному. Думаю, если объяснить без нагромождений, типа декларативной семантики, время вхождения в логическое программирование для «обычного» программиста не превысит 30 минут.
Попробую описать его с точки зрения процедурного программирования.
ПРОЛОГ имеет два основных отличия от процедурных языков — способ организации вычислений и способ представления данных. Оба этих аспекта языка коренным образом отличаются от традиционных языков программирования. Но не будем забывать, что логическое программирование реализуется на тех же машинах с фон — Неймановской архитектурой.
Представим себе язык программирования, в котором все операции сводятся к вызову процедур. При этом каждая процедура существует в нескольких вариантах и программа сама выбирает себе правильный, точнее говоря, пригодный для каждого конкретного варианта исходных данных вариант реализации (тело) процедуры. Как определяется пригодность – каждый вызов процедуры, во время исполнения программы, по результатам исполнения процедуры, получает логическое значение – TRUE или FALSE. Совокупность процедур с одинаковым именем и арностью называется предикатом.
Каждый предикат в языке ПРОЛОГ идентифицируется двумя параметрами –именем и арностью – количеством параметров. Например, предикат инвертирования списков идентифицируется, как nrev/2, а предикат соединения списков как append/3. Никакого объявления параметров или переменных не требуется, но можно ограничить параметры паттерном в заголовке процедуры. Например, в одном варианте предиката первый параметр может быть указан как [] – пустой список, в другом – как [A,B,C] – список из трех элементов, а в третьем как [H|T] – произвольный непустой список.
Если какое-то условие в теле процедуры не выполняется, выполнение прекращается и вызов процедуры, точнее говоря, выполнение очередного варианта тела процедуры, прекращается и получает значение FALSE. В этом случае, интерпретатор языка запускает следующий по порядку вариант тела этой процедуры. Если же все варианты оказались непригодными, происходит возврат к предыдущей процедуре и для нее также происходит перебор вариантов, таким образом, вычисление в ПРОЛОГе сводится к обходу дерева вложенности процедур.
Возврат к предыдущему вызову называется бэктрекингом (backtracking). По существу это откат, поскольку все значения, полученные переменными в отмененной процедуре, отменяются. Бэктрекинг – уникальное средство данного языка, не имеющее аналогов ни в одном из других массовых языков программирования. Бэктрекинг обеспечивает полный обход дерева логического вывода, что обеспечивает основу для решения интеллектуальных задач.
Алгоритм интерпретации программы (выполнения цели) в системе ПРОЛОГ.
1. Найти в памяти процедуру по имени p с арностью n.
2. Унифицировать входные параметры цели с заголовком найденной процедуры.
3. Если унификация параметров прошла, выполнить первую цель из тела найденной процедуры.
4. Если унификация не прошла, найти следующий вариант процедуры P/n.
5. Если следующий вариант процедуры P/n не найден, закончить работу с результатом FAIL.
6. Если первая цель выполнилась, перейти к выполнению следующей цели.
7. Если следующая цель не выполнилась, вернуться к предыдущей цели и выполнить следующий вариант ее реализации.
8. Если текущий вариант реализации процедуры P/n не выполнился, перейти к следующему варианту.
9. Если все цели из тела процедуры выполнены, закончить работу с результатом TRUE.
В связи с такой структурой вычислений каждый вызов процедуры называется целью, которая может быть достигнута или нет. Всякое вычисление в ПРОЛОГе имеет логическое значение. Вычисление еще называют поиском вывода (доказательства), а язык ПРОЛОГ – языком логического программирования.
Наверное, синтаксически ПРОЛОГ – самый простой среди языков программирования. Основной синтаксической процедурой является предикат – выражение, аналогичное вызову процедуры — имя и список аргументов –
P(x1, …xn). Имена пишем с малой буквы, а переменные – с большой.
Если опустить детали, синтаксис ПРОЛОГа можно описать следующим образом:
Проверка связи списков:
Здесь символ “;” означает запрос другого варианта решения путем запуска бэктрекинга.
В ПРОЛОГе принято различать вычисления с бэктрекингом (недетерминированные) и без него (детерминированные).
Пример недетерминированного предиката: Решение числовой головоломки.
/*
D O N A L D
+
G E R A L D
— R O B E R T */
sum1(L1,L2,L3,L11,L12,L13,Ii,Lv):-
dl(L11,L111,E1),
dl(L12,L121,E2),
dl(L13,L131,E3),
val(E1,Lv,Lv1),val(E2,Lv1,Lv2),val(E3,Lv2,Lv3),
sd(E1,E2,E3,Ii,Io),
sum1(L1,L2,L3,L111,L121,L131,Io,Lv3).
sd(A,B,C,Ii,Io):-
C1 is A+B+Ii,
C is C1 mod 10,
Io is C1 // 10.
s:-
A1=[D, O, N, A, L, D],
A2=[G, E, R, A, L, D],
A3=[R, O, B, E, R, T],
sum(A1,A2,A3),
write(A1),nl,
write(A2),nl,
write(A3),nl.
Предикат sum/3 выполняет основную операцию подбора значений цифр для заданной буквенной формулы. Вычисление проводится для формулы сложения двух чисел любой длины. При наличии известных цифр можно их вставлять вместо переменных. Если длина слагаемых различна, можно вставить нули в начале соответствующего списка.
Предикат sum1/8 использует первые три аргумента для записи результата, аргументы под номером 4,5,6 – в качестве рабочих переменных, седьмой аргумент – начальное значение разряда переноса, восьмой аргумент – список допустимых значений цифр.
Предикат dl/3 выполняет выбор и удаление последнего элемента из списка переменных.
Предикат val/3 выбирает допустимое значение из списка оставшихся вариантов, при этом выбранный вариант цифры, удаляется из списка допустимых вариантов.
Если вариант значения для очередной буквы устанавливался ранее, то он остается без изменений.
Предикат sd/5 проверяет вариант заданной тройки цифр одного столбца:
Если sd/5 не выполняется, возникает бэктрекинг — последний из вызовов предиката val/3 присваивает новое значение переменной E3. Если ни одно из значений E3 не подошло, бэктрекинг продолжается на шаг назад — для E2 выбирается новое значение, затем – если не подойдет ни один вариант E3 E2, для E1.
Предикат sum1/8 выполняется рекурсивно до исчерпания входного списка переменных.
Предикат s/0 – пример вызова предиката sum/3 для решения одного варианта головоломки.
Как видно из примера, программа на ПРОЛОГе может быть очень компактной, при этом алгоритм прост и прозрачен, поскольку никакие неявные вызовы функций не используются.
Можно развивать программу решения таких головоломок, например, сделать ее универсальной – для всех типов числовых ребусов, улучшить ввод исходных данных.
Для этого надо делать такие операции как лексический и синтаксический анализ. Эти операции рассмотрим во второй части.
Логическое программирование на Prolog для чайников
Узнаем, что такое логическое программирование (ЛП ), и его области применения
Научимся писать простые программы на Prolog
Научимся спискам в Prolog
Разберем преимущества и недостатки Prolog.
Эта статья будет полезна для тех, кто:
Интересуется необычными подходами и расширяет свой кругозор
Начинает изучать Prolog (например, в институте)
В конце статьи я оставлю полезные ссылки. Если у вас останутся вопросы — пишите в комментариях!
Начнем туториал: Пролог для чайников!
Логическое программирование
Существуют разные подходы к программированию. Часто выделяют такие парадигмы программирования:
Императивное (оно же алгоритмическое или процедурное). Самая известная парадигма. Программист четко прописывает последовательность команд, которые должен выполнить процессор. Примеры: C/C++, Java, C#, Python, Golang, машина Тюрьнга, алгоритмы Маркова. Все четко, последовательно как надо. Синоним императивного — приказательное.
Аппликативное (Функциональное). Менее известная, но тоже широко используемая. Примеры языков: Haskell, F#, Лисп. Основывается на математической абстракции лямбда вычислениях. Благодаря чистым функциям очень удобно параллелить такие программы. Чистые функции — функции без побочных эффектов. Если такой функции передавать одни и те же аргументы, то результат всегда будет один и тот же. Такие языки обладают высокой надежностью кода.
И наконец — Декларативное (Логическое). Основывается на автоматическом доказательстве теорем на основе фактов и правил. Примеры языков: Prolog и его диалекты, Mercury. В таких языках мы описываем пространство состояний, в которых сам язык ищет решение к задаче. Мы просто даем ему правила, факты, а потом говорим, что «сочини все возможные стихи из этих слов», «реши логическую задачу», «найди всех братьев, сестер, золовок, свояков в генеалогическом древе», или «раскрась граф наименьшим кол-вом цветов так, что смежные ребра были разного цвета».
Установка Prolog
Существую разные реализации (имплементации) Пролога: SWI Prolog, Visual Prolog, GNU Prolog. Мы установим SWI Prolog.
Установка на Arch Linux:
Установка на Ubuntu:
Prolog работает в режиме интерпретатора. Теперь можем запустить SWI Prolog. Запускать не через swi-prolog, а через swipl:
Теперь поставим на Windows.
Перейдем на официальный сайт на страницу скачивания стабильной версии. Ссылка на скачивание. Клик. Скачаем 64х битную версию. Установка стандартная. Чтобы ничего не сломать, я решил галочки не снимать. Ради приличия я оставлю скрины установки.
Основы Prolog. Факты, правила, предикаты
Есть утверждения, предикаты:
Марк изучает книгу (учебник, документацию)
Маша видит клавиатуру (мышку, книгу, тетрадь, Марка)
Миша изучает математику (ЛП, документацию, учебник)
С английского «predicate» означает «логическое утверждение».
Есть объекты: книга, клавиатура, мышка, учебник, документация, тетрадь, математика, ЛП, Марк, Маша, Саша, Даша, Лёша, Миша, да что угодно может быть объектом.
Есть отношения между объектами, т.е то, что связывает объекты. Связь объектов можно выразить через глаголы, например: читать, видеть, изучать. Связь можно выразить через прилагательное. Миша старше Даши. Даша старше Лёши. Получается.. связью может быть любая часть речь? Получается так.
Прекрасно! Давайте попробуем запрограммировать эти утверждения на Прологе. Для этого нам нужно:
Создать новый текстовый файл, который я назову simple.pl (.pl — расширение Пролога)
В нем написать простой однострочный код на Прологе
Запустить код с помощью SWI Prolog
Спросить у Пролога этот факт
Запустим. На линуксе это делается таким образом:
На Windows я использую notepad++ для написания кода на Прологе. Я запущу SWI-Prolog и открою файл через consult.
Видим, что он скомпилировал условия. Даже написал «1 clauses», т.е один факт
Что мы сделали? Мы загрузили базу знаний (те, которые мы описали в простом однострочном файле simple.pl) и теперь можем задавать вопросы Прологу. То есть система такая: пишем знания в файле, загружаем эти знания в SWI Prolog и задаем вопросы интерпретатору. Так мы будем решать поставленную задачу. (Даже видно, в начале интерпретатор пишет «?- «. Это означает, что он ждет нашего вопроса, как великий мистик)
Давайте спросим «Марк изучает книгу?» На Прологе это выглядит так:
По сути мы спросили «есть ли факт study(mark, study) в твоей базе?», на что нам Пролог лаконично ответил «true.» и продолжает ждать следующего вопроса. А давайте спросим, «изучает ли Марк документацию?»
Интерпретатор сказал «false.». Это означает, что он не нашел этот факт в своей базе фактов.
Расширим базу фактов. После я определю более строгую терминологию и опишу, что происходит в этом коде.
Сделаю важное замечание для начинающих. Сложность Пролога состоит в специфичной терминологии и в непривычном синтаксисе, в отсутствии императивных фич, вроде привычного присвоения переменных.
Терминология. Объекты данных в Прологе называются термами (предполагаю, от слова «термин»). Термы бывают следующих видов:
Переменными. Начинаются с заглавной буквы: X, Y, Z, Peremennaya, Var.
Структурами (сложные термы). Например, study(misha, lp).
Списками. Пример: [X1], [Head|Tail]. Мы разберем их позже в этой статье.
Есть хорошая статья, которая подробно рассказывает про синтаксис и терминологию Пролога. Рекомендую её, чтобы лучше понять понятия Пролог.
Пролог использует методы полного перебора и обход дерева. Во время проверки условий (доказательства утверждений) Пролог заменяет переменные на конкретные значения. Через пару абзацев будут примеры.
study(mark, book). — такие конструкции называются фактами. Они всегда истинны. Если факта в базе знаний нету, то такой факт ложный. Факты нужно оканчивать точкой, так же как утверждения в русском языке.
Давайте загрузим факты в Пролог и будем задавать вопросы. Давайте узнаем, что изучал mark. Для этого нам нужно написать «study(mark, X).» Если мы прожмем «Enter«, то Пролог нам выдаст первое попавшееся решение
Чтобы получить все возможные решения, нужно прожимать точку с запятой «;«.
Можем узнать, кто изучал документацию.
Можно узнать, кто и что изучал!
Пролог проходится по всей базе фактов и находит все такие переменные Who и Object, что предикат study(Who, Object) будет истинным. Пролог перебирает факты и заменяет переменные на конкретные значения. Пролог выведет такие значения переменных, при которых утверждения будут истинными. У нас задача состояла только из фактов, и решение получилось очевидным.
Переменная Who перебирается среди имен mark, misha, а переменная Object среди book, studentbook, docs, lp, math.
Who не может равняться masha, потому что masha ничего не узнала согласно нашей базе фактов. Аналогично Object не может равняться tomuChevoNetuVBaze, так как такого значения не было в базе фактов. Для study на втором месте были только book, studentbook, docs, lp, math.
Короче, я старался понятным языком объяснить метод полного перебора, и что Пролог тупо все перебирает, пока что-то не подойдет. Все просто.
А теперь разберем правила в Прологе. Напишем ещё одну программу old.pl.
older(X,Y) :- older(X, Z), older(Z,Y) — такие конструкции называются правилами. Чтобы из факта получить правило, нужно заменить точку «.» на двоеточие дефис «:-» и написать условие, когда правило будет истинным. Правила истинны только при определенных условиях. Например, это правило будет истинно в случае, когда факты older(X,Z) и older(Z,Y) истинны. Если переформулировать, то получается «X старше Y, если X старше Z и Z старше Y». Если математически: «X > Y, если X > Z и Z > Y».
Запятая «,» в Прологе играет роль логического «И». Пример: «0 5». X меньше 0 ИЛИ больше 5.
Отрицание «not(Какой-нибудь предикат)» играет роль логического «НЕ». «not(X==5)». X НЕ равен 5.
Факты и правила образуют утверждения, предикаты. (хорошая статья про предикаты)
Сперва закомментируйте правило и поспрашивайте Пролог, кто старше кого.
Маша старше Миши. Пролог просто прошелся по фактам и нашел единственное верный факт. Но.. мы хотели узнать «Кого старше Маша?». Логично же, что если Миша старше Саши И Маша старше Миши, то Маша также старше Саши. И Пролог должен решать такие логические задачи. Поэтому нужно добавить правило older(X,Y) :- older(X, Z), older(Z,Y).
Повторим вопрос.
Программа смогла найти все решения. Но что это такое? Ошибка! Стек переполнен! Как вы думаете, с чем это может быть связано? Попробуйте подумать, почему это происходит. Хорошее упражнение — расписать на бумаге алгоритм older(masha,X) так, как будто вы — Пролог. Видите причину ошибки?
Это связано с бесконечной рекурсией. Это частая ошибка, которая возникает в программировании, в частности, на Прологе. older(X, Y) вызывает новый предикат older(X,Z), который в свою очередь вызывает следующий предикат older и так далее.
Нужно как-то остановить зацикливание. Если подумать, зачем нам проверять первый предикат «older(X, Z)» через правила? Если не нашел факт, то значит весь предикат older(X, Y) ложный (подумайте, почему).
Нужно объяснить Прологу, что факты и правила нужно проверять во второй части older(Z, Y), а в первой older(X, Y) — только факты
Нужно объяснить Прологу, что если он в первый раз не смог найти нужный факт, то ему не нужно приступать к правилу. Нам нужно как-то объяснить Прологу, где факт, а где правило.
Это задачу можно решить, добавив к предикатам ещё один аргумент, который будет показывать — это правило или факт.
Наша программа вывела все верные ответы.
Возможно, возникает вопрос: откуда Пролог знает, что изучает Марк и что Миша старше Даши? Как он понимает такие человеческие понятия? Почему ассоциируется study(mark, math) с фразой «Марк изучает математику»? Почему не с «математика изучает Марка»?. Это наше представление. Мы договорились, что пусть первый терм будет обозначать «субъект», сам предикат «взаимосвязь», а второй терм «объект». Мы могли бы воспринимать по-другому. Это просто договеренность о том, как воспринимать предикаты. Пролог позволяет нам абстрактно описать взаимоотношения между термами.
Напишем предикат для нахождения факториала от N.
«is» означает присвоить, т.е N1 будет равняться N-1. Присвоение значений переменным Пролога называется унификацией. «is» работает только для чисел. Чтобы можно было присваивать атомы, нужно вместо «is» использовать «=».
Зададим запросы. Здесь стоит прожимать Enter, чтобы получить первое решение и не попасть в бесконечный цикл.
Можно улучшить, добавив дополнительное условие, что N должно быть больше или равно 0. Тогда наше решение точно не попадет в бесконечный цикл.
В качестве упражнения я предлагаю вам решить такие задачи:
Описать свое генеалогическое древо на предикатах female(X), male(X) и parent(X,Y).
Написать предикат нахождения N числа ряда Фибоначчи.
Описать дерево (граф без циклов) и найти, с какими вершинами связанная заданная вершина.
Списки в Prolog
Списки — важная структура в Прологе. Списки позволяют хранить произвольное количество данных. Связный список — структура данных, состоящая из узлов. Узел содержит данные и ссылку (указатель, связку) на один или два соседних узла. Списки языка Prolog являются односвязными, т.е. каждый узел содержит лишь одну ссылку. Приложу наглядную картинку.
Списки выглядят так: [],[a], [abc, bc], [‘Слово 1’, ‘Слово 2’, 1234], [X], [Head|Tail].
Рассмотрим [Head|Tail]. Это всё список, в котором мы выделяем первый элемент, голову списка, и остальную часть, хвост списка. Чтобы отделить первые элементы от остальной части списка, используется прямая черта «|».
Можно было написать такой список [X1,X2,X3|Tail]. Тогда мы выделим первые три элемента списка и положим их в X1, X2, X3, а остальная часть списка будет в Tail.
В списках хранятся данные, и нам нужно с ними работать. Например, находить минимум, максимум, медиану, среднее, дисперсию. Может нужно найти длину списка, длину самого длинного атома, получить средний балл по N предмету среди студентов группы G. Может нужно проверить, есть ли элемент Elem в списке List. И так далее. Короче, нужно как-то работать со списками. Только предикаты могут обрабатывать списки (да и в целом в Прологе все обрабатывается предикатами).
Напишем предикат для перебора элементов списка, чтобы понять принцип работы списка.
element([Head|Tail],Element) будет истинным, если Element равен Head (первому элементу списка) ИЛИ если предикат element(Tail, Element) истинный. В какой-то момент эта рекурсия окончится. (Вопрос читателю: когда кончится рекурсия? Какое условие будет терминирующим?) Таким образом, предикат будет истинным, если Element будет равен каждому элементу списка [Head|Tail]. Пролог найдет все решения, и мы переберем все элементы списка.
Часто бывает нужным знать длину списка. Напишем предикат для нахождения длины списка. Протестим.
Мой Пролог предупреждает, что была не использована переменная H. Код будет работать, но лучше использовать анонимную переменную _, вместо singleton переменной.
В SWI Prolog имеется встроенный предикат length. Я реализовал аналогичный предикат list_length. Если встречается пустой список, то его длина равна нулю. Иначе отсекается голова списка, рекурсивно определяется длина нового получившегося списка и к результату прибавляется единица.
Чтобы лучше понять алгоритм, пропишите его на бумаге. Последовательно, так, как делает Пролог.
Последняя задача про списки в этой статье, это определить, принадлежит ли элемент списку. Например, 1, 2, 3 и 4 являются элементами списка [1,2,3,4]. Этот предикат мы назовем list_member.
Очевидно, что если список начинается с искомого элемента, то элемент принадлежит списку. В противном случае необходимо отсечь голову списка и рекурсивно проверить наличие элемента в новом получившемся списке.
Преимущества и недостатки Prolog
Пролог удобен в решении задач, в которых мы знаем начальное состояние (объекты и отношения между ними) и в которых нам трудно задать четкий алгоритм поиска решений. То есть чтобы Пролог сам нашел ответ.
Список задач, в которых Пролог удобен:
Компьютерная лингвистика. Написание стихов, анализ речи
Поиск пути в графе. Работа с графами
Знаменитую логическую задачу Эйнштейна можно гораздо легче решить на Прологе, чем на любом другом императивном языке. Одна из вариаций такой задачи:
На улице стоят пять домов. Каждый из пяти домов окрашен в свой цвет, а их жители — разных национальностей, владеют разными животными, пьют разные напитки и имеют разные профессии.
Англичанин живёт в красном доме.
У испанца есть собака.
В зелёном доме пьют кофе.
Зелёный дом стоит сразу справа от белого дома.
Скульптор разводит улиток.
В жёлтом доме живет математик.
В центральном доме пьют молоко.
Норвежец живёт в первом доме.
Сосед поэта держит лису.
В доме по соседству с тем, в котором держат лошадь, живет математик.
Музыкант пьёт апельсиновый сок.
Норвежец живёт рядом с синим домом.
Кто пьёт воду? Кто держит зебру?
Замечание: в утверждении 6 справа означает справа относительно вас.
Научиться решать логические задачи на Пролог, можно по этой статье.
Ещё одна интересная статья. В ней автор пишет программу сочинитель стихов на Prolog.
Интересная задача, которую вы можете решить на Прологе: раскрасить граф наименьшим количеством цветов так, чтобы смежные вершины были разного цвета.
Иллюстрация к задаче
Пролог такой замечательный язык! Но почему его крайне редко используют?
Я вижу две причины:
Альтернативы (например, нейросетей на Python)
Пролог решает задачи методом полного перебора. Следовательно, его сложность растет как O(n!). Конечно, можно использовать отсечения, например, с помощью «!». Но все равно сложность останется факториальной. Простые задачи не так интересны, а сложные лучше реализовать жадным алгоритмом на императивном языке.
Области, для которых предназначен Пролог, могут также успешно решаться с помощью Python, C/C++, C#, Java, нейросетей. Например, сочинение стихов, анализ речи, поиск пути в графе и так далее.
Я не могу сказать, что логическое программирование не нужно. Оно действительно развивает логическое мышление. Элементы логического программирования можно встретить на практике. И в принципе, логическое программирование — интересная парадагима, которую полезно знать, например, специалистам ИИ.
Что дальше?
Я понимаю, что статью я написал суховато и слишком «логично» (вероятно, влияние Пролога). Я надеюсь, статья вам помогла в изучении основ Логического Программирования на примере Пролога.
(Мои мысли: я часто использую повторения в статье. Это не сочинение, это туториал. Лучше не плодить ненужные синонимы и чаще использовать термины. По крайней мере, в туториалах. Так лучше запоминается. Повторение — мать учения. А как вы считаете?).
Это моя дебютная статья, и я буду очень рад конструктивной критике. Задавайте вопросы, пишите комментарии, я постараюсь отвечать на них. В конце статьи я приведу все ссылки, которые я упоминал и которые мне показались полезными.
Статью написал Горохов Михаил, успехов в обучении и в работе!