В качестве примера приводится вопрос:
?ЛИНИЯ(0,0,x,0,1);.
В результате ответа на этот вопрос на экране появится треугольник белого цвета. В данном ситуации все просто. Причина появления белого треугольника в том, что величина абциссы второй точки не определена, в этом случае абцисса должна быть любым числом, в допустимых пределах. Как правило, область допустимых значений ограничена размерами экрана. Языковые средства Пролога-Д обеспечивают возможность наращивать определения, естественным путем поддерживают структурность описания объекта. В качестве примера приводится описание построения домика. Домик можно определить как треугольник и квадрат, совмещенные одной стороной. Квадрат можно определить посредством четырех отрезков формально это выглядит так:
квадр(x,y,z,t)<-ЛИНИЯ(x,y,x,t,1),ЛИНИЯ(x,y,z,y,1),
ЛИНИЯ(x,t,z,t,1), ЛИНИЯ(z,y,z,t,1);.
Аналогично определяется треугольник:
треуг(x,y,z,t)<-ЛИНИЯ(x,y,t,y,1),СЛОЖЕНИЕ(x,t,r),
ДЕЛЕНИЕ(r,2,f), ЛИНИЯ(x,y,f,z,1), ЛИНИЯ(f,z,t,y,1);
(Предикат с именем ДЕЛЕНИЕ - предикат деления первого аргумента на второй, частное в третьем, а предикат с именем СЛОЖЕНИЕ есть сложение первого аргумента со вторым, результат в третьем аргументе.) Oпределение дома длиной 20 единиц, высотой этажа 10 единиц и высотой крыши 20 единиц имеет вид:
дом(x,y)<-крыша(x,y,r,f),этаж(x,y,f);
этаж(x,y,f)<-СЛОЖЕНИЕ(y,20,z),квадр(x,y,f,z);
крыша(x,y,r,f)<-СЛОЖЕНИЕ(r,10,y),СЛОЖЕНИЕ(x,20,f),
треуг(x,y,r,f);
Вновь необходимо разделить это описание на две части: в одной части определяется крыша, а в другой, следующей, этаж. (Это, именно тот случай, когда дом начинают строить с крыши.) Использование рекурсивных определений дает возможность записать базу знаний более лаконично. Рекурсия может быть использована и для создания динамически изменяющегося графического объекта. Для этого на одном и том же месте последовательно фиксируется образ объекта, так, что его цвет попеременно меняется от цвета фона до цвета, определяемого в базе знаний. Например, описание летящей птицы, машущей крыльями. В предикате взмах описан взмах вниз и, затем, взмах вверх. Первому положению соответствует горизонтальное положение отрезка белого цвета, затем этот отрезок гасится, становится цветом фона. Положению вверх соответствует угол, состоящий из двух отрезков белого цвета, которые затем гасятся. Каждое из понятий вверх и вниз описывается отдельно, при этом производятся арифметические операции, необходимые для вычисления координат начала и конца отрезков. Периодическое повторение взмаха вверх и вниз осуществляется с помощью рекурсивного обращения к одному и тому же предикату птица. (Внимание! В некоторых вариантах транслятора может быть не предусмотрена обработка возникающей в данном примере эффекта концевой рекурсии, типа петли. Следствием этого может быть аварийный останов после нескольких десятков взмахов. Полное описание птицы, машущей крыльями, приведено ниже:
птица(x,y)<-взмах(x,y),птица(x,y);
взмах(x,y)<-вниз(x,y,1),вниз(x,y,0), вверх(x,y,1), вверх(x,y,0);
вниз(x,y,c)<-сдв(x,y,z,t,u,v), ЛИНИЯ(z,y,u,y,1);
вверх(x,y)<-сдв(x,y,z,t,u,v),ЛИНИЯ(x,y,z,t,1), ЛИНИЯ(x,y,u,v,1);
сдв(x,y,z,t,u,v)<-сдп(x,y,z,t),сдл(x,y,u,v);
сдп(x,y,z,t)<-СЛОЖЕНИЕ(x,5,z),СЛОЖЕНИЕ(t,5,y);
сдл(x,y,z,t)<-СЛОЖЕНИЕ(z,5,x),СЛОЖЕНИЕ(t,5,y);
Декларативность языка позволяет создавать достаточно сложные картины, используя известные принципы декомпозиции графического объекта на части и последующее их описание. Например, картина, содержащая дом, летящую птичку есть пример и описания сложного синтетического объекта, и использования рекурсии для определения динамического изменения объекта:
дом(x,y)<-крыша(x,y,r,f), этаж(x,y,f);
этаж(x,y,f)<-СЛОЖЕНИЕ(y,20,z),квадр(x,y,f,z);
крыша(x,y,r,f)<-СЛОЖЕНИЕ(r,10,y),СЛОЖЕНИЕ(x,20,f),
треуг(x,y,r,f);
треуг(x,y,z,t)<-ЛИНИЯ(x,y,t,y,1),ДЕЛЕНИЕ2(x,t,f),угол(x,y,z,t,f);
угол(x,y,z,t,f)<-ЛИНИЯ(x,y,f,z,1),ЛИНИЯ(f,z,t,y,1);
ДЕЛЕНИЕ2(x,t,f)<-СЛОЖЕНИЕ(x,t,r),ДЕЛЕНИЕ(r,2,f);
квадр(x,y,z,t)<-ЛИНИЯ(x,y,x,t,1),ЛИНИЯ(x,y,z,y,1),ч2(x,y,z,t);
ч2(x,y,z,t)<-ЛИНИЯ(x,t,z,t,1),ЛИНИЯ(z,y,z,t,1);.
птица(x,y)<-взмах(x,y),птица(x,y);
взмах(x,y)<-вниз(x,y,1),вниз(x,y,0),вверх(x,y,1),вверх(x,y,0);
вниз(x,y,c)<-сдв(x,y,z,t,u,v),ЛИНИЯ(z,y,u,y,1);
вверх(x,y)<-сдв(x,y,z,t,u,v),
ЛИНИЯ(x,y,z,t,1),ЛИНИЯ(x,y,u,v,1);
сдв(x,y,z,t,u,v)<-сдп(x,y,z,t),сдл(x,y,u,v);
сдп(x,y,z,t)<-СЛОЖЕНИЕ(x,5,z),СЛОЖЕНИЕ(t,5,y);
сдл(x,y,z,t)<-СЛОЖЕНИЕ(z,5,x),СЛОЖЕНИЕ(t,5,y);
В ответ на вопрос:
?дом(70,110),птица(120,50);
на экране будет построен дом и нарисована птичка, машущая крыльями. Данный пример представляет собой совокупность двух описаний - дома и птицы, машущей крыльями, каждый из которых был разобран выше. Обратите внимание только на одно обстоятельство - предикат птица должен быть описан после предиката дом, так как в нем содержится концевая рекурсия - типа петли.
Контрольные вопросы и задания
Задание:1. Используя рекурсивное определение, напишите базу знаний, описывающую многоэтажный дом.
Задание:2. Опишите на языке Пролог-Д построение улицы без учета и с учетом перспективы.
Тема5: Обработка списков.
| Содержание лекции | Содержание лабораторного занятия |
| Программные средства разработки и реализации ИИС: универсальные языки программирования, универсальные языки представления знаний и программные оболочки. Краткая характеристика программных средств Лисп, Пролог, FRL, Rule-Master, Expert-Easy, ЭКО и др. Технические средства разработки и реализации ИИС: Лисп и Пролог- процессоры. | Программные средства разработки и реализации ИИС: универсальные языки программирования, универсальные языки представления знаний и программные оболочки. Краткая характеристика программных средств. Задачи, связанные с перечислением объектов. Обработка списков. Элементы списка. Принадлежность элемента списку. Склеивание двух списков. |
Задание: Составить базу знаний для своего варианта используя обработку списков.
Исполнение: Написать программу, реализующего функции обработки списков на языке Пролог-Д.
Лабораторная установка: Персональный компьютер с ОС Windows, MS Office, языке Пролог-Д, являющемся учебной версией классического Пролога.
Оценка: Рассматривают содержание нового направления информатики (базы знаний) и особенности его реализации.
Время выполнения работы: 4 часа.
Методические указания
На практике часто встречаются задачи, связанные с перечислением объектов. Для описания таких объектов используются списки. Например, список учеников первого класса: [Саша,Петя,Дима,Ксюша,Лена,Оля,Катя].
Элементами списка могут быть не только атомы, но и функции и, вообще, любые элементы, даже списки. Например, список, состоящий из функций - список остановок поезда с указанием времени стоянки:
[Челябинск(0),Миасс(2),Златоуст(5),Вязовая(5),Усть-Катав(2), Аша(2), Уфа(20),Абдулино(3),Самара(20),Сызрань(2),Инза(2),
Рузаевка(10), Потьма(2), Рязань(5), Москва(0)].
Примером списка, состоящего из списков, может служить прямоугольная таблица (матрица), представляющая собой список строк, каждая из которых список элементов в данной строке. Например, таблица: 23 45 56 2 78 89 66 45 56 12 3 75 2 3 6 5 2 1 56 2 5 8 9 22 23 22 33 5 6 9 1 33 может быть представлена следующим списком, состоящим из списков:
[[23,45,56,2,78,89,66,45],[56,12,3,75,2,3,6,5],
[2,1,56,2,5,8,9,22],[2,1,56,2,5,8,9,22],[23,22,33,5,6,9,1,33]].
Во всех примерах квадратные скобки означают, что данный объект представляет собой список. Список может быть определен двумя способами: перечислением элементов списка, то есть так, как это было сделано выше и определением головы и хвоста списка. Например, список [X|Y] определен именно таким путем. X - это голова списка, а Y - его хвост. Различные шаблоны определяют различное внутреннее представление.
Шаблону [x,y] соответствует внутреннее представление
СПИСОК
/ \
x СПИСОК
/ \
y [ ]
Шаблону [x|y] соответствует внутреннее представление:
СПИСОК
/ \
x y
Разные шаблоны - разные внутренние представления - обуславливают различия в унификации. Используя представление списка можно решить ряд задач.
1. Принадлежность элемента списку.
Эту задачу можно описать с помощью следующих выражений:
а). Основной случай можно сформулировать следующим образом:
терм Р принадлежит списку [X..Y], если P=X..
б). Рекурсивная ситуация описывается с помощью высказывания "терм Р принадлежит списку [X..Y], если Р принадлежит Y". На языке Пролог-Д эти два высказывания можно записать в виде двух предложений:
принадлежит(P,L)<- равно(L,[X|Y]),равно(P,X);
принадлежит(P,L)<- равно(L,[X|Y]),принадлежит(P,Y);.
Эти определения можно усовершенствовать, если вспомнить, что, в соответствии с процедурной семантикой, Пролог-Д унифицирует сначала голову правила, а затем его цели. Усовершенствованная программа будет выглядеть так:
элемент(P,[P|T]);
элемент(P,[X|Y])<- элемент(P,Y);.
2. Склеивание двух списков.
Эту задачу можно описать с помощью следующих выражений:
а). основная ситуация состоит в том, что если к пустому списку [ ] добавить список Р, то в результате получится Р.
б). рекурсивная ситуация состоит в том, что можно список Р добавить к концу списка С, если Р будет добавлен к хвосту С и затем присоединен к голове В. На Прологе-Д эти предикаты можно записать так:
добавить([],[P],[P]);
добавить(C,P,B)<- равно(C,[X,Y]),добавить(Y,P,Z), равно(B,[T,Z]);.
Пользуясь вышеупомянутым свойством процедурной семантики Пролога-Д, эту программу тоже можно упростить:
присоединить([],[P],[P]);
присоединить([X|Y],P,[X|T])<-присоединить(Y,P,T);.
Например, если задан вопрос к этой базе знаний:
?присоединить(L,[Джим |R],[Джек, Билл, Джим, Тим, Джим, Боб];,
то будут получены ответы:
L=[Джек, Билл] R=[Тим, Джим, Боб] L=[Джек, Билл, Джим, Тим] R=[Боб].
Контрольные вопросы и задания
Задание:1. Напишите базу знаний, описывающую сортировку списка, элементы которого целые, по убыванию.