Назад | Содержание| Вперёд 7. 2. Создание и декомпозиция термов: =.., ...

Назад | Содержание| Вперёд

7. 2. Создание и декомпозиция термов: =.., functor, arg, name

Имеются три встроенные предиката длядекомпозиции и синтеза термов: functor, argи =.. . Рассмотрим сначала отношение =.., которое записывается как инфиксный оператор.Цель

Терм =.. L

истинна, если L - список, начинающийся с главногофунктора терма Терм, вслед за которымидут его аргументы. Вот примеры:

?- f( а, b) =.. L.

L = [f, а, b]

?- Т =..[прямоугольник, 3, 5].

Т = прямоугольник( 3, 5)

?- Z =.. [р, X, f( X,Y) ].

Z = p( X, f( X,Y) )

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

Рассмотрим программу, которая манипулируетгеометрическими фигурами. Фигуры - это квадраты,прямоугольники, треугольники, окружности в т.д. Впрограмме их можно представлять в виде термов,функтор которых указывает на тип фигуры, ааргументы задают ее размеры:

квадрат( Сторона)

треугольник( Сторона1,Сторона2, Сторона3)

окружность( R)

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

увел( Фиг,Коэффициент, Фиг1)

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

увел( квадрат( A), F,квадрат( А1) ) :-

A1 is F*A

увел( окружность( R),F, окружность( R1) ) :-

R1 is F*R1

увел(прямоугольник( А, В), F, прямоугольник( А1, В1)) :-

A1 is F*A, B1 is F*B.

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

Ниже приводится программа, в которой делаетсяпопытка (неудачная) справиться для начала хотя бысо всеми однопараметрическими фигурами припомощи одного предложения:

увел( Тип( Пар), F,Тип( Пар1) ):-

Пар1 is F*Пар.

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

увел( Фиг, F, Фиг1):-

Фиг =.. [Тип | Параметры],

умножспис( Параметры, F, Параметры1),

Фиг1 =.. [Тип | Параметры)].

умножспис( [ ], _, [ ]).

умножспис( [X | L], F, [X1| L1] ) :-

X1 is F*X, умножспис( L, F, L1).

Наш следующий пример использования предиката'=..' связан с обработкой символьных выражений(формул), где часто приходится подставлять вместонекоторого подвыражения другое выражение. Мыопределим отношение

подставить(Подтерм, Терм, Подтерм1, Терм1)

следующим образом: если все вхождения Подтерм'ав Терм заменить на Подтерм1, тополучится Терм1. Например:

?- подставить( sin(x), 2*sin( x)*f( sin( x)), t, F ).

F = 2*t*f( t)

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

?- подставить( а+b,f( а, А+В), v, F).

даст результат

F = f( а, v) F = f( a, v+v)

А = а а не А = а+b

В = b В = а+b

При определении отношения подставитьнам нужно рассмотреть несколько случаев и длякаждого принять свое решение:

если Подтерм = Терм,то Терм1 = Подтерм1;

иначе если Терм -"атомарный" (не структура),

то Терм1 = Терм (подставлятьнечего),

иначе подстановку нужно выполнить над

аргументами Tерм'a.

Эти правила можно превратить в программу,показанную на рис. 7.3.

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

получить( Функтор),

вычислить( Списарг),

Цель =.. [Функтор | Списарг],

Цель

Здесь получить и вычислить -некоторые определенные пользователем процедуры,предназначенные для вычисления компонент цели.После этого цель порождается предикатом '=..', азатем активизируется при помощи простогоуказания ее имени Цель.

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

% Отношение

% подставить( Подтерм, Терм, Подтерм1,Терм1)

% состоит в следующем: если всевхождения Подтерм'а в Терм

% заменить на Подтерм1, то получитсяТерм1.

% Случай 1: Заменить весь терм

подставить( Терм,Терм, Терм1, Терм1) :- !.

% Случай 2: нечего подставлять

подставить( _, Терм,_, Терм) :-

atomic( Терм), !.

% Случай 3: Проделать подстановку варгументах

подставить( Под,Терм, Под1, Терм1) :-

Терм =.. [F | Арги],

% Выделить аргументы

подспис( Под,Арги, Под1, Арги1),

% Выполнить над ними подстановку

Терм1 =.. [F |Арги1].

подспис( Под, [Терм |Термы], Под1, [Терм1 | Термы1]) :-

подставить( Под, Терм, Под1, Терм1),

подспис( Под, Термы, Под1, Термы1).

Рис. 7. 3. Процедураподстановки в терм вместо одного из его

подтермов некоторого другого подтерма.

зависимости от ее текущей конкретизации, можетпо своей синтаксической форме не подойти вкачестве

цели. Эту трудность можнообойти при помощи еще одного встроенногопредиката

call

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

. . .

Цель = [Функтор | Списарг],

саll( Цель)

Иногда нужно извлечь из терма только егоглавный функтор или один из аргументов. В этомслучае можно, конечно, воспользоватьсяотношением '=..' Но более аккуратным и практичным,а также и более эффективным

способомбудет

применение одной из двух новыхвстроенных процедур:

functor

аrg

. Вот их смысл: цель

functor(Терм, F, N)

истинна, если F - главный функтор Tepм'a,а N -арность F. Цель

arg( N, Терм, А)

истинна, если А - N-й аргумент в Терм'е,в предположении, что нумерация аргументов идетслева направо и начинается с 1. Примеры дляиллюстрации:

?- functor( t( f( x), X, t),Фун, Арность).

Фун = t

Арность = 3

?- аrg( 2, f( X, t( a), t( b)), Y).

Y = t( a)

?- functor( D, дата, 3),

arg( 1, D, 29),

arg( 2, D, июнь),

arg( 3, D, 1982).

D = дата( 29, июнь, 1982)

Последний пример иллюстрирует особый случайприменения предиката functor. Цель functor(D, дата, 3) создает "обобщенный" терм сглавным функтором дата и тремяаргументами. Этот терм обобщенный, так как всетри его аргумента - не конкретизированныепеременные, чья имена генерируются пролог -системой. Например:

D = дата( _5, _6, _7)

Затем эти три переменные конкретизируются припомощи трех целей аrg.

К рассматриваемому

множествувстроенных предикатов относится также ивведенный в гл. 6 предикат

name

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

name( A, L)

истинна, если L - список кодов (в кодировке ASCII)символов, входящих в состав атома А.

Упражнения

7. 3. Определите предикат конкрет(Терм)так, чтобы он принимал значение истина, когда в Tepм'eнет ни одной неконкретизированной переменной.

7. 4. Процедура подставитьиз данного раздела производит, при наличииразных вариантов, лишь самую "внешнюю"подстановку.

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

?- подставить( a+b,f( A+B), новый, НовыйТерм).

А = а

В = b

НовыйТерм = f( новый);

А = а+b

В = а+b

НовыйТерм = f( новый +новый)

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

7. 5.

Определитеотношение

включает(Tepмl, Терм2)

которое выполняется, если Терм1является более общим, чем Терм2.Например:

?- включает( X, с).

yes

?- включает( g( X), g(t( Y))).

yes

?- включает f( X,X),f( a,b)).

Назад | Содержание| Вперёд

Оглавление