Поиск с возвратом для внутреннего целевого утверждения

Вот еще один, слегка усложненный пример, иллюстрирующий, как в Про-

логе происходит поиск с возвратом.

/* Program CH05EX05.PRO */

predicates

type(symbol, symbol)

is_a(symbol, symbol)

lives(symbol, symbol)

can_swim(symbol)

goal

can_swim(What) ,

write("A ", What, " can swim.").

clauses

type(ungulate, animal).

type(fish, animal).

is_a(zebra, ungulate).

is_a(herring, fish).

is_a(shark, fish).

lives(zebra, on_land).

lives(frog, on_land).

lives(frog, in_water).

lives(shark, in_water).

can_swim(Y) :-

type(X, animal) ,

is_a(Y, X) ,

lives(Y, in_water).

Данный пример программы использует внутреннее целевое утверждение, с

тем чтобы приллюстрировать, как работает поиск с возвратом. После того

как программма скомпилирована и запущена, Турбо Пролог автоматически нач-

нет выполнение целевого утверждения, пытаясь согласовать все подцели в

разделе программы goal.

1. Турбо Пролог обращается к предикату can_swim со свободной пере-

менной What. Пытаясь выполнить это обращение, Турбо Пролог просмат-

ривает программу в поисках соответствия. Он обнаруживает соответст-

вие с предложением, определяющим can_swim, и переменная What унифи-

цируется с переменной Y.

2. Затем Турбо Пролог пытается согласовать тело правила. При этом

Турбо Пролог обращается к первой подцели в теле правила, type(X,

animal) , и ищет соответствие для этого обращения. Он обнаруживает

соответствие с первым фактом, определяющим отношение type.

3. В этот момент Х связывается с ungulate. Поскольку здесь налицо

более, чем одно возможное решение, Турбо Пролог проставляет точку

возврата возле факта type(ungulate, animal).

4. Имея Х, связанным с ungulate, Турбо Пролог производит обращение

ко второй подцели в правиле ( is_a(Y,ungulate) ) и снова ищет соот-

ветствие. Он находит его с первым фактом, is_a(zebra, ungulate). Y

связывается с zebra, и Пролог выставляет точку возврата около

is_a(zebra, ungulate).

5. Теперь, имея Х, связанным с ungulate, и Y - с zebra, Пролог пыта-

ется согласовать последнюю подцель, lives(zebra, in_water). Пролог

проверяет каждое предложение lives, но в программе нет предложения

lives(zebra, in_water), поэтому обращение завершается неудачно и

Пролог начинает поиск с возвратом другого решения.

6. Когда Турбо Пролог совершает обратный ход, процесс возвращается к

последней позиции, где была помещена точка возврата. В данном случае

последняя точка возврата была поставлена у второй подцели в правиле,

на факте is_a (zebra, ungulate).

7. При достижении точки возврата Турбо Пролог освобождает перемен-

ные, которым были присвоены новые значения после последней точки

возврата, и пытается найти другое решение для обрабатываемого обра-

щения. В данном случае обращение было is_a (Y, ungulate).

8. Tурбо Пролог продолжает спуск по предложениям в поиске другого

соответствующего предложения, начиная с того места, где поиск был

прекращен. Так как в программе больше нет соответствующих предложе-

ний, обращение завершается неудачно, и Турбо Пролог вновь ведет по-

иск с возвратом в попытке решить исходное целевое утверждение.

9. Для теперешней позиции последней точкой возврата является

type(ungulate, animal).

10.Турбо Пролог освобождает переменные, использованные в исходном

обращении, и пытается найти другое решение для обращения type(X,

animal). Поиск начинается после точки возврата. Турбо Пролог находит

соответствие со следующим фактом type в программе

(type(fish,animal)); X связывается с fish, и новая точка возврата

ставится возле этого факта.

11.Теперь Турбо Пролог продвигается вниз, к следующей подцели в пра-

виле; поскольку это уже новое обращение, поиск начинается с вершины

программы для is_a(Y,fish).

12.Турбо Пролог находит соответствие для этого обращения, и Y стано-

вится связанным с herring.

13.Tак как Y теперь связан с herring, следующая подцель, к которой

происходит обращение, суть lives(herring,in_water) Это опять-таки

новое обращение, и поиск начинается с вершины программы.

14.Турбо Пролог исследует каждый факт lives, но не находит соответс-

твия, и подцель не выполняется.

15.Теперь Турбо Пролог возвращается к последней точке возврата is _a

(herring, fish).

16.Переменные, которые были связаны этим сопоставлением, не освобож-

дены. Начиная с того места, где процесс был прекращен, Турбо Пролог

теперь ищет новое решение для обращения is_a(Y, fish).

17. Турбо Пролог находит соответствие со следующим предложением

is_a, Y становится связанным с идентификатором shark.

18.Турбо Пролог опять исследует последнюю подцель, имея переменную

Y, связанную с shark. Он выполняет обращение lives(shark, in_water);

поиск начинается с вершины программы, так как это уже новое обраще-

ние. Он обнаруживает соответствие, и последняя для правила подцель

выполняется.

19.К этому моменту тело правила can_swim(Y) согласовано. Турбо Про-

лог возвращает Y обращению can_swim(What). Tак как What связана с Y,

a Y связан с shark, отныне в целевом утверждении What связана с

shark.

20.Турбо Пролог продолжает процесс с того места в разделе goal, где

он был остановлен, и обращается ко второй подцели в целевом утверж-

дении.

21.Турбо Пролог завершает программу выводом:

A shark can swim.

Программа закончена успешно.

|------------------------------------|

| ПРАВИЛО: can_swim(What) :- | What унифицировано с Y.

| type(X,animal), |

| is_a(What,X), |

| lives(What,in_water). |

|------------------------------------|

|-------------------------------------|

* | ОБРАЩЕНИЕ : type(X,animal) | Х связан с ungulate

: | СООТВЕТСТВИЕ: type(ungulate,animal) |

: |---------------------------------|---|

: |

: v

: |-------------------------------------|

: * | ОБРАЩЕНИЕ : is_a(Y,ungulate) | Y связан с zebra

: : | СООТВЕТСТВИЕ: is_a(zebra,ungulate) |

: : |---------------------------------|---|

: : |

: : v

: : |-----------------------------------|

: : | ОБРАЩЕНИЕ : lives(zebra,in_water) | Не согласуется

: : | НЕУДАЧА : lives(zebra,in_water) |

: : |--|--------------------------------|

: : |

: : |

: : v

: : |-----------------------------------|

: :.| ЕЩЕ РАЗ : is_a(Y,ungulate) | Больше нет фактов,

: | НЕУДАЧА : is_a(Y,ungulate) | соответствующих

: |--|--------------------------------| обращению

: |

: |

: v

: |-------------------------------------|

:.| ЕЩЕ РАЗ : type(X,animal) |Х теперь связан с fish

| СООТВЕТСТВИЕ: type(fish,animal) |

|---------------------------------|---|

|

v

|-----------------------------------|

* | ОБРАЩЕНИЕ : is_a(Y,fish) | Y теперь связан с

: | СООТВЕТСТВИЕ: is_a(herring,fish) | herring

: |---------------------------------|-|

: |

: v

: |-------------------------------------|

: | ОБРАЩЕНИЕ : lives(herring,in_water) | Не согласуется

: | НЕУДАЧА : lives(herring,in_water) |

: |--|----------------------------------|

: |

: |

: v

: |-----------------------------------|

:.| ЕЩЕ РАЗ : is_a(Y,fish) | Теперь Y связан с

| СООТВЕТСТВИЕ: is_a(shark,fish) | shark

|---------------------------------|-|

|

v

|--------------------------------------|

| ОБРАЩЕНИЕ : lives(shark,in_water) | What связано

| СООТВЕТСТВИЕ : lives(zebra,in_water) | с shark

|--------------------------------------|

Рис. 5.1 : Как работает программа can_swim