ПРЕДЛОЖЕНИЯ НУЛЬ УСТАНОВИТЬ ПРЕДЛОЖЕНИЯ ЧТСП

11 (ДАЕТ-МОЛОКО < §> ИМЕЕТ-ВОЛОС-ПОКРО81 @

12 ИМЕЕТ-В0Л0С-П0КР082 ф ИМЕЕТ-РОГА @ МЛЕКОПИТАЮЩЕЕ

13 @ К03ЕЛ1 < §> К03ЕЛ2 < §> КОЗЕЛЗ @ )

U РЕШЕНИЯ НУЛЬ УСТАНОВИТЬ ЦЕЛИ НУЛЬ УСТАНОВИТЬ
15 НУЛЬ КОЗЕЛ ЦЕЛИ СПИСОК

Экран 71. Расширенная база знаний

она вносит в вершину стека флаг, предназначенный для UNTIL в
слове ПОИСК. При ложном значении флага поиск продолжается,
при истинном - завершается и на стек помещается следующий
флаг, означающий успех или неудачу.

Для самой внешней конструкции IF-ELSE-THEN в слове
(ПОИСК) «гтвь ELSE выбирается тогда, когда список ЦЕЛИ пуст.
На стеке остаются два флага: первый для завершения, второй для
обозначения успеха. Слово ВОЗВРАТ, стоящее перед IF-THEN,
осуществляет манипуляции с флагом. При успешном завершении
ВОЗВРАТА оно передает истинное значение флага, ПОИСК не
завершает свое выполнение и выдает ложный флаг. Если же. воз-
врат заканчивается неудачей, возвращается ложный флаг и в сте-
ке остаются флаги в таком порядке: ложь-истина.

Слова НАЙТИ-ПРЕДЛОЖЕНИЕ? и ЮЗВРАТ приводятся на
экране 61. Как (ПОИСК), так и ВОЗВРАТ используют слово
НАЙТИ-ПРЕДЛОЖЕНИЕ?, а оно в свою очередь - слово НАЙ-
ТИ-ПРЕДЛОЖЕИИЕ, изображенное на экране 60, для фактичес-
кого поиска подходящего предложения. НАЙТИ-ПРЕДЛОЖЕНИЕ
получает цель и указатель на ПРЕДЛОЖЕНИЯ, а затем ищет
предложение, заголовок которого сопоставим с целью. Если под-
ходящее предложение обнаруживается, то в стек помещается как
цель, так и указатель на выбранное предложение. Поскольку ПРЕ-
ДЛОЖЕНИЯ есть список предложений, каждое из которых само

204

ЦЕЛИ: (КОЗЕЛ)
РЕШЕНИЯ: НУЛЬ

ЦЕЛИ: (БОРЬКА)
РЕШЕНИЯ: (КОЗЕЛ БОРЬКА)

ЦЕЛИ: (МЛЕКОПИТАЮЩЕЕ ИМЕЕТ-РОГА)
РЕШЕНИЯ: (КОЗЕЛ МЛЕКОПИТАЮЩЕЕ ИМЕЕТ-РОГА)

ЦЕЛИ: (ДАЕТ-МОЛОКО ИМЕЕТ-ВОЛОС-ПОКРОВ ИМЕЕТ-РОГА)
РЕШЕНИЯ: (МЛЕКОПИТАЮЩЕЕ ДАЕТ-МОЛОКО

ИМЕЕТ-ВОЛОС-ПОКРОВ)

(КОЗЕЛ МЛЕКОПИТАЮЩЕЕ ИМЁЕТ-РОГА)

ЦЕЛИ: (ИМЕЕТ-ВОЛОС-ПОКРОВ ИМЕЕТ-РОГА)
РЕШЕНИЯ: (ДАЕТ-МОЛОКО)

(МЛЕКОПИТАЮЩЕЕ ДАЕТ-МОЛОКО ИМЕЕТ-ВОЛОС-ПОКРОВ)

(КОЗЕЛ МЛЕКОПИТАЮЩЕЕ ИМЕЕТ-РОГА)

ЦЕПИ: (ИМЕЕТ-РОГА)

РЕШЕНИЯ: (ИМЕЕТ-ВОЛОС-ПОКРОВ) (ДАЕТ-МОЛОКО)

(МЛЕКОПИТАЮЩЕЕ ДАЕТ-МОЛОКО ИМЕЕТ-ВОЛОС-ПОКРОВ)

(КОЗЕЛ МЛЕКОПИТАЮЩЕЕ ИМЕЕТ-РОГА)

ЦЕЛИ: НУЛЬ

РЕШЕНИЯ: (ИМЕЕТ-РОГА) (ИМЕЕТ-ВОЛОС-ПОКРОВ)

(ДАЕТ-МОЛОКО)

(МЛЕКОПИТАЮЩЕЕ ДАЕТ-МОЛОКО

ИМЕЕТ-ВОЛОС-ПОКРОВ)

(КОЗЕЛ МЛЕКОПИТАЮЩЕЕ ИМЕЕТ-РОГА)

УСПЕШНОЕ ЗАВЕРШЕНИЕ

Рис. 9.3. Сл е д поиска

является списком, указатель на ПРЕДЛОЖЕНИЯ будет с т латься
на некоторый список, например такой:

((КОЗЕЛ БОРЬКА)

(КОЗЕЛ МЛЕКОПИТАЮЩЕЕ ИМЕЕТ РОГА))

что соответствует второму фрейму на рис. 9.4.

Чтобы получить заголовок первого предложения этого " уре-
занного" (посредством слова ХВОСТ) списка ПРЕДЛОЖЕНИЯ,
потребуется два раза применить слово ПЕРВЫЙ. После первого
применения возвратится первое предложение, после второго - его
заголовок. Затем указатель на заголовок предложения в теле
НАЙТИ-ПРЕДЛОЖЕНИЕ будет сравниваться (посредством = ) с

                                                      205

целью. Так как имя данной цели и указатель на нее представляет
собой простую переменную Форта, то для сравнения можно вос-
пользоваться операцией =. (В полном Прологе операция = замене-

62

0 \ ИНТЕРПРЕТАТОР ПРАВИЛ ПРОЛОГА

1 ( -> ФЛАГ ИСТИНА|ЛОЖЬ) \ ФЛАГ=ИСТИНА => УСПЕШНОЕ

2 3 4 5 6 7 8 9 10 11 12 13 14 15

\ ЗАВЕРШЕНИЕ
(ПОИСК)

ЦЕЛИ @ НОЛЬ NOT
IF ПОЛУЧИТЬ-ЦЕЛЬ ПРЕДЛОЖЕНИЯ @ НАЙТИ-ПРЕДЛОЖЕНИЕ?

IF ДОБАВИТЬ-ЦЕЛИ FALSE

ELSE ВОЗВРАТ

IF FALSE ELSE FALSE TRUE THEN

THEN

ELSE TRUE DUP
THEN

Экран 62. Интерпретатор правил Пролога: (ПОИСК)

Слово ВОЗВРАТ прежде всего восстанавливает цель и указа-
тель на предложение (последний отмечает точку возврата в
списке ПРЕДЛОЖЕНИЯ) из списка РЕШЕНИЯ, а затем устанав-
ливает его в качестве нового значения в хвост списка РЕШЕНИЯ,
т.е. оно продвигается по списку через два элемента, удаляя
только что восстановленные цель и указатель на предложение. Да-
лее, чтобы возобновить поиск цели, начиная с указателя пред-

60
0 \ ИНТЕРПРЕТАТОР ПРАВИЛ ПРОЛОГА

1

2 20 НОВСПИСОК ЦЕЛИ

3 20 НОВСПИСОК РЕШЕНИЯ                                                    

4 200 НОВСПИСОК ПРЕДЛОЖЕНИЯ
5

6 7 8 9 10 11 12 13 14 15

( -> ЦЕЛЬ)

: ПОЛУЧИТЬ-ЦЕЛЬ ЦЕЛИ @  DUP ПЕРВЫЙ SWAP ХВОСТ
ЦЕЛИ SWAP УСТАНОВИТЬ;

( ЦЕПЬ ©ПРЕДЛОЖЕНИЯ1 -> ЦЕЛЬ @ПРЕДЛОЖЕНИЯ2)
: НАЙТИ-ПРЕДЛОЖЕНИЕ

BEGIN 2DUP ПЕРВЫЙ ПЕРВЫЙ DUP > R • R> НОЛЬ OR NOT
WHILE ХВОСТ
REPEAT

 

на операцией UNIFY (УНИФИКАЦИЯ), объяснение которой при-
водится ниже.) Если сопоставления не произошло, а в списке еще
остались элементы, то указатель хвоста предложений переместится
на следующее предложение и сравнение повторится. После того
как слово НАЙТИ-ПРЕДЛОЖЕНИЁ завершит свое выполнение,
оно возвратит указатель. Если ни одно из сравнений не сработало,
этот указатель будет ссылаться на пустой список предложений.

Слово НАЙТИ-ПРЕДЛОЖЕНИЕ? проверяет, не является ли
возвращенный список (указатель) НУЛЕМ (применяя НОЛЬ) и
помещает копию полученного флага (используя > R) в стек возвра-
тов. Если поиск закончился неудачей, стек очищается, и флаг пе-
редается снова. Если же поиск прошел успешно, то как цель, так и
указатель предложения связываются в список РЕШЕНИЯ. Таким
образом, структура списка РЕШЕНИЯ следующая:

(цель, указатель-предложения₁ цеяь₂ указатель-
предложения ₂... цель _n указатель-предложения_п)

На рис. 9.4 показано только первое предложение из оставшей-
ся части списка ПРЕДЛОЖЕНИЯ, на которое ссылается указатель
предложения.

61

0 \ ИНТЕРПРЕТАТОР ПРАВИЛ ПРОЛОГА

1 ( ЦЕЛЬ @ ПРЕДЛОЖЕНИЕ -> ФЛАГ) \ ПОИСК

 

2 \ ПОДХ.ПРЕДЛОЖЕНИЯ И ПОМЕЩ. В РЕШЕН.

3 \ ФЛАГ ИСТИНЕН, ЕСЛИ ПРЕДЛОЖЕНИЕ НАЙДЕНО

4: НАЙТИ-ПРЕДЛОЖЕНИЕ? НАЙТИ-ПРЕДЛОЖЕНИЕ

5 DUP НОЛЬ DUP > R

6 IF 2DR0P

7 ELSE РЕШЕНИЯ СВЯЗЬ РЕШЕНИЯ СВЯЗЬ

8 THEN R> NOT;

9: ДОБАВИТЬ-ЦЕЛИ РЕШЕНИЯ @ ХВОСТ ПЕРВЫЙ

10 ПЕРВЫЙ ХВОСТ ЦЕЛИ 2С0ЕД;

11 ( -> ФЛАГ) \ ФЛАГ - ЛОЖЬ, ЕСЛИ СПИСОК РЕШЕНИЯ ПУСТ

12: ВОЗВРАТ РЕШЕНИЯ @ DUP ПЕРВЫЙ SWAP

 

13 ХВОСТ ПЕРВЫЙ ХВОСТ РЕШЕНИЯ DUP @ ХВОСТ ХВОСТ

14 УСТАНОВИТЬ НАЙТИ-ПРЕДЛОЖЕНИЕ? DUP

I F ДОБАВИТЬ-ЦЕЛИ THEN;

Экраны 60, 61. Интерпретатор правил Пролога: ПОЛУЧИТЬ-ЦЕЛЬ,
НАЙТИ-ПРЕДЛОЖЕНИЕ, НАЙТИ-ПРЕДЛОЖЕНИЕ? и ВОЗВРАТ

 

206

207

ЦЕЛИ:   (КОЗЕЛ)
РЕШЕНИЯ: НУЛЬ

ЦЕЛИ:   (БОРЬКА)
РЕШЕНИЯ: (КОЗЕЛ БОРЬКА)

ЦЕЛИ:   (ГРУБИЯН)
РЕШЕНИЯ: (КОЗЕЛ ГРУБИЯН)

ЦЕЛИ:   (МЛЕКОПИТАЮЩЕЕ ИМЕЕТ-РОГА)
РЕШЕНИЯ: (КОЗЕЛ МЛЕКОПИТАЮЩЕЕ ИМЕЕТ-РОГА)

ЦЕЛИ:   (ДАЕТ-МОЛОКО ИМЕЕТ-ВОЛОС-ПОКРОВ ИМЕЕТ-РОГА)
РЕШЕНИЯ: (МЛЕКОПИТАЮЩЕЕ ДАЕТ-МОЛОКО

ИМЕЕТ-ВОЛОС ПОКРОВ)
(КОЗЕЛ МЛЕКОПИТАЮЩЕЕ ИМЕЕТ-РОГА)

ЦЕЛИ:   (ИМЕЕТ-ВОЛОС-ПОКРОВ ИМЕЕТ-РОГА)
РЕШЕНИЯ: (ДАЕТ-МОЛОКО)

(МЛЕКОПИТАЮЩЕЕ ДАЕТ-МОЛОКО
ИМЕЕТ-ВОЛОС- ПОКРОВ)

(КОЗЕЛ МЛЕКОПИТАЮЩЕЕ ИМЕЕТ-РОГА)

ЦЕЛИ:   (ГРУБИЯН ИМЕЕТ-РОГА)

РЕШЕНИЯ: (ИМЕЕТ-ВОЛОС-ПОКРОВ ГРУБИЯН)

(ДАЕТ-МОЛОКО)

(МЛЕКОПИТАЮЩЕЕ ДАЕТ-МОЛОКО
. ИМЕЕТ-ВОЛОС-ПОКРОВ)

(КОЗЕЛ МЛЕКОПИТАЮЩЕЕ ИМЕЕТ-РОГА)

ЦЕЛИ:   (ИМЕЕТ-РОГА)

РЕШЕНИЯ: (ИМЕЕТ-ВОЛОС-ПОКРОВ)

(ДАЕТ-МОЛОКО)

(МЛЕКОПИТАЮЩЕЕ ДАЕТ-МОЛОКО
ИМЕЕТ-ВОЛОС-ПОКРОВ)

(КОЗЕЛ МЛЕКОПИТАЮЩЕЕ ИМЕЕТ-РОГА)

ЦЕЛИ: НУЛЬ

РЕШЕНИЯ: (ИМЕЕТ-РОГА ИМЕЕТ-ВОЛОС-ПОКРОВ)

(ДАЕТ-МОЛОКО)

(МЛЕКОПИТАЮЩЕЕ ДАЕТ-МОЛОКО
ИМEЕТ-ВОЛОС-ПОКРОВ)

(КОЗЕЛ МЛЕКОПИТАЮЩЕЕ ИМЕЕТ-РОГА)

УСПЕШНОЕ ЗАВЕРШЕНИЕ

Рис. 9.4. Еще одна трасса выполнения слова ПОИСК с возвратом в
первых двух фреймах

208

ложения, ВОЗВРАТ вызывает слово НАЙТИ-ПРЕДЛОЖЕНИЕ.
При успешном завершении поиска новые цели из подобранного
предложения посредством вызова ДОБАВИТЬ-ЦЕЛИ добавляются
к списку ЦЕЛИ. Если подходящего предложения не оказалось,
поиск завершается неудачей. ВОЗВРАТ возвращает в стек флаг,
означающий успех или неудачу.

Теперь нам осталось лишь объяснить два второстепенных
слова из определения ПОИСК. Слово ДОБАВИТЬ-ЦЕЛИ выбира-
ет цели из списка, на который ссылается первый указатель
предложения, и присоединяет его к списку ЦЕЛИ. Достижение це-
лей в списке РЕШЕНИЯ нетривиально - чередованием слов ПЕР-
ВЫЙ и ХВОСТ. Выражение РЕШЕНИЯ @ ХВОСТ осуществляет
перемещение за первую цель в списке РЕШЕНИЯ, возвращая в
качестве результата оставшуюся часть данного списка. Затем слово
ПЕРВЫЙ возвращает список, содержащий предложения, - урезан-
ный посредством слова ХВОСТ список ПРЕДЛОЖЕНИЯ. Следую-
щее вхождение слова ПЕРВЫЙ возвращает первое предложение из
этого списка, а последнее слово ХВОСТ перемещается за заголо-
вок. Оставшаяся часть представляет собой список, содержащий
цели первого предложения.

Слово ПОЛУЧИТЬ-ЦЕЛЬ восстанавливает первый элемент из
списка ЦЕЛИ и удаляет его, превращая этот список в его хвост.
Помимо перечисленных слов, нам требуются три списка, которые
занимают небольшой объем памяти и показаны на экране 60.

Кроме собственно слова ПОИСК, на экранах с 63 го по 65-й
описаны несколько дополнительных слов для пользовательского
интерфейса и отладки. В Прологе запрос цели может быть осуще-
ствлен следующим образом:

? - цель

Здесь приводится еще одно похожее слово, которому, правда,
нужно задавать список целей. Чтобы доказать цель, нужно
набрать:

? -(ЦЕЛЬ)

Слово? - для получения списка целей, находящихся в списке
ЦЕЛИ, использует слово ЧТСП. Это слово опустошает список
РЕШЕНИЯ, подготавливая его для нового поиска. Ответом на
запрос будет лиое УСПЕХ, либо НЕУДАЧА- Если вы хотите уви-
деть следы поиска, то можно встроить в? - слово СЛЕД (как было
показано ранее), для чего необходимо выполнить переустановку
вектора вычисления ВЫВОД на СЛЕД:

^‘ СЛЕД IS ВЫВОД

В исходном состоянии вектор ВЫВОД установлен на слово
ПОИСК, которое не оставляет следов.

209

63

О Ч ИНТЕРПРЕТАТОР ПРАВИЛ ПРОЛОГА
1

2 ( -> ФЛАГ) \ ФЛАГ * ИСТИНА => УСПЕХ

3: ПОИСК

BEGIN (ПОИСК)

5 UNTIL
в;

7

8 DEFER ВЫВОД ' ПОИСК IS ВЫВОД

в

10: ? - РЕШЕНИЯ НУЛЬ УСТАНОВИТЬ ЦЕЛИ OUP НУЛЬ

11 УСТАНОВИТЬ ЧТСП ВЫВОД СЯ П ВЫВОД > ВО0У @ П

12 ПОИСК f \ УСТАНОВЛЕН ЛИ ВЫВОД НА ПОИСК?

13 IF

14   IF, " УСПЕХ" ELSE." НЕУДАЧА" THEN

15 THEN;
64

О \ ИНТЕРПРЕТАТОР ПРАВИЛ ПРОЛОГА
1

2 \ МАКСИМУМ ЦЕЛЕЙ В ПРАВИЛЕ « 4

3: ПРАВИЛО: CREATE HERE OUP 2+, НУЛЬ, 10 ALLOT ЧТСП;
4

 

5; , КЛ ПРЕДЛОЖЕНИЯ ф ВЫДАТЬ;

6! .ЦЕЛИ ЦЕЛИ @  ВЫДАТЬ;
7

8: КАК? РЕШЕНИЯ @ OUP НОЛЬ

9 IF ВЫДАТЬ

ELSE

11 BEGIN OUP НОЛЬ NOT

12 WHILE DUP ХВОСТ ПЕРВЫЙ ПЕРВЫЙ ВЫДАТЬ ХВОСТ ХВОСТ

13 REPEAT DROP

14 THEN
15;

65

0 \ ИНТЕРПРЕТАТОР ПРАВИЛ ПРОЛОГА

1: ДОСТАТОЧНО? KEY?

2          IF KEY DROP KEY 13 «

3              ELSE FALSE

4         THEN

5;
6

7 \ СЛЕДЫ ПОИСКА

8: СЛЕД

9 BEGIN CR. * ЦЕЛИ: " ЦЕЛИ @ ВЫДАТЬ

10 CR." РЕШЕНИЯ: " КАК? CR (ПОИСК) DUP > R

11 IF

12        IF." УСПЕХ" ELSE." НЕУДАЧА" CR THEN

13      THEN R> ДОСТАТОЧНО? OR

14   UNTIL
15;

Экраны 63, 64, 65, Интерпретатор правил Пролога: ПОИСК, ? -,
ПРАВИЛО:, -КЛ, , ЦЕЛИ, КАК?, ДОСТАТОЧНО? и СЛЕД

Описание слова СЛЕД приведено на экране 65.. Оно ана-
логично слову ПОИСК, но на каждом шаге выдает фреймы
списков ЦЕЛИ и РЕШЕНИЯ. Имеется также слово ДОСТАТОЧ-
НО?, которое позволяет управлять выводом следов с клавиатуры.
Если во время вывода следов вы нажмете любую клавишу, то
трассировка приостановится до следующего нажатия любой кла-
виши, исключая клавишу < ВК>. Если во время паузы вы нажмете
клавишу < ВК>, слово СЛЕД завершит свое выполнение.

С помощью слова КАК? СЛЕД печатает первое предложение
из списка РЕШЕНИЯ. Слово.КЛ упрощает вывод списка ПРЕД-
ЛОЖЕНИЯ, а слово.ЦЕЛИ - списка ЦЕЛИ. Слово ПРАВИЛО:
упрощает составление правил (см.экраны 70 и 71). Формат его
применения таков:

ПРАВИЛО: имя-предложения список

Здесь список считывается внутри слова ПРАВИЛО: посредством
ЧТСП. Чтобы минимизировать число имен, имя заголовка предло-
жения должно совпадать с именем предложения (например, МЛЕ-
КОПИТАЮЩЕЕ или ДАЕТ-МОЛОКО на экране 70). В данной
реализации правило может содержать до четырех целей, по-
скольку для него выделено всего 10 байт: два на заголовок и
восемь на цели.

ДЕРЕВЬЯ ВЫВОДА

Дерево вывода облегчает процесс слежения за выполнением
поиска. На рис.9.5 изображено дерево вывода Для следа, показан-
ного на рис.9.3. Это графическая иллюстрация последовательности
вывода, где каждый шаг представлен в виде узла, и все узлы про-
нумерованы в порядке следования фреймов. Цели правила соеди-
нены с соответствующими предложениями линиями. Структура де-
рева отражает общий алгоритм поиска, а его уровни - ход пост-
роения цепочек интерпретатором правил.

На верхнем уровне задана цель КОЗЕЛ. Поиск подходящего
предложения приводит нас к правилу 2 на следующем уровне. По-
скольку данное предложение не подходит, происходит возврат на
верхний уровень и выбирается следующее предложение, в резуль-
тате чего мы выходим на правило 3. Правило 3 определяет цели
МЛЕКОПИТАЮЩЕЕ и ИМЕЕТ-РОГА, что ведет к поиску на оче-
редном уровне. Обратите внимание на то, что вид логических
отношений между узлами чередуется через уровень. На верхнем
уровне, если задано несколько целей, все они для успешного
завершения общего поиска должны быть удовлетворены. Каждая
цель может рассматриваться как подзадача, и для того чтобы
общая задача была решена, необходимо решить все подзадачи.

 

210

211

Таким образом, логические отношения между целями на верхнем уровне представляют собой конъюнкцию.

 

 

Рис. 9.5. Дерево вывода для цели КОЗЕЛ, показывающ чередование уровней ветвлений типа И и ИЛИ. Числа указывают порядок
использования предложений

Если же спуститься уровнем ниже, то здесь каждая ветвь' ото-
бражает альтернативное предложение, и для успешного заверше-
ния поиска требуется, чтобы успешно завершилось хотя бы одно из
ник, т.е. должен благополучно завершиться вывод в узле 2 или в
узле 3. На этом уровне логические отношения между узлами
определяются как дизъюнкция. На следующем уровне обе цели
МЛЕКОПИТАЮЩЕЕ и ИМЕЕТ-РОГА должны быть достигнуты -
вствй логически конъюнктивны (дуга, соединяющая линии, пока-
зывает, что они логически связаны конъюнкцией). Итак, с одной
стороны, дерево вывода графически представляет сосгояние памяти
во время пояска, а с другой - показывает путь разбиения задачи
достижения цели верхнего уровня на подзадачи.

⇐ Предыдущая21222324252627282930Следующая ⇒

Поделиться: