С. Григорьев
Йошкар-Ола
Программирование на Прологе-Д
Программа на Прологе представляет собой базу знаний и следующий за ней вопрос. Построению базы знаний посвящена данная статья. Здесь рассматриваются структура программы и некоторые приемы технологии программирования, связанные с использованием встроенных предикатов, рекурсии, графики, специфичные для Пролога-Д. Как и прежде во всех случаях, где это необходимо, будут оговариваться различия Пролога-Д MSX и Пролога-Д БК-0010.
Факты и правила
Особенностью языка Пролог-Д, отличающей его от других языков, используемых для работы на ЭВМ, является его применение не для программирования, но главным образом для описания данных и правил их обработки. Построение базы знаний на Прологе-Д означает выявление множества исследуемых объектов и связей между ними, совокупность которых описывает явление или процесс: иными словами, создание информационно-логической модели описываемого на языке Пролог-Д явления или процесса.
Первый шаг построения базы знаний состоит в выявлении объектов и соотношений между ними, отвечающих на вопрос «что дано?». Такую информацию целесообразно представлять в виде совокупности факсов. Классическим примером фактографии служит англо-русский словарь. Записанный средствами Пролога-Д, он выглядит так:
Код:
русангл(мама,mammy);
русангл(небо,sky);
русангл(солнце,sun);
русангл(мальчик,boy);
и т.д. Подобные отношения представляют собой грамматическую конструкцию Пролога-Д, называемую фактом. Факт задается в виде функционала: имя и совокупность аргументов. В данном примере «русангл» - это имя; оно определяет информацию, записываемую в факте. Русские и английские слова мама, mammy, небо, sky, солнце, sun, мальчик, boy представляют собой аргументы фактов, определяющих взаимно-однозначное соответствие между русскими и английскими словами. Необязательно, чтобы факт имел два аргумента. Например, факт
имеет один аргумент Николай, а факт
Код:
родился(Петров,Иван,10,сентябрь,1979);
имеет пять аргументов. Однако с точки зрения синтаксиса языка Пролог-Д необходим хотя бы один аргумент. Если факт в базе знаний имеет имя и не имеет аргументов, то система выдаст сообщение о синтаксической ошибке.
Приведенный пример, по сути дела, уже является базой знаний. Перед этой базой знаний можно ставить различные вопросы:
если необходимо узнать все слова, хранящиеся в базе знаний;
чтобы узнать, как по-английски «мама»;
чтобы узнать, что значит слово sky.
Для описания всего множества информации достаточно фактов. Однако если можно задать некоторые связи и отношения между объектами, то удается сократить число фактов и тем самым сделать базу знаний более лаконичной. Связи и отношения между объектами задаются правилами. При построении правил выделяется совокупность отношений, отвечающих на вопрос «что известно?». Правило можно построить, пользуясь известным принципом разделения исходной задачи на более простые, которые тоже, в свою очередь, могут быть разделены. Этот процесс известен под названием декомпозиции задачи. Декомпозиция заканчивается в тот момент, когда отношения связывают зафиксированные в базе знаний объекты. Например, в задаче о построении родственных отношений можно определить следующие правила:
Код:
бабушка(x,y)<-мама(x,z),мама(z,у);
бабушка(х,у)<-мама(x,z),папа(z,y);
дедушка(х,у)<—папа(х,z),папа(z,у);
дедушка(х,у)<-папа(x,z),мама(z,y);
Левая часть правила называется головой; разделенные запятыми выражения в правой части - целями; последние образуют тело правила.
Процесс декомпозиции не обязательно однозначен. Даже простой пример о родственниках допускает и иную трактовку. Если ввести правило, определяющее понятие «родитель»
Код:
родитель(х,у)<-мама(х,у);
родитель(х,у)<-папа(х,у);
то бабушку и дедушку можно определить проще:
Код:
бабушка(х,у)<-мама(x,z),родитель(z,y);
дедушка(х,у)<-папа(x,z),родитель(z,y);
Если к только что записанным правилам добавить несколько фактов, определяющих мам и пап, то получается база знаний «семья»:
Код:
мама(Саша,Петя);
папа(Сережа,Петя);
мама(Оля,Саша);
папа(Коля,Саша);
мама(Люда,Сережа);
папа(Петя,Сережа);
родитель(x,y)<-мама(x,y);
родитель(x,y)<-папа(x,y);,
бабушка(x,y)<-мама(x,z),родитель(z,y);
дедушка(x,y)<-папа(x,z),родитель(z,y);
В данном примере для определения понятия родитель(х, у) потребовалось более одного правила. По сути дела, здесь использовано недетерминированное ветвление, дающее альтернативное определение этого отношения и используемое системой после того, как было применено первое отношение. Следует подчеркнуть, что в определении участвуют оба правила. В общем случае число правил не ограничено.
Упражнения.
- В электронике известно понятие «стандартный ряд номинальных значений сопротивлений»: 10, 11, 12, 13, 15, 16, 18, 20 22, 24, 27, ЗС, 33, 36, 39, 43, 47, 51, 56, 62, 68, 75, 82, 91. Любое сопротивление, выпущенное промышленностью, имеет номинал, кратный элементам указанного ряда. Напишите базу знаний, в которой описывается этот ряд.
- Опишите на языке Пролог-Д состав своей семьи.
- Составьте базу знаний, описывающую республики, входящие в состав СССР.
- Напишите на языке Пролог-Д таблицу умножения чисел от 1 до 10. Какое количество предложений требуется для записи этой базы знаний?
Арифметические и другие встроенные предикаты в Прологе-Д
Системы логического программирования, к числу которых относится и Пролог-Д, не предназначены для вычислений. Традиционный для Пролога-Д подход при выполнении арифметических действий дан в упражнении 4 из предыдущего раздела. Однако для определения таким образом всех математических действий памяти компьютера будет явно недостаточно. Поэтому традиционные действия, связанные с выполнением арифметических операций, осуществляются посредством специальных, так называемых встроенных предикатов.
В системе Пролог-Д
БК-0010 для выполнения арифметических действий предусмотрен один встроенный арифметический предикат:
Код:
ВЫЧ(Арг1,Арг2,АргЗ,Арг4)
В системе Пролог-Д
MSX для выполнения арифметических действий предусмотрены два встроенных арифметических предиката:
Код:
УМНОЖЕНИЕ(Арг1,Арг2,АргЗ,Арг4)
СЛОЖЕНИЕ(Арг1,Арг2,АргЗ)
Встроенный предикат ВЫЧ (в MSX УМНОЖЕНИЕ) имеет четыре аргумента (целых; переменных, конкретизированных целыми; неконкретизированных переменных). ВЫЧ (в MSX УМНОЖЕНИЕ) обеспечивает реализацию формулы
Предикаты предусматривают обратимость аргументов и полностью покрывают арифметические операции в области целых чисел, предусмотренных синтаксисом входного языка (0 <= <число> <= 65535 «Электроника БК-0010» и -32766 <= <число> <= 32766 в системе MSX). Если результат дробный, он округляется до целого. Оба предиката могут быть использованы только в качестве цели в предложении.
Предикат СЛОЖЕНИЕ (Арг1,Арг2,АргЗ) обеспечивает реализацию формулы
Следующая база знаний на языке Пролог-Д показывает, как можно описать любые арифметические операции в системе Пролог-Д
БК-0010:
Код:
сложение(X,Y,Z)<-ВЫЧ(1,X,Y,Z);
вычитание(X,Y,Z)<-ВЫЧ(1,X,Z,Y);
умножение(X,Y,Z)<-ВЫЧ(X,Y,0,Z);
деление(X,Y,Z)<-ВЫЧ(Y,Z,0,X);
Во всех четырех случаях X, Y - операнды операций, a Z - результат. Например, СЛОЖЕНИЕ (X, Y, Z) реализует арифметическую операцию Z=X+Y.
Аналогично в системе Пролог-Д
MSX:
Код:
вычитание(X,Y,Z)<-УМНОЖЕНИЕ(1,X,Z,Y);
умнож(X,Y,Z)<-УМНОЖЕНИЕ(X,Y,0,Z);
деление(X,Y,Z)<-УМНОЖЕНИЕ(Y,Z,0,X);
Обратите внимание, вычитание можно определить в MSX и иначе:
Код:
вычитание(X,Y,Z)<-СЛОЖЕНИЕ(Y,Z,X);
Более подробное описание синтаксиса встроенных арифметических предикатов ВЫЧ, УМНОЖЕНИЕ, СЛОЖЕНИЕ приведено в технических описаниях трансляторов.
Пример 1. На Прологе-Д опишем вычисление площади прямоугольника, имеющего стороны длиной a и b: S=a*b. Соответствующий предикат должен иметь три аргумента - длины сторон и величину площади. Имя предиката должно отражать его назначение, этому критерию удовлетворит имя «площадь». В системе Пролог-Д БК-0010:
Код:
умножение(X,Y,Z)<-ВЫЧ(X,Y,0,Z);
площадь(a,b,S)<-умножение(a,b,S);
Первый предикат «умножение» потребовалось определить для наглядности записи. Необходимо отметить, что предикат «площадь» обратим, это означает, что, пользуясь этим описанием, можно вычислить не только площадь по заданным сторонам, но и любую (одну) сторону по другой стороне и площади. Перед базой знаний можно поставить вопрос:
Ответ системы Пролог-Д: S=200
Ответ системы Пролог-Д: а=5
В системе Пролог-Д
MSX:
Код:
умнож(X,Y,Z)<-УМНОЖЕНИЕ(X,Y,0,Z);
площадь(a,b,S)<-умнож(a,b,S);
Пример 2. На Прологе-Д необходимо описать вычисление объема параллелепипеда высотой h, в основании которого прямоугольник, имеющий стороны длиной a и b: V=a*b*h. Соответствующий предикат должен иметь четыре аргумента - длины сторон a, b, высоту h и объем V.
В системе Пролог-Д
БК-0010:
Код:
умножение(X,Y,Z)<-ВЫЧ(X,Y,0,Z);
объем(a,b,h,V)<-умножение(a,b,S),умножение(S,h,V);
Как и прежде, предикат «объем» обратим, это означает, что, используя это описание, можно вычислить не только объем по заданным сторонам и высоте, но и любую (одну) сторону или высоту по высоте, стороне и объему.
Можно иначе записать объем, если воспользоваться формулой V=Sz. Эту базу знаний предлагается написать самостоятельно.
Перед данной базой знаний можно поставить вопрос:
Ответ системы Пролог-Д: V=1000
В системе Пролог-Д
MSX:
Код:
умнож(X,Y,Z)<-УМНОЖЕНИЕ(X,Y,0,Z);
объем(a,b,h,V)<-умнож(а,b,S),умнож(S,h,V);
Наряду с арифметическим предикатом в системе БК-0010 существуют два предиката БОЛ и НЕ.
Встроенный предикат БОЛ (Арг1,Арг2) предназначен для сравнения двух целых констант или переменных. Он имеет два аргумента (целых или переменных конкретизированных целыми). Оба аргумента к моменту выполнения должны быть определены. Если эти требования не выполнены, то появится сообщение об ошибке: «Функция не может быть выполнена (ошибка 34)». Предикат выполнен, если Арг1>Арг2, иначе не выполнен.
Несмотря на то что предикат БОЛ один, его достаточно для описания всех возможных предикатов для сравнения числовой информации: равенство - «равно», меньше - «меньше», меньше и равно - «мир» и т. д. Это показывает база знаний, приведенная ниже.
Код:
равно(X,X);
меньше(X,Y)<-БОЛ(Y,X);
мир(X,Y)<-НЕ(БОЛ(X,Y)) ;
В последнем предложении использован встроенный предикат НЕ, его синтаксис:
Он имеет один аргумент, который обязательно должен быть предикатом. Предикат НЕ выполнен тогда и только тогда, когда предикат-аргумент не выполнен.
А теперь несложный пример, иллюстрирующий применение БОЛ и НЕ.
Пример 3. Опишите на языке Пролог-Д вычисление функции Хевисайда, определяемую формулой:
h(x)=0, если x<=0;
h(x)=1, если x>0.
База знаний должна содержать описание предиката «меньше и равно», который выше уже был описан; предикат, выполняющийся при вычислении функции Хевисайда, будет называться «хевисайд». Этот предикат будет иметь два аргумента: первый - аргумент функции, второй - ее значение. Предикат «хевисайд» определяется через два альтернативных описания для обоих значений х.
Код:
мир(X,Y)<-НЕ(БОЛ(X,Y);
хевисайд(X,0)<-мир(X,0);
хевисайд(X,1)<-БОЛ(X,0);
Перед этой базой знании можно поставить различные вопросы.
Ответ системы Пролог-Д: Х=1
В системе Пролог-Д MSX существует полный набор предикатов сравнения, их имена БОЛЬШЕ, МЕНЬШЕ, РАВНО.
Еще один, последний, встроенный предикат - «отсечение», предназначенный для управления логическим выводом. Этот предикат потребуется для решения следующих проблем:
- ограничения количества найденных решений;
- нахождения некоторого особенного решения задачи;
- ограничения объема поиска с целью повышения эффективности работы системы.
Предикат «отсечение» обозначается восклицательным знаком !. Это традиционное обозначение отсечения в системах логического программирования. Если данный предикат использовать в качестве цели в предложении, то полученный при этом эффект можно проиллюстрировать дверью, через которую можно пройти только слева направо, но нельзя вернуться назад через эту дверь. Роль двери выполняет символ !. Как известно, система Пролог-Д будет пытаться выполнять цели предложения в порядке просмотра слева направо начиная от символа <-, от первой до последней цели. Если какая-либо цель оказывается невыполненной, то осуществляется возврат и делается попытка найти альтернативные решения. Отсечение ограничивает возможность поиска альтернатив с того момента, как была просмотрена цель, обозначенная символом !. Например, если не выполнены цели А,Б,В, возврат для нахождения альтернативных решений в предложении
Код:
пример<-А,Б,В,!,Г,Д,Е;
возможен, а если не выполнены цели Г, Д или Е, то уже нет. Рубикон при движении слева направо перейден.
Необходимо отметить важность этого предиката, особенно при описании задач, допускающих множественные решения.
Иллюстрация предиката «отсечение» на примере базы знаний «мама». Действительно, у человека не может быть две матери, поэтому, определив для данного человека имя матери, необходимо прекратить дальнейшие поиски.
Код:
мама(Наташа,Петя)<-!;
мама(Наташа,Ваня)<-!;
мама(Оля,Лена)<-!;
мама(Катя,Даша)<-!;
мама(Люда,Сережа)<-!;
мама(Лена,Костя)<-!;
Перед базой знаний может быть поставлен вопрос
Ответ системы Пролог-Д:
Код:
х=Наташа
ДРУГИХ РЕШЕНИЙ НЕТ
После отыскания первого решения поиск альтернатив не производится. Что будет, если убрать во всех предложениях предикаты отсечения?
Упражнения.
- Опишите на языке Пролог-Д вычисление площадей геометрических фигур: трапеции, треугольника, параллелограмма.
- Опишите вычисление площади круга и длины окружности. Какова точность вычислений этих величин? Можно ли вычислить радиус круга по длине окружности?
- На языке Пролог-Д напишите базу знаний, в которой определяется функция, заданная соотношением:
F(x)=x², если x<1,
F(x)=x+1, если -1<=x<1,
F(x)=x², если x>1.
Какие сложности могут возникнуть в базе знаний о мамах, если у двух мам дети будут тезками? - Предположим, что дана программа на Прологе-Д:
Код:
ff(xx);
ff(x)<-pp(xx),ff(x);
Каким должен быть предикат рр(х), чтобы система нашла одно решение; бесконечно много решений?
Рекурсия
Существует огромное количество задач, в которых отношения между объектами можно определить, только используя сами определяемые соотношения. При этом получаются правила, называемые рекурсивными. Применение рекурсии для списания задач при работе с системами логического программирования - широко распространенный прием.
Рекурсия будет проиллюстрирована несколькими примерами построения программ, как вычислительных, так и логических.
Первым примером будет пример вычисления наибольшего общего делителя (НОД) двух чисел. Предикат, который выполняется, если найден НОД двух данных чисел, будет иметь имя «нод» и три аргумента: числа a, b и значение НОД - c. Для описания вычисления НОД используются следующие соображения:
если a=b, то c=a=b;
если a>b, то необходимо вычислить НОД для чисел b и a-b;
если b>а, то необходимо вычислить НОД для чисел a и b-a.
Эти три утверждения естественным образом могут быть записаны на Прологе-Д в системе
БК-0010.
Код:
нод(a,a,a);
нод(a,b,c)<-БОЛ(a,b),вычитание(a,b,d),нод(b,d,c);
нод(a,b,c)<-БОЛ(b,a),вычитание(b,a,d),нод(a,d,c);
вычитание(X,Y,Z)<-ВЫЧ(1,Y,Z,X);
Если перед этой базой знаний поставить вопрос
то система Пролог-Д ответит:
Код:
x=5
ДРУГИХ РЕШЕНИЙ НЕТ
Предикат «нод» оказывается обратимым.
В системе Пролог-Д
MSX последняя строка базы знаний запишется иначе:
Код:
вычитание(X,Y,Z)<-СЛОЖЕНИЕ(Y,Z,X);
а предикат БОЛ необходимо заменить на БОЛЬШЕ. Других изменений нет.
В качестве второго примера рассмотрим задачу о вычислении элементов последовательности 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... известной как последовательность Фибоначчи. Каждый ее элемент определяется следующими правилами:
f(0)=0,
f(1)=1,
f(n)=f(n-1)+f(n-2)
Первая формула утверждает, что значение нулевого элемента последовательности равно нулю. Это можно записать в виде факта
Вторая утверждает, что первый элемент равен 1. На Прологе-Д это можно записать так:
Третья формула представляет собой запись рекурсивного соотношения, переписываемого так:
Код:
Фб(N,X)<-БОЛ(N,1),вы(N,1,M),вы(N,2,K),Фб(M,Y),Фб(K,Z),сл(Y,Z,X);
«вы» и «сл» - имена предикатов «вычитание» и «сложение», определенных с помощью правил
Код:
сл(X,Y,Z)<-ВЫЧ(1,X,Y,Z);
вы(X,Y,Z)<-ВЫЧ(1,Y,Z,X);
в системе
БК-0010. Использование таких обозначений объясняется тем, что длина одной строки в редакторе системы Пролог-Д БК-0010 не должна превышать 64 символов.
Данные предложения представляют собой базу данных на языке Пролог-Д, позволяющую вычислять значения элементов последовательности. На вопрос
система Пролог-Д ответит:
Код:
X=21
ДРУГИХ РЕШЕНИЙ НЕТ
Поиск числа Фибоначчи с порядковым номером более 8 невозможен в БК-0010 из-за ограниченной памяти, поэтому рекомендуется первым предложением базы знаний написать
Код:
Фб(N,Y)<-БОЛ(N,8),!;
Необходимо сказать, что такой путь решения данной задачи не самый лучший. Для нахождения N+1 числа Фибоначчи требуется 2(N+1)-1 рекурсивное обращение. Однако этого можно избежать, если перейти к другой базе знаний, в которой предикат с именем «Фиб» определен как имеющий три аргумента, включающий в себя в качестве аргумента значения N-го и N-1-го элементов последовательности. Запишем эту базу знаний.
- Нулевой элемент последовательности равен нулю, а «минус первый» не определен:
в данном случае значение X может быть любым. - Первый элемент последовательности равен 1, а нулевой - 0:
- Для остальных элементов:
Код:
Фиб(N,F,f)<-БОЛ(N,1),вы(N,1,M),Фиб(M,Ф,F),сл(Ф,F,f);
Обращение к этой базе знаний будет иметь вид:
Ответ системы Пролог-Д:
Код:
F=55,
f=34
ДРУГИХ РЕШЕНИЙ НЕТ
При работе с этой базой знаний для вычисления N-го числа Фибоначчи необходимо всегда лишь N рекурсивных обращений.
Для системы Пролог-Д характерна особенность, проявляющаяся при работе с рекурсивными программами. В общем случае порядок предложений в базе знаний не имеет значения. Однако в нижеследующем примере эго не так.
Код:
родитель(X)<-родитель(Y),отец(Y,Z);
родитель(Коля);
отец(Коля,Петя);
родитель(Петя);
В первом предложении голова имеет то же имя, что и одна из целей - «родитель». В процессе поиска ответа в этой базе знаний будет применено правило «предложение, стоящее первым, будет и применено первым», известное как принцип поиска в глубину. Это приведет к тому, что система будет обращаться только к первому предложению базы знаний и ответ на вопрос
не будет найден никогда. Вместе с тем небольшое изменение базы знаний, перестановка двух предложений, приводит к удачному поиску решения:
Код:
родитель(Коля);
родитель(X)<-родитель(Y),отец(Y,X);
отец(Коля,Петя);
?родитель(Петя);
Неограниченно-повторное обращение к предложению может быть и более замаскированным, как это получается в примере:
Код:
выше(A,B)<-ниже(B,A);
ниже(B,A)<-выше(A,B);
выше(Коля,Петя);
?ниже(Петя,Коля);
Однако если третье предложение стоит на первом месте, то повторного обращения не произойдет и ответ будет найден. Такая ситуация называется петлей.
При вычислении элементов последовательности Фибоначчи может появляться бесконечная петля при исполнении программы. В самом деле, если вопрос имеет вид
то первый возможный результат
x=0,
y=1
Далее в попытке отыскать следующее решение возникает бесконечная петля так как будет отыскиваться
Фиб(-1,x,y), Фиб(-2,…),…
Для контроля за подобной ситуацией необходима модификация базы знаний.
Первые два предложения должны быть записаны в виде
Код:
Фиб(0,x,1)<-!;
Фиб(1,1,1)<-!;
тогда при поиске альтернативного решения после получения ответа на вопрос:
Код:
?Фиб(0,x,y);
х=0
у=1
будет получен результат: БОЛЬШЕ РЕШЕНИЙ НЕТ. Данный пример иллюстрирует первое возможное использование предиката «отсечение».
Еще одно, чисто эстетическое предложение. База знаний на Прологе-Д будет выглядеть лучше, если предложения с одинаковыми именами расположены в одном месте. Для сравнения приводятся две базы знаний:
1.
Код:
мама(Таня,Надя);
бабушка(X,Y)<~мама(X,Z),мама(Z,Y);
мама(Надя,Катя);
2.
Код:
мама(Таня,Надя);
мама(Надя,Катя);
бабушка(X,Y)<—мама(X,Z),мама(Z,Y);
Упражнения.
- Написать базу знаний, описывающую вычисление факториала.
- Написать базу знаний, описывающую вычисление суммы чисел натурального ряда.
- Написать базу знаний, описывающую вычисление суммы квадратов чисел натурального ряда.
- Описать вычисление наименьшего общего кратного.
- Написать базу знаний, описывающую известную притчу «У попа была собака, он ее убил. Она съела кусок мяса, он ее убил, на могиле написал...» и т. д. Как сделать, чтобы эта база знаний не содержала петли?
- Написать базу знаний, описывающую сказку о репке, которую тянут-потянут, а вытянуть не могут.
[свернуть]
