Знакомство сswi/prolog. Запуск простой программы
Знакомство с интерпретатором SWI/PROLOG, включая использование меню, создание программных файлов, запуск и трассировку программ наSWI/PROLOG.
Главное меню
В папке с установленным SWI/PROLOGвойдите в директориюpl/bin, содержащую файлplwin.exe, и запустите его. На экране появится главное меню и главное (диалоговое) окно с приглашениемSWI/PROLOG (см рис.1).
Рис.1Вид диалогового окнаSWI/PROLOG
Главное меню можно сделать активным, нажав F10 илиAlt. Когда главное меню активно, его элементы можно выбрать с помощью клавиш управления курсором (
) и последующим нажатием клавишиEnter. Выбирать элементы главного меню можно также и мышью.
Первая программа
Программа
на Прологе состоит из фактовиправил, которые образуютбазу знанийПролог-программы, изапросак этой базе, который задаетцельпоиска решений.
Предикат
описывают отношение между объектами, которые являются аргументами предиката.
Констатируют наличие заданного предикатом отношения между указанными объектами.
Констатация факта в предложениии
Эллен любит теннис.
в синтаксисе Пролога выглядит так:
Имя предиката(функтора) и объекта должноначинаться с маленькойбуквы и может содержать латинские буквы, кириллицу, цифры и символ подчеркивания (_). Кириллица используется наравне с латинскими буквами. Обычно предикатам дают такие имена, чтобы они отражали смысл отношения. Например:main, add_file_name. Два предиката могут иметь одинаковые имена, тогда система распознает их как разные предикаты, если они имеют различное число аргументов (арность). Например, любит/2, любит/3.
Имя предиката может совпадать с именем какого-либо встроенного предиката SWI/PROLOG-а. Однако, если совпали имена пользовательского и встроенного предиката, то при обращении к нему (либо из интерпретатора, либо из программы), будет вызван пользовательский предикат, т.е. пользовательское определение «перекроет» предопределенное вSWI/PROLOG-е.
Правила
описывают связи между предикатами.
Билл любит все, что любит Том.
в синтаксисе Пролога
Правило B:-Aсоответствует импликацииA→B(«ЕСЛИ A , ТО B»).
В общем виде правило— это конструкция вида:
Предикат P0называетсязаголовком правила, выражениеP1,P2,…,Pn—телом правила, а предикатыPi—подцелями правила.Запятаяозначает логическое «И«.
Факты и правила называются также утверждениямииликлозами. Факт можно рассматривать как правило, имеющее заголовок и пустое тело.
Процедура
— это совокупность утверждений, заголовки которых имеют одинаковый функтор и одну и ту же арность. Процедура задает определение предиката.
Конец предложения всегда отмечается точкой, поэтому все факты, правила и запросы должны заканчиваться точкой. Заметим также, что между именем предиката и скобкой не должно быть пробелов.
Переменная
— поименованная область памяти, где может храниться значение.
Если переменная не связана со значением – она называется свободной переменной.
Унификация
— процесс получения свободной переменной значения в результате сопоставления при логическом выводе в SWI/PROLOG-е.
Понятие переменной в логическом программировании отличается от базового понятия переменной, которое вводится в структурном программировании. Прежде всего, это отличие заключается в том, что переменная в SWI/PROLOG-е, однажды получив свое значение при унификации в процессе работы программы, не может его изменить, т.е. она скорее является аналогом математического понятия «переменная» – неизвестная величина. Переменная вSWI/PROLOGне имеет предопределенного типа данных и может быть связана с значением любого типа данных.
Переменная в SWI/PROLOGобозначается как последовательность латинских букв, кириллицы и цифр, начинающаяся с заглавной буквы или символа подчеркивания ( _ ). Заметим, что если значение аргумента предиката или его имя начинается с заглавной буквы, то оно пишется в апострофах (см. предыдущий пример).
В SWI/PROLOGразличаются строчные и заглавные буквы.
Рассмотрим следующую программу на SWI/PROLOG, которую будем использовать для иллюстрации процессов создания, выполнения и редактирования Пролог-программ.
ПРОГРАММА 1. /* кто что любит */
любит(‘Эллен’,теннис). %Эллен любит теннис
любит(‘Джон’,футбол). %Джон любит футбол
любит(‘Том’,бейсбол). %Том любит бейсбол
любит(‘Эрик’,плавание). %Эрик любит плавание
любит(‘Марк’,теннис). %Марк любит теннис
любит(‘Билл’,X):-любит(‘Том’,X). %Билл любит то, что любит Том
Комментарий в строке программы начинается с символа % и заканчивается концом строки. Блок комментариев выделяется специальными скобками: /* (начало) и */ (конец).
Для того чтобы набрать текст программы воспользуйтесь встроенным текстовым редактором. Чтобы создать новый файл выберете команду File/New, в диалоговом окне укажите имя нового файла, например,тест. Для редактирования уже созданного файла с использованием встроенного редактора можно воспользоваться командой меню File/Edit. Набейте программу 1 (текст программы выше по тексту) и сохраните ее (File/Save buffer).
Внешний вид редактора
Красным цветом подсвечиваются предикаты в заголовках предложений, которые с точки зрения синтаксиса SWI/PROLOGа корректны. Указатель “курсор” можно использовать для выверки (например, корректности) расстановки скобок. Зелёным цветом выделяются комментарии ,темно-красным цветом — переменные. Подчеркиванием выделяются предикаты в теле правила, которые совпадают с предикатом заголовка,- таким образом акцентируется внимание на возможном зацикливании программы.
Чтобы запустить программу, сначала необходимо ее загрузить в SWI/PROLOGдля выполнения. Это делается выбором опцииCompile/Compile bufferиз окна редактора. Результат компиляции отображается в окне интерпретатораSWI/PROLOGа. Там же указываются ошибки, возникшие при компиляции, чаще всего они отображаются и во всплывающем окне ошибок. Обычно перед компиляцией предлагается сохранить файл.
Другой способ загрузить уже существующий файл – это выполнение команды Consultв подменюFileдиалогового окнаSWI/PROLOG. На экране появится диалоговое окно.
Укажите имя файла, который вы хотите загрузить, и выберите Открыть. Если вы попытаетесь загрузить для выполнения файл, в котором есть синтаксические ошибки, то он не загрузится, а вы получите сообщение об ошибке в главном окне. Угловые скобки<< >>будут выделять место, где встретилась ошибка. По умолчанию файлы, ассоциируемые сSWI/PROLOGимеют расширение.pl.
Файлы также можно загрузить, используя встроенный предикат:
consult(Имя файла или имена нескольких файлов).
consult(Test). % test – имя файла
consult([Test1,Test2]). % Загрузка двух файлов.
Для выполнения загрузки этот предикат нужно написать в главном окне после приглашения интерпретатора (?-), которое означает, что интерпретатор ждет запрос.
Запрос
— это конструкция вида:
которая читается «Верно ли P1иP2и . Pn?». ПредикатыPiназываютсяподцелями запроса.
Запрос является способом запуска механизма логического вывода, т.е фактически запускает Пролог-программу.
Для просмотра предложений загруженной базы знаний можно использовать встроенный предикат listing.
Проверьте загрузку исходного файла, задайте запрос
?-любит(‘Билл’,бейсбол). % Любит ли Билл бейсбол?
Получите ответ yes (да) и новое приглашение к запросу.
Введите следующие запросы и посмотрите на результаты.
?-любит(‘Билл’,теннис).%Любит ли Билл теннис?
?-любит(Кто, теннис). %Кто любит теннис?
?-любит(‘Марк’,Что),любит(‘Эллен’,Что).%Что любят Марк и Эллен?
?-любит(Кто, Что). %Кто что любит?
?-любит(Кто, _). %Кто любит?
При поиске решений в базе Пролога выдается первое решение.
Если необходимо продолжить поиск в базе по этому же запросу и получить альтернативные решения, то вводится точка с запятой ;.
Если необходимо прервать выполнение запроса, (например, нужно набрать другой запрос), используйте клавишу b.
Если Вы хотите повторить один из предыдущих запросов, воспользуйтесь клавишами «стрелка вверх» или «стрелка вниз».
Перезагрузить, измененные во внешнем редакторе, файлы можно, используя встроенный предикат make. Например так:
Как работать в SWI Prolog
Если у вас возникают проблемы с пониманием того, как вообще выполняются программ на Prolog — посмотрите статью: Введение в логическое программирование.
В этой статье описан процесс установки SWI Prolog и запуска простой программы в консоли (терминале) с помощью утилицы swipl. Однако, для SWI Prolog есть несколько сред разработки.
Установка SWI Prolog
Я буду устанавливать SWI Prolog на 64х разрядную версию OpenSUSE 42.1. Для установки открываем центр управления Yast:
Выбираем «Управление программным обеспечением». В появившемся окне вводим swipl, в правой части окна появляется соответствующий пакет, нажимаем на него правой кнопкой мыши и выбираем «установить»:
Теперь для работы в среде SWI Prolog можно открыть терминал и ввести команду swipl. Будет запущен интерпретатор, в который можно передавать команды:
Программирование в SWI Prolog
Для присоединения файлов с исходным кодом можно выполнить команду consult(путь к файлу) или [путь к файлу] . Немного удобнее использовать редактор кода (например kate или gedit) со встроенным окном терминала (для этого во многих редакторах есть специальные плагины):
Для работы нужно открыть в редакторе файл исходного кода, в терминале перейти в соответствующий каталог и выполнить в нем команду swipl , присоединить файл исходного кода при помощи consult . Теперь можно передавать интерпретатору команды. В приведенном выше примере, в файле описаны студенты в соответствии с заданием, мы выполняем команду student(Who, Rate) для получения информации обо всех студентах в базе.
В отличии от Visual Prolog, SWI Prolog не выводит сразу все найденные решения. Выводится первое решение, при этом если полученных данных пользователю достаточно, он может ввести точку, а если ему нужны другие решения — то нужно ввести точку с запятой.
Введем в текстовом редакторе программу в соответствии с заданием:
Для обновления данных в интерпретаторе нужно повторно выполнить команду consult.
Разберем предложенную программу:
- предикаты company и student являются фактами (подобно предикату parent из предыдущей работы);
- предикат stipendya принимает имя студента, выполняет поиск студента в базе и получение его среднего балла. Затем выполняется сравнение среднего балла с константой:
- если сравнение проходит успешно, то предикат также завершится успешно и «снаружи» мы получим имя студента, для которого есть стипендия;
- если при сравнении выясняется, что балл студента меньше константы, то предикат завершается неудачей. Никакого результата (информации о студенте, с которым это случилось) «снаружи» мы при этом не получим, но будет запущен механизм поиска с возвратами (интерпретатор попробует подобрать других студентов, соответствующих нашим критериям);
- предикат может завершиться неудачей до выполнения сравнения — если передано имя студента, о котором нет информации в базе (мы просто не сможем получить для него средний балл);
- наконец, если в предикат передана анонимная переменная stipendya(Name) , то будут выведены все студенты, для которых начисляется стипендия.
Чтобы составить запрос относительно получения стипендии студентом Поповым достаточно передать имя студента в качестве аргумента правилу stipendya . При выполнении такого запроса мной были получены ошибки:
.Интерпретатор сообщает, что нет такого предиката в нашей программе. На самом деле, в программе содержится опечатка (имя функции написано неверно). После исправления ошибки и перекомпиляции программы командой [имя файла] или consult(имя файла) ошибка исправлена, получен ответ true , означающий, что студенту Попову положено получать стипендию.
Аналогично выполняется проверка получения стипендии студентом Федоровым (которому стипендия не положена, поэтому выводится false ):
Чтобы получить имена всех студентов, получающих стипендию передадим в качестве аргумента функции stipendiya анонимную переменную:
Чтобы получить минимальный средний балл, необходимый для трудоустройства в Microsoft нужно выполнить запрос company('Microsoft', X) . Во время его выполнения нужная информация будет получена непосредственно из факта company('Microsoft', 5) . Результат:
Чтобы проверить может ли Попов трудоустроиться в Microsoft нужно использовать предикат isAbleToWork :
Чтобы узнать организации, в которые может устроиться на работу Федоров, нужно передать имя студента в isAbleToWork , но в качестве названия компании передать анонимную переменную:
Чтобы получить имена студентов, способных устроиться в Apple, нужно наоборот передать в isAbleToWork имя компании, а вместо имени студента указать переменную без присвоенного заранее значения:
Аналогичный запрос, но с именем компании IBM нужно выполнить для поиска студентов, которые могут трудоустроиться в эту компанию. Результаты отличаются тем, что устроиться может несколько студентов. Для получения всех студентов нужно вводить точку с запятой после каждого результата:
Выводы: во время выполнения работы были получены навыки работы в среде SWI-Prolog Исследован код программы, выданный преподавателем; во время выполнения заданий получены некоторые навыки отладки программ в интерпретаторе SWI-Prolog.
Prolog Language учебник
Начало работы с языком PrologДобавьте PPA ppa:swi-prolog/stable к источникам программного обеспечения вашей системы (разработчики могут выбрать для ppa:swi-prolog/devel ):
Откройте терминал (Ctrl + Alt + T) и введите: sudo add-apt-repository ppa:swi-prolog/stable
Затем обновите информацию о пакете: sudo apt-get update
Теперь установите SWI-Prolog через диспетчер пакетов: sudo apt-get install swi-prolog
Теперь вы можете запустить SWI-Prolog через командную строку с командой swipl
добавление / 3
append/3 является одним из самых известных отношений Prolog. Он определяет связь между тремя аргументами и является истинным, если третий аргумент представляет собой список, который обозначает объединение списков, указанных в первом и втором аргументах.
Примечательно, что, как и для хорошего кода Prolog, append/3 можно использовать в нескольких направлениях : его можно использовать для:
добавьте два полностью или частично созданных списка:
проверьте , верно ли отношение для трех полностью созданных списков:
создать все возможные способы добавления двух списков в данный список:
Ограничения CLP (FD)
Ограничения CLP (FD) предоставляются всеми серьезными реализациями Prolog. Они позволяют нам рассуждать о целых числах чистым способом.
Программирование баз данных
Пролог классифицирует все на:
- Атомы — любая последовательность символов, которые не начинаются с прописного алфавита. Например — a , b , okay
- Числа — для чисел нет специального синтаксиса, объявление не требуется. Например, 1 , 22 , 35.8
- Переменные — строка, начинающаяся с символа верхнего регистра или подчеркивания ( _ ). Например, X , Y , Abc , AA
- Сложные термины — они сделаны из функтора и последовательности аргументов . Имя комплексного члена всегда является атомом, а аргументы могут быть либо атомами, либо переменными. Например, father(john,doe) , relative(a) , mother(X,Y) .
Логическая база данных содержит набор фактов и правил .
Сложный член с атомами в качестве аргументов называется фактом, а сложный член с переменными в качестве аргументов называется правилом.
Пример фактов в Прологе:
Пример правила в Prolog:
Обратите внимание, что ; здесь как оператор or на других языках.
Prolog — это декларативный язык, и вы можете прочитать эту базу данных следующим образом:
Для всех X и Y X является дочерним элементом Y если Y является отцом X или Y является матери X
Фактически, конечный набор фактов и / или правил представляет собой логическую программу .
Использование такой программы демонстрируется путем выполнения запросов . Запросы позволяют извлекать информацию из логической программы.
Чтобы загрузить базу данных в интерпретатор (если вы сохранили базу данных в каталоге, в котором запущен интерпретатор), вы просто вводите:
заменив имя nameofdatabase на фактическое имя файла (обратите внимание, что здесь мы исключаем расширение .pl в имя файла).
Пример запросов в интерпретаторе для программы выше и результатов:
Запросы выше и их ответы можно прочитать следующим образом:
является ли судан ребенком Фреда? — правда
Вот как мы программируем логику в Prolog. Логическая программа более формально: набор аксиом или правил, определяющих отношения (ака предикаты) между объектами. Альтернативный способ интерпретации базы данных выше более формальным логическим способом:
Отношение father_child держится между fred и susan
Отношение mother_child относится к холмику и Джо
Для всех X и Y отношение child_of выполняется между X и Y если отношение father_child выполняется между Y и X , или отношение mother_child выполняется между Y и X
Привет, мир
Привет, Мир в интерактивном интерпретаторе
Чтобы напечатать «Привет, мир!» в интерпретаторе Prolog (здесь мы используем swipl , оболочку для SWI Prolog):
?- это системное приглашение: оно указывает, что система готова для пользователя ввести последовательность целей (т.е. запрос ), которые должны быть прерваны с помощью . (полная остановка).
Здесь запрос write('Hello World!'), nl имеет два цели:
- write('Hello World!') : 'Hello World!' должен отображаться и ( , )
- должна следовать новая строка ( nl ).
write/1 (символ /1 используется, чтобы указать, что предикат принимает один аргумент), а nl/0 — встроенные предикаты (определение предоставляется заранее системой Prolog). Встроенные предикаты предоставляют средства, которые не могут быть получены с помощью чистого определения Prolog или для сохранения программиста от необходимости определять их.
заканчивается на yes что означает, что запрос преуспел. В некоторых системах вместо « yes печатается true .
Привет, Мир из файла
Откройте новый файл hello_world.pl и вставьте следующий текст:
Директива initialization указывает, что цель hello_world, halt следует вызывать, когда файл загружен. halt завершает работу программы.
Затем этот файл можно выполнить с помощью исполняемого файла Prolog. Точные флаги зависят от системы Prolog. Если вы используете SWI Prolog:
Это даст результат Hello, World! , Флаг -q подавляет баннер, который обычно отображается, когда вы вызываете run swipl . Параметр -l указывает файл для загрузки.
Логическое программирование на Prolog для чайников
Prolog — самый популярный язык логического программирования
Узнаем, что такое логическое программирование (ЛП ), и его области применения
Установим самый популярный язык ЛП — 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х битную версию. Установка стандартная. Чтобы ничего не сломать, я решил галочки не снимать. Ради приличия я оставлю скрины установки.
Сайт SWI Prolog — установщики последней стабильной версии 
Галочки не трогаем 
Ищу SWI-Prolog через поиск Windows. Запускаю 
Ура! Теперь и на Windows все работаетОсновы Prolog. Факты, правила, предикаты
Есть утверждения, предикаты:
Марк изучает книгу (учебник, документацию)
Маша видит клавиатуру (мышку, книгу, тетрадь, Марка)
Миша изучает математику (ЛП, документацию, учебник)
Саша старше Лёши
С английского «predicate» означает «логическое утверждение».
Есть объекты: книга, клавиатура, мышка, учебник, документация, тетрадь, математика, ЛП, Марк, Маша, Саша, Даша, Лёша, Миша, да что угодно может быть объектом.
Есть отношения между объектами, т.е то, что связывает объекты. Связь объектов можно выразить через глаголы, например: читать, видеть, изучать. Связь можно выразить через прилагательное. Миша старше Даши. Даша старше Лёши.Получается.. связью может быть любая часть речь? Получается так.Прекрасно! Давайте попробуем запрограммировать эти утверждения на Прологе. Для этого нам нужно:
Создать новый текстовый файл, который я назову simple.pl (.pl — расширение Пролога)
В нем написать простой однострочный код на Прологе
Запустить код с помощью SWI Prolog
Спросить у Пролога этот факт
Запустим. На линуксе это делается таким образом:
На Windows я использую notepad++ для написания кода на Прологе. Я запущу SWI-Prolog и открою файл через consult.
Видим, что он скомпилировал условия. Даже написал «1 clauses», т.е один факт
Что мы сделали? Мы загрузили базу знаний (те, которые мы описали в простом однострочном файле simple.pl) и теперь можем задавать вопросы Прологу. То есть система такая: пишем знания в файле, загружаем эти знания в SWI Prolog и задаем вопросы интерпретатору. Так мы будем решать поставленную задачу. (Даже видно, в начале интерпретатор пишет «?- «. Это означает, что он ждет нашего вопроса
, как великий мистик)Давайте спросим «Марк изучает книгу?» На Прологе это выглядит так:
По сути мы спросили «есть ли факт study(mark, study) в твоей базе?», на что нам Пролог лаконично ответил «true.» и продолжает ждать следующего вопроса. А давайте спросим, «изучает ли Марк документацию?»
Интерпретатор сказал «false.». Это означает, что он не нашел этот факт в своей базе фактов.
Расширим базу фактов. После я определю более строгую терминологию и опишу, что происходит в этом коде.
Сделаю важное замечание для начинающих. Сложность Пролога состоит в специфичной терминологии и в непривычном синтаксисе, в отсутствии императивных фич, вроде привычного присвоения переменных.
Терминология. Объекты данных в Прологе называются термами (предполагаю, от слова «термин»). Термы бывают следующих видов:
Константами. Делятся на числа и атомы. Начинаются с маленькой буквы. Числа: 1,36, 0, -1, 123.4, 0.23E-5. Атомы — это просто символы и строки: a, abc, neOdinSimvol, sTROKa. Если атом состоит из пробела, запятых и тд, то нужно их обрамлять в одинарные кавычки. Пример атома: ‘строка с пробелами, запятыми. Eto kirilicca’.
Переменными. Начинаются с заглавной буквы: X, Y, Z, Peremennaya, Var.
Структурами (сложные термы). Например, study(misha, lp).
Списками. Пример: [X1], [Head|Tail]. Мы разберем их позже в этой статье.
Есть хорошая статья, которая подробно рассказывает про синтаксис и терминологию Пролога. Рекомендую её, чтобы лучше понять понятия Пролог.
Пролог использует методы полного перебора и обход дерева. Во время проверки условий (доказательства утверждений) Пролог заменяет переменные на конкретные значения. Через пару абзацев будут примеры.
study(mark, book). — такие конструкции называются фактами. Они всегда истинны. Если факта в базе знаний нету, то такой факт ложный. Факты нужно оканчивать точкой, так же как утверждения в русском языке.
«Задавать вопросы Прологу» означает попросить Пролог доказать наше утверждение. Пример: ?- study(mark, book). Если наше утверждение всегда истинно, то Пролог напечатает true, если всегда ложно, то false. Если наше утверждение верно при некоторых значениях переменных, то Пролог выведет значения переменных, при которых наше утверждение верно.
Давайте загрузим факты в Пролог и будем задавать вопросы. Давайте узнаем, что изучал 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 < X, X < 5». X меньше 5 И больше 0.
Точка с запятой «;» играет роль логического «ИЛИ». «X < 0; X > 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» использовать » full-width «>
Списки в Прологе отличаются от списков в C/C++, Python и других процедурных языков. Здесь список — это либо пустой элемент; либо один элемент, называемый головой, и присоединенный список — хвост. Список — это рекурсивная структура данных с последовательным доступом.
Списки выглядят так: [],[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, нейросетей. Например, сочинение стихов, анализ речи, поиск пути в графе и так далее.
Я не могу сказать, что логическое программирование не нужно. Оно действительно развивает логическое мышление. Элементы логического программирования можно встретить на практике. И в принципе, логическое программирование — интересная парадагима, которую полезно знать, например, специалистам ИИ.
Что дальше?
Я понимаю, что статью я написал суховато и слишком «логично» (вероятно, влияние Пролога). Я надеюсь, статья вам помогла в изучении основ Логического Программирования на примере Пролога.
(Мои мысли: я часто использую повторения в статье. Это не сочинение, это туториал. Лучше не плодить ненужные синонимы и чаще использовать термины. По крайней мере, в туториалах. Так лучше запоминается. Повторение — мать учения. А как вы считаете?).
Это моя дебютная статья, и я буду очень рад конструктивной критике. Задавайте вопросы, пишите комментарии, я постараюсь отвечать на них. В конце статьи я приведу все ссылки, которые я упоминал и которые мне показались полезными.