Example: Formal Differentiation

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
3*(X+X)
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>>;
    };
  };

Bibliography

[Hen1980] P.Henderson. Functional Programming: Application and Implementation. Prentice-Hall. 1980.

Parent topic: Logical conditions