Логическое программирование — это направление современного программирования, возникшее первоначально в рамках работ по искусственному интеллекту и получившее свое развитие во второй половине восьмидесятых годов, благодаря японскому проекту ЭВМ пятого поколения. Наиболее полное выражение идеи логического программирования нашли в языке Prolog (PROgramming in LOGic — программирование в терминах логики). Первоначальный вариант языка Prolog был разработан под руководством Алэна Кольмероэ (Alain Colmerauer) в Марсельском университете в 1972 году. В настоящее время существуют разнообразные версии для DOS (PDC Prolog, Arity Prolog и др.), Windows (Visual Prolog, Strawberry Prolog, Trinc Prolog и др.), Linux (Arity Prolog, Visual Prolog и др.).
Теоретической основой Prolog является раздел символьной логики, называемый исчислением предикатов. Prolog присущ ряд свойств, которыми не обладают традиционные языки программирования, что делает его мощным средством в области логического программирования. К таким свойствам относятся механизм вывода с поиском и возвратом, встроенный механизм сопоставления с образцом и простая, но выразительная структура данных с возможностью ее изменения. В Prolog отсутствуют указатели, операторы присваивания и GOTO. Естественным методом программирования является рекурсия.
Программа на Prolog есть совокупность утверждений. Утверждения состоят из целей. В конце утверждения ставится точка «.». Иногда утверждение называется предложением.
Основная операция Prolog — доказательство целей, входящих в утверждение.
Существуют два типа утверждений:
- факт — это одиночная цель, которая, безусловно, истинна;
- правило состоит из одной головной цели и одной или более хвостовых целей, которые истинны при некоторых условиях.
Правило обычно имеет несколько хвостовых целей в форме конъюнкции целей.
Конъюнкцию можно рассматривать как логическую функцию И. Таким образом, правило согласовано, если согласованы все его хвостовые цели.
Примеры фактов:
person (john). мужчина (виктор). нравиться (джон, мери).
Примеры правил:
человек (Х) :- мужчина(Х). твистик(Кто_то) if человечек(Кто_то), любит_танцевать(Кто_то, твист).
Выберем для реализации систему Visual Prolog (www.visual-prolog.com).
Решим задачу о родственных отношениях, так как Prolog хорошо приспособлен для обработки нечисловой информации.
Тот факт, что Том является родителем Боба, можно записать на Prolog так:
родитель(том, боб).
Здесь мы выбрали родитель в качестве имени отношения, том и боб — в качестве аргументов этого отношения. Записываем имена, как том, начиная со строчной буквы. Все дерево родственных отношений (семантическая сеть)
пам том
\ / \
боб лиз
/ \
энн пат
/
джим
описывается следующей программой на языке Visual Prolog:
domains name=symbol predicates родитель(name,name) clauses родитель(pam,bob). родитель(tom,bob). родитель(tom,liz). родитель(bob,ann). родитель(bob,pat). родитель(pam,jim). goal родитель(bob,pat).
Для программирования необходимо
1. Запустить систему Visual Prolog.
Рис. 12.1. Окно Visual Prolog 5.0
2. Ввести программу File ® New.
3. Протестировать цель Project ® Test Goal.
На заданный вопрос: «Является Боб родителем Пат?» — система ответит yes (да), найдя такой факт в программе.
Другой вопрос: «Кто является родителем Лиз?»
goal родитель(X,liz).
Ответ системы
X=tom
1 Solution.
Вопрос «Кто дети Боба?» можно передать в такой форме:
goal родитель(bob, X). Ответ X=ann X=pat 2 Solutions
Программе можно задавать и более общие вопросы: «Кто чей родитель?» Сформулируем его таким образом:
Найти X и Y такие, что X - родитель Y.
На Prolog это записывается так:
goal родитель(X,Y).
Система будет по очереди находить все пары вида «родитель-ребенок».
X=pam, Y=bob
X=tom, Y=bob
X=tom, Y=liz
X=bob, Y=ann
X=bob, Y=pat
X=pam, Y=jim
6 Solutions
Запрограммируем задачу.
Даны утверждения:
Зевс — отец Ареса. Гера — мать Ареса. Арес — отец Гармонии. Афродита — мать Гармонии. Карид — отец Семелы. Зевс — отец Диониса. Семела — мать Диониса. Божества — Зевс, Гера, Арес, Афродита. Гармония — царица.
Определить правила: женщина, мужчина, родитель, родители, дедушка, бабушка.
domains name=string predicates отец(name, name) % отец (Кто, Чей) мать(name, name) % мать (Кто, Чья) божество(name) % божество(Имя) царица (name) % царица (Имя) clauses отец("Зевс", "Арес"). отец("Арес", "Гармония"). отец("Карид", "Семела"). отец("Зевс", "Дионис"). мать( "Гера", "Арес"). мать("Афродита", "Гармония"). мать("Семела", "Дионис"). божество( "Зевс"). божество("Гера"). божество("Арес"). божество("Афродита"). царица ( "Гармония").
Определим правило женщина, исходя из только описываемого мира.
X является женщиной, если X — мать кого-либо Y или X — царица. женщина (X) if мать (X,_). женщина (X) if царица (X).
Аналогично правило мужчина.
X является мужчина, если X — отец кого-либо Y. мужчина (X) if отец (X,_).
Правило родитель.
X родитель для Y, если X отец Y, либо X мать Y. родитель (X, Y) if отец (X, Y). родитель (X, Y) if мать (X, Y).
Правило родители.
X и Y родители , если X родитель Z и Y родитель Z. родители (X, Y) if родитель (X, Z), родитель (Y, Z).
Цели можно поставить следующие.
goal женщина (Kto).% Кто является женщиной? goal мужчина (Kto).% Кто является мужчиной? goal родитель (X, "Дионис"). % Кто родители Диониса?
Решим задачу о родственных отношениях семьи Романовых, и найдем детей Алексея Михайловича.
domains name=string predicates родитель(name, name) % родитель (Кто, Чей) мужчина(name) % мужчина (Кто) женщина(name) % женщина (Кто) царь(name, integer, integer) % царь(Имя, начало_правления, конец_правления) goal родитель("Алексей Михайлович", X). clauses родитель("Михаил", "Алексей Михайлович"). родитель("Алексей Михайлович", "Федор"). родитель("Алексей Михайлович", "Иван"). родитель("Алексей Михайлович", "Софья"). родитель("Алексей Михайлович", "Петр I"). родитель("Петр I", "Алексей"). родитель("Екатерина II", "Павел I"). родитель("Петр III","Павел I"). мужчина("Михаил"). мужчина("Алексей Михайлович"). мужчина("Федор"). мужчина("Иван"). мужчина("Петр I"). мужчина("Алексей"). мужчина("Павел I"). мужчина("Петр III"). женщина("Софья"). женщина("Екатерина II"). царь("Михаил", 1613, 1645). царь("Алексей Михайлович", 1645 ,1676). царь("Федор",1676 ,1682). царь("Иван",1682 ,1696). царь("Софья",1682 ,1689). царь("Петр I",1682 , 1725). царь("Екатерина II", 1762, 1796). царь("Петр III", 1761,1762 ). царь("Павел I",1796 ,1801 ). 4 Solutions
Ответ системы:
X=Федор X=Иван X=Софья X=Петр I
Найдем всех цариц с помощью составного вопроса.
goal царь(X,_,_),женщина(X). X=Софья X=Екатерина II 2 Solutions
Добавим несколько правил: брат (brother), сколько_правил (how_reign).
predicates brother (name,name) how_reign (name,integer) clauses brother(X, Y) if родитель(Z, X) and %(1) родитель(Z, Y) and %(1) мужчина(X) and %(2) X<>Y. %(3) how_reign(Name, H) :- царь(Name, H1, H2), H=H2-H2.
Правило определения брата можно прочитать так:
Для любых X и Y, X является братом Y, если
- у X и Y есть общий родитель, и
- X - мужчина, и
- X сам себе не брат.
В процессе достижения цели Prolog осуществляет автоматический перебор вариантов, делая возврат при неуспехе какого-либо из них. Иногда требуется его ограничить или исключить вовсе.
Для этого в Prolog существует ограничивающая перебор цель «отсечение» (!), которая безусловна верна.
Найдем только одного сына Алексея Михайловича
goal родитель(“Алексей Михайлович”,Son), мужчина(Son),!. Son=Федор 1 solution
Опишем предикат, определяющий из двух целых чисел максимальное.
predicates max(integer, integer, integer) goal max(5,9, Max). clauses max(X,Y,Max) if X>=Y, Max=X. max(X,Y,Max) if X<Y, Max=Y.
Эти правила являются взаимоисключающими. Если выполняется первое, второе обязательно потерпит неудачу. Можно видоизменить при помощи отсечения правила.
max(X,Y,X) if X>=Y, !. max(X,Y,Y).
Prolog содержит стандартный предикат, выполнение которого заканчивается всегда неудачей — fail. Предикат fail инициирует процесс бэктрекинга (backtracking), то есть поиска новых решений, или передоказательства целей. Покажем на примере.
domains name=symbol predicates отец (name, name) everybody clauses отец ("Leonard", "Katherine"). отец ("Carl", "Jason"). отец ("Carl", "Marilyn"). everybody if отец (X, Y) and write(X,"является для ",Y," отцом\n") and fail. goal everybody.
Ответ системы:
Leonard является для Katherine отцом Carl является для Jason отцом Carl является для Marilyn отцом no Цель everybody завершена неудачно.
Для реализации отрицания используется предикат not. Особенность его использования состоит в том, что все переданные переменные должные быть связанными, то есть конкретизированными. Например, ответ на вопрос: «Леонард не отец Джейсону?» будет найден.
goal not(отец ("Leonard","Jason")). yes
Цель
goal not(отец (X,"Jason")).
не будет восприниматься системой. Можно переформулировать цель: «Кто из известных системе отцов не является отцом Джейсона?».
goal отец (X,_), not(отец (X,"Jason")). X=Leonard 1 Solution
Таким образом, нельзя получить знание из незнания, и предикат not используется только для проверки целей.
В приведенных программах на Visual Prolog можно выделить и дополнить:
Секции:
|
Domains |
% определение типов данных |
|
Predicates |
% определение предикатов (имен отношений) |
|
Clauses |
% определение фактов и правил |
|
Goal |
% целевое утверждение |
Основная операция, выполняемая на Prolog, — это операция сопоставления (называемая также унификацией или согласованием). Операция сопоставления может быть успешной или закончиться неудачей;
Переменные обозначаются последовательностью букв и цифр, начинающейся с заглавной буквы. Особый вид переменной — анонимная переменная _, используемая в качестве аргумента предиката, когда конкретное значение переменной несущественно. На переменные в правилах действуют кванторы общности. Переменные получают свои значения в результате сопоставления с константами в фактах или правилах. Переменные служат частью процесса сопоставления, а не «хранилищем» информации. Область действия переменной — ровно одно предложение;
Факты — это предикаты с аргументами-константами, обозначающие отношения между объектами или свойства объектов, именованными этими константами. Факты в программе считаются всегда безусловно истинными и служат основой доказательства, происходящего при выполнении программы;
Правила — фразы с заголовком и одной или несколькими подцелями-предикатами, имеют форму
<голова правила> :- <список подцелей>.
или
<голова правила> if <список подцелей>.