As an introduction to the Small Lisp programming language, we consider how it could be used to solve the problem of symbolic differentiation. But first we review the elements of the language.

Symbolic Data in Lisp

The S-expression (symbolic expression) is the fundamental data domain in Small Lisp. The domain consists of two primitive elements (numeric and symbolic atoms) and lists. Lists are sequences of zero or more S-expressions.

1. Numeric atoms are positive or negative integers.
   • EBNF: [-] <digit> {<digit>}
   • 0
   • 42
   • -128
2. Symbolic atoms are (possibly hyphenated) alphanumeric identifiers, or operator symbols made up of special characters.
   • EBNF: <letter> {[-] <letter> | <digit> } | <special> {<special>}
   • RE: <special> = [-+*/<>=&|@!#$%?:]
   • x0
   • gensym-432
   • @@@
3. Lists have zero-or more S-expressions within parentheses.
   • (R2D2 C3P0)
   • (A (partially parsed) sentence)
   • ((A 3) (B 4) (C 5) (D 1))
   • (())

Special Atoms

• T represents true
• F represents false

Small Lisp Built-In Functions

Small Lisp has 20 primitive functions. Many of the functions are recognizers for distinguishing different types of data objects or comparing data objects. Analyzers

Test for a Numeric Atom

• numberp[3] = T
• numberp["x"] = F
• numberp[(R2D2 C3PO)] = F
• numberp[()] = F

Test for a Symbolic Atom

• symbolp[3] = F
• symbolp["x"] = T
• symbolp[(R2D2 C3PO)] = F
• symbolp[()] = F

Test for a List

• listp[3] = F
• listp["x"] = F
• listp[(R2D2 C3PO)] = T
• listp[()] = T

Test for an Empty List

• endp[3] = run-time error
• endp["x"] = run-time error
• endp[(R2D2 C3PO)] = F
• endp[()] = T

Symbolic Atom Comparison

• eq["X"; "X"] = T
• eq["X"; "Y"] = F

Numeric Atom Comparison

• eqp["3"; "4"] = F
• lessp["3"; "4"] = T

List Operations

• first[(A B C)] = A
• rest[(A B C)] = (B C)
• cons["X"; (B C)] = (X B C)

Numeric Operations

There are no operators in Small Lisp, but numeric functions instead.

• plus[4; 5] = 9
• times[4; 5] = 20

Function Definitions in Small Lisp

Functions are defined in Small Lisp by giving a name, a list of parameters and an expression that evaluates to the function result.

Defining Functions for the second and third element of a list

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

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

Small Lisp Control: Conditional Expressions and Recursion

The only control structure in Small Lisp is the conditional expression. It is a series of if-then clauses whose if-parts are evaluated in order until one returns T (true). Then the corresponding then part is evaluated and returned as the expression result.

Conditional expressions are typically combined with recursive function calls to perform any kind of repetitive task.

The Length of a List

length[list] =
  [endp[list] --> 0;
   otherwise --> plus[length[rest[list]]; 1]]

Appending Two Lists

append[list1; list2] =
  [endp[list1] --> list2;
   otherwise --> cons[first[list1]; append[rest[list1]; list2]]]

Algebraic Expressions in Lisp

We can represent algebraic expressions as Lisp data objects in a very straightforward way.

1. Use numeric atoms to represent Nums.
2. Use symbolic atoms to represent Vars.
3. Represent binary algebraic expressions with a 3-element list, whose second element is an operator symbol.
   • 4*x**2+3*x is represented: ((4 * (x ** 2)) + (3 * x))
4. Represent unary algebraic expressions with a 2-element list.
   • -5*x is represented (- (5 * x))

deriv in Small Lisp

Now take a look at symbolic differentiation in Small Lisp!

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]];
   difference-p[E] -->
     make-difference[deriv[operand1[E]; V]; deriv[operand2[E]; V]];
   power-p[E] -->
     make-product
       [make-product[exponent[E]; deriv[base[E]; V]];
        make-power
          [base[E]; make-constant[minus[const-val[exponent[E]]; 1]]]];

This is a recursive program which differs from the Haskell version primarily by the use of data access functions to replace pattern matching.

Programming Data Access Functions in Small Lisp

Now we introduce functions for recognizing, analyzing and constructing algebraic objects.

;;; The recognizers.
;;;
constant-p[expr] = numberp[expr]

variable-p[expr] = symbolp[expr]

negation-p[expr] =
  [listp[expr] -->
     [endp[rest[rest[expr]]] --> eq[first[expr]; "-"];
      otherwise --> F];
   otherwise --> F]

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; "+"]

difference-p[expr] = dyadic-math-p[expr; "-"]

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

;;;
;;; The selectors.
;;;
operand[expr] = second[expr]

operand1[expr] = first[expr]

operand2[expr] = third[expr]

base[expr] = first[expr]

exponent[expr] = third[expr]

;;;
;;; The constructors.
;;;
make-negation[expr] = list2["-"; expr]

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

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

make-difference[expr1; expr2] = list3[expr1; "-"; expr2]

make-power[expr1; expr2] = list3[expr1; "**"; expr2]

;;;
;;; The converters.
;;;
const-val[const-expr] = const-expr

make-constant[numeric-atom] = numeric-atom

var-name[variable] = variable

make-variable[symbolic-atom] = symbolic-atom