Упражнение

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