1. Сопоставление и унификация
Рассмотрим программу ch04e01.pro (рис.1) с точки зрения того, как утилита Test Goal будет отыскивать все решения следующей цели written_by(X, Y).

domains

title, author = symbol

pages= unsigned

predicates

book(title, pages)

written_by(author, title)

long_novel (title)

clauses

written_by(fleming, "DR NO").

written_by(melville, "MOBY DICK").

book("MOBY DICK", 250).

book("DR NO", 310).

long_novel (Title) :-

written_by(_, Title),

book(Title, Length),

Length > 300.

Листинг программы ch04e01.pro

Пытаясь выполнить целевое утверждение written_by(X, Y), Visual Prolog должен проверить каждое предложение written_by(X, Y) в программе. Сопоставляя аргументы X и Y с аргументами каждого предложения written_by, Visual Prolog выполняет поиск от начала программы до ее конца. Обнаружив предложение, соответствующее целевому утверждению, Visual Prolog присваивает значения свободным переменным таким образом, что целевое утверждение и предложение становятся идентичными. Говорят, что целевое утверждение унифицируется с предложением. Такая операция сопоставления называется унификацией.

Поскольку X и Y являются свободными переменными в целевом утверждении, а свободная переменная может быть унифицирована с любым другим аргументом (и даже с другой свободной переменной), то целевое утверждение может быть унифицировано с первым предложением written_by в программе, как показано ниже:

written_by (X,Y).

written_by(fleming,"DR NO").

Visual Prolog устанавливает соответствие, X становится связанным с fleming, a Y - “dr no”. В этот момент Visual Prolog напечатает:

X=fleming, Y="DR NO"

Поскольку Test Goal ищет все решения для заданной цели, целевое утверждение также будет унифицировано и со вторым предложением written_by:

written_by(melville, "MOBY DICK").

Test Goal печатает второе решение:

X=melville, Y="MOBY DICK"

2 Solutions

Рассмотрим, как Visual Prolog выполнит следующее целевое утверждение:

long_novel(X).

Когда Visual Prolog пытается выполнить целевое утверждение, он проверяет, действительно ли обращение может соответствовать факту или заголовку правила. В нашем случае устанавливается соответствие с

long_novel(Title)

Visual Prolog проверяет предложение для long_novel, пытаясь завершить сопоставление унификацией аргументов. Поскольку в целевом утверждении X - свободная переменная, то она может быть унифицирована с любым другим аргументом. Title также не является связанным в заголовке предложения long_novel. Целевое утверждение соответствует заголовку правила, и унификация выполняется. Впоследствии Visual Prolog будет пытаться согласовывать подцели с правилом

long_novel(Title) :-

written_by(_, Title), book(Title, Length), Length>300.

Пытаясь выполнить согласование тела правила, Visual Prolog обратится к первой подцели в теле правила -- written_by(_, Title). Поскольку авторство книги является несущественным, на месте аргумента author появляется анонимная переменная (_). Обращение written_by (_, Title) становится текущей подцелью, и Пролог ищет решение для этого обращения.

Пролог ищет соответствие с данной подцелью от вершины и до конца программы. В результате достигается унификация с первым фактом для written_by, а именно:

written_by(_, Title),

written_by (fleming, "DR NO").

Переменная Title связывается с "dr no", и к следующей подцели book (Title, Length) обращение выполняется уже с этим значением переменной. Далее Visual Prolog начинает очередной процесс поиска, пытаясь найти соответствие с обращением к book. Так как Title связан с "dr no", фактическое обращение выглядит как book("DR NO", Length). Процесс поиска опять начинается с вершины программы. Заметим, что первая попытка сопоставления с предложением book(“MOBY DICK", 250) завершится неудачно, и Visual Prolog перейдет ко второму предложению book в поиске соответствия. Здесь заголовок книги соответствует подцели, и Visual Prolog связывает переменную Length с величиной 310.

Теперь третье предложение в теле long_novel становится текущей подцелью:

length > 300.

Visual Prolog выполняет сравнение, завершающееся успешно: 310 больше, чем 300. В этот момент все подцели в теле правила выполнены, и, следовательно, обращение long_novel(X) успешно. Так как X в обращении был унифицирован с переменной Title в правиле, то значение, с которым связывается Title при подтверждении правила, возвращается и унифицируется с переменной X. Переменная Title в случае подтверждения правила имеет значение "dr no", поэтому Visual Prolog выведет:

X="DR NO"

1 Solution.

2. Поиск с возвратом

Часто при решении реальной задачи мы придерживаемся определенного пути для ее логического завершения. Если полученный результат не дает искомого ответа, мы должны выбрать другой путь.

Так, вам, возможно, приходилось играть в лабиринт. Один из верных способов найти конец лабиринта -- это поворачивать налево на каждой развилке лабиринта до тех пор, пока вы не попадете в тупик. Тогда следует вернуться к последней развилке и попробовать свернуть вправо, после чего опять поворачивать налево на каждом встречающемся распутье. Путем методичного перебора всех возможных путей вы, в конце концов, найдете выход.

Visual Prolog при поиске решения задачи использует именно такой метод проб и возвращений назад; этот метод называется поиск с возвратом. Если, начиная поиск решения задачи (или целевого утверждения), Visual Prolog должен выбрать между альтернативными путями, то он ставит маркер у места ветвления (называемого точкой отката) и выбирает первую подцель, которую и станет проверять. Если данная подцель не выполнится, Visual Prolog вернется к точке отката и попробует проверить другую подцель.

predicates

likes(symbol,symbol)

tastes(symbol, symbol)

food(symbol)

clauses

likes(bill,X):-

food(X), tastes(X,good) .

tastes(pizza,good).

tastes(brussels_sprouts,bad).

food(brussels_sprouts).

food(pizza).

Программа ch04e02.pro

Эта маленькая программа составлена из двух множеств фактов и одного правила. Правило, представленное отношением likes, утверждает, что Билл любит вкусную пищу.

Чтобы увидеть, как работает поиск с возвратом, дадим программе для решения следующее целевое утверждение:

likes(bill, What).

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

В данном случае Пролог будет искать решение, производя с вершины программы поиск соответствия с подцелью likes (bill, what).

Он обнаруживает соответствие с первым предложением в программе и переменная What унифицируется с переменной X. Сопоставление с заголовком правила заставляет Visual Prolog попытаться удовлетворить это правило. Производя это, он двигается по телу правила и обращается к первой находящейся здесь подцели: food(X).

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

Пытаясь согласовать первую подцель, Visual Prolog (начиная с вершины) производит сопоставление с каждым фактом или заголовком правила, встреченным в программе.

Он обнаруживает соответствие с запросом у первого же факта, представляющего отношение food. Таким образом, переменная X связывается со значением brussels_sprouts. Поскольку существует более чем один возможный ответ на обращение food(X), Visual Prolog ставит точку возврата (маркер) возле факта food(brussels_sprouts). Эта точка поиска с возвратом указывает на то место, откуда Пролог начнет поиск следующего возможного соответствия для food(X).

Когда установление соответствия обращения завершается успешно, говорят, что обращение возвращается, и может быть испытана очередная подцель.

Поскольку переменная X связана с brussels_sprouts, следующее обращение будет выполняться так:

tastes(brussels_sprouts, good)

и Visual Prolog вновь начнет поиск с вершины программы, пытаясь согласовать это вращение. Поскольку соответствующих предложений не обнаруживается, обращение завершается неудачно, и теперь Visual Prolog запускает механизм возврата. Начиная поиск с возвратом, Пролог отступает к последней позиции, где была уставлена точка отката. В данном случае Пролог возвращается к факту

food(brussels_sprouts).

Единственным способом освободить переменную, однажды связанную в предложении, является откат при поиске с возвратом.

Когда Пролог отступает к точке поиска с возвратом, он освобождает все переменные, связанные после этой точки, и будет искать другое решение для исходного обращения.

Обращение было food(X), так что связанность brussels_sprouts с X отменена. Теперь Пролог пытается заново произвести решение для этого обращения. Он обнаруживает соответствие с фактом food (pizza); на этот раз переменная X связывается со значением pizza.

Пролог переходит к следующей подцели в правиле, имея при этом новую связанную переменную. Производится новое обращение, tastes (pizza, good), и начинается поиск (опять от вершины программы). На этот раз соответствие найдено, и целевое утверждение успешно выполняется.

Поскольку переменная what в целевом утверждении унифицирована с переменной X в правиле likes, а переменная X связана со значением pizza, переменная What отныне связана со значением pizza и Visual Prolog сообщает решение:

What=pizza

1 Solution

3. Управление поиском решений

Встроенный механизм поиска с возвратом в Прологе может привести к поиску ненужных решений, в результате чего теряется эффективность, например, когда желательно найти только одно решение. В других случаях может оказаться необходимым продолжать поиск дополнительных решений, даже если целевое утверждение уже согласовано.

Visual Prolog обеспечивает два инструментальных средства, которые дают возможность управлять механизмом поиска с возвратом: предикат fail, который используется для инициализации поиска с возвратом, и cut или отсечение (обозначается !) -- для запрета возможности возврата.

Использование предиката fail
Visual Prolog начинает поиск с возвратом, когда вызов завершается неудачно. В определенных ситуациях бывает необходимо инициализировать выполнение поиска с возвратом, чтобы найти другие решения. Visual Prolog поддерживает специальный предикат fail, вызывающий неуспешное завершение, и, следовательно, инициализирует возврат. Действие предиката fail равносильно эффекту от сравнения 2=3 или другой невозможной подцели. Программа ch04e06.pro (рис. 3) иллюстрирует использование этого специального предиката.

domains

name = symbol

predicates

father(name, name)

everybody

clauses

father(leonard,katherine).

father (carl, jason).

father (carl,marilyn)

everybody:-

father (X,Y),

write(X," is ",Y,"'s father\n"), fail.

Программа ch04e06.pro

Пусть необходимо найти все решения цели father (X,Y). Используя утилиту Test Goal, можно записать цель как

goal

father(X,Y).

Test Goal найдет все решения цели father (X,Y) и отобразит значения всех переменных следующим образом:

X=leonard, Y=katherine

X=carl, Y=jason

X=carl, Y=marilyn

3 Solutions

Но если вы скомпилируете эту программу и запустите ее, то Visual Prolog найдет только первое подходящее решение для father (X,Y). После того как целевое утверждение, определенное в разделе goal, выполнено впервые, ничто не говорит Прологу о необходимости продолжения поиска с возвратом. Поэтому обращение к father приведет только к одному решению. Как же найти все возможные решения? Предикат everybody в программе ch04e06.pro использует fail для поддержки поиска с возвратом.

Задача предиката everybody -- найти все решения для father и выдать полный ответ. Сравните предыдущие ответы утилиты Test Goal с целью father(X,Y) и ответы на выполнение следующей цели:

goal

everybody.

отображенные сгенерированной программой:

leonard is katherine' s father

carl is Jason's father

carl is marilyn's father

Предикат everybody использует поиск с возвратом с тем, чтобы получить все решения для father (X, Y), заставляя Пролог выполнять поиск с возвратом сквозь тело правила everybody:

father (X, Y),

mite(X," is ",Y, "'s father\n"),

fail.

fail не может быть согласован (он всегда неуспешен), поэтому Visual Prolog вынужден повторять поиск с возвратом. При поиске с возвратом он возвращается к последнему обращению, которое может произвести множественные решения. Такое обращение называют недетерминированным. Недетерминированное обращение является противоположностью детерминированному обращению, которое может произвести только одно решение.

Предикат write не может быть вновь согласован (он не может предложить новых решений), поэтому Visual Prolog должен выполнить откат дальше, на этот раз к первой подцели в правиле.

Обратите внимание, что помещать подцель после fail в теле правила бесполезно. Предикат fail все время завершается неудачно, нет возможности для достижения подцели, расположенной после fail.

Прерывание поиска с возвратом: отсечение
Visual Prolog предусматривает возможность отсечения, которая используется для прерывания поиска с возвратом; отсечение обозначается восклицательным знаком (!). Действует отсечение просто: через него невозможно совершить откат (поиск с возвратом).

Отсечение помещается в программу таким же образом, как и подцель в теле правила. Когда процесс проходит через отсечение, немедленно удовлетворяется обращение к cut и выполняется обращение к очередной подцели (если таковая имеется). Однажды пройдя через отсечение, уже невозможно произвести откат к подцелям, расположенным в обрабатываемом предложении перед отсечением, и также невозможно возвратиться к другим предложениям, определяющим обрабатывающий предикат (предикат, содержащий отсечение).

Существуют два основных случая применения отсечения.

· Если вы заранее знаете, что определенные посылки никогда не приведут к осмысленным решениям (поиск решений в этом случае будет лишней тратой времени), -- примените отсечение, -- программа станет быстрее и экономичнее. Такой прием называют зеленым отсечением.

· Если отсечения требует сама логика программы для исключения из рассмотрения альтернативных подцелей. Это -- красное отсечение.

В этом вопросе даются примеры, показывающие, как следует использовать отсечение, рассматриваются несколько условных правил (rl, r2 и rЗ), которые определяют условный предикат г, а также несколько подцелей -- а, b, с и т. д.

6.1.1 Предотвращение поиска с возвратом к предыдущей подцели в правиле

r1 :- а,b,

Такая запись является способом сообщить Visual Prolog о том, что вас удовлетворит первое решение, найденное им для подцелей а и b. Имея возможность найти множественные решения при обращении к с путем поиска с возвратом, Пролог при этом не может произвести откат (поиск с возвратом) через отсечение и найти альтернативное решение для обращений а и b. Он также не может возвратиться к другому предложению, определяющему предикат rl.

В качестве конкретного примера рассмотрим программу ch04e07.pro (рис. 4).

predicates

buy_car(symbol,symbol)

car (symbol,symbol,integer)

colors(symbol,symbol)

clauses

buy_car(Model,Color):-

car(Model,Color,Price),

colors(Color,sexy),

Price < 25000.

car(maserati,green,25000).

car(corvette,black,24000).

car(corvette,red,26000).

car(porsche,red,24000).

colors(red,sexy).

colors(black,mean).

colors(green,preppy).

goal

buy_car(corvette,Y).

Рис. 4. Программа ch04e07.pro

В данном примере поставлена цель: найти corvette (Корвет) приятного цвета, подходящий по стоимости. Отсечение в правиле buy_car означает, что поскольку в базе данных содержится только один "Корвет" приятного цвета, хоть и со слишком высокой ценой, то нет нужды искать другую машину. Получив целевое утверждение

buy_car(corvette, Y)

программа отработает следующие шаги:

1. Visual Prolog обращается к саг, первой подцели для предиката buy_car.

2. Выполняет проверку для первой машины, maserati, которая завершается неудачно.

3. Затем проверяет следующее предложение саг и находит соответствие, связывая переменную Color со значением black.

4. Переходит к следующему обращению и проверяет, имеет ли выбранная машина приятный цвет. Черный цвет не является приятным в данной программе, таким образом, проверка завершается неудачно.

5. Выполняет поиск с возвратом к обращению саг и снова ищет corvette, удовлетворяющий этому критерию.

6. Находит соответствие и снова проверяет цвет. На этот раз цвет оказывается приятным, и Visual Prolog переходит к следующей подцели в правиле: к отсечению. Отсечение немедленно выполняется, "замораживая" все переменные, ранее связанные в этом предложении.

7. Переходит к следующей (и последней) подцели в правиле, к сравнению

Price < 25000.

8. Проверка завершается неудачно, и Visual Prolog пытается совершить поиск с возвратом с целью найти другую машину для проверки. Отсечение предотвращает попытку решить последнюю подцель, и наше целевое утверждение завершается неудачно.

6.1.2 Предотвращение поиска с возвратом к следующему предложению

Отсечение может быть использовано, как способ сообщить Visual Prolog, что он выбрал верное предложение для определенного предиката. Например, рассмотрим следующий фрагмент:

r(1) :-

а, b, с.

r(2):-

r(3):-

с.

r(_) :-

write("This is a catchall clause.").

Использование отсечения делает предикат r детерминированным. В данном случае Visual Prolog выполняет обращение к r с единственным целым аргументом. Предположим, что произведено обращение r(l). Visual Prolog просматривает программу в поисках соответствия для обращения; он находит его с первым предложением, определяющим r. Поскольку имеется более чем одно возможное решение для данного обращения, Visual Prolog проставляет точку возврата около этого предложения.

Теперь Visual Prolog начинает обработку тела правила, проходит через отсечение и исключает возможность возвращения к другому предложению r. Это отменяет точки поиска с возвратом, повышая эффективность выполнения программы, а также гарантирует, что отлавливающее ошибки предложение будет выполнено лишь в том случае, если ни одно из условий не будет соответствовать обращению к r.

Обратите внимание, что конструкция такого типа весьма похожа на конструкцию case в других языках программирования; условие проверки записывается в заголовке правил. По возможности, всегда следует помещать проверочное условие именно в заголовок правила, -- это повышает эффективность программы и упрощает ее чтение.

Детерминизм и отсечение
Если бы предикат r, определенный в предыдущей программе, не содержал отсечений, то это был бы недетерминированный предикат (способный производить множественные решения при помощи поиска с возвратом). В предыдущих реализациях Пролога программисты должны были обращать особое внимание на недетерминированные предложения из-за сопутствующих им дополнительных требований к ресурсам памяти. Теперь Visual Prolog сам выполняет проверку на недетерминированные предложения, облегчая вашу работу.

В Прологе существует директива компилятора check_determ. Если вставить эту директиву в самое начало программы, то Visual Prolog будет выдавать предупреждение в случае обнаружения недетерминированных предложений в процессе компиляции.

Можно превратить недетерминированные предложения в детерминированные, вставляя отсечения в тело правил, определяющих данный предикат.

Предикат not
Следующая программа ch04el0.pro (рис. 5.) демонстрирует, как вы можете использовать предикат not для того, чтобы выявить успевающего студента: студента, у которого средний балл (GPA) не менее 3.5 и у которого в настоящее время не продолжается испытательный срок.

domains

name = symbol

gpa = real

predicates

honor_student(name)

student(name, gра)

probation(name)

clauses

honor_student (Name) :-

student(Name, GPA),

GPA>=3.5,

not(probation(Name)).

student ("Betty Blue", 3.5).

student ("David Smith", 2.0).

student ("John Johnson", 3.7).

probation ("Betty Blue").

probation ("David Smith").

goal

honor_student (X) .

Программа ch04e10.pro

При использовании предиката not необходимо иметь в виду следующее:

Предикат not будет успешным, если не может быть доказана истинность данной подцели.

Это приводит к предотвращению связывания внутри not несвязанных переменных. При вызове изнутри not подцели со свободными переменными, Visual Prolog возвратит сообщение об ошибке: "Free variables not allowed in not or retractall" (Свободные переменные не разрешены в not или retract). Это происходит вследствие того, что для связывания свободных переменных в подцели, подцель должна унифицироваться с каким-либо другим предложением и выполняться. Правильным способом управления несвязанными переменными подцели внутри not является использование анонимных переменных.

Первый пример работает правильно:

likes (bill, Anyone) :-% Anyone -- выходной аргумент

likes(sue, Anyone),

not(hates(bill, Anyone).

В этом примере Anyone связывается посредством likes (sue, Anyone) до того, как Visual Prolog делает вывод, что hates (bill, Anyone) не является истиной. Данное предложение работает корректно.

Если пример изменить таким образом, что обращение к not будет выполняться первым, то получите сообщение об ошибке: "Free variable are not allowed in not" (Свободные переменные в not не разрешены).

likes(bill, Anyone):-% Это не будет работать правильно

not(hates(bill, Anyone)),

likes(sue, Anyone).

Даже если вы замените в not (hates (bill, Anyone)) Anyone на анонимную переменную, и предложение, таким образом, не будет возвращать ошибку, все равно получите неправильный результат.

likes(bill, Anyone):- % Это не будет работать правильно

not(hates(bill, _)),

likes(sue, Anyone).

Это предложение утверждает, что Биллу нравится кто угодно, если неизвестно ничего о том, кого Билл ненавидит, и если этот "кто-то" нравится Сью. Подлинное предложение утверждало, что Биллу нравится тот, кто нравится Сью, и при этом Билл не испытывает к этому человеку ненависти.

Неверное использование предиката not приведет к сообщению об ошибке или к ошибкам в логике вашей программы.Простые и составные объекты

До сих пор мы работали только основными видами объектов данных Visual Prolog, таких как числа, идентификаторы и строки. Visual Prolog может создавать не только простые, но и составные типы.

5. Простые объекты данных
Простой объект данных -- это переменная или константа. Не путайте это значение слова "константа" с символьными константами, которые вы определяете в разделе constants программы. То, что мы здесь называем константой, это нечто, идентифицирующее объект, который нельзя изменять: символ (char), число (integer или real) или атом (symbol или string).

Константы включают числа, символы и атомы. Числа и символы были рассмотрены ранее.

Атомы имеют тип идентификатор (symbol) или строка (string). Отличие между ними -- главным образом вопрос машинного представления и реализации, и, в основном, оно синтаксически не заметно. Когда атом передается в качестве аргумента при вызове предиката, то к какому домену принадлежит атом -- symbol или string -определяется по тому, как описан этот аргумент в декларации предиката.

Visual Prolog автоматически преобразует типы между доменами string и symbol, поэтому вы можете использовать атомы symbol в доменах string и наоборот. Однако принято считать, что объект в двойных кавычках принадлежит домену string, а объект, не нуждающийся в кавычках, домену symbol. Атомы типа symbol -- это имена, начинающиеся со строчной буквы и содержащие только буквы, цифры и знак подчеркивания.

Атомы типа string выделяются двойными кавычками и могут содержать любую комбинацию литер, кроме ASCII-нуля (0, бинарный нуль), который обозначает конец строки атома.

Примеры строк и идентификаторов приведены в табл. 1.

Строки и идентификаторы

Атомы-идентификаторы	Атомы-строки
food	"Jesse James"
rick_Jones_2nd	"123 Pike street"
fred_Flintstone_1000_Bс_Bedrock	"jon"
a	"a"
new_york	"New York"
pdcProlog	"Visual Prolog, by Prolog Development Center"

Так как string/symbol взаимозаменяемы, их отличие не существенно. Однако имена предикатов и функторы для составных объектов должны соответствовать синтаксическим соглашениям домена symbol.

6. Составные объекты данных и функторы
Составные объекты данных позволяют интерпретировать некоторые части информации как единое целое таким образом, чтобы затем можно было легко разделить их вновь. Возьмем, например, дату "октябрь 15, 1991". Она состоит из трех частей информации -- месяц, день и год. Представим ее на рис. 1, как древовидную структуру.

Древовидная структура даты

Можно объявить домен, содержащий составной объект date:

domains

date_cmp = date(string,unsigned,unsigned)

а затем просто записать:

D = date("0ctober",15,1991) .

Такая запись выглядит как факт Пролога, но это не так -- это объект данных, который вы можете обрабатывать наряду с символами и числами. Он начинается с имени, называемого функтором (в данном случае date), за которым следуют три аргумента.

Функтор в Visual Prolog -- не то же самое, что функция в других языках программирования; это просто имя, которое определяет вид составного объекта данных и объединяет вместе его аргументы. Функтор не обозначает, что будут выполнены какие-либо вычисления.

Аргументы составного объекта данных могут сами быть составными объектами. Например, вы можете рассматривать чей-нибудь день рождения (рис. 2), как информацию со следующей структурой:

Рис. 2. древовидная структура даты рождения.

На языке Пролог это выглядит следующим образом:

birthday(person("Leo","Jensen"),date("Apr",14,1960))

7. Унификация составных объектов

Составной объект может быть унифицирован с простой переменной или с составным объектом (возможно, содержащим переменные в качестве частей во внутренней структуре), который ему соответствует. Это означает, что составной объект можно использовать для того, чтобы передавать целый набор значений как единый объект, и затем применять унификацию для их разделения. Например:

date("April",14,I960)

сопоставляется с X и присваивает X значение date ("April", 14,1960). Также

date("April",14,I960)

сопоставляется с date (Mo, Da, Yr) и присваивает переменным Мо = "April", Da=14 и Yr = 1960.

8. Использование нескольких значений как единого целого
Составные объекты могут рассматриваться в предложениях Пролога как единые объекты, что сильно упрощает написание программ. Рассмотрим, например, факт:

owns(john, book(“From Here to Eternity", "James Jones")).

в котором утверждается, что у Джона есть книга "From Here to Eternity" (Отсюда в вечность), написанная James Jones (Джеймсом Джонсом). Аналогично можно записать:

owns (john, horse (blacky) ) .

что означает:

John owns a horse named blacky.(У Джона есть лошадь Блеки.)

Если вместо этого описать только два факта:

owns (john, "From Here to Eternity"), owns(john, blacky).

то нельзя было бы определить, является ли blacky названием книги или именем лошади.

9. Объявление составных доменов

Рассмотрим, как определяются составные домены. После компиляции программы, которая содержит следующие отношения:

owns(john, book("From Here to Eternity", "James Jones")).

owns (John, horse (blacky) ).

вы можете послать системе запрос в следующем виде:

owns (John, X)

Переменная Х может быть связана с различными типами объектов: книга, лошадь и, возможно, другими объектами, которые вы определите. Отметим, что теперь вы не можете более использовать старое определение предиката owns:

owns (symbol, symbol)

Второй элемент более не является объектом типа symbol. Вместо этого вы можете дать новое определение этого предиката

owns(name, articles)

Домен articles в разделе domains можно описать так

domains

articles = book(title, author); horse(name)

Точка с запятой читается как "или" В этом случае возможны два варианта книга будет определяться своим заглавием и автором, а лошадь будет распознаваться своим именем Домены title, author и name имеют стандартный тип symbol.

К определению домена легко могут быть добавлены другие варианты.

10. Многоуровневые составные объекты

Visual Prolog позволяет конструировать составные объекты на нескольких уровнях. Например:

domains

articles = book(title, author);%Первый уровень

author= author(first_name, last_name) %Второй уровень

title, first_name, last_name = symbol%Третий уровень

При использовании составных объектов со многими уровнями часто помогает такое "дерево" (рис. 7):

Дерево многоуровневого составного объекта

Повтор и рекурсия

Компьютеры способны повторять одно и то же действие снова и снова, Visual Prolog может выражать повторение как в процедурах, так и в структурах данных. Идея повторяющихся структур данных может показаться странной, но Пролог позволяет создавать структуры данных, размер которых не известен во время создания.

11. Процесс повторения

Программисты на языках Pascal, Basic или С, которые начинают использовать Visual Prolog, часто испытывают разочарование, обнаружив, что язык не имеет конструкций for, while или repeat. В Прологе не существует прямого способа выражения повтора. Пролог обеспечивает только два вида повторения

· откат, с помощью которого осуществляется поиск многих решений в одном запросе,

· и рекурсию, в которой процедура вызывает сама себя.

Однако этот недостаток не снижает мощи Пролога. Фактически, Visual Prolog распознает специальный случай рекурсии -- хвостовую рекурсию -- и компилирует ее в оптимизированную итерационную петлю. Это означает, что хотя программная логика и выражается рекурсивно, скомпилированный код так же эффективен, как если бы программа была написана на Pascal или Basic.

Использование поиска с возвратом для организации повторов
Когда выполняется процедура поиска с возвратом (откат), происходит поиск другого решения целевого утверждения. Это осуществляется путем возврата к последней из проверенных подцелей, имеющей альтернативное решение, использования следующей альтернативы этой подцели и новой попытки движения вперед (см. пример ch06e01). Очень часто для этого используется директива fail.

predicates

country(symbol)

print_countries

clauses

country("England").

country("France").

country("Germany").

country("Denmark").

print_countries:-

country(X),

write(X),% записать значение Х

nl,% начать новую строку

fail.

print_countries.

goal

print__countnes.

Программа ch06e01.pro

Предварительные и последующие операции
Отметим, что программа, которая находит решения для целевого утверждения, может выполнять какие-либо предварительные или завершающие операции. Например, в нашем примере программа могла бы:

1. Напечатать

Some delightful places to live are... (Некоторые восхитительные места для проживания...).

2. Напечатать все решения для country (X).

3. Завершить печать фразой And maybe others (Могут быть и другие).

Заметьте, что print_countries, определенное в предыдущем примере, уже содержит предложение вывести на печать все решения country (X) и отпечатать завершающее сообщение.

Первое предложение для print_countries соответствует шагу 2 и выводит на печать все решения. Его второе предложение соответствует шагу 3 и просто успешно завершает целевое утверждение (потому что первое предложение всегда в режиме fail -- "неудачное завершение").

Можно было бы изменить второе предложение в программе ch06e01.pro.

print_countnes :-

write("And maybe others."), nl.

которое выполнило бы шаг 3, как указано.

А что можно сказать о шаге 1? В нем нет смысла, когда print_countnes содержал только 2 предложения. Но в предикате может быть и три предложения:

print_countries :-

write("Some delightful places to live are"), nl,

fail.

pnnt_countnes :-

country(X),

write(X),nl,

fail.

print_countries :-

write("And maybe others."), nl.

Наличие fail в первом предложении важно, поскольку он обеспечивает после выполнения первого предложения возврат и переход ко второму предложению Кроме того, это важно, потому что предикаты write и nl не образуют альтернатив Строго говоря, первое предложение проверяет все возможные решения перед тем, как завершиться неуспехом.

Такая структура из трех предложений более удобна по сравнению с общепринятым подходом.

Использование отката с петлями
Поиск с возвратом является хорошим способом определить все возможные решения целевого утверждения Но, даже если ваша задача не имеет множества решений, можно использовать поиск с возвратом для выполнения итераций Просто определите предикат с двумя предложениями

repeat

repeat - repeat

Этот прием демонстрирует создание структуры управления Пролога (см листинг на рис. 2.), которая порождает бесконечное множество решений. Цель предиката repeat -- допустить бесконечность поиска с возвратом (бесконечное количество откатов)

/* Использование repeat для сохранения введенных символов и печатать их до тех пор, пока пользователь не нажмет Enter (Ввод)*/

predicates

repeat

typewriter

clauses

repeat.

repeat -repeat.

typewriter :-

repeat,

readchar(C),% Читать символ, его значение присвоить С

write(С),

С = '\r',% Символ возврат каретки (Enter)? или неуспех

goal

typewriter (), nl.

Листинг 13.2. Программа ch06e02.pro

Программа ch06e02 pro показывает, как работает repeat Правило typewriter - описывает процесс приема символов с клавиатуры и отображения их на экране, пока пользователь не нажмет клавишу <Enter> (<Return>)

Правило typewriter работает следующим образом

1 Выполняет repeat (который ничего не делает, но ставит точку отката).

2 Присваивает переменной с значение символа.

3 Отображает С.

4 Проверяет, соответствует ли с коду возврата каретки.

5 Если соответствует, то -- завершение. Если нет -- возвращается к точке отката и ищет альтернативы, так как ни write, ни readchar не являются альтернативами,

12. Рекурсивные процедуры
Понятие рекурсии
Одним из способов организации повторений -- рекурсия. Рекурсивная процедура -- это процедура, которая вызывает сама себя. В рекурсивной процедуре нет проблемы запоминания результатов ее выполнения, потому что любые вычисленные значения можно передавать из одного вызова в другой как аргументы рекурсивно вызываемого предиката.

Логика рекурсии проста для осуществления. Представьте себе ЭВМ, способную "понять":

Найти факториал числа N:

Если N равно 1, то факториал равен 1

Иначе найти факториал N-1 и умножить его на N.

Этот подход означает следующее:

первое («закручиваете» стек), чтобы найти факториал 3, вы должны найти факториал 2, а чтобы найти факториал 2, вы должны вычислить факториал 1. факториал 1 ищется без обращения к другим факториалам, т.к. он равен 1, поэтому повторения не начнутся.

второе («раскручиваете» стек), если у вас есть факториал 1, то умножаете его на 2, чтобы получить факториал 2, а затем умножаете полученное на 3, чтобы получить факториал 3.

Информация хранится в области памяти, называемой стековым фреймом (stack frame) или просто стеком (stack), который создается каждый раз при вызове правила. Когда выполнение правила завершается, занятая его стековым фреймом память освобождается (если это не недетерминированный откат), и выполнение продолжается в стековом фрейме правила-родителя.

Преимущества рекурсии
Рекурсия имеет три основных преимущества:

· она может выражать алгоритмы, которые нельзя удобно выразить никаким другим образом;

· она логически проще метода итерации;

· она широко используется в обработке списков.

Рекурсия -- хороший способ для описания задач, содержащих в себе подзадачу такого же типа. Например, поиск в дереве (дерево состоит из более мелких деревьев) и рекурсивная сортировка (для сортировки списка, он разделяется на части, часть сортируются и затем объединяются вместе).

Логически рекурсивным алгоритмам присуща структура индуктивного математического доказательства. Приведенная выше рекурсивная программа вычисления факториала описывает бесконечное множество различных вычислений с помощью всего лишь двух предложений. Это позволяет легко увидеть правильность этих предложений. Кроме того, правильность каждого предложения может быть изучена независимо от другого.

Пример рекурсивного определения правил
Давайте добавим к программе о родственных связях еще одно отношение - предок. Определим его через отношение родитель. Все отношение можно выразить с помощью двух правил. Первое правило будет

определять непосредственных (ближайших) предков, а второе - отдаленных. Будем говорить, что некоторый X является отдаленным предком некоторого Z, если между X и Z существует цепочка людей, связанных между собой отношением родитель-ребенок, как показано на рис.1.. В нашем примере на рис. 1. Том - ближайший предок Лиз и отдаленный предок Пат.

Пример отношения предок:(а) X - ближайший предок Z; (b) X - отдаленный предок Z.

Первое правило простое и его можно сформулировать так:

Для всех X и Z,

X - предок Z, если X - родитель Z.

Это непосредственно переводится на Пролог как

предок( X, Z) :.-родитель( X, Z).

Второе правило сложнее, поскольку построение цепочки отношений родитель может вызвать некоторые трудности. Один из способов определения отдаленных родственников мог бы быть таким, как показано на рис. 2. В соответствии с ним отношение предок определялось бы следующим множеством предложений:

предок( X, Z) :-

родитель( X, Z).

предок( X, Z) :-

родитель( X, Y), родитель( Y, Z).

предок( X, Z) :-

родитель( X, Y1),

родитель( Y1, Y2),

родитель( Y2, Z).

предок (X, Z) :-

родитель( X, Y1),

родитель( Y1, Y2),

родитель( Y2, Y3),

родитель( Y3, Z).

Пары предок-потомок, разделенных разным числом поколений.

Эта программа длинна и, что более важно, работает только в определенных пределах. Она будет обнаруживать предков лишь до определенной глубины фамильного дерева, поскольку длина цепочки людей между предком и потомком ограничена длиной наших предложений в определении отношения.

Существует, однако, корректная и элегантная формулировка отношения предок - корректная в том смысле, что будет работать для предков произвольной отдаленности. Ключевая идея здесь - определить отношение предок через него самого. Рис. 3 иллюстрирует эту идею:

Для всех X и Z,

X - предок Z, если существует Y, такой, что

(1) X - родитель Y и

(2) Y - предок Z.

Предложение Пролога, имеющее тот же смысл, записывается так:

предок( X, Z) :-

родитель ( X, Y), предок( Y, Z).

Теперь мы построили полную программу для отношения предок, содержащую два правила: одно для ближайших предков и другое для отдаленных предков. Здесь приводятся они оба вместе:

предок( X, Z) :-

родитель( X, Z).

предок( X, Z) :-

родитель( X, Y),

предок( Y, Z).

Рекурсивная формулировка отношения предок.

Ключевым моментом в данной формулировке было использование самого отношения предок в его определении. Такие определения называются рекурсивными. Логически они совершенно корректны и понятны. Рекурсия - один из фундаментальных приемов программирования на Прологе. Без рекурсии с его помощью невозможно решать задачи сколько-нибудь ощутимой сложности.

Оптимизация хвостовой рекурсии
У рекурсии есть один большой недостаток -- она «съедает» память. Всякий раз, когда одна процедура вызывает другую, информация о выполнении вызывающей процедуры должна быть сохранена для того, чтобы она (вызывающая процедура) могла, после выполнения вызванной процедуры, возобновить выполнение на том же месте, где остановилась. Это означает, что если процедура вызывает себя 100 раз, то 100 различных состояний должно быть записано одновременно (состояния выполнения решения сохраняются в стековом фрейме). Максимальный размер стека у 16-битных платформ, таких как IBM PC, работающая под DOS, составляет 64 Кбайт, что позволяет разместить максимум 3000 или 4000 стековых фреймов. На 32-битных платформах стек теоретически может возрасти до нескольких гигабайт; но здесь проявятся другие системные ограничения, прежде чем стек переполнится. Что же можно сделать, чтобы избежать использования столь большого стекового пространства?

Рассмотрим специальный случай, когда процедура может вызвать себя без сохранения информации о своем состоянии. Что, если вызывающая процедура не собирается возобновлять свое выполнение после завершения вызванной процедуры?

Предположим, что процедура вызывается последний раз, т. е. когда вызванная процедура завершит работу, вызывающая процедура не возобновит свое выполнение. Это значит, что вызывающей процедуре не нужно сохранять свое состояние, потому что эта информация уже не понадобится. Как только вызванная процедура завершится, работа процессора должна идти в направлении, указанном для вызывающей процедуры после ее выполнения.

Например, допустим, что процедура А вызывает процедуру В, а В -- С в качестве своего последнего шага. Когда В вызывает С, В не должна больше ничего делать. Поэтому, вместо того чтобы сохранить в стеке процедуры В информацию о текущем состоянии С, мы можем переписать старую сохраненную информацию о состоянии В (которая больше не нужна) на текущую информацию о С, сделав соответствующие изменения в хранимой информации. Когда С закончит выполнение, она будет считать, что она вызвана непосредственно процедурой А.

Предположим, что на последнем шаге выполнения процедура В вместо процедуры С вызывает себя. Получается, что когда В вызывает В, стек (состояние) для вызывающей в должен быть заменен стеком для вызванной В. Это очень простая операция, просто аргументам присваиваются новые значения и затем выполнение процесса возвращается на начало процедуры В. Поэтому, с процедурной точки зрения, происходящее очень похоже на всего лишь обновление управляющих переменных в цикле

Эта операция называется оптимизацией хвостовой рекурсии (tail recursion optimization) или оптимизацией последнего вызова (last-call optimization) Обратите внимание, что по техническим причинам оптимизация последнего вызова неприменима к рекурсивным функциям.

Как задать хвостовую рекурсию
Что означает фраза "одна процедура вызывает другую, выполняя свои самый последний шаг"? На языке Пролог это значит.

П вызов является самой последней подцелью предложения,

О ранее в предложении не было точек возврата

Ниже приводится удовлетворяющий обоим условиям пример

count (N) : -write(N), nl, NewN = N+l, count(NewN) .

Эта процедура является хвостовой рекурсией, которая вызывает себя без резервирования нового стекового фрейма, и поэтому не истощает запас памяти Как показывает программа ch06e04 pro (листинг 13 4), если вы дадите ей целевое утверждение

count (0) .

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

Листинг 13.4. Программа ch06e04.pro

/* Программа с хвостовой рекурсией, которая не истощает память */ predicates count(ulong)

clauses

count(N):-

write('\r',N), NewN = N+l, count(NewN).

GOAL nl, count(0).

13. Определение списка

В Прологе список -- это объект, который содержит конечное число других объектов. Списки можно грубо сравнить с массивами в других языках, но, в отличие от массивов, для списков нет необходимости заранее объявлять их размер.

Список, содержащий числа 1, 2 и 3, записывается так:

[1, 2, 3]

Каждая составляющая списка называется элементом. Чтобы оформить списочную структуру данных, надо отделить элементы списка запятыми и заключить их в квадратные скобки. Вот несколько примеров:

[dog, cat, canary]

["valerie ann", "jennifer caitlin", "benjamin thomas"]

14. Объявление списков

Чтобы объявить домен для списка целых, надо использовать декларацию домена, такую как:

domains

integerlist = integer*

Символ (*) означает "список чего-либо"; таким образом, integer* означает "список целых".

Элементы списка могут быть любыми, включая другие списки. Однако все его элементы должны принадлежать одному домену. Декларация домена для элементов должна быть следующего вида:

domains

elementlist = elements*

elements = ....

Здесь elements имеют единый тип (например: integer, real или symbol) или являются набором отличных друг от друга элементов, отмеченных разными функторами. В Visual Prolog нельзя смешивать стандартные типы в списке. Например, следующая декларация неправильно определяет список, составленный из элементов, являющихся целыми и действительными числами или идентификаторами:

elementlist = elements*

elements = integer; real; symbol/* Неверно */

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

elementlist = elements*

elements = i(integer); r(real); s(symbol)% функторы здесь i,r и s

15. Головы и хвосты

Список является рекурсивным составным объектом. Он состоит из двух частей -- головы, которая является первым элементом, и хвоста, который является списком, включающим все последующие элементы. Хвост списка -- всегда список, голова списка -- всегда элемент. Например:

голова [а, b, с] есть а

хвост [а, b, с] есть [b, с]

Что происходит, когда вы доходите до одноэлементного списка? Ответ таков:

голова [с] есть с

хвост [с] есть []

Если выбирать первый элемент списка достаточное количество раз, вы обязательно дойдете до пустого списка []. Пустой список нельзя разделить на голову и хвост.

В концептуальном плане это значит, что список имеет структуру дерева, как и другие составные объекты. Структура дерева [а, b, с, d] представлена на рис. 1.

Рис. 1. Структура дерева

Одноэлементный список, как, например [а], не то же самое, что элемент, который в него входит, потому что [а] на самом деле -- это составная структура данных.

16. Работа со списками

В Прологе есть способ явно отделить голову от хвоста. Вместо разделения элементов запятыми, это можно сделать вертикальной чертой "|". Например:

[а, b, с] эквивалентно [а| [b, с]] и, продолжая процесс,

[а| [b, с] ] эквивалентно [а| [b| [с] ]], что эквивалентно [а| [b| [с| [] ] ] ]

Можно использовать оба вида разделителей в одном и том же списке при условии, что вертикальная черта есть последний разделитель. При желании можно набрать

[а, b, с, d] как [а, b|[с, d]].

В табл. 1. приведены несколько примеров на присвоение в списках.

Таблица 1. Присвоение в списках

Список 1	Список 2	Присвоение переменным
[X, Y, Z]	[эгберт, ест, мороженое]	Х=эгберг, У=ест, Z=мороженое
[7]	[X \| Y]	Х=7, Y=[]
[1, 2, 3, 4]	[X, Y \| Z]	X=l, Y=2, Z=[3,4]
[1, 2]	[3 \| X]	fail% неудача

17. Использование списков

Список является рекурсивной составной структурой данных, поэтому нужны алгоритмы для его обработки. Главный способ обработки списка -- это просмотр и обработка каждого его элемента, пока не будет достигнут конец.

Алгоритму этого типа обычно нужны два предложения. Первое из них говорит, что делать с обычным списком (списком, который можно разделить на голову и хвост), второе -- что делать с пустым списком.

18. Печать списков

Если нужно напечатать элементы списка, это делается так, как показано в листинге 1.

Листинг 1. Программа ch07e01.pro;

domains

list = integer*% Или любой тип, какой вы хотите

predicates

write_a_list(list)

clauses

write_a_list([ ]),% Если список пустой -- ничего не делать

write_a_list([Н|Т]):-% Присвоить Н-голова,Т-хвост, затем...

write(H),nl,

write_a_list(Т).

goal

write_a_list([1, 2, 3]).

Вот два целевых утверждения write_a_list, описанные на обычном языке:

Печатать пустой список -- значит ничего не делать.

Иначе, печатать список -- означает печатать его голову (которая является одним элементом), затем печатать его хвост (список) .

19. Подсчет элементов списка
Рассмотрим, как можно определить число элементов в списке. Что такое длина списка? Вот простое логическое определение:

Длина [] -- 0.

Длина любого другого списка -- 1 плюс длина его хвоста.

Можно ли применить это? В Прологе -- да. Для этого нужны два предложения (листинг 2).

Листинг 2. Программа ch07e02.pro

domains

list = integer*

predicates

length_of(list,integer)

clauses

length_of ( [ ] , 0).

length_of ( [ _|T],L) :-

length_of(T,TailLength),

L = TailLength + 1.

Посмотрим сначала на второе предложение. Действительно, [_|T] можно сопоставить любому непустому списку, с присвоением т хвоста списка. Значение головы не важно, главное, что оно есть, и компьютер может посчитать его за один элемент.

Таким образом, целевое утверждение

length_of([1, 2, 3], L).

подходит второму предложению при T=[2, 3]. Следующим шагом будет подсчет длины T. Когда это будет сделано (не важно как), TailLength будет иметь значение 2, и компьютер добавит к нему 1 и затем присвоит L значение 3.

Итак, как компьютер выполнит промежуточный шаг? Это шаг, в котором определяется длина [2, 3] при выполнении целевого утверждения

length_of([2, 3], TailLength).

Другими словами, length_of вызывает сама себя рекурсивно.

Страницы: 1, 2