Рекурсия. Декларативная и процедурная семантики.

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

 

13) родитель(Х,Y):– отец(Х,Y).	15) предок(Х,Y):– родитель(Х,Y).
14) родитель(Х,Y):– мать(Х,Y).	16) предок(Х,Y):– родитель(Х,Z), предок(Z,Y).

 

Особого внимания заслуживает правило 16. Оно утверждает, что X является предком Y, если он является родителем некоторого Z, а тот, в свою очередь, – предком Y. Это – пример рекурсивного правила, в котором правая часть содержит предикат из левой части (естественно, с другими компонентами). Такие правила широко используются для представления в БЗ отношений, задаваемых рекурсивно. Другой пример рекурсивного правила был приведен выше в фрагменте описания предметной области «Дифференцирование».

Необходимым условием использования для описания отношения рекурсивного правила является наличие в БЗ хотя бы одного нерекурсивного правила для этого отношения. В нашем случае таким нерекурсивным правилом является правило 15. При использовании рекурсивных правил нужно важно соблюдать рекомендации относительно следования предложений в базе знаний и предикатов в правых частях рекурсивных правил. Рекомендации здесь простые, они формулируются на основе принципа «от простого к сложному». Во-первых, для каждого заданного рекурсивно отношения рекомендуется сначала указать нерекурсивные предложения, а затем – рекурсивные. Во-вторых, в правой части каждого рекурсивного правила предикат, образующий рекурсию, должен находиться после нерекурсивных предикатов (исключение – только для некоторых встроенных предикатов, о которых речь пойдет ниже).

Вы можете легко убедиться, что предложения 15 и 16 удовлетворяют этим рекомендациям.

Введем в рассмотрение предложение 16 ¢:

предок(Х, Y):– предок(Z, Y), родитель(Х, Z).

Теперь рассмотрите различные варианты предложений 15, 16 и 16 ¢. В базе знаний нашего примера это предложения 15, 16 и этот вариант можно считать эталонным. Другие варианты: а) 16, 15; б) 15, 16 ¢; в) 16 ¢, 15. Убедитесь, что в них выводы целей, представленных предикатом предок в случае а значительно усложнятся; в случае б будут найдены только если цель не содержит переменных; в случае в не будут найдены ни при каких значениях термов. Причина неудач для вариантов б и в в том, что алгоритм логического вывода будет выполнять бесконечный цикл.

 

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

 

Встроенные предикаты

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

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

 

Арифметика

 

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

Арифметические операции реализуются в Прологе с помощью хорошо известных операторов: +, -, *, /, div, mod. Операнды первых четырех из них могут быть как целыми, так и вещественными, последние два определены только для целых операндов. Арифметические выражения строятся в Прологе по правилам, не отличающимся от общепринятых. Вот примеры выражений, не требующие комментариев: (A+B)*C/2, ((3.1*A-12)/(B-1)+2.5)*2 и т.д. Выражения не являются предикатами. Они должны быть частью оператора присваивания, либо операндами сравнений, которые представлены встроенными предикатами особого типа, синтаксис которых отличается от синтаксиса других предикатов. Важной особенностью этих предикатов является то, что они представлены в инфиксной форме:

<аргумент1> <имя предиката> <аргумент2>

 

Сначала остановимся на операторе присваивания. Это особая конструкция Пролога для рассмотрения которой необходимо ввести понятия конкретизированной и свободной переменных. Конкретизированной называется переменная, которой было присвоено некоторое значение. В большинстве случаев значение переменной присваивается при унификации. Пусть, например, активная цель имеет вид: p (a, Y) и сопоставляется с правилом базы знаний вида: p (X, Y):- q ₁ (X, Z), …, q_n (t ₁, …, t_m). Наиболее общий унификатор таков: {(X, a)} и поэтому после резолюции образуется список целей: q (a, Z), …. Таким образом, применение унификации позволило определить значение всех вхождений переменной X в приведенное правило, и, следовательно, эта переменная оказалась конкретизированной. Важно помнить, что областью действия конкретизации X является правая часть правила, использованного для резолюции, иначе говоря, список целей q ₁ (X, Z),…, q_n (t ₁, …, t_m). В то же время значения переменных Y и Z остались неопределенными. Такие переменные называются свободными.

Синтаксис оператора присваивания таков:

A = <обобщенный терм>, либо <обобщенный терм> = A,

где A – свободная переменная, а <обобщенный терм> – арифметическое выражение или терм. Обратите внимание, что переменная, которой присваивается значение, может быть расположена как слева, так и справа от знака равенства. Если в операторе используется арифметическое выражение, то переменной присваивается его численное значение. В противном случае переменной присваивается значение терма.

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

Предикаты сравнения

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

<аргумент1> <отношение> <аргумент2>.

Здесь аргументы – это сравниваемые термы, а отношение обозначается обычными синтаксическими знаками: <, <=, =, >, >=. Таким образом, предикат сравнения по виду не отличается от отношений процедурных языков. Отметим, что сравнивать необходимо термы одинаковых типов, например, числа с числами, строки со строками и т.д. Предикаты принимают значение «истина», если для аргументов выполнено соответствующее отношение.

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

 

Предикаты ввода-вывода

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

Предикаты, имена которых начинаются строкой букв read, предназначены для ввода данных. Например, readint служит для ввода целых, readreal – вещественных чисел, readln – символьную строку и т.д.Вообще говоря, эти предикаты могут вводить данные из разных источников. Но по умолчанию они вводятся с экрана монитора, для чего в большинстве реализаций предусмотрено специальное окно.Аргументами этих предикатов должны быть свободные переменные, число их неограниченно.

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

Рассмотренные предикаты этой группы являются тождественно истинными.

 

Предикат отсечения

 

Важнейшим из встроенных предикатов является предикат отсечения, который часто называют просто отсечением. Это тождественно истинный предикат, не имеющий аргументов. Изображается он чаще всего восклицательным знаком: «!». Побочный эффект этого предиката позволяет программно управлять перебором. Пусть активная цель представлена предикатом p и он унифицировался с предикатом из правила (аргументы предикатов в данном случае несущественны):

p:- p ₁, …, p_m,!, p_{m +1}, …, p _n.

Таким образом, список целей приобрел вид:

p ₁, …, p_m,!, p_{m +1}, …, p _n, …

Предположим также, что в базе знаний после данного правила имеется еще несколько правил и/или фактов для данного предиката, например:

p:- q ₁₁, …, q_{k .}

…

                                                            p.

…

                                                            p:- q ₂₁, …, q_l и т.д.

Пусть цели p ₁, …, p_m достигнуты, и предикат отсечения оказался активной целью:

                                                           !, p_{m +1}, …, p _n, …

Так как «!» – это тождественно истинный предикат, данная активная цель будет достигнута, а его побочный эффект отключает механизм возвратов для перебора других вариантов вывода целей p ₁, …, p_m, а также выводы первоначальной цели p с помощью правил и фактов, расположенных в базе знаний после правила, содержащего отсечение. В то же время, перебор выводов целей p_{m +1}, …, p _n, … будет выполнен в полном объеме.

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

 

Тождественно ложный предикат

Предикат fail является тождественно ложным предикатом, не имеющим побочного эффекта. Этот предикат применяется в ряде случаев, например, при так называемом «откате после неудачи».

 

Примеры

1) Рассмотрим пример использования функторов при моделировании предметной области «Библиотечные каталоги», содержащей сведения о личных библиотеках. Будем считать, что в базу знаний включены имена владельцев библиотек, и данные о книгах: автор, название, издательство, год выпуска. Последние естественно объединить функтором. Таким образом, база знаний должна состоять из фактов, перечисляющих единицы хранения библиотек и их владельцев. Для ее формирования достаточно использовать единственный предикат collection:

collection("Анисимова",

book("Программирование на языке Пролог",

     "Клоксин У., Меллиш К.",

     "Мир",1987)).

collection("Анисимова",

book("Логика в решении проблем",

     "Ковальски Р.",

     "Наука",1990)).

collection("Анисимова",

book("Язык программирования Пролог",

     "Стобо Дж.",

     "Радио и связь",1993)).

collection("Анисимова",

book("Системы продукций",

     "Яхно Т.М.",

     "АН СССР. Сиб. отделение",1990)).

collection("Братчиков",

book("Синтаксис языков программирования",

     "Братчиков И.Л.",

     "Наука",1975)).           

collection("Братчиков",

book("Введение в МПролог",

     "Иванова Г.С., Тихонов Ю.В.",

     "МГТУ",1990)).

collection("Братчиков",

book("Принципы искусственного интеллекта",

     "Нильсон Н.",

     "Радио и связь",1985)).

collection("Братчиков",

book("Реализация экспертных систем",

     "Клещев А.С.",

     "Препринт ДВО АН СССР",1988)).

collection("Братчиков",

book("Компиляторы",

      "Ахо А., Сети Р., Ульман Дж. ",

      "Вильямс", 2003)).

 

2)«ОБЕЗЬЯНА И БАНАН». Построим базу знаний для моделирования поведения обезьяны в следующей ситуации. Обезьяну впускают в комнату, в которой имеется ящик, стоящий у окна, а посередине комнаты к потолку подвешен банан. Обезьяна хочет достать банан, но для этого ей нужно подойти к ящику, перетащить его на середину комнат и залезть на ящик.

 

База знаний примера:

 

1) ход(состояние (середина, на-ящике, середина, не-имеет), схватить, состояние(середина, на-ящике, середина, имеет).

 

2) ход(состояние (Р, на-полу, Р, Н), залезть, состояние(Р, на-ящике, Р, Н).

 

3) ход(состояние (Р1, на-полу, Р1, Н), подвинуть(Р1,Р2), состояние(Р2, на-полу, Р2, Н).

 

4) ход(состояние (Р1, на-полу, В, Н), перейти (Р1,Р2), состояние(Р2, на-полу, В, Н).

 

5) может_завладеть(состояние(_, _, _, имеет)).

 

6) может_завладеть (С1):--

ход (С1, Ход, С2), может_завладеть (С2).

 

Здесь «состояние» – это функтор, определяющий состояние, в котором находится система. Компоненты функтора: расположение обезьяны в комнате, вертикальное расположение обезьяны (на полу или на ящике), расположение ящика в комнате и указание на то, схватила ли обезьяна банан.

В базе знаний используются два предиката. Предикатом «ход» определяются возможные действия обезьяны. Три аргумента предиката задают состояние системы до действия обезьяны, само действие (тоже функтор, в зависимости от действия либо без компонентов, либо с двумя компонентами) и состояние после действия. Предикат «может_завладеть» имеет один аргумент – состояние системы. Цель, представленная этим предикатом, достигается, если при данном состоянии обезьяна, действуя правильно, может схватить банан.

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

Рассмотрим работу алгоритма поиска логического вывода для приведенной базы знаний и следующего вопроса (для сокращения записи обозначим предикат «может_завладеть» через «м_з»):

 

? м_з (состояние(у-двери, на-полу, у-окна, не-имеет))

 

1) Цель может быть унифицирована с (6).

Унификатор: { (С1, состояние(у-двери,

на-полу, у-окна, не-имеет) }.

 

Теперь имеем следующий список целей:

 

ход(состояние(у-двери, на-полу, у-окна, не-имеет), Ход, С2), м_з(С2).

 

 2) Первая цель может быть унифицирована с (4).

Унификатор: { (Р1, у-двери), (В, у-окна), (Н, не-имеет),

(Ход, перейти(у-двери, Р2)), (С2, состояние

    (Р2, на-полу, у-окна, не-имеет)) }.

Так как первая цель достигнута, остается только вторая цель:

 

м-з(состояние(Р2, на-полу, у-окна, не-имеет)).

 

3) Оставшаяся цель может быть унифицирована с (6).

Унификатор: { (С1, состояние(Р2, на-полу, у-окна, не-имеет)) }.         

 

Теперь имеем следующий список целей:

 

ход(состояние(Р2, на-полу, у-окна, не-имеет), Ход, С2), м-з(С2).

 

4) Первая цель может быть унифицирована с (2).

 Унификатор { (Р2, у-окна), (Р, у-окна), (Н, не-имеет),

(Ход, залезть), (С2, состояние(у-окна,

на-ящике, у-окна, не-имеет)) }.

 

Так как первая цель достигнута, остается только вторая цель:

 

м-з(состояние(у-окна, на-ящике, у-окна, не-имеет)).

 

5) Оставшаяся цель может быть унифицирована с (6).

Унификатор: { (С1, состояние(у-окна, на-ящике, у-окна, не-имеет)) }.

 

Список целей:

 

ход(состояние(у-окна, на-ящике, у-окна, не-имеет), Ход, С2), м-з(С2).

 

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

 

4¢) Первая цель может быть унифицирована с (3).

Унификатор { (Р2, у-окна), (Р1, у-окна), (Н, не-имеет),

(Ход, подвинуть(у-окна, Р2)), (С2, состояние(Р2,

на-полу, Р2, не-имеет)) }.

 

Так как первая цель достигнута, остается только вторая цель:

 

м-з(состояние(Р2, на-полу, Р2, не-имеет)).

 

5¢) Вновь унифицируем с (6).

 Унификатор: { (C1, состояние(Р2, на-полу, Р2, не-имеет)}.

 

Список целей:

 

ход(состояние(Р2, на-полу, Р2, не-имеет), Ход, С2), м-з(С2).

 

6) Первую цель унифицируем с (2).

Унификатор: { (Р2, P), (H, не-имеет), (Ход, залезть),

(С2, состояние(Р, на-ящике, Р, не-имеет)) }.

 

Оставшаяся цель:

 

м-з(состояние(Р, на-ящике, Р, не-имеет)).

 

7) Унифицируем с (6).

Унификатор: { (C1, состояние(Р, на-ящике, Р, не-имеет)) }.

 

ход(состояние(P, на-ящике, Р, не-имеет), Ход, С2), м-з(С2).

 

8) Унифицируем с (1).

Унификатор: { (Р, середина), (Ход, схватить), (C2,

состояние(середина, на ящике, середина, имеет))}.

 

Получили цель:

   

 м-з(состояние(середина, на ящике, середина, имеет)).

 

Эта цель унифицируется с фактом (5). Цель достигнута, список целей оказывается пустым и, таким образом, вывод получен. Система на поставленный вопрос ответит «ДА».

Проанализируем найденный логический вывод. Нетрудно видеть, что нам достаточно просмотреть последовательность «ходов» обезьяны и подстановки вместо переменных предиката «ход», представленных переменными. Ходы определяются на четных шагах вывода:

2) перейти (у-двери, Р2);

4) (Р2, у-окна), залезть - тупик.

4¢) (Р2, у-окна), подвинуть (у-окна, Р2);

6) (Р2, Р), залезть;

8) (Р, середина), схватить.

 

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

1) Обезьяна идет от двери к окну.

2) Обезьяна залезает на ящик, который находится у окна.

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

4) Обезьяна переносит ящик на середину комнаты.

5) Обезьяна залезает на ящик.

6) Обезьяна хватает банан.

3) Вывести на экран монитора целые числа, находящиеся в интервале [ M, N ].

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

beg – 0-местный предикат, предназначенный для ввода пользователем границ интервала и контроля корректности вводимых границ. Использует встроенный предикат readint.

print (M, N) – 2-местный предикат, осуществляющий вычисление целых чисел, находящихся в заданном интервале, и вывод их на экран. Использует встроенный предикат write. Программа решения задачи такова:

 

beg:-

write("Введите нижнюю границу интервала: "),

readint(A),

write("Введите верхнюю границу интервала: "),

readint(B),

A<=B, write ("Числа в интервале [",A,",",B,"]:"),

print(A,B),!.

beg:- write("Неверные начальные данные!"), fail.

print (N,M):- N < M, write(N, ","),

K = N+1, print(K,M).

print(N,_):- write(N, "."), Nl.

 

 

В программе рассматриваются два случая:

a) Границы интервала введены верно (M £ N). В этом случае должны выводиться числа, находящиеся внутри интервала. С помощью ответа “ Yes ” система сообщит, что задание выполнено.

b) Границы интервала введены неверно (M > N). Информация об ошибке должна быть выведена пользователю. С помощью ответа “ No ” система сообщит, что задание не выполнено.

 Первое правило программы для предиката beg осуществляет ввод границ интервала, проверку корректности ввода и вывод и в случае корректности введенных границ вывод на экран последовательности чисел. Если все цели из правой части правила оказались достижимы, оператор отсечения (“! ”) блокирует обработку второго правила для beg.

Второе правило выполняется в случае недостижимости цели A <= B из первого правила. С его помощью пользователю выдается информация об ошибке, а встроенный предикат fail инициирует вывод ответа “ No ”.

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

 

       

Списки

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

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

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

 

  [a, b, c, d] или [[“Л.Н. Толстой”, “Война и мир”], [“Ф.М. Достоевский”, “Преступление и наказание”]] или [] - пустой список.

 

2. Список может представляться в виде структуры, состоящей из «головы» и «хвоста». При этом «голова» - это первый элемент списка, а «хвост» - это список, состоящий из остальных элементов. При этом голову и хвост разделяет вертикальная черта «|»:

 

[ Голова | Хвост].

 

В списках, представленных в п. 1, головы - это, соответственно, а и [“Л.Н. Толстой”, “Война и мир”], а хвосты - это [b, c, d] и [[“Ф.М. Достоевский”, “Преступление и наказание”]]. Список, представленный одним элементом, имеет пустой хвост. У пустого списка нет головы, и поэтому он не может быть представлен в виде головы и хвоста

3. Список может задаваться в виде «соединения»:. (Голова, Хвост). Такой список состоит из Головы, к которой приписан Хвост. Например:

 

. (а, [b,c,d]) 

или                                                        . (a. (b. (c. (d,[]))))

 

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

1) Операция «принадлежности». Это двухместный предикат, принимающий значение «истина», если первый аргумент является одним из элементов списка, представленного вторым аргументом. Этот предикат можно задать в виде следующих факта и правила:

 

belong (Х, [Х | Хвост]).

belong (X, [ Голова |Хвост ]):- belong (Х, Хвост).

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

 

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

 

conc ([ ], С, С).

conc ([ Х | С1], С2, [ Х | С3]):- conc (С1, С2, С3).

 

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

 

? – conc([ a, b, c], [d e], [a, b, c, d, e].

Цель: conc([ a, b, c], [d, e], [a, b, c, d, e].

 

Возможна унификация с головой второго предложения.

Унификатор: { (X, a), (C 1, [ b, c ]), (C 2, [ d, e ]), (C 3, [ b, c, d, e ]) }.

Цель: conc([ b, c], [d, e], [ b, c, d, e]).

 Возможна унификация с головой второго предложения.

 Унификатор: { (X, b), (C 1, [ c ]), (C 2, [ d, e ]), (C 3, [ c, d, e ]) }.

Цель: conc([c], [d, e], [c, d, e]).

Возможна унификация с головой второго предложения.

Унификатор: { (X, c), (C 1, [ ]), (C 2, [ d, e ]), (C 3, [ d, e ]) }.

Цель: conc([ ], [d, e], [d, e])

 

Теперь возможна унификация с первым предложением.

Унификатор: { (C, [ d, e ]) }.

 

После этого список целей оказывается пустым и, таким образом, ответ системы - «Yes».

 

3) Операция добавления элемента в начало списка. Представляется трехместным предикатом, первый аргумент которого - элемент, а второй и третий - списки. Предикат принимает значение «истина», если третий параметр - это список, полученный присоединением ко второму параметру первого параметра в качестве головы. Предикат задается в виде одного факта:

  

attach (Х, С, [ Х | С ]).

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

 

delete (Х, [ X | Хвост], Хвост).       

delete (Х, [ Y | Хвост], [ Y | Хвост1]):- delete (Х, Хвост, Хвост1).

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

Задайте следующие операции: добавление элемента в конец списка, варианты удаления, перечисленные в п. 4.

Основы Турбо-Пролога

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

Турбо-Пролог успешно используется для разработки средств искусственного интеллекта, таких как экспертные системы, системы общения с компьютером на естественном языке и другие, а также для создания игр и головоломок. Формат настоящей книги не позволяет полностью изложить все средства Турбо-Пролога и методы программирования на нем. Мы сможем рассмотреть лишь основные особенности системы и привести некоторые примеры ее использования. Детальному описанию Турбо-Пролога посвящена книга […].  

     

Интерфейс пользователя

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

 

 

Рис. 1

 

Рассмотрим сначала расположение окон. Слева вверху расположено окно редактора, в котором размещается тестируемая или выполняемая программа (без вопроса). Она может быть загружена из файла или составлена с помощью встроенного редактора. В окне сообщений (“Message”) помещается информация о действиях, выполненных системой, например, загрузка базы знаний из файла (как на рис. 1), компиляция, выполнение программы, диагностика ошибок и пр. Диалоговое окно (“Dialog”) используется для помещения вопросов и результатов выполнения программы. Наконец, в окне трассировки (“Trace”) при использовании специальной директивы помещается трассировка, т.е. информация о результатах каждого шага выполнения программы. При необходимости редактирования больших программ окно базы знаний может быть расширено за счет других окон с помощью функциональной клавиши F5 и тогда главное меню примет вид:

 

 

Рис 2

 

Повторное нажатие клавиши F5 вернет меню у первоначальному виду. Аналогично можно расширить и диалоговое окно.

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

 

3.2. Структура программна Турбо-Прологе  

 

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

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

 

Раздел Database – описание динамической базы данных

Будет рассмотрен ниже.

Раздел Predicates – описание предикатов

В этом раздел е должны быть перечислены все предикаты, используемые в базе знаний данной программы за исключением встроенных. Для каждого предиката указывается его имя и в скобках через запятую имена типов констант, представляющих термы предиката (если они имеются). Приведем описание некоторых предикатов, рассмотренных в пп. 2.3 – 2.5:

предок(string, string), diff(formula, symbol, formula), belong(char, list), conc(list, list, list).

В разделе Domains должны быть описаны типы констант formula и list.

 

Раздел Clauses – база знаний

 

/*                                                                        */  /*                     комментарий                       */  /*                                                                       */    Domains   <описание нестандартных типов констант>    Database   <описание динамической базы данных>   Predicates   <описание предикатов>    Clauses   <база знаний>    /*                                                                      */  /*                    комментарий                      */  /*                                                                      */

 

Рис. 3

 

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

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

 

Раздел Domains – описание нестандартных типов констант

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

 

тип констант	Имя	домен	Примеры
Символы	Char	любые символы	′a′, ′A′, ′1′, ′&′, ′\13′
целые числа	Integer	в диапазоне от -32768 до 32767	325, -1450, -1, +56, 32766
вещественные числа	Real	по модулю в диапазоне от 1E-307 до 1E306	3425, -24, 124.31, 12.1E-2, 0.234E10, 14.23E+3
Строки	String	последовательность любых символов в кавычках	²John², ²Андрей Сидоров², ²12.234², ²(a+b)*c²
символические имена	Symbol	Строки либо последовательность букв, цифр и знаков подчеркивания, начинающаяся со строчной буквы	²John², ²12.234², pattern, day_1, pay_check_125
Файлы	File	Имя файла	new.txt, matrix.doc, A.dba

 

Нестандартные типы констант, которые используются в программе, должны быть описаны в разделе “Domains”. Каждый нестандартный тип определяется через стандартные или другие описанные в данной программе нестандартные типы. Пусть, например, нам требуется ввести типы “owner”, и “thing”. В первый из них включим владельцев некоторым имуществом, а во второй – имущество (вещи), принадлежащие владельцам. Если и те и другие представлены в базе знаний строками, то в разделе “Domains” они могут быть описаны так:

Owner = string thing = string-

или

owner = string thing = owner

или

owner, thing = string

 

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