Программирования в логике (стр. 7 )

Конкретный экземпляр элементарного класса называется атомом. Это - числовые, символьные и строчные константы.

Термы

Все типы данных в Прологе называются термами. Имя терма называется доменом.

Терм может быть простым. Простой терм - это любой класс объектов, определяемый прямо (object=integer) или косвенно доменом стандартного типа:

object2=object;object2=object*

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

любить(миша, шоколад).

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

Любая структура определяет некоторое отношение между составляющими ее термами (объектами). В таком случае функтор – это имя отношения. Например, терм (факт)

мяч(форма(сфера),материал(резина),размер(25), цвет([синий, красный]))

определяет конкретный объект класса «мяч». Функтор «мяч» есть имя одноместного отношения «быть объектом».

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

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

Простые домены следует рассматривать как характеристики объектов, выраженные (в конечном итоге) в терминах встроенных типов.

Сложные домены определяют иерархию по вхождению менее сложных объектов в более сложные.

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

Задавая системы типов, мы подготовливаем поле для задания аксиом, которые в Прологе выражаются либо фактами внутренней БД или безусловно верными предикатами (которые также называются фактами, пример: черный(X):-темный(X).

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

Пролог-программа

Пролог-программу следует рассматривать как доказательство теоремы, сформулированной в разделе GOAL. Доказательство использует аксиомы, сформулированные как факты Пролога, а также вспомогательные теоремы, сформулированые в виде предложений.

Часто используемый термин цель - это и есть теорема или целевое утверждение. Предложения и отдельные его утверждения рассматриваются как подцели.

Вопрос - это та же теорема или цель. Использование этого термина связано со взглядом на пролог-программу как систему управления Базой Знаний, сами знания в которой представлены фактами.

В случае «Кто у нас большой и темный?» вторая интерпретация конъюнкции большой(X),темный(X) - это теорема о существовании большого и темного объекта X.

Для формулирования целей и подцелей используются переменные.

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

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

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

Утверждение - одно или несколько отношений, связанных конъюнктивно (отношения, перечисляемые через запятую).

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

Правило - утверждение, истинность которого зависит от выполнения ряда условий.

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

Правила состоят из двух частей - головы правила и тела правила - соединенных логической связкой «если»: (if|:-)." И синтаксически и семантически левая часть правила – это отношение, что то же самое, что и утверждение. Т. е. правило в целом читается как «отношение имеет место быть, если верны утверждения в правой части» или «утверждение в левой части верно, если верны утверждения в правой части правила.»

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

В этом смысле раздел clauses содержит определения предикатов.

Предикаты должны быть объявлены в разделе predicates.

Предикат может содержать одно или несколько утверждений:

женщина(умная).

женщина(красивая).

женщина(нежная).

женщина(страстная).

женщина(сварливая).

.................

Предикату могут соотвествовать несколько правил. В таком случае говорят о «множественном определении предиката»

Число объектов определяет арность предиката. Предикат женщина имеет арность, равную 1.

Пример предиката нулевой арности:

люблю_женщину:-

женщина(умная),

женщина(красивая),

женщина(нежная),

женщина(страстная).

5.2. Внутренние дела Пролога

Работу пролог-программы можно сравнить с поиском пути на разветвленной дороге (коей является последовательность и семантика утверждений), когда известны все или часть характеристик искомого объекта, но не неизвестно, где следует свернуть. Если у нескольких объектов совпадают характеристики, то будет найден первый объект на этой дороге. Пролог ищет «первую истину».

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

Как Пролог убеждается, что цель достигнута?

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

Подстановкой или конкретизацией Θ называется всякое множество присваиваний вида x=t, где x - переменная, а t - терм. Каждой переменной присваевается только одно значение.

Результат подстановки иногда называют подстановочным примером. Если применение подстановки Θ к утверждениям (выражениям) E1,E2 дает один и тот же подстановочный пример, такая подстановка называется унификатором, сам подстановочный процесс - унификацией, а утверждения (предикаты) - унифицируемыми.

5.3. Что такое шаблоны?

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

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

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

5.4. Управление поиском

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

1. Операторы сравнения и альтернатива (или: or|;).

2. Множественность правил для одного предиката.

3. Встроенные предикаты fail, (cut | !), котороые порождают искусственный откат и отсечение возможных переборов соотвественно.

4. Рекурсия или самовызов предиката.

5. Комбинация отсечения и искусственного отката.

6. Использование предиката типа repeat. repeat:-repeat

Пример

predicates

search2

search

search3

f1(integer, string)

f2(integer, string)

goal

% Если search3 успешен, то write и выполнить search,

% search2, иначе выполнить search, search2.

% используется метод ОО - отсечение и откат.

search3,!,write("Два первых факта удовлетворяют условию"),fail;

search,

search2;

!.

clauses

f1(1,"String1").

f1(2,"String2").

f1(3,"String3").

f1(4,"String4").

f2(1,"String1").

f2(0,"String2").

f2(-5,"String3").

f2(4,"String4").

% Найти первую комбинацию различных фактов, удовлетворяющих

% условию.

% Используется «естественный откат – бэктрегинг» для поиска

% единственного успешного решения.

search:-

f1(X1,S1),

f2(X2,S2),

X2<X1,write(X1," ",S1," ",X2," ",S2),nl.

% Найти все комбинации разных фактов, удовлетворяющих условию

% Используется ОПН - откат после неудачи.

search2:-

f1(X1,S1),

f2(X2,S2),

X2<X1,write(X1," ",S1," ",X2," ",S2),nl,

fail.

search2:-!.

% Удовлетворяют ли условию 1-ые 2 разных факта

% Здесь важно, в каком месте использован откат. Если он был бы

% поставлен после сравнения, то было бы найдено единственное

% решение, как в предикате search.

search3:-

f1(X1,S1),

f2(X2,S2),!,

X2<X1,write(X1," ",S1," ",X2," ",S2),nl.

Литература

1. Программирование на языке Пролог для искусственного интеллекта/Пер. с англ. - М.: Мир, 1990.

2. Искусство программирования на языке Пролог. /Пер. с англ. - М.: Мир, 1990.

3. Дж. Мартин. Надежность программного обеспечения. /Пер. с англ. - М.:Мир. - 1986.

4. Построение экспертных систем.- М.: Мир, 1987.

5. Игорь Швыркин. Пролог. Генезис.\\ Мир ПК, №5,2000

6. Ин Ц., Использование Турбо-Пролога /Пер. с англ. - М.: Мир, 1993.

7. Логическое программирование и Visual Prolog. - Санкт-Петербург: БХВ-Петербург, 2003.

[1] Излагается по [2,7]