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

Министерство общего и профессионального образования Российской Федерации

 

Магнитогорский государственный технический

 университет им. Г.И. Носова

 

 

Кафедра вычислительной техники и прикладной математики

 

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

 

 

 

 

 

 

 

 

 

Составители:   Кирпичева  Н.Т.

Торчинский В.Е.

Файнштейн С.И.

 

 

Магнитогорск  
2000

ГЛАВА 1. ВВЕДЕНИЕ В ПРОЛОГ

1. Декларативные и процедурные  языки программирования

Процедурные (ИМПЕРАТИВНЫЕ) языки программирования требуют полного описания последовательности шагов (команд), которые нужно предпринять, чтобы решить задачу . К ним относятся СИ, ПАСКАЛЬ, АССЕМБЛЕР.

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

Далее Пролог пытается ДОКАЗАТЬ заданную цель, то есть вывести ее логическим путем из уже имеющихся фактов и правил. Этот логический вывод осуществляют ВСТРОЕННЫЕ УНИФИКАЦИОННЫЕ ПРОЦЕДУРЫ путем перебора имеющихся утверждений и попыток сопоставить их с доказываемой целью. В Прологе отсутствуют явные управляющие структуры типа IF...THEN...ELSE..., нет детального описания последовательности шагов. Все это — дело внутренних процедур. Иногда Пролог считают не языком программирования, а пользовательской оболочкой, позволяющей формулировать запросы к базе данных, записанной в Пролог — программе.

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

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

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

Язык Turbo Prolog фирмы Borland является компромиссом между ПРОЛОГОМ в чистом виде и эффективным компилируемым языком. При грамотном программировании можно добиться большой эффективности выполнения. Особенно хорош Turbo Prolog для создания:

— систем управления динамическими базами данных;

— экспертных систем;

— программ с естественно-языковым интерфейсом.

2. Пролог и логика предикатов. Внешние  цели

Логические взаимосвязи между фактами и объектами в логических языках описываются с помощью обозначений, унаследованных из логики предикатов. Синтаксически все объекты данных и отношения представляют собой ТЕРМЫ.

Пример 1.1

«Мэри любит яблоки»

Два объекта «Мэри» и «яблоки» связаны отношением «любит».

Отношение, связывающее объекты, называется ПРЕДИКАТОМ.

Предикат «любит» связывает объекты «Мэри» и «яблоки»:

любит (Мэри, яблоки). % Факт

и «любит», и «яблоки», и «любит (Мэри, яблоки)» — все это термы.

«Бет любит то же самое, что и Мэри»

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

«Бет любит это, если Мэри любит это.»

Условная часть: «если Мэри любит это».

Следствие: «Бет любит это».

Если условие истинно, то истинно и следствие.

любит (Бет, это):- % Правило

     любит (Мэри, это).

Простые объекты могут быть двух типов:

— конкретные объекты или КОНСТАНТЫ (Мэри,Бет,-1,0.21);

— ПЕРЕМЕННЫЕ (это).

По правилам Пролога константы пишутся со строчной буквы, переменные — с прописной (мери, бет, X,Y).

Все известные нам соотношения можно переписать так:

likes(mary,apples).

likes(beth,X):-

      likes(mary,X).

Это практически готовая Пролог — программа.

Можно подвести итог:

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

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

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

Условная часть правила называется ТЕЛОМ, следствие (или часть вывода) — ГОЛОВОЙ правила. Если тело правила состоит из нескольких условий, они могут быть связаны конъюнкцией (логическим «И»), обозначающейся запятой «,»:

любит (джон, X):-

 любит (мэри,X), % конъюнкция двух условий

любит (энн, X).

или дизъюнкцией (логическое «ИЛИ»), обозначающейся точкой с запятой «;».

Кроме того, от предикатов разрешатся брать отрицание:

Not (likes (mary, oranges)). % Мэри не любит апельсины.

ЗАПРОС или ЦЕЛЬ также является утверждением Пролог — программы.

Если ФАКТ — ПРАВИЛО С ПУСТЫМ ТЕЛОМ, ТО ЦЕЛЬ (ЗАПРОС или формулировка задачи, которую нужно решить) — ПРАВИЛО, ИМЕЮЩЕЕ ТОЛЬКО ТЕЛО.

Турбо-Пролог использует как внутренние цели, которые содержатся в программе, так и внешние. Если внутри программы не содержится цель, то система после запуска программы выдает приглашение Goal:, и пользователь вводит цель с клавиатуры. После удовлетворения внешней цели выполнение программы не завершается. Система просит ввести следующую внешнюю цель. Прекратить запросы можно, нажав при выдаче очередного приглашения ESC.

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

Это означает, что, в ответ на внешний запрос система находит все возможные наборы значений для переменных, содержащихся в запросе.

3. Управление программой. Подцели. Механизм  сопоставления

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

Если цель является фактом:

Goal: likes (mary, kiwi)

FALSE

Goal: likes (beth, apples)

TRUE

то ответ будет TRUE или FALSE.

Если цель содержит переменные, то Пролог выдаст или значения переменных, при которых цель истинна, или сообщение

No solutions (Нет решений)

Goal: likes (beth, X)

X= apples

Goal: likes(X, kiwi)

No solutions

Рассмотрим, как Пролог будет пытаться доказать цель «любит (бет, яблоки)» (рис 1.1).

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

Переменная X стала СВЯЗАННОЙ или ОЗНАЧЕННОЙ.

Успешно сопоставив цель и голову правила «любит (бет, X)» с присвоением X значения «яблоки», Пролог переходит к доказательству тела правила, (голова правила будет истинна, если истинно тело). Для доказательства тела правила Пролог сам генерирует ПОДЦЕЛЬ «любит (мэри, яблоки)» и пытается ее доказать.

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

рис 1.1

Сопоставление — это процесс, проверяющий идентичность двух термов.

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

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

Два предиката сопоставимы, если:

• имеют одинаковый предикатный терм (главный функтор),
• одинаковую арность (число аргументов),
• все их соответствующие компоненты сопоставимы.

Значения переменных определяются при сопоставлении компонент.

4. ВНУТРЕННИЕ ПОДПРОГРАММЫ УНИФИКАЦИИ

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

Пусть наша программа пополнилась еще двумя фактами (программа 1.1):

любит (мэри, яблоки).

любит (мэри, апельсины).

любит (мэри, попкорн).

любит (бет, X):-

      любит (мэри, X).

Goal: любит (мэри, X).

X — свободная (неозначенная) переменная, она не имеет значения. Она не равна 0, не равна пробелу, не равна ничему. Цель сопоставляется с первым фактом, X получает значение «яблоки». Цель доказана, Пролог выдает сообщение, что X=яблоки.

Затем X снова становится свободной переменной. Так как цель была внешней, то есть была задана после запуска программы, система будет искать все возможные решения. Поэтому цель сопоставится со вторым утверждением и X получит значение «апельсины» и будет напечатано второе решение. X снова станет свободной, цель сопоставится с третьим утверждением, будет найдено решение X=попкорн. Последнее утверждение и цель несопоставимы, поиск решений окончен.

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

Область известности (лексический диапазон) переменных — одно утверждение.

Поэтому одно и то же имя в двух разных предложениях обозначает две разных переменных.

Значение сохраняется переменной ровно до тех пор, пока:

— либо очередное сопоставление оказывается неуспешным, и вся цель несопоставимой;

— либо цель успешо вычислена.

/* Программа 1.1 «Любители морковки». Назначение:

демонстрация использованием внешней цели    */

domains  %  описание типов объектов

   %  symbol — символическое имя

   name, fruit = symbol

predicates

   likes(name, fruit)  % описание предикатов

clauses 

   likes(mary,apples).          

   likes(mary,oranges).

   likes(mary,popcorn).

   likes(ann,apples).  

   likes(beth,X):-              

      likes(mary,X).

   likes(jonh,X):-              

      likes(mary,X),

      likes(ann,X).     

/*        Конец программы                  */    

Пример 1.2.

Генеалогическое древо имеет следующий вид (рис. 1.2)

рис.1.2

Опишем дерево с помощью отношений «родитель», «мужчина», «женщина».

родитель (том, боб). % Том — родитель Боба

мужчина (том).

женщина (пат).

Определим с помощью правил отношения «сестра», «отпрыск», «мать» (рис 1.3).

рис. 1.3

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

По генеалогическому дереву (рис. 1.2) составить программу, включив в нее отношения «сестра», «отпрыск», «мать» (рис. 1.3).

Обратите внимание, как система отвечает на запрос

 Goal: sister(X, Y). Отчего так происходит?

Опишем отношение предок(X,Z) (рис. 1.4).

рис 1.4

Для всех X и Z ,

X — предок Z, если

X — родитель Z.

Для всех X и Z ,

X — предок Z, если

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

 существует Y , такой, что

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

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

Составим процедуру — множество утверждений об одном и том же отношении.

ancestor(X, Z):-

   pearent(X, Z) .

ancestor(X, Z):-

   pearent(X, Y),

   ancestor(Y, Z).

Ключевым моментом в данной формулировке было использование отношения «предок» в его определении. Такое определение называется рекурсивным.

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

В программу из упражнения 1.1 включите отношение ancestor. Задайте системе вопрос

Goal: ancestor(tom, pat)

и изобразите на диаграмме, какие шаги сделает система для достижения этой цели.

ГЛАВА 2. ВНУТРЕННИЕ ЦЕЛИ. МЕХАНИЗМ ВОЗВРАТА

1. СТРУКТУРА ПРОЛОГ-ПРОГРАММЫ

Любая программа, написанная на Турбо-Прологе, состоит из пяти разделов. Таковыми являются раздел описания доменов, раздел базы данных, раздел описания предикатов, раздел описания цели и раздел описания утверждений. Ключевые слова constants, domains, database, predicates, goal и clauses отмечают начала соответствующих разделов.

Назначение этих разделов таково:

— Раздел constants содержит описание констант.

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

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

— Раздел predicates служит для описания используемых программой предикатов.

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

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

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

/*          комментарии                      */

constants

     < описание констант >

domains

     < описание доменов  >

database

< описание  предикатов динамической базы  данных >

predicates

  < описание предикатов >

goal

  < целевое утверждение >

clauses

  < утверждения  >

2. ИСПОЛЬЗОВАНИЕ ВНУТРЕННИХ ЦЕЛЕЙ

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

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

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

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