Методические указания по языку «Пролог» (стр. 5 )

Дерево на рис.5.2.1 является неупорядоченным.

Рис.4.2.2. Упорядоченное бинарное дерево

Обратите внимание, что упорядочение приводит не к единствен­ному варианту представления множества с помощью дерева. Напри­мер, на рис.5.2.3 изображено то же множество, что и на рис.5.2.2.

Будем называть линейным представление такого вида, как на рис.5.2.3, и сбалансированным - такое, как на рис.5.2.2.

Моделирование принадлежности множеству. Имея множество, описанное бинарным деревом, мы можем моделировать принадлежность множеству с помощью целевого утверждения принадлежит_дереву. При этом используется оператор @ <, выражающий от­ношение «меньше, чем», и оператор @ >, выражающий отношение «больше, чем».

/* Граничное условие: X принадлежит

/* дереву, если X является корнем.

принадлежит_дереву(Х, бд(Лд, Х,Пд)).

/* Рекурсивные условия

/* X принадлежит дереву, если X больше

/* значения корня и находится в правом

/* поддереве:

принадлежит_дереву(Х, бд(Лд, Y,Пд)) :-

X@Y,

принадлежит_дереву (Х, Пд).

/* X принадлежит дереву, если X меньше

/* значения корня и находится в левом

/* поддереве:

принадлежит_дереву(Х, бд(Лд, Y,Пд)):-

X@Y,

принадлежит_дереву (Х, Лд).

Если множество из первых 1024 чисел описать с помощью сбалансированного бинарного дерева Т, то при ответе на запрос

?- принадлежит_дереву(3000,Т).

Пролог сравнит число 3000 не более чем с 11 элементами множества, прежде чем ответит:

нет

Конечно, если Т имеет линейное представление, то потребуется сравнение 3000 с 1024 элементами множества.

Построение бинарного дерева. Задача создания упорядоченного бинарного дерева при добавлении элемента X к другому упорядочен­ному бинарному дереву формулируется следующим образом:

Граничное условие:

Добавление X к nil дает бд(nil,Х,nil).

Рекурсивные условия:

При добавлении X к бд(Лд, К,Пд) нужно рассмотреть два случая, чтобы быть уверенным, что результирующее дерево будет упорядо­ченным.

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

2. X больше, чем К. В таком случае нужно добавить X к Пд, что­бы получить правое поддерево. Левое поддерево равно Лд, а значе­ние корня - К.

Такой формулировке задачи соответствует программа:

/* Граничное условие:

включ_бд(nil, Х,бд(nil, Х,nil)).

/* Рекурсивные условия:

/*(1)

включ_бд(бд(Лд, К,Пд),Х, бд(Лднов, К,Пд)) :-

Х@К,

включ_бд(Лд, Х,Лднов).

/*(2)

включ_бд(бд(Лд, К,Пд),Х, бд(Лд, К,Пднов)):-

Х@К,

включ_бд(Пд, Х,Пднов).

На запрос

?- включ_бд(nil, d,T1) ,включ_бд (Т1 ,а, Т2).

будут получены значения

T1=бд(nil, d,nil)

T2=бд(бд(nil, a,nil),d, nil)

Процедуру включ_бд() можно использовать для построения упо­рядоченного дерева из списка:

/* Граничное условие:

список_в_дерево([],nil).

/* Рекурсивное условие:

список_в_дерево([Н | Т],Бд) :-

список_в_дерево(Т, Бд2),

включ_бд(Н, Бд2,Бд).

Заметим, что включ_бд не обеспечивает построения сбалансиро­ванного дерева. Однако существуют алгоритмы, гарантирующие та­кое построение.

Создание отсортированного списка. Для построения отсортиро­ванного списка элементов воспользуемся упорядоченным бинарным деревом.

Граничное условие:

Пустое бинарное дерево (nil) приводит к пустому списку [].

Рекурсивное условие:

Отсортированный список для упорядоченного бинарного дерева бд(Лд, К,Пд), где Лд имеет отсортированный список СЛ, а Пд - отсортированный список СП, получается присоединением [К | СП] к СЛ.

Рассмотрим, например, упорядоченное бинарное дерево

бд(бд(бд(nil, alice, nil),fred, бд(nil, graham, nil)),

jim, бд(nil, ray, nil))

Левому поддереву соответствует отсортированный список

[alice, fred, graham]

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

[rау]

Следовательно, отсортированным списком для всего дерева будет

присоединить( [alice, fred, graham], [jim | ray] ,L)

что равно

[alice, fred, graham, jim, ray]

Используя процедуру присоединить (см. разд. 5.1.2), преобразу­ем приведенный алгоритм в утверждения Пролога:

дерево_в_список (nil, []).

дерево_в_список(бд(Лд, К,Пд),С) :-

дерево_в_список(Лд, СЛ),

дерево_в_список(Пд, СЛ),

присоединить (СЛ, [К | СП],С).

5 Операторы и структуры

В этой главе описывается связь операторов со структурами и из­лагаются способы объявления и использования операторов. Дается объяснение следующим трем свойствам операторов:

1) позиция;

2) приоритет;

3) ассоциативность.

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

Структура в Прологе образуется из атома, называемого главным функтором, и следующей за ним последовательности термов, назы­ваемых компонентами. Последовательность компонент заключается в круглые скобки. Между главным функтором и открывающей скоб­кой не должно быть пробела. Компоненту разделяются запятыми. Например, +(1,2) представляет собой структуру с главным функто­ром + и компонентами 1 и 2.

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

а) синтаксис операторов для структур, арность которых равна од­ному или двум;

б) синтаксис списков для структур в виде списков;

в) синтаксис строк для списков символов, записанных в кодах ASCII или EBCDIC.

В настоящей главе мы обсудим первую форму - синтаксис опера­торов. Структуры с арностью, равной одному или двум, могут быть переписаны в синтаксисе операторов посредством объявления глав­ного функтора структуры оператором с одним или двумя аргумента­ми. Компоненты структуры записываются как аргументы оператора.

Например, если + и - объявить системными операторами, то +(1,2) принимает вид 1+2, а-(1) записывается как -1.

Если арность структуры равна единице, оператор может быть объявлен как

а) префиксный оператор. В этом случае оператор записывается перед единственным аргументом ор А;

б) постфиксный оператор. В этом случае оператор записывает­ся после единственного аргумента А ор.

Если арность структуры равна двум, оператор может быть объяв­лен как инфиксный. В таком случае он записывается между двумя своими аргументами: А ор В.

Например, такие структуры, как

+(X, Y).

;(P, Q). (; обозначает 'или')

< (X, Y).

является_частью(А, В)

прошло(Р).

допускают общепринятую форму записи

X+Y.

P;Q.

X<Y.

А является_частью В.

Р прошло.

Максимальное число компонент в структуре операторного типа равно двум. Следует подчеркнуть, что синтаксис операторов исполь­зуется вместо обычного формата структур только для удобства.

Свойства операторов

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

Позиция оператора указывает, где он записывается по отноше­нию к своим аргументам.

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

Ассоциативность оператора показывает, какая операция вы­полняется первой в выражении, содержащем два или более операто­ра с одинаковым приоритетом.

Теперь мы поясним значение свойств и их использование в объ­явлении оператора.

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

Инфиксный - оператор располагается между двумя аргументами, например: X + Y или X < Y .

Префиксный - оператор располагается перед единственным аргументом, например: not X или - X.

Постфиксный - оператор располагается после единственного аргумента, например: X факториал или Р прошло

Каждый оператор имеет приоритетный номер, указываемый при объявлении оператора. Номер является целым числом и обычно '"' находится в пределах от 1 до 1500.

Если выражение содержит более одного оператора, например

X + Y*2,

то возникает неопределенность в порядке выполнения операций. Эта проблема разрешается посредством назначения всем операторам приоритетного номера. Вычисления осуществляются, начиная с оператора, имеющего наименьший номер, и заканчивая оператором с наибольшим номером. В нашем примере X + Y * 2 оператор * имеет более низкий приоритетный номер, чем оператор +. Поэтому, как и следовало ожидать, выражение вычисляется так: X + (Y * 2).

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

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

Рассмотрим выражение a/b/с. Результат его вычисления зависит от расстановки скобок:

(а/b)/с или а/(b/с)

Арифметические операции +, -(минус), * и / определены в Про­логе как левоассоциативные. Это означает, что они должны иметь слева операторы равного или низшего приоритета, а справа - опера­торы строго низшего приоритета.

Следовательно, приведенное выше выражение в соответствии с правилом можно вычислить только как (а/b)/с, а не как а/(b/с).

Позицию и ассоциативность оператора удобно задавать с по­мощью спецификатора. Перечислим виды спецификаторов:

fx для определения постфиксного оператора;

fy

xf для определения префиксного оператора;

yf

xfx для определения инфиксного оператора;

xfy " (правоассоциативногооператора);

yfx " (левоассоциативного оператора);

yfy

В такой форме записи приняты следующие соглашения:

f представляет оператор. Им может быть системный оператор или оператор, объявленный с помощью предиката ор;

х представляет выражение, содержащее операторы только ни­зшего приоритета по отношению к приоритету f;

у представляет выражение, которое может содержать операторы равного или низшего приоритета по отношению к приоритету f.

Если оператор объявлен со спецификатором yfx, то он является левоассоциативным и подвыражение у вычисляется первым. Возь­мем в качестве примера

5 + 4*10/5.

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

У f x

(5+4*10) / 5

(5+(4*10)) / 5

Следовательно, (5+(4*10))/5 равно 9, если использовать правило определения приоритета.

Если оператор объявлен со спецификатором xfy, то он является правоассоциативным и подвыражение у, стоящее справа, вычисляет­ся первым.

Спецификатор yfy недопустим в Прологе, так как выражения, содержащие операторы с такой ассоциативностью, окажутся неопре­деленными. Если бы * и / были объявлены со спецификаторами yfy, тогда выражение из предыдущего примера 5+4*10/5 можно было бы вычислить либо как прежде

(5+(4*10))/5=9,

либо как

5+(4*(10/5))=13

(суммирование + объявлено с большим приоритетом, чем * или /).

Применение спецификатора xfx в Прологе допустимо. Он ис­пользуется, например, при объявлении операторов сравнения, таких, как < и >. Обычно трудностей не возникает, так как для операторов < и > в Прологе определяется более высокий приоритет, чем для арифметических операторов. Следовательно, правая и левая части выражения должны быть вычислены до того, как будет произведена попытка выполнить функцию сравнения, например,

5+2 < 6+3

будет вычисляться как

(5+2)<(6+3)

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

Примером может служить выражение X opr Y opr Z, где оператор орr имеет позицию и ассоциативность xfx.

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

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

(a opr b) opr c.

Если * > объявлен как левоассоциативный, а < * - как правоассоциативный оператор с помощью управляющих команд (директив)

?-op(60,yfx,*>).

?-op(60,xfy,<*).

то выражение а*>b*>с вычисляется как (a*>b)*>c, a<*b<*c вычисля­ется как а<*(b<*с) и а<*b*>с вычисляется как (а<*b)*>с по умолча­нию.

Некоторые реализации Пролога в таких неясных случаях выдают сообщение об ошибке.

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

op(P, S,N)

Здесь Р - приоритет оператора, S - спецификатор, а N - имя ато­ма, который будет использоваться в качестве главного функтора в соответствующей структуре.

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

?-op(P, S,N).

Покажем на примере, как можно написать оператор для преобра­зования температуры по Цельсию в температуру по Фаренгейту. Сначала зададим предикат, который преобразует температуру С (по Цельсию) в температуру F (по Фаренгейту).

(consult) *

/* приглашение пользователю ввести предложение:

?- [user]

/* ввод предложения

:t(C, F) :- F is (C*9/5+32).

: $ /* окончание работы пользователя

Теперь объявим предикат t как инфиксный левоассоциативный оператор с приоритетом 100:

?-op(100,yfx, t).

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

Например:

tabulate(C, F) :- write(C),tab(3),C t F,

tab(3),write (F).

Обычно в реализации языка Пролог системные операторы, их позиция/ассоциативность и приоритет объявляются следующим обра­зом:

Имя	Спецификатор	Приоритет
:-	xfx	1200
?-	fx	1200
;	xfy	1100
,xfy	1000
spy	fx	900
nospy	fx	900
not	fx	800
.	xfy	750
=..	xfx	700
=	xfx	700
\=	xfx	700
is	xfx	700
=:=	xfx	700
=\=	xfx	700
<	xfx	700
= <	xfx	700
>	xfx	700
> =	xfx	700
==	xfx	700
\==	xfx	700
—	yfx	500
+	yfx	500
/	yfx	400
*	yfx	400
div	yfx	400
mod	xfx	300

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

В настоящей главе рассматриваются встроенные предикаты Про­лога, описываются способы обновления базы данных, вопросы вво­да/вывода и обработки файлов.