К сожалению, наш интерпретатор запрограммирован таким образом, что он блокирует механизм автоматических возвратов, так как для манипулирования базой данных он использует процедуры assert и retract. Это положение можно исправить, применив другой способ реализации базы данных, не требующий обращения к этим встроенным процедурам. Например, все состоять базы данных можно представить одним прологовским термом, передаваемым в процедуру пуск в качестве аргумента. Простейший способ реализации этой идеи — организовать этот терм в виде списка объектов базы данных. Тогда верхний уровень базы данных примет вид:
пуск( Состояние) :-
Условие ---> Действие,
проверить( Условие, Состояние),
выполнить( Действие, Состояние).
Задача процедуры выполнить — получить новое состояние базы данных и обратиться к процедуре пуск, подав на ее вход это новое состояние.
Проект
Запрограммируйте интерпретатор, который, в соответствии с приведенным выше замечанием, реализует базу данных как аргумент пусковой процедуры и не использует для этого внутренней базы данных пролог-системы (т.е. обходится без assert и retract). Эта новая версия интерпретатора будет допускать автоматические возвраты. Попытайтесь разработать такое представление базы данных, которое облегчало бы сопоставление с образцами.
Резюме
• Архитектура, ориентированная на типовые конфигурации (образцы), хорошо приспособлена для решения многих задач искусственного интеллекта.
• Программа, управляемая образцами, состоит из модулей, запускаемых при возникновении в базе данных тех или иных конфигураций.
• Прологовские программы можно рассматривать как частный случай систем, управляемых образцами.
• Параллельная реализация — наиболее естественный способ реализации систем, управляемых образцами. Реализация на последовательной машине требует разрешения конфликтов между модулями, содержащимися в конфликтном множестве.
• В этой главе был реализован простой интерпретатор для программ, управляемых образцами. Он был затем применен к задаче автоматического доказательства теорем пропозициональной логики.
• Были рассмотрены следующие понятия:
системы, управляемые образцами
архитектуры, ориентированные на образцы
программирование в терминах образцов
модули, управляемые образцами
конфликтное множество, разрешение конфликтов
принцип резолюции
автоматическое доказательство теорем на основе принципа резолюции
Литература
Waterman and Hayes-Roth (1978) — классическая книга по системам, управляемым образцами. В книге Nilsson (1980) можно найти фундаментальные понятия, относящиеся к задаче автоматического доказательства теорем, включая алгоритм преобразования логических формул в конъюнктивную нормальную форму. Прологовская программа для выполнения этого преобразования приведена в Clocksin and Mellish (1981).
Clocksin F. W. and Mellish С S. (1981). Programming in Prolog. Springer-Verlag. [Имеется перевод: Клоксин У., Мелиш К. Программирование на языке Пролог. — М.: Мир, 1987.]
Nilsson N. J. (1980). Principles of Artificial Intelligence. Tioga; Springer-Verlag.
Waterman D. A. and Hayes-Roth F. (1978, eds). Pattern-Directed Inference Systems. Academic Press.
Ответы к некоторым упражнениям
Глава 1
1.1
(a) no
(b) X = пат
(c) X = боб
(d) X = боб, Y = пат
1.2
(a) ?- родитель( X, пат).
(b) ?- родитель( лиз, X).
(c) ?- родитель( Y, пат), родитель( X, Y).
1.3
(a) счастлив( X) :-
родитель( X, Y).
(b) имеетдвухдетей( X) :-
родитель( X, Y),
сестра( Z, Y).
1.4
внук( X, Z) :-
родитель( Y, X),
родитель( Z, Y).
1.5
тетя( X, Y) :-
родитель( Z, Y),
сестра( X, Z).
1.6
Да. (Определение верно)
1.7
(a) возвратов не будет
(b) возвратов не будет
(c) возвратов не будет
(d) возвраты будут
Глава 2
2.1
(a) переменная
(b) атом
(c) атом
(d) переменная
(e) атом
(f) структура
(g) число
(h) синтаксически неправильное выражение
(i) структура
(j) структура
2.3
(a) успех
(b) неуспех
(c) неуспех
(d) D = 2, E = 2
(e) P1 = точка(-1, 0)
Р2 = точка( 1, 0)
Р3 = точка( 0, Y)
Такая конкретизация определяет семейство треугольников, у которых две вершины располагаются на оси x в точках 1 и -1, а третья — в произвольной точке оси у.
2.4
отр( точка( 5, Y1), точка( 5, Y2) )
2.5
регулярный( прямоугольник( точка( X1, Y1),
точка( Х2, Y1), точкa( X2, Y3),
точка( X1, Y3) ) ).
Здесь предполагается, что первая точка соответствует нижней левой вершине прямоугольника.
2.6
(a) А = два
(b) no
(c) С = один
(d) D = s(s(1));
D = s(s(s(s(s(1)))))
2.7
родственники( X, Y) :-
предок( X, Y);
предок( Y, X);
предок( Z, X),
предок( Z, Y);
предок( X, Z),
предок( Y, Z).
2.8
преобразовать( 1, один).
преобразовать( 2, два).
преобразовать( 3, три).
2.9
В случае, изображенном на рис. 2.10, пролог-система выполняет несколько больший объем работы.
2.10
В соответствии с определением сопоставления, приведенном в разд. 2.2, данное сопоставление будет успешным. X приобретает вид циклической структуры, в которой сам X присутствует в качестве одного из аргументов.
Глава 3
3.1
(a) конк( L1, [ _, _, _ ], L)
(b) конк( [ _, _, _ ], L1, L),
% Удалить 3 первые элемента L
конк( L2, [ _, _, _ ], L1)
% Удалить 3 последние элемента L1
Вот более короткий вариант, предложенный I. Tvrdy:
конк( [ _, _, _ | L2], [ _, _, _ ], L)
3.2
(а) последний( Элемент, Список) :-
конк( _, [Элемент], Список).
(b) последний( Элемент, [Элемент]).
последний( Элемент, [Первый | Остальные]):-
последний( Элемент, Остальные).
3.3
четнаядлина( [] ).
четнаядлина( [Первый | Остальные] ) :-
нечетнаядлина( Остальные).
нечетнаядлина( [ _ ] ).
нечетнаядлина( [Первый | Остальные] ) :-
четнаядлина( Остальные).
3.4
обращение( [], []).
обращение( [Первый | Остальные], ОбращСпис): -
обращение( Остальные, ОбращСписОстальных),
конк( О6ращСписОстальных, [Первый], ОбращСпис).
3.5
% Такой предикат легко определить при помощи отношения обратить
палиндром( Список) :-
обратить( Список, Список).
% Вот другое решение, не использующее обратить
палиндром1( [] ).
палиндром1( [ _ ] ).
палиндром1 [Первый | Остальные] ) :-
конк( Середина, [Первый], Остальные),
палиндром1( Середина).
3.6
сдвиг( [Первый | Остальные], Сдвинут) :-
конк( Остальные, [Первый], Сдвинут).
3.7
перевод( [], []).
перевод( [Голова | Хвост], [Голова1 | Хвост1]) :-
означает( Голова, Голова1),
перевод( Хвост, Хвост1).
3.8
подмножество( [], [] ).
подмножество( [Первый | Остальные], [Первый | Подмн]):-
% Оставить первый элемент в подмножестве
подмножество( Остальные, Подмн).
подмножество( [Первый | Остальные], Подмн) :-
% Убрать первый элемент из подмножества
подмножество( Остальные, Подмн).
3.9
разбиениесписка( [], [], []). % Разбивать нечего
разбиениесписка( [X], [X], []).
% Разбиение одноэлементного списка
разбиениесписка( [X, Y | Список], [X | Список1],
[Y | Список2]) :-
разбиениесписка( Список, Список1, Список2).
3.10
можетзавладеть( состояние( _, _, _, имеет), [] ).
% Ничего не надо делать
можетзавладеть( Состояние, [Действие | Действия]):-
ход( Состояние, Действие, НовоеСостояние),
% Первое действие
можетзавладеть( НовоеСостояние, Действия).
% Оставшиеся действия
3.11
