Search This Blog

Saturday, November 21, 2026

Derivative flipping

{-# OPTIONS_GHC -Wincomplete-patterns #-}

I want to take a look at another way of thinking about automatic differentiation. I'm not going to give an actual AD algorithm but it will show how to implement some AD algorithms - possibly an easier way to think about some published work.

But first I want to talk about regular expression matching using the Brzozowski derivative. You can skip this bit but it's what I was thinking about as I wrote the code below.

Let's define the angle bracket operator \(\langle\cdot,\cdot\rangle\) by \(\langle R,S\rangle=1\) if \(R\) is a regular expression matching the string \(S\) and 0 if it doesn't match. I'll copy the definition from Wikipedia but modify the notation a bit

\[ \begin{aligned} \partial_a a &= 1 \\ \partial_a b &= 0 \qquad \text{for each symbol } b \ne a \\ \partial_a \varepsilon &= 0 \\ \partial_a \varnothing &= 0 \\ \partial_a (R^*) &= (\partial_a R)R^* \\ \partial_a (RS) &= (\partial_a R)S \lor \nu (R)\partial_a S \\ \partial_a (R \lor S) &= (\partial_a R) \lor (\partial_a S) \end{aligned} \]

(and some auxiliary definitions on Wikipedia).

If you've not seen it before that definition looks scary but it all comes down to one key property:

\[ \langle R,aS\rangle = \langle \partial_a R,S\rangle \]

So to find out if a regular expression matches a string \(S\) we can peel off the letters from the front of it one by one and apply the corresponding derivative operator to \(R\). We also need to do algebraic simplifications in the regexp algebra. If we end up with a regular expression that matches the empty string then the original regexp matched the original string. For more details on making this practical, see Regular-expression derivatives reexamined by Scott Owens, John Reppy, and Aaron Turon.

Although we may expect to get all manner of intermediate expressions when we keep differentiating, there is only a finite number of truly distinct expressions we get (considering two regexps equivalent if they match identical sets of strings). They form the states of a finite state automaton for recognising the regexp's target.

Let's mimic that for ordinary calculus. Given a pair of multivariate polynomials \(p\) and \(q\), define

\[ \langle p,q\rangle = \left. p(\partial_1, \partial_2, \ldots)\,q(x_1, x_2, \ldots) \right|_{x_1=x_2=\cdots=0} \]

We can go ahead and implement this in Haskell. Ultimately I'll define pair p q which is the pairing defined by the angle brackets.

First I'll define expressions in a ring generated by elements of v over a:

data Expr v a = Var v
              | Expr v a :+: Expr v a
              | Expr v a :*: Expr v a
              | Lit a
              deriving (Eq, Show)

And now we can give it the Num interface:

instance Num a => Num (Expr v a) where
  fromInteger = Lit . fromInteger
  (+) = (:+:)
  (*) = (:*:)
  negate x = Lit (negate 1) * x
  signum = undefined
  abs = undefined

I should add simplification but there's no real need when this code is purely pedagogical. And now we implement the rules that interpret p as a differential operator acting on q.

apply :: (Eq v, Num a) => Expr v a -> Expr v a -> Expr v a

This says \(\partial_i x_j=\delta_{ij}\):

apply (Var v) (Var w) | v == w = 1
apply (Var v) (Var w) = 0

Linearity:

apply (a :+: b) c = apply a c + apply b c

I find this interesting. Multiplication on the right of a \(\langle\cdot,\cdot\rangle\) is ordinary polynomial multiplication but on the left it is composition of differential operators:

apply (a :*: b) c = (apply a . apply b) c

apply a@(Lit _) b = a * b
apply a (b :+: c) = apply a b + apply a c

The usual Leibniz rule:

apply v@(Var _) (b :*: c) = apply v b * c + b * apply v c

apply v@(Var _) (Lit _) = 0

And now we evaluate at zero. Note that this corresponds to the situation with regular expressions where you ask if the residual expression matches the empty string:

atZero :: (Num a, Eq v) => Expr v a -> a
atZero (Lit a) = a
atZero (Var _) = 0
atZero (a :+: b) = atZero a + atZero b
atZero (a :*: b) = atZero a * atZero b

And finally the pairing:

pair a b = atZero (apply a b)

Now comes the magic bit. We have two theorems:

\[ \langle p,x_i q\rangle = \langle \partial_i p,q\rangle \]

And more surprisingly, maybe, given that the interpretation of polynomials on the left is so different to polynomials on the right:

\[ \langle p,q\rangle = \langle q,p\rangle \]

So let's set up an example:

main = do
  let x = Var 0
  let y = Var 1

With this definition:

  let lap = x * x + y * y

\(\langle \mathrm{lap},q\rangle\) is the Laplacian of \(q\) evaluated at \(x = y = 0\).

  print $ pair lap ((x + y + 1) * (x - 3 * y + 2) * (x + y + 3))

But now comes the plot twist:

  print $ pair ((x + y + 1) * (x - 3 * y + 2) * (x + y + 3)) lap

Instead of applying a simple differential operator to a complicated expression, we are applying a complicated differential operator to a simple expression. No matter how complicated an expression \(p\) we apply, the intermediate results of applying it to \(q\) are always bounded in complexity. For example in this case we are only ever going to get linear combinations of

\[ x^2+y^2,\quad \partial_x(x^2+y^2)=2x,\quad \partial_y(x^2+y^2)=2y,\quad \partial_x(2x)=2 \]

and that's it. Anything else that pops up is just going to be a linear combination of these. Which means that if we're interested in computing the Laplacian in 2D we only ever need to track 4 coefficients. We don't need to keep track of the full Hessian. In fact we can replace the polynomial on the right of the pairing with a 4-vector and replace apply with code to act directly on that representation.

We have just rediscovered the method for computing Laplacians I described many years ago at Computing errors with square roots of infinitesimals. But now it's more general and we can use this for any constant differential operator. For example the biharmonic operator corresponds to the polynomial \((\sum_i x_i^2)^2\). When you compute all of the possible expressions that can arise from applying the \(\partial_i\) operator it forms a far smaller space than you might get from naively carrying along the power series up to degree 4.

Final Words

After I proposed my original Laplacian method it was eventually rediscovered and turned into well-optimized code at folx. It's used in many places such as PINNs and VMC.

Compare also with this paper: Collapsing Taylor Mode Automatic Differentiation

ChatGPT keeps wanting to turn this into a subject called apolar algebra (which shows that many AD problems were solved over a century ago) but the key construction there is a quotient and quotients are hard to work with.

FWIW I fully embrace our new AI overlords but I actually wrote all of this myself giving Codex the role of formatting it for blogger.com

I need to mention that the idea that you can flip the role of differentiator and differentiated expression plays a major role in quantum mechanics. And lastly, this pairing is central to umbral calculus.

Blog Archive