Программирование, основанное на правилах преобразований

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

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

Чтобы было понятно, как это делается, предположим, что в системе MATHEMATICA нет встроенной функции Log[a, x] и построим ее с помощью следующих правил – аксиом:

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

Убеждаемся в том, что правила преобразований сработали ожидаемым образом. Если бы мы попытались запрограммировать эти правила обычным образом, программа получилась бы очень громоздкой.

Обратите внимание на то название построенной процедуры записано с прописной буквы, в отличие от встроенной функции, решающей ту же задачу.

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

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

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

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

Два типа глобальных присвоений (подстановок)

expr 1 = expr 2 выражение expr 2 вычисляется в момент

(непосредственное присвоения, и значение этого вычисления

присвоение) закрепляется за expr 1;

expr 1: = expr 2 expr 2 вычисляется заново каждый раз, когда

(отложенное запрашивается значение expr 1 (это удобно,

присвоение) когда некоторые параметры выражения expr 2

могут быть изменены в течение сеанса).

Два типа локальных присвоений (подстановок)

expr 1 –> expr 2 expr 2 вычисляется в момент задания

(непосредственная правила, но само правило применяется

локальная подстановка) локально, т. е. только внутри выражения F при помощи команды ReplaceAll:

ReplaceAll[F, expr 1 –> expr 2]

(или F/. expr 1 –> expr 2);

expr 1: > expr 2 expr 2 вычисляется в момент применения

(отложенная правила, и это правило применяется

локальная подстановка) локально с помощью той же команды

ReplaceAll.

Действие присвоения можно ограничить условиями с помощью функции Condition (краткая форма /;). Простенький пример.

На самом деле все не всегда так просто, но это уже на самостоятельное освоение.

Пример.

Задан сигнал с битональной АМ. Нужно построить векторную диаграмму соответствующего аналитического сигнала. Для этого, если Вы еще что-то помните из курса СПР, необходимо найти сигнал, сопряженный по Гильберту исходному. Это и сделано по правилам преобразований в программе, приведенной ниже.

Красиво получилось.

Для обобщенного представления выражений в системе MATHEMATICA разработано такое средство, как шаблоны (Patterns).

Шаблоны – это классы выражений системы MATHEMATICA. Самый общий шаблон имеет вид Blank[ ], или в краткой форме _ (символ подчеркивания). Он обозначает любое выражение MATHEMATICA, т. е. определяет класс всех возможных выражений системы. Каждое конкретное выражение в MATHEMATICA можно считать шаблоном, являющимся классом только этого выражения. Другие шаблоны занимают промежуточное положение по степени общности. Например, а + _обозначает все суммы, в которых одно из слагаемых равно а. Шаблоны можно именовать. Имя шаблона произвольный символ, стоящий впереди. Например: у _{– –} – любая последовательность из одного или более выражений, представленная именем у. Имя составного шаблона отделяется от этого шаблона двоеточием, например, z: _– + _–^2.

Выражению, задаваемому шаблоном, можно придать значение по умолчанию, которое будет ему присвоено при вычислениях, если среди аргументов вычисляемой функции не указано значение для этого шаблона. Делается это с помощью конструкции x_–: value.

Пример.

В следующей таблице приведены основные шаблоны системы MATHEMATICA.

_ любое выражение;

х_ любое выражение с именем х;

x: pattern шаблон pattern с именем х;

pattern? test все выражения, удовлетворяющие шаблону

pattern, для которых test принимает значение

True;

_h любое выражение с заголовком h;

x_h любое выражение с именем х, имеющее заголовок h;

_ _ любая последовательность из одного или более

выражений;

_ _ _ любая последовательность из нуля или более

выражений;

х_ _ и х_ _ _ последовательности выражений, представленные

именем х;

_ _h и _ _ _h последовательности выражений, имеющих

заголовок h;

х_ _h и х_ _ _h последовательности выражений с заголовком h, представленные именем х;

x_: v выражение со значением по умолчанию v;

x_h: v выражение с заголовком h и значением по

умолчанию v;

х_. выражение с глобально определенным

(встроенным) значением по умолчанию;

Optional[h, x] выражение, которое должно иметь заголовок h и глобально определенное значение по умолчанию;

pattern.. шаблон, повторяемый один или более раз;

pattern … шаблон, повторяемый нуль или более раз;

patt ₁| patt ₂ |… шаблон, который подходит хотя бы к одному

из шаблонов patt_i;

pattern /; cond шаблон, для которого вычисленное условие

cond дает True;

HoldPattern[ pattern ] невычисленный шаблон;

Verbatim[ expr ] задает шаблон, который должен быть в точности

вида expr, без замены входящих в него _, _ _ и

_ _ _ любыми выражениями

Все шаблоны, кроме последних двух, не требуют дополнительных пояснений, хотя поупражняться с ними нужно. Разберитесь с ними самостоятельно на собственных примерах. Соответствующие nb-файлы на дискетах сдадите мне. Дискеты верну.

Два последних рассмотрим на примерах.

Шаблон Verbatim полезен, когда нужно задать правило преобразований не над выражениями, а над шаблонами. Шаблону Verbatim[x_] будет подходить только х_. Чтобы это понять, сравните два следующих примера:

Для проверки соответствия выражений шаблонам имеется встроенная функция

MatchQ[ expr, pattern ] возвращает True, если выражение expr

соответствует шаблону pattern, и False – в

противоположном случае

Пример.

Результаты первых двух тестов понятны. С третьим – сходу не понять, нужны пояснения.

Дело в том, что выражение _*_, задаваемое как " составной" шаблон,

вычисляется системой в момент задания. При этом получается:

Теперь понятно, что выражение a*b не соответствует шаблону _². Система на это и отреагировала.

Шаблон HoldPattern предотвращает нежелательное вычисление. Тогда,

На этом краткое введение в технологию программирования, основанного на правилах преобразований, закончим (если что-то поняли и оценили, уже хорошо). Опять же кратко рассмотрим третий стиль программирования в системе MATHEMATICA.