Упражнение
2.9. Рассмотрите программу, приведенную в листинге 2.1, и промоделируйте в стиле этого листинга выполнение системой Prolog процедуры поиска ответа на следующий вопрос: ?- big ( х) , dark ( X) .
Сравните полученную трассировку выполнения с приведенной в листинге 2.1,
когда вопрос был по сути тем же самым, но цели были представлены в другом
порядке:
?- darkt X), big( X).
В каком из этих двух случаев системе Prolog пришлось выполнить больше работы, прежде чем найти ответ?
Глава 2. Синтаксис и значение программ Prolog
Листинг 2.2. Процедура выполнения целей Prolog
procedure execute ( Program, GoalList, Success); Входные параметры;
Program- список предложений
GoalList - список целей Выходкой параметр:
Success - истинностное значение; параметр Success становится равным true, если GoalList равен true применительно к Program Локальные переменные:
Goal - цель
OtherGoals - список целей
Satisfied - истинностное значение
MatchOK - истинностное значение
Instant - конкретизация переменных
Н, В', Б1, BI ' , ...,Бп, Е::' - цели Вспомогательные функции:
empty(L) - возвращает значение true, если L - пустой список
head(L) - возвращает первый элемент списка
tail(L) - возвращает остальную часть списка L
append(Ll,L2) - добавляет список L2 к концу списка L1
match(Т1,Т2,MatchOK,Instant) - предпринимает попытки согласовать термы Т1 и
12; в случае успеха MatchOK становится равным true,a Instant содержит соответствующую конкретизацию переменных
substitute(Instant,Goals) - выполняет подстановку переменных в Goals в
соответствии: с конкретизацией Instant
Begin
if empty(GoalList) thenSuccess := true else begin
Goal := head(GoalList); OtherGoals := tail(GoalList); Satisfied :- false;
while notSatisfied and"в программе имеются другие предложения" do begin
Допустим, что следующим предложением в Program является
Н :- В1, ..., Вп. Сформировать вариант этого предложения
Н" :- В1 ' , ... , Вп' . match(Goal,H',MatchOK,Instant); if MatchOK thenbegin
NewGoals := append([Bl',.. .,Bn'], OtherGoals); NewGoals :«• substitute (Instant,NewGoals) ,-execute(Program,NewGoals,Satisfied) endend; Success := Satisfied end end;
2.5. Пример: обезьяна и банан
Задача с обезьяной и бананом используется как простой пример решения проблемы. Приведенная в данном разделе программа Prolog, предназначенная для решения этой задачи, показывает, каким образом а подобных упражнениях могут использоваться механизмы согласования и перебора с возвратами. Вначале программа будет разработана непроцедурным способом, а затем подробно исследовано ее процедурное поведение. Предполагается, что эта программа должна быть компактной и наглядной.
Часть I. Язык Prolog
В данном разделе используется следующий вариант задачи. Перед дверью, ведущей в комнату, находится обезьяна. Б середине комнаты с потолка свисает банан. Обезьяна голодна и хочет получить банан, но не может дотянуться до него с пола. У окна комнаты стоит ящик, которым может пользоваться обезьяна. Обезьяна может выполнять следующие действия: ходить по полу, залезать на ящик, передвигать ящик (если она уже находится рядом с ящиком) и срывать банан, если она стоит на ящике непосредственно под бананом. Может ли обезьяна получить этот банан?
Одной из важных задач в программировании является поиск одного из представлений проблемы в терминах используемого языка программирования. В данном случае можно всегда рассматривать "мир, в котором существует обезьяна", как находящийся в определенном состоянии, которое может изменяться во времени. Текущее состояние определяется положением объектов. Например, начальное состояние этого мира описано ниже.
1. Обезьяна находится у двери.
2. Обезьяна находится на полу.
| i |
3. Ящик стоит у окна. 4. Обезьяна не имеет банана. Было бы удобно объединить все эти четыре фрагмента информации в один структурированный объект. Выберем в качестве функтора слово state (состояние), чтобы все четыре компонента описания состояния хранились вместе. На рис. 2.10 изображено начальное состояние, представленное как структурированный объект,
State