Suppose we want to define a function that, given an algebraic expression and a variable, will
produce the derivative of the expression with respect to the variable [Hen1980]. To keep the
presentation concise, we deal only with simple formulae consisting of integers, variables, and
binary operators + and *. The generalization to more
complicated formulae is straightforward, and is left for the reader as an exercise.
Let x and y stand for arbitrary variables,
i for an integer, and e for a formula. Let
Dx(e) denote the result of differentiating e
with respect to x. Then the rules of differentiation can be written as
follows:
Dx(x)
=
1
Dx(y)
=
0 (where y is different from x)
Dx(i)
=
0
Dx(e1 + e2)
=
Dx(e1) + Dx(e2)
Dx(e1 * e2)
=
e1 * Dx(e2) + e2 *
Dx(e1)
Before writing the program of differentiating, we have to represent formulae by ground
expressions. Let [e] stand for the formula e represented by
a ground expression. Then we may choose the representation defined by the following rules:
[x]
=
x
[i]
=
i
[e1 + e2]
=
(Sum [e1] [e2])
[e1 * e2]
=
(Prod [e1] [e2])
Now a function Diff can be easily defined whose first argument is a
variable, and the second argument a formula. The function returns the result of
differentiating the formula with respect to the variable.
$func Diff sX tE = tE;
Diff sX tE =
tE :
{
sX = 1;
sY = 0;
(s.Oper t.E1 t.E2) =
<Diff sX tE1> :: t.DxE1,
<Diff sX tE2> :: t.DxE2,
s.Oper :
{
Sum = (Sum t.DxE1 t.DxE2);
Prod = (Sum (Prod t.E1 t.DxE2) (Prod t.E2 t.DxE1));
};
};
An obvious deficiency of the above definition of the function Diff is that
the formulae produced by the function contain a lot of unnecessary parts. For example,
according to the above rules of differentiation we have
DX(3*(X*X)+5)
=
(3*((X*1)+(X*))+(X*X)*0)+0
which could have been reduced to by means of evident simplifications. Thus we can enhance the definition of the
function Diff by making the function perform the following reductions:
0 + e2
==>
e2
e1+ 0
==>
e1
0 * e2
==>
0
e1* 0
==>
0
1 * e2
==>
e2
e1* 1
==>
e1
(We won't consider more complicated reductions, to keep the presentation concise.)
There are two ways of implementing the above simplifications. The first way is to perform the
simplifications only after the result of the differentiation has been completely built. The
second way is to try the simplifications "on the fly", during the differentiation. And it is
the second way that we are going to implement.
As the first step, we define two functions Sum and
Prod, each function taking two formulae and returning respectively the sum
and the product of the formulae. It is in these functions that the simplifications are
performed.
$func Sum t1 t2 = t;
$func Prod t1 t2 = t;
Sum
{
0 t2 = t2;
t1 0 = t1;
t1 t2 = (Sum t1 t2);
};
Prod
{
0 t2 = 0;
1 t2 = t2;
t1 0 = 0;
t1 1 = t1;
t1 t2 = (Prod t1 t2);
};
Now we can rewrite the above definition of the function Diff, inserting at
appropriate places the calls to the functions Sum and
Prod:
Diff sX tE =
tE :
{
sX = 1;
sY = 0;
(s.Oper t.E1 t.E2) =
<Diff sX tE1> :: t.DxE1,
<Diff sX tE2> :: t.DxE2,
s.Oper :
{
Sum = <Sum t.DxE1 t.DxE2>;
Prod = <Sum <Prod t.E1 t.DxE2> <Prod t.E2 t.DxE1>>;
};
};