|
Домен
|
Описание и реализация
|
|
char
|
Символ, реализуемый как беззнаковый byte.
Синтаксически это символ, заключенный между двумя одиночными кавычками: 'а'
|
|
real
|
Число с плавающей запятой, реализуемое как 8 байт в соответствии
с соглашением IEEE; эквивалентен типу double в С. При необходимости, целые автоматически
преобразуются в real
|
|
string
|
Последовательность символов, реализуемых как указатель на
байтовый массив, завершаемый нулем, как в С. Для строк допускается два
формата:1. Последовательность букв, цифр и символов подчеркивания, причем
первый символ должен быть строчной буквой.2. Последовательность символов,
заключенных в двойные кавычки.
Примеры строк:
telephone_number
"railway ticket" "Dorid Inc"
Строки, которые пишутся в программе, могут достигать длины в 255
символов, в то время как строки, которые система Visual Prolog считывает из файла или
строит внутри себя, могут достигать (теоретически) до 4 Гбайт на 32-битных
платформах
|
|
symbol
|
Последовательность символов, реализуемых как указатель на вход в
таблице идентификаторов, хранящей строки идентификаторов. Синтаксис — как для
строк
|
Идентификаторы
и строки взаимозаменяемы в программе, однако Visual Prolog хранит их раздельно. Идентификаторы
хранятся в таблице идентификаторов, а для представления используются лишь
их индексы в этой таблице, но не сами строки идентификаторов. Это означает, что
сопоставление идентификаторов выполняется очень быстро, а в случае если они
встречаются в программе несколько раз, то и хранение их компактно. Строки же не
хранятся в поисковой таблице, и при необходимости сопоставления Visual Prolog проверяет их символ за
символом. Вы сами должны определять, какой домен лучше использовать в каждой
конкретной программе.
Объявление
доменов аргументов в разделе predicates называется заданием типов аргументов. Предположим,
имеется следующая связь объектов:
Франк — мужчина, которому 45 лет.
Факт Пролога,
соответствующий этому предложению естественного языка, может быть следующим:
person(frank, male, 45).
Для того
чтобы объявить person (человек), как предикат с этими тремя аргументами, вы можете
разместить в разделе predicates следующую строку:
person(symbol, symbol, unsigned).
Здесь для
всех трех аргументов использованы стандартные домены. Отныне всякий раз при
работе с предикатом person, вы должны передавать ему три аргумента, причем первые два должны
быть типа symbol, а третий — типа integer.
Если в
программе используются только стандартные домены, то нет необходимости
использовать раздел domain; вы уже видели несколько программ такого типа.
Или,
предположим, что вы хотите описать предикат, который сообщал бы позицию буквы в
алфавите, т. е. цель
alphabet_position(Letter, Position)
должна
вернуть вам Position = 1, если Letter = a, Position = 2, если Letter = Ь и т. д. Предложения этого предиката могут
выглядеть следующим образом:
alphabet_position(A_character,
N).
Если при
объявлении предиката используются только стандартные домены, то программе не
нужен раздел domains. Предположим, что вы хотите описать предикат так, что цель будет
истинна, если A_character является N-м символом алфавита.
Предложения этого предиката будут такими:
alphabet_position('а', 1). alphabet_position('b', 2).
alphabet_position('с', 3).
alphabet_position(' z1, 26).
Вы можете
объявить данный предикат следующим образом:
predicates
alphabet_position(char, unsigned)
и тогда вам
не будет нужен раздел domains. Если разместить все фрагменты программы вместе,
получим:
predicates
alphabet_position(char, integer)
clauses
alphabet_position('a', 1).
alphabet_position('b', 2)
.
alphabet_position('c', 3).
% здесь находятся остальные буквы
alphabet_position('z', 26).
Ниже
представлено несколько простых целей, которые вы можете использовать:
alphabet_position ('а', 1).
alphabet_position(X, 3).
alphabet_position (' z',
What).
Арность
предиката — это количество аргументов, которые он принимает. Вы можете иметь два
предиката с одним и тем же именем, но отличающейся арностью. В разделах predicates и clauses версии предикатов с
одним именем и разной арностью должны собираться вместе; за исключением этого
ограничения, различная арность всегда понимается как полное различие
предикатов. Проиллюстрируем это примером/
domains
person = symbol
predicates
father(person)% этот
person — отец
father(person, person)% первый
person является отцом другого
clauses
father (Man)
:-father(Man, _) .
father(adam,seth).
father(abraham,isaac).
Правила
используются в Прологе в случае, когда какой-либо факт зависит от истинности
другого факта или группы фактов. Как мы объясняли ранее в этой главе, в правиле
Пролога есть две части: заголовок и тело. Ниже представлен обобщенный синтаксис
правила в Visual Prolog:
HEAD: - <Subgoal>, <Subgoal>, ...,
<Subgoal>.
Заголовок: — <Подцель>,
<Подцель>, ... , <Подцель>.
Тело правила
состоит из одной или более подцелей. Подцели разделяются запятыми, определяя
конъюнкцию, а за последней подцелью правила следует точка.
Каждая
подцель выполняет вызов другого предиката Пролога, который может быть истинным
или ложным. После того, как программа осуществила этот вызов, Visual Prolog проверяет истинность
вызванного предиката, и если это так, то работа продолжается, но уже со
следующей подцелью. Если же в процессе такой работы была достигнута точка, то
все правило считается истинным; если хоть одна из подцелей ложна, то все
правило ложно.
Для успешного
разрешения правила Пролог должен разрешить все его подцели и создать
последовательный список переменных, должным образом связав их. Если же одна из
подцелей ложна, Пролог вернется назад для поиска альтернативы предыдущей
подцели, а затем вновь двинется вперед, но уже с другими значениями переменных.
Этот процесс называется поиск с возвратом.
Как
упоминалось выше, в качестве разделителя заголовка и тела правила Пролог
использует знак:-, который читается как "если" (if). Однако if Пролога отличается от if, написанного в других
языках, например в Pascal, где условие, содержащееся в операторе if, должно быть указано
перед телом оператора, который может быть выполнен. Другими словами:
если ЗАГОЛОВОК истинен, тогда ТЕЛО
истинно (или: тогда выполнить ТЕЛО
Данный тип
оператора известен как условный оператор если/тогда (if/then). Пролог же использует
другую форму логики в таких правилах. Вывод об истинности заголовка правила
Пролога делается, если (после того, как) тело этого правила истинно, например,
так:
ЗАГОЛОВОК истинен, если ТЕЛО — истинно
(или: если ТЕЛО может Сыть выполнено).
Учитывая
вышесказанное, правило Пролога соответствует условной форме тогда/если (then/if).
Совсем не
обязательно, чтобы при сопоставлении двух Visual Prolog-переменных они
принадлежали одному и тому же домену. Переменные могут быть связаны с
константами из различных доменов. Такое (избирательное) смешение допускается,
т. к. Visual Prolog автоматически выполняет преобразование типов (из одного домена в
другой), но только в следующих случаях:
·
между
строками (string) и идентификаторами (symbol);
·
между
целыми, действительными и символами (char). При преобразовании символа в числовое значение
этим значением является величина символа в коде ASCII.
Аргумент из
домена my_dom, который объявлен следующим образом:
domains
my_dom = <base
domain> % <base domain> — это стандартный домен
может
свободно смешиваться с аргументами из этого основного домена и с аргументами
всех совместимых с ним стандартных доменов. Если основной домен — string, то с ним совместимы
аргументы из домена symbol; если же основной домен integer, то с ним совместимы домены real, char, word и др. Такое
преобразование типов означает, например, что вы можете:
·
вызвать
предикат с аргументами типа string, задавая ему аргументы типа symbol, и наоборот;
·
передавать
предикату с аргументами типа real параметры типа integer;
·
передавать
предикату с аргументами типа char параметры типа integer;
·
использовать
в выражениях и сравнениях символы без необходимости получения их кодов в ASCII.
Существует
набор правил, определяющих, к какому домену принадлежит результат смешивания
разных доменов. Эти правила будут детально рассмотрены далее.
Теперь, когда
вы ознакомились с такими разделами программ Visual Prolog, как clauses, predicates, domains и goal, поговорим о некоторых
других, часто используемых разделах программ: facts, constants и различных глобальных (global) разделах.
Программа на Visual Prolog представляет собой набор
фактов и правил. Иногда в процессе работы программы бывает необходимо
модифицировать (изменить, удалить или добавить) некоторые из фактов, с которыми
она работает. В этом случае факты рассматриваются как динамическая или внутренняя
база данных, которая при выполнении программы может изменяться. Для
объявления фактов программы, рассматривающихся как части динамической (или
изменяющейся) базы данных, Visual Prolog включает специальный раздел — facts.
Ключевое
слово facts объявляет раздел фактов. Именно в этой секции вы объявляете
факты, включаемые в динамическую базу данных. Отметим, что в ранних версиях Visual Prolog для объявления раздела
фактов использовалось ключевое слово database, т. е. ключевое слово facts — синоним устаревшего
ключевого слова database. В Visual Prolog есть несколько встроенных предикатов,
облегчающих использование динамических фактов.
В своих
программах на Visual Prolog вы можете объявлять и использовать символические константы.
Раздел для объявления констант обозначается ключевым словом constants, за которым следуют сами
объявления, использующие следующий синтаксис:
<id> =
<Макроопределение>
<id>— имя символической
константы, а <макроопределение> — это то, что вы присваиваете этой
константе. Каждое <макроопределение> завершается символом новой строки и,
следовательно, на одной строке может быть только одно описание константы.
Объявленные таким образом константы могут позже использоваться в программах.
Рассмотрим
следующий фрагмент программы:
constants
zеrо = О
one = 1
two = 2
hundred = (10*(10-1)+10)
pi = 3.141592653
ega = 3
slash_fill = 4
red = 4
Перед
компиляцией программы Visual Prolog заменит каждую константу на соответствующую ей
строку.
На
использование символических констант накладываются следующие ограничения:
·
описание
константы не может ссылаться само на себя:
my_number = 2*my_number/2
% не допускается
·
это
приведет к сообщению об ошибке "Recursion in constant definition" (Рекурсия в
описании константы);
·
в
описаниях констант система не различает верхний и нижний регистры.
Следовательно, при использовании в разделе программы clauses идентификатора типа constants, его первая буква должна
быть строчной для того, чтобы избежать путаницы между константами и
переменными.
·
в
программе может быть несколько разделов constants, однако объявление
константы должно производиться перед ее использованием;
·
идентификаторы
констант являются глобальными и могут объявляться только один раз.
Множественное объявление одного и того же идентификатора приведи к сообщению об
ошибке "Constant identifier can only be declared once" (Идентификатор
константы может объявляться только один раз).
Visual Prolog поддерживает несколько директив
компилятора, которые можно добавлять в программу для сообщения компилятору
специальных инструкций по обработке вашей программы при ее компиляции. Кроме
этого, вы можете устанавливать большинство директив компилятора с помощью
команды меню среды визуальной разработки Visual Prolog Options/Project/Compiler Options.
Директива include
Для того
чтобы избежать многократного набора повторяющихся процедур, вы можете
использовать директиву include.
Ниже приведен
пример того, как это делается.
1.
Создаете
файл (например, MYSTUFF.PRO), в котором объявляете свои наиболее I часто используемые
предикаты (с помощью разделов domains и predicates) и даете их описание в разделе clauses.
2.
Пишете
исходный текст программы, которая будет использовать эти процедуры.
3.
В
"допустимых областях" исходного текста программы размещаете строку:include "mystuff.pro"
"Допустимые
области" — это любое место программы, в котором вы можете расположить декларацию
разделов domains, facts, predicates, clauses или goal.
При
компиляции исходных текстов программы Visual Prolog вставит содержание файла
MYSTUFF.PRO прямо в окончательный
текст файла для компиляции.
Директиву include можно использовать для
включения в исходный текст (практически любого) часто используемого фрагмента.
Кроме того, любой включаемый в программу файл может, в свою очередь, включать
другой файл (однако каждый файл может быть включен в вашу программу только один
раз).
II. Унификация и поиск с возвратом
Рассмотрим программу 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)
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.
Рис. 1.
Листинг программы 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.
Часто при
решении реальной задачи мы придерживаемся определенного пути для ее логического
завершения. Если полученный результат не дает искомого ответа, мы должны
выбрать другой путь.
Так, вам, возможно, приходилось играть в лабиринт.
Один из верных способов найти конец лабиринта — это поворачивать налево на
каждой развилке лабиринта до тех пор, пока вы не попадете в тупик. Тогда
следует вернуться к последней развилке и попробовать свернуть вправо, после
чего опять поворачивать налево на каждом встречающемся распутье. Путем
методичного перебора всех возможных путей вы, в конце концов, найдете выход.
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).
Рис. 2.
Программа 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
Встроенный
механизм поиска с возвратом в Прологе может привести к поиску ненужных решений,
в результате чего теряется эффективность, например, когда желательно найти
только одно решение. В других случаях может оказаться необходимым продолжать
поиск дополнительных решений, даже если целевое утверждение уже согласовано.
Visual Prolog обеспечивает два
инструментальных средства, которые дают возможность управлять механизмом поиска
с возвратом: предикат fail, который используется для инициализации поиска с
возвратом, и cut или отсечение (обозначается !) — для запрета возможности
возврата.
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.
Рис. 3.
Программа 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, с и т. д.
r1
:- а,b,
!,
c.
Такая запись
является способом сообщить 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.
Рис. 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 пытается совершить поиск с возвратом с целью
найти другую машину для проверки. Отсечение предотвращает попытку решить
последнюю подцель, и наше целевое утверждение завершается неудачно.
Отсечение
может быть использовано, как способ сообщить Visual Prolog, что он выбрал верное
предложение для определенного предиката. Например, рассмотрим следующий
фрагмент:
r(1)
:-
!,
а,
b, с.
r(2):-
!,
d.
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 будет выдавать предупреждение в случае обнаружения
недетерминированных предложений в процессе компиляции.
Можно
превратить недетерминированные предложения в детерминированные, вставляя
отсечения в тело правил, определяющих данный предикат.
Следующая
программа 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) .
Рис. 5.
Программа 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 может создавать не только простые, но и составные типы.
Простой
объект данных — это переменная или константа. Не путайте это значение слова
"константа" с символьными константами, которые вы определяете в
разделе constants программы. То, что мы здесь называем константой, это нечто,
идентифицирующее объект, который нельзя изменять: символ (char), число (integer или real) или атом (symbol или string).
Константы включают числа, символы и
атомы. Числа и символы были рассмотрены ранее.
Атомы имеют тип идентификатор (symbol) или строка (string). Отличие между ними —
главным образом вопрос машинного представления и реализации, и, в основном, оно
синтаксически не заметно. Когда атом передается в качестве аргумента при вызове
предиката, то к какому домену принадлежит атом — symbol или string -определяется по тому,
как описан этот аргумент в декларации предиката.
Visual Prolog автоматически
преобразует типы между доменами string и symbol, поэтому вы можете использовать атомы symbol в доменах string и наоборот. Однако
принято считать, что объект в двойных кавычках принадлежит домену string, а объект, не
нуждающийся в кавычках, домену symbol. Атомы типа symbol — это имена,
начинающиеся со строчной буквы и содержащие только буквы, цифры и знак
подчеркивания.
Атомы типа string выделяются двойными
кавычками и могут содержать любую комбинацию литер, кроме ASCII-нуля (0, бинарный нуль),
который обозначает конец строки атома.
Примеры строк
и идентификаторов приведены в табл. 1.
Таблица 2.
Строки и идентификаторы
|
Атомы-идентификаторы
|
Атомы-строки
|
|
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.
Составные
объекты данных позволяют интерпретировать некоторые части информации как единое
целое таким образом, чтобы затем можно было легко разделить их вновь. Возьмем,
например, дату "октябрь 15, 1991". Она состоит из трех частей
информации — месяц, день и год. Представим ее на рис. 1, как древовидную
структуру.
Рис. 6.
Древовидная структура даты
Можно
объявить домен, содержащий составной объект 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))
Составной
объект может быть унифицирован с простой переменной или с составным объектом
(возможно, содержащим переменные в качестве частей во внутренней структуре),
который ему соответствует. Это означает, что составной объект можно
использовать для того, чтобы передавать целый набор значений как единый объект,
и затем применять унификацию для их разделения. Например:
date("April",14,I960)
сопоставляется
с X и присваивает X значение date ("April", 14,1960). Также
date("April",14,I960)
сопоставляется
с date (Mo, Da, Yr) и присваивает
переменным Мо = "April", Da=14 и Yr = 1960.
Составные
объекты могут рассматриваться в предложениях Пролога как единые объекты, что
сильно упрощает написание программ. Рассмотрим, например, факт:
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 названием книги или именем лошади.
Рассмотрим,
как определяются составные домены. После компиляции программы, которая содержит
следующие отношения:
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.
К определению
домена легко могут быть добавлены другие варианты.
Visual Prolog позволяет конструировать
составные объекты на нескольких уровнях. Например:
domains
articles
= book(title, author);%Первый уровень
author=
author(first_name, last_name) %Второй уровень
title,
first_name, last_name = symbol%Третий уровень
При
использовании составных объектов со многими уровнями часто помогает такое
"дерево" (рис. 7):
Рис. 7.
Дерево многоуровневого составного объекта
Повтор и рекурсия
Компьютеры
способны повторять одно и то же действие снова и снова, Visual Prolog может выражать
повторение как в процедурах, так и в структурах данных. Идея повторяющихся
структур данных может показаться странной, но Пролог позволяет создавать
структуры данных, размер которых не известен во время создания.
Программисты
на языках 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.
Рис. 8.
Программа 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
:-
readchar(C),%
Читать символ, его значение присвоить С
write(С),
С
= '\r',% Символ возврат каретки (Enter)? или неуспех
goal
typewriter
(), nl.
Рис. 9.
Листинг 13.2. Программа ch06e02.pro
Программа ch06e02 pro показывает, как работает
repeat Правило typewriter - описывает процесс приема символов с клавиатуры и
отображения их на экране, пока пользователь не нажмет клавишу <Enter>
(<Return>)
Правило typewriter работает следующим образом
1 Выполняет repeat (который ничего не делает, но
ставит точку отката).
2 Присваивает переменной с значение символа.
3 Отображает С.
4 Проверяет, соответствует ли с коду возврата
каретки.
5 Если соответствует, то — завершение. Если нет —
возвращается к точке отката и ищет альтернативы, так как ни write, ни readchar
не являются альтернативами,
Одним из
способов организации повторений — рекурсия. Рекурсивная процедура — это
процедура, которая вызывает сама себя. В рекурсивной процедуре нет проблемы
запоминания результатов ее выполнения, потому что любые вычисленные значения
можно передавать из одного вызова в другой как аргументы рекурсивно вызываемого
предиката.
Логика
рекурсии проста для осуществления. Представьте себе ЭВМ, способную
"понять":
Найти
факториал числа 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. Том - ближайший предок Лиз и отдаленный
предок Пат.
Рис. 10.
Пример отношения предок:(а) 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).
Рис. 11.
Пары предок-потомок, разделенных разным числом поколений.
Эта программа
длинна и, что более важно, работает только в определенных пределах. Она будет
обнаруживать предков лишь до определенной глубины фамильного дерева, поскольку
длина цепочки людей между предком и потомком ограничена длиной наших
предложений в определении отношения.
Существует,
однако, корректная и элегантная формулировка отношения предок - корректная в
том смысле, что будет работать для предков произвольной отдаленности. Ключевая
идея здесь - определить отношение предок через него самого. Рис. 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).
Рис. 12.
Рекурсивная формулировка отношения предок.
Ключевым
моментом в данной формулировке было использование самого отношения предок в его
определении. Такие определения называются рекурсивными. Логически они
совершенно корректны и понятны. Рекурсия - один из фундаментальных приемов
программирования на Прологе. Без рекурсии с его помощью невозможно решать
задачи сколько-нибудь ощутимой сложности.
У рекурсии
есть один большой недостаток — она «съедает» память. Всякий раз, когда одна
процедура вызывает другую, информация о выполнении вызывающей процедуры должна
быть сохранена для того, чтобы она (вызывающая процедура) могла, после
выполнения вызванной процедуры, возобновить выполнение на том же месте, где
остановилась. Это означает, что если процедура вызывает себя 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).
В Прологе список
— это объект, который содержит конечное число других объектов. Списки можно
грубо сравнить с массивами в других языках, но, в отличие от массивов, для
списков нет необходимости заранее объявлять их размер.
Список,
содержащий числа 1, 2 и 3, записывается так:
[1,
2, 3]
Каждая
составляющая списка называется элементом. Чтобы оформить списочную
структуру данных, надо отделить элементы списка запятыми и заключить их в квадратные
скобки. Вот несколько примеров:
[dog,
cat, canary]
["valerie
ann", "jennifer caitlin", "benjamin thomas"]
Чтобы
объявить домен для списка целых, надо использовать декларацию домена, такую
как:
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
Список
является рекурсивным составным объектом. Он состоит из двух частей — головы,
которая является первым элементом, и хвоста, который является списком,
включающим все последующие элементы. Хвост списка — всегда список,
голова списка — всегда элемент. Например:
голова [а, b, с] есть а
хвост [а, b, с] есть [b, с]
Что
происходит, когда вы доходите до одноэлементного списка? Ответ таков:
голова [с] есть
с
хвост [с]
есть []
Если выбирать
первый элемент списка достаточное количество раз, вы обязательно дойдете до
пустого списка []. Пустой список нельзя разделить на голову и хвост.
В
концептуальном плане это значит, что список имеет структуру дерева, как и
другие составные объекты. Структура дерева [а, b, с, d] представлена на рис. 1.
Рис. 1.
Структура дерева
Одноэлементный
список, как, например [а], не то же самое, что элемент, который в него входит,
потому что [а] на самом деле — это составная структура данных.
В Прологе
есть способ явно отделить голову от хвоста. Вместо разделения элементов
запятыми, это можно сделать вертикальной чертой "|". Например:
[а, 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.
Использование
списков
Список
является рекурсивной составной структурой данных, поэтому нужны алгоритмы для
его обработки. Главный способ обработки списка — это просмотр и обработка
каждого его элемента, пока не будет достигнут конец.
Алгоритму
этого типа обычно нужны два предложения. Первое из них говорит, что делать с
обычным списком (списком, который можно разделить на голову и хвост), второе —
что делать с пустым списком.
Если нужно
напечатать элементы списка, это делается так, как показано в листинге 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, описанные на обычном
языке:
Печатать
пустой список — значит ничего не делать.
Иначе,
печатать список — означает печатать его голову (которая является одним
элементом), затем печатать его хвост (список) .
Рассмотрим,
как можно определить число элементов в списке. Что такое длина списка? Вот
простое логическое определение:
Длина
[] — 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] Имеются и другие
стандартные домены.