Prolog — удивительный язык программирования. Введение в язык логического программирования пролог Язык программирования prolog

Чем же он удивительный? Я знаю пару десятков языков и для меня не проблема изучить еще один новый, я просто уже не вижу необходимости.

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

Пролог - уникален по своей природе, он появился благодаря счастливому совпадению (таинственному устройству мира). Когда-то в 60-х годах очень бурно развивалась теория автоматического доказательства теорем и Робинсоном был предложен алгоритм резолюций, который позволял доказать любую верную теорему (вывести из аксиом) за конечное время (за какое не известно). Как оказалось позже, это наилучшее решение общей задачи, невозможно доказать теорему за ограниченное число операций. Простыми словами, алгоритм представляет собой обход (в общем случае бесконечного) графа в ширину, естественно, что предсказуемость работы алгоритма практически равно 0, соответственно для Языка Программирования - это абсолютно не подходит. И в этот момент Кальмэроу нашел блестящее сужение задачи, благодаря которому доказательство некоторых теорем выглядело как процедурное исполнение программы. Стоит отметить, что класс доказуемых теорем достаточно широк и очень хорошо применим для класса программируемых задач. Вот так в 1972 появился Prolog.

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

Главной чертой Prolog является то, что его можно легко читать, но очень тяжело писать, что принципиально отличается от всех mainstream языков, которые так и говорят писать стало еще легче еще один шаг и можно будет писать на планшете, перетягивая рабочие модули как друзей в Google+ , от этого все мы знаем очень сильно страдает само качество кода. Вроде бы каждая строчка понятна, но как система работает за гранью понимания даже для разработчиков, как говорится наиндусили. Мне кажется во всех книгах по обучению Prolog, делают одну и ту же ошибку, начиная рассказ о фактах, отношениях, запросах и у человека складывается отношение к языку как к Экспертной Системе или Базе Данных. Гораздо важнее научится правильно читать программы и почитать так с десяток:)

Как правильно читать программы на прологе

Понятия

Программа

A:- B_1, B_2. % правило читается как: Если B_1 и B_2, то A
нечетное_простое(Число) :- простое(Число), нечетное(Число).
% Если "Число" - простое и нечетное, то "Число" - нечетное_простое

Как видно имя переменной имеет область видимости - это правило. Математически верно, правило звучит: для любой переменной - «Число», если оно простое и нечетное, то оно простое_нечетное. Аналогично, можно перефразировать так: Если существует «Число», что оно нечетное и простое, то оно нечетно_простое. Поэтому имя переменной очень важно! Если в левой части (до:-) заменить Число на Число2, то правило поменяет смысл: Для любого Число2 и Число, если Число - простое и нечетное, то Число2 - простое нечетное. Получается все числа простые_нечетные! Это самая распространенная ошибка в Прологе.

A:- B_1, B_2. % правило читается как: Если B_1 и B_2, то A нечетное_простое(Число) :- простое(Число), нечетное(Число). % Если "Число" - простое и нечетное, то "Число" - нечетное_простое

Пример - совершенные числа

Для начала формально прочитаем, что означают правила:

1. Если «Ч» - число и для «Ч» и «СуммаДелителей» выполняется условие сумма_делителей_без_числа, проще говоря СуммаДелителей есть сумма делителей числа «Ч», и «Ч» равно «СуммаДелителей», то «Ч» совершенное число.
2. 1 - совершенное число. Правила могут не иметь условий, в этом случае они называются фактами.
3. Всякий объект «О» равен «О». В принципе существует, стандартный предикат "=", но можно вполне заменить на свой.
4. Факт сумма_делителей_без_числа 1 равна 1.
5. Если сумма делителей «Число» до предыдущего числа «Число» равна «Сумма», то это и есть сумма_делителей_без_числа. Таким образом выражается, сумма делителей X меньше либо равных Y, так как X делится на X, поэтому берем Y = X - 1.
6. Далее 3 предиката определяют сумму делителей число меньше либо равных Y (Делитель), 1-й случай Y равное 1, 2-й случай Число делится на Y, тогда сумма_делителей(X, Y) = сумма_делителей(X, Y-1) + Y, и 3-й случай Число не делится на Y, тогда сумма_делителей(X, Y) = сумма_делителей(X, Y-1).

Программа - как набор определений

Данный способ чтения широко применяется, так как позволяет объединять предикаты в однородные группы и помогает понять, в каком же порядке интерпретатор раскручивает предикаты, для того, чтобы
проверить истинность некоторого утверждения. Например, очевидно, что если предикат не имеет ни одного определения, то доказать истинность утверждения с ним невозможно. В примере № 1 не имеет определения предикат «делится_на».

Интересный факт, что в Прологе нет ни циклов, ни присвоения переменных, ни объявления типов, а если вспомнить еще про термы и отсечение, то язык становится алгоритмически полным.

Термы

С точки зрения программирования терм можно объяснить гораздо проще: терм - это объект с набором атрибутов, атрибуты могут быть другими термами или константами или переменными (то есть не определены). Главное отличие, все объекты в Prolog immutable, то есть менять атрибуты в них нельзя, зато есть специальное состояние - переменная.

Пример - целочисленная арифметика

1. Определение свойства нат (натуральное число). 0 - натуральное число, если Число натуральное, то существует объект число(Число), которое тоже является натуральным. Математически терм «число» выражает функцию +1, с точки зрения программирования «число» рекурсивная структура данных, вот ее элементы: число(0), число(число(0)), число(число(число(0))).
2. Отношение плюс - 0 + Число = Число. Если Ч1 + Ч2 = Рез, то (Ч1+1) + Ч2 = (Рез+1).
3. Отношение умножить - 0 * Число = 0. Если Ч1 * Ч2 = Рез и Рез + Ч2 = Рез2, то (Ч1+1) * Ч2 = Рез2.

Как Prolog понимает предикаты и как доказывает утверждения

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

Рассмотрим на примере запроса плюс(0, 0, Результат) :
1. Находим совпадение (своеобразный pattern-matching, резолюция) данного запроса с левой частью одно из правил. Для данного запроса плюс(0, Число, Число). Соотнесем поочередно все аргументы запроса с правилом и получим: 0 = 0, 0 = Число, Результат = Число. В этих уравнениях участвуют 2 переменные (Число и Результат), решив их мы получаем, что Число = Результат = 0. Так как у данного правила нет условий, мы получили ответ на заданный вопрос. Ответ: да и Результат = 0.

Запрос нат(Число) :
1. Находим 1-е совпадение с правилом, правило нат(0), решая уравнения по соответствию, проще говоря находя резолюцию, мы получаем Число = 0. Ответ: да и Число = 0.

Запрос плюс(Результат, 0, число(0)) :
1. Находим резолюцию с правилом плюс(0, Число, Число): Результат = 0, 0 = Число, число(0) = Число, но (!) Число = 0 = число(0) - не возможно так как 0 совпадает число(0). Следовательно ищем резолюцию со следующим правилом.
2. Находим резолюцию с правилом плюс(число(Ч1), Ч2, число(Рез)), получаем число(Ч1) = Результат, Ч2 = 0, число(Рез) = число(0), отсюда Рез = 0. У этого правила, есть условия которые мы должны проверить, учитывая результаты резолюции (значения переменных), плюс(Ч1, Ч2, Рез) -> плюс(Ч1, 0, 0). Запоминаем значение переменных в стеке и формируем новый запрос плюс(Ч1, 0, 0)
3*. Решая запрос плюс(Ч1, 0, 0) находим резолюцию с плюс(0, Число, Число) и получаем Ч1 = 0 и Число = 0.
4. Возвращаемся по стеку к предыдущим переменным Результат = число(Ч1) = число(0). Ответ найден число(0). Соответственно сейчас пролог машина решила уравнение X + 0 = 1.

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

Пример запроса плюс(Число, Число, Число) : ответ да, Число = 0.

Пример запроса плюс(0, 0, 0) : ответ нет, при первой же попытке все резолюции не выполняются.

Пример запроса плюс(Число, Число, число(Число)) : ответ да, Число = 1. Решение уравнения X + X = X + 1.

Попробуйте провести вывод для умножить(Число, число(0), число(0)), для этого потребуется 2 раза заносить в стек переменные и вычислять новый запрос. Суть Пролог машины такова, что вы можете отказаться от 1-го результата, тогда Пролог вернется к предыдущему состоянию и продолжит вычисление. Например запрос нат(Число) , сначала применит 1-е правило и выдаст 0, а затем применит 2-е правило + 1-е правило и выдаст число(0), можно повторить и получить бесконечную последовательность всех натуральных чисел. Другой пример, запрос плюс(Число, число(0), Число2) , будет выдавать последовательность всех пар решения уравнения X + 1 = Y.

Заключение

В следующей статье я бы хотел рассказать, как решаются задачи сортировки, о последовательности переливаний, Miss Manners и другие известные логические задачи. Для тех, кто почувствовал себя неудовлеторенным хочу предложить следующую задачу (решившему первым приз ):
Написать предикат , который бы генерировал, бесконечную последовательность натуральных чисел, начиная с 3. Это должны быть стандартные числа в Прологе, операции над которыми выполняются при помощи предиката is: X is 3 + 1 => X=4.

Язык программирования

Prolog (от “PROgramming in LOGic”) - декларативный язык программирования общего назначения.

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

Стандарт языка дан в ISO/IEC 13211-1 (1995 год).

Prolog — один из старейших и все еще один из наиболее популярных языков логического программирования, хотя он значительно менее популярен, чем основные императивные языки. Он используется в системах обработки естественных языков, исследованиях искусственного интеллекта, экспертных системах, онтологиях и других предметных областях, для которых естественно использование логической парадигмы.

Prolog был создан под влиянием более раннего языка Planner и позаимствовал из него следующие идеи:

• обратный логический вывод (вызов процедур по шаблону, исходя из целей);
• построение структура управляющей логики в виде вычислений с откатами;
• принцип “отрицание как неудача”;
• использование разных имен для разных сущностей и т.д.

Главной парадигмой, реализованной в языке Prolog, является логическое программирование. Как и для большинства старых языков, более поздние реализации, например, Visual Prolog , добавляют в язык более поздние парадигмы, например, объектно-ориентированное или управляемое событиями программирование, иногда даже с элементами императивного стиля.

Prolog использует один тип данных, терм, который бывает нескольких типов:

• атом — имя без особого смысла, используемое для построения составных термов;
• числа и строки такие же, как и в других языках;
• переменная обозначается именем, начинающимся с прописной буквы, и используется как символ-заполнитель для любого другого терма;
• составной терм состоит из атома-функтора, за которым следует несколько аргументов, каждый из которых в свою очередь является атомом.

Программы, написанные на чистом Prolog, описывают отношения между обрабатываемыми сущностями при помощи клауз Хорна. Клауза — это формула вида Голова:- Тело. , которая читается как “чтобы доказать/решить Голову, следует доказать/решить Тело”. Тело клаузы состоит из нескольких предикатов (целей клаузы), скомбинированных с помощью конъюнкции и дизъюнкции. Клаузы с пустым телом называются фактами и эквивалентны клаузам вида Голова:- true. (true — не атом, как в других языках, а встроенный предикат).

Другой важной частью Prolog являются предикаты. Унарные предикаты выражают свойства их аргументов, тогда как предикаты с несколькими аргументами выражают отношения между ними. Ряд встроенных предикатов языка выполняют ту же роль, что и функции в других языках, например, ….

Предикаты с несколькими аргументами могут действовать в нескольких направлениях в зависимости от того, какие из аргументов уже связаны, а какие — нет. Например, ….

Наконец, для того, чтобы быть языком общего назначения, Prolog должен предоставлять ряд сервисных функций, например, процедур ввода/вывода. Они реализованы как предикаты без специального логического смысла, которые всегда оцениваются как истинные и выполняют свои сервисные функции как побочный эффект оценивания.

Целью выполнения программы на Prolog является оценивание одного целевого предиката. Имея этот предикат и набор правил и фактов, заданных в программе, Prolog пытается найти привязки (значения) переменных, при которых целевой предикат принимает значение истинности.

…

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

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

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

Пролог относится к так называемым декларативным языкам, требующим от автора умения составить формальное описание ситуации. Поэтому программа на Прологе не является таковой в традиционном понимании, так как не содержит управляющих конструкций типа if … then, while … do; нет даже оператора присваивания. В Прологе задействованы другие механизмы. Задача описывается в терминах фактов и правил, а поиск решения Пролог берет на себя посредством встроенного механизма логического вывода.

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

Пролог реализован практически для всех известных операционных систем и платформ. В число операционных систем входят OS для мэйнфреймов, всё семейство Unix, Windows, OS для мобильных платформ.

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

Пролог критикуется в первую очередь за свою недостаточную гибкость, отчего решения на обычных языках программирования (типа C++ , Java) в сочетании с базами данных оказываются более технологичными, чем аналогичные решения на Прологе. Негибкость заключается в трудности изучения языка, более высоких требованиях к квалификации программиста на Прологе, трудности отладки программы, неразвитости технологии программирования, плохой контролируемости промежуточных результатов.

Основные вехи развития языка Prolog

Prolog стал воплощением идеи использования логики в качестве языка программирования, которая зародилась в начале 1970-х годов, и само его название является сокращением от слов “programming in logic” (программирование в терминах логики). Первыми исследователями, которые занялись разработкой этой идеи, были Роберт Ковальски (Robert Kowalski) из Эдинбурга (теоретические основы), Маартен ван Эмден (Maarten van Emden) из Эдинбурга (экспериментальная демонстрационная система) и Ален Колмероэ (Alain Colmerauer) из Марселя (реализация). Популяризации языка Prolog во многом способствовала эффективная реализация этого языка в середине 1970-х годов Дэвидом Д. Г. Уорреном (David D.H. Warren) из Эдинбурга. К числу новейших достижений в этой области относятся средства программирования на основе логики ограничений (Constraint Logic Programming - CLP), которые обычно реализуются в составе системы Prolog. Средства CLP показали себя на практике как исключительно гибкий инструмент для решения задач составления расписаний и планирования материально-технического снабжения. А в 1996 году был опубликован официальный стандарт ISO языка Prolog.

Наиболее заметные тенденции в истории развития языка Prolog

В развитии языка Prolog наблюдаются очень интересные тенденции. Этот язык быстро приобрел популярность в Европе как инструмент практического программирования. В Японии вокруг языка Prolog были сосредоточены все разработки компьютеров пятого поколения. С другой стороны, в США этот язык в целом был принят с небольшим опозданием в связи с некоторыми историческими причинами. Одна из них состояла в том, что Соединенные Штаты вначале познакомились с языком Microplanner, который также был близок к идее логического программирования, но неэффективно реализован. Определенная доля низкой популярности Prolog в этой стране объясняется также реакцией на существовавшую вначале “ортодоксальную школу” логического программирования, представители которой настаивали на использовании чистой логики и требовали, чтобы логический подход не был “запятнан” практическими средствами, не относящимися к логике. В прошлом это привело к широкому распространению неверных взглядов на язык Prolog. Например, некоторые считали, что на этом языке можно программировать только рассуждения с выводом от целей к фактам. Но истина заключается в том, что Prolog - универсальный язык программирования и на нем может быть реализован любой алгоритм. Далекая от реальности позиция “ортодоксальной школы” была преодолена практиками языка Prolog, которые приняли более прагматический подход, воспользовавшись плодотворным объединением нового, декларативного подхода с традиционным, процедурным.

Элементы синтаксиса:

Примеры:

Hello, World!:

Visual Prolog создает проекты автоматически. Для запуска примера следует создать новый проект, выбрав “Console” в качестве UI Strategy, перейти к редактированию файла main.pro и заменить его содержимое приведенным кодом.

implement main open core constants className = "main" . classVersion = "" . clauses classInfo (className , classVersion ). clauses run ():- console : : init (), stdio : : write ("Hello, World!" ), programControl:: sleep (1000 ), succeed (). end implement main goal mainExe:: run (main : :run ).

Факториал:

В main.cl добавлена одна строка factorial: (integer N, integer F) procedure (i,o). , которая определяет бинарный предикат factorial с известным первым и неизвестным вторым аргументами. Ключевое слово procedure описывает поведение предиката, указывая, что его вычисление всегда будет успешным и будет найдено ровно одно решение, так что откаты не понадобятся.

В main.pro находится собственно определение нового предиката. Для каждого его вызова есть два возможных соответствия — с нулевым или произвольным первым аргументом. Visual Prolog перебирает формулы в порядке их появления в коде, так что если первый аргумент равен нулю, проверка начинается с первой формулы factorial(0,F) . Первое правило формулы — !, так называемое отсечение, использование которого предотвращает откат ко второй формуле и таким образом обеспечивает наличие ровно одного решения предиката. После этого переменная F, содержащая решение предиката, устанавливается в 1 и выводится на печать. Вторая формула factorial(N,F) рекурсивно вычисляет F1 как факториал N-1, устанавливает решение предиката равным N*F1 и выводит его на печать. Наконец, stdio::nl печатает новую строку.

При выполнении основной программы предикат factorial выполняется ровно один раз, для N=12. С каждым вызовом рекурсии N уменьшается на единицу, пока не становится равным нулю. После этого значения факториалов возвращаются и выводятся на печать в порядке возрастания. Программа обрабатывает только факториалы до 12!, т.к. попытка вычисления 13! вызывает ошибку переполнения целочисленного типа.

% main.cl class main open core predicates classInfo : core : :classInfo . factorial : (integer N , integer F ) procedure (i , o ). predicates run : core : :runnable . end class main % main.pro implement main open core constants className = "main" . classVersion = "" . clauses classInfo (className , classVersion ). factorial (0 , F ) :- !, F = 1 , stdio : : write ("0! = 1" ), stdio : :nl . factorial (N , F ) :- factorial (N - 1 , F1 ), F = N * F1 , stdio : : write (N , "! = " , F ), stdio : :nl . clauses run ():- console : : init (), factorial (12 , F ), programControl:: sleep (1000 ), succeed (). end implement main goal mainExe:: run (main : :run ).

Числа Фибоначчи:

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

Следует отметить отличие реализаций предикатов от примера для факториала: формулы, описывающие начальные условия, задаются для произвольного значения переменной, но вычисляются до конца только в том случае, если первое правило (N<3 или N=1 , соответственно) оценивается как истинное. Кроме того, каждый предикат записан как одна формула, использующая конъюнкцию и дизъюнкцию, а не как набор отдельных формул, использующих только конъюнкцию.

% main.cl class main open core predicates classInfo : core : :classInfo . fibonacci : (integer N , integer F ) procedure (i , o ). loop : (integer N ) procedure (i ). predicates run : core : :runnable . end class main % main.pro implement main open core constants className = "main" . classVersion = "" . clauses classInfo (className , classVersion ). fibonacci (N , F ) :- N < 3 , !, F = 1 ; fibonacci (N - 1 , F1 ), fibonacci (N - 2 , F2 ), F = F1 + F2 . loop (N ) :- ( N = 1 , !, fibonacci (1 , F ); loop (N - 1 ), fibonacci (N , F ) ), stdio : : write (F , ", " ). clauses run ():- console : : init (), loop (16 ), stdio : : write ("..." ), programControl:: sleep (1000 ), succeed (). end implement main goal mainExe:: run (main : :run ).

Hello, World!:

Этот пример не требует загрузки фактов или правил. Запрос выполняется в интерактивном режиме, и его результат выглядит следующим образом:

Hello, World!
yes

Первая строка является собственно выводом предиката write , вторая — результат оценивания запроса.

Следует отметить, что замена одинарных кавычек на двойные выводит строку как массив ASCII-кодов отдельных символов:

| ?- write("Hello, World!").

write ("Hello, World!" ), nl .

Числа Фибоначчи:

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

После этого предикат fib(N,F) определяется рекурсивно, но каждый вызов fib “обернут” в предикат memo , поэтому для каждого значения N fib(N,F) оценивается только один раз. При таком подходе печать вычисленных чисел может производиться сразу после их вычисления, без дополнительного цикла.

% fibonacci.pl :- dynamic (stored / 1 ). memo (Goal ) :- stored (Goal ) -> true ; Goal , assertz (stored (Goal )). fib (1 , 1 ) :- !, write ("1, " ). fib (2 , 1 ) :- !, write ("1, " ). fib (N , F ) :- N1 is N - 1 , memo (fib (N1 , F1 )), N2 is N - 2 , memo (fib (N2 , F2 )), F is F1 + F2 , write (F ), write (", " ). % interactive [ - fibonacci ]. fib (16 , X ), write ("..." ), nl .

Факториал:

Этот пример состоит из двух частей — первую часть кода следует сохранить в файле fact.pl , расположенном в рабочем каталоге Poplog, а вторую — ввести вручную в интерактивном режиме.

[-fact]. загружает базу фактов и правил из этого файла в текущую сессию Poplog (и выводит сообщение fact reconsulted , чтобы обозначить успешность загрузки). Запрос fact(16,X). пытается найти значение X, при котором этот предикат будет оценен как истинный. Вывод, требующийся в примере, будет побочным эффектом оценивания запроса, а основным результатом будет X = 20922789888000 ? . Это означает, что если вы недовольны такой привязкой переменных, вы можете отказаться от нее (введя;), и будет продолжен поиск лучшей привязки.

% fact.pl fact (X , F ) :- ( X = 0 , F = 1 ; Y is X - 1 , fact (Y , Z ), F is X * Z ), write (X ), write ("! = " ), write (F ), nl . % interactive [ - fact ]. fact (16 , X ).

Квадратное уравнение:

Для запуска создайте новый проект с UI Strategy “Console” и замените содержимое файлов main.cl и main.pro приведенным кодом.

В main.cl добавлена одна строка q: () procedure(). . Ключевое слово procedure описывает поведение предиката, указывая, что его вычисление всегда будет успешным и будет найдено ровно одно решение, так что откаты не понадобятся.

В main.pro находится собственно определение нового предиката. Предикат q не принимает аргументов, поскольку читает необходимые данные из stdio . Условное оценивание (конструкция if-then-else) работает точно так же, как в других языках. Единственным отличием является знак отсечения! перед then . Это означает, что как только условие if выполняется, откат уже не потребуется.

Хитрость этого примера в том, что невозможно сразу вычислить дискриминант, как в других языках. Тип данных по умолчанию для переменной D в присвоении D = B*B-4*A*C - uReal , который может хранить только неотрицательные числа.

% main.cl class main open core predicates classInfo : core : :classInfo . q : () procedure (). predicates run : core : :runnable . end class main % main.pro implement main open core constants className = "main" . classVersion = "" . clauses classInfo (className , classVersion ). q () :- stdio : : write ("A = " ), A = stdio : : read (), if (A = 0 ), ! then stdio : : write ("Not a quadratic equation." ), stdio : :nl else stdio : : write ("B = " ), B = stdio : : read (), stdio : : write ("C = " ), C = stdio : : read (), if (B * B = 4 * A * C ), ! then stdio : : writef ("x = %f" , - B / 2 . 0 / A ) elseif (B * B > 4 * A * C ), ! then D = B * B - 4 * A * C , stdio : : writef ("x1 = %f\n" , (- B + math : : sqrt (D )) / 2 . 0 / A ), stdio : : writef ("x2 = %f" , (- B - math : : sqrt (D )) / 2 . 0 / A ) else D = - B * B + 4 * A * C , stdio : : writef ("x1 = (%f, %f)\n" , - B / 2 . 0 / A , math : : sqrt (D ) / 2 . 0 / A ), stdio : : writef ("x2 = (%f, %f)" , - B / 2 . 0 / A , - math : : sqrt (D ) / 2 . 0 / A ) end if end if . clauses run ():- console : : init (), q (), succeed (). end implement main goal mainExe:: run (main : :run ).

Факториал:

Как в GNU Prolog , так и в B-Prolog 12! не помещается в целочисленный тип данных, поэтому все значения после 11! неправильны. В SWI-Prolog переполнения не возникает.

Результат для GNU Prolog: compiling /home/nickolas/Desktop/progopedia/prolog/fact.pl for byte code…
/home/nickolas/Desktop/progopedia/prolog/fact.pl compiled, 3 lines read - 1372 bytes written, 5 ms

Результат для B-Prolog: consulting::fact.pl

`| ?- fact(16,X).

0! = 1
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
9! = 362880
10! = 3628800
11! = 39916800
12! = -57869312
13! = -215430144
14! = 205203456
15! = -143173632
16! = -143294464

X = -143294464 ?`

% fact.pl fact (X , F ) :- ( X = 0 , F = 1 ; Y is X - 1 , fact (Y , Z ), F is X * Z ), write (X ), write ("! = " ), write (F ), nl . % interactive [ fact ]. fact (16 , X ).

Числа Фибоначчи:

Пример почти идентичен примеру для , за исключением синтаксиса подключения файла.

% fibonacci.pl :- dynamic (stored / 1 ). memo (Goal ) :- stored (Goal ) -> true ; Goal , assertz (stored (Goal )). fib (1 , 1 ) :- !, write ("1, " ). fib (2 , 1 ) :- !, write ("1, " ). fib (N , F ) :- N1 is N - 1 , memo (fib (N1 , F1 )), N2 is N - 2 , memo (fib (N2 , F2 )), F is F1 + F2 , write (F ), write (", " ). % interactive [ fibonacci ]. fib (16 , X ), write ("..." ), nl .

Квадратное уравнение:

read_integer — не стандартный предикат, а расширение GNU Prolog, поэтому этот пример не будет работать в других реализациях.

q :- write ("A = " ), read_integer (A ), ( A = 0 , write ("Not a quadratic equation" ); write ("B = " ), read_integer (B ), write ("C = " ), read_integer (C ), D is B * B - 4 * A * C , ( D = 0 , write ("x = " ), X is - B / 2 / A , write (X ); D > 0 , write ("x1 = " ), X1 is (- B + sqrt (D )) / 2 / A , write (X1 ), nl , write ("x2 = " ), X2 is (- B - sqrt (D )) / 2 / A , write (X2 ); R is - B / 2 / A , I is abs (sqrt (- D ) / 2 / A ), write ("x1 = (" ), write (R ), write (", " ), write (I ), write (")" ), nl , write ("x1 = (" ), write (R ), write (", -" ), write (I ), write (")" ) ) ).

Квадратное уравнение:

Числа Фибоначчи:

Числа Фибоначчи вычисляются рекурсивно, при этом используется мемоизация, реализованная при помощи ECLiPSe-специфичного механизма store .

Для организации цикла в предикате main используется специфичная для ECLiPSe итеративная управляющая структура (мета-предикат) for .

:- local store (fibonacci ). fibonacci (1 , 1 ) :- !. fibonacci (2 , 1 ) :- !. fibonacci (N , F ) :- N > 2 , ( % используем сохраненный результат store_get (fibonacci , N , F ), ! ; N1 is N - 1 , N2 is N - 2 , fibonacci (N1 , F1 ), fibonacci (N2 , F2 ), F is F1 + F2 , store_set (fibonacci , N , F ) % сохраняем полученный результат ). main :- ( for (N , 1 , 16 ) do fibonacci (N , F ), write (F ), write (", " ) ), writeln ("..." ).

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

В октябре 1981 года Японское министерство международной торговли и промышленности объявило о создании исследовательской организации - Института по разработке методов создания компьютеров нового поколения (Institute for New Generation Computer Technology Research Center ). Целью данного проекта было создание систем обработки информации, базирующихся на знаниях. Предполагалось, что эти системы будут обеспечивать простоту управления за счет возможности общения с пользователями при помощи естественного языка. Эти системы должны были самообучаться, использовать накапливаемые в памяти знания для решения различного рода задач, предоставлять пользователям экспертные консультации, причем от пользователя не требовалось быть специалистом в информатике. Предполагалось, что человек сможет использовать ЭВМ пятого поколения так же легко, как любые бытовые электроприборы типа телевизора, магнитофона и пылесоса. Вскоре вслед за японским стартовали американский и европейский проекты.

Появление таких систем могло бы изменить технологии за счет использования баз знаний и экспертных систем. Основная суть качественного перехода к пятому поколению ЭВМ заключалась в переходе от обработки данных к обработке знаний. Японцы надеялись, что им удастся не подстраивать мышление человека под принципы функционирования компьютеров, а приблизить работу компьютера к тому, как мыслит человек, отойдя при этом от фон неймановской архитектуры компьютеров. В 1991 году предполагалось создать первый прототип компьютеров пятого поколения.

Теперь уже понятно, что поставленные цели в полной мере так и не были достигнуты, однако этот проект послужил импульсом к развитию нового витка исследований в области искусственного интеллекта и вызвал взрыв интереса к логическому программированию. Так как для эффективной реализации традиционная фон неймановская архитектура не подходила, были созданы специализированные компьютеры логического программирования PSI и PIM .

В качестве основной методологии разработки программных средств для проекта ЭВМ пятого поколения было избрано логическое программирование , ярким представителем которого является язык Пролог . Думается, что и в настоящее время Пролог остается наиболее популярным языком искусственного интеллекта в Японии и Европе (в США, традиционно, более распространен другой язык искусственного интеллекта -язык функционального программирования Лисп ).

Название языка "Пролог" происходит от слов ЛОГическое ПРОграммирование (PROgrammation en LOGique во французском варианте и PROgramming in LOGic - в английском).

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

В истории возникновения и развития языка Пролог можно выделить следующие этапы.

В 1965 году в работе "A machine oriented logic based on the resolution principle", опубликованной в 12 номере журнала " Journal of the ACM ", Дж Робинсон представил метод автоматического поиска доказательства теорем в исчислении предикатов первого порядка, получивший название " принцип резолюции ". Эту работу можно прочитать в переводе: Робинсон Дж. Машинно-ориентированная логика, основанная на принципе резолюции // Кибернетический сборник. - Вып. 7 (1970). На самом деле, идея данного метода была предложена Эрбраном в 1931 году, когда еще не было компьютеров (Herbrand, "Une methode de demonstration ", These, Paris, 1931). Робинсон модифицировал этот метод так, что он стал пригоден для автоматического, компьютерного использования, и, кроме того, разработал эффективный алгоритм унификации, составляющий базис его метода.

В 1973 году " группа искусственного интеллекта" во главе с Аланом Колмероэ создала в Марсельском университете программу, предназначенную для доказательства теорем. Эта программа использовалась при построении систем обработки текстов на естественном языке. Программа доказательства теорем получила название Prolog (от Programmation en Logique). Она и послужила прообразом Пролога. Ходят легенды, что автором этого названия была жена Алана Колмероэ. Программа была написана на Фортране и работала довольно медленно.

Большое значение для развития логического программирования имела работа Роберта Ковальского " Логика предикатов как язык программирования " (Kowalski R. Predicate Logic as Programming Language . IFIP Congress, 1974), в которой он показал, что для того чтобы добиться эффективности, нужно ограничиться использованием множества хорновских дизъюнктов . Кстати, известно, что Ковальский и Колмероэ работали вместе в течение одного лета.

В 1976 г. Ковальский вместе с его коллегой Маартеном ван Эмденом предложил два подхода к прочтению текстов логических программ: процедурный и декларативный. Об этих подходах речь пойдет в третьей лекции.

В 1977 году в Эдинбурге Уоррен и Перейра создали очень эффективный компилятор языка Пролог для ЭВМ DEC–10, который послужил прототипом для многих последующих реализаций Пролога. Что интересно,

И рассмотреть решения простейших задач на Прологе.

Прежде, чем начинать, хотелось бы кратко ответить на злободневные вопросы от хабрачитателей:
- Где реально используется Пролог?
- Такие проекты существуют, некоторые приводились в комментариях к 1-й статье. Важно что, большинство программистов пишут на Прологе не от безвыходности, а от того, что им нравится Пролог. В конце концов Пролог не может использоваться для любой задачи, такой создание UI или манипулирование с файлами.

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

Почему нет сообщества Пролога?
- Оно есть. Такова специфика языка, что он очень полюбился в академической среде (большинство Prolog систем пишутся в различных университетах и наоборот практически любой университет пишет свой Пролог), из-за этого можно сказать страдает и применимость языка. Стоит отметить, что сообщество небольшое, но очень лояльное: практически все известные языки нашли свое отражение в современных языках (Lisp, ML -> F#, Scala; Smalltalk -> Java, Scala (агенты), скриптовые -> Ruby), в отличие от Пролог.

Думаю на этом хватит философских рассуждений и можно приступить к реальным примерам:)

В конце как обычно ожидает задача на приз.

Пример №1 - поиск совершенных чисел

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

Не пытайтесь описать инструкции поиска решения, предположите, что вы уже нашли решение, а ваша задача только проверить, что решение найдено.

Как ни странно, но это стратегия прекрасно работает.
%% Декларативное определение натуральных чисел ints(0). ints(X) :- ints(Y), X is Y + 1. %% Совершенное число - это 1) натуральное число 2) сумма делителей равна числу perfect_number(X) :- ints(X), Y is X - 1, calculatesum_divisors_till(Sum, X, Y), Sum = X. %% Проверка суммы делителей 1-й аргумент Сумма, 2-й - число для которого ищем делители, %% 3-е - число до которого ищем делители calculatesum_divisors_till(0, _NumberToDivide, 0). calculatesum_divisors_till(Sum, NumberToDivide, Till) :- Till > 0, Rem is NumberToDivide mod Till, Rem = 0, Ts is Till - 1, calculatesum_divisors_till(SumPrev, NumberToDivide, Ts), Sum is SumPrev + Till. calculatesum_divisors_till(Sum, NumberToDivide, Till) :- Till > 0, Rem is NumberToDivide mod Till, Rem > 0, Ts is Till - 1, calculatesum_divisors_till(Sum, NumberToDivide, Ts).

Вставляем исходный текст в файл, запускаем интерпретатор и компилируем его (через запрос:-compile("путь_к_файлу/perfect_numbers.pl"). Пишете запрос :- perfect_number(X). и интерпретатор выдает ответ, при нажатии ";" выдает следующий. Обратите внимание запрос может быть :- perfect_number(X), X > 6 . Тогда все ответы будут больше 6. Конечно программа работает не оптимально, сама проверка может быть упрощена с использованием простых делителей, попробуйте.

Пример №2 - генерация перестановок.

Как многие бы сказали обычная рекурсия и чтобы списки не выглядели как-то особенно в Прологе существует синтаксический сахар для них: nil можно записать , t(1, nil) - , t(1, t(2, nil)) - , t(1, Sublist) - , t(1, t(2, Sublist)) - . Рекомендуется пользоваться синтаксическим сахаром для списков, потому как внутреннее название термов может отличаться (чаще всего терм называется ".").
%% 1. результат находится в голове списка (1-й элемент) member(X, ). %% 2. результат не первый элемент, но содержится в хвосте списка после первого элемента member(X, [_| Tail]) :- member(X, Tail).
Вернемся к исходной задаче генерации перестановок. Все прекрасно помнят, что количество перестановок n!, но вот дай эту задачу большинству программистов и все начнут судорожно вспоминать и говорить, что писали это в школе и забыли как делается перебор. В среднем алгоритм появляется после стараний и мучений через минут 20. При знании Пролога этот алгоритм пишется за 2 минуты или не пишется вообще:)

Как же решить на Прологе? Воспользуемся правилом не поиска решения, а проверки, что решение найдено. Предикат perm(Source, Permutation) - где Source исходный список, Permutation - перестановка.

%% Если исходный список пустой то существует одна перестановка пустой список perm(, ). %% 1-й элемент перестановки должен содержаться в исходном списке, %% при чем его надо сразу исключить из оригинального списка, %% остальные элементы должны быть перестановкой перестановкой %% оставшегося оригинального списка perm(Source, ) :- member_list_exclude(Element, Source, SourceExcluded), perm(SourceExcluded, Tail). %% Проверка того, что элемент содержится в списке, а 2-й список является списком без элемента %% Название предиката member_list_exclude соответствует порядку аргументов %% 1-й - элемент, 2-й - список, 3-й - список без элементов member_list_exclude(X, , L). member_list_exclude(X, , ) :- member_list_exclude(X, L, Ls).
Запрос :-perm(, X) генерирует все перестановки. Интересно, что запросы симметричны :-perm(X, ) относительно аргументов, правда данный запрос зависает и чтобы он работал необходимо поменять member_list_exclude и perm местами в perm.

Пример №3 - генерация сочетаний.

Member(X, ). member(X, [_|L]) :- member(X, L). comb(, ). %% Вариант 1: 1-й элемент сочетания содержится в исходном списке comb(, ) :- comb(List, Tail). %% Вариант 2: сочетание является правильным сочетанием хвоста списка, %% то есть 1-й элемент исходного списка не содержится в сочетании comb([_|List], Tail) :- comb(List, Tail).

Пример №4 - сортировка.

Вариант 1. Сортировка наивная : первый элемент отсортированного массива должен быть минимальным, остальные элементы должны быть отсортированы. Первый массив исходный, второй массив отсортированный исходный.

Sort(, ). sort(List, ) :- min_list_exclude(Min, List, Exclude), sort(Exclude, SortRest). %% Рекурсивно исключаем минимальное число, если в списке одно число исключаем его min_list_exclude(M, [M], ). min_list_exclude(Min, , ExcludeRes) :- min_list_exclude(Ms, L, Exclude), find_result(result(M, L), result(Ms, ), result(Min, ExcludeRes)). %% Дополнительный предикат для определения пары с минимальным ключом find_result(result(M, L), result(Ms, _), result(M, L)):- M < Ms. find_result(result(M, _), result(Ms, Exclude), result(Ms, Exclude)):- Ms =< M.
Можно заметить, что сложность данного алгоритма квадратичная и основная проблема в том, что мы каждый раз ищем минимальный элемент, не сохраняя при этом никакой полезной информации.
Отметим также, что мы пытаемся определить, что такое 1-й элемент отсортированного массива.

Вариант 2. Быстрая сортировка. Посмотрим на проблему со второй стороны и попытаемся определить место 1-го элемента списка в отсортированном массиве (применим рекурсию к исходному массиву).

Sort_b(, ). sort_b(, List) :- split(T, R, Less, Great), sort_b(Less, LessSort), sort_b(Great, GreatSort), append(LessSort, , List). %% Разделяем массив на 2 массива больше и меньше split(_, ,, ). split(T, ,, Great) :- M < T, split(T,R, Less,Great). split(T, ,Less, ) :- M >= T, split(T,R, Less,Great). %% Склеиваем 2 списка append(, M, M). append(, Right, ) :- append(Left, Right, Res).
Можно заметить, что мы улучшили результаты сортировки, так как быстрая сортировка заведомо быстрее пузырьковой. Для того, чтобы еще улучшить результаты, мы можем вспомнить сортировку слияниями, которая в любом случае дает O(n lg n), но к сожалению данная сортировка применима только к массивам, а не к связным списка, с которыми мы работаем. Единственный вариант использовать дополнительную структуру данных для хранения - дерево.

Вариант 3. Сортировка с использованием бинарного дерева.

Для данного вида сортировки переведем исходный список в бинарное дерево, а затем, воспользовавшись обходом дерева слева, получим отсортированный массив. Дерево будем представлять рекурсивным термом tree(Object, LeftSubTree, RightSubTree) .
sort_tree(, nil). sort_tree(, Tree) :- sort_tree(L, LTree), plus(X, LTree, Tree). %% Добавление в элемента в дерево plus(X, nil, tree(X, nil, nil)). plus(X, tree(O, L, R), tree(O, ResL, R)) :- O >= X, plus(X, L, ResL). plus(X, tree(O, L, R), tree(O, L, ResR)) :- O < X, plus(X, R, ResR). sort_t(X, Y) :- sort_tree(X, Tree), tree_list(Tree, Y). append_list(, L, L). append_list(, R, ) :- append_list(L, R, T). tree_list(nil, ). tree_list(tree(X, L, R), List) :- tree_list(L, ListL), tree_list(R, ListR), append_list(ListL, , List).

Вариант 4. Сортировка с использованием сбалансированного бинарного дерева.

Проблема использования бинарного дерева такая же как использования быстрой сортировки. Метод не гарантирует оптимальной работы. В случае бинарного дерева, дерево может быть разбалансировано и процедура добавления элемента в него может быть линейна, а не логарифмична. Специально для этого выполняются процедуры балансировки дерева, ниже для ознакомления будет приведен алгоритм с использованием АВЛ-дерева .

Sort_btree(X, Y) :- sort_tree(X, Tree), tree_list(Tree, Y). tree_list(nil, ). tree_list(tree(X, L, R, _), List) :- tree_list(L, ListL), tree_list(R, ListR), append(ListL, , List). sort_tree(, nil). sort_tree(, Tree) :- sort_tree(L, LTree), plus_tree(X, LTree, Tree). construct_tree(A, AL, AR, tree(A, AL, AR, ADepth)) :- diff(AL, AR, _, ADepth). diff(AL, AR, ADiff, ADepth) :- depth_tree(ALs, AL), depth_tree(ARs, AR), ADiff is ALs - ARs, max_int(ALs, ARs, AD), ADepth is AD + 1. max_int(A, B, A) :- A > B. max_int(A, B, B) :- A =< B. append(, L, L). append(, R, ) :- append(L, R, T). depth_tree(0, nil). depth_tree(X, tree(_, _, _, X)). plus_tree(X, nil, tree(X, nil, nil, 1)). plus_tree(X, tree(O, L, R, _), Res) :- O >= X, plus_tree(X, L, ResL), diff(ResL, R, Diff, Dep), balance_tree(tree(O, ResL, R, Dep), Diff, Res). plus_tree(X, tree(O, L, R, _), Res) :- O < X, plus_tree(X, R, ResR), diff(L, ResR, Diff, Dep), balance_tree(tree(O, L, ResR, Dep), Diff, Res). %% No rotations balance_tree(Tree, ADiff, Tree) :- ADiff < 2, ADiff > -2. %% Small right rotation balance_tree(tree(A, tree(B, BL, BR, _), AR, _), ADiff, Result) :- ADiff > 1, diff(BL, BR, BDiff, _), BDiff >= 0, construct_tree(A, BR, AR, ASubTree), construct_tree(B, BL, ASubTree, Result). %% Big right rotation balance_tree(tree(A, tree(B, BL, BR, _), AR, _), ADiff, Result) :- ADiff > 1, diff(BL, BR, BDiff, _), BDiff < 0, BR = tree(C, CL, CR, _), construct_tree(B, BL, CL, BSubTree), construct_tree(A, CR, AR, ASubTree), construct_tree(C, BSubTree, ASubTree, Result). %% Small left rotation balance_tree(tree(A, AL, tree(B, BL, BR, _), _), ADiff, Result) :- ADiff < -1, diff(BL, BR, BDiff, _), BDiff =< 0, construct_tree(A, AL, BL, ASubTree), construct_tree(B, ASubTree, BR, Result). %% Big left rotation balance_tree(tree(A, AL, tree(B, BL, BR, _), _), ADiff, Result) :- ADiff < -1, diff(BL, BR, BDiff, _), BDiff > 0, BL = tree(C, CL, CR, _), construct_tree(B, CR, BR, BSubTree), construct_tree(A, AL, CL, ASubTree), construct_tree(C, ASubTree, BSubTree, Result).
Данный пример не является достаточно выразительным для реализации на Прологе, хотя и дает представление о программах среднего объема. Для тренировки можно реализовать пузырьковую сортировку или сортировку вставками, оставим это на усмотрение читателя.

Пример №5 - Задача о переливаниях.

Прежде чем генерировать различные алгоритмы и пытаться их применить к задаче, давайте сначала перепишем условия в терминах Пролога. Опишем емкость как терм sosud(Id, MaximumCapacity, CurrentCapacity) , состояние системы опишем как список емкостей. Пример . Теперь опишем запрос:

%% solve_pr_wo(InitialState, Goal, Steps). :- solve_pr_wo(, sosud(X, _, 6), Steps).

Обратите внимание, что Goal = sosud(_, _, 6), то есть нам не важно какой емкости сосуд главное чтобы в нем было именно 6 литров.

Теперь когда нам все известно опишем способ проверки решения, считая что шаги заданы в переменной Steps.

%% Для получения состояния не требуется ни одного шага, %% значит один из сосудов находится в списке solve_pr_wo(State, Goal, ) :- member(Goal, State). %% Первый шаг это перелить из Sosud в Sosud2 и получить состояние %% первого сосуда ResSosud, а второго ResSosud2. %% Конкретный пример шага: %% mv(sosud(1, 12, 12) -> sosud(2, 8, 0), sosud(1, 12, 4) -> sosud(2, 8, 8)). solve_pr_wo(State, Goal, ) :- %% В первую очередь проверка домена, что сосуды действительно %% содержатся в текущем состоянии и они не равны друг другу member(Sosud, State), member(Sosud2, State), not(Sosud = Sosud2), %% Осуществление самого переливания, здесь %% участвуют все 4 переменных шага mv(Sosud, Sosud2, ResSosud, ResSosud2), %% Замена состояния сосудов в списке состояний по очереди replace(Sosud, State, ResSosud, State2), replace(Sosud2, State2, ResSosud2, StateX), %% Дальнейшие шаги должны выполняться по рекурсии solve_pr_wo(StateX, Goal, Steps). %% На самом деле обычная замена элемента в списке %% replace(ElementToReplace, InList, ElementToReplaceWith, OutList). replace(S, , X, ). replace(S, , X, ) :- replace(S, L, X, Ls). %% Процедура переливания - 2 варианта %% исходный сосуд будет исчерпан или целевой наполнен %% Опустошение первого сосуда во второй mv(sosud(Id1, Max1, Current), sosud(Id2, Max2, Current2), sosud(Id1, Max1, 0), sosud(Id2, Max2, Current3)) :- Current > < Max2. %% Переливание из первого сосуда до краев второго mv(sosud(Id1, Max1, Current), sosud(Id2, Max2, Current2), sosud(Id1, Max1, Current3), sosud(Id2, Max2, Max2)) :- Current > 0, Current3 is Current2 + Current - Max2, Current3 >= 0.

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

Что же, описание программы написано - можно запустить. Не стоит удивляться программа не заработает, оно попросту зависнет:) Это не так плохо как может показаться, потому что если бы программа не зависла, то она выдала бы правильный ответ. Следует разобраться почему же она зависла и здесь нам на помощь придет понимание как же Пролог разворачивает правила, чтобы найти решение. На самом деле, не надо иметь голову способную запомнить до 10 точек возврата, чтобы понять, что каждый следующий раз когда solve_pr_wo -> вызывает по рекурсии solve_pr_wo, он вызывает 2 предиката member/2, которые всегда выдают одно и то же 1-й и 2-й сосуд (предикат not вызывает backtracking и не позволяет member выбрать 1-й и 1-й сосуд). То есть алгоритм постоянно переливает из 1-го во 2-й и обратно.

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

Полная версия программа с распечаткой состояний и единственным предикатом для вызова solution:

Write_list(). write_list() :- writeln(X), write_list(L). solution:- solve_pr(, sosud(_, _, 6), , Steps), write_list(Steps). replace(S, , X, ). replace(S, , X, ) :- replace(S, L, X, Ls). %% будем считать стратегией переливания не сами шаги, а просто конечные состояния %% зная начальное и конечное состояние, не трудно догадаться, какой шаг был выполнен solve_pr(State, Goal, _, ) :- member(Goal, State). solve_pr(State, Goal, History, ) :- member(Sosud, State), member(Sosud2, State), not(Sosud = Sosud2), mv(Sosud, Sosud2, ResSosud, ResSosud2), replace(Sosud, State, ResSosud, State2), replace(Sosud2, State2, ResSosud2, StateX), %%% та самая проверка конечного состояния not(member(StateX, )), solve_pr(StateX, Goal, , Steps). %% mv(sosud(_Id, Max, Current), sosud(_Id2, Max2, Current2), ...,...). %% Опустошение первого сосуда во второй mv(sosud(Id1, Max1, Current), sosud(Id2, Max2, Current2), sosud(Id1, Max1, 0), sosud(Id2, Max2, Current3)) :- Current > 0, Current3 is Current2 + Current, Current3 =< Max2. %% Переливание из первого сосуда до краев второго mv(sosud(Id1, Max1, Current), sosud(Id2, Max2, Current2), sosud(Id1, Max1, Current3), sosud(Id2, Max2, Max2)) :- Current > 0, Current3 is Current2 + Current - Max2, Current3 >= 0.

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

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

Заключение

Хотелось бы отметить, что задачи рассмотренные в данной статье являются этюдами для программирования на Прологе. Так как большинство из них занимает около 10-15 строк, то программист на Прологе в состоянии воспроизвести их по памяти при достаточном частом порешевании их. А возвращаться к ним обязательно стоит, так как это напоминает об искусстве программирования (точно так же как быстрая сортировка на C). Более сложные и более прикладные задачи для повседневного использования будут рассмотрены позже.

В конце аж 2 задачки на приз :

1. Как известно в функциональном и логическом всячески пытаются избежать программ с side эффектами, оборачивают их в монады, придумывают специальные концепции. Стандартная проблема - это проблема внешнего мира, например, запись данных в файл, невозможно откатить запись в файл или отменить отсылку нескольких байт по сокету, а следовательно бэктрекинг будет работать не совсем корректно. Совет один - не используйте для этих целей Пролог. Но есть такие предикаты, которые очень хороши и специфичны для Пролога, но имеют side effect. Пример assert (asserta, assertz): он добавляет в базу правил (фактов) простое правило (факт). Пример assert(prime(3)) : добавляет факт, что 3 простое число и запрос :-prime(X) , теперь будет выдавать 3, даже при пустой исходной программе.

   Задача : написать декларативную версию assert , то есть при возврате программы по бэктрекингу факт не должен оставаться в памяти, а должен работать как логическое предположение.

   Пример работы : запрос c(X) должен выдавать одно число 4 для следующей программы!
   a(X) :- b(Y), X is Y + 1 . c(X) :- my_assert(b(3)), a(X). c(X) :- b(X).

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

   Задача : дан некоторый одноместный предикат a/1 (в общем случае множество элементов не ограничено, может быть бесконечно), написать предикат subset_a/1, который будет выдавать подмножества, состоящие из элементов множества a.

   Пример : запрос subset_a(X) выдает X = , X = , X = , X = (порядок не важен):
   a(1). a(2). subset_a(X) :- ....?

Спасибо за внимание.

Теги: Добавить метки

Данный урок посвящен базовым понятиям языка Prolog. Так, на уроке будут изучаться основы написания программ на Прологе

Для начала вспомним нормальную форму Бэкуса-Наура (БНФ) , которая была создана для формального описания синтаксиса языков программирования в 1960 году . Ее авторы — Джон Бэкус и Питер Наур.

Итак, в БНФ приняты следующие обозначения:

Символ::= читаемый как «по определению» («это», «есть»). Слева от символа располагается объясняемое понятие, справа — разъясняющая конструкция. Например,

<Имя> ::= <Идентификатор>

Части выражения, используемые для обозначения синтаксической конструкции языка, берутся в угловые скобки; в нашем примере это <Имя> и <Идентификатор> .

Символ | означает логическое «или» и применяется для разделения различных равнозначных альтернативных объяснений определяемого понятия.

Используя данный символ можно, например, определить десятичную цифру:

<цифра> ::= 0|1|2|3|4|5|6|7|8|9

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

Так запись

<Целое число> ::= [-]<Положительное целое число>

говорит о том, что целое число можно объяснить как положительное целое число, перед которым может стоять знак минус (а может и не стоять).

Символ * указывает на то, что стоящая перед ним синтаксическая конструкция может повторяться произвольное количество раз (начиная с ноля и выше). Вместо символа * иногда используются фигурные скобки ({, }), по сути равнозначные ему.

Снова определим положительное целое число, используя нотацию БНФ:

<Положительное целое число> ::= <цифра>[<цифра>]*.

Что означает, что положительное целое число состоит из одной или нескольких цифр.

Структура программы на языке Prolog

Стандартная программа на языке состоит из следующих разделов :

1. Constants

Необязательный раздел определения констант.

2. Domains

Раздел описания доменов (аналогичен описанию типов данных).

В Turbo Prolog можно выделить простые типы данных :
char — символьный тип
integer — целое число
real — вещественное число
string — последовательность символов типа char, которая заключена в кавычки
symbol — последовательность букв латинского алфавита, цифр и знаков подчеркивания, которая начинается со строчной буквы (тогда без кавычек) или заключена в кавычки (тогда можно с прописной буквы)

3. Predicates

Раздел описания предикатов (аналогичен разделу описания процедур и функций); по сути представляет собой шаблон написания фактов в разделе Clauses.

4. Clauses

Утверждения (аналог: тело основной программы).

5. Goal

Целевое утверждение – «цель».

Задание prolog 2_1: Запустите компилятор . Создайте новый файл и наберите код программы, выводящий ответ на вопрос «Любит ли Мэри яблоки?» (ответ true или false). Код представлен ниже:

domains a=symbol predicates likes (a,a) clauses likes (mary,apples).

Перейдите в окно Dialog (меню Run) и введите запрос:

likes(mary,apples)

В результате в окне должен появиться ответ true

Факты и правила

Часто программу, написанную на Прологе, называют базой знаний .

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

Существует два вида предложений: факты и правила .

Предложения-правила имеют вид:

A:- B1,… , Bn.

Где A — это заголовок или голова предложения, а B1,..., Bn – это тело .

Факт обычно утверждает , что между объектами выполнено некоторое отношение и состоит из :

• отношения
• объекта или объектов, заключенных в круглые скобки (аргументы)
• завершается точкой (.)

Пример факта:

likes (bill, dogs).

где likes — факт
bill , dogs — аргументы факта, между которыми выполнено отношение (likes)

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

Таким образом, предикат (факт) может состоять либо только из имени, либо из имени и следующей за ним последовательности параметров (аргументов) , которые заключаются в скобки.

Если факт состоит только из заголовка, то можно сказать, что факт – это предложение, у которого тело пустое .

Аргументом факта или предиката может быть константа , переменная или составной объект; от их числа зависит так называемая местность (n-местность) факта.

Отличие константы от переменной: константа получает свое значение в разделе описания констант , тогда как переменная инициализируется в процессе работы программы .

В TProlog имя предиката или факта может содержать: латинские буквы, цифры, знаки подчеркивания и начинаться с буквы или знака подчеркивания.

В следующем примере наводите курсор на части конструкций, и появится подсказка:

likes (bill, dogs). - Билл любит собак.
bird (vorobej). Птица – воробей.

Таким образом, в примере likes — это имя двухаргументного предиката (факта), у которого строковая константа « bill » является первым аргументом, а « dogs » — вторым аргументом.

Аргументы с известными или постоянными значениями должны начинаться со строчных букв

Задание prolog 2_2: Дано начало программы (раздел domains и predicates) для базы данных «Возраст ребенка» . Составить факты для программы, основываясь на данных указанных разделов и следующих сведений: Ивану 2 года, Алексу 3 года, Марии — 5 лет.

domains a=symbol b=integer predicates age(a,b) clauses age(...,...). ...(...,...). ...(...,...).

Наберите код программы в компиляторе.

Цели

Цель — это формулировка задачи, которую программа должна решить. Цель также служит «триггером» для запуска программы.

Турбо-Пролог использует как , которые содержатся в программе, так и , которые вводятся с клавиатуры после запуска программы. Здесь существует два варианта:

1. Если цель является фактом , то Турбо-Пролог отвечает True (истина) или False (ложь):

goal likes(mary,X).

Дословно: Что любит Мэри?

Важно: Переменные начинаются с прописных букв

Таким образом, цель состоит из взаимосвязанных предикатов. Ее структура точно такая же, как у факта. Т.е. цель зачастую совпадает с правилом или фактом .

Так, наш пример может быть как фактом, так и целью:

likes(mary,apples). — Мэри любит яблоки и Любит ли Мэри яблоки?

Алгоритм составления программы

Программа для компилятора TProlog состоит из разделов, рассмотренных в примере:

clauses likes (mary,apples). likes(mary,oranges). color(apples,red).

goal likes(mary,X),write("mary lyubit ", X).

Результатом примера будет: «mary lyubit apples» .

В данном примере цель записана в виде раздела GOAL прямо в программе, но нужно иметь в виду, что чаще всего цели, требующие логический ответ (правда или ложь), записываются в окне Dialog (goal в программе тогда не пишется)

Бесконечный цикл

В примере, описанном выше, в результате выдается значение только первого из трех фактов:

clauses likes (mary,apples). likes(mary,oranges). color(apples,red). goal likes(mary,X),write("mary lyubit ", X).

Результат выдает только apples . Хотя еще есть oranges.

Чтобы выдать все значения, необходимо организовать бесконечный цикл , который в коде выглядит как оператор fail , установленный в конце раздела GOAL

goal likes(mary,X),write("mary lyubit ", X),nl,fail.

nl — означает переход на следующую строку (каждое значение выводится с новой строки).
Результат:
«mary lyubit apples» .
«mary lyubit oranges» .

Код программы целиком:

domains a=symbol predicates likes (a,a) clauses likes (mary,apples). likes(mary,oranges). color(apples,red). goal likes(mary,X),write("mary lyubit ", X),nl,fail.

Рассмотрим еще один пример.

Пример: Составить базу фактов по стихотворению «Дом, который построил Джек» .
Составить разные запросы к базе данных (выполнить часть запросов в окне Dialog , а другую часть в разделе Goal программы).

Код программы без запросов:

domains a=symbol predicates построил (a,a) хранится (a,a) ворует (a,a) ловит (a,a) треплет (a,a) доит (a,a) бранится (a,a) будят (a,a) clauses построил (джек,дом). хранится (пшеница, чулан_дома). ворует (птица_синица, пшеница). ловит (кот, птица_синица). треплет (кот, птица_синица). треплет (пес, кот). доит (старушка, корова). бранится (пастух, старушка). будят (два_петуха, пастух).

Выполнение запросов в окне dialog:

Построил (Х, дом). /*Кто построил дом?*/

Ответ: Х=Джек

? – ловит (кот, Y) /*Кого ловит кот?*/

Ответ: Y= птица_синица

? – хранится (X, чулан_дома), ворует (X,Y). /*Что хранится в чулане дома и кто ворует это */

Ответ: X = пшеница, Y= птица_синица

Выполнение запросов в разделе Goal:

goal postroil(X,house),write(X),nl,fail.

Задание prolog 2_3:

1. Составить базу данных «Именины и хобби друзей» .

• чьи именины в сентябре?
• когда именины у Ивана?
• кто любит танцы?
• кто любит книги и спорт?
• что любит Петр?

domains a=symbol b=integer predicates birthday(a,b,a) likes(a,a) clauses birthday(nataly, 8, september). birthday(yana, 25, august). birthday(nina, 28, september). birthday(peter, 2, august). birthday(ivan, 12, august). likes(nataly, books). likes(nataly, sport). likes(yana, books). likes(yana, dances). likes(peter, music). likes(peter, dances). likes(ivan, sport). likes(ivan, books). Goal /* birthday(X,Y,september),write(X," rodilas ", Y, " sentyabrya"),nl,fail.*/ … , write(…), nl, fail.

Задание prolog 2_4:

1. Составить базу данных «Предметы и преподаватели» , содержащую информацию о названии предмета, должности и фамилии преподавателя, номер семестра, отчетность.
2. Составить запросы к базе данных, исходя из приведенных ниже:

• по каким предметам экзамен?
• какой предмет и когда читает доцент морозов?
• какая отчетность по тои?
• кто и когда читает ПРЗ?

domains a=symbol b=integer predicates teach(a,a,a,b) vedomost(a,a) clauses teach(prz, assistent,ivanova,2). teach(toi, docent, morozov,4). teach(mpi,docent, petrova, 5). vedomost(toi, exam). vedomost(prz, zach). vedomost(mpi, exam). Goal /* vedomost(X,exam) ,write("exam po predmetu ", X),nl,fail. */ … , write(…), nl, fail.

* Для удобства после выполнения очередного запроса, комментируйте его (/* ... */) и приступайте к написанию кода следующего запроса.

* При использовании материалов обязательна ссылка на