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

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

2-е издание, исправленное

Ефимова Е.А.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Основы программирования на языке Visual Prolog/ Е.А. Ефимова - М.: Национальный Открытый
Университет “ИНТУИТ”, 2016

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

(c) ООО “ИНТУИТ.РУ”, 2014-2016
(c) Ефимова Е.А., 2014-2016

3

Определение отношений в программе

Вводятся основные понятия логического программирования и базовые понятия языка
Пролог. Рассматриваются примеры определения отношений в программе на языке
Пролог. Показывается, как использовать интерпретатор PIE для написания программ
на языке Пролог, а также как создавать консольные приложения в системе Visual
Prolog. Описываются основные разделы программы в языке Visual Prolog.

Предисловие

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

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

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

Используется одна из самых развитых реализаций языка Пролог – современная версия
языка Visual Prolog. Система программирования Visual Prolog обладает всеми
средствами для быстрой разработки современных приложений. Она предоставляет
возможность сочетать логическое, функциональное и объектно-ориентированное
программирование.

Язык Visual Prolog имеет простой и ясный синтаксис, близкий к математическому.

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

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

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

4

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

1.1. Понятие логической программы

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

 — термы. Термы без переменных называются основными, или замкнутыми

термами. Отношения описываются с помощью предикатов. Выражения вида 

, где  — имя предиката, а 
 — термы, называются

атомарными формулами. Атомарная формула или ее отрицание называется литералом.

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

,

где 
 — знак конъюнкции, 
 — знак импликации, 
 — атомарная формула, а 

 — литералы. На языке Пролог такое предложение записывается

следующим образом:

.

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

 .

Правило с пустым телом называется фактом. Правило с пустым заголовком — это
цель, запрос или вопрос к программе.

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

Рассмотрим программу

млекопитающее("слон").
млекопитающее("зебра").

животное("страус").
животное("уж").
животное(X):- млекопитающее(X).

5

С помощью фактов определяются безусловные отношения. Отношению
“млекопитающее” принадлежат элементы “слон” и “зебра”. В программе они
представлены константами. Соответственно, область истинности предиката
млекопитающее имеет вид: {слон, зебра}.

Правило выражает импликацию

.

Областью истинности предиката животное является множество {страус, уж, слон,

зебра}.

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

.

В ответе на частный запрос отмечается истинность или ложность цели.

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

.

Ответом на запрос является множество значений переменных, при которых формула
цели является истинной.

Простые вопросы состоят из одной цели, составные — из нескольких, их называют
подцелями. В составных вопросах подцели соединяются знаками конъюнкции “,” или
знаками дизъюнкции “;” (см. упр. 2). В первом случае запрос называется
конъюнктивным, во втором — дизъюнктивным. Значения переменных в подцелях,
разделенных знаками дизъюнкции, не связаны между собой.

Переменные в языке Пролог локальны и имеют математический смысл. Их значение
сохраняется только на протяжении одного правила. Они не объявляются, в любом
предложении их всегда можно переименовать. Переменные пишутся с прописной
буквы или начинаются со знака подчеркивания. Состоят только из знака
подчеркивания или начинаются с него анонимные переменные, которые не принимают
никаких значений. Если в предложении встречается несколько анонимных
переменных, то все они считаются разными переменными, хотя и обозначаться могут
одинаково, например, с помощью только знака подчеркивания “_”.

Во всех словах — ключевых словах, именах переменных, предикатах, доменах и др.,
которые используются в программе, имеет значение регистр только первого символа,
регистр остальных символов не важен.

В языке Visual Prolog комментарий до конца строки начинается со знака %. Между
знаками /* и */ можно заключать комментарии произвольной длины.

6

Всюду ниже обозначение 
 используется для указания арности отношения или

предиката: предикат  имеет арность .

1.2. Декларативная семантика логической программы

В классическом случае все 
 в правиле >
 являются атомарными

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

.

Поэтому логическое программирование в узком смысле называют программированием
на хорновских дизъюнктах.

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

Декларативным значением программы называется ее минимальная модель (которая
единственна, с точностью до изоморфизма). Перейдем к основным определениям.

Подстановкой термов вместо переменных называется множество  пар термов вида 

, где  — переменная, а  — терм, не содержащий переменную . Иногда вместо

равенств используются обозначения 
 или 
.

Если 
 — формула, то выражение 
 обозначает формулу, полученную из формулы

A заменой всех вхождений переменной  на терм  для всех равенств x = t,
имеющихся в подстановке .

Например, если 
, 
, то 
.

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

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

из равенств 
, где  — переменная, не входящая в исходное правило.

Например, правило 
 является вариантом правила 

.

Правило 
, которое не содержит переменных и получается из

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

основным примером исходного правила.

Например, правило 
 является основным

примером правила 
. В этом случае 
.

7

Эрбранов универсум логической программы — это множество 
 термов, построенных

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

Для рассматриваемой программы 
.

Эрбранов базис логической программы — это множество 
 простых замкнутых целей,

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

В нашем примере B = {млекопитающее(слон), млекопитающее(зебра),
млекопитающее(страус), млекопитающее(уж), животное(слон), животное(зебра),

животное(страус), животное(уж)}.

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

Моделью I логической программы называется такая интерпретация этой программы,
что для каждого основного примера 
,правила 

выполняется: если 
, то 
, для всех правил программы.

Например, моделью является сам эрбранов базис.

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

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

 следует, что в любую модель нашей программы

входят цели 
 и 
. Таким образом, минимальная модель

программы имеет вид:

I0 = {млекопитающее(слон), млекопитающее(зебра), животное(страус), 
животное(уж), животное(слон), животное(зебра)}

1.3. Приложение Prolog Inference Engine

Приложение Prolog Inference Engine (PIE) входит в собрание примеров Visual Prolog
Examples, которые поставляются вместе с системой Visual Prolog (ссылка: www.visualprolog.com). Оно представляет собой интерпретатор реализации языка Пролог,
синтаксис которой близок к реализации Эдинбургского Пролога. Для запуска
приложения необходимо открыть проект в среде разработки Visual Prolog. Для этого
нужно запустить файл vip.exe, выбрать команду меню Project > Open, нажать кнопку
Browse… окна Visual Prolog Environment (рис. 1.1) и открыть файл Visual rolog
Examples\pie\pie.vipprj. После этого следует выбрать команду меню Build > Execute (см.
замечание в конце главы). В дальнейшем можно сразу запускать Exe-файл приложения

8

PIE.

Рис. 1.1.  Среда разработки Visual Prolog. Окно Visual Prolog Environment

Информация об открываемых (и вновь созданных) проектах отображается в окне Visual
Prolog Environment. Открывать проекты повторно можно прямо из списка проектов.

В следующей программе определяются предикаты летает/1, животное/1 и птица/1.

летает("синица").            % факты 
летает("лебедь").
летает("аэроплан").

животное("лебедь").
животное("синица").
животное("тигр").

птица("пингвин").
птица("страус").
птица(X):- животное(X), летает(X).      % правило

?- птица(A).              % запрос

Пример 1.1. “Птицы”

9

Упражнение 1.

1. Какие элементы принадлежат отношению “птица”, определенному в программе

“Птицы” (см. листинг 1.1)?

2. Запустите приложение PIE, поместите в него программу “Птицы” и найдите ответ

на запрос к программе. Для этого откройте новый файл, поместите в него текст
программы (факты и правила), сделайте активным окно с программой и выберите
команду меню Engine > Reconsult. В окне Dialog введите запрос птица(A).

Поставьте курсор после знака точки и нажмите клавишу Enter (рис. 1.2). Ответ на
запрос появится в этом же окне.

Рис. 1.2.  Приложение PIE

Для имен переменных в PIE следует использовать буквы латинского алфавита, для
предикатов и констант можно использовать кириллицу. На языке Visual Prolog можно
использовать кириллицу и для имен переменных.

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

родитель("Иван", "Мария").
родитель("Анна", "Мария").
родитель("Мария", "Павел").
родитель("Мария", "Петр").

супруг("Иван", "Анна").
супруг("Павел", "Юлия").

мужчина("Иван").

10