Методическое пособие по логическому программированию

Название “Пролог” есть сокращение для "ПРОграммирование в терминах ЛОГики". Пролог может быть использован в различных приложениях, относящихся к искусственному интеллекту:

– общение с ЭВМ на естественном языке;

– символьные вычисления;

– написание компиляторов;

– базы данных;

– экспертные системы и т.д.

Диалект Пролога язык PDC Prolog является компиляторно-ориентированным языком программирования высокого уровня, разработан фирмой и предназначен для программирования задач из области искусственного интеллекта.

Следует отметить некоторую трудность усвоения языка начинающими пользователями. Пролог относится к так называемым декларативным языкам, требующим от автора умения составить формальное описание ситуации. Как следствие, в языке отсутствуют управляющие конструкции типа if … then, while … do; нет даже оператора присваивания. Программа, составленная на этом языке, не содержит детального описания последовательности шагов, ведущих к результату. Однако методические трудности, связанные с обучением использованию Пролога начинающих программистов, можно успешно преодолеть на основе принципа – "делай как мы".

1. Организация вычислительного процесса

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

А:– В1, В2, ... , Вn,

которая интерпретируется : "А является истинным, если В1, В2, ...., Вn являются истинными". Если n=0, то такое предложение выражает факт, и это записывается "А." .

Если получен запрос (т.е. цель, которую нужно удовлетворить), Пролог пытается определить его истинность двумя способами. Во-первых, цель успешно удовлетворяется (т.е. считается истинной), если она сопоставляется с существующим фактом (так как факты всегда являются истинными). Во-вторых, цель считается истинной, если она сопоставляется с заголовком “А” правила " А, если В1, ... , Вn " и если подцели В1, ... , Вn могут быть завершены успешно. В случае успешного сопоставления Пролог выдает ответ "yes", т.е. цель согласована.

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

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

В Прологе нет оператора присваивания, а есть логическое сравнение, обозначаемое знаком равенства, поэтому понятно, что запись вида N = N+ 1 бессмысленна: величина никогда не равна самой себе, увеличенной на единицу, надо использовать другую переменную: N1 = N + 1.

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

В синтаксисе Пролога факт имеет следующий вид:

relation(object, object,.....object).

Правила имеют основную форму:

relation(object, object,.....object) :–

relation1(object, object,.....object) ,

...

relationN(object, object,.....object).

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

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

p :– q,s.

p :– r,t.

Эту программу можно прочитать следующим образом. При выполнении процедуры p выполняются процедуры q и s. Если они завершаются успешно, то и процедура p считается успешно завершенной. Если это не так, то выполняются процедуры r и t. В этом случае процедура успешно завершается, если r и t завершены успешно. В противном случае процедура p терпит неудачу. Этот процесс возврата к поиску других решений называется бэктрекингом (backtracking).

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

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

2. Основные элементы языка

2.1. Имена

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

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

При образовании имен необходимо учитывать следующие правила:

- имена строковых констант должны начинаться с маленькой буквы;

- имена переменных должны начинаться с большой буквы или символа подчеркивания "_".

2.2. Типы данных

Имеется следующие стандартные типы данных:

symbol	Символьная строка, которая начинается со строчной буквы или заключена в кавычки
string	Также символьная строка, но имеющая другое внутреннее представление
char	Отдельный символ, заключенный в апострофы
integer	Целое число в диапазоне от -32768 до 32767
real	Любое вещественное число

2.3. Константы и переменные

Константы Пролога должны быть записаны:

а) либо с маленькой буквы (исключая кириллицу):

fact1, summa, person ;

б) либо стоять в одинарных кавычках (отдельный символ) или бинарных кавычках (строковая константа):

'c' , "summa=", "сумма" ;

в) либо они являются числами, целыми или вещественными:

25, 0.5, 3.2e-4 .

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

Переменные – это цепочки, состоящие из букв, цифр и символа подчеркивания. Имя переменной всегда начинается с прописной буквы или с символа подчеркивания:

X, Summa, List_of_members, _x23.

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

2.4. Программные секции Пролога

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

Domains	Определение типов данных
Database	Объявление предикатов базы данных
Predicates	Объявление предикатов
Clauses	Определение фактов или правил
Goal	Цель

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

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

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

Комментарии к программе записываются либо парами символов слэш-звездочка:

/* это комментарий,

он занимает несколько строк */

либо остаток строки записывается после знака процента:

% это тоже комментарий

2.4.1. Секция Domains

Для объявления секции domains используются следующие форматы:

1. Первый формат:

name = t ,

где name – имя Пролога, t – один из стандартных типов. Это объявление используется для объектов, которые синтаксически схожи, а семантически различны. Например, предложение

age, number = integer

объявляет два domains целого типа.

2. Второй формат:

mylist = elevent* ,

где mylist – объявление списка элементов, element – элемент, ранее описанный пользователем в Domains либо один из стандартных типов Турбо-Пролога, “*” обозначает список. Hапример,

namlist = integer*

объявляет список целых чисел.

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

region = functor1(d1,d2,...); functor2(d3,d4,...);...

где region объявляет сложную область, functor1,functor2 – имена альтернатив составной области, d1,d1,...,d3,d4 – один из типов Пролога, стандартный или определенный ранее в программе в Domains (описание типов может отсутствовать).

Пример:

object = int(integer); str(string)

mesto = sprava; sleva .

Данный способ указания Domains позволяет также рекурсивно описывать объекты сложных типов (деревьев).

2.4.2. Секция Ppredicates

Здесь указываются все имена предикатов с соответствующими областями определения аргументов. Аргументы дизъюнктов Пролога называются термами. Существует три типа термов: константа, переменная, составной терм (структура).

Общий вид описания предиката:

name(d1,d2,...) ,

где name – имя предиката, d1, d2,... – соответственно области определения аргумента1, аргумента2 и т.д. Например:

syn(string)

math(preson,person) .

2.4.3. Секция Database

Объявление оперативной базы данных. Синтаксис объявления такой же, как и в секции Predicates. Объявленные здесь предикаты не должны объявляться в секции Predicates, но дизъюнкты этих предикатов могут присутствовать в секции Clauses.

2.4.4. Секция Clauses

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

functor(d1,d2,...) :– cond1, cond2,... .

Здесь functor – имя предиката;

functor(d1,d2,...) – голова дизъюнкта;

cond1,cond2,... – условия истинности дизъюнкта;

":–" -обозначение "ЕСЛИ".

Если опущены условия, то functor(d1,d2,...) описывает факт. Каждый из дизъюнктов одного предиката секции Clauses соответствует альтернативам этого предиката.

2.4.5. Секция Goal

Здесь указывается вопрос (цель), на который должен ответить Пролог. Записывается он как дизъюнкт без головы и знака ":–" .

3. Примеры программ

3.1. Программы с фактами и простыми правилами

1. Некоторое множество фактов и правил, задающих объекты и отношения между ними, и образуют простую программу на Прологе. Следующие факты

likes(ellen,tennis).

likes(john,football).

likes(tom,baseball).

likes(eric,swimming).

likes(mark,tennis).

соответствуют утверждениям на английском языке:

Ellen likes tennis.

John likes football.

Tom likes baseball.

Eric likes awimming.

Mark likes tennis.

Подобным образом вопрос: "Что любит Джон?" сводится к поиску объекта, который отношение likes (нравится) связывает с Джоном; этот объект и будет служить ответом на запрос. Отметим, что при определении отношения между объектами существенен порядок, в котором эти объекты входят в отношение:

likes(john,football) отличается от likes(football,john).

Запишем эти факты в виде Пролог-программы.

Predicates

likes(string,string)

Clauses

likes(ellen,tennis).

likes(john,football).

likes(tom,baseball).

likes(eric,swimming).

likes(mark,tennis).

После исправления ошибок в программе выберите опцию RUN в меню Пролога. В этой программе цель не указана (отсутствует секция goal, которая, вообще говоря, не обязательна), поэтому когда система в отдельном диалоговом окне запросит цель, введите запрос:

Goal: likes(john,football).

Пролог ответит

Yes

Поскольку такой факт имеется.

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

car(volvo, 1990, red, 1800).

car(toyota, 1988, black, 2000).

car(ford, 1994, white, 3000).

Наберите эту программу согласно правилам оформления Пролог-программы и исполните команду RUN. Когда система запросит цель, введите запрос:

Goal: car(toyota,_,_,_).

Пролог ответит

1 solution

Yes

в диалоговом окне и будет ждать, когда вы введете другую цель.

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

Если зададите в качестве цели

Goal: car(mersedes,1990,_,_) ,

система ответит

No solution ,

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

Теперь предположим, что мы хотим узнать все марки машин, имеющиеся в базе данных, т.е. задать вопрос: "Каковы те объекты Х, которые являются марками машины?". Тогда наш вопрос запишется так:

Goal: car(Х,_,_,_).

Пролог ответит:

Х=“volvo”

Х="toyota"

Х="ford"

3 solutions.

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

Goal car(X,Y,_,_), Y<1992.

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

year(volvo, 1990).

year(toyota, 1988).

year(ford, 1994).

color(volvo, red).

color(toyota, black).

color(ford, white).

cost(volvo, 2000).

cost(toyota, 2500).

cosr(ford, 3000).

В случае необходимости атрибуты можно собрать в единое целое при помощи правила:

car(M,Y,C,P) :– year(M,Y), color(M,C), cost(M,P).

3. Использование бэктрекинга (возврата) для получения всех решений. В данном примере предикат-факт counry содержит сведения о названии страны и населении. Программа выдает список стран, население которых превышает 1е7.

Predicates

country(symbol,real)

print_countries

Clauses

country(england,3e7).

country(france,2.3e7).

country(germany,1.6e7).

country(denmark,2.4e6).

country(canada,7.3e6).

country(chile,2.5e).

print_countries :-

country(X,P), % рассматривается очередной факт

P > 1e7,

write(X), % вывод на экран названия страны

nl, % перевод строки

fail. % fail – встроенный предикат, означает «ложь»

print_countries.

Goal print_countries.

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

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

predicates

solve(real, real, real) % Запуск программы

reply(real, real, real) % Ветви вычислений

mysqrt(real, real, real) % Вычисление квадратного корня

equal(real, real) % Проверка на равенство

clauses

solve(A, B, C) :– D = B*B-4*A*C, % вычисление дискриминанта

reply(A, B, D), nl.

reply(_, _, D) :– D < 0, write("No solution"), !.

reply(A, B, D) :– D = 0, X=-B/(2*A), write("x=", X), !.

reply(A, B, D) :–

sqrt(D, D, SqrtD),

X1 = (-B + SqrtD)/(2*A),

X2 = (-B – SqrtD)/(2*A),

write("x1 = ", X1," and x2 = ", X2).

Goal solve(3,4,5).

5. Логический вывод. Имеется следующая задача из психологического практикума.

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

Predicates

cat(string)

dog(string)

color(string,string)

have(string,string)

rod(string)

animal(string)

clauses

cat(butsi). cat(korni). cat(mac).

dog(rover). dog(fles). dog(spot).

color(butsi,brown).

color(korni,black).

color(mac,yellow).

color(rover,yellow).

color(spot,white).

color(fles,black_and_white).

have(tom,X):–color(X,black); color(X,brown).

have(keit,X):–dog(X), not(color(X,white)), not(have(tom,X)).

have(alan,mac):–not(have(keit,butsi)), not(rod(spot)).

rod(X):–animal(X), have(tom,X).

rod(X):–animal(X), have(keit,X).

animal(X):–cat(X); dog(X).

goal animal(X),not(have(_,X)),write(X).

3.2. Рекурсии

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

6. Примером рекурсивных вычислений является известный алгоритм вычисления факториала. Hа Прологе эта программа может иметь такой вид:

Domains

N, F=real

Predicates

factorial(N,F)

Clauses

factorial(1,1). % база рекурсии, ограничение вычислений

factorial(N,R):– N>0, N1=N-1,

factorial(N1,R1), R=R1*N.

Goal

factorial(8,F),write(F).

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

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

3.3. Программирование циклов

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

7. Рекурсивный цикл со счетчиком. Цикл выполнится 10 раз.

for(10).

for(N):– N<10,

prosess,

N1=N+1,

for(N1).

Goal for(0).

8. Бесконечный рекурсивный цикл. Выполняется ввод и печать символов. Процесс повторяется до нажатия клавиши ENTER, имеющей кодовое число 13.

typewr('\13').

typewr(Char):–write(Char),

readchar(C),

typewr(C).

Goal readchar(Char), typewr(Char).

9. Использование бэктрекинга для перебора всех вариантов. Пусть есть фрагмент программы

fact(f1).

fact(f2).

fact(f3).

print_fact:– fact(X), write(X), fail.

print_fact.

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

10. Большую группу примеров циклов можно продемонстрировать с использованием предиката repeat. Этот предикат программируется следующим образом:

repeat.

repeat:–repeat.

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

Пример цикла с сочетанием repeat и fail.

run:– repeat,

readln(X),

prosess(X,Y),

write(Y),

fail.

Предикат fail заставляет систему осуществлять возврат к repeat и prosess в случае успешного завершения.

Можно также использовать сочетание repeat и стандартного предиката keypressed (вместо repeat – fail) или сочетание not(keypressed) и рекурсии:

run:– repeat, prosess,

keypråssed.

run:– not(keypressed),

prosess, run.

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

run:– repeat,

prosess,

write("Будет еще ввод? (y/n)" ),

readchar(Ans), Ans = 'n'.

3.4. Работа со списками

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

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

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

– список является либо пустым,

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

Для обозначения списка используются квадратные скобки, а для отделения головы списка от его хвоста – символ "|". Например, для списка [1|2,3] элемент 1 является головой, а список [2, 3] хвостом. Пустой список обозначается [ ]. Если список не разделяется на голову и хвост, квадратные скобки можно опустить.

Рассмотрим некоторые предикаты для обработки списков.

11. Добавление элемента в список. Этот предикат должен иметь три аргумента: добавляемый элемент, список и результирующий список. Наиболее простой способ добавить элемент в список – это вставить его в самое начало так, чтобы он стал новой головой. Если X – это новый элемент, который добавляют в список L, то предикат добавления элемента в список можно записать таким образом:

add(X,L, [X|L]).

12. Удаление элемента. Удаление элемента X из списка L можно определить в виде отношения

away(X,L,L1),

где L1 – это список L, из которого удален элемент X.

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

away(X, [X|T],T).

away(X, [Y|T], [Y|T1]):– away(X,T,T1).

13. Проверка принадлежности элемента списку. Требуется определить предикат:

member(X,L).

Здесь L – некоторый список, Х – объект того же типа, что и элементы списка L. Составление предиката может быть основано на следующих соображениях: X есть либо голова списка L, либо X принадлежит хвосту. Это может быть записано в виде двух предложений, первое из которых есть простой факт, ограничивающий вычисления, а второй – рекурсивное правило:

member(X, [X| _ ]).

member(X, [ _ | T ]):– member(X,T).

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

Если окажется пустой список, тогда предикат завершается ложно, так как для пустого списка нет своего правила.

14. Сцепление (конкатенация) списков.

conc(L1,L2,L3).

Объединяемые списки задаются первыми двумя аргументами L1 и L2. Список L3 представляет собой конкатенацию этих списков.

Для определения отношения конкатенация отделим два случая:

(1) Если первый список пуст, то второй и третий представляют собой один и тот же список:

ñonc([ ],L,L).

(2) Если первый аргумент не пуст, то он имеет голову и хвост, т.е. [X|L1]. Его сцепление со списком L2 – список [X|L3], где список L3 получен после сцепления списков L1 и L2, т.е.

conc([X|L1],L2,[X|L3]):–conc(L1,L2,L3).

15. Удаление из списка повторяющихся элементов. Аргументами предиката unik являются два списка: исходный и результирующий. Смысл алгоритма прост: если элемент присутствует в списке (проверяется предикатом member), то он не записывается в результирующий список, иначе добавляется в качестве головного элемента.

unik([ ],[ ]).

unik([H|T], L):– member(H,T), unik(T,L).

unik([H|T], [H|L]):– unik(T,L).

16. Обращение списка. Определим предикат

reverse(L1,L2).

Аргументы L1 и L2 – два списка, из которых список L2 содержит элементы списка L1, записанные в обратном порядке.

reverse(L1,L2):–reverse1(L1,[],L2).

reverse1([],L,L).

reverse1([H|T],L1,L2):–reverse1(T,[H|L1],L2).

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

17. Вычисление суммы элементов списка. Можно выполнить предикатом

sum(L,S).

Здесь S – сумма элементов списка L. Запрограммировать этот предикат можно двумя способами. Рассмотрим сначала более очевидный:

sum([ ],0).

sum([H|T], S1):– sum(T,S2),S1=S2+H.

Декларативный смысл этого алгоритма: если список пуст, то сумма его элементов равна нулю, иначе список можно разделить на голову H и хвост T; сумма элементов такого списка S1, при этом сумма элементов хвоста T есть S2 и S1=S2+H. Обратим внимание, что это рекурсия нехвостовая: в рекурсивном правиле предиката sum рекурсивное условие записано не последним. Нехвостовая рекурсия при последовательных вызовах генерирует промежуточные переменные, которые конкретизируются при обратном прохождении рекурсии.

Рассмотрим работу этого предиката на примере. Пусть требуется найти сумму элементов списка [3,6,1]. Последовательность вызовов следующая:

sum([3|6,1],S) вызывает предикат sum([6,1],S1) и S=S1+3

sum([6|1],S1) вызывает предикат sum([1],S11) и S1=S11+6.

sum([1],S11) вызывает предикат sum([],S111) и S11=S111+1.

sum([ ],S111) удовлетворяется, если S111 конкретизируется 0.

sum([1],S11) удовлетворяется, если S11 конкретизируется 1.

sum([6,1],S1) удовлетворяется, если S1 конкретизируется 7.

sum([3,6,1],S) удовлетворяется, если S конкретизируется 10.

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

sum(L,S):–sum1(L,0,S).

sum1([ ],S,S). % базовое правило, список пуст, сумма накоплена

sum1([H|T],S1,S):–

S2=S1+H,

sum1(T,S2,S).

Здесь используем тот же прием, что и в предикате обращения списка: используем более общий предикат sum1, имеющий дополнительный аргумент S, в котором зафиксируется результат. Декларативный смысл базового правила: если список исчерпан, то сумма накоплена, при этом конкретизируется третий аргумент.

Тот же пример:

sum1([3|6,1], 0, S) вызывает предикат sum1([6,1], 3, S).

sum1([6|1], 3, S) вызывает предикат sum1([1], 9, S).

sum1([1],9, S) вызывает предикат sum1([], 10, S).

sum([ ], 10, S) удовлетворяется, если S конкретизируется 10.

Последовательность возвратов следующая:

sum1([1], 9,1 0)

sum1([6,1], 3,1 0)

sum1([3,6,1], 0, 10)

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

max(X,Y,X):– X>=Y.

max(X,Y,Y):– X<Y.

Результативный предикат maxlist(LIST,MAX), где MAX – наибольший элемент списка LIST, выглядит следующим образом:

maxlist([X],X).

maxlist([X,Y|TAIL],MAX):–

maxlist([Y|TAIL],MAXTAIL),

max(X,MAXTAIL,MAX).

Смысл базового правила: максимальный элемент одноэлементного списка равен самому этому элементу. Иначе, если в списке есть хотя бы два элемента X и Y, выбирается максимальный элемент хвоста MAXTAIL и при этом MAX равен наибольшему из X и MAXTAIL. Рекурсия здесь нехвостовая, чтобы обеспечить конкретизацию переменных X и MAXTAIL.

3.5. Нахождение пути на графе

19. Поиск пути на графе – классическая задача. На Прологе она записывается очень компактно. После несложного расширения эта программа сможет отвечать на следующие вопросы:

- как добраться из одной вершины в другую, не посещая дважды одной и той же вершины;

- как пройти по маршруту, посетив заданную вершину;

- как добраться до нужной вершины, избежав некоторых вершин.

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

road(v1,v3).

road(v4,v1).

road(v3,v5).

Необходимо иметь информацию об обратных направлениях. Чтобы не дублировать базу данных, воспользуемся вспомогательным предикатом road1:

road1(T1,T2):–road(T1,T2);

road(T2,T1).

Для решения этой задачи удобнее всего собирать в список все пройденные вершины пути, исходя из следующих соображений: если существует дуга из вершины X в вершину Y, то путь найден (базовое правило), иначе чтобы найти путь из X в Y, надо найти дугу из X в Z и затем путь из Z в Y (рекурсивное правило):

way(X,Y,[ ]):–road1(X,Y).

way(X,Y,[Z|W]):–road1(X,Z), way(Z,Y,W).

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

way(X,Y,[Z|W]]);- road1(X,Z), way(Z,Y,W), not(membr(Z,W)).

Здесь member – знакомый предикат проверки принадлежности элемента списку.

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

way(X,Y,W,W):–road1(X,Y).

way(X,Y,W,L):– road1(X,Z), not(member(Z,W)),

way(Z,Y,[Z|W],L).

Для запуска этой программы можно воспользоваться интерфейсным предикатом go, аргументы которого содержат начальный и конечный пункты:

go(Here,There):– way(Here,There,[Here],W),

add(There,W,W1), reverse(W1,W2), write(W2).

Здесь исходный список маршрута конкретизируется начальной вершиной. К списку найденного маршрута добавляется конечный пункт (предикат add). Предикат reverse выполняет инверсию этого списка. Клозы этих последних предикатов было записано ранее.

3.6. Использование структур

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

Структура данных в Прологе задается на составной области определения (третий способ указания Domains).

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

20. База данных "Семья". Каждая семья состоит, с точки зрения логики, из трех объектов: мужа, жены и детей. Поскольку количество детей в разных семьях может быть разным, то их целесообразно представить в виде списка, состоящего из произвольного числа элементов. Каждого члена семьи в свою очередь можно представить структурой, состоящей из четырех компонент: имени, фамилии, даты рождения и работы. Информация о работе – это либо "не работает", либо указания кода работы и оклада.

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

Domains

data=dat(integer,string,integer)

work=worker(string,integer);notwork

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

memfam=mem(string,string,data,work)

Информацию о семьях можно занести в базу данных с помощью следующих предложений:

family(mem(jon,kelly,dat(17,may,1950),worker(bbz,15000)),

mem(bony,kelly,dat(29,may,1951),notwork)),

[mem(pat,kelly,dat(5,april,1983),notwork),

mem(liz,kelly,dat(10,april,1960),notwork)).

family(mem(bob,rob,dat(14,may,1930),worker(pla,12000)),

mem(sally,rob,dat(5,october,1931),worker(plt,11000)),[ ]). % нет детей

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

goal family(mem(_,kelly,_,_),_,_).

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

Можно найти все семьи с тремя детьми при помощи выражения:

goal family(X,_, [_,_,_]).

Чтобы найти имена и фамилии всех женщин, имеющий по крайней мере трех детей, можно задать вопрос:

goal family(_, mem(Name,Fam,_,_),[_,_,_|_]).

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

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

husband(X):–family(X,_,_). % X – ìóæ

vife(X):–family(_,X,_). % X – жена

child(X):–family(_,_,Children), % X – ребенок

member(X,Children).

exist(X):–husband(X); vife(X); child(X). % X – любой член семьи

dohod(mem(_,_,_,worker(_,D)),D). % D – доход работающего

dohod(mem(_,_,_,notwork),0). % 0 – доход неработающего

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

1) найти имена и фамилии всех людей из базы данных:

Goal exist(mem(Nam,Fam,_,_)).

2) Найти всех работающих жен:

Goal vife(mem(Nam,Fam,_,worker(_,_))).

3) Найти фамилии людей, чей доход меньше чем 8000:

Goal exist(Man), dohod(Man,D), D<8000.

21. Задача "Ханойская башня". Имеется три стержня А,В,С. На стержне А лежит N дисков пирамидой, сужающейся кверху. Надо переместить диски со стержня А на стержень C, используя промежуточный стержень B и соблюдая законы:

1) диски можно перемещать с одного стержня на другой по одному;

2) нельзя класть больший диск на меньший;

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

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

Собственно "перемещению" диска соответствует оператор вывода, указывающий, с какого стержня на какой переместить диск. Основным рабочим предикатом является рекурсивный предикат move. Базовое правило этой рекурсии: если диск один, то переместить его с левого стержня на правый. Иначе, переместить N-1 диск с левого диска на средний промежуточный, переместить один диск с левого стержня на правый и затем переместить N-1 диск со среднего стержня на правый, используя левый стержень как промежуточный.

domains

loc = right; middle; left

predicates

hanoi(integer)

move(integer, loc, loc, loc)

inform(loc, loc)

clauses

hanoi(N) :– move(N, left, middle, right). % Запуск программы

move(1, A, _, C) :– inform(A, C), !. % Переместить один диск

move(N, A, B, C) :– % Переместить N дисков

N1=N-1, move(N1, A, C, B),

inform(A, C), move(N1, B, A, C).

inform(Loc1, Loc2) :– write("\nMove a disk from ", Loc1, " to ", Loc2).

Goal hanoi(10). % Перемещаем 10 дисков

3.7. Динамическая база данных

Пролог поддерживает реляционную базу данных. Предикаты базы данных нужно объявлять в отдельном разделе Database. Программная секция Database должна предшествовать объявлению предикатов Predicates. Объявление предикатов базы данных аналогично их описанию в секции Predicates.

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

Для работы с базой данных используют стандартные предикаты asseta, assertz, retractall, consult, save и др. (см. раздел "Стандартные предикаты"). Также нужно иметь представление о структуре памяти системы Пролога. Исходная программа на Прологе хранится в области SOURSE, в то время как для размещения фактов динамической базы данных отведена область HEAP. Поэтому на экране нельзя видеть информацию, записанную в базу данных. Однако ее можно просмотреть как текстовый файл, если сохранить его в каталоге под своим именем.

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

22. Пример работы с динамической базой данных.

Domains

list=integer*

Database – db1 % База данных с именем db1

fact1(integer,string,list)

Database – db2 % База данных с именем db2

fact2(integer,string)

Clauses

fact1(1,f1,[1,2,3]).

fact1(2,f2,[1,3]).

fact1(3,f3,[2,2,1]).

fact2(1,],"one").

fact2(1,"one one"]).

fact2(2,"two").

Тогда цель:

Goal fact1(X,Y,Z)

ответит:

X=1 Y=f1 Z=[1,2,3])

X=2 Y=f2 Z=[1,3]).

X=3 Y=f3 Z=[2,2,1]).

3 solutions

Goal rettactall(fact1(X,Y,[_,2|Z])) % удалить факты по образцу

X=1 Y=f1 Z=3

X=3 Y=f3 Z=1

Goal retractall(fact1(X,Y,Z))

X=2 Y=f2 z=[1,3]

Goal retractall(db2) % удалить поименованную базу данных

Yes .

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

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

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

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

animal_is("гепард") :– it_is("млекопитающее"),

it_is("хищник"),

positive("имеет","рыжий цвет"),

positive("имеет", "черные пятна").

animal_is(“тигр”) :– it_is(“млекопитающее”),

it_is(“хищник”),

positive(“имеет”, “рыжий цвет”),

positive(“имеет”, “черные полосы”).

animal_is("зебра") :– it_is("копытное"),

positive("имеет","черные полосы").

animal_is("пингвин") :– it_is("птица"),

negative("умеет", "летать"),

positive("умеет", "плавать"),

positive("имеет", "черно-белый цвет").

Сходные правила должны быть для всех животных, которых предстоит классифицировать программе.

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

it_is("хищник") :–

positive("имеет","острые зубы"),

positive("имеет", "когти"),

positive("имеет", "глаза, направленные вперед").

it_is("копытное") :–

it_is("млекопитающее"),

positive("имеет","копыта"),

positive("æóåò", "æâà÷êó").

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

Goal animal_is(X), !,

write("Задуманное вами животное ",X).

Далее система пытается по очереди установить истинность или ложность правил высокого уровня, т.е. найти кандидата, которого она сможет проверить на соответствие предикату animal_is.

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

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

database

xpositive(symbol, symbol)

xnegative(symbol, symbol)

Clauses

positive(X, Y) :– % Положительный ответ обнаружен

xpositive(X, Y), !. % в базе данных

positive(X,Y):–xnegative(X,Y),!,fail. % Отрицательный ответ обнаружен

positive(X, Y) :– % Задается вопрос, для которого

not(xnegative(X, Y)), % ожидается положительный ответ

ask(X, Y, yes),!.

ask(X, Y, yes) :–

write(X, " оно ", Y, '\n'),

readchar(Reply),

ans_pos(X, Y, Reply).

ans_pos(X,Y,'y'):– assertz(xpositive(X,Y)).

ans_pos(X,Y,'n'):– assertz(xnegative(X,Y)), !, fail.

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

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

Все, что программа помещает в базу данных, всегда имеет вид пары, состоящей из глагола и свойства, например:

positive("имеет","перья").

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

xpositive(verb,,attribute)

xnegative(verb,attribute).

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

3.8. Обработка текстов

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

В данном разделе продемонстрируем две системы грамматического разбора. Система грамматического разбора – это программа, которая распознает синтаксические объекты в потоке лексем, т.е. реализует какую-либо формальную грамматику. Общеизвестны две основные стратегии грамматического разбора: нисходящая (сверху вниз) и восходящая (снизу вверх).

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

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

предложение --> группа_подлежащего группа_сказуемого

группа_подлежащего --> определение существительное

группа_подлежащего --> существительное

группа_сказуемого --> глагол существительное

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

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

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

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

Более важной сферой применения систем грамматического разбора является построение так называемого дерева грамматического разбора в том или ином виде, в котором явно указаны классы объектов и существующие между ними отношения

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

Предикат run начинает работу программы с создания окна, считывает исходное выражение в переменную STR . Следующий предикат tokl переводит строковую переменную в список токенов (лексем) TOKL, далее предикат s_exp запускает рабочий предикат plusexp, с которого собственно начинается работа анализатора.

Процедура multexp первую лексему (имя переменной) переводит в префиксную форму и проверяет остаток на наличие после нее (лексемы) операции умножения предикатом multexp1. Если знак "*" присутствует, последний предикат переводит сомножители в префиксную форму.

Предикат plusexp1 проверяет остаток после знака "+" на наличие операции умножения предикатом multexp. Если умножения нет, слагаемые также переводятся в префиксную форму.

domains

TOKL = STRING*

EXP=var(STRING);

plus(EXP,EXP);

mult(EXP,EXP)

PREDICATES

run

tokl(STRING,TOKL)

s_exp(TOKL,TOKL,EXP)

multexp(TOKL,TOKL,EXP)

multexp1(TOKL,TOKL,EXP,EXP)

plusexp(TOKL,TOKL,EXP)

plusexp1(TOKL,TOKL,EXP,EXP)

elmexp(TOKL,TOKL,EXP)

GOAL

run.

CLAUSES

run:– makewindow(1,2,7,"",0,0,25,80),

readln(STR),tokl(STR,TOKL),

s_exp(TOKL,_,EXP), write(EXP),nl.

tokl(STR,[TOK|TOKL]):–

fronttoken(STR,TOK,STR1),

tokl(STR1,TOKL).

tokl(_,[]).

s_exp(IL,OL,EXP):–plusexp(IL,OL,EXP).

plusexp(IL,OL,EXP2):–

multexp(IL,OL1,EXP1),

plusexp1(OL1,OL,EXP1,EXP2).

plusexp1(["+"|IL],OL,EXP1,EXP3):–

multexp(IL,OL1,EXP2),

plusexp1(OL1,OL, plus(EXP1,EXP2),EXP3).

plusexp1(IL,IL,EXP,EXP).

multexp(IL,OL,EXP2):–

elmexp(IL,OL1,EXP1),

multexp1(OL1,OL,EXP1,EXP2).

multexp1(["*"|IL],OL,EXP1,EXP3):–

elmexp(IL,OL1,EXP2),

multexp1(OL1,OL, mult(EXP1,EXP2),EXP3).

multexp1(IL,IL,EXP,EXP).

elmexp([NAME|IL],IL, var(NAME)).

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

<VERB PHRASE> ::= <verb> | <NOUN PHRASE>

Программа на Прологе:

DATABASE %Слова , которые должны быть распознаны

det( STRING ) % Определитель

noun( STRING ) % Существительное

rel( STRING ) % Предлог

verb( STRING ) % Глагол

DOMAINS % Описание грамматики

DETERM = none ; determ( STRING )

NOUNP = nounp( DETERM, STRING, RELCL)

RELCL = none ; relcl( STRING, VERBP )

SENTENCE = sent( NOUNP, VERBP )

VERBP = verb( STRING ) ; verbp( STRING, NOUNP )

TOKL = STRING*

PREDICATES

is_det( STRING )

is_noun( STRING )

is_rel( STRING )

is_verb( STRING )

s_determ( TOKL, TOKL, DETERM )

s_nounp( TOKL, TOKL, NOUNP )

s_relcl( TOKL, TOKL, RELCL )

s_sentence( TOKL, TOKL, SENTENCE )

s_verbp( TOKL, TOKL, VERBP )

tokl( STRING, TOKL )

tom(TOKL)

run1

run2(STRING)

sen_an

GOAL makewindow(1,6,0,"",0,0,25,80),

sen_an.

CLAUSES

sen_an:– write("Try: every man that lives loves a woman"),

readln(LIN), LIN >< "" ,

tokl(LIN,TOKL),

s_sentence( TOKL, _, SENT),

write("PROLOG OBJECT=",SENT," "),

readchar(_),clearwindow,!.

tokl(STR,[TOK|TOKL]) :–

fronttoken(STR,TOK,STR1),

tokl(STR1,TOKL).

tokl(_,[ ]).

s_sentence(TOKL,TOKL2,sent(NOUNP,VERBP)):–

s_nounp(TOKL,TOKL1,NOUNP),

s_verbp(TOKL1,TOKL2,VERBP),

TOKL2=[ ],!.

s_sentence(_,_,_):–write(">> Sentence not recognized \n"),fail.

% Группа подлежащего

s_nounp(TOKL,TOKL2,nounp(DETERM,NOUN,RELCL)):–

s_determ(TOKL,[NOUN|TOKL1],DETERM),

is_noun(NOUN),

s_relcl(TOKL1,TOKL2,RELCL).

% Определитель

s_determ([DETERM|TOKL],TOKL,determ(DETERM)):–

is_det(DETERM).

s_determ(TOKL,TOKL,none).

% Группа дополнения

s_relcl([REL|TOKL],TOKL1,relcl(REL,VERBP)):–

is_rel(REL),

s_verbp(TOKL,TOKL1,VERBP).

s_relcl(TOKL,TOKL,none).

% Группа сказуемого

s_verbp([VERB|TOKL],TOKL1,verbp(VERB,NOUNP)):–

is_verb(VERB),

s_nounp(TOKL,TOKL1,NOUNP).

s_verbp([VERB|TOKL],TOKL,verb(VERB)):–

is_verb(VERB).

is_noun(X):–noun(X),!.

is_noun(X):–noun(Y),concat(Y,"s",X).

is_det(X):–det(X).

is_rel(X):–rel(X).

is_verb(X):–verb(X),!.

is_verb(X):–verb(Y),concat(Y,"s",X),!.

is_verb(X):–verb(Y),concat(Y,"ed",X),!.

is_verb(X):–verb(Y),concat(Y,"es",X),!.

is_verb(X):–verb(Y),concat(Y,"ing",X).

% Словарь

det("every").

det("a").

noun("man").

noun("woman").

rel("that").

rel("who").

rel("whom").

rel("which").

rel("that").

verb("love").

verb("live").

4. Стандартные предикаты

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

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

(i,i) (i,o) (o,i) (o,o),

где i – входной параметр, о – выходной параметр. Однако не для каждого предиката все возможные варианты поточного шаблона имеют смысл.

Hиже приводятся некоторые наиболее часто употребляемые стандартные предикаты, сгруппированные в отдельные классы по их функциональному назначению. Более полный список стандартных предикатов можно найти в [3].

4.1. Ввод/вывод

readln(StringVariable)

(string) – (o)

Считывает строку с текущего устройства ввода и связывает ее с заданной переменной StringVariable. Обычно чтение производится с клавиатуры. В качестве конца строки используется символ возврата каретки. Readln считывает до 150 символов в строке при вводе с клавиатуры и до 64К при вводе с других устройств.

readint(IntgVariable)

(integer) – (o)

Читает целое число с текущего устройства ввода и связывает его с заданной переменной.

readreal(RealVariable)

(real) – (o)

Читает действительное число с текущего устройства чтения и связывает его с заданной переменной RealVariable. Обычно чтение производится с клавиатуры.

readchar(CharVariable)

(char) – (o)

Читает символ с текущего устройства ввода и связывает его с заданной переменной CharVariable. В отличие от inkey устанавливает режим ожидания ввода.

inkey(CharVariable)

(Char) – (o)

Читает символ со стандартного устройства ввода. В отличие от предиката readchar выполнение программы не прерывается. Поэтому inkey применяют главным образом для организации циклов ожидания.

keypressed

Выполняется успешно, если нажата некоторая клавиша. В отличие от предиката inkey с помощью keypressed можно установить, нажата ли клавиша, не читая при этом введенный с клавиатуры символ.

write( Variable|Constant * )

Запись заданных значений переменных и констант в заданное активное окно на текущем устройстве вывода.

Вызывает возврат каретки и перевод строки.

4.2. Управление экраном и оконная система

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

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

Фон	Передний план
Черный 0	Черный 0
Голубой 16	¦Голубой 1
Зеленый 32	Зеленый 2
Бирюзовый 48	Бирюзовый 3
Красный 64	Красный 4
Алый 80	Алый 5
Коричневый 96	Коричневый 6
Белый 112	Белый 7

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

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

makewindow(WindowNo, ScrAtt, FrameAtt, Framestr, Row, Column, Height, Width)

(integer,integer,integer,string,integer,integer,integer,integer)

- (i,i,i,i,i,i,i,i) (o,o,o,o,o,o,o,o)

Определяет для (i,i,i,i,i,i,i,i) область экрана в качестве окна. Каждое окно задается номером WindowNo. ScrAtt задает значение атрибута для всех позиций описываемого окна. Если FrameAtt не равно 0, окно берется в рамку и верхняя граница включает текст Framestr. Позиция левого верхнего угла окна задается параметрами Row и Col. Параметры Height и Width определяют соответственно высоту и ширину окна, которые должны быть совместимыми с размерами экрана. В случае (о,о,о,о,о,о,о,о) связывает характеристики текущего окна с выходными параметрами.

shiftwindow(WindowNo)

(integer) – (i) (o)

Активизирует (i) окно с номером WindowNo. Окно должно быть создано заранее. Связывает (o) c параметром "номер текущего окна".

removewindow

Удаляет текущее активное окно.

clearwindow

Очищает текущее активное окно.

cursor(Row,Column)

(integer,integer) – (i,i) (o,o)

Для (i,i) помещает курсор в позицию с координатами (Row,Column) или присваивает переменным Row и Column значения текущих координат курсора при (o,o).

4.3. Обработка строк

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

frontchar(String,FrontChar,RestString)

(string,char,string) – (i,o,o) (i,i,o) (i,o,i) (i,i,i) (o,i,i)

Разделяет заданную строку String согласно поточному шаблону на две части: первый символ FrontChar и оставшаяся часть строки RestString.

fronttoken(String,Token,RestString)

(string,string,string) – (i,o,o) (i,i,o)(i,o,i) (i,i,i) (o,i,i)

Разделяет строку, заданную параметром String, на лексему Token и остаток RestString согласно поточному шаблону. (Лексема – это последовательность символов, имеющих смысл. Она определяется либо как имя в соответствии с синтаксисом Турбо-Пролога, либо как строчное представление числа, при этом знак возвращается отдельно, либо как отдельный символ.)

frontstr(Lenght,Inpstring,StartString,RestString)

(integer,string,string,string) – (i,i,o,o)

Разделяет строку Inpstring на две части. StartString будет иметь длину Lenght первых символов исходной строки, RestString представляет собой остаток строки InpString.

concat(String1,String2,String3)

(string,string,string) – (i,i,o) (i,o,i) (o,i,i) (i,i,i)

Слияние строк , согласно поточному шаблону, по формуле: String3 = String1 + String2.

str_len(String,Length)

(string,integer) – (i,i) (i,o) (o,i)

Определяет длину Length строки String.

isname(StringParam)

(string) – (i)

Завершается успешно, если StringParam есть имя, удовлетворяющее синтаксису Пролога.

4.4. Преобразование типов

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

char_int(CharParam,IntgParam)

(char,integer) – (i,o) (o,i) (i,i)

Преобразует символ в код ASCII, согласно поточному шаблону.

str_int(StringParam,IntgParam)

(string,integer) – (i,o) (o,i) (i,i)

Строка, представляющая целое десятичное число, преобразуется в это число.

str_char(StringParam,CharParam)

(string,char) – (i,o) (o,i) (i,i)

Один знак как строка преобразуетс в символ.

str_real(StringParam,RealParam)

(string,real) – (i,o) (o,i) (i,i)

Строка, представляющая десятичное число, преобразуется в это число.

4.5. Работа с базой данных

consult(DosFileName)

(string) – (i)

Добавляет текстовый файл с именем DosFileName к текущей базе данных. Текстовый файл может быть, например, создан в результате выполнения предиката save. Этот файл содержит факты, которые должны быть описаны в разделе DbaseDom. Выполнение предиката не будет успешным, если в файле имеются синтаксические ошибки.

save(DosFileName)

(string) – (i)

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

asserta( Term )

(DbaseDom) – (i)

Заносит факт Term в базу данных перед другими фактами. Факт должен быть термом, принадлежащим области определения DbaseDom.

assertz( Term )

(DbaseDom) – (i)

Заносит факт Term в конец базы данных. Факт должен быть термом, принадлежащим области определения DbaseDom.

retract( Term )

(DbaseDom) – (_)

Удаляет первый факт из базы данных, который соответствует заданному факту Term.

retractall(Term)

(InternalDatabaseDomain) – (_)

Очищает всю базу данных.

4.6. Управляющие предикаты

exit

Выполняет немедленный выход из программы.

fail

Вынуждает завершиться предикат ложно и, следовательно, возвратиться к предыдущей точке разветвления (backtracking).

true

Значение предиката всегда истинно.

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

4.7. Прочие стандартные предикаты

random(RealVariable)

(real) – (o)

Равномерное псевдослучайное число в диапазоне от 0 до 1.

random(MaxValue,RandomInt)

(integer,integer) – (i,o)

Равномерное псевдослучайное целое число RandomInt в диапазоне от 0 до MaxValue.

findall( Variable, Atom, ListVariable )

В списке ListVariable возвращаются все решения для переменной Variable в предикате Atom.

not( Atom )

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

free( Variable )

Выполняется успешно, если Variable не является конкретизированной переменной.

bound( Variable )

Выполняется успешно, если Variable является конкретизированной переменной.

4.8. Арифметические и логические предикаты

В арифметических операциях могут участвовать операнды (числа и переменные), арифметические операции + (сложение), – (вычитание), * (умножение), / (деление), mod (деление по модулю), div (целочисленное деление), скобки.

Приоритет выполнения операций представлен числами:

+ , –	1
* , /	2
div ,mod	3
– ,+ (унарные)	4

Логические операторы:

>	Бодьше
<	Меньше
=	Равно
>=	Больше или равно
<=	Меньше или равно
<> ,	Не равно

Арифметические функции:

sin(Х)	Синус, угол в радианах
cos(Х)	Косинус, угол в радианах
tan(Х)	Тангенс, угол в радианах
arctan(Х)	Арктангенс
ln(Х)	Логарифм натуральный
log(Х)	Логарифм десятичный
abs(X)	Модуль аргумента
exp(Х)	Экспонента
sqrt(Х)	Корень квадратный

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

Часть 2. Лабораторные работы

Лабораторная работа №1. Общие сведения об языке логического программирования

Пример 1. Наша первая Пролог программа будет содержать информацию о военнослужащих некоторого воинского подразделения и их званиях: “Павлов генерал”, “Сабо полковник”, “Денисов капитан”, “Матвеев капитан”, “Кулёмин сержант”, “Николаев сержант”. Сформулировать на Прологе следующие вопросы: 1) Павлов генерал? 2) Кто является полковником? 3)Кем является Денисов? 4)В подразделение есть военный в звание сержанта? 5) В подразделение есть военный в звание подполковника? 6) Вывести военных, имеющих одинаковые звания.

В программе каждого военного мы представим предикатом military размерности 2, каждый компонент- атом, первый представляет фамилию, а второй – его звание.

Программа 3. База данных «Военная часть»

Domains

s=symbol

Predicates

military(s,s)

Clauses

military(pavlov, general).

military(sabo, polkovnik).

military(denisov, kapitan).

military(matveev, kapitan).

military(kulemin, serzhant).

military(nikolaev, serzhant).

Сформулируем запросы:

1) ? military(pavlov, general)

Ответ: yes

2) ? military(X, polkovnik)

Ответ: X= sabo

3) ? military(denisov, X)

Ответ: X= kapitan

4) ? military(_, serzhant)

Ответ: yes

5)? military(_, podpolkovnik)

Ответ: no

6) ? military(X,Y), military(Z, Y), X<>Z

Ответ: X= denisov Z= matveev Y= kapitan

X= kulemin Z= nikolaev Y= serzhant

Пример 2. Данные о крупных реках России сведены в таблицу:

Таблица 5.

Данные о крупных реках России

Название реки	Длина, км	Годовой сток, км³	Площадь бассейна, тыс. км²	Истоки	Куда впадает
Амур	4416	350	1855	Яблоневый хребет	Татарский пролив
Лена	4400	488	2490	Байкальский хребет	Море Лаптевых
Обь	4070	400	2990	Предгорья Алтая	Карское море
Иртыш	4248	323	1643	Китай	Обь
Енисей	3487	600	2580	Восточный Саян	Карское море
Волга	3530	255	1360	Валдайская возвышенность	Каспийское море
Колыма	2129	44	643	Хребет Черского	Восточносибирское море
Урал	2428	54	231	Южный Урал	Каспийское море
Дон	2200	45	504	Среднерусская возвышенность	Азовское море
Кама	1805	130	507	Верхне — Камская возвышенность	Волга
Печора	1809	130	322	Северный Урал	Баренцево море
Ангара	1779	62	1039	Байкал	Енисей
Селенга	1024	14	447	Монголия	Байкал
Кубань	870	11	58	Кавказ	Азовское море

Составить базу данных и ответить на следующие вопросы:

1) Определить реки, впадающие в Азовское море.

2) Определить реки, исток которых находится на Валдайской возвышенности?

3) Какие реки короче Камы?

4) Какие реки длиннее Иртыша?

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

Программа 4. База данных «Реки России»

Domains

S=symbol

N=integer

Predicates

reka(S,N,N,N,S,S)

Clauses

reka(amur, 4416, 350, 1855,yablonevi_hrebet,tatar_proliv).

reka(lena, 4400, 488, 2490, baikal_hrebet, more_laptevih).

reka(ob, 4070, 400, 2990, altai, more_karskoe).

reka(irtish, 4248, 323, 1643, kitai, ob).

reka(enisei, 3487, 600, 2580, vost_cain, more_karskoe).

reka(volga, 3530, 255, 1360, valdais_vozvishennost, more_kaspi).

reka(kolima, 2129, 44, 643, hrebet_cherskogo, vost_sibir_more).

reka(ural, 2428, 54, 231, yuzhni_ural, more_kaspi).

reka(don, 2200, 45, 504, sredn_rus_vozvvishennost, more_azov).

reka(kama, 1805, 130, 507, verhne_kamsk_ vozvvishennost, volga).

reka(pechora, 1809, 130, 322, sever_ural, barenzevo_more).

reka(angara, 1779, 62, 1039, baikal, enisei).

reka(selenga, 1024, 14, 447, mongolia, baikal).

reka(kuban, 870, 11, 58, kavkaz, more_azov).

Запросы:

reka(X, _, _, _, _, more_azov)

reka(X, _, _, _, valdais_vozvishennost,_)

reka(X, Y, _, _, _, _), reka(lena, Z, _, _, _, _), Y<Z

reka(X, Y, _, _, _, _), reka(irtish, Z, _, _, _, _), Y>Z

reka(kama, A,B,C,D,E)

Пример 3. Известно, что Лене нравится теннис, Денису нравится футбол, Борису – бейсбол, Эдику – плавание, Марку нравится теннис, а Фёдору то, что нравится Борису. Записать факты на Прологе и ответить на вопросы: 1)Кому нравится теннис? 2) Что нравится Федору? 3)Кто занимается одинаковыми видами спорта?

Программа 5. База знаний «Предпочтения»

Predicates

likes(symbol,symbol)

Clauses

likes(lenа, tennis).

likes(denis, football).

likes(boris, baseball).

likes(edic, swimming).

likes(mark, tennis).

likes(fedor, Activity):- likes(boris, Activity).

/* Activity играет роль переменной*/

Запросы

1) ? likes(X, tennis)

Ответ:

X= lenа

X= mark

2) ? likes(fedor, X)

Ответ:

X= baseball

3) ? likes(X, T), likes(Y, T)

Ответ:

X= lenа Y= mark T= tennis

X= mark Y= lenа T= tennis

X= boris Y= fedor T= baseball

X= fedor Y= boris T= baseball

Пример 4. Лена, Анна, Денис и Борис-люди, лада и нисан - автомобили, Лене нравится лада, Анне - пицца, Денису - футбол, а Борис - Мерседес, Ваське - рыбка. Пицца, лада, мерседес продаются. Человек может купить машину, если она продается, и она ему нравится. Сформулировать на прологе вопросы: 1)Какую машину может купить Лена? 2) Кто-нибудь может купить мерседес? 3) какие машины продаются, и ответить на них.

Программа 6. База знаний «Предпочтения и возможности»

Domains

s=symbol

Predicates

human(s)

car(s)

likes(s,s)

can_by(s,s)

cells(s)

Clauses

human( lena ).

human( anna ).

human( denis ).

human( boris ).

car( lada ).

car( nissan ).

likes( lena, lada ).

likes( anna, pizza ).

likes( denis, football ).

likes( boris, mersedes ).

likes( vasya, ribka ).

cells(pizza).

cells(lada).

cells(mersedes).

can_by(X,Y):-human(X), car(Y), likes(X,Y), cells(Y).

Запросы:

1) can_by(lena, X)

X=lada

2) can_by(_,mersedes)

3) car(X),cells(X)

X=lada

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

Программа 7. Ввод данных

Predicates

vvod_int

vvod_ch

vvod_s

Clauses

vvod_int:- readint(N1), readint(N2), N=N1+N2, write(N).

vvod_ch:- readchar(N1), readchar(N2), N=N1+N2, write(N).

vvod_s:- readln(N1), readln(N2), concat(N1,N2,N), write(N).

Пример 6. Вывести в каждой строке сообщения: Леонард отец Катерины, Карл отец Джейсона, Карл отец Марины.

Программа 8. База знаний «Семья»

Domains

name = symbol

Predicates

father(name, name)

everybody

clauses

father(leonard, katherine).

father(carl, jason).

father(carl, marinа).

everybody :-

father(X, Y),

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

fail.

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

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

Отрицание задается с помощью предиката not.

Пример 7. У нас есть информация о странах-партнерах Европы, имеющих общую границу. Предположим, нас интересуют какие страны-партнеры не имеют общей границы.

Программа 9. База знаний «Страны Европы»

Domains

country=symbol

Predicates

euro_pair(country, country)

border(country, country)

find_non_border_pair

Clauses

euro_pair(”France”, ”Germany”).

euro_pair(”France”, ”Spain”).

euro_pair(”France”, ”Italy”).

euro_pair(”Germany”, ”Spain”).

euro_pair(”Germany”, ”Italy”).

euro_pair(”Spain”, ”Italy”).

border(”France”, ”Germany”).

border(”France”, ”Spain”).

border (”France”, ”Italy”).

find_non_border_pair:-

euro_pair(X,Y),

not(border(X,Y)),

write(X,” – “,Y),fail,nl.

Goal

find_non_border_pair

Результатом запроса будет ответ

Germany - Spain. Germany - Italy. Spain - Italy.

Пример 8. Использование составных объектов

Программа 10. База данных «Коллекция»(Вариант 1)

Domains

personal_library=book(title, author, publisher, year)

collector, title, author, publisher=symbol

year=integer

Predicates

collection(collector, personal_library)

Clauses

collection(ivanov, book(”Zolushka”, ”Denis Tarakanov”, ”Dinamo”, 2003)).

collection(petrov, book(”Maslenniza”, ”Anna Zimina”, ”Zenit”, 2005)).

collection( petrov, book(”Repka”,”Irina Larina”, ”Mir”, 1999)).

/*Демонстрация двухуровневого составного объекта*/

Программа 11. База данных «Коллекция»(Вариант 2)

Domains

personal_library=book(title, author, publiсation)

publiсation= publiсation (publisher, year)

collector, title, author, publisher =symbol

year=integer

Predicates

collection(collector, personal_library)

Clauses

collection(ivanov,book(”Zolushka”,”Den Taran”, publiсation (”Dina”, 2003))).

collection(petrov,book(”Maslenniza”,”Anna Zima”,publiсation(”Zenit”,2005))).

collection( petrov, book(”Repka”,”Irina Larina”,publiсation (”Mir”, 1999))).

/*Демонстрация использования конструкций альтернативных доменов*/

Программа 12. База знаний «Клуб по интересам»

Domains

thing=misc_ thing (whatever);

book(author, title);

record(artist, album, type)

person, whatever, title, author,artist, album, type =symbol

Predicates

owns(person, thing)

show_misc_things

show_books

show_records

Clauses

owns (“Ivanov“, misc_things(“sports car“)).

owns (“Petrov“, misc_things(“motor cycle“)).

owns (“Smirnov“, misc_things(“piano“)).

owns (“Ivanov”, book (“James A.Mishener“,“Space“)).

owns (“Petrov”, book (“Frank Herbert“, “Dune“)).

owns (“Sidorov”, book (“J.R.R. Tolkein“,“Return of the Ring“)).

owns (“Ivanov”, record (“Elton John”, “Ice Fair”, “popular“)).

owns (“Petrov”, record(“Michael Jackson“, “We are the World“, “popular“)).

owns (“Sidorov”, record (“Madonna“,“Madonna“, “popular“)).

show_misc_things:- owns (X, misc_things(Y)),write( X, “ ”,Y), nl, fail.

show_books:- owns (X, book (_,Y)),write( X, “ ”,Y), nl, fail.

show_records:- owns (X, record (_,Y,_)),write( X, “ ”,Y), nl, fail.

Задания для самостоятельной работы

Вариант1.Дана база данных “Родители и дети”:

родитель(полина, борис), родитель(анатолий, борис), родитель(анатолий, лиза), родитель(борис, катя), родитель(борис, валентина), родитель(полина, евгений).

Сформулировать вопросы на Прологе: Кто является родителем Кати? Есть ли у Лизы ребенок? Кто дети Бориса? Кто чей родитель?

Вариант 2.Дана база данных “Теремок”:

живет (муха, горюха), живет(комар, пискун), живет(мышка, погрызуха), живет(лягушка, квакушка), живет(заюнок, кривоног),

живет( лиса, краса), живет(волк, хватыш), не_живет(медведь, пригнетыш).

Указать ответы на следующие вопросы:

?-живет(мышка, погрызуха). ? -живет(волк, X).

?-живет(Х, кривоног). ?-не_живет(М,P).

Сформулировать вопросы на Прологе: Живет ли лягушка в теремке? Какое прозвище у лисы? Кто имеет прозвище горюха? Какой следует задать вопрос, чтобы узнать обитателей теремка (без прозвищ)?

Вариант 3.База данных “Рождение и хобби друзей”:

рождение(иванова, лена, 22, июнь, 1971), рождение(петров, сергей, 25, октябрь, 1973), рождение(сидорова, оля, 1, декабрь, 1974), любит(иванова, лена, книги), любит(иванова, лена, танцы), любит(петров, сергей, видео), любит(сидорова, оля, кино).

Сформулировать вопросы на Прологе: Кто родился в 1971 году? Кто родился в октябре? Кто любит книги? Кто любит и книги и танцы?

Вариант 4. База данных “Колобок”: ушел(колобок,дедушка), ушел(колобок, бабушка), ушел(колобок, заяц), ушел(колобок, волк), ушел(колобок, медведь), не_ушел(колобок, лиса).

Сформулировать вопросы на Прологе: Кто ушел от волка? Кто не ушел от лисы? Кто ушел от волка и от бабушки? Какой следует задать вопрос, чтобы узнать всех персонажей сказки?

Вариант 5 База данных “Распорядок дня”:

занятие (0, 7, сон), занятие (7, 8, завтрак), занятие (8, 13, школа), занятие (13, 14, обед), занятие (14, 19, свобода), занятие (19, 20, ужин), занятие (20, 23, отдых), занятие (23, 24, сон).Сформулировать вопросы на Прологе: Когда бывает обед? Что бывает между 14 и 19 часами? Когда бывает сон? (сколько будет решений?)

Вариант 6.Построить базу данных “Важнейшие события Древнего Мира” на основе установленных фактов, произошедших с 31 по 6 век до нашей эры.

Каждый факт приводить в виде событие(Х,Y,Z), где X — название государства, где произошло событие, Y - в каком веке произошло событие, Z — какое произошло событие.

В 31-м веке до нашей эры возникли первые города-государства. Единое государство в Египте образовалось в 30 веке до нашей эры. В 27 веке до нашей эры в Индии появились первые древнейшие города, а в Египте построена пирамида Хеопса. Первые греческие государства появились в 18 веке до нашей эры. В этом же веке в Египте произошло крупное восстание бедняков и рабов. В 15 веке до нашей эры появились первые государства в Китае. Тутмос III правил в Египте в 15 веке до нашей эры. Греция вела троянскую войну в 13 веке до нашей эры. Вторжение борийских племен в Грецию произошло в 11 веке до нашей эры. В 8 веке до нашей эры был основан город Рим. Олимпийские игры стали проводиться в Греции в 8 веке до нашей эры. В 6 веке до нашей эры в Риме была установлена республика, а в Греции произошли реформы Солона. В этом же веке персы взяли Вавилон в Междуречье и завоевали Египет.

1. Составить 3 запроса к этой базе данных.

2. Какие события произошли в период с 15 до 7 в. до н.э.

3. В таблице даны некоторые характеристики движения планет Солнечной системы (числовые величины округлены):

Вариант 7

Таблица 6.

Характеристики движения планет солнечной системы

Планета	Расстояние до Солнца (у.е.)	Период обращения	Средние солнечные сутки
Меркурий	39	88 суток	176 суток
Венера	72	225 суток	117 суток
Земля	100	365 суток	24 часа
Марс	152	687 суток	25 часов
Юпитер	520	12 лет	10 часов
Сатурн	954	29 лет	10 часов
Уран	1920	84 года	24 часа
Нептун	3010	165 лет	22 часа
Плутон	3950	247 лет	6 суток

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

Ответить на вопросы: Какие планеты ближе к Солнцу, чем Земля? Какие планеты дальше от Солнца, чем Земля? На каких планетах солнечные сутки меньше, чем земные? На каких планетах период обращения измеряется в годах?

Вариант 8 Построить базу знаний “Рабочая смена”:

Мария работает в дневную смену. Сергей работает в вечернюю смену. Борис работает в вечернюю смену. Валентина работает в вечернюю смену. Два служащих знают друг друга, если они работают в одну смену. Определить: Знает ли Сергей Бориса? Кого знает Валентина? Кого знает Мария?

Вариант 9 Даны результаты сдачи экзаменов для группы из пяти учеников:

Таблица 7.

Успеваемость

Фамилия	Алгебра	Геометрия	История
Бобров	5	3	2
Вяткин	5	5	5
Кротов	2	3	3
Соснин	4	4	4
Вавилов	4	2	1

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

отличник - человек, у которого по всем предметам пятерки;

двоечник - есть хотя бы одна двойка;

математик - по алгебре и по геометрии учится на 4 и 5;

введите предикаты алгебра, геометрия, история для определения оценки Y для ученика X.

Получить ответы на следующие вопросы: Является ли Вяткин отличником? Определить всех отличников. Является ли Соснин математиком? Определить всех неуспевающих по истории.

Вариант 10. Сформировать базу знаний “Квартет” из следующих фактов и правил:

Мартышка играет на скрипке. Осел играет на альте. Козел играет на виолончели. Мишка играет на контрабасе. Четверо музыкантов X,Y,Z и W могут образовать квартет, если один из них играет на скрипке, другой — на альте, третий — на виолончели и четвертый — на контрабасе.

Ответить на вопросы: Кто играет на альте? На чем играет мартышка? Образуют ли квартет Мартышка, Осел, Козел и Мишка? Кто из музыкантов данной базы знаний может образовать квартет?

Вариант 11. База знаний “Воинская служба”:

возраст(борис ,18), возраст(андрей, 17), возраст(михаил,18), возраст(анна,18), возраст(юлия ,17), мужчина(андрей), мужчина(борис), мужчина(михаил), женщина(анна), женщина(юлия).

Определить правило подлежит призыву, не_подлежит_призыву.

Сформулировать вопросы: Кто подлежит призыву? Подлежит ли призыву Анна?

Вариант 12. База знаний "Семья”:

мать(екатерина, юлия), мать(екатерина, мария), мать(анна, екатерина), отец(петр, юлия), отец(виктор,петр), отец(андрей, екатерина).

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

Сформулировать вопросы на Прологе:

Кто является ребенком Екатерины и Петра? Кто является дедом Юлии? Кто является бабкой Юлии?

Вариант 13.Запрограммируйте утверждения.

Число четное. Число не четное. Ни одно число не является четным и нечетным одновременно. Число не четное, если следующее за ним четное. Число, следующее за данным числом нечетное, если данное число четное, число, следующее за данным числом четное, если данное число нечетное.

Рекомендуемая литература

1. Стобо Д.Ж. Язык программирования Пролог: Пер. с англ.- М.- Радио и связь, 1993.-368 с.:ил.

2. Ин Ц., Соломон Д. Использование Турбо-Пролога: Пер. с англ.-М.:Мир, 1993.-608 с.,ил.

3. Информатика. Задачник-практикум в 2 т./Под ред. И.Г.Семакина, Е.К. Хеннера: Том.2.-М.:-БИНОМ. Лаборатория знаний, 2003.-278 с.:ил.

4. Каймин В.А. Основы компьютерной технологии.- М.:Финансы и статистика, 1992.-208 с.: ил.

Лабораторная работа №2. Арифметика. Управление логическим выводом в программах

Пример 1. Описать предикаты для вычисления суммы, разности, произведения, частного двух чисел, возведения числа в квадрат, вывода остатка при деление на 3, вывод случайного числа из интервала [1,100].

Программа 13. Арифметика

Domains

N=integer

R=real

Predicates

add(N,N)

sub(N,N,N)

multi(N,N,N)

division(N,N,R)

kvadrat(N,N)

ostat(N,N)

vivod(N)

Clauses

add(X,Y):-S=X+Y, write(“Sum= ”,S),nl.

sub(X,Y,S):-S=X-Y.

multi(X,Y,P):-P=X*Y.

division(X,Y,R):-Y<>0, R=X/Y.

kvadrat(X,N):-N=X*X.

ostat(X,N):-N=X mod 3.

vivod(N):-random(Y), N=1+Y*100.

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

max(X,Y,X):-X>=Y.

max(X,Y,Y):-X<Y.

Эти правила являются взаимоисключающими. Возможна более экономная формулировка: если X>=Y, то максимум=X, иначе =Y. На Прологе это запишется следующим образом:

max(X,Y,X):-X>=Y, !.

max(_,Y,Y).

Программа 14. Максимум

Domains

N=integer

Predicates

max(N,N,N)

Clauses

max(X, Y, X):-X>Y,!.

max(_,Y,Y).

Пример 3. Рассмотрим различные способы записи предиката different, определяющего различны ли числа, использующие сочетание встроенных предикатов ! и fail.

different(X,X):-!,fail.

different(_,_).

или

different(X,Y):-X=Y,!,fail.

different(_,_).

или

different(X,Y):-X=Y,!,fail; true.