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

При помощи задания верхних значений можно строить простейшие базы данных (Е. М. Воробьёв [1, с. 146]). В примере на рис. 10.4 мы создаём базу данных о галилеевых спутниках Юпитера. Мы задаём информацию о массе спутника как верхнее значение выражения Mass[satname], где satname — название спутника (Io, Callisto, Europa и Ganymede), а также о размерах спутника и дате открытия — верхние значения выражений Dimension[satname] и OpeningDate[satname], соответственно. Теперь узнать информацию о спутнике satname можно, задав выражение ?satname. В примере In[13] на рис. 10.4. мы выводим данные о спутнике Ганимед, введя ?Ganymede.

Подробней о присвоении верхних значений см. книгу Е. М. Воробьёва [1, с. 145–148].

Есть в Mathematica и понятие нижних значений, которое тесно связанно с хорошо известными нам по предыдущей лекции пользовательскими функциями.

В примере In[1] на рис. 10.5 зададим функцию DoubSqr, возводящую в квадрат заданное выражение и удваивающую полученный результат. Теперь DoubSqr[expr] для любого выражения expr будет заменяться выражением 2 expr2 (пример In[2]). Это правило преобразования и будет составлять одно из так называемых нижних значений заголовка DoubSqr.

С любым заголовком можно ассоциировать любое количество нижних значений (Е. М. Воробьёв [1, с. 142]). Например, если мы хотим, чтобы при значении expr, равном 0, функция DoubSqr давала значение 1, зададим нижнее значение выражению с заголовком DoubSqr и аргументом 0 — пример In[3] на рис. 10.5.

Вывести на экран нижние значения, ассоциированные с заголовком arbhead, можно, применив к нему функцию DownValues. Е. М. Воробьёв [1, с. 143] отмечает, что если заголовок ассоциирован с несколькими нижними значениями, то Mathematica будет применять правила преобразований в том порядке, в котором они даны в DownValues: более частные правила предшествуют более общим. Именно поэтому в нашем примере выражение DoubSqr[0] при вычислении даст результат 1, а не 0 — пример In[4] на рис. 10.5.

Теперь попробуем изменить порядок присваивания нижних значений. Присвоим сначала некоторому выражению CubSqrt[4] значение 1000, а затем зададим пользовательскую функцию CubSqrt[x_], возводящую выражение в аргументе в степень 3/2 — примеры In[5] и In[6] на рис. 10.5. В примере In[7] при помощи функции DownValues ознакомимся со списком нижних значений выражения CubSqrt: в Out[7] мы найдём значения, заданные как в In[6], так и в In[5].

Если одному и тому же выражению последовательно присваивается несколько нижних значений (пример In[8] на рис. 10.5), то окончательно присвоенным оказывается то, которое присваивалось позже остальных (пример In[11]).

Подробней о присвоении нижних значений см. книгу Е. М. Воробьёва [1, с. 142–144].

10.1.2. Локальные правила преобразования

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

Локальными вариантами функций немедленного присваивания Set и отложенного присваивания SetDelayed являются функции Rule и RuleDelyed. Их инфиксные формы выглядят как " -> " и " :> ", соответственно. Ещё две инфиксные формы задания этих функций выглядят соответственно как " \to " и " :\to ", и ввести их можно, пользуясь палитрой. Кроме того, в последних версиях Mathematica введённое с клавиатуры выражение -> автоматически преобразовывается в " \to ", а " :> " — в " :\to ". С функцией Rule в инфиксной форме мы уже имели дело, когда в предыдущих лекциях знакомились с опциями функций.

Как мы уже знаем, если в тексте программы мы воспользуемся функцией Set[x,y], то во всех выражениях, содержащих символ x, он будет заменён символом y. Если же в тексте программы мы воспользуемся функций Rule[x,y] (пример In[1] на рис. 10.6), то никаких замен, связанных с символом x, ни в одном выражении не произойдёт (пример In[2]). Для того чтобы всё-таки осуществить замену в некотором выражении, нужно воспользоваться функцией ReplaceAll, указав в качестве её аргументов это самое выражение и необходимую локальную замену. Если, например, в выражении x^2+x+1 мы хотим заменить символ x выражением a+b, то мы задаём соответствующую функцию в следующей форме: ReplaceAll[x^2+x+1,Rule[x,a+b]] (пример In[3]). Функция ReplaceAll также имеет инфиксное представление, которое задаётся как " /. ". Итак, функцию из предыдущего примера можно задать следующим образом: $$x^2+x+1/.x->a+b$$ (пример In[4]).

Выражения, содержащие локальные правила преобразования, также имеют собственный порядок вычислений, описанный П. Веллином и др. в [14, с. 165]. В случае немедленной замены при использовании функции Rule порядок вычислений следующий. Сначала полностью вычисляется выражение, выступающее в качестве первого аргумента функции ReplaceAll (или находящееся слева от инфиксного выражение " /. "). Затем вычисляются выражения в левой и правой частях правил преобразования (второго аргумента функции ReplaceAll или стоящего справа от " /. "). В самом конце выражения в левой части правил, содержащиеся в первом аргументе функции ReplaceAll, заменяются выражениями в правой части правил. Порядок расчёта можно проследить при помощи уже известной нам функции Trace.

В примере In[1] на рис. 10.7 мы задаём некоторое выражение $$(m+n)^2$$, представляем его в полиномиальном виде, и осуществляем замену символов m и n выражениями Sin[2.] и Cos[2.], соответственно. В том же примере мы знакомимся с тем фактом, что к одному и тому же выражению мы можем применять одновременно несколько правил преобразований: в этом случае они должны быть оформлены в виде списка. В примере In[2] мы применяем функцию Trace к выражению в In[1]. По результату, содержащемуся в Out[2], можно поэтапно проследить, что Mathematica делает с исходным выражением на каждом этапе:

В случае отложенной замены (функция RuleDelayed) вычисление выражений в правой части правил преобразований осуществляется после подстановки, то есть, пункты 2 и 4 представленного выше перечня следуют после пункта 7. Это также легко пронаблюдать при помощи функции Trace — см. пример In[4] на рис. 10.7.

Правила преобразования могут применяться к символам, причём нигде не оговорено, какую роль в тексте программы эти символы должны выполнять. В предыдущих примерах мы применяли замену к символам, являющимся переменными в некотором выражении. Однако преобразуемый символ может являться и заголовком выражения. В примере In[1] на рис. 10.8 мы преобразуем полином в список входящих в него слагаемых, заменяя символ Plus, задающий сумму выражений, символом List, задающим список. Обратный пример преобразования списка в сумму его элементов приведён в книге П. Веллина и др. [14, с. 166].

В примере 10.7 мы уже познакомились с возможностью применения к выражению одновременно нескольких правил преобразований: для этого правила оформляются в виде списка. Следует учесть, что эффект параллельного применения правил отличается от последовательного, когда каждое новое правило применяется при помощи отдельной функции ReplaceAll. В примере In[2] на рис. 10.8 мы одновременно применили к выражению $$a*x^2+x*a^2$$ правила преобразования $$a->x$$ и $$x->y$$, а в примере In[3] — последовательно. Результаты вычислений Out[2] и Out[3] разительно отличаются друг от друга. Объясняется это достаточно просто: если в первом случае (в примере In[2]) оба правила, и a->x, и x->y, применяются к исходному выражению $$a*x^2+x*a^2$$, то во втором (в примере In[3]) к нему применяется только правило $$a->x$$, а правило $$x->y$$ применяется к результату предыдущей замены, то есть, к уже изменённому выражению.

Зачастую в процессе вычисления некоторого выражения каждое новое преобразование, подразумевающее замену некоторого символа expr1 символом expr2, приводит к новому выражению, вновь содержащему expr1. Если задачей ставится окончательно избавиться от expr1 в исходном выражении, заменив его выражением expr2, можно прибегнуть к многократному применению правил преобразования. Функция ReplaceRepeated, заданная в виде ReplaceRepeated[initaxpr,rules], будет до тех пор применять правила rules, пока получаемое в результате выражение не перестанет изменяться. Инфиксная форма функции ReplaceRepeated в Mathematica — " //. ". В примере In[4] на рис. 10.8 мы воспользовались многократным преобразованием некоторого выражения, а в примере In[5] для сравнения применили однократное преобразование. Как мы видим, в результате вычислений Out[5] по-прежнему содержится символ q, для которого задавалось правило, а в Out[4] символов, требующих замены не осталось.

Однако следует быть осторожным при работе с функцией ReplaceRepeated: некоторые правила преобразования могут вызывать принципиальную невозможность точного выполнения функции. Так в примере In[6] на рис. 10.8 мы пытаемся заменить содержащийся в исходном выражении символ t выражением, которое также содержит этот символ, тем самым, ввергая программу в бесконечную рекурсию. В результате мы получаем сообщение о том, что операция преобразования была выполнена 65536 раз и после этого остановлена, а выходная ячейка Out[6] содержит результат применения правила преобразования 65536 раз.

Подробней о локальных правилах преобразований см. книги Е. М. Воробьёва [1, с. 141, 158–162] и П. Веллина и др. [14, с. 164–167].

10.2. Шаблоны

10.2.1. Использование шаблонов в глобальных правилах преобразования

В Mathematica, согласно А.Н. Прокопене и А.В. Чичурину [5, с. 89], "шаблоном является выражение, содержащее символ подчёркивания "_"(выражение Blanc[])". С подобными выражениями мы уже встречались в предыдущей лекции, посвящённой функциональному программированию, когда учились задавать пользовательские функции.

Е. М. Воробьёв [1, с. 148] весьма точно определяет назначение шаблонов: "В принципе шаблоны используются для выделения классов выражений "Математики"".

Самый широкий класс выражений очерчивает самый простой шаблон, состоящий только из одного символа подчёркивания " _ ". Этому классу соответствуют абсолютно все выражения Mathematica.

Можно объединить в один класс выражения, обладающие определённым заголовком head: для этого задаётся шаблон вида _head. Для того чтобы задать шаблон для действительных чисел, следует записать _Real, а чтобы выделить в отдельный класс все символьные выражения — задать _Symbol.

Для того чтобы определить, относится ли то или иное выражение expr к классу данных, задаваемому некоторым шаблоном pat, следует воспользоваться функцией MatchQ[expr,pat]: она возвращает значение True, если выражение expr соответствует шаблону pat, и значение False — если не соответствует.

В примере In[1] на рис. 10.9 мы проверяем на принадлежность классу данных, задаваемых шаблоном " _ ", ряд выражений различных типов данных. Как мы видим в Out[2], все они соответствуют данному шаблону. В примере In[2] для проверки мы задаём новый шаблон вида _Complex, описывающий комплексные числа, а в In[3] — _List для поиска списков.

Заголовок head не обязательно должен быть стандартным выражением Mathematica. Для иллюстрации этого факта воспользуемся примером, аналогичным приведённому в книге П. Веллина и др. [14, с. 152] — см. пример In[4] на рис. 10.9: в качестве шаблона мы задаём выражение _g, где g — заголовок неопределённой функции, а затем проверяем ряд выражений на соответствие этому шаблону.

Для иллюстрации следующей особенности задания шаблонов воспользуемся примером, приведённым в работе Е. М. Воробьёва [1, с.149] — см. In[1] на рис. 10.10. Очевидно и для пользователя, и для программы, что выражение x^3 соответствует шаблону _Symbol^_Integer. В математике любое целое число (в нашем примере показатель степени 3) можно представить как сумму двух других целых чисел. Поэтому у пользователя может возникнуть предположение, что приведённое выражение должно соответствовать и шаблону _Symbol^(_Integer+_Integer). Но в этой ситуации Mathematica не согласна с пользователем, поскольку, как справедливо пишет Е. М. Воробьёв [1, с. 149], она "сравнивает внутренние полные формы выражения и шаблона, а не устанавливает их математическую эквивалентность".

Шаблоны вида " _ " и _h являются анонимными: первый, как мы уже знаем, описывает абсолютно любые выражения, а второй задаёт ограничение по заголовку выражения. Однако для большей конкретизации критериев соответствия шаблону и, соответственно, сужения класса выражений может возникнуть необходимость прибегнуть к именованным шаблонам, которые задаются в виде symb_, где symb — некоторый символ. Проиллюстрируем разницу между шаблонами _Symbol и Symbol_ в примерах In[2] и In[3] на рис. 10.10. Мы воспользовались новой функцией Cases, которая, будучи заданной в виде Cases[{expr1,expr2,…},patts], выбирает из списка выражений {expr1,expr2,…} только те, которые соответствуют шаблонам patts. В обоих примерах (In[2] и In[3]) мы предоставляем для проверки соответствия шаблонам один и тот же список выражений {g^h,g^g,h^h,h^g,f[y]^f[y]}, но получаем (в Out[2] и Out[3], соответственно) совершенно разные результаты.

В первом примере (In[2]) при отборе играют роль два ключевых критерия.

Во-первых, отбираются только те выражения, и в основании, и в показателе степени которых содержатся выражения с заголовком Symbol: именно поэтому не функцией Cases игнорируется выражение f[y]^f[y], поскольку оба заголовка есть f.

Во-вторых, совершенно не имеет значения, совпадают выражения в основании и показателе степени (g^g,h^h) или нет (g^h,h^g): в обоих случаях выражения оказываются соответствующими шаблону.

Во втором примере Symbol определяет не требуемый для соответствия заголовок, а попросту указывает на присутствие некоторого выражения, поэтому никакого несоответствия в выражении f[y]^f[y] функция Cases не находит. Однако другой критерий задаёт необходимость того, чтобы выражения в основании и показателе степени были одинаковыми, поскольку в обеих частях шаблона используется одно и то же выражение Symbol_. Именно поэтому не проходят проверку на соответствие выражения g^h и h^g, и отбираются в результирующий список выражения g^g и h^h.

Подробней о шаблонах см. книги Е. М. Воробьёва [1, с. 148–151] и П. Веллина и др. [14, с. 151–153].

Для задания шаблонов могут использоваться выражения, содержащие два и три символа подчёркивания, — " __ " и " ___ ". Их внутренние представления имеют, соответственно, следующий вид: BlankSequence[] и BlankNullSequence[]. Таки шаблоны оказываются необходимыми и эффективными при работе со списками.

Выражение вида h__, то есть, содержащее двойное подчёркивание, очерчивает класс выражений, состоящих из одного или более выражений с заголовком h, разделённых запятыми.

Выражение вида h___ (содержащее тройное подчёркивание) очерчивает класс выражений, состоящих из нуля или более выражений с заголовком h, также разделённых запятыми.

Проиллюстрируем действие шаблонов с двойным и тройным подчёркиванием на примере, аналогичном приведённому в работе П. Веллина и др. [14, с. 153–154]. Пусть мы имеем двухуровневый вложенный список {{a,b},{c},{d,e},{},{f,g,h}}, элементами которого являются списки, содержащие от нуля до трёх элементов. В примере In[1] на рис. 10.11 при помощи функции Cases мы выберем из этого списка элементы, соответствующие шаблону x_, в примере In[2] — шаблону y__, a в примере In[3] — шаблону z___. В первом примере в результирующий список Out[1] попало только одно выражение, представляющее собой список, содержащий один элемент. Во втором примере результирующий список оказался значительно шире: помимо выражения {c}, отобранного и в предыдущем примере, в него также попали списки с двумя и тремя элементами. В последнем примере результирующий список оказался полностью идентичен исходному, поскольку помимо выражений, содержащихся и в Out[2], в него попали и пустые списки {}, проигнорированные в обоих предыдущих примерах.

Подробней о шаблонах с двумя и тремя подчёркиваниями см. книги Е. М. Воробьёва [1, с. 149–150] и П. Веллина и др. [14, с. 153–156].

10.2.2. Задание шаблонов с условиями

В предыдущих разделах мы научились задавать правила преобразований и шаблоны для выделения класса выражений, соответствующих значениям гладких математических функций, таких, как правило преобразования, удваивающее квадрат заданного выражения в примере In[1] на рис. 10.5, и шаблон для функций вида xa в примерах на рис. 10.10. Пусть некоторая функция f(x) переменной x принимает значения f1(x) при x<0, значение 0 при x=0 и значения f2(x) при x>0. Для того чтобы задать правило преобразования для такой функции, используют функцию постановки условий Condition. Задаётся эта функция в виде Condition[rppatt,cond], где rppatt — правая часть правила преобразования при условии cond. Так для нашей предполагаемой функции f(x) при условии x<0 правило устанавливается следующим образом: f[x_]:=Condition[f1[x],x<0]. Функция Condition имеет также инфиксную форму " /; ", и задание правила для функции f(x) будет выглядеть как f[x_]:=f1[x]/;x<0. Безусловно, операции сравнения требуют, чтобы участвующие в них выражения были числами.

На рис. 10.12 приведено несколько примеров задания правил преобразований с условиями. В In[1] мы отдельно задаём правила преобразования для отрицательных и неотрицательных значениях аргумента. Если аргумент y функции g[y_] примет отрицательное значение (например, -2, как в первом элементе списка In[3]), то будет найден его синус (-Sin[2]), если нулевое или положительное (например, 1) — косинус (Cos[1]). Поскольку для случая, если аргумент y не является числом (k), никаких условий не указано, к выражению никаких правил преобразований применяться не будет, и оно будет переписано в исходном виде с указанным аргументом (g[k]).

В примере In[4] мы выбираем из некоторого списка выражений только те, показатель степени которых чётный. Для этого мы, во-первых, задаём шаблон для выбора выражений со степенью, _^x_, и во-вторых, задаём условие для отфильтровывания нечётных степеней, EvenQ[x].

Подробней о шаблонах с условиями см. книги Е. М. Воробьёва [1, с. 152–153] и П. Веллина и др. [14, с. 156–159].

10.2.3. Задание шаблонов-альтернатив

Если имеется некоторый набор шаблонов, и требуется проверить, соответствует ли то или иное выражение хотя бы одному из них, используются так называемые шаблоны-альтернативы, которые П. Веллин и др. [14, с. 159] определяет как выражения вида patt1|patt2|..., где patt1,patt2,... — независимые шаблоны.

На рис. 10.13 приведём ряд примеров, аналогичных примерам в работе (П. Веллин и др. [14, с. 160]), которые иллюстрируют возможности применения шаблонов-альтернатив. В примере In[1] мы проверяем, представляет ли собой выражение a^5 символ а, возведённый в целочисленную степень либо символ а, возведённый в вещественную степень. Для полноты иллюстрации в In[2] мы проводим такие же манипуляции с выражением a^5.1. В результате обоих вычислений, как и ожидалось, мы получаем True. В примерах In[3] и In[4] мы проверяем те же выражения на соответствие шаблону "символ a, возведённый в целую или вещественную степень", то есть, задаём альтернативу не для полной формы выражения, а только для показателя степени. В примере In[5] из списка разнотипных данных мы выбираем только те элементы, которые являются целыми или рациональными числами.

Подробней о шаблонах-альтернативах см. книгу П. Веллина и др. [14, с. 159–161].

10.2.4. Использование шаблонов в локальных правилах преобразования

Использование шаблонов в локальных правилах преобразований подробно комметирует Е. М. Воробьёв в своей книге [1, с. 158–162]. Как мы помним из пункта 10.1.2, локальные правила преобразования задаются выражениями вида exprl->expr2 и exprl:>expr2. В настоящем пункте мы научимся задавать локальные правила преобразования, содержащие в выражении expr1 шаблоны. Для этого воспользуемся примером, аналогичным, приведённому в книге Е. М. Воробьёва [1, с. 159–160]. Применим к представляющему собой список выражению {m,n} три разных набора правил подстановки. В примере In[1] на рис. 10.14 зададим правила {m->a,n->b}. Результат преобразований Out[1] достаточно очевиден: m заменено на a, n — на b. В примере In[2] добавим к имеющимся ещё одно правило {m,n}->c. Результирующее выражение Out[2] отличается от Out[1], поскольку последнее правило замены, как оказалось, гораздо больше соответствует преобразуемому выражению.

Теперь попробуем осуществить ту же замену при помощи шаблонов. Для этого в примере In[3] на рис. 10.14 зададим правило замены в виде {x_,y_}->c.

Как мы выяснили в примерах In[1] и In[2] на рис. 10.14, в случае, если к некоторому выражению применено несколько правил преобразования, не содержащих шаблоны, то в первую очередь выполняется то, которое больше соответствует изменяемому выражению. Определим, какое из правил будет выполняться, если они содержат шаблоны. В примере In[4] применим к тому же выражению {m,n} набор правил преобразований {{x_,x_}->c,{_,_}->d}. Хотя исходное выражение соответствует обоим шаблонам, преобразование было выполнено по правилу {x_,x_}->c. В примере In[5] поменяем местами правила преобразований в наборе, т.е., зададим {{_,_}->d,{x_,x_}->c}. Результат в Out[4] показывает, что в данном случае была осуществлена замена по другому правилу, {_,_}->d. Следовательно, если изменяемое выражение соответствует нескольким шаблонам в правилах преобразований, выполняется то правило, которое указано раньше остальных.

Специфическим образом осуществляется вычисление функции многократного применения локальных правил преобразований ReplaceRepeated с шаблонами. Эта специфика доступно пояснена в книге Е. М. Воробьёва [1, с. 160]: "…ее [функции ReplaceRepeated] вычисление сводится к повторному вычислению функции ReplaceAll до тех пор, пока ни одно из подвыражений преобразуемого выражения не удается преобразовать в соответствии с хотя бы одним шаблоном списка. При этом порядок применения шаблонов следующий. Первый шаблон списка используется, пока в преобразуемом выражении находится хотя бы одно подвыражение, ему соответствующее. Затем применяется второй шаблон списка и т.д. Ни в коем случае не следует думать, что каждый раз применяется более чем один шаблон списка".

На рис. 10.15. приведён пример также из книги Е. М. Воробьёва [1, с. 160], иллюстрирующий действие функции ReplaceRepeated. Первый шаблон списка был применён дважды: в результате исходное выражение было сведено к одноэлементному списку {а}. Затем к полученному на предыдущем этапе выражению был применён третий шаблон. Второй шаблон не использовался ни разу, хотя на одном из этапов преобразования и получалось соответствующее ему выражение. После применения третьего шаблона результирующее выражение a оказывается несоответствующим ни одному указанному шаблону, и вычисления прекращаются.

Ключевые термины

Верхнее значение выражения — это правило преобразования, ассоциированное с находящимся на первом уровне выражения элементом этого выражения.

Глобальным называется правило преобразования, которое осуществляет заданное преобразование во всём тексте программы.

Локальным называется правило преобразования, которое осуществляет заданное преобразование в отдельном фрагменте программы.

Нижнее значение выражения — это правило преобразования, ассоциированное с заголовком выражения независимо от его элементов на нижних уровнях.

Шаблоном является выражение, содержащее символ подчёркивания (выражение Blanc[]).

Краткие итоги

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

Вопросы

Упражнения