Форум   Статьи   Новости   Файлы   Bugtraq   Сниффер   Друзья   О Клубе
  , 13:45   #1
Местный
 
Регистрация: 06.02.2012
Сообщений: 264

Репутация: 2 / 0
Post Prolog

Здравствуйте Юзверы.модераторы и Админ!
Не видел не одной теме о языке пролог.Решил написать статью про язык программирования Prolog.

Что такое Prolog?
развтие языка?
примеры язка.
Приступим.


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

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

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

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



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



Развитие языка

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

В языке существует 2 понятия предикаты (условия) и объекты (они же переменные и термы). Предикаты выражают некоторое условие, например объект зеленый или число простое, естественно что условия имеют входные параметры. Например green_object(Object), prime_number(Number) . Сколько в предикате параметров, такова и арность предиката. Объектами — являются термы, константы и переменные. Константы — это числа и строки, переменные — выражают неизвестный объект, возможно искомый, и обозначаются как строчки с большой буквы. Оставим пока термы и рассмотрим простейшую программу.

Программа

Программа — это набор правил, вида Если условие1 и условие2 и… то верно условие. Формально эти правила объединяются через И, но противоречие получить невозможно, так как в Прологе отсутствует логическое отрицание, а в связке То может присутствовать только один предикат (условие).


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


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

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



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

совершенное_число(Ч) :- число(Ч), сумма_делителей_без_числа(Ч, СуммаДелителей),
равно(СуммаДелителей, Ч).
совершенное_число(1).

равно(Объект, Объект).
сумма_делителей_без_числа(1, 1).
сумма_делителей_без_числа(Число, Сумма) :- число_предыдущее(Число, Предыдущее), сумма_делителей_числа_до_числа(Число, Сумма, Предыдущее).

сумма_делителей_числа_до_числа(Число, 1, 1).
сумма_делителей_числа_до_числа(Число, Сумма, Делитель) :- делится_на(Число, Делитель),
число_предыдущее(Делитель, Предыдущее), сумма_делителей_числа_до_числа(Число, СуммаПред, Предыдущее), сложить(СуммаПред, Делитель, Сумма).
сумма_делителей_числа_до_числа(Число, Сумма, Делитель) :- не_делится_на(Число, Делитель),
число_предыдущее(Делитель, Предыдущее), сумма_делителей_числа_до_числа(Число, Сумма, Предыдущее).




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


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

Существует второй способ прочтения данных правил, менее математический и более естественный, основанный на «определениях». Можно заметить, что в Прологе все правила слева (в части то) содержат только одно условие, что по сути является «определением» это условия.
Например, 1-ое правило определение совершенных чисел. «Ч» совершенное число, когда «Ч» число и сумма делителей «Ч» равна «Ч». Одинаковые предикаты группируются по имени объединяясь условием «или». То есть к определению можно добавить: «Ч» совершенное число, когда .., или когда «Ч» — это 1.

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

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

Термы

Термы имеют рекурсивное определение, как именованная совокупность объектов. Терм = 'имя'(объект, объект, ...), пример person('Name', 'Surname'), '+'(1, 2), person(address('Некоторый адрес'), surname('Фамилия'), phone('Телефон')) . Если рассматривать терм, как математическое понятие, то терм является функцией, а точнее функтором, то есть '+'(1, 2) — означает, что существует такой объект, который равен 1+2. Это абсолютно не означает, что 1+2 = 3, в Прологе — это выражение неистинно, точно так же как и в группе остатков по модулю 2, там 3 вообще не существует. Опять же с математической точки зрения Переменные связываются словом Для Всех, а если в утверждении необходимо слово существует то, для этой цели применяется терм (функтор). Для любого числа существует число-факториал :- factorial(X, fact(X)).

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

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

нат(0).
нат(число(Число)) :- нат(Число).

плюс(0, Число, Число).
плюс(число(Ч1), Ч2, число(Рез)) :- плюс(Ч1, Ч2, Рез).

умножить(0, Число, 0).
умножить(число(Ч1), Ч2, Рез2) :- умножить(Ч1, Ч2, Рез), плюс(Рез, Ч2, Рез2).


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

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

Как 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)):
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.






Элементы синтаксиса:
Комментарий до конца строки %
Регистрозависимость да
Регулярное выражение идентификатора переменной [_A-Z][_a-zA-Z0-9]*
Регулярное выражение идентификатора функции [_a-z][_a-zA-Z0-9]*
Присваивание значения переменной is
Объявление переменной = или :-
Группировка выражений ( ... )
Тождественное равенство ==
Тождественное неравенство \==
Сравнение @< @=< @> @>=
Вызов функции f(a,b,...)
Вызов функции без параметров f
Последовательность ,
Если - то - иначе ( A -> B ; C)
Цикл с постусловием repeat, ..., condition






ПРИМЕРЫ

code:
% Как запускать.
%
% Проверено с GNU Prolog 1.3.1
%
% # gplc --no-top-level gcd.pro
% # ./gcd 22 33 44 121
 
 
% Первое число, второе число, НОД
 
% Верно, что НОД (A, 0) = A
gcd2(A, 0, A).
 
% Верно, что НОД(A, B) = G,
% когда A>0, B>0 и НОД(B, A % B) = G (% - остаток от деления)
gcd2(A, B, G) :- A>0, B>0, N is mod(A, B), gcd2(B, N, G).
 
gcdn(A, [], A).
gcdn(A, [B|Bs], G) :- gcd2(A, B, N), gcdn(N, Bs, G).
gcdn([A|As], G) :- gcdn(A, As, G).
 
:- initialization(main).
 
str2int([], []).
str2int([S|St], [N|Nt]) :- number_atom(N, S), str2int(St, Nt).
 
main :-
    argument_list(Args),
    str2int(Args, Numbers),
    gcdn(Numbers, G),
    write(G), nl.
Факториал:
Пример для версий Visual Prolog 7.2
Для запуска создайте новый проект с UI Strategy “Console” и замените содержимое файлов main.cl и main.pro приведенным кодом.

В 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! вызывает ошибку переполнения целочисленного типа.

code:
% 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).

Кроссплатформенность

Пролог реализован практически для всех известных операционных систем и платформ (в том числе для JAVA и .[COLOR="rgb(65, 105, 225)"]NET[/color]). В число операционных систем входят OS для [COLOR="rgb(65, 105, 225)"]мейнфреймо[/color]в, всё семейство [COLOR="rgb(65, 105, 225)"]Unix[/color], [COLOR="rgb(65, 105, 225)"]Windows[/color], ОС для мобильных платформ.

Архитектура

Многие современные реализации языка имеют внутреннее расширение за счет ООП-архитектуры. Кроме проприетарных решений также существуют свободные реализации Пролог. В 1996 году был принят стандарт ISO, получивший название ISO/IEC JTC1/SC22/WG17.
Базовым принципом языка является равнозначность представления программы и данных (декларативность), отчего утверждения языка одновременно являются и записями, подобными записям в базе данных, и правилами, несущими в себе способы их обработки. Сочетание этих качеств приводит к тому, что по мере работы системы Пролога знания (и данные и правила) накапливаются. Поэтому Пролог-системы считают естественной средой для накопления базы знаний и обучения студентов и школьников.



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

Для этого примера нам понадобится предикат is/2. X is 3 + 1 * 2 — вычисляет выражение справа и заносит в переменную слева, это не присваивание (!), а утверждение что X = 7. Проще говоря фраза X = 7, X = 3 — не имеет решения потому как X не может быть одновременно 7 и 3.
Так же нам понадобится решение задачи из предыдущего топика. Задача была написать предикат, который бы генерировал все натуральные числа подряд, вот решение:
ints(0).
ints(X) :- ints(Y), X is Y + 1.


На самом деле это декларативная версия стандартного предиката integer/1, который проверяет, что аргумент целое число. Проблема стандартного предиката, что он работает правильно для запроса :- integer(1) и не работает для запроса integer(X).

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

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

Как ни странно, но это стратегия прекрасно работает.
%% Декларативное определение натуральных чисел
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 — генерация перестановок.

Для постановки и решения этой задачи нам понадобятся понятие списков. Списки не являются базовым понятиям языка, между списками можно провести прямую аналогию со связными списками в C. Вернемся к определению терма как к рекурсивной структуре данных.
%% Определим пустой список как объект nil
list(nil).
%% Определим список из одного элемента 1
list(t(1, nil)).
%% Определим список из элементов 1, 2, 3
list(t(1, t(2, t(3, nil) ) ) ).

%% Опишем к примеру процедуру поиска в списке
%% 1. результат находится в голове списка (1-й элемент)
%% _ - означает незначимую для нас переменную
member(X, t(Y, _)) :- X = Y.

%% 2. результат не первый элемент, но содержится в хвосте списка после первого элемента
member(X, t(_, Tail)) :- member(X, Tail).



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

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


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

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

%% Если исходный список пустой то существует одна перестановка пустой список
perm([], []).
%% 1-й элемент перестановки должен содержаться в исходном списке,
%% при чем его надо сразу исключить из оригинального списка,
%% остальные элементы должны быть перестановкой перестановкой
%% оставшегося оригинального списка
perm(Source, [Element|Tail]) :- member_list_exclude(Element, Source, SourceExcluded),
perm(SourceExcluded, Tail).

%% Проверка того, что элемент содержится в списке, а 2-й список является списком без элемента
%% Название предиката member_list_exclude соответствует порядку аргументов
%% 1-й - элемент, 2-й - список, 3-й - список без элементов
member_list_exclude(X, [X|L], L).
member_list_exclude(X, [Y|L], [Y|Ls]) :- member_list_exclude(X, L, Ls).


Запрос :-perm([1, 2, 3], X) генерирует все перестановки. Интересно, что запросы симметричны :-perm(X, [1, 2, 3]) относительно аргументов, правда данный запрос зависает и чтобы он работал необходимо поменять member_list_exclude и perm местами в perm.


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

Генерация сочетаний по простоте реализации похожа на генерацию перестановок. Нам понадобится предикат member/2 — принадлежность элемента списку. Предположим у нас есть 2 списка: 1-й исходный список, 2-й — предполагаемое сочетание, необходимо проверить правильность сочетания. Элементы сочетания располагаются в порядке исходного списка.

member(X, [X|_]).
member(X, [_|L]) :- member(X, L).

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

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

Данный пример рассмотрим достаточно подробно и попытаемся провести оптимизацию первичного решения. Процесс написания на Прологе выглядит следующим образом: 1) первичное описание задачи и получение переборного решения 2) логическая оптимизация перестановкой предикатов справа 3) логическая оптимизация введения упрощенных проверок или удаление лишних условий 4) введение эвристик и оптимизация отдельних случаев путем отсечений.

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

sort([], []).
sort(List, [Min|SortRest]) :- min_list_exclude(Min, List, Exclude), sort(Exclude, SortRest).

%% Рекурсивно исключаем минимальное число, если в списке одно число исключаем его
min_list_exclude(M, [M], []).
min_list_exclude(Min, [M|L], ExcludeRes) :- min_list_exclude(Ms, L, Exclude),
find_result(result(M, L), result(Ms, [M|Exclude]), 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([T|R], List) :- split(T, R, Less, Great), sort_b(Less, LessSort), sort_b(Great, GreatSort),
append(LessSort, [T|GreatSort], List).

%% Разделяем массив на 2 массива больше и меньше
split(_, [],[], []).
split(T, [M|R],[M|Less], Great) :- M < T, split(T,R, Less,Great).
split(T, [M|R],Less, [M|Great]) :- M >= T, split(T,R, Less,Great).

%% Склеиваем 2 списка
append([], M, M).
append([L|Left], Right, [L|Res]) :- append(Left, Right, Res).


Можно заметить, что мы улучшили результаты сортировки, так как быстрая сортировка заведомо быстрее пузырьковой. Для того, чтобы еще улучшить результаты, мы можем вспомнить сортировку слияниями, которая в любом случае дает O(n lg n), но к сожалению данная сортировка применима только к массивам, а не к связным списка, с которыми мы работаем. Единственный вариант использовать дополнительную структуру данных для хранения — дерево.

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

Для данного вида сортировки переведем исходный список в бинарное дерево, а затем, воспользовавшись обходом дерева слева, получим отсортированный массив. Дерево будем представлять рекурсивным термом tree(Object, LeftSubTree, RightSubTree).
sort_tree([], nil).
sort_tree([X|L], 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([X|L], R, [X|T]) :- 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, [X|ListR], List).

Существует 4 способа объявления типов данных (доменов);

1. name =d , где name – имена объектов стандартного типа, d – один из типов (char, symbol, integer, real, string)

2. list = element*, где list – список элементов element, element – элемент, лписанный в разделе domains или один из стандартных типов, * - список.

3. num1=f1 (d11, …, d1M); f2 )d21, …, d2N) Тип num1 включает сложные объекты, которые объявляются путем установления пунктора и описаний всех входящих в него компонент. collection = book (author, title) record (artist, album, type). Один оператор раздела domains описысвает только один уровень дерева. books = book (title, author (name, surname)) – неверно.

4. file = name1; name2; … Используется для обращения к файлам по символическим именам. В разделе domains может быть тоько один оператор этого типа. Симолические имена файлов, если их несколько, задаются в качестве альтернативы.

Раздел predicates

Предикат (отношение) – в общем случае эта стуктура выглядит так:

predname (comp1, …, compN), где predname – имя предиката, comp1, …, compN – имя компонент.

domains

fio=string

den, god = integer

mes = symbol

predicates

anketa (fio, den, mes, god)

Если в предикатах испоьзуется только стандартные типы данных, то раздел domains может отсутствовать.

anketa (string, integer, symbol, integer)

Предикат может состоять только из одного имени, то есть не иметь компонент. Допускается многократное объявление предиката с одним и тем же именем. Альтернатива необяазтельно должна иметь одинаковое число компонентов.

Раздел clauses

Здесь размещаются предложения (утверждения). Они представляют собой факт ил правило, соответствующее одному из объявленных предикатов. Факт – простейший вид утверждения, который устанавливает отношения между объектами.

anketa ("Иванов”, 8, august, 1958).

Факт содержит содержит атом anketa, который является именем предиката и в () после него список соответствующих термов, соответствующих компонентам этого предиката. Факт всегда заканчиваетяс точкой. Факт содержит условие, которое являетяс верным. Правило сотоит из заголовка и тела, соединенных символом :- (если). Правила заканчиваются точкой. Заголовок являетяс одним из ранее описанных предикатов, в которых в качестве компонентов может быть переменные. Заголовок правила описывает факт, для определения которого предназначено это правило. Тело правила описывает цель, которая должна быть последовательно согласована с фактом для того, чтобы заголовок правила был истинным. Тело содержит список термов, разделенных запятыми или ; ( :- if) (. and) or).

Переменная означает один и тот же объект только в пределах одного правила.

Раздел goal

Записывается третий тип предложения, состоит из одного или нескольких целевых утверждений, разделенных «,» и оканчивающихся «.». Пролог система, рассматривает вопросы как цели, к которы нужно стремиться . Ответ на вопрос оказывается или положительным или отрицательным в зависимости от того, может быть цель достигнута или нет. Если на вопрос существует несколько ответов, то система может найти и выдать все из них. В разделе goal может быть только один вопрос, на который будет выдано только одно решение. Для получения всех решений можно удалит цель из из программы и задать цель на подсказку ТП в окне. Применение внешних целей бывает полкзно при записи коротких вопросов, а также для получения всег набора допустимых значений.

Пролог-программы, должны содержать как минимум две части:
- predicates - часть для описания структур отношений, используемых в программе, в виде предикатов;
- clauses - часть для определения предикатов в виде набора фактов и правил.

Возьмем, к примеру код программы:
predicates
likes(string, string)
clauses
likes("Ivan", "Maria").
likes("Petr", "Pivo").
likes("Ivan", X) :- likes("Petr", X).


в части predicates описание типов - будут строковые переменные(в нашем случае),
в части clauses наборы фактов и правил, например, Иван и Петр любят пить пиво, и это заключено в строчках
likes("Petr", "Pivo").
likes("Ivan", X) :- likes("Petr", X).

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

Теперь запускаем программу:
пишем в части Goal (правая часть от программы):
Goal: likes(Who, "pivo")

Результат выполнения этого запроса:
Who = Petr
Who = Ivan
2 Solution


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

SWI-Prolog
__________________
amstel.lione@gmail.com

Последний раз редактировалось TDSS; 01.11.2012 в 20:35.
Пользователь вне форума    
Наши Спонсоры
  , 18:29   #2
Продвинутый
 
Аватар для CyberComrade
 
Регистрация: 05.01.2011
Сообщений: 1,579

Репутация: 192 / 3
По умолчанию

Ой! Прологик! Прямо моя молодость на него вся ушла!
__________________
--------------------------------------------------------------------------------------
Пробиваю любую информацио. По всем вопросам ЛС или ICQ 624957418.
--------------------------------------------------------------------------------------
Пользователь вне форума    
  , 18:38   #3
Продвинутый
 
Аватар для BlackH
 
Локация: underworld
Регистрация: 05.12.2011
Сообщений: 1,607

Репутация: 167 / 3
По умолчанию

Ну как кодить на нём,норм?Я вот смотрю на этот код...Блин,муть а не код)
хелворд на нём покажите?
__________________
Вангую..
Пользователь вне форума    
 

 

Часовой пояс GMT +2
Powered by vBulletin® 3.x.x Copyright ©2000 - 2012, Jelsoft Enterprises Ltd.

Copyright © 2008 - 2013 «HPC» Реклама на сайте Правила Форума Пользовательское соглашение Работа на сайте
При копировании материалов ставьте ссылку на источник
Все материалы представлены только в ознакомительных целях, администрация за их использование ответственности не несет.