Книга: Программирование на языке Пролог для искусственного интеллекта

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

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

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

Терм =.. L

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

?- f( а, b) =.. L.
L = [f, а, b]
?- T =.. [прямоугольник, 3, 5].
T = прямоугольник( 3, 5)
?- Z =.. [p, 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)
А = а
В = b

а не

F = f( a, v + v)
А = а + 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м1, Терм2)

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

?- включает( X, с).
yes
?- включает( g( X), g( t( Y))).
yes
?- включает f( X,X), f( a,b)).
no

Оглавление книги