Algorithmic differentiation

[Dimitris]

Hallo,
algorithmic differentiation differs from symbolic differentiation as well as numerical. In practice, it takes existing code (i.e., it does not do symbolic math in a new language) and computes the derivative of that function. As you may suspect Lisp is very suitable for AD.

So, I'm trying to implement the code from this paper (Appendix 2):
http://www.cs.berkeley.edu/~fateman/papers/ADIL.pdf
but I get the error "*** - PROGN: variable TWO-ARG has no value". I assume the error is in defarithmetic (and I probably messed up the quotes). Here is the code so far:

Code: Select all

;;; Automatic Differentiation code for Common Lisp 
;;; using overloading, forward differentiation.

(defpackage :ga ;generic arithmetic
    (:shadow "+" "-" "/" "*" "expt"     ;binary arithmetic
             "=" "/=" ">" "<" "<=" ">=" ;binary operations
             "sin" "cos" "tan"          ;... more trigonometric
             "atan" "asin" "acos"       ;... more inverse trigonometric
             "sinh" "cosh" "atanh"      ;... more hyperbolic
             "expt" "log" "exp" "sqrt"  ;... more exponential, powers
             "1-" "1+" "abs" 
             )
     (:use :common-lisp)
)

(in-package :ga)

;; structure for f,d: f is function value, and d derivative, default 0 
(defstruct (df (:constructor df (f &optional (d 0)))) f d)

;; print df structure with < , >
(defmethod print-object ((a df) stream)(format stream "<~a, ~a>" (df-f a)(df-d a)))

;;function ARITHMETIC-IDENTITY: When fed an operator and a non-nil 
;;argument, it returns a value for unary application. What does (+ a) mean? 
;;A nil arg means there were NO operands. What does (+ ) mean. 
;;It is used only by defarithmetic, which in turn helps 
;; us to write out + * - / of arbitrary number of args.

(defmacro arithmetic-identity (op arg)
    `(case ,op
      (+ (or ,arg 0))
      (- (if ,arg (two-arg-* -1 ,arg) 0))
      (* (or ,arg 1))
      (/ (or ,arg (error "/ given no arguments")))
      (expt (or ,arg (error "expt given no arguments")))
      (otherwise nil))) ;binary comparisons?
      
(defun tocl(n)  ; get corresponding name in cl-user package
    (find-symbol (symbol-name n) :cl-user))
    
(defmacro defarithmetic (op)
    (let ((two-arg
                (intern (concatenate 'string "two-arg-" (symbol-name op))
                    :ga))
            (cl-op (tocl op)))
        `(progn
            (defun ,op (&rest args)
                (cond ((null args) (arithmetic-identity `,op nil))
                      ((null (cdr args))(arithmetic-identity `,op (car args)))
                      (t (reduce (function ,two-arg)
                                 (cdr args)
                                 :initial-value (car args)))))
            (defgeneric ,two-arg (arg1 arg2))
            (defmethod ,two-arg ((arg1 number) (arg2 number)) 
                (,cl-op arg1 arg2))
            (compile `,two-arg) 
            (compile `,op) 
            ,op)))
            
(defarithmetic +) ;; defines some of + programs. See below for more 
(defarithmetic -) 
(defarithmetic *) 
(defarithmetic /)
(defarithmetic expt)

I use the CLisp implementation.

Thanks in advance,
Dimitris

PS. I have to admit that I am new to Common Lisp, so I don't know much about macros.

[ramarren]

Notes: There seems to be no reason for ARITHMETIC-IDENTITY to be a macro at all, and the comment calls it a function. Typically you wouldn't call compile manually in this way, compilation is typically handled by file compilation mechanism.

You problem is caused by using the quasiquote where you need a standard quote: `,THING is equivalent to THING, since the comma negates the quasiquote directly preceding it. In your macro you need the comma to cause evaluation in the context of the macro-level quasiquote, and the standard quote to prevent such (typically) symbol evaluated at compile time from being evaluated at runtime.

[Dimitris]

Thank you! That solved the problem. However, I get a continuable Error:
"DEFUN/DEFMACRO(EXPT): #<PACKAGE COMMON-LISP> is locked"
which leads to the following warnings:

Code: Select all

WARNING: DEFUN/DEFMACRO: redefining function EXPT in /Users/dp/work/fem/AD.lisp, was defined in C
WARNING: |two-arg-EXPT| is already compiled.
WARNING: in EXPT : Function TWO-ARG-* is not defined
WARNING: in EXPT : Function TWO-ARG-* is not defined

I assume I have to read quite a lot about those macros
Thanks a lot!

[ramarren]

Symbol names in Common Lisp are case sensitive. The reader algorithm upcases symbol names by default, but when specifying them as strings, like you do in :shadow clause, the case matters. Which means you shadow symbol named "expt", and later you define a function named with a symbol "EXPT" from the cl-user package, which causes a conflict. Similar effect causes the two-arg-* error, you pass a lowercase string to intern, but the call in ARITHMETIC-UNITY is uppercased by the reader. You can write in code more general symbol names using the |symbol name| syntax, which allow the use of any character (with internal pipes quoted with a backslash) of any case, if you want to call any of those from code. But I would suggest normalizing case in created symbols to uppercase.

Also symbols for :shadow and other defpackage clauses can be specified using the #:expt syntax, which creates an uninterned symbol with a name created by the same reader as the rest of the code, which avoids these issues.

[Dimitris]

Thank you very much for the answers! I suppose I have to study more...