Lab 3: Auto-Diff
Bard College – Computer Science – Design of Programming Languages

In this week’s lab we will create a program that computes derivatives automatically. Building upon SICP’s approach of symbolic differentiation, we will use a technique called Automatic Differentiation. This approach is used in modern neural networks libraries like TensorFlow and PyTorch.

You will want to review 2.1.1: Arithmetic Operations for Rational Numbers and 2.3.2: Symbolic Differentiation from SICP before starting this lab.

A Dual-Number Type

Our first step will be creating a new dual-number data type to perform "forward-mode” automatic differentiation. For dual-numbers in Scheme, an implementation using pairs makes sense. The first element of the pair will be x and the second will be the infinitesimal xx': (x . x')
 
(define (make-dual n d) (cons n d))
(define (val x)  (car x))
(define (dval x) (cdr x))
(define (make-variable x) (make-dual x 1))

(This implementation is reminiscent of the rational number data type outlined in 2.1.1: Arithmetic Operations for Rational Numbers.)

To find the derivative of an addition expression, for example, f(x)=x+xf(x) = x + x; f(2)f'(2), we apply the procedure add-dual:

(define (add-dual u v)
  (make-dual (+ (val u)  (val v))
             (+ (dval u) (dval v))))

(define x (make-variable 2))
(add-dual x x) --> (4 . 2)

Your dual numbers should support the following mathematical functions:
For example, f(x)=1/cos(sin(x)2)f(x) = 1/\cos(\sin(x)^2)
(quo-dual (make-constant 1)
          (cos-dual (pow-dual (sin-dual x) (make-constant 2))))
             -->(1.48 . -1.21)

A Derivative Interpreter

Building upon the program in 2.3.2: Symbolic Differentiation from SICP and our dual numbers, create a function deval to allow more declarative evaluation of derivative expressions. 

Don’t use scheme’s eval for this lab.

deval: (expression x symbol x value) → dual-number

(deval '(* x 2) 'x 2)                   --> (4 . 2)
(deval '(/ 1 (cos (^ (sin x) 2))) 'x 2) --> (1.48 . -1.21)

Next Steps

  • Use an assoc list, instead of a single variable and value, in the deval procedure to allow multivariate equations.
  • (deval '(* x y) '((x 2) (y 2)))  --> (4 2 2)
  • (deval (infix->prefix "1/cos((sin x)^2)") 'x 2) --> (1.48 . -1.21)
  • Allow procedures and implement the chain rule.

Learning Goals

  • Create a dual number type.
  • Evaluate prefix expressions.
  • Learn about automatic differentiation.