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 Lisp. 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 currently being used by a growing number of 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.
In order 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: \[ \frac{dc}{dx} = 0\text{ for $c$ a constant or a variable different from $x$} \] \[ \frac{dx}{dx} = 1 \] \[ \frac{d(u+v)}{dx} = \frac{du}{dx}+\frac{dv}{dx} \] \[ \frac{d(uv)}{dx} = u\left( \frac{dv}{dx}\right)+v\left( \frac{du}{dx}\right)\] 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? |
is_same_variable(v1, v2) | Are v1 and v2 the same variable? |
is_sum(e) | Is e a sum? |
addend(e) | Addend of the sum e. |
augend(e) | Augend of the sum e. |
make_sum(a1, a2) | Construct the sum of a1 and a2. |
is_product(e) | Is e a product? |
multiplier(e) | Multiplier of the product e. |
multiplicand(e) | Multiplicand of the product e. |
make_product(m1, m2) | Construct the product of m1 and 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("unknown expression type in deriv", exp); }
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.
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"). Then our data representation for the differentiation problem is as follows:
function is_variable(x) { return is_string(x); }
function is_same_variable(v1, v2) { return is_variable(v1) && is_variable(v2) && v1 === v2; }
function make_sum(a1, a2) { return list("+", a1, a2); }
function make_product(m1, m2) { return list("*", m1, m2); }
function is_sum(x) { return is_pair(x) && head(x) === "+"; }
function addend(s) { return head(tail(s)); }
function augend(s) { return head(tail(tail(s))); }
function is_product(x) { return is_pair(x) && head(x) === "*"; }
function multiplier(s) { return head(tail(s)); }
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"); // ["+", [1, [0, null]]]
deriv(list("*", "x", "y"), "x"); // ["+", [["*", ["x", [0, null]]], // [["*", [1, ["y", null]]], null]]]
deriv(list("*", list("*", "x", "y"), list("+", "x", 3)), "x"); // [ "+", // [["*", [["*", ["x", ["y", null]]], // [["+", [1, [0, null]]], null]]], // [["*", // [["+", // [["*", ["x", [0, null]]], // [["*", [1, ["y", null]]], null]]], // [["+", ["x", [3, null]]], null] ] ], // null ]]]
The program produces answers that are correct; however, they are unsimplified. It is true that \[ \frac{d(xy)}{dx} = x\cdot 0+1\cdot y \] 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); }
function number_equal(exp, num) { return is_number(exp) && exp === num; }
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); }
deriv(list("+", "x", 3), "x"); // 1
deriv(list("*", "x", "y"), "x"); // "y"
deriv(list("*", list("*", "x", "y"), list("+", "x", 3)), "x"); // [ "+", // [["*", ["x", ["y", null]]], // [["*", ["y", [["+", ["x", [3, null]]], null]]], null]] ]
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.
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("unknown expression type in deriv", exp); }
deriv(list("*", "x", "y", list("+", "x", 3)), "x");
deriv(list("*", "x", "y", list("+", "x", 3)), "x");
list("x", "+", list(3, "*", list("x", "+", list("y", "+", 2))))
list("x", "+", "3", "*", list("x", "+", "y", "+", 2))
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("unknown expression type in deriv", exp); }
function items_before_first(op, s) { return head(s) === op ? null : pair(head(s), items_before_first(op, tail(s))); } function items_after_first(op, s) { return head(s) === op ? tail(s) : items_after_first(op, 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) && ! (is_null(member("+", x)); } function addend(s) { return items_before_first("+", s); } function augend(s) { return 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) && is_null(member("+", x); } function multiplier(s) { return items_before_first("*", s); } function multiplicand(s) { return 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("unknown expression type in deriv", exp); }