Язык логического программирования prolog. Введение в язык логического программирования пролог. Управляемые событиями приложения

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

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, которые приняли более прагматический подход, воспользовавшись плодотворным объединением нового, декларативного подхода с традиционным, процедурным.

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

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

Примеры:

Hello, World!:

Пример для версий Visual Prolog 7.2

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 ).

Факториал:

Пример для версий Visual Prolog 7.2

В 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 ).

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

Пример для версий Visual Prolog 7.2

В этом примере определяются два новых предиката — бинарный 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!:

Пример для версий B-Prolog 7.4-3 , ECLiPSe CLP 6.0 #188 , Poplog 15.5 (Prolog) , gprolog 1.3.0 , swipl 5.6.x

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

Hello, World!
yes

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

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

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

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

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

Пример для версий Poplog 15.5 (Prolog)

Простая рекурсивная реализация слишком неэффективна с точки зрения памяти, чтобы успешно выполняться в 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 .

Факториал:

Пример для версий Poplog 15.5 (Prolog)

Этот пример состоит из двух частей — первую часть кода следует сохранить в файле 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 ).

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

Пример для версий Visual Prolog 7.2

Для запуска создайте новый проект с 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 ).

Факториал:

Пример для версий B-Prolog 7.4-3 , gprolog 1.3.0 , swipl 5.6.x

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

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

Пример для версий B-Prolog 7.4-3 , gprolog 1.3.0 , swipl 5.6.x

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

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

Пример для версий gprolog 1.3.0

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 (")" ) ) ).

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

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 ((N , F ) :- N > 0 , N1 is N - 1 , factorial (N1 , F1 ), F is N * F1 . main :- ( for (N , 0 , 16 ) do factorial (N , F ), write (N ), write ("! = " ), write (F ), nl ). (N1 , F1 ), fibonacci (N2 , F2 ), F is F1 + F2 . main :- ( for (N , 1 , 16 ) do fibonacci (N , F ), write (F ), write (", " ) ), writeln ("..." ).

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

Пример для версий ECLiPSe CLP 6.0 #188

Числа Фибоначчи вычисляются рекурсивно, при этом используется мемоизация, реализованная при помощи 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 ("..." ).

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

Идея использования логики исчисления предикатов I порядка в качестве основы языка программирования возникла в 60-е годы, когда создавались многочисленные системы автоматического доказательства теорем и вопросно-ответные системы. В 1965 г. Робинсон предложил принцип резолюции, который в настоящее время лежит в основе большинства систем поиска логического вывода. Метод резолюций был использован в системе GPS (general problem solver). В нашей стране была разработана система ПРИЗ, которая может доказать любую теорему из школьного учебника геометрии.

Язык программирования PROLOG (programming in logic) был разработан и впервые реализован в 1972 г. группой сотрудников Марсельского университета во главе с Колмероэ. Группа занималась проблемой автоматического перевода с одного языка на другой. Основа этого языка - исчисления предикатов I порядка и метод резолюций.

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

Суть Пролога – программирование в терминах целей. Программист описывает условие задачи, пользуясь понятиями объектов различных типов и отношений между ними, и формулирует вопрос. PROLOG-система обеспечивает ответ на вопрос, находя автоматически последовательность вычисления решения, используя встроенную процедуру поиска. До 1981 г. число исследователей, занимавшихся логическим программированием, составляло около сотни во всем мире. В 1981 году PROLOG был выбран в качестве базового языка компьютеров пятого поколения, и количество исследователей логического программирования резко возросло. Одной из наиболее интересных тем исследований является связь логического программирования с параллелизмом.

Где же используется Пролог в настоящее время? Это область автоматического доказательства теорем, построение экспертных систем, машинные игры с эвристиками (например, шахматы), автоматический перевод с одного языка на другой.

В настоящее время создано достаточно много реализаций языка Пролог: Wisdom Prolog, SWI Prolog, Turbo Prolog, Visual Prolog, Arity Prolog и т.д.

В нашем курсе будем использовать SWI Prolog. SWI-Prolog развивается с 1987 года. Его создателем и основным разработчиком является Ян Вьелемакер (Jan Wielemaker). Название SWI происходит от Sociaal-Wetenschappelijke Informatica (гол. социально-научная информатика), первоначального названия группы в Амстердамском университете, где работает Вьелемакер.

SWI-Prolog позволяет разрабатывать приложения любой направленности, включая Web-приложения и параллельные вычисления, но основным направлением использования является разработка экспертных систем, программ обработки естественного языка, обучающих программ, интеллектуальных игр и т.п. Это интерпретатор. Файлы, содержащие программы, написанные на языке SWI Prolog, имеют расширение pl.

SWI-Prolog-Editor является средой программирования для языка SWI-Prolog, включающую редактор программ с подсветкой синтаксиса, интерпретатор и отладчик программ. Основным назначением среды является обучение логическому программированию на языке Prolog.

Сначала устанавливаем SWI Prolog, затем - SWI Prolog Editor. Для запуска редактора SWI Prolog Editor необходимо запустить файл SwiplEdit.exe. Для настройки работы интерпретатора в специальном окне редактора, следует установить путь к интерпретатору, выполнив в редакторе команду Окно-Конфигурация на закладке Программы установить в строке Папка Пролога путь к интерпретатору. Там же, на закладке Настройки необходимо установить поле Codepage равным cp1251. Настройка кодовой страницы необходима для правильного сопоставления строковых констант, набранных русским алфавитом, между текстом программы в среде SWI-Prolog-Editor и языком SWI-Prolog. Для запуска программы из панели редактирования программ ее следует сохранить и нажать функциональную клавишу F9 или соответствующий значок на панели инструментов. В случае успешной загрузки на панели запросов появится:

Consult(<имя файла>).

Загрузить файл можно так же с помощью команды: [<имя файла>].

После любой модификации программу требуется заново загрузить в память. Перезапуск интерпретатора Пролога осуществляется нажатием Ctrl+F9 или соответствующего значка на панели инструментов.

Для выхода из интерпретатора Пролога используется команда: halt.

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

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

Рисунок 10 - Дерево родственных отношений

Пример 1: Это дерево можно описать следующей Пролог-программой.

родитель(пам, боб).

родитель(том, боб).

родитель(том, лиз).

родитель(боб, энн).

родитель(боб, пат).

родитель(пат, джим).

У нас имеется отношение родитель между двумя объектами. Описаны 6 фактов наличия отношений между конкретными объектами. Имена объектов начинаются с маленьких букв (они являются константами). В Прологе принято соглашение, что константы начинаются с маленькой буквы, а переменные – с большой. После набора такой Пролог-программы в редакторе можно загрузить программу в Пролог и задавать вопросы, касающиеся отношения родитель.

Запрос к программе набирается после приглашения?- и должен заканчиваться точкой. Для выполнения набранного запроса необходимо нажать Enter. Ответ будет выдан под запросом. Запрос может быть набран в несколько строк - для перехода на новую строку используется клавиша Enter. В том случае, если строка будет заканчиваться точкой и будет нажата клавиша Enter SWI-Prolog начнет выполнение запроса. Если возможны несколько вариантов ответа на запрос, то для получения каждого следующего используется клавиша Enter. Варианты ответов SWI-Prolog отделяет друг от друга точкой с запятой. Прекратить выполнение программы (выдачу альтернативных ответов) можно нажав клавишу «a».

Вопросы могут быть простые и сложные (в качестве связки «и» при составлении сложного вопроса используется запятая). Ответы Пролог-системы выводятся сразу после вопроса. Могут быть следующие варианты ответов:

No (соответствует нет или не найдены значения переменных в вопросе);
Перечисляются возможные значения переменных в вопросе. При этом при нажатии клавиши «a» поиск решений прекращается, а при нажатии клавиши Enter, продолжается поиск новых решений до тех пор, пока не будут найдены все. Альтернативные решения разделяются точкой с запятой. Вывод завершается словом Yes, если не все решения были найдены и No, если других решений не осталось.

Вопрос относительно отношения родитель	Вопрос в Пролог-системе	Ответ Пролог-системы
Боб является родителем Пат?	родитель(боб,пат).
Пат – ребенок Лиз?	родитель(лиз,пат).
Кто родители Лиз?	родитель(X,лиз).
Кто дети Энн?	родитель(энн, X).
Кто дети Боба?	родитель(боб,X).
Есть ли дети у Лиз?	родитель(лиз,_).
Кто чей родитель?	родитель(X,Y).
Кто внуки Тома?	родитель(том,X), родитель(X,Y).
Кто родители родителей Джима?	родитель(X,джим), родитель(Y,X).

Итак, в простейшем случае Пролог-программа описывает факты и правила.

Факт – это безусловное утверждение (всегда истинное), характеризующее объект с некоторой стороны или устанавливающее отношение между несколькими объектами. Факт не требует доказательств. Факт имеет следующий вид:

<имя предиката>(O 1 ,O 2 ,…,O n).

Обратим внимание на то, что в конце факта ставится точка. <имя предиката> должно начинаться со строчной буквы и может содержать буквы, цифры, знаки подчеркивания. О i (i = 1,..,n) - аргументы предиката могут быть конкретными объектами (константами) или абстрактными объектами (переменными). Если конкретные объекты начинаются с буквы, то эта буква должна быть строчной.

Переменные начинаются с прописной буквы или символа подчеркивания. Переменная в Прологе, в отличие от алгоритмических языков программирования, обозначает объект, а не некоторую область памяти. Пролог не поддерживает механизм деструктивного присваивания, позволяющий изменять значение инициализированной переменной, как императивные языки. Переменные могут быть свободными или связанными. Свободная переменная – переменная, которая еще не получила значения. Она не равняется ни нулю, ни пробелу; у нее вообще нет никакого значения. Такие переменные еще называют неконкретизированными. Переменная, которая получила какое-то значение и оказалась связанной с определенным объектом, называется связанной. Если переменная была конкретизирована каким-то значением и ей сопоставлен некоторый объект, то эта переменная уже не может быть изменена.

Областью действия переменной в Прологе является одно предложение. В разных предложениях может использоваться одно и то же имя переменной для обозначения разных объектов. Исключением из правила определения области действия является анонимная переменная, которая обозначается символом подчеркивания. Анонимная переменная предписывает интерпретатору проигнорировать значение переменной. Если в правиле несколько анонимных переменных, то все они отличаются друг от друга, несмотря на то, что записаны с использованием одного и того же символа.

Правило – утверждение, которое истинно при выполнении некоторых условий. Правило состоит из условной части (тела) и части вывода (головы). Головой правила является предикат, истинность которого следует установить. Тело правила состоит из одного или нескольких предикатов, связанных логическими связками: конъюнкция (обозначается запятой), дизъюнкция (обозначается точкой с запятой) и отрицание (означается not или \+). Правило имеет следующий вид:

<голова правила > :– <тело правила>.

В конце правила так же ставится точка. Можно считать, что факт – это правило, имеющее пустое тело.

С помощью правил можно описывать новые отношения.

Пример: Пусть имеется двуместное отношениеродительи одноместное отношение мужчина. Эти отношения описываются в виде фактов. Опишем новое двуместное отношениедед, используя правила.Xявляется дедомY, если существует цепочка:X– родительZ,Z– родительY, при этомXдолжен быть мужчиной.

дед(X,Y):–родитель(X,Z),родитель(Z,Y),мужчина(X).

Пример: Пусть имеется двуместное отношение родитель, описанное в виде фактов. Опишем новое двуместное отношение предок, используя правила. X является предком Y, если X – родитель Y или существует цепочка людей между Х и Y, связанных отношением родитель.

предок(X,Y):–родитель(X,Y).

предок(X,Y):–родитель(X,Z),предок(Z,Y).

Эти правила можно записать по-другому:

предок(X,Y):–родитель(X,Y);

родитель(X,Z),предок(Z,Y).

В данном примере получили рекурсивное определение отношения предок.

Пример. Определим двуместное отношение дальний_родственник с помощью правила, используя имеющееся отношение предок. X является дальним родственником Y, если они связаны отношением предок, но при этом не связаны отношением родитель.

дальний_родственник (X,Y):–предок(X,Y),not(родитель(X,Y));

предок(Y,X),not(родитель(Y,X)).

В правой части правила для сравнения можно использовать знаки @<, @=<, @>=, @> для проверки на упорядоченность, == для проверки на равенство и \== для проверки на неравенство.

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

В октябре 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 - поиск совершенных чисел

Для этого примера нам понадобится предикат 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) - , 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/2 - принадлежность элемента списку. Предположим у нас есть 2 списка: 1-й исходный список, 2-й - предполагаемое сочетание, необходимо проверить правильность сочетания. Элементы сочетания располагаются в порядке исходного списка.

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) первичное описание задачи и получение переборного решения 2) логическая оптимизация перестановкой предикатов справа 3) логическая оптимизация введения упрощенных проверок или удаление лишних условий 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 - Задача о переливаниях.

В качестве следующей задачи рассмотрим классическую задачу о состояниях, эта задача гораздо лучше отражает преимущества использования Пролог. Общая постановка задачи: даны некоторые емкости с водой, необходимо путем переливаний получить определенное количество воды в некоторой емкости. Для примера возьмем 3 кувшина емкостью 12 литров, 8 литров, 5 литров, наполним 1-й полностью, то есть 12 литрами и поставим задачу получить 6 литров . Для начала попытайтесь решить эту школьную задачу при помощи ручки и листка бумаги :)

Прежде чем генерировать различные алгоритмы и пытаться их применить к задаче, давайте сначала перепишем условия в терминах Пролога. Опишем емкость как терм 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 задачки на приз :

Как известно в функциональном и логическом всячески пытаются избежать программ с 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 теориям уделяется гораздо больше внимание, чем всем остальным - это теория множеств и теория предикатов . Между ними существуют определенная связь, одно выражается через другое и наоборот. Например, предикат - это множество значений на которых он истинен, и наоборот множество - это предикат принадлежности. Традиционная реляционная теория баз данных оперирует множествами, а Пролог оперирует - предикатами. В общем, задача состоит в том, чтобы выразить абсолютно традиционную для теории множеств операцию - операцию взятия множества всех подмножеств .
Задача : дан некоторый одноместный предикат a/1 (в общем случае множество элементов не ограничено, может быть бесконечно), написать предикат subset_a/1, который будет выдавать подмножества, состоящие из элементов множества a.
Пример : запрос subset_a(X) выдает X = , X = , X = , X = (порядок не важен):
a(1). a(2). subset_a(X) :- ....?

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

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

Цель урока: Знакомство с историей языка программирования Prolog, основы работы с компиляторами

Prolog (Pro gramming in log ic) — это язык высокого уровня, не алгоритмический, предназначенный для написания программ с использованием концепций и методов .

История

Пролог был разработан в Марсельском университете во Франции Алэном Колмероэ и другими членами «группы искусственного интеллекта» в 1973 году. Данная команда энтузиастов разработала программу, предназначенную для доказательства теорем. Написана она была на Фортране, и использовалась при построении систем обработки текстов на естественном языке. Работала программа довольно медленно и назвалась Prolog (от Programmation en Logique на франц.). Программа послужила прообразом Пролога.

Язык логического программирования prolog — , что означает, что программа, написанная на нем, выглядит как набор логических описаний, определяющих цель, ради которой она и написана .

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

Логика предикатов - это простейший способ объяснить, как «работает» мышление.

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

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

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

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

Особенности языка

Описание проблемы и правил ее решения.
Нахождение всех возможных решений с помощью механизма поиска с возвратом (backtracking).
Легкий синтаксис.

Версии и компиляторы

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

Изучать Пролог без привязки к конкретной его версии не совсем целесообразно. Версий Пролога очень много, но мы выберем наиболее известную в России и довольно эффективную версию Пролога - Турбо Пролог . Начинала разработку версии (реализации) фирма Borland International совместно с датской компанией Prolog Development Center (PDC ). Первая версия вышла в 1986 году. Последняя совместная версия 1988 года вышла под номером 2.0.

Рис. 1. Сайт центра разработки Prolog (Prolog Developement Center)

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

Таким образом, в 1992 году вышла версия PDC Prolog 3.31, а в 1996 году, при участии группы питерских программистов, PDC выпустила систему Visual Prolog 4.0, у которой много достоинств, но мы не будем на них останавливаться.

Для работы мы выберем самый простой компилятор TPtolog (Турбо Пролог).

К достоинствам Турбо Пролога относится возможность присоединять к программе на этом языке процедуры, написанные на Паскале, Си , Фортране или ассемблере.

Для работы в Tprolog с 68 битной системой необходимо использовать программу для эмуляции DOS (например, dosbox).

Алгоритм работы с программой следующий:

запуск dosbox
mount c c:\dos\TProlog
c: => enter
prolog => enter
Набор кода программы в редакторе «notepad++» и сохранение с расширением.PRO в папке tprolog\labs

Работа в Tprolog

Горячие клавиши и основные команды:

F10 , Esc — переход в главное меню.
Esc — выход из текущего пункта / отмена.
Меню Edit — переход к редактированию кода.
Меню Files -> New File — создание нового файла.
Меню Compile -> Memory -> Меню Run — компиляция и запуск программы.

При работе в tprolog иногда возникают нестандартные ситуации, когда программа не реагирует на нажатия клавиш. Если не открывается какой-либо пункт меню – то надо несколько раз нажать клавишу i .

Запуск программы осуществляется :

Через написание раздела GOAL и запуска программы в меню compile и run .
Работа с окном DIALOG (в таком случае раздел GOAL в программе не нужен).

Запуск программы при использовании раздела GOAL

Compile — компилируем
Run — запускаем
Esc – выход в меню

Работа с окном dialog

Команда Run .
Окно dialog .
Запрос в виде: postroil (jack,house) .

Раздел Goal программы нельзя использовать, если работа осуществляется в окне dialog