Упражнения. 7.1. Напишите процедуру упростить для упрощения алгебраических сумм, в которых участвуют числа и символы (строчные буквы)

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

?- упростить(1 + 1 + а, E).

E = а + 2

?- упростить(1 + a + 4 + 2 + b + с, E).

E = а + b + с + 7

?- упростить(3 + x + x, E).

E = 2*x + 3

7.2. Определите процедуру

добавить(Элемент, Список)

для добавления нового элемента в список. Предполагается, что все элементы, хранящиеся в списке, — атомы. Список состоит из всех хранящихся в нем элементов, а за ними следует хвост, который не конкретизирован и служит для принятия новых элементов. Пусть, например, в списке уже хранятся а, b и с, тогда

Список = [а, b, с | Хвост]

где Хвост — переменная. Цель

добавить(d, Список)

вызовет конкретизацию

Xвoст = [d | НовыйХвост] и

Список = [а, b, с, d | НовыйХвост]

Таким способом структура может наращиваться, включая в себя новые элементы. Определите также соответствующее отношение принадлежности.

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) символов, входящих в состав атома А.