1.6. Механизм логического вывода: унификация
Программы на Прологе содержат утверждения, сделанные программистом, т. е. декларации логических соотношений, необходимые для решения задачи. При решении задачи Пролог использует два основных механизма: сопоставление и откат (бэктрекинг). Для этого в составе языка имеются внутренние подпрограммы унификации. Эти подпрограммы выполняют сопоставление целей и подцелей с фактами и головами правил для того, чтобы вычислить эти цели или подцели. Программист в соответствии с логическим синтаксисом Пролога объявляет в своей программе, какой результат должны давать заданные им факты и правила при различных подцелях, а внутренние подпрограммы унификации автоматически выполняют оставшуюся часть логического вывода.
1.6.1 Как Пролог отвечает на вопросы
Приведем неформальное объяснение того, как Пролог отвечает на вопросы. «Неформально» означает, что мы не разбираем унификационные процедуры Пролога, как вытекающие из теории ППП (предикаты первого порядка), поддержанные математической логикой и теорией алгоритмов. Вместо формального математического обоснования Пролога, мы привлекаем интерпретацию и понятные всем рассуждения «на пальцах». Говоря о Прологе «неформально», мы также не подразделяем «язык Пролог» и «программную систему Пролог».
Итак, попробуем разобраться и объяснить, как Пролог отвечает на вопросы. Мы знаем, что синтаксически вопрос к Прологу – это последовательность из одной или нескольких целей. Для того, чтобы ответить на вопрос, Пролог пытается достичь всех заявленных целей. «Достичь» – означает доказать истинность (true), сформулированную в утверждении цели (вопроса к программе). Другими словами, достичь цели – это значит показать, что она логически следует из фактов и правил программы. Если вопрос содержит переменные, то Пролог должен найти конкретные объекты, которые (будучи подставленные вместо этих переменных) обеспечивают достижение цели. Найденные Прологом конкретизации сообщаются пользователю. Если Пролог не нашел таких конкретных объектов, то ответом на вопрос будет «нет».
Вот классический пример. Пусть имеются аксиомы:
Все люди смертны.
Сократ – человек.
Тогда из этих аксиом вытекает логически следующее заключение (теорема):
Сократ – смертен.
Запишем эти рассуждения синтаксически на Прологе:
smarten(X):- chelovek(X). %все люди смертны.
chelovek(‘Сократ’). %Сократ – человек.
?- smarten(‘Сократ’). %Сократ смертен?
Yes (да)
Выполните такую программу, запустите трассировщик и сделайте пошаговую проверку процесса унификации Пролога. Задайте вопрос относительно другого лица. Убедитесь, что ответ отрицательный. Подумайте, что надо изменить в программе, чтобы она давала положительный ответ для любого лица.
1.7. Списки в Прологе
В свое время, когда создавался язык Лисп, специально ориентированный на обработку списков, он быстро стал излюбленным языком американских университетов. Множество ранних программ и систем искусственного интеллекта были разработаны ведущими университетами США именно на Лиспе. И это не случайно: списки – очень универсальная структура данных, с помощью которой можно описать самые разнообразные объекты. Например, только в области естественного языка: слова – списки букв, предложения – списки слов, тексты – списки предложений. Самолет – список его агрегатов, агрегат – список узлов, узел – список деталей и т. д.
Когда появился Пролог, язык, который, кроме удобной обработки списков, имеет еще и встроенные унификационные процедуры логического вывода, то Лисп – померк. Многие американские университеты принялись переписывать разработанные ранее интеллектуальные и экспертные системы на язык Пролог.
В этом разделе мы ознакомимся со списками, как структурой данных и с принципами их обработки на Прологе. Серьезное программирование со списками, их использование в задачах искусственного интеллекта, перенесем в следующую главу
Список – это простая структура данных, широко используемая в программировании без чисел. Список представляет собой последовательность, составленную из произвольного числа некоторых объектов. Список членов семьи может состоять, например, из четырех человек: Иванов Иван Иванович, Иванова Людмила Александровна, Петя Иванов и Лена Иванова. На Прологе это будет записываться так:
[
‘Иванов Иван Иванович’,
‘Иванова Людмила Александровна’,
‘Петя Иванов’,
‘Лена Иванова’
].
т. е. элементы списка разделяются запятой, а вначале и в конце списка ставится квадратная скобка. Однословные английские названия объектов не обязательно выделять апострофами, например, имя George можно записать списком символов как [g, e, o, r, g, e]. Заметьте, что первый символ мы написали с маленькой буквы. Объясните – почему?
Допустим пустой список: []. Если список не пустой, то в Прологе объявлен следующий синтаксис: первый элемент списка можно отделить от остальной части списка с помощью вертикальной черты, например, [g|[e,o,r,g,e]]. Такое разделение списка на два элемента называют разделением на голову и хвост. Голова – первый элемент списка, хвост – содержит остальные элементы списка. Он может быть и пустым, если исходный список состоял из одного элемента. Например, две записи: [‘Единственный элемент списка’] и [‘Единственный элемент списка’|[]] совершенно эквивалентны. Разделение списка на голову и хвост очень эффективно используется в Прологе для обработки списков. С эти мы познакомимся в следующей главе. А пока, наберите простейшую программу ввода с клавиатуры и вывода элементов списка на экран. Трассируйте и разберитесь, как в ней используются: разделение списка на голову и хвост, и унификация. Текст программы приведен в Листинге 1.2, а результаты работы показаны на рис.1.2.
|
Листинг 1.2. Обработка списков разделением на голову и хвост |
|
:- dynamic n/1. %динамический предикат (с хранимым значением аргументов)
solve_the_problem:- retractall(n(_)), %очистка памяти динамических предикатов write1, write(' N = '), n(X), write(X), %RTTI %spy(input), %пошаговая отладка выделенного предиката input(Ls), %nospy(input),%конец пошаговой отладки (нажмите n) write2(Ls), output(Ls), nl, write('- OK, by!').
%write1. input(_). write2. output(_). %стартовая отладочная заглушка
write1:- nl, write('Задайте число имен, которые вы желаете ввести: '), read(N), assert(n(N)).
input(Ls):- n(N), input2(N,Ls). %input(Ls):- input2(2,Ls).
input2(N,[]):- N =< 0, !. input2(N,Ns):- M is N - 1, input2(M,Ms), add_member_to_list(Ms,Ns).
add_member_to_list(Ms,Ns):- nl, write('Введите имя: '), read(W), append([W],Ms,Ns).
write2(Ls):- nl,write('Вы ввели список из '),length(Ls,N),write(N),write(' имен:'),nl.
output(Ls):- reverse(Ls,L2s), nl,write(L2s).
?- solve_the_problem.
|
Рис.1.2. Обработка списков с разделением на голову и хвост (листинг 1.2)
Кое что в этой программе может еще оставаться. В следующей главе мы займемся обработкой списков подробней.
Вопросы для проверки
Дайте определения алгоритмического и декларативного языков программирования.
Пролог – декларативный или алгоритмический язык?
Что означают в Прологе понятия: атом, переменная, функтор, предикат, терм, литерал, дизъюнкт? Какой их синтаксис?
Из каких основных элементов состоит пролог-программа?
Сколько целей одновременно может содержать пролог-программа?
Что такое унификация в Прологе? Как Пролог ищет ответы на вопросы?
Какие существуют представления списка в Прологе? Какой их синтаксис и семантика?
Как выглядит в Прологе список, представленный в виде «головы» и «хвоста»? Какой смысл имеют эти элементы списка?
Дискуссионные вопросы
В настоящее время сложилась парадоксальное положение с распространением Пролога в системах программирования. По существу только компания Sun серьезно занимается внедрением Пролога в языки и системы web-программирования (см. ее Пролог для взаимодействия с Java). По нашему мнению, это связано в основном с отсутствием запросов на Пролог со стороны профессионального сообщества программистов. Мы уже упоминали о том, что программировать в декларативном стиле – трудно и непривычно, как раз для программистов-профессионалов, привыкших к алгоритмическому мышлению. Но думается, что до массового увлечения Прологом просто еще не дошло дело. Ведь задать сложную логику обработки данных на Прологе значительно легче, чем писать такую логику в виде явного алгоритма на любом из универсальных алгоритмических языков.
Но крупные разработчики систем программирования могли бы поступить и так, как это сделала компания Sun, упрятав прологовские структуры в специальные классы. Правда пока еще это на привело к эффективному созданию пролог-программ, но зато были сняты многие вопросы управления памятью, в частности, очистки памяти.
А как вы думаете? Попробуйте, используя Интернет, ответить на вопрос о ближних и дальних перспективах использования Пролога в web-программировании.
Подведение итогов
В этой главе мы обсудили основные понятия Пролога: атом, переменную, функтор, предикат, терм, литерал и дизъюнкт. Мы показали, что прлог-программа состоит из фактов, правил и цели (вопроса). Последовательно можно ставить любое количество запросов, но при каждом запуске пролог-программы может присутствовать только один вопрос (цель). Подведем некоторые итоги.
Пролог предусматривает только один тип данных, называемый термом. Каждый объект в пролог-программе есть терм.
Для структурирования объектов предусмотрены функторы, имеющие размерность (арность). Увеличивая арность функтора, можно описать объект как структуру с любой степенью подробности.
Конкретные объекты предметной области задаются с помощью фактов.
Неконкретные объекты описываются с помощью правил.
Правило имеет заголовок и тело.
Заголовок правила выполняется (true) только тогда, когда выполняются все элементы тела правила.
Как факты, так и правила являются утверждениями, декларациями. Правило – это условное утверждение: условие для заголовка правила задается телом правила. Факт – это безусловное утверждение с пустым телом.
Вопросы к пролог-программе задаются с помощью структур (функторов), используемых в качестве целей.
Цель согласуется (получает значение true), если она сопоставляется (унифицируется) с каким-либо фактом или заголовком правила.
Согласование цели может вызвать целую цепочку согласования подцелей. Для каждой цели и подцели Пролог ищет подходящее для сопоставления (унификации) утверждение, каждый раз стартуя с самого начала базы данных, описываемой фактами и заголовками правил. Сопоставляя, Пролог просматривает все возможные логические варианты до тех пор, пока ему не удастся найти хотя бы одно правильное сопоставление. Принудительно (программным путем) можно заставить Пролог находить не одно, а все возможные правильные сопоставления.
Переменная – это «забронированное место». Любой терм, сколь угодно сложной структуры может заменить переменную (занять забронированное ею место).
Когда два терма сопоставляются, переменные в них заменяются на некоторые значения. Это называют означиванием переменных.
В следующей главе мы рассмотрим основные методы декларативного программирования на Прологе.
Дополнения