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

При работе с правопрошитым деревом уже необязательно применять стек во время выполнения этого алгоритма. С другой стороны, недостаток подобного представления дерева заключается в том, что необходимо делать копии поддеревьев. Например, в правиле для D{u f v) потребуется трижды копировать и н v, тогда как в.место дерева можно было бы испальзовать представление в виде Списка из раздела 2.3.5 и избежать такого котгирования.

Алгоритм D {Дифференцирование). Если Y.- адрес заголовка списка, который указывает на формулу, представленную в описанном выше виде, а DY-адрес заголовка списка для пустого дерева, то в результате выпо.лнения этого алгоритма NODE(DY) будет указывать на дерево, представляющее производную от Y по X. Dl. [Инициализация.] Установить Р <- Ys (а именно, первый узел дерева при обходе в обратном порядке, который является первым узлом соответствующего бинарного дерева в симметричном порядке). D2. [Дифференцирование.] Установить Р1 <- LLINK(P) и. если Р1 ф Л, также установить (}1 <- RLINK(Pl). Затем вьшолнить описанную ниже программу DIFFtTYPE(P)]. (Программы DIFF[0] DIFF[1] и т. д. вычисляют производную дерева с корнем Р и задают для указательной переменной Q значение адреса корня этой производной. Чтобы упростить спецификацию програ.мм DIFF, прежде всего следует установить пере.менные Р1 и Q1.) D3. [Восстановление связи.] Если TYPE(P) обозначает бинарный оператор, установить RLINK(Pl) <- Р2. (Пояснение дается ниже, при описании следующего шага.)

D4. [Продвижение к Р$.] Установить Р2 <- Р, Р <- Р$. Теперь, если RTAG(P2) = О (т. е. если N0DE(P2) имеет справа брата или сестру), установить RLINK(P2) Ц. (Именно здесь и заключена суть этого алгоритма: структура дерева Y временно разрзшается так, чтобы сохранить для дальнейи1его использования связь с производной Р2. Недостающая связь будет восстановлена позднее, па шаге D3. Более подробное описание этой уловки приводится в упр. 21.) D5. [Обход завершен?] Если Р Y, вернуться к шагу D2. В противном случае установить LLINK(DY) -(- Q и RLINK(Q) <- DY, RTAG(Q) <- 1. Программа, описанная в алгоритме D, является общей программой операций дифференцирования, непосредственно выполняемых программами DIFF[0], DIFF[1]. которые вызываются на шаге D2. Во многом алгоритм D напоминает программу управления интерпретирующей системы (или компилятор), кото1)ая рассмотрена в разделе 1.4.3, но совершает обход дерева, а не простой последовательности инструкций.

Для завершения алгоритма D необходимо определить программы, которые непосредственно вьшолняют дифс])еренцирование. Далее утверждение "Р указывает на дерево" будет означать, что узел NODE(P) является корнем дерева, которое хранится в памяти компьютера в виде правопрошитого бинарного дерева, хотя оба указателя RLINK(P) и RTAG(P) утрачивают смысл при работе с таким деревом. Вос-пользуе.мся функцией конструирования деревьев {tree constiiictioii furictwu). которая

позволяет создавать новые деревья за счет объединения деревьев меньшего размера. Пусть X обозначает узе*л некоторого типа, содержащий константу, переменную или оператор, а U и V обозначают указатели на деревья. В таком случае

TREE (ж. и, V) образует новое дерево с корнем х и поддеревьями U и V этого корня: W AVAIL, INFO(W) -(- х, LLINK (W) -(- U, RLINK(U) V, RTAG(U) -(- 0, RLINK(V) <r- W, RTAG(V) i- 1;

TREE (ж, U) аналогично образует новое дерево только с одним поддеревом: W -Ф= AVAIL, INFO(W) -(- X, LLINK(W) (- U, RLINK(U) <- W, RTAG(U) <- 1;

TREECz) образует новое дерево с корнем х, который является концевым узлом: W AVAIL, INFO(W) <- х. LLINK(W) -(- Л.

Кроме того, для TYPE(W) задается значение, соответствующее типу узла х. Во всех случаях значением TREE является W, т. е. указатель на только что построенное дерево. Читателю следует тщательно изучить эти определения, поскольку они иллюстрируют представление дерева на основе бинарного дерева. Еще одна функция. COPY(U), создает копию дерева, на которое указывает U, а ее значением является указатель на только что созданное дерево. Основные функции TREE и COPY упрощают процесс поэтапного создания дерева, соответствующего производной для заданной формулы.

Нуль-арные операторы (константы и переменные). Для этих операций узел NODE(P) является концевым, а значения переменных Р1, Р2, Q1 и Q для их вьтолнения несущественны.

DIFFCO]: (NODE(Р)-константа.) Установить Q <-TREE(0).

DIFFC1]: (NODE(Р)-переменная.) Если INFO(P) = "X", установить Q -е-TREE(l): в противном случае установить Ц TREE(O).

Унарные операторы (логарифм и отрицание). Для этих операций NODE(P) имеет одного ребенка. U. на которого указывает Р1, а Q указывает на D(U). Значения переменных Р2 и Ц1 для выполнения этих операций несущественны.

DIFFC2]: (NODE(P) -"In".) Если INF0(Q)70, установить Q-(-TREE("/".Q, COPY(Pl)).

DIFFtS]: (NODE(P) - "neg".) Если INFO(Q) Ф 0, установить Q <- TREE("neg" ,Q).

Бинарные операторы (сложение, вычитание, умножение, деление, возведение в степень). Для этих операций NODE(P) имеет двух детей, U и \\ на которых указывают Р1 и Р2 соответственно; Q1 и Q указывают на D(U) и D(V) соответственно.

DIFFC4]: (Операция .) Если INFO(Ql) = О, установить AVAIL Q1. В противном случае, если INFO(Q) = О, установить AVAIL Q и Q <- Q1; иначе - установить Q TREE("-b".Ql,Q).

DIFF[5]: (Операция "-".) Если INFO(Q) = О, установить AVAIL Q и Q -(- Q1. В противном случае, если INF0(Q1)=0, установить AVAIL-t=Ql и Q(-TREE("neg",Q); иначе - установить Q TREE ("-", Q1, Q).

DIFF[6]: (Операция "х".) Если INFO(Ql) ф О, установить Q1 -(- MULT(Q1, C0PY(P2)). Затем, если INFO(Q) ф О, установить Q -(- MULT(C0PY(P1) ,Q). После эюю перейти к выполнению программы DIFF [4].

Здесь MULT (и, V) является новой функцией, которая создает дерево для U х V и проверяет, не равны ли U или V единице:

если INFO(U) = 1 и TYP:(U) = О, установить AVAIL <!= U и MULT(U,V) -(- V; если INFO(V) = 1 и TYPE(V) = О, установить AVAIL <!= V и MULT(U,V) 4- U; в противном случае установить MULT(U,V) <- TREECx" ,U, V).

DIFF[7]: (Операция "/".) Если INFO(Ql) ф О, установить Q1 -(- TREE(7",Q1,C0PY(P2)). Затем, если INFO(Q) ф О, установить

Q 4- TREE(7".MULT(C0PY(Pl),Q),TREE("t", COPY(P),TREE(2))). После этого перейти к выполнению программы DIFF [5]. DIFF [8]: (Операция "f.) См. упр. 12.

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

Программа D (Дифференцирование). Приведенная ниже программа на языке MIXAL реализует алгоритм D с такими значениями регистров гИ = Р, г13 = Р2, г14 = Р1, г15 = Q, г16 = Q1. Для удобства порядок вычислений немного изменен. 001 * ДИФФЕРЕНЦИРОВАНИЕ В ПРАВОПРОШИТОМ ДЕРЕВЕ