Как работает пролог машина
Как технически работает Prolog? Что под капотом?
Я хочу узнать больше о внутренностях Prolog и понять, как это работает.
Я знаю, как использовать его. Но не так, как это работает внутри. Как называются алгоритмы и концепции, используемые в Prolog?
вероятно, он строит какую-то древовидную структуру или ориентированный граф объектов, а затем по запросам пересекает этот граф с помощью сложного алгоритма. Возможно, глубинный Поиск. Возможно, есть какой-то исходный код, но было бы здорово прочитать сначала об этом с точки зрения высокого уровня.
Я действительно Новичок в ИИ, и понимание пролога кажется отличным способом начать, имхо. Моя идея-попытаться перестроить что-то подобное и полностью пропустить часть парсера. Мне нужно знать направления, в которых я должен проводить свои исследования.
7 ответов
проверьте также статьи Википедии, чтобы узнать о других областях ИИ.
как называются алгоритмы и концепции, используемые в прологе?
См. Sterling & Shapiro,искусство Пролог (MIT Press) для теории пролога.
вероятно, он строит какую-то древовидную структуру или направленный граф объектов, и тогда на запросы traveres, что график сложный алгоритм. Возможно, глубинный Поиск.
он не строит граф явно, что было бы невозможно даже с бесконечными пространствами поиска. Проверьте первые главы Russell & Norvig концепции пространства состояний поиск. Да, он выполняет поиск глубины с обратным отслеживанием, но нет, это не очень сложно. Это просто очень удобно и программирование альтернативных стратегий поиска не так уж сложно в прологе.
понимание пролога кажется отличным способом начать, имхо.
зависит от того, что вы хотите сделать, но знание пролога, безусловно, не повредит. Это совсем другой взгляд на Программирование. Знание Prolog помогло мне очень быстро понять функциональное программирование.
моя идея-попытаться перестроить что-то подобное и полностью пропустить часть парсера
Вы имеете в виду пропуск синтаксиса пролога? Если вы случайно знакомы со схемой или Lisp, то проверьте раздел 4.4 Abelson & Sussman где они объясняют, как реализовать вариант логического программирования схемы, в схеме.
вы также можете прочитать о Абстрактная Машина Уоррена
как правило, код пролога переводится в инструкции WAM, а затем выполняется более эффективно.
языки программирования: интерпретатор на основе подхода Н. Самуил камень. Книга вышла из печати, но вы можете найти ее в университетской библиотеке. Он содержит реализацию Prolog в Pascal.
Тим Бадд » интерпретаторы Kamin на C++» (в постскриптуме)
презентация в стандарте ISO core не так уж плоха. Каждая управляющая конструкция описывается в виде прецедента прозы со ссылкой на абстрактную машину пролога, состоящую из стека, так далее.. Затем есть изображения, которые показывают стек до и после выполнения конструкции элемента управления.
книга Стерлинга и Шапиро, упомянутые larsmans, на самом деле содержит модели исполнения Пролог. Это довольно приятно и ясно объясняет,»как работает Пролог». И это отличная книга!
есть и другие источники, которые вы можете попробовать. Наиболее примечательно, что некоторые книги Lisp строят педагогически ориентированные интерпретаторы прологов:
из них последний самый ясный (по моему скромному мнению). Однако вам нужно будет изучить некоторый Lisp (либо общий Lisp, либо схему), чтобы понять их.
Prolog использует подмножество логики предикатов первого порядка, называемое логикой Рога. Алгоритм, используемый для получения ответов, называется разрешением SLD.
Алгоритм работы Пролог-машины
А.Л. Машкова
РЕАЛИЗАЦИЯ МЕТОДОВ ИСКУССТВЕННОГО
ИНТЕЛЛЕКТА СРЕДСТВАМИ ЛОГИЧЕСКОГО ПРОГРАММИРОВАНИЯ
МЕТОДИЧЕСКИЕ УКАЗАНИЯ
ПО ВЫПОЛНЕНИЮ ЛАБОРАТОРНЫХ РАБОТ
ОРЕЛ 2015
Рецензент: д.э.н., профессор О.А. Савина
Методические указания предназначены для студентов очной формы обучения. В методических указаниях представлены основные теоретические сведения, необходимые для выполнения лабораторных работ по настоящей дисциплине, приведен порядок выполнения лабораторных работ.
Содержание
1 Лабораторная работа № 1. 4
1.1 Данные и знания. 5
1.2 Синтаксис языка Пролог. 7
1.3 Семантика языка Пролог. 8
1.4 Алгоритм работы Пролог-машины. 9
1.5 Пример построения базы правил на Пролог. 10
1.6 Задание на лабораторную работу. 11
2 Лабораторная работа № 2. 12
2.1 Использование списков в Пролог. 13
2.2 Использование накапливающего параметра. 14
2.3 Управление перебором. 15
2.4 Задание на лабораторную работу. 17
3 Лабораторная работа № 3. 18
3.1 Представление задачи в терминах пространства состояний. 19
3.2 Слепые методы поиска. 19
3.3 Методы эвристического поиска. 20
3.4 Поиск оптимального пути. 23
3.4 Задание на лабораторную работу. 24
4 Лабораторная работа № 4. 25
4.1 Основные понятия теории игр. 26
4.2 Представление игры в матричной форме. 27
4.3 Представление игры в виде игрового дерева. 29
4.4 Задание на лабораторную работу. 30
Лабораторная работа № 1
ПРОДУКЦИОННАЯ МОДЕЛЬ ПРЕДСТАВЛЕНИЯ ЗНАНИЙ
Цель занятия
Ознакомиться с основными принципами представления знаний в продукционной форме и способами их представления на языке Пролог.
Порядок выполнения работы
1 Изучить основные синтаксические и семантические правила в языке Пролог
2 Рассмотреть пример построения базы знаний на Пролог
3 Реализовать базу знаний о родственных отношениях
5 Ответить на контрольные вопросы
Содержание отчета
1 Текст базы фактов и правил
3 Результаты выполнения запросов к базе знаний
Контрольные вопросы
1 Этапы формализации знаний
2 Виды предложений в языке Пролог
3 Декларативный и процедурный смысл правил в языке Пролог
4 Алгоритм работы Пролог-машины
Данные и знания
Параллельно с развитием структуры ЭВМ происходило развитие информационных структур для представления данных. Появились способы описания данных в виде векторов и матриц, возникли списочные структуры, иерархические структуры. В настоящее время в языках программирования высокого уровня используются абстрактные типы данных, структура которых задается программистом. Появление баз данных (БД) знаменовало собой еще один шаг на пути организации работы с декларативной информацией. В базах данных могут одновременно храниться большие объемы информации, а специальные средства, образующие систему управления базами данных (СУБД), позволяют эффективно манипулировать с данными, при необходимости извлекать их из базы данных и записывать их в нужном порядке в базу.
По мере развития исследований в области ИС возникла концепция знаний, которые объединили в себе многие черты процедурной и декларативной информации.Данные – это отдельные факты, характеризующие объекты и процессы предметной области. Знания – это закономерности предметной области, полученные в результате практической деятельности, т.е. основанные на опыте человека. Знания – это хорошо структурированные данные. Знания проходят этапы:
1 – знания в голове человека;
2 – знания на бумажном носителе информации, записанные на естественном языке;
3 – формальные модели представления знаний;
4 – база знаний на машинном носителе информации.
Продукционные правила имеют вид:
Если предпосылки P1… Рт верны, то верны и заключения Q1…Qn. Предпосылки часто называются условиями. Иногда используется и другая терминология, согласно которой предпосылки называются левой частью правила, а действия — правой. Иногда подобные правила записывают в виде условного оператора: if P1… Pm then Q1…Qn.
Продукционная модель представления знаний реализована в языке ЛП Пролог. Она включает факты и правила. Основными понятиями в языке Пролог являются факты, правила логического вывода и запросы, позволяющие описывать базы знаний, процедуры логического вывода и принятия решений. Особую роль в интерпретаторе Пролога играют конкретные запросы к базам знаний, на которые система логического программирования генерирует ответы «истина» и «ложь». Для обобщённых запросов с переменными в качестве аргументов созданная систем Пролог выводит конкретные данные в подтверждение истинности обобщённых сведений и правил вывода. В языке Прологе факты описываются в форме логических предикатов с конкретными значениями. Правила описываются логическими предикатами с определением правил логического вывода в виде списка предикатов над базами знаний и процедурами обработки информации.
Синтаксис языка Пролог
Наименьшие элементы Пролог-программы: Атомы, Числа, Переменные.
Атомы можно записывать тремя способами:
3 – цепочка символов, заключенная в ». Пр. ‘катя’.
Числа в Прологе могут быть целые и вещественные.
Переменные представляются в виде последовательности букв, цифр и _, начинающейся с заглавной буквы. Пр. Х. Особая переменная _ используется в тех местах, где значение нам безразлично.
Пример: имеет_ребенка(Х) :- родитель(Х, _).
Структура – это конструкция Пролог, которая позволяет объединить другие компоненты: атомы, числа, переменные и др. структуры. В последнем случае структура рекурсивная (дерево, список). Количество аргументов структуры называется ее арностью.
Пример: дерево на Пролог узел(а1, а2) или узел(узел(а1,а2), а3)
Все объекты называются термами. Термы входят в состав предикатов (простых предложений). Предикаты обозначают отношения между объектами (не путать со структурами). Предикаты составляют факты, правила и вопросы, структуры являются термами, то есть входят в состав предикатов.
p – предикатный символ.
Из предикатов строятся предложения: факты, правила и вопросы.
Факт – это предикат, после которого ставится точка.
Правила имеют вид: p:-p1, p2,…,pn.
P, p1, p2,…,pn – предикаты
P – заголовок правила
p1, p2,…,pn – тело правила
Факт – это правило, у которого нет тела.
Семантика языка Пролог
Правила в пролог имеют 2 смысла: декларативный и процедурный.
1 – декларативный смысл правила p:-p1, p2,…,pn.
р истинно, если истинны все p1, p2,…,pn.
2 – процедурный смысл правила определяет порядок достижения целей. Если предикат рассматривать как цель, то для достижения цели р нужно последовательно достичь цели p1, p2,…,pn.
Правило можно представить как процедуру р с параметрами t1, t2,…,tm:
Для выполнения процедуры р необходимо выполнить процедуры p1(…), p2(…),…, рn(…).
Вопрос системе можно рассматривать как вызов процедуры.
Алгоритм работы Пролог-машины.
Процедура «Вычислить» получает на входе список целей, на выходе результат: успех или неудача. В случае успеха выдается подстановка. Этот алгоритм в процессе работы просматривает базу фактов и правил и согласует их с целями. Факты можно считать правилами, у которых нет тела.
1. Если список целей пуст, то алгоритм успешно завершает работу.
2. если список не пуст, то запускается процедура «Просмотр». Она просматривает факты и правила (предложения), пока не обнаружит предложение С, голова которого сопоставима с первой целью G1.
3. Если такого предложения найти не удается, то процедура «Просмотр» возвращает неудачу. Если предложение найдено, то оно будет иметь вид H :- B1, B2. Bn. Подходящих предложений может быть несколько, тогда выберет первый. Находим подстановку (пока достаточно знать, что переменная сопоставима с конкретным значением). В списке целей первая цель G1 заменяется телом правила:
B1, B2. Bn, G2,…, Gm. //новый список целей
Если найден факт, то список целей уменьшится, если правило, то такой же по размеру или увеличится.
4. К новому списку целей применяется подстановка. Этот список возвращается процедуре «Вычислить».
5. Если этот список целей приведет к успеху, то и вычисление всей программы будет успешным. Если вычисление списка приведет к неудаче, то и процедура «Просмотр» должна продолжить свою работу: найти еще одно предложение.
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, я решил написать небольшое дополнение к ней в виде 2 небольших задач.
Вот они:
1. Интерпретатор языка brainfuck
2. Машина Тьюринга
Для начала нам требуется SWI-Prolog и немного свободного времени.
Задача 1. Интерпритатор языка brainfuck
Команды и их описание:
Должно выйти что-то вроде этого:
?- run(‘a.txt’).
Hello World!
true.
Задача 2. Машина Тьюринга
Опять немного теории от Вики
Маши́на Тью́ринга (МТ)— абстрактный исполнитель (абстрактная вычислительная машина). Была предложена Аланом Тьюрингом в 1936 году для формализации понятия алгоритма.
Машина Тьюринга является расширением конечного автомата и, согласно тезису Чёрча— Тьюринга, способна имитировать все другие исполнители (с помощью задания правил перехода), каким-либо образом реализующие процесс пошагового вычисления, в котором каждый шаг вычисления достаточно элементарен.
Конкретная машина Тьюринга задаётся перечислением элементов множества букв алфавита A, множества состояний Q и набором правил, по которым работает машина. Они имеют вид: qiaj→qi1aj1dk (если головка находится в состоянии qi, а в обозреваемой ячейке записана буква aj, то головка переходит в состояние qi1, в ячейку вместо aj записывается aj1, головка делает движение dk, которое имеет три варианта: на ячейку влево (L), на ячейку вправо ®, остаться на месте (N)). Для каждой возможной конфигурации имеется ровно одно правило. Правил нет только для заключительного состояния, попав в которое машина останавливается. Кроме того, необходимо указать конечное и начальное состояния, начальную конфигурацию на ленте и расположение головки машины.
Будем использовать МТ предложеную Викой
q0*→q0*R
q01→q01R
q0×→q1×R
q11→q2aR
q21→q21L
q2a→q2aL
q2=→q2=L
q2×→q3×L
q31→q4aR
q3a→q3aL
q3*→q6*R
q4×→q4×R
q4a→q4aR
q4=→q4=R
q41→q41R
q4*→q51R
q5*→q2*L
q6a→q61R
q6×→q7×R
q7a→q7aR
q71→q2aR
q7=→q8=L
q8a→q81L
q8×→q9H
Prolog, введение
Довольно оживленное обсуждение предыдущей стати (http://habrahabr.ru/blogs/programming/47416/) показало, что тема пролога оказалась интересна сообществу.
Чтобы заинтересовать еще более читателя и вместе с тем облегчить ему начало работы с этим языком, я решил написать немного начальных данных о прологе.
Кратко основные особенности.
Сразу нужно сделать важную оговорку. Все переменные (неизвестные) обозначаются с большой буквы.
S = [1055, 1088, 1080, 1074, 1077, 1090, 32, 1084, 1080|. ].
Видно, что строки являются списками кодов символов, т.е. к ним применимы все те же операции что и к спискам, но об этом позже.
Видим, что списки
1) могут быть разнородными (содержать любые комбинации выше- (и ниже-) перечисленных типов)
2) могут быть вложенными
Структура в прологе представляется функтором (имя структуры, то что до скобок) и параметрами (то что в скобках). Число параметров называется арностью функтора.
Как видим, структуры тоже могут быть вложенными.
Последний запрос может быть не совсем понятен, но должен стать понятен в процессе прочтения статьи.
Заметим, что между этими типами существует глубокая связь, например, списки есть ни что иное, как более красивое (синтаксический сахар) применение функтора «.»
Забегая на перед скажем, что так можно разбивать список на голову и хвост
Хотя так никто не делает, в виду того, что для конструирования списков из головы и хвоста (а также обратное преобразование, т.е. разделение списка на голову и хвост) есть более удобный синтаксис вида [H | T].
Tail = [о, с, т, а, л, ь, н, о, е],
List = [голова, о, с, т, а, л, ь, н, о|. ].
В равнозначности синтаксисов можно убедиться запросом
Как видим, тут проявляется на первый взгляд не совсем привычное поведение знака «=», а именно то, что он работает «в обе стороны». И это очень важный момент. Дело в том, что в прологе знак «=» обозначает не обычное (императивное) равенство (присвоение), а унификацию (что в других языках называется сопоставление с образцом), а именно сопоставление левой и правой части и в случае удачного сопоставления конкретизация неизвестных значений.
Фраза может выглядеть немного заумно, легче пояснить на примере.
B = bbb. % удачно + выполнена конкретизация
Разобравшись немного с понятием унификации, становится понятно, почему
Выполнив первую унификацию, пролог система сопоставляет неизвестную A c числом 2. Таким образом вторая унификация будет ни что иное как 2 = 5, т.е. сопоставление чисел 2 и 5 которое конечно же окончится неудачей в виду того что числа не равны. Таким образом, в прологе переменные могут быть конкретизированы только один раз (по этому, например, попытки императивного программирования вида N = N + 1 в прологе не имеют смысла, подобное обычно делается через рекурсию).
Чтобы точно уяснить смысл последнего запроса, нужно еще пояснить смысл функтора «,». Да, не удивляйтесь, «,» это действительно функтор (а именно, инфиксный оператор с арностью 2). В этом можно убедиться, выполнив запросы
здесь противоречий нет, и система просто конкретизирует значения неизвестных.
Однако, мы отвлеклись. Оператор «,» обозначает ни что иное, как логическое «И». Понятно что если мы говорим системе что некоторое число равно 2 и (при этом) оно же равно 5 то мы, очевидно, врем, о чем система нам и сообщает. Для логического «ИЛИ» предусмотрен оператор «;».
Собственно, ответ системы не представляет ничего удивительного. Она ответила ровно то, что мы ей сообщили, а именно, что неизвестное число это либо 2 либо 5.
Впрочем если мы конкретизируем наш запрос (неизвестное число это либо 2 либо 5 и при этом оно четное), то и ответ системы обретет однозначность
тут нас ожидает конфуз. Оказывается, система воспринимает арифметические операции как обычную комбинацию функторов (впрочем наблюдательные могли заметить это выше). Действительно, запрос
показывает что так и есть. Что же тогда делать? Однако, оказывается, есть специальный предикат is/2 (через «/» обычно обозначается арность предиката), который выполняет арифметическое действие.
Пока что мы работали в интерактивном режиме, чтобы «пощупать» пролог на вкус. Обычно же, пролог-программы, как и программы на любом другом языке представляют собой файл с текстом программы. Обычной практикой является загрузка этого файла в интерактивную среду с помощью команды consult(‘file’). (или ее синтаксическим сахаром — [file].) и последующими запросами к программе, т.е. к фактам и предикатам в ней определенным.
Пролог машина, используя описанные выше 2 основных механизма (унификация с конкретизацией + backtracking) вычисляет необходимый результат.
Программа на прологе представляет собой обычно совокупность фактов и предикатов. Подробнее об этих понятиях.
Факт есть некоторое отношение, а точнее сказать экземпляр такого отношения, например
Полезно заметить, что факт — это фактически тоже разновидность предиката, более того вышеприведенные 3 факта woman(. ) могут быть записаны одним предикатом
но все же из соображений выразительности следует применять факты там где это логично.
Запросы к системе, ознакомленной с приведенной программой:
Или так (получить сразу список):
Хотелось бы особо отметить чем предикаты пролога отличаются от функций (методов) императивного языка.
Во-первых, они, в общем случае, могут быть «многовходовыми», что есть прямым следствием свойств рассмотренного понятия унификации, а во-вторых они могут «возвращать одновременно целый набор значений», что есть следствием бэктрекинга (правда, правильнее говорить, что предикат может оставлять несколько точек возврата).
Действительно, рассмотрим тривиальный предикат
этот предикат допускает фактически 3 способа применения:
заметим еще, что этот предикат может быть записан в виде факта:
Более показательный в этом плане пример с предикатом append (сложение списков).
И все это используя только один предикат!
Чтобы подытожить, можно отметить, что программа на прологе представляет собой одновременно базу данных (не реляционную, конечно, но допускающую практически любую функциональную зависимость) (факты) и инфраструктуру запросов к этой базе данных (предикаты), позволяющую построить по данным из базы данных новые отношения, зависимости, или получить некий результат, связанный с данными (впрочем, факты могут и отсутствовать).
При этом сами запросы (предикаты) способны иметь довольно замысловатую логику или даже выполнять вычислительные задачи. Чтобы окончательно повергнуть читателя, добавим, что предикаты способны динамически порождать факты и даже другие предикаты. Отличие от, вероятно, знакомой читателю императивной парадигмы программирования — в декларативной сущности получаемых программ.
Обратная сторона подобной гибкости концепции, разумеется, скорость (о чем справедливо указывали коментаторы предыдущего поста по прологу, впрочем коммерческие реализации пролога обладают довольно недурной производительностью).
Однако соблазнительная сторона такого подхода — возможность чрезвычайно выразительного (пусть, возможно, и не быстрого) решения на прологе задач символьных вычислений, парсинга текста и сложных структур данных (в т.ч. по грамматикам), задачах поиска, экспертных системах, задачах искуственного интеллекта.
Как-то гуляя по просторам сайта рефал-сообщества (еще один интересный язык программирования, местами идейно перекликающийся с прологом), наткнулся на сравнение Refal’а с Java’ой на примере решения конкретной задачи http://wiki.botik.ru/Refaldevel/ForJavaProgrammer (собственно первоисточник — тут http://nuclight.livejournal.com/111696.html ). Для интереса написал решение на прологе (написание заняло
% если равны первый знак патерна и строки, или первый знак паттерна «?»
% то для соответствия должны соответствовать «хвосты» строки и паттерна
matches([ H | T ], [ H1 | T1 ]) :-
и проверка (остальные тест-кейсы опустил из-за того, что очень длинные строки распирают страницу сайта)