ANNOUNCE: fad 1.0 — Forward Automatic Differentiation for Haskell

I’m pleased to announce the initial release of the Haskell fad library, developed by Barak A. Pearlmutter and Jeffrey Mark Siskind. Fad provides Forward Automatic Differentiation (AD) for functions polymorphic over instances of Num. There have been many Haskell implementations of forward AD, with varying levels of completeness, published in papers and blog posts, but alarmingly few of these have made it into hackage — to date Conal Elliott’s vector-spaces package is the only one I am aware of.

Fad is an attempt to make as comprehensive and usable a forward AD package as is possible in Haskell. However, correctness is given priority over ease of use, and this is in my opinion the defining quality of fad. Specifically, Fad leverages Haskell’s expressive type system to tackle the problem of perturbation confusion, brought to light in Pearlmutter and Siskind’s 2005 paper Perturbation Confusion and Referential Transparency. Fad prevents perturbation confusion by employing type-level “branding” as proposed by myself in a 2007 post to haskell-cafe. To the best of our knowledge all other forward AD implementations in Haskell are susceptible to perturbation confusion.

As this library has been in the works for quite some time it is worth noting that it hasn’t benefited from Conal’s ground-breaking work in the area. Once we wrap our heads around his beautiful constructs perhaps we’ll be able to borrow some tricks from him.

As mentioned already, fad was developed primarily by Barak A. Pearlmutter and Jeffrey Mark Siskind. My own contribution has been providing Haskell infrastructure support and wrapping up loose ends in order to get the library into a releasable state. Many thanks to Barak and Jeffrey for permitting me to release fad under the BSD license.

Fad resides on GitHub and hackage and is only a cabal install fad away! What follows is Fad’s README, refer to the haddocks for detailed documentation.

   Copyright  : 2008-2009, Barak A. Pearlmutter and Jeffrey Mark Siskind
   License    : BSD3

   Maintainer : bjorn.buckwalter@gmail.com
   Stability  : experimental
   Portability: GHC only?

Forward Automatic Differentiation via overloading to perform
nonstandard interpretation that replaces original numeric type with
corresponding generalized dual number type.

Each invocation of the differentiation function introduces a
distinct perturbation, which requires a distinct dual number type.
In order to prevent these from being confused, tagging, called
branding in the Haskell community, is used.  This seems to prevent
perturbation confusion, although it would be nice to have an actual
proof of this.  The technique does require adding invocations of
lift at appropriate places when nesting is present.

For more information on perturbation confusion and the solution
employed in this library see:

To install:
    cabal install

    runhaskell Setup.lhs configure
    runhaskell Setup.lhs build
    runhaskell Setup.lhs install

Define an example function 'f':

> import Numeric.FAD
> f x = 6 - 5 * x + x ^ 2  -- Our example function

Basic usage of the differentiation operator:

> y   = f 2              -- f(2) = 0
> y'  = diff f 2         -- First derivative f'(2) = -1
> y'' = diff (diff f) 2  -- Second derivative f''(2) = 2

List of derivatives:

> ys = take 3 $ diffs f 2  -- [0, -1, 2]

Example optimization method; find a zero using Newton's method:

> y_newton1 = zeroNewton f 0   -- converges to first zero at 2.0.
> y_newton2 = zeroNewton f 10  -- converges to second zero at 3.0.

Authors: Copyright 2008,
Barak A. Pearlmutter <barak@cs.nuim.ie> &
Jeffrey Mark Siskind <qobi@purdue.edu>

Work started as stripped-down version of higher-order tower code
published by Jerzy Karczmarczuk <jerzy.karczmarczuk@info.unicaen.fr>
which used a non-standard standard prelude.

Initial perturbation-confusing code is a modified version of

Tag trick, called "branding" in the Haskell community, from
Bjorn Buckwalter <bjorn.buckwalter@gmail.com>