Visual prolog руководство

В этом руководстве мы представляем программу, разработанную на платформе системы программирования Visual Prolog. Алгоритмы, используемые в руководстве , — те же, что и в руководстве «Fundamental Prolog» (Часть 2).

Отличия между Visual Prolog и традиционным Прологом

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

• Различия в структуре программы:
  Различия между Visual Prolog и традиционным Прологом имеются, но они не существенны. Они сводятся к пониманию того, как различаются декларации (declarations) от определений (definitions), а также к явному выделению цели Goal. Все это поддержано специальными ключевыми словами.

• Файловая структура программы::
  Visual Prolog предоставляет возможности структуризации программ с использованием файлов различного типа.

• Границы видимости:
  Программа системы Visual Prolog может поддерживать функционирование, располагающееся в различных модулях с использованием концепции идентификация пространств.

• Объектная ориентированность:
  Программа на языке Visual Prolog может быть написана как объектно ориентированная программа с использованием классических свойств объектно-ориентированной парадигмы.

Различия в структуре программ

Декларации и Определения

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

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

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

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

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

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

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

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

Ключевые слова

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

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

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

В этом руководстве используются следующие ключевые слова:

implement и end implement

Среди всех ключевых слов, обсуждаемых здесь, это единственные ключевые слова, используемые парно. Visual Prolog рассматривает код, помещенный между этими ключевыми словами, как код, принадлежащий одному классу. За ключевым словом implement обязательно ДОЛЖНО следовать имя класса.

open

Это ключевое слово используется для расширения области видимости класса. Оно должно быть помещено вначале кода класса, сразу после ключевого слова implement (с именем класса и, возможно именем интерфейса — прим. перев.).

constants

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

constants
pdc="PDC Prolog".

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

domains

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

Вообще говоря, объявляется функтор, который будет использоваться в качестве домена и ряд доменов, которые используются в качестве его аргументов. Функторы и составные домены рассматриваются в соответствующем руководстве.

class facts

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

class predicates

Эта секция содержит объявления предикатов, которые определяются в тексте программы в разделе clauses. И опять, объявление предиката — это имя, которое присваивается предикату, и набор аргументов, каждый из которых должен соответствовать либо стандартному (предопределенному), либо объявленному домену.

clauses

Среди всех разделов, существующих в тексте программ на Visual Prolog, это единственный раздел, который близко совпадает с традиционными программами на Прологе. Он содержит конкретные определения объявленных в разделе class predicates предикатов, причем синтаксически им соответствующие.

goal

Этот раздел определяет главную точку входа в программу на языке системы Visual Prolog. Более детальное описание приводится ниже.

Goal (цель)

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

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

Файловое структурирование программ

Необходимость помещения всех частей большой программы в один файл несомненно является неудобством. Это ведет к тому, что программа становится нечитаемой и иногда неправильной. Visual Prolog предусматривает возможность деления текста программы на отдельные файлы, используя среду IDE (Integrated Development Environment) и, кроме того, IDE позволяет помещать логически связанные фрагменты текста программы в отдельные файлы. Несмотря на такое разделение программы на части, сущности, находящиеся в общем использовании, доступны.

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

Для упрощения этого руководства мы будем использовать один файл для разработки текста программы. На самом деле в процессе построения программы среда IDE создавала бы автоматически несколько файлов, но мы сейчас будем это умалчивать. Об этом написано в других руководствах.

Расширение Области Видимости

В Visual Prolog текст программы разделен на отдельные части, какждая часть определяется как класс (class). В объектно-ориентированных языках программирования, класс — это пакет кода и ассоциированные с ним данные. Это требует длительных объяснений и сделано в других руководствах. Те, кто не знаком с объектно-ориентированным программированием, может представлять себе класс нестрого как синоним понятия модуль. В Visual Prolog каждый класс обычно помещается в отдельный файл.

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

Visual Prolog позволяет делать такие взаимные ссылки на предикаты или данные используя так называемую концепцию области видимости (scope access). Это может стать понятным на примере. Предположим имеется предикат, называемый pred1 и определенный в классе называемом class1 (который помещается в другом файле, согласно стратегии среды IDE), и мы хотим вызвать этот предикат в теле клауза некоторого другого предиката pred2, находящегося в другом файле (скажем, class2). Тогда вот как предикат pred1 должен бы быть вызван в теле клауза предиката pred2 :

clauses
  pred3:-
    ...
    !.
 
  pred2:-
    class1::pred1, % pred1 неизвестен в этом файле. 
                   % Он определен в другом файле, 
                   % поэтому требуется квалификатор класса.
    pred3,
    ...

В приведенном примере видно, что тело клауза предиката pred2 вызывает два предиката pred1 и pred3. Поскольку pred1 определен в другом файле (где определен класс class1), постольку слово class1 с символом :: (два двоеточия) предшествует слову pred1. Это можно назвать как квалификатор класса. Но предикат pred3 определен внутри того же самого файла, что и предикат pred2. Поэтому здесь нет необходимости использовать class2:: перед вызовом предиката pred3.

Технически такое поведение объясняется следующим: Область видимости (scope visibility) предиката pred3 находится внутри той же области, где находится предикат pred2. Поэтому здесь не нужно показывать, что pred3 и pred2 находятся в одном классе. Компилятор автоматически увидит определение предиката pred3 внутри той же области, в классе class2.

Область видимости конкретного класса лежит внутри границ, где класс определен (то есть в интервале между ключевыми словами implement — end implement ). Предикаты, определенные здесь, могут вызывать друг друга без квалификатора класса и двойного двоеточия (::).

Область видимости класса может быть расширена использованием ключевого слова open. Это ключевое слово информирует компилятор о том, что в этот класс должны быть «доставлены» имена (предикатов / констант / доменов), которые были определены в других файлах. Если область видимости расширена, то необходимости использования квалификатора класса (с двойным двоеточием) нет.

open class1
  ...
 
clauses
  pred3:-
    ...
    !.
 
  pred2:-
    pred1, % Внимание: квалификатор "class1::" больше не нужен,
           % поскольку область видимости расширена 
           % использованием ключевого слова 'open'
    pred3,
    ...

Объектная ориентированность

Visual Prolog является полностью объектно-ориентированным языком.

Весь код, который разрабатывается для программы, помещается в класс. Это происходит само собой, даже если Вы не интересуетесь объектными свойствами языка. Это свойство обнаруживается в примере, разбираемом в этом руководстве. Код помещается в класс, называемый «family1», несмотря на то, что мы не используем объекты, порождаемые этим классом. Кроме того, вы этом классе мы используем общедоступные предикаты, находящиеся в других классах.

В этом руководстве объектные свойства языка не используются. Объектные свойства языка используются в других руководствах.

Полностью работающий пример: family1.prj6

Сгрузитe: Исходные Файлы проекта, используемого в этом руководстве.

Давайте теперь все полученные знания соберем вместе и создадим первую программу на языке системы Visual Prolog. Общая логика будет та же, что и рассмотренная в руководстве «Fundamental Prolog. Part 2». Текст программы приведен ниже. Его надо поместить в файл с именем family1.pro. Реальный текст программы мы напишем с помощью среды IDE (Integrated Development Environment) системы Visual Prolog. На самом деле файлов больше, чем требуется для этого руководства, но они будут созданы (и в дальнейшем будут поддерживаться) автоматически средой IDE. Пошаговая инструкция по использованию IDE (с фрагментами экрана) для разработки программы приводится ниже.

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

implement family1
open core
 
constants
  className = "family1".
  classVersion = "$JustDate: $$Revision: $".
 
clauses
  classInfo(className, classVersion).
 
domains
  gender = female(); male().
 
class facts - familyDB
  person : (string Name, gender Gender).
  parent : (string Person, string Parent).
 
class predicates
  father : (string Person, string Father) nondeterm anyflow.
clauses
  father(Person, Father) :-
    parent(Person, Father),
    person(Father, male()).
 
class predicates
  grandFather : (string Person, string GrandFather) nondeterm anyflow.
clauses
  grandFather(Person, GrandFather) :-
    parent(Person, Parent),
    father(Parent, GrandFather).
 
class predicates
  ancestor : (string Person, string Ancestor) nondeterm anyflow.
clauses
  ancestor(Person, Ancestor) :-
    parent(Person, Ancestor).
  ancestor(Person, Ancestor) :-
    parent(Person, P1),
    ancestor(P1, Ancestor).
 
class predicates
  reconsult : (string FileName).
clauses
  reconsult(FileName) :-
    retractFactDB( familyDB),
    file::consult(FileName, familyDB).
 
clauses
  run():-
    console::init(),
    stdIO::write("Load datan"),
    reconsult("fa.txt"),
    stdIO::write("nfather testn"),
    father(X, Y),
      stdIO::writef("% is the father of %n", Y, X),
    fail.
  run():-
    stdIO::write("ngrandFather testn"),
    grandFather(X, Y),
      stdIO::writef("% is the grandfather of %n", Y, X),
    fail.
  run():-
    stdIO::write("nancestor of Pam testn"),
    X = "Pam",
    ancestor(X, Y),
      stdIO::writef("% is the ancestor of %n", Y, X),
    fail.
  run():-
    stdIO::write("End of testn").
end implement family1
 
goal
mainExe::run(family1::run).

Шаг 1: Создайте в IDE новый консольный проект

Шаг 1a. После старта среды программирования Visual Prolog, выберите New из меню Project.

Шаг 1b. Появляется диалог. Введите соответствующую информацию. Удостоверьтесь, что стратегия пользовательского интерфейса (UI Strategy) Console, а НЕ GUI.

Шаг 2: Постройте пустой проект

Шаг 2a. Когда проект только что создан, среда будет показывать проектное окно, как показано ниже. В этот момент пока никакой информации о том, от каких файлов зависит проект, нет. Однако основные тексты программ проектных файлов уже созданы.

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

В процессе построения проекта посмотрите на сообщения, которые динамически появляются в окне Messages среды IDE. (Если окно Messages не видно, его можно вызвать на передний план, используя меню Window в среде IDE). Вы заметите, что среда IDE разумно включит в Ваш проект ВСЕ в необходимые модули PFC (Prolog Foundation Classes). Классы PFC являются теми классами, которые содержат поддержку функционирования программ, которые Вы строите.

Шаг 3: Поместите в файл family1.pro актуальный код

Шаг 3a. Начальный код, созданный самой средой IDE имеет самый общий вид и сам по себе не делает ничего полезного. Вам необходимо удалить этот код полностью и скопировать (через Copy и Paste) полностью (актуальный на данный момент) код программы family1.pro (приведенный в этом руководстве) в окно редактора.

Шаг 3b. После выполнения операции copy-paste окошко с текстом файла family1.pro должно выглядеть так, как показано ниже:

Шаг 4: Перестроение кода проекта

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

В процессе выполнения команды Build среда IDE выполняет не только компиляцию. В это же время выясняется, нужны ли проекту другие модули из набора PFC (Prolog Faundation Classes), и, если это так, то такие модули добавляются и вызывается повторная перекомпиляция, если необходимо. Этот процесс можно наблюдать по сообщениям, появляющимся в окне сообщений (Message Window). Можно увидеть как IDE вызвало построение проекта дважды, поскольку были обнаружены директивы «include», повлиявшие на это.

Файл:FundamentalVisualProlog7.jpg

Шаг 5: Исполнение Программы

Теперь у нас есть приложение, успешно откомпилированное с помощью Visual Prolog. Для того, чтобы проверить работу приложения, которое только что построено, можно запустить ее выполнение, вызвав команду из меню Build | Run in Window. Но в нашем случае это приведет к ошибке. Причина заключается в том, что наша маленькая программа для обеспечения своей работы пытается читать текстовый файл fa.txt. Этот текстовый файл содержит содержит записи относительно лиц, которые (записи) программа должна обработать. Вопросов синтаксита представления данных в этом файле мы коснемся позже.

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

Давайте создадим такой файл сами с использованием среды IDE. Вызовите команду меню File | New. Появляется окно создания новой сущности Create Project Item. Выберите Текстовый файл (Text File) в списке слева. Затем выберите директорию, где будет размещаться файл (та же директория, где располагается исполняемое приложение family1.exe). Присвойте теперь имя fa.txt файлу и нажмите кнопку Create (создать). До тех пор, пока имя файла не введено, кнопка Create (создать) будет неактивна (надпись серого цвета). Удостоверьтесь, что флажот Add to project as module (добавить в проект на правах модуля) включен. Полезность включения файла в проект заключается в том, что это будет удобно для последующей отладки и других действий.

Файл следует заполнить текстом следующего содержания:

clauses
    person("Judith",female()).
    person("Bill",male()).
    person("John",male()).
    person("Pam",female()).
    parent("John","Judith").
    parent("Bill","John").
    parent("Pam","Bill").

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

Синтаксис файла fa.txt ДОЛЖЕН быть совместим с определениями доменов в программе. Например, функтор, применяемый для определения персоны ДОЛЖЕН быть person и никак иначе. В противном случае соответствующий составной домен не будет инициализирован. (Понятия функторов и составных доменов рассматриваются в других руководствах).

Теперь, запустив программу по команде меню Build | Run in the Window вы увидите:

Программа обрабатывает данные, помещенные в файл fa.txt и порождает логические связи персон, данные о которых там помещены.

Рассмотрение программы

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

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

Обработка данных основывается на стандартных механизмах отката и рекурсивных вызовов. В этом руководстве детально не рассматривается как работает Пролог, но приведем краткое описание работы.

Когда предикат run вызывает предикат father, он не ограничивается первым удовлетворяющим решением предиката father. Применение предиката fail в конце последовательности понуждает механизм Пролога к поиску следующего прохода предиката father. Такое поведение, называется backtracking (откат), поскольку кажется, что механизм Пролога буквально перепрыгивает назад, минуя ранее исполненный код.

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

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

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

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

И, наконец, квалификатор anyflow включает ситуацию, когда оба параметра предиката father являются свободными переменными. В этом случае, предикат father вернет в ответ на запрос различные комбинации отношений родитель-потомок, предусмтотренные в программе (представленные в загружаемом файле fa.txt). Последний вариант как раз и использован в предикате run, как видно во фрагменте, приведенном ниже. Можно заметить, что переменные X и Y переданные предикату father не связаны при его вызове.

clauses
    run():-
        console::init(),
        stdIO::write("Load  datan"),
        reconsult("fa.txt"),
        stdIO::write("nfather testn"),
        father(X,Y),
        stdIO::writef("% is the father of %n", Y, X),
        fail.

Заключение

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

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

Ссылки

Язык логического программирования Visual Prolog

I.
Основы языка Visual
Prolog

1.
Введение в
логическое программирование

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

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

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

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

Таблица 1.
Синтаксис логики предикатов

2.
Факты

На Прологе
описываются объекты (objects) и отношения (relations), а затем описывает правила
(rules), при которых эти отношения являются истинными. Например, предложение

Билл любит собак. (Bill likes dogs.)

устанавливает
отношение между объектами Bill и dogs (Билл и собаки); этим отношением является likes (любит). Ниже
представлено правило, определяющее, когда предложение «Билл любит
собак» является истинным:

Билл любит собак, если собаки хорошие. (Bill likes dogs if the dogs are nice.)

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

Ниже
представлено несколько предложений на естественном языке с отношением
«любит» (likes):

Билл любит Синди. (Bill
likes Cindy)

Синди любит Билла.
(Cindy likes Bill)

Билл любит собак. (Bill likes dogs)

А теперь
перепишем эти же факты, используя синтаксис Пролога:

likes(bill, cindy).

likes(cindy, bill).

likes (bill, dogs).

Факты, помимо
отношений, могут выражать и свойства. Так, например, предложения естественного
языка «Kermit is green» (Кермит зеленый) и «Caitlin is girl» (Кейтлин —
девочка) на Прологе, выражая те же свойства, выглядят следующим образом:

green (kermit).

girl(caitlin).

3.
Предикаты

Отношение в
Прологе называется предикатом. Аргументы — это объекты, которые
связываются этим отношением; в факте

likes (bill, cindy).

отношение likes — это предикат, а
объекты bill и cindy — аргументы.

Примеры
предикатов с различным числом аргументов:

pred(integer, symbol)

person (last, first, gender)

run()

birthday(firstName, lastName,
date)

В примере
показано, что предикаты могут вовсе не иметь аргументов.

4.
Правила

Правила
позволяют вам вывести один факт из других фактов. Другими словами, можно
сказать, что правило — это заключение, для которого известно, что оно
истинно, если одно или несколько других найденных заключений или фактов являются
истинными. Ниже представлены правила, соответствующие связи «любить»
(likes):

Синди любит все, что любит Билл. (Cindy likes everything that Bill likes)

Кейтлин любит все зеленое. (Caitlin likes everything that is green)

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

Синди любит Синди. (Cindy likes Cindy)

Кейтлин любит Кермит. (Caitlin likes
Kermit)

Чтобы
перевести эти правила на Пролог, вам нужно немного изменить синтаксис:

likes(cindy,
Something):- likes (bill, Something). ilikes(caitlin, Something):- green
(Something) .

Символ :-
имеет смысл «если», и служит для разделения двух частей правила:
заголовка и тела. Можно рассматривать правило и как процедуру. Другими словами, правила

likes(cindy,
Something):- likes (bill, Something).

likes(caitlin, Something):- green
(Something).

означают: «Чтобы
доказать, что Синди любит что-то, докажите, что Билл любит это» и
«Чтобы доказать, что Кейтлин любит что-то, докажите, что это что-то зеленое».
С такой «процедурной» точки зрения правила могут
«попросить» Пролог выполнить другие действия, отличные от
доказательств фактов, например, напечатать что-нибудь.

5.
Запросы
(Цели)

Описав в
Прологе несколько фактов, можно задавать вопросы, касающиеся отношений между
ними. Это называется запросом (query) системы языка Пролог. Можно задавать Прологу
такие же вопросы, которые мы могли бы задать вам об этих отношениях.
Основываясь на известных, заданных ранее фактах и правилах, вы можете ответить
на вопросы об этих отношениях, в точности так же это может сделать Пролог. На
естественном языке мы спрашиваем: Does Bill like Cindy? (Билл любит Синди?) По правилам Пролога мы
спрашиваем:

likes(bill, cindy).

Получив такой
запрос, Пролог ответит:

yes (да)

потому что
Пролог имеет факт, подтверждающий, что это так. Немного усложнив вопрос, можно
спросить на естественном языке: What does Bill like? (Что любит Билл?) По правилам Пролога мы
спрашиваем:

likes(bill, What).

Необходимо
отметить, что второй объект — What -начинается с большой буквы, тогда как первый
объект — bill — нет. Это происходит потому, что bill — фиксированный,
постоянный объект — известная величина, a What — переменная.

Переменные
всегда
начинаются с заглавной буквы или символа подчеркивания!

Пролог
всегда ищет ответ на запрос, начиная с первого факта, и перебирает все факты,
пока они не закончатся. Получив запрос о том, что Билл любит, Пролог ответит:

What=cindy

What=dogs

2 Solutions

Так, как ему
известно, что

likes(bill, cindy).

и

likes(bill, dogs) .

Если бы мы
спросили:

What does Cindy like? (Что любит Синди?)

likes(cindy, What).

то Пролог
ответил бы:

What = bill

What = cindy

What = dogs

3 solutions

поскольку
Пролог знает, что Синди любит Билла, и что Синди любит то же, что и Билл, и что
Билл любит Синди и собак.

Мы могли бы
задать Прологу и другие вопросы, которые можно задать человеку. Но вопросы типа
«Какую девушку любит Билл?» не получат решения, т. к. Прологу в
данном случае не известны факты о девушке, а он не может вывести заключение,
основанное на неизвестных данных: в этом примере мы не дали Прологу
какого-нибудь отношения или свойства, чтобы определить, являются ли какие-либо
объекты девушками.

6.
Размещение фактов,
правил и запросов

Предположим,
есть следующие факты и правила:

Быстрая машина — приятная. (A fast car is fun).

Большая машина — красивая. (A big car is nice).

Маленькая машина —
практичная. (A little car is practical).

Биллу нравится машина, если она приятная.
(Bill likes a car if the car is fun).

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

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

likes(ellen, tennis).

likes (John, football).

likes (torn, baseball).

likes (eric, swimming).

likes (mark, tennis).

likes (bill, Activity):-
likes (torn, Activity).

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

Биллу нравится занятие, если Тому
нравится это занятие. (Bill likes an activity if Tom likes
that activity)

В данном
правиле заголовок — это likes (bill, Activity), а тело — likes (torn, Activity). Заметим, что в этом
примере нет фактов о том, что Билл любит бейсбол. Чтобы выяснить, любит ли Билл
бейсбол, можно дать Прологу такой запрос:

likes (bill, baseball).

Пытаясь отыскать
решение по этому запросу, Пролог будет использовать правило:

likes(bill, Activity):-
likes(torn, Activity).

Загрузите
программу ch02e01.pro в среду визуальной разработки Visual Prolog и запустите ее утилитой Test Goal.

predicates

likes(symbol,symbol)

clauses

likes(ellen,tennis).

likes(John,football).

likes(torn,baseball).

likes(eric,swimming).

likes(mark,tennis).

likes(bill,Activity):-likes(torn,
Activity).

goal

likes(bill,
baseball).

Утилита Test Goal ответит в окне
приложения:

yes (да)

Система
использовала комбинированное правило

likes(bill, Activity):-
likes(torn, Activity).

с фактом

likes(torn, baseball).
для решения, что likes(bill, baseball).

Попробуйте
также следующий запрос в GOAL-разделе:

likes (bill, tennis).

Утилита Test Goal ответит:

no (нет)

поскольку:

·  
нет
фактов, которые говорят, что Билл любит теннис;

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

Вполне
возможно, что Билл любит теннис в реальной жизни, но ответ Visual Prolog
основан только на фактах и правилах, которые вы дали ему в тексте программы.

7. ПРОГРАММЫ
НА VISUAL PROLOG

Синтаксис Visual Prolog разработан для того,
чтобы отображать знания о свойствах и взаимосвязях.

В отличие от
других версий Пролога, Visual Prolog — компилятор, контролирующий типы: для каждого
предиката объявляются типы объектов, которые он может использовать. Это
объявление типов позволяет программам Visual Prolog быть скомпилированными
непосредственно в машинные коды, при этом, скорость выполнения сравнима, а в
некоторых случаях — и превышает скорости аналогичных программ на языках С и Pascal.

8. Основные разделы Visual Prolog-программ

Обычно
программа на Visual Prolog состоит из четырех основных программных разделов, к
которым относятся:

·  
раздел
clauses (предложений);

·  
раздел
predicates
(предикатов);

·  
раздел
domains
(доменов);

·  
раздел
goal
(целей).

Раздел clauses — это сердце Visual Prolog-программы; именно в этот
раздел записываются факты и правила, которыми будет оперировать Visual Prolog, пытаясь разрешить цель
программы.

Раздел predicates — это тот, в котором
объявляются предикаты и домены (типы) их аргументов (вам не нужно объявлять
предикаты, встроенные в Visual Prolog).

Раздел domains служит для объявления
доменов, не являющихся стандартными доменами Visual Prolog.

В раздел goal помещается цель Visual Prolog-программы.

9.
Раздел предложений

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

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

10.
Раздел предикатов

Если в
разделе clauses программы на Visual Prolog описан собственный предикат, то его необходимо
объявить в разделе predicates (предикатов). В результате объявления предиката сообщается,
к каким доменам (типам) принадлежат аргументы этого предиката.

11. ОБЪЯВЛЕНИЕ
ПОЛЬЗОВАТЕЛЬСКОГО ПРЕДИКАТА

Объявление предиката
начинается с имени этого предиката, за которым идет открывающая (левая) круглая
скобка, после чего следует ноль или больше доменов (типов) аргументов
предиката:

predicateName
(argument_typel OptionalNamel,

argument_type2
OptionalName2, …,

argument_typeN OptionalNameN)

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

Имена предикатов

Имя предиката
должно начинаться с буквы, за которой может располагаться последовательность
букв, цифр и символов подчеркивания. Буквы должны быть в нижнем регистре!
Имя предиката может иметь длину до 250 символов.

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

Аргументы
предикатов

Аргументы
предикатов должны принадлежать доменам, известным Visual Prolog. Эти домены могут быть
либо стандартными, либо пользовательскими.

12.
Раздел доменов

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

Иногда очень
полезно описать новый домен — особенно, когда вы хотите прояснить отдельные
части раздела predicates. Объявление собственных доменов, благодаря присваиванию осмысленных
имен типам аргументов, помогает документировать описываемые вами предикаты. Рассмотрим
пример, показывающий, как объявление доменов помогает документировать
предикаты:

Франк — мужчина, которому 45 лет.

Используя
стандартные домены, вы можете так объявить соответствующий предикат:

person(symbol, symbol, integer).

В большинстве
случаев такое объявление будет работать хорошо, но не наглядно для чтения
программы. Более правильным было бы следующее описание:

domains

name, sex = symbol

age = integer

predicates

person(name, sex, age)

Одним из
главных преимуществ объявления собственных доменов является то, что Visual Prolog может отслеживать ошибки
типов, например, такие:

same_sex(X,Y):-

person(X, Sex, _),

person(Sex, Y, _).

Несмотря на
то, что и name и sex описываются как symbol, они не эквивалентны друг другу. Это и позволяет
Visual Prolog определить ошибку, если
вы перепутаете их. Это полезно в тех случаях, когда ваши программы очень велики
и сложны.

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

Следующий
пример программы при его загрузке приведет к ошибке типа.

Domains product, sum =
integer

predicates

add_em_up(sum,sum,sum)

multiply_em(product,product,product)

clauses

add_em_up(X, Y, Sum):-Sum=X+Y.

multiply_em(X,Y,Product):-Product=X*Y.

Эта программа
выполняет две операции: складывает и умножает. Зададим ей следующую цель:

add_em_up(32, 54, Sum)
.

Visual
Prolog (Test Goal) ответит:

Sum=86

1 Solution

что является
суммой двух целых чисел, которые вы передали в программу.

С другой
стороны, эта же программа с помощью предиката multiply_em умножает два аргумента.
Допустим, мы хотим удвоить произведение 31 на 17. Задаем следующую цель:

multiply_em(31, 17, Sum), add_em_up(Sum, Sum, Answer).

и ждем, что Visual Prolog (Test Goal)
ответит:

Sum=527, Answer=1054

1 Solution

Однако вместо
этого вы получите ошибку типа. Это случилось из-за того, что имела место
попытка передать результирующее значение предиката multiply_em, которое относится к
домену product, в качестве первого и второго аргументов (которые должны
относится к домену sum) в предикат add_em_up. И хотя оба эти домена соответствуют типу integer — это различные домены.

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

13.
Раздел цели

По существу,
раздел goal (цели) аналогичен телу правила: это просто список подцелей. Цель
отличается от правила лишь следующим:

·  
за
ключевым словом goal не следует :-;

·  
при
запуске программы Visual Prolog автоматически выполняет цель.

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

14.
Декларации и правила

В Visual Prolog есть несколько
встроенных стандартных доменов. Их можно использовать при декларации типов
аргументов предикатов без описания в разделе domains.

Основные
стандартные домены перечислены в табл. 1.

Таблица 1.
Основные
стандартные домены

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

Домены типов byte, word и dword наиболее удобны при
работе с машинными числами. В основном используются типы integer и unsigned, а также short и long (и их беззнаковые
аналоги) для более специализированных приложений.

В объявлениях
доменов ключевые слова signed и unsigned могут использоваться вместе со стандартными
доменами типов byte, word и dword для построения новых базовых доменов. Так:

domains

i8 = signed byte

создает новый
базовый домен в диапазоне от -128 до +127.

Другие
базовые домены показаны в табл. 2[1].

Таблица 2.
Основные
стандартные домены

Идентификаторы
и строки взаимозаменяемы в программе, однако 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.

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

15.
Другие разделы программ

Теперь, когда
вы ознакомились с такими разделами программ 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. Унификация и поиск с возвратом

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)

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.

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).

Рис. 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

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 fathern»), 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 fathern»),

fail.

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

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

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

Прерывание поиска с возвратом:
отсечение

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

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

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

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

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

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

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

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 пытается совершить поиск с возвратом с целью
найти другую машину для проверки. Отсечение предотвращает попытку решить
последнюю подцель, и наше целевое утверждение завершается неудачно.

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

Отсечение
может быть использовано, как способ сообщить 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 будет выдавать предупреждение в случае обнаружения
недетерминированных предложений в процессе компиляции.

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

Предикат 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) .

Рис. 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 может создавать не только простые, но и составные типы.

5. Простые
объекты данных

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

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

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

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

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

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

Таблица 2.
Строки и идентификаторы

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

6. Составные
объекты данных и функторы

Составные
объекты данных позволяют интерпретировать некоторые части информации как единое
целое таким образом, чтобы затем можно было легко разделить их вновь. Возьмем,
например, дату «октябрь 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))

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):

Рис. 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.

Рис. 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
не являются альтернативами,

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. Том — ближайший предок Лиз и отдаленный
предок Пат.

Рис. 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).

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.
Присвоение в списках

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] Имеются и другие
стандартные домены.

Заказать решение задачи на Prolog можно тут

Цель работы: ознакомление с основами среды логического программирования Visual Prolog.

Установка Visual Prolog

Скачать Visual Prolog 5.2.
32-х разрядная версия Visual Prolog 5.2 для Windows была установлена на 64х разрядный компьютер с операционной системой OpenSUSE 42.1, при этом использовался Wine 1.8.4. Процесс установки ничем не отличается от установки под Windows, при клике по установщику автоматически запускается Wine и процесс установки продолжается в обычном режиме.

Создание проекта в Visual Prolog

После установки системы, запускаем Visual Prolog и создаем проект. В появившемся окне вводим имя проекта и путь к нему.

Затем нужно перейти во вкладку Target и выбрать консольный режим (Textmode), т. к. наше приложение будет консольным:

Нажимает кнопку Create, после этого будет открыто рабочее окно системы, в левой части которого отобразится структура проекта. Проект содержит файл parents.pro с исходным кодом.

Разработка программы в Visual Prolog

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

Открываем файл parents.pro, приступаем к написанию исходного кода. Нам требуется создать базу родственных отношений между именами. Опишем тип имени в секции domains:

domains
	name = symbol

В данном случае записано, что name является эквивалентом типа данных symbol. В свою очередь symbol — это символьный тип данных, элементами которого могут являться как строки (например, «Ilia», «Elena»), заключенные в кавычки, так и любые идентификаторы, начинающиеся со строчной буквы (например marina, ira и т. п.).

Опишем отношение базы данных, задающее родство двух имен:

database
	parent(name, name)

Теперь можно добавлять элементы во внутреннюю базу данных. Сделать это можно в секции clauses:

clauses
	parent(ilia, marina).
	parent(marina, ira).
	parent(elena, ivan).
	parent(nikolay, ira).
	parent(olga, aleksei).
	parent(marina, sasha).
	parent(sergei, ivan).

Первый запрос, который мы реализуем, должен проверять, что «Марина является родителем Саши». Запросы описываются в секции goal:

Для запуска цели нажимает комбинацию Ctrl+g, программа запускается и начинает свое выполнение с секции goal. В появившемся окне можем наблюдать результат работы программы. Выводится yes, т. к. утверждение является верным для описанных в базе фактов:

Следующее утверждение, которое проверим «Алексей является родителем Ольги» — ложно, т. к. в базе нет факта parent(aleksei, olga). Запишем этот запрос в секции goal и убедимся, что результат — no:

В запросе «Кто является ребенком Николая» нужно использовать анонимную переменную (ее имя начинается с большой буквы), т. к. имя ребенка неизвестно. Интерпретатор попробует подобрать все возможные решения, сопоставив эту переменную с каждым значением базы данных. В результате он сообщит нам, что ребенок Николая — Ира:

Несмотря на то, что пролог в предыдущем запросе перебирал все возможные варианты, был получен только один ответ, т. к. у Николая других детей нет. Однако, в запросе «Кто родители Ивана» мы получим несколько решений:

При определении всех родителей и их детей мы используем две анонимных переменных в запросе (т. к. ни конкретные родители, ни дети нам заранее не известны). В результате будет выведено все содержимое нашей базы данных:

Более подробно про работу с базами данных в Prolog.

Выводы по работе в Visual Prolog:

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