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.

Sisterinlaw

The "numerical-methods" tag is not adequate for your question, because what you are asking for is symbolical differentiation. Finding the deriviative of a function f at x by numerical differentiation would simply be a calculation of (f(x+dx)-f(x))/dx for some small value of dx. – Preeminent

@curd: By adding the numerical-methods tag, I didn't mean to imply that I was looking for a way to perform numerical differentiation, which, clearly, I am not. I just meant that the question concerns itself with functions relevant to numerical computing (e.g. evaluating symbolic expressions that implement numerical methods). – Sisterinlaw

I'm with you. It's frustrating the way every time I mention automatic differentiation people confuse it with symbolic differentiation and often refuse to hear that there is a difference. It is most certainly a "numerical method", and it certainly isn't "numerical differentiation". – Esdraelon

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

Kenzie

Answer 2

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

Karisa

Thank you! One last thing: could you define or perhaps provide reference for the term "perturbation confusion"? I'm unfamiliar with the term. – Sisterinlaw

Ok found the answer myself, from this paper: eprints.nuim.ie/archive/00000566/01/Perturbation.pdf "these implementations (...) can compute grossly incorrect results when the differentiation operator is applied to a function that itself uses that operator. The underlying cause of this problem is perturbation confusion, a failure to distinguish between distinct perturbations introduced by distinct invocations of the differentiation operator. We then discuss how perturbation confusion can be avoided." – Sisterinlaw

Answer 3

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).

Acting

Thanks, but external tools for symbolic differentiation aren't what I'm looking for. I've edited the question to clarify this. – Sisterinlaw

It should be possible to use Maxima as a library from any common lisp program (and thus it can be used from inside a macro), so it is not that "external" after all. – Photokinesis

It's the symbolicness that's a problem. I'm looking for a macro that takes a function F and returns a function F'. I mean an evaluable function, which takes numeric arguments, not a symbolic expression. – Sisterinlaw

Answer 4

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

Cenesthesia

Answer 5

Here is an implementation of AD in common lisp.

Esdraelon

Answer 6

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

Overthrow

Answer 7

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

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

Preeminent

I've edited the question to make it clear why those examples don't quite provide everything I'm looking for. – Sisterinlaw