2.3.2 Example: Symbolic Differentiation

As an illustration of symbol manipulation and a further illustration of data abstraction, consider the design of a function that performs symbolic differentiation of algebraic expressions. We would like the function to take as arguments an algebraic expression and a variable and to return the derivative of the expression with respect to the variable. For example, if the arguments to the function are $ax^2 + bx +c$ and $x$, the function should return $2ax+b$. Symbolic differentiation is of special historical significance in the programming language Lisp.[1] It was one of the motivating examples behind the development of a computer language for symbol manipulation. Furthermore, it marked the beginning of the line of research that led to the development of powerful systems for symbolic mathematical work, which are today routinely used by applied mathematicians and physicists.

In developing the symbolic-differentiation program, we will follow the same strategy of data abstraction that we followed in developing the rational-number system of section 2.1.1. That is, we will first define a differentiation algorithm that operates on abstract objects such as sums, products, and variables without worrying about how these are to be represented. Only afterward will we address the representation problem.

The differentiation program with abstract data
抽象データを用いた微分プログラム

To keep things simple, we will consider a very simple symbolic-differentiation program that handles expressions that are built up using only the operations of addition and multiplication with two arguments. Differentiation of any such expression can be carried out by applying the following reduction rules:

\[ \begin{array}{rll} \dfrac{dc}{dx} & = & 0\quad \text{for $c$ a constant or a variable different from $x$} \\[12pt] \dfrac{dx}{dx} & = & 1 \\[12pt] \dfrac{d(u+v)}{dx} & = & \dfrac{du}{dx}+\dfrac{dv}{dx} \\[12pt] \dfrac{d(uv)}{dx} & = & u\left( \dfrac{dv}{dx}\right)+v\left( \dfrac{du}{dx}\right) \end{array} \]

Observe that the latter two rules are recursive in nature. That is, to obtain the derivative of a sum we first find the derivatives of the terms and add them. Each of the terms may in turn be an expression that needs to be decomposed. Decomposing into smaller and smaller pieces will eventually produce pieces that are either constants or variables, whose derivatives will be either $0$ or $1$.

To embody these rules in a function we indulge in a little wishful thinking, as we did in designing the rational-number implementation. If we had a means for representing algebraic expressions, we should be able to tell whether an expression is a sum, a product, a constant, or a variable. We should be able to extract the parts of an expression. For a sum, for example, we want to be able to extract the addend (first term) and the augend (second term). We should also be able to construct expressions from parts. Let us assume that we already have functions to implement the following selectors, constructors, and predicates:

`is_variable(e)`	Is `e` a variable? `e` は変数か？
`is_same_variable(v1, v2)`	Are `v1` and `v2` the same variable? `v1` と `v2` は同じ変数か？
`is_sum(e)`	Is `e` a sum? `e` は和か？
`addend(e)`	Addend of the sum `e`. 和 `e` の加数。
`augend(e)`	Augend of the sum `e`. 和 `e` の被加数。
`make_sum(a1, a2)`	Construct the sum of `a1` and `a2`. `a1` と `a2` の和を構成する。
`is_product(e)`	Is `e` a product? `e` は積か？
`multiplier(e)`	Multiplier of the product `e`. 積 `e` の乗数。
`multiplicand(e)`	Multiplicand of the product `e`. 積 `e` の被乗数。
`make_product(m1, m2)`	Construct the product of `m1` and `m2`. `m1` と `m2` の積を構成する。

Using these, and the primitive predicate is_number, which identifies numbers, we can express the differentiation rules as the following function:

function deriv(exp, variable) {
    return is_number(exp)
           ? 0
           : is_variable(exp)
           ? is_same_variable(exp, variable) ? 1 : 0
           : is_sum(exp)
           ? make_sum(deriv(addend(exp), variable),
                      deriv(augend(exp), variable))
           : is_product(exp)
           ? make_sum(make_product(multiplier(exp),
                                   deriv(multiplicand(exp),
                                         variable)),
                      make_product(deriv(multiplier(exp),
                                         variable),
                                   multiplicand(exp)))
           : error(exp, "unknown expression type -- deriv");
}

This deriv function incorporates the complete differentiation algorithm. Since it is expressed in terms of abstract data, it will work no matter how we choose to represent algebraic expressions, as long as we design a proper set of selectors and constructors. This is the issue we must address next.

Representing algebraic expressions
代数式の表現

We can imagine many ways to use list structure to represent algebraic expressions. For example, we could use lists of symbols that mirror the usual algebraic notation, representing $ax+b$ as list("a", "*", "x", "+", "b"). However, it will be more convenient if we reflect the mathematical structure of the expression in the JavaScript value representing it; that is, to represent $ax+b$ as list("+", list("*", "a", "x"), "b"). Placing a binary operator in front of its operands is called prefix notation, in contrast with the infix notation introduced in section 1.1.1. With prefix notation, our data representation for the differentiation problem is as follows:

The variables are just strings. They are identified by the primitive predicate is_string:
変数は単なる文字列です。プリミティブな述語 is_string で識別されます。
```
function is_variable(x) { return is_string(x); }
```
Two variables are the same if the strings representing them are equal:
2つの変数は、それらを表す文字列が等しい場合に同じです。
```
function is_same_variable(v1, v2) {
    return is_variable(v1) && is_variable(v2) && v1 === v2;
}
```

Sums and products are constructed as lists:

function make_sum(a1, a2) { return list("+", a1, a2); }

function make_product(m1, m2) { return list("*", m1, m2); }

A sum is a list whose first element is the string "+":
和は最初の要素が文字列 "+" であるリストです。
```
function is_sum(x) {
    return is_pair(x) && head(x) === "+";
}
```
The addend is the second item of the sum list:
加数は和リストの2番目の要素です。
```
function addend(s) { return head(tail(s)); }
```
The augend is the third item of the sum list:
被加数は和リストの3番目の要素です。
```
function augend(s) { return head(tail(tail(s))); }
```
A product is a list whose first element is the string "*":
積は最初の要素が文字列 "*" であるリストです。
```
function is_product(x) {
    return is_pair(x) && head(x) === "*";
}
```
The multiplier is the second item of the product list:
乗数は積リストの2番目の要素です。
```
function multiplier(s) { return head(tail(s)); }
```
The multiplicand is the third item of the product list:
被乗数は積リストの3番目の要素です。
```
function multiplicand(s) { return head(tail(tail(s))); }
```

Thus, we need only combine these with the algorithm as embodied by deriv in order to have a working symbolic-differentiation program. Let us look at some examples of its behavior:

deriv(list("+", "x", 3), "x");

list("+", 1, 0)

deriv(list("*", "x", "y"), "x");

list("+", list("*", "x", 0), list("*", 1, "y"))

deriv(list("*", list("*", "x", "y"), list("+", "x", 3)), "x");

list("+", list("*", list("*", "x", "y"), list("+", 1, 0)),
          list("*", list("+", list("*", "x", 0), list("*", 1, "y")),
                    list("+", "x", 3)))

The program produces answers that are correct; however, they are unsimplified. It is true that

\[ \begin{array}{lll} \dfrac{d(xy)}{dx} & = & x\cdot 0+1\cdot y \end{array} \]

but we would like the program to know that $x\cdot 0 = 0$, $1\cdot y = y$, and $0+y = y$. The answer for the second example should have been simply y. As the third example shows, this becomes a serious issue when the expressions are complex.

Our difficulty is much like the one we encountered with the rational-number implementation: we haven't reduced answers to simplest form. To accomplish the rational-number reduction, we needed to change only the constructors and the selectors of the implementation. We can adopt a similar strategy here. We won't change deriv at all. Instead, we will change make_sum so that if both summands are numbers, make_sum will add them and return their sum. Also, if one of the summands is 0, then make_sum will return the other summand.

function make_sum(a1, a2) {
    return number_equal(a1, 0)
           ? a2
           : number_equal(a2, 0)
           ? a1
           : is_number(a1) && is_number(a2)
           ? a1 + a2
           : list("+", a1, a2);
}

This uses the function number_equal, which checks whether an expression is equal to a given number:

function number_equal(exp, num) {
    return is_number(exp) && exp === num;
}

Similarly, we will change make_product to build in the rules that 0 times anything is 0 and 1 times anything is the thing itself:

function make_product(m1, m2) {
    return number_equal(m1, 0) || number_equal(m2, 0)
           ? 0
           : number_equal(m1, 1)
           ? m2
           : number_equal(m2, 1)
           ? m1
           : is_number(m1) && is_number(m2)
           ? m1 * m2
           : list("*", m1, m2);
}

Here is how this version works on our three examples:

deriv(list("+", "x", 3), "x");

deriv(list("*", "x", "y"), "x");

"y"

deriv(list("*", list("*", "x", "y"), list("+", "x", 3)), "x");

list("+", list("*", "x", "y"), list("*", "y", list("+", "x", 3)))

Although this is quite an improvement, the third example shows that there is still a long way to go before we get a program that puts expressions into a form that we might agree is simplest. The problem of algebraic simplification is complex because, among other reasons, a form that may be simplest for one purpose may not be for another.

Exercise 2.56

Show how to extend the basic differentiator to handle more kinds of expressions. For instance, implement the differentiation rule

\[ \begin{array}{lll} \dfrac {d(u^{n})}{dx} & = & nu^{n-1}\left( \dfrac{du}{dx}\right) \end{array} \]

by adding a new clause to the deriv program and defining appropriate functions is_exp, base, exponent, and make_exp. (You may use the string "**" to denote exponentiation.) Build in the rules that anything raised to the power 0 is 1 and anything raised to the power 1 is the thing itself.

function base(e) {
    return head(tail(e));
}
function exponent(e) {
    return head(tail(tail(e)));
}
function make_exp(base, exp) {
    return number_equal(exp, 0)
           ? 1
           : number_equal(exp, 1)
             ? base
             : list("**", base, exp);
}
function is_exp(x) {
    return is_pair(x) && head(x) === "**";
}
function deriv(exp, variable) {
    return is_number(exp)
           ? 0
           : is_variable(exp)
             ? (is_same_variable(exp, variable) ? 1 : 0)
             : is_sum(exp)
               ? make_sum(deriv(addend(exp), variable),
                          deriv(augend(exp), variable))
               : is_product(exp)
                 ? make_sum(make_product(multiplier(exp),
                                deriv(multiplicand(exp),
                                      variable)),
                            make_product(deriv(multiplier(exp),
                                               variable),
                                multiplicand(exp)))
                 : is_exp(exp)
                   ? make_product(make_product(exponent(exp),
                                      make_exp(
                                          base(exp),
                                          exponent(exp) - 1)),
			          deriv(base(exp), variable))
                   : error(exp, "unknown expression type -- deriv");
}

Exercise 2.57

Extend the differentiation program to handle sums and products of arbitrary numbers of (two or more) terms. Then the last example above could be expressed as

deriv(list("*", "x", "y", list("+", "x", 3)), "x");

Try to do this by changing only the representation for sums and products, without changing the deriv function at all. For example, the addend of a sum would be the first term, and the augend would be the sum of the rest of the terms.

function augend(s) {
    return accumulate(make_sum, 0, tail(tail(s)));
}
function multiplicand(s) {
    return accumulate(make_product, 1, tail(tail(s)));
}

Exercise 2.58

Suppose we want to modify the differentiation program so that it works with ordinary mathematical notation, in which "+" and "*" are infix rather than prefix operators. Since the differentiation program is defined in terms of abstract data, we can modify it to work with different representations of expressions solely by changing the predicates, selectors, and constructors that define the representation of the algebraic expressions on which the differentiator is to operate.

Show how to do this in order to differentiate algebraic expressions presented in infix form, as in this example:
中置形式で表現された代数式を微分するために、これをどのように行うか示しなさい。次の例のようにします。
```
list("x", "+", list(3, "*", list("x", "+", list("y", "+", 2))))
```
To simplify the task, assume that "+" and "*" always take two arguments and that expressions are fully parenthesized.
課題を簡単にするため、"+" と "*" は常に2つの引数を取り、式は完全に括弧付けされていると仮定しなさい。
The problem becomes substantially harder if we allow a notation closer to ordinary infix notation, which omits unnecessary parentheses and assumes that multiplication has higher precedence than addition, as in this example:
不要な括弧を省略し、乗算が加算より高い優先順位を持つと仮定する、通常の中置記法に近い表記を許可すると、問題はかなり難しくなります。次の例のようにします。
```
list("x", "+", 3, "*", list("x", "+", "y", "+", 2))
```
Can you design appropriate predicates, selectors, and constructors for this notation such that our derivative program still works?
この表記に対して適切な述語、セレクタ、コンストラクタを設計して、微分プログラムが引き続き動作するようにできますか？

function make_sum(a1, a2) {
    return number_equal(a1, 0)
           ? a2
           : number_equal(a2, 0)
             ?  a1
             : is_number(a1) && is_number(a2)
               ? a1 + a2
               : list(a1, "+", a2);
}
function is_sum(x) {
    return is_pair(x) && head(tail(x)) === "+";
}
function addend(s) {
    return head(s);
}
function augend(s) {
    return head(tail(tail(s)));
}
function make_product(m1, m2) {
    return number_equal(m1, 0) || number_equal(m2, 0)
           ?  0
           : number_equal(m1, 1)
             ? m2
             : number_equal(m2, 1)
               ?  m1
               : is_number(m1) && is_number(m2)
                 ? m1 * m2
                 : list(m1, "*", m2);
}
function is_product(x) {
    return is_pair(x) && head(tail(x)) === "*";
}
function multiplier(s) {
    return head(s);
}
function multiplicand(s) {
    return head(tail(tail(s)));
}
function deriv(exp, variable) {
    return is_number(exp)
        ? 0
        : is_variable(exp)
          ? (is_same_variable(exp, variable) ? 1 : 0)
          : is_sum(exp)
            ? make_sum(deriv(addend(exp), variable),
                       deriv(augend(exp), variable))
            : is_product(exp)
              ? make_sum(make_product(multiplier(exp),
                             deriv(multiplicand(exp),
                                   variable)),
                         make_product(deriv(multiplier(
                                                    exp),
                                            variable),
                                      multiplicand(exp)))
              : error(exp, "unknown expression type -- deriv");
}

function items_before_first(op, s) {
    return is_string(head(s)) && head(s) === op
           ? null
           : pair(head(s),
                  items_before_first(op, tail(s)));
}
function items_after_first(op, s) {
    return is_string(head(s)) && head(s) === op
           ? tail(s)
           : items_after_first(op, tail(s));
}
function simplify_unary_list(s) {
    return is_pair(s) && is_null(tail(s))
           ? head(s)
           : s;
}
function contains_plus(s) {
    return is_null(s)
           ? false
           : is_string(head(s)) && head(s) === "+"
             ? true
             : contains_plus(tail(s));
}
function make_sum(a1, a2) {
    return number_equal(a1, 0)
           ? a2
           : number_equal(a2, 0)
             ?  a1
             : is_number(a1) && is_number(a2)
               ? a1 + a2
               : list(a1, "+", a2);
}
// a sequence of terms and operators is a sum
// if and only if at least one + operator occurs
function is_sum(x) {
    return is_pair(x) && contains_plus(x);
}
function addend(s) {
    return simplify_unary_list(items_before_first("+", s));
}
function augend(s) {
    return simplify_unary_list(items_after_first("+", s));
}
function make_product(m1, m2) {
    return number_equal(m1, 0) || number_equal(m2, 0)
           ?  0
           : number_equal(m1, 1)
             ? m2
             : number_equal(m2, 1)
               ?  m1
               : is_number(m1) && is_number(m2)
                 ? m1 * m2
                 : list(m1, "*", m2);
}
// a sequence of terms and operators is a product
// if and only if no + operator occurs
function is_product(x) {
    return is_pair(x) && ! contains_plus(x);
}
function multiplier(s) {
    return simplify_unary_list(items_before_first("*", s));
}
function multiplicand(s) {
    return simplify_unary_list(items_after_first("*", s));
}
function deriv(exp, variable) {
    return is_number(exp)
        ? 0
        : is_variable(exp)
          ? (is_same_variable(exp, variable) ? 1 : 0)
          : is_sum(exp)
            ? make_sum(deriv(addend(exp), variable),
                       deriv(augend(exp), variable))
            : is_product(exp)
              ? make_sum(make_product(multiplier(exp),
                             deriv(multiplicand(exp),
                                   variable)),
                         make_product(deriv(multiplier(exp),
                                            variable),
                             multiplicand(exp)))
              : error(exp, "unknown expression type -- deriv");
}

The differentiation program with abstract data抽象データを用いた微分プログラム

Representing algebraic expressions代数式の表現

The differentiation program with abstract data
抽象データを用いた微分プログラム

Representing algebraic expressions
代数式の表現