Язык логического программирования Пролог - файл prolog-general.doc

Язык логического программирования Пролог
скачать (490.4 kb.)
Доступные файлы (8):
prolog-general.doc105kb.05.02.2009 13:36скачать
n2.txt65kb.02.02.2009 17:10скачать
n3.doc73kb.05.02.2009 14:13скачать
n4.doc102kb.05.02.2009 13:46скачать
n5.doc91kb.09.02.2009 15:36скачать
n6.doc143kb.09.02.2009 15:23скачать
n7.doc646kb.09.02.2009 15:39скачать
n8.doc79kb.09.02.2009 15:31скачать

prolog-general.doc

КраткаЯ характеристика Языка ПРОЛОГ


Язык программирования (ЯП) Пролог (PROgramming in LOGic) был реализован в начале 70-х годов Колмероэ в Марселе (Франция) на основе теоретической разработок, выполненных в Эдинбургском университете (Шотландия) Ковальским. Однако, широкое внимание к себе он привлек только после того как в 1977 году появилась его очень удачная версия для ЭВМ DEC-10, а затем Япония выбрала Пролог в качестве базового ЯП для своего проекта ЭВМ 5-го поколения, ориентированного на принципиально новую технологию использования компью­теров для работы со знаниями.

В традиционных ЯВУ описание задачи неотделимо от описания процесса ее решения. Все функции и отношения определяются указанием конкретного способа их вычисления. Принципиальная особенность Пролога заключается в том, что программа представляется как множество объектов и множество отношений между ними (т.е. пара < P,R >), что традиционно для математического стиля описания задач.

Поэтому вполне естественно, что источниками создания Пролога послужили логика предикатов 1-го порядка, теория рекурсивных функций, методы логического вывода (конкретно метод резолюций), языки программирования Плэнер и Лисп.

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

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

Необходимо подчеркнуть, что влияние, которое Пролог оказал на информатику (в частности, в связи с проектом ЭВМ 5-го поколения) гораздо существеннее, чем можно было бы пред­положить, оценивая число написанных на нем программ.

Рассмотрим основные понятия Пролога:

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

Числа и символы понимаются в традиционном смысле.

Примеры констант: -67, 5, ‘s’, ‘/’, 3.14

Для констант могут быть введены символические имена, которые будут использоваться в тексте программы вместо самой константы. Например, pi = 3.14 или zero=0. Для этого служит специальная секция CONSTANTS.

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

Примеры атомов: машина, иван, “ кто-то ”, “Иван”, “иван”.

Здесь иван и “иван” – это один и тот же атом, но “Иван” и “иван” - разные

Примеры переменных: Иван, Студент, Z34, xyz, _test.

Переменная может находиться в свободном(free) или связанном (bound) состоянии. Причем переменные не предназначены для хранения значений, т.е. им нельзя явно присвоить какое-либо значение. А связанными они становятся в процессе проверки утверждений Пролога.

Примечание: Visual Prolog использует понятие “тип данных – domain”. К стандартным (встроенным) доменам относятся целые типы: integer- unsigned, long – ulong, short – ushort, sbyte – byte; real (аналогичен типу double в С); char (байт без знака - символ в одинарных кавычках – 'a'); string; symbol; binary; ref (для добавления термов в базу данных Пролога). Разница между типами string и symbol заключается только в их внутреннем представлении. Тип string аналогичен строкам в С.. Тип symbol реализуется как ссылка на внутреннюю symbol-таблицу, хранящую все строки, используемые в программе на Прологе. По умолчанию атомы, заданные в виде строк, окаймленных двойными кавычками, обрабатываются по типу string. А атомы, определенные в виде строк, начинающихся со строчной буквы, - по типу symbol.

К сложным (составным) объектам данных в Прологе относятся структуры и списки.

Регистр символов в имени структуры не имеет значения, но рекомендуется не использовать прописные символы. Спецсимволы '$’, ‘-‘, ‘?’ и другие, за исключением символа подчеркивания нельзя использовать в именах структур.

Аргументами могут быть числа, атомы, переменные, структуры и другие сложные объекты. Однако, количество компонент структуры фиксировано и не может меняться в процессе выпол­нения программы. Вообще говоря, могут использоваться и структуры без аргументов.

Примеры структур:

Если внимательно посмотреть на приведенные примеры, то видно, что синтаксически они записаны одинаково, но имеют несколько разный характер.

Граф состоит из вершин a,b,c,d,u,v,x .

Каждый «студент» описывается такими свойствами как фамилия, имя, возраст.

Наша семья состоит из … и перечисляется состав.

Иван имеет машину.

Дерево описывается свойством "цвет" и значение у этого свойства - зеленый .

Таким образом, примеры 1 и 5 определяют новые объекты через другие объекты, пример 2 – как комбинацию свойств. Пример 3 определяет отношение между Иваном и машиной. А пример 4 выделяет одно из свойств объекта. Эти примеры подчеркивают, что синтаксически одинаковая запись в Прологе может быть использована как для представления сложного объекта - структуры, так и для представления отношения между объектами или описания свойств объектов (т.е. унарных отношений).

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

Соответственно, все структуры должны быть описаны в секции DOMAINS вместе с пользовательскими типами данных. А все используемые в программе предикаты (кроме встроенных) - в секции PREDICATES.

Примечание: Visual Prolog в отличие от стандартного ПРОЛОГА реализован в виде типизированного компилятора, и, в частности,. требует обязательного описания типов аргументов для всех структур и предикатов. Это позволяет обеспечить высокую скорость исполнения программ на Visual Prolog, сравнимую с С и Паскалем.

Кроме того при описании предикатов могут быть заданы такие их свойства как

Примеры предикатов:

получил_оценку("Петров",5)

отличная(Оценка)

обучает(профессор, студент, дисциплина)

Примеры описания предикатов:

DOMAINS

студент = symbol

профессор=symbol

дисциплина=symbol

оценка=integer

PREDICATES

nondeterm получил(студент, оценка)

determ получил_оценку_по_дисциплине(студент, оценка, дисциплина)

обучает(профессор, студент, дисциплина)

Здесь студент может иметь несколько оценок по разным предметам, поэтому предикат неоднозначен. Но оценка по каждой дисциплине может быть только одна.

В Прологе существует множество встроенных специальных предикатов. Например,

Другим сложным объектом данных Пролога является список.

Список не имеет имени, а количество его элементов может меняться.

Примеры списков:

Следует подчеркнуть, что атом “иван” и список [“иван”], состоящий из единственного элемента “иван” – это разные объекты данных.

Чтобы использовать список, надо сначала описать его домен. Например,

DOMAINS

персонал = сотрудник*

сотрудник = преподаватель; инженер

преподаватель, инженер = symbol

Здесь именно символ «*» определяет персонал как список сотрудников.

Символ запятая (,) определяет логическое «и», а символ двоеточие (;) – логическое «или».

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

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

Голова списка – элемент, а хвост – всегда список. Например, голова списка [s] – это “s”, а хвост равен [ ]. Если достаточное число раз отделить первый элемент списка, то получим в конце концов пустой список.

Для отделения головы от хвоста Пролог использует специальный выделенный символ “|”. Например, [a,b,c] эквивалентно [a | [b,c] ] и далее [a | [ b | [c ] ] ] и [a | [ b | [ c | [ ] ] ] ].

Основная операция над объектами в Прологе - это унификация (иногда называют сопостав­ление, согласование, конкретизация). По своей сути унификация - это сравнение объектов или их совокупностей.

Правила унификации:

Очевидно, что операция сопоставления может кончиться неудачно.

Примеры унификации:

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

Примеры унификации :

Выражение

Результат

X = 3+3

X=6

X = '3' + '3'

X=102

X = “3” + “3”

Неверный тип Это ошибка

X = 4 + x

Неверный тип тип Это ошибка

X = X+1

Свободная переменная в выражении

[a,X,Y]=[a,b,c]

X=b , Y=c

[Z,u,D]=[x,y,z]

No Это результат

[X|Y]=[a,b,c]

X=a , Y=[“b”, “c”]

L=[a,b,c,d],L1=[1|L]

L=[a,b,c,d] , L1=[1,a,b,c,d]

Основными утверждениями (clauses) Пролога являются факт и правило. Отличительной чертой утверждения является точка в конце.

Факты описывают свойства объектов и отношения между объектами.

Свойства

Отношения

собака (бобик).

владеет(иван,машина).

человек (сократ).

владеет(иван,юпитер).

человек(Студент).

любит(петя,оля).

студент(петя).

любит(Мальчик,Девочка).

ест(_)

является_родителем(Кто,_).

На обычном языке эти утверждения будут выглядеть следующим образом:

Бобик – это собака.

Сократ – это человек.

Иван владеет машиной.

Петя любит Олю

Особо следует выделить примеры в последней строке. Они будут звучать как: «Все едят» и «Все, кто является родителем». Автономно используемый символ подчеркивания ‘_’ называется «анонимной переменной» и в утверждении показывает, что не имеет значения какой объект будет подставлен вместо соответствующего аргумента предиката.

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

A называется заголовком или целью, B, C, D - телом или подцелями. Цель правила – всегда единственна, число подцелей -произвольно.

Интерпретация правила выглядит следующим образом: A истинно, если одновременно истинны B, C и D.

Примеры правил:

Здесь связка ‘:-‘ может читаться как «если (if)» и трактоваться как аналог условного оператора из традиционных ЯП.

Символ “запятая” означает коньюнкцию подцелей (логическая операция “И”), “точка с запятой” - дизъюнкцию (логическая операция “ИЛИ”). Например, последний пример можно переписать следующим образом:

Синтаксически между фактом и правилом нет никакой разницы. Факт - это правило, тело которого всегда истинно.

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

Утверждения записываются в секции CLAUSES.

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

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

В отличие от традиционных ЯВУ процедура Пролога представляет собой не описание последовательности действий, а скорее определение некоторого понятия.

Пример процедуры:

является_элементом(X,[Первый|Z]):  X = Первый; является_элементом (X, Z).

В этом примере показана именно процедура, т.к. его можно переписать следующим образом:

Пример:

является_элементом(X,[Первый|Z]):  X = Первый.

является_элементом(X,[Первый|Z]):  является_элементом (X, Z).

Выполнение Visual Prolog программы начинается тогда, когда в ее тексте встречается секция GOAL следующего вида:

GOAL A,B,C.

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

Алгоритм доказательства (алгоритм логического вывода) всегда жестко встроен в Пролог-систему и обычно имеет следующий вид:

  1. целевой запрос заменяется на обратный;

  2. множество утверждений программы приводится к нормальной конъюктивной форме(......)  (......)  (......) ...;

  3. последовательно применяются
    - унификация подцелей,
    - правило резолюции ( P  Q1 )  ( P  Q2 )  Q1  Q2 ,
    - удаление истинных утверждений типа А  А

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

Пример (этот пример традиционно повторяется в каждой книге по Прологу):

Пусть заданы следующие утверждения:

смерть (X): человек(X). (человек смертен)

человек (сократ). (сократ - это человек)

?  смерть (сократ). (смертен ли сократ?)

Нормальная конъюктивная форма будет иметь следующий вид:

( человек(X)  смерть(Х) )  человек(сократ)  смерть(сократ).

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

Проводим унификацию, сопоставляя переменную X и атом “сократ”:

( человек(сократ)  смерть(сократ) )  человек(сократ)  смерть(сократ).

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

( человек(сократ)  смерть(сократ) )  ( человек(сократ)   )(смерть(сократ)  )

После упрощения получаем

смерть(сократ)  смерть(сократ).

Это выражение ложно, т.к. утверждение “сократ смертен” не может одновременно быть и истиной, и ложью. Следовательно исходный запрос имеет ответ “да”.

Пример целевого запроса:

GOAL является_элементом(3,[1,3,5,7]).

да

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

Пример:

DOMAINS

человек=symbol

существо=symbol

PREDICATES

любит (человек,существо)

CLAUSES

любит (миша, cat).

GOAL

любит ("миша", Что).
Что=cat (ответ Пролога)

1 решение

Теперь добавим в программу еще один факт:

любит ("миша", "собака").

В результате получим сообщение об ошибке: «Решение неоднозначно».

Таким образом мы столкнулись с еще одной особенностью Пролога – он может найти не только одно, а все множество возможных решений исходной задачи. Однако, в нашем примере, чтобы помочь Прологу сделать это, надо указать, что предикат likes допускает неоднозначность.

Пример:

DOMAINS

человек=symbol

существо=symbol

PREDICATES

nondeterm любит (человек,существо)

Clauses

любит (миша, cat).

любит ("миша", "собака").

GOAL

любит ("миша", X).
X=cat (ответ Пролога)

X=собака

2 решения

Для поиска решения в Прологе используется встроенный механизм, который называется «backtracking» - backing-up-and-trying-again method. Его смысл в том, что когда некоторая под­цель достигнута, Пролог возвращается к точке , где начался поиск решения для этой подцели (т.е. к точке, где была достигнута предыдущая подцель) и пытается получить ее другим способом.

Чтобы понять, как работает этот механизм, рассмотрим простой пример:

Пример работы механизма backtracking:

DOMAINS

студент = symbol

то_что_можно_жевать = symbol

качество = symbol

PREDICATES

nondeterm любит(студент,то_что_можно_жевать)

имеет_вкус(то_что_можно_жевать,качество)

nondeterm съедобное(то_что_можно_жевать)

CLAUSES

любит(петя, X):- съедобное (X), имеет_вкус(X,good).

имеет_вкус (пицца, good).

имеет_вкус (плов,bad).

съедобное (плов).

съедобное (пицца).

GOAL

любит(петя, Что).

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

Чтобы увидеть , как работает backtracking, зададим цель:

любит (петя, Что).

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

Для управления backtracking-ом в Прологе существует множество встроенных предикатов. Например:

fail - определяет, что текущий поиск решения для некоторой подцели неудачен и требуется начать новый поиск;

cut (или !) – принудительно завершает все поиски.

В частности, эти предикаты можно использовать для организации циклических процессов, т.к. в Прологе отсутствуют конструкции типа FOR, WHILE или REPEAT, имеющиеся в традиционных ЯП.

Другой мощный механизм организации циклов в ПРОЛОГЕ – это рекурсия. Рассмотрим, как с помощью рекурсии реализуется "суммирование нечетных чисел из списка".

Типовой пример: Суммирование нечетных чисел

DOMAINS

список = integer*

число = integer

PREDICATES

nondeterm является_результатом_проверки_на_нечетность(число,число) - (o,i)

nondeterm является_суммой_нечетных_элементов(число,список) - (o,i)

CLAUSES

/* Процедура проверки на нечетность */

является_результатом_проверки_на_нечетность(0,X):- Y = X mod 2, Y=0.

является_результатом_проверки_на_нечетность(X,X):- Y = X mod 2, Y=1.

является_суммой_нечетных_элементов(0,[ ]). /* Сумма элементов пустого списка = 0 */

является_суммой_нечетных_элементов(S,[Первый|Хвост]):-

является_суммой_нечетных_элементов(S1,Хвост),

является_результатом_проверки_на_нечетность(R,Первый),S= R + S1.

GOAL

является_суммой_нечетных_элементов(Сумма_Нечетных,[23,34,7,9]).

Ответ ПРОЛОГА:

Сумма=39

1 Solution

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

Примеры небольших программ на Visual Prolog приведены в разделе «Примеры решений».

В заключение обзора рассмотрим некоторые особенности программ на Visual Prolog:

  1. Программы на Visual Prolog имеют следующую структуру:

< описание параметров компиляции>

CONSTANTS

< описание символических констант>

имя = значение

DOMAINS

< описание пользовательских типов данных, в т.ч. составных объектов >

домен1, …, доменК = базовый домен

домен2 =домен*

домен3 = функтор1(аргумент11, …,аргумент1N); функтор2(аргумент21, …,аргумент2N)

FACTS ( или DATABASE)

< описание таких предикатов, для которых факты могут меняться динамически >

функтор(домен1, …,доменN)

PREDICATES

< описание пользовательских предикатов и функций >

функтор(домен1, …,доменN)

CLAUSES

< описание фактов и правил >

функтор(объект1, …, объектN).

функтор1(об1, …, обN):- функтор2(обK1, …, обKN), …, функторN(обM1, …, обMN).

GOAL

< описание единственной цели >

функтор(объект1, …, объектN).

  1. Примеры директив компиляции:

Diagnostics – в окне “Messages выводит имена используемых предикатов, их типы, детерми­нированность, размер кода и т.п.

Errorlevel = - задает степень подробности отчета об ошибках.

  1. Для указания, что некоторый текст является только комментарием, а не частью программы используются следующие ключевые символы:

  1. Чтобы включить в программу содержимое другого файла применяется директива

include “устройство:\\путь\\файл”

Два \ используются, т.к. этот символ является служебным.

К недостаткам Пролога можно отнести

Стандарт на Пролог долгое время отсутствовал, но неофициально им считалось описание , предложенное Клоксином.

Наиболее распространенными версиями были Турбо-Пролог и М-Пролог, реализованный в Венгрии.

Л И Т Е Р А Т У Р А


  1. Клоксин У., Меллиш К. Программирование на языке Пролог. - М.: Мир, 1987.

  2. Братко И. Программирование на языке Пролог для искус­ствен­ного интеллекта. - М.: Мир, 1990.





Учебный материал
© bib.convdocs.org
При копировании укажите ссылку.
обратиться к администрации