Automatic differentiation library in Scheme / Common Lisp / Clojure

Question

I've heard that one of McCarthy's original motivations for inventing Lisp was to write a system for automatic differentiation. Despite this, my Google searches haven't yielded any libraries/macros for doing this. Are there any Scheme/Common Lisp/Clojure libraries (macros) out there for taking a function F and returning a function dF/dx that calculates the derivative of F?

I would want it to support F's with multiple arguments. The user would choose which of these is the x to differentiate with respect to. Ideally, the differentiator would work even for vector-valued F's and x's.

EDIT: Several people have mentioned symbolic differentiation. The difference between symbolic differentiation and automatic differentiation is a subtle one, but it's summarized well in Wikipedia, and particularly in this picture. This distinction isn't as strong in lisp, where symbolic expressions can be turned into working programs as-is, but there remains a potential difficulty:

Symbolic differentiation requires the expression being differentiated to be composed of operations with known derivatives. For example, someone mentioned SICP's example of a macro that churns through simple sexps like (+ y (* (x y))), and uses the chain rule, along with knowledge of how to differentiate + and *, to return a sexp that represents the derivative. I would need that to work with expressions like (* (foo x y) (bar x)), where foo and bar may in turn call other functions whose derivatives aren't known at differentiation time.

This would be fine if there's a way to take an expression like (foo x y) and replace it with its function body, substituting any mention of the arguments with x and y in a hygenic way. Is there?

Also, none of the above addresses complications that come about when differentiating vector-valued functions with respect to vector-valued arguments... which is what most autodifferentiation implementations are geared for.

Answer 1

There are two other packages, both for automatic differentiation in Scheme. The second is based on the first, but reworked as a chicken egg. These support both forward and reverse mode.

• https://github.com/qobi/R6RS-AD
• https://github.com/abarbu/AD

Answer 2

If you are looking for a symbolic system, you could try maxima (or here). It runs on a number of Common-Lisp/OS platform combinations, but is more of a complete system than a library.

Console output is OK, but it can produce quite nice looking output when coupled with texmacs.

Maxima 5.23.2 http://maxima.sourceforge.net
using Lisp GNU Common Lisp (GCL) GCL 2.6.8 (a.k.a. GCL)
Distributed under the GNU Public License. See the file COPYING.
Dedicated to the memory of William Schelter.
The function bug_report() provides bug reporting information.
(%i1) diff(sin(1/x),x);
                                        1
                                     cos(-)
                                         x
(%o1)                              - ------
                                        2
                                       x

---

EDIT

OK, looks like I misunderstood the question. A bit of googling suggests that there are some tools for this in SCMUTILS here, download here, user manual here (see p24 onwards).

Answer 3

Alexey Radul writes:

Well, there's the automatic differentiation system in Scmutils

http://groups.csail.mit.edu/mac/users/gjs/6946/linux-install.htm

(which coincidentally also does symbolic differentiation). I don't know of any other released implementations, though you might check http://autodiff.org/ .

There's also a nice explanation of how to implement it yourself in an appendix of Structure and Interpretation of Classical Mechanics

http://mitpress.mit.edu/sicm/

as well as in the academic literature. Particularly forward mode is not that hard, though you do have to be careful to avoid perturbation confusion. You might consult the publications of Barak Pearlmutter and Jeffrey Mark Siskind, who are collaborating on a high-performance Lisp variant that incorporates AD and have been publishing on surrounding issues.

http://scholar.google.com/scholar?q=Barak+Pearlmutter+and+Jeffrey+Mark+Siskind

Answer 4

Google for 'lisp symbolic differentiation' and you will find plenty examples, e.g.

http://mitpress.mit.edu/sicp/full-text/sicp/book/node39.html

Answer 5

It may be of interest that scmutlis has now been ported to Clojure. There is a lot more work to be done, but the code in the fist chapters of the SICM book seems to be running fine.

Differentiation routines and operators also seem OK with what little testing I've done, and it is even free of some bugs that appear to have crept into later versions of scmutils.

I think that scmutils covers OP's requirements re differentiation, since it will correctly handle derivatives of both known and unknown (literal) functions. This page gives the details needed to see how well it fits requirements: SICM - Derivatives - Notation

One of the advantages of running on the JVM, is that will run as a standalone if so required, no need even to install Clojure!

It is very close to the original Scheme, minimal concessions made for Clojure syntax.

You can see it here: https://github.com/littleredcomputer/sicmutils#sicmutils

===

Addendum: Here is an example of automatic differentiation in the SicmUtils Clojure package. This is a common example circulating on various Internet sites, the code to be differentiated is

    function f(x)
      y = x;
      for i=1...100
        y = sin(x+y);
      return y

After Clojurifying it a bit we have

   > (defn inner [y] (fn[x] (sin (+ x y))))
   > (defn f100 [x] (nth (iterate (inner x) x) 100))
   ;; value of derivative at 6
   > ((D f100) 6)
    => 0.51603111348625
   ;; value of the 4th derivative at 1
   > (((expt D 4) f100) 1)
    => -1.7853200839806143

Answer 6

Here is an implementation of AD in common lisp.

Answer 7

Worth checking out Deriva, which does Automatic Differentiation for both Clojure and Java:

• https://github.com/lambder/Deriva

You may also be interested in expresso, which is more about numerical expression manipulation but still has some differentiation features and could probably be adapted to most AD use cases:

• https://github.com/clojure-numerics/expresso