Структуры

Структурированными объектами (или структурами) называются объекты, ко­торые имеют несколько компонентов. Сами компоненты, в свою очередь, также мо­гут быть структурами. Например, дата может рассматриваться как структура с тре­мя компонентами: число, месяц, год. Несмотря на то что структуры состоят из не­скольких компонентов, они рассматриваются в программе как целостные объекты. Для соединения компонентов в целостный объект необходимо выбрать функтор. В данном примере подходящим функтором является date. Например, дату "1 мая 2001 года" можно записать следующим образом (рис. 2.2):

date £ 1, may, 2001)

date date{ 1, may, 2001)

/l\ /\l/

May 2001 функтор параметры

A) 6J

Рис. 2.2. Дата как пример структурированно­го объекта: а) представяснногов виде дерева; б) рассматриваемого в той записи, которая применяется в языке Prolog

В этом примере все компоненты (два целых числа и один атом) являются кон­стантами. Компоненты могут также представлять собой переменные или другие структуры. Объект, который обозначает любое число мая, можно представить в виде следующей структуры: date! Day, may, 2001}

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

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

Часть I. Язык Prolog

С точки зрения синтаксиса все объекты данных в языке Prolog представляют со­бой термы. Например, термами являются объекты may и datef I, may, 2001)

Все структурированные объекты можно представить графически в виде деревьев (см. рис. 2.2). Корнем дерева является функтор, а ветвями - компоненты. Если компонент представляет собой структуру, он становится поддеревом этого дерева, ко­торое соответствует всему структурированному объекту.

В следующем примере показано, как могут использоваться структуры для пред­ставления некоторых простых геометрических объектов (рис. 2.3). Точка в двухмер­ном пространстве определена двумя своими координатами; отрезок прямой определен двумя точками, а треугольник можно определить тремя точками. Предположим, что выбраны следующие функторы:

• point, для обозначения точек;

• sест, для обозначения отрезков прямых;

• triangle, для обозначения треугольников.

5 ■

(6,4)

4i

А ■

Р2 = (2,Э]

⁸' /

а ■ у (4,2)

Р1 = (1,1)

Рис, 2.3. Некоторые простые геометриче­ские объекты

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

PI - point (1,1) Р2 - point(2,3! S = seg< PI, Р2) = seg( pointd.l), point<2,3>)

T - ttiangle[ point(4,2), point(6,4). point (7,1))

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

Если бы в той же программе были также точки в трехмерном пространстве, то для их представления можно было бы использовать другой функтор, скажем, point3: point3( X, Y, Z!

Но допускается использовать одно и то же имя, в данном случае point, для точек в двух- и в трехмерном пространстве и, например, записывать: point; xi, YD и point: X, Y, Z)

Если одно и то же имя встречается в программе в двух разных ролях, как в при­веденном выше случае с функтором point, система Prolog определяет различие меж­ду ними по количеству параметров и интерпретирует само это имя как два функтора,

Глава 2. Синтаксис и значение программ Prolog

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

1. Имя, которое имеет такую же синтаксическую структуру, как

2. Арность, т.е. количество параметров.

и атомы.

Р1 = point

S = seg

Point

Point

/\ /\

T = triangle

Point

Pnrnl

Potirt

Рис, 2.4, Древовидное представление объектов, пока-занныхна рис. 2.3

Как было описано выше, все структурированные объекты в языке Prolog пред­ставляют собой деревья, которые отображаются л программе с помощью термов. Рас­смотрим еще два примера для иллюстрации того, как можно естественным образом представить с помощью термов Prolog сложные объекты данных. На рис. 2.5 показа­на древовидная структура, которая соответствует следующему арифметическому вы­ражению: (а + Ь) ' (с - 5)

Рис. 2.5. Древовидная структу­ра, соответствующая, арифме­тическому выражению(а + Ь)

* (с - 5)

В соответствии с синтаксисом термов, описанным выше, это выражение можно за­писать, используя символы "-", "+ " и "-"в качестве функторов, следующим образом:

* ( .+ [ а, Ь) , - ( с, 5) )

Это, безусловно, допустимый терм Prolog, но обычно такая форма записи вряд ли является приемлемой. Люди, как правило, предпочитают использовать общеприкя-

Часть I. Язык Prolog

тую инфиксную систему обозначений, которая широко распространена в математике. В действительности язык Prolog также позволяет применять инфиксную систему обозначений таким образом, чтобы символы "-", "+ " и "-" записывались как ин­фиксные знаки операций. Подробные сведения о том, как программист может опре­делить свои собственные операции, приведены в главе 3.

В качестве последнего примера рассмотрим некоторые простые электрические схемы (рис. 2.6). Справа на этом рисунке показаны древовидные представления соот­ветствующих схем, Атомы rl, г2, гЗ и г4 представляют собой имена резисторов, а функторы par z seq обозначают параллельные и последовательные соединения рези­сторов. Ниже перечислены соответствующие термы Prolog.

seq< rl, r2)

par( rl, r2>

par( rl, par( r2, r3)1

par( rl, se<jts»rir2,x3),r4!)

Seq

--><

/\

rl

R2

Par

v,

R2

I1

RZ

Par

/\

R1 par

/\

F2 r3

/\

Seq

/\

Par r4

i?

ГЗ

Рис.. 2.6. Примеры простых электрических схем. и их древовидных представлений:а) последователь­ное соединение резисторов rl и z2; б) параллель нос соединение двух резисторов; в) параллельное соединение трех резисторов; г) параллельное со­единение резистора rl и еще одной схемы

Глава 2. Синтаксис изначение программ Prolog