61

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

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

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

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

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

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

Синтаксис логики предикатов

Предложения на естественном языке	Синтаксис логики предикатов
Машина красивая	fun (car)
Роза красная	red (rose)
Билл любит машину, если машина красивая	likes (bill, Car) if fun (Car)

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. Основные стандартные домены

Домен	Описание	Реализация
short	Короткое, знаковое, количественное	Все платформы 16 бит (-32 768--32 767)
ushort	Короткое, беззнаковое, количественное	Все платформы 16 бит (0--65 535)
long	Длинное, знаковое, количественное	Все платформы 32 бит (-2 147 483 648-2 147 483 647)
ulong	Длинное, беззнаковое, количественное	Все платформы 32 бит (0-4 294 967 295)
integer	Знаковое, количественное, имеет платформо-зависимый	Платформы 1 6 бит (-32 768-32 767)
	размер	Платформы 32 бит (-2 147 483 648-2 147 483 647)
unsigned	Беззнаковое, количественное, имеет платформо-зависимый размер	Платформы 16 бит (0--65 535) Платформы 32 бит (0-4 294 967 295)
byte		Все платформы 8 бит (0-- 55)
word		Все платформы 16 бит (0--65 535)
dword		Все платформы 32 бит (0--4 294 967 295)

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

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

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

domains

i8 = signed byte

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

Другие базовые домены показаны в табл. 2 Имеются и другие стандартные домены..

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

Домен	Описание и реализация
char	Символ, реализуемый как беззнаковый byte. Синтаксически это символ, заключенный между двумя одиночными кавычками: 'а'
real	Число с плавающей запятой, реализуемое как 8 байт в соответствии с соглашением IEEE; эквивалентен типу double в С. При необходимости, целые автоматически преобразуются в real
string	Последовательность символов, реализуемых как указатель на байтовый массив, завершаемый нулем, как в С. Для строк допускается два формата:1. Последовательность букв, цифр и символов подчеркивания, причем первый символ должен быть строчной буквой.2. Последовательность символов, заключенных в двойные кавычки. Примеры строк: telephone_number "railway ticket" "Dorid Inc" Строки, которые пишутся в программе, могут достигать длины в 255 символов, в то время как строки, которые система Visual Prolog считывает из файла или строит внутри себя, могут достигать (теоретически) до 4 Гбайт на 32-битных платформах
symbol	Последовательность символов, реализуемых как указатель на вход в таблице идентификаторов, хранящей строки идентификаторов. Синтаксис -- как для строк

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

Задание типов аргументов при декларации предикатов

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

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

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

person(frank, male, 45).

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

person(symbol, symbol, unsigned).

Здесь для всех трех аргументов использованы стандартные домены. Отныне всякий раз при работе с предикатом person, вы должны передавать ему три аргумента, причем первые два должны быть типа symbol, а третий -- типа integer.

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

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

alphabet_position(Letter, Position)

должна вернуть вам Position = 1, если Letter = a, Position = 2, если Letter = Ь и т. д. Предложения этого предиката могут выглядеть следующим образом:

alphabet_position(A_character, N).

Если при объявлении предиката используются только стандартные домены, то программе не нужен раздел domains. Предположим, что вы хотите описать предикат так, что цель будет истинна, если A_character является N-м символом алфавита. Предложения этого предиката будут такими:

alphabet_position('а', 1). alphabet_position('b', 2).

alphabet_position('с', 3).

alphabet_position(' z1, 26).

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

predicates

alphabet_position(char, unsigned)

и тогда вам не будет нужен раздел domains. Если разместить все фрагменты программы вместе, получим:

predicates

alphabet_position(char, integer)

clauses

alphabet_position('a', 1).

alphabet_position('b', 2) .

alphabet_position('c', 3).

% здесь находятся остальные буквы

alphabet_position('z', 26).

Ниже представлено несколько простых целей, которые вы можете использовать:

alphabet_position ('а', 1).

alphabet_position(X, 3).

alphabet_position (' z', What).

Арность (размерность)

Арность предиката -- это количество аргументов, которые он принимает. Вы можете иметь два предиката с одним и тем же именем, но отличающейся арностью. В разделах predicates и clauses версии предикатов с одним именем и разной арностью должны собираться вместе; за исключением этого ограничения, различная арность всегда понимается как полное различие предикатов. Проиллюстрируем это примером/

domains

person = symbol

predicates

father(person)% этот person -- отец

father(person, person)% первый person является отцом другого

clauses

father (Man) :-father(Man, _) .

father(adam,seth).

father(abraham,isaac).

Синтаксис правил

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

HEAD: - <Subgoal>, <Subgoal>, ..., <Subgoal>.

Заголовок: -- <Подцель>, <Подцель>, ... , <Подцель>.

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

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

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

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

если ЗАГОЛОВОК истинен, тогда ТЕЛО истинно (или: тогда выполнить ТЕЛО

Данный тип оператора известен как условный оператор если/тогда (if/then). Пролог же использует другую форму логики в таких правилах. Вывод об истинности заголовка правила Пролога делается, если (после того, как) тело этого правила истинно, например, так:

ЗАГОЛОВОК истинен, если ТЕЛО -- истинно (или: если ТЕЛО может Сыть выполнено).

Учитывая вышесказанное, правило Пролога соответствует условной форме тогда/если (then/if).

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

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

· между строками (string) и идентификаторами (symbol);

· между целыми, действительными и символами (char). При преобразовании символа в числовое значение этим значением является величина символа в коде ASCII.

Аргумент из домена my_dom, который объявлен следующим образом:

domains

my_dom = <base domain> % <base domain> -- это стандартный домен

может свободно смешиваться с аргументами из этого основного домена и с аргументами всех совместимых с ним стандартных доменов. Если основной домен -- string, то с ним совместимы аргументы из домена symbol; если же основной домен integer, то с ним совместимы домены real, char, word и др. Такое преобразование типов означает, например, что вы можете:

· вызвать предикат с аргументами типа string, задавая ему аргументы типа symbol, и наоборот;

· передавать предикату с аргументами типа real параметры типа integer;

· передавать предикату с аргументами типа char параметры типа integer;

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

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

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)

clauses

written_by(fleming, "DR NO").

written_by(melville, "MOBY DICK").

book("MOBY DICK", 250).

book("DR NO", 310).

long_novel (Title) :-

written_by(_, Title),

book(Title, Length),

Length > 300.

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

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

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

written_by (X,Y).

written_by(fleming,"DR NO").

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

X=fleming, Y="DR NO"

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

written_by(melville, "MOBY DICK").

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

X=melville, Y="MOBY DICK"

2 Solutions

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

long_novel(X).

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

long_novel(Title)

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

long_novel(Title) :-

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

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

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

written_by(_, Title),

written_by (fleming, "DR NO").

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

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

length > 300.

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

X="DR NO"

1 Solution.

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

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

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

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

predicates

likes(symbol,symbol)

tastes(symbol, symbol)

food(symbol)

clauses

likes(bill,X):-

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

tastes(pizza,good).

tastes(brussels_sprouts,bad).

food(brussels_sprouts).

food(pizza).

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

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

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

likes(bill, What).

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

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

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

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

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

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

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

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

tastes(brussels_sprouts, good)

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

food(brussels_sprouts).

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

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

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

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

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

What=pizza

1 Solution

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

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

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

Использование предиката fail

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

domains

name = symbol

predicates

father(name, name)

everybody

clauses

father(leonard,katherine).

father (carl, jason).

father (carl,marilyn)

everybody:-

father (X,Y),

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

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

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

goal

father(X,Y).

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

X=leonard, Y=katherine

X=carl, Y=jason

X=carl, Y=marilyn

3 Solutions

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

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

goal

everybody.

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

leonard is katherine' s father

carl is Jason's father

carl is marilyn's father

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

father (X, Y),

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

fail.

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

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

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

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

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

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

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

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

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

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

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

r1 :- а,b,

!,

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. Программа 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 проставляет точку возврата около этого предложения.