Symbolic Programming

29.1 Symbolic Differentiation (SICP 2.3.2)

(define (variable? x) (symbol? x))
(define (same-variable? a b) (and (variable? a) (variable? b) (eq? a b)))
(define (=number? exp num) (and (number? exp) (= exp num)))

(define (make-sum a b)
  (cond ((=number? a 0) b)
        ((=number? b 0) a)
        ((and (number? a) (number? b)) (+ a b))
        (else (list '+ a b))))
(define (make-product a b)
  (cond ((or (=number? a 0) (=number? b 0)) 0)
        ((=number? a 1) b)
        ((=number? b 1) a)
        ((and (number? a) (number? b)) (* a b))
        (else (list '* a b))))
(define (sum? x) (and (pair? x) (eq? (car x) '+)))
(define (product? x) (and (pair? x) (eq? (car x) '*)))
(define addend cadr) (define augend caddr)
(define multiplier cadr) (define multiplicand caddr)

(define (deriv exp var)
  (cond ((number? exp) 0)
        ((variable? exp) (if (same-variable? exp var) 1 0))
        ((sum? exp) (make-sum (deriv (addend exp) var) (deriv (augend exp) var)))
        ((product? exp)
         (make-sum (make-product (multiplier exp) (deriv (multiplicand exp) var))
                   (make-product (deriv (multiplier exp) var) (multiplicand exp))))
        (else (error "unknown expression type" exp))))

(deriv '(+ (* 3 x) (* x x)
…

29.2 Pattern Matching and Rule-Based Systems

Classic symbolic AI programs (ELIZA, expert systems, algebra systems like Macsyma/Maxima, theorem provers like ACL2) were built this way. Maxima is still written in Common Lisp.

;; A tiny pattern matcher: ?x matches anything and binds it
(define (pattern-var? x) (and (symbol? x) (char=? (string-ref (symbol->string x) 0) #\?)))
(define (match pat dat bindings)
  (cond ((not bindings) #f)
        ((pattern-var? pat)
         (let ((b (assq pat bindings)))
           (cond ((not b) (cons (cons pat dat) bindings))
                 ((equal? (cdr b) dat) bindings)
                 (else #f))))
        ((and (pair? pat) (pair? dat))
         (match (cdr pat) (cdr dat) (match (car pat) (car dat) bindings)))
        ((equal? pat dat) bindings)
        (else #f)))
(match '(?x loves ?y) '(ana loves lisp) '())   ; ((?y . lisp) (?x . ana))