Symbolic Differentiation in Small Lisp

CMPT 384 Lecture Notes
Robert D. Cameron
September 13, 1999

Symbolic Differentiation

an initial demonstration of symbolic computing
representation of algebraic expressions as Lisp data objects
algebraic expressions as an abstract data type (ADT)
recognizer, selector, constructor and converter functions
deriv as a recursive program on the algebraic expression domain
representation can be summarized by a grammar (GRAIL)

Symbolic Differentiation: The Problem

Write a program which implements the following rules of mathematics:


d`n`/dx	=	0
d`v`/dx	=	1, if `v` = x, 0 otherwise
d(-`f`)/dx	=	- d`f`/dx
d(`f` × `g`)/dx	=	`f` × d`g`/dx + `g` × d`f`/dx
d(`f` + `g`)/dx	=	d`f`/dx + d`g`/dx

Here,

n stands for an arbitrary numeric constant.
v stands for an arbitrary mathematical variable.
f and g stand for arbitrary algebraic expressions of any type.

Solution: A Recursive Program

deriv[E; V] =
  [constant-p[E] --> make-constant[0];
   variable-p[E] -->
     [eq[var-name[E]; var-name[V]] --> 
        make-constant[1];
      otherwise --> make-constant[0]];
   negation-p[E] --> 
     make-negation[deriv[operand[E]; V]];
   product-p[E] -->
     make-sum
       [make-product
          [operand1[E]; 
           deriv[operand2[E]; V]];
        make-product
          [operand2[E]; 
           deriv[operand1[E]; V]]];
   sum-p[E] -->
     make-sum[deriv[operand1[E]; V]; 
              deriv[operand2[E]; V]]]

Data Access Functions

The deriv program is a straightforward translation of differentation rules. Data access functions (DAFs) refer to symbolic representations of algebraic expressions.

Recognizers: distinguish alternative types of algebraic expression: constant-p, variable-p, negation-p, etc.
Converters: convert between numeric or string values and their symbolic representations as algebraic expressions: make-constant, var-name.
Selectors: select components of structured algebraic expressions: operand, operand1, operand2.
Constructors: build structured algebraic expressions from components: make-negation, make-product, make-sum.

DAFs Hide the Representation

So far, no computer representation of algebraic expressions has been specified! An abstract solution.

Readable: details of representation do not clutter the algorithm.
Language-independent: easy to write in any language.
Concreteness: need a representation for algebraic expressions.
The DAFs comprise an abstract data type for algebraic expressions.

Lisp lists: a quick and convenient way of representing algebraic expressions.

Representation of Algebraic Expressions

How can we represent algebraic expressions as Lisp lists? For example, consider 2×x+3×y How about using:

(2 * x + 3 * y)

Problem: This does not group the appropriate components together as single substructures (lists). Instead:

((2 * x) + (3 * y))

A workable compromise.

Expression	Representation
numeric constants	numeric atoms
variables	symbolic atoms
-`f`	`(- F`)
`f` × `g`	`(F * G)`
`f`+`g`	`(F + G)`

Here, F is the representation of f, G the representation of g, and N the representation of n (a numeric constant).

Expression	Representation
2	`2`
x	`x`
3	`3`
y	`y`
2 × x	`(2 * x)`
3 × y	`(3 * y)`
2 × x+3 × y	`((2 * x) + (3 * y))`

Now we need to implement the DAFs.

Implementation of DAFs: Constructors

Build the lists that represent structured formulas (negations, products and sums). First, some helper functions.

list2[e1; e2] = 
  cons[e1; cons[e2; ()]]
list3[e1; e2; e3] = 
  cons[e1; list2[e2; e3]]

A negation expression is a two-element list whose first element is the atom ``-''.

make-negation[expr] = 
  list2["-"; expr]

Sums and products are three-element lists with infix operators.

make-sum[expr1; expr2] = 
  list3[expr1; "+"; expr2]
make-product[expr1; expr2] = 
  list3[expr1; "+*; expr2]

Implementation of DAFs: Selectors

Helper functions are useful for selecting list elements.

second[list] = first[rest[list]]
third[list] = second[rest[list]]

The component of a "negation" expression its operand.

operand[expr] = second[expr]

Sum and product expression there have two operands:

operand1[expr] = first[expr]

operand2[expr] = third[expr]

When we use the same selectors for two or more different types of symbolic data, we say they are overloaded.

Implementation of DAFs: Recognizers

Input assumption: recognizers are given a valid representation of an algebraic expression. Output: return T iff the algebraic expression is of the correct type.

constant-p[expr] = numberp[expr]

variable-p[expr] = symbolp[expr]

;;;  Check for a 2-element list, 
;;;  whose first element is the atom "-".
negation-p[expr] =
  [listp[expr] -->
     [endp[rest[rest[expr]]] --> 
        eq[first[expr]; "-"];
      otherwise --> F];
   otherwise --> F]

Note: endp[rest[rest[expr]]] asks the question: Is the list empty after removing two elements? \newpage The job recognizing a three-element list with a particular operator symbol can be factored out into a single routine.

dyadic-math-p[expr; infix-sym] =
  [listp[expr] -->
     [endp[rest[rest[expr]]] --> F;
      otherwise --> 
        eq[second[expr]; infix-sym]];
   otherwise --> F]

product-p[expr] = 
  dyadic-math-p[expr; "*"]

sum-p[expr] = 
  dyadic-math-p[expr; "+"]

Implementation of DAFs: Convertors

In Small Lisp, convertor functions are trivial!

const-val[const-expr] = const-expr

make-constant[num-atom] = num-atom

var-name[variable] = variable

make-variable[sym-atom] = sym-atom

These are identity functions! Why? In Lisp, atoms serve two roles:

as the ground elements of symbolic notations.
as representations for numbers and strings.

In other languages, symbolic data will typically be represented by pointer objects. Conversion will be required.

Demo

1: cameron_alrisha% setenv PATH ${PATH}:/gfs1/CMPT/384/bin

2: cameron_alrisha% smlisp
Commands:  /help, /info, /log, /read, /reset, /save, /show, /stop.
/reset /gfs1/CMPT/384/src/deriv.cfg
deriv[((2 * x) + (3 * y)); "x"]
(((2 * 1) + (x * 0)) + ((3 * 0) + (y * 0)))
/stop

Symbolic Differentiation in Small Lisp

CMPT 384 Lecture Notes Robert D. Cameron September 13, 1999