0.32.0: Reverse-mode AD is here!

This release has been a long time coming, and introduces some substantial improvements to Emmy. The top-line items are:

Reverse-mode automatic differentiation

Forward-mode AD is now much simpler to understand; the implementation lives in emmy.dual. emmy.tape and emmy.autodiff round out our AD implementations.

Our reverse-mode AD implementation is faster for everything in the library, but substantially faster for functions with many inputs and few outputs (like Lagrangians). See the new D-forward, D-reverse, partial-forward and partial-reverse for more control over which you like.

Native Complex and Fraction

@littleredcomputer implemented our Fraction.js and Complex.js dependencies in pure CLJS, letting us remove these JS dependencies. This opens the door for symbolic complex numbers and more fun down the road.

Value protocol => multimethods

The emmy.value/Value protocol is now gone, in favor of a "multimethods everywhere" approach. If you want speed you can compile your functions... otherwise simple is better, and this keeps us closer to the scmutils style.

Excellent docs on https://2.maria.cloud

Thanks to @mhuebert, SCI now properly grabs all docstrings and arglists from all Emmy functions, making for an excellent user experience.

Faster compilation

@littleredcomputer (in #143) replaced thee the implementation of common subexpression elimination with the algorithm described in Flajolet's 1990 paper (cited within). This speeds up (and makes possible at all) compilation of some of the big, nasty functions we ran into generating manifolds in examples like https://sritchie.github.io/strange-loop-2023/notebooks/stl/pq_knot

All CHANGELOG entries

• #170:

  • changes D and partial to use reverse mode automatic differentiation by default, and fixes all associated tests

  • adds emmy.generic/{zero?,one?,identity?} implementations (all false) to emmy.tape/Completed, in case some collection type tries to simplify these during reverse-mode AD

• #185:

  • adds a dynamic variable emmy.calculus.derivative/*mode* that allows the user to switch between forward and reverse mode automatic differentiation

  • adds a new emmy.calculus.derivative/gradient that acts like emmy.tape/gradient but is capable of taking multiple variables

  • adds new operators emmy.calculus.derivative/{D-forward, D-reverse} and operator-returning-functions emmy.calculus.derivative/{partial-forward, partial-reverse} that allow the user to explicitly invoke forward-mode or reverse-mode automatic differentiation. D and partial still default to forward-mode

  • modifies emmy.tape/gradient to correctly error when passed invalid selectors, just like emmy.dual/derivative.

• #183:

  • adds emmy.{autodiff, tape} to emmy.sci's exported namespace set

  • adds emmy.dual/extract-id implementations for all supported output types (every type that already implements emmy.dual/IPerturbed)

  • moves emmy.tape/Completed to emmy.dual/Completed; it doesn't really make sense there, but this is the only current way to remove the circular dependency between emmy.dual and emmy.tape. (tape needs a dual import to gain emmy.dual/IPerturbed.)

  • simplifies the emmy.tape/gradient implementation down to only handle single real-or-structural arguments, just like emmy.dual/derivative. We'll share the "handle-multiple-input" implementation between the two in a follow-up PR

  • makes the tests in emmy.calculus.derivative generic on the derivative implementation, so we can run all tests in forward and reverse mode.

• #182:

  • moves the generic implementations for TapeCell and Dual to emmy.autodiff

  • moves emmy.calculus.derivative to emmy.dual/derivative

  • removes emmy.dual/perturbed? from IPerturbed, as this is no longer used.

• #180 renames emmy.differential to emmy.dual, since the file now contains a proper dual number implementation, not a truncated multivariate power series.

• #179:

  • Moves the IPerturbed implementation for functions to emmy.function, out of emmy.calculus.derivative

  • Adds a new mode parameter to emmy.differential/extract-tangent, in preparation for allowing reverse and forward mode across all output types

• #175:

  • Adds emmy.env/{tau,-tau} constants for the $\tau$ fans out there

  • Adds ^:const metadata to all constants, reaping small performance wins

  • Updates emmy.numerical.unimin.brent/{brent-min,brent-max,brent-min-commons,brent-max-commons} to:

    • take a new :initial-guess argument, useful if you have some idea of where the minimum might lie

    • swaps the relative and absolute threshold defaults to match those from scmutils

    • adjusts the initial guess from the midpoint between a and b to a golden section cut (closer to a), to match scmutils

• #156:

  • Makes forward- and reverse-mode automatic differentiation compatible with each other, allowing for proper mixed-mode AD

  • Adds support for derivatives of literal functions in reverse-mode

• #165:

  • Fixes Alexey's Amazing Bug for our tape implementation

  • Adds the id field back into TapeCell, required for the tag replacement machinery for fixing Alexey's Bug

  • Adds an emmy.differential/IPerturbed implementation to TapeCell

  • Fixes some old documentation referencing :in->partials, plural

  • Updates emmy.tape/tag-of to return nil in case of a non-tape argument vs ##-Inf, again preparation for forward/reverse interactions

  • Adds support for partial derivatives via a selectors argument to gradient

  • Fixes a bug in the g/abs implementation for TapeCell, where (g/abs <tape>) would return a positive primal

  • Adds a simplify implementation for TapeCell

• #163:

  • replaces the emmy.differential.Differential generalized dual and its term list algebra with a simplified emmy.differential.Dual number type

    This new approach works because the emmy.differential/*active-tags* stack allows us to make sure that lifted binary operations always wrap their output in a new Dual with the tag assigned by the inner-most derivative call.

  • deletes emmy.util.vector-set and tests, as these are no longer used

  • adds a nil implementation for extract-tangent, meaning that nil-valued functions now work with D

• #159:

  • Fixes Differential's implementation of emmy.value/numerical? to always return false. The reason is that numerical? is used by g/* and friends to decide on simplifications like (* <dx-with-1> x) => x, which would lose the structure of dx-with-1. By returning false we avoid these simplifications.

  • Converts a number of emmy.value/numerical? calls to emmy.value/scalar?. The numerical? protocol method is used only in generic functions like g/* for deciding whether or not to apply numerical simplifications, like (* x 1) => x.

    Guarding on v/scalar? instead allows us to let in numbers, tapes and differentials, since these latter two are meant to WRAP numbers, but should not be subject to numerical simplifications.

  • Adds emmy.structure/fold-chain for performing a tree-like fold on structures, saving us work over the alternate pattern of s/mapr, flatten and reduce.

• #155

  • Replace the implementation of arbitrary-precision rational arithmetic provided by fraction.js with Clojure code, allowing us to remove a JavaScript dependency.

  • We note here a subtlety with fraction reader syntax. When the CLJS compiler runs and encounters input like #emmy/ratio 1/2, since the compilation occurs in a JVM Clojure environment the 1/2 will deserialize as a Ratio, which is then transformed by the reader into code which will generate a ClojureScript Fraction. The ClojureScript reader, however, evaluates the input as q JS expression resulting in 0.5, which is then rationalized with an expensive algorithm which may lose exactness because of the unwanted floating-point conversion. For this reason, when we emit a ratio in string form, we quote the arguments: #emmy/ratio "1/2" to prevent the conversion. Consider this a deprecation notice for the unquoted form. We also now allow the form #emmy/ratio [1 2], like Complex, and now no longer allow an initial + on the numerator.

• #154:

  • Adds emmy.tape with an implementation of reverse-mode automatic differentiation. The implementation is based on Alexey Radul's implementation in dvl, and seems to be higher-performance by quite a bit and capable of replacing our forward-mode implementation.

    • The centerpiece of the implementation is emmy.tape/gradient, which can handle $R^n \to R^m$ functions, as well as nested derivatives.

    • All operations supported by [[emmy.differential/Differential]] are supported by the backing [[emmy.tape/TapeCell]] instance.

• #151

  • By porting complex.js to Clojure, we can remove the dependency on this library on the JavaScript side as well as the Apache Commons complex implementation on the JVM side.

    The JavaScript implementation is followed fairly closely and done with generic Emmy arithmetic at the component level (except when that is clearly unnecessary). The (complex) constructor has been made equivalent to the reader parser.

    The former implementation made a special case of i^r, raising the complex unit to a real power, but it only worked for integral r, and threw an exception in other cases; this special case is removed.

• #149

  • Retires the Value protocol in favor of MultiFns in the generic scope. Doing this carefully, by revoking the existing implementation and then restoring it step by step, revealed some interesting corner cases:

    • (zero? [0]) but (not (zero? (lazy-seq [0])))
    • (not (zero? (series 0)))

    The only remaining element of the Value protocol was the kind function, used to classify arguments for multi-dispatch. The protocol has therefore been renamed IKind.

  • Changed behavior:

    • Objects produced by make-literal

      In the protocol regime, the implementation of zero? was dispatched via the Literal class; with the MultiFn, it is dispatched by the kind, which is supplied by the creator. The protocol dispatch effectively used numeric-zero?. That behavior is replicated for the kind :emmy.expression/numeric; if you create literals of a different kind, you can inherit this behavior using derive or supply a defmethod yourself.

    • We now prefer to let Clojure internals report an exception whenever an unimplemented MultiFn in what was formerly the emmy.value/Value protocol instead of defining a method that throws. The exception thrown in such cases therefore changes from UnsupportedOperationException to IllegalArgumentException.

    • For this reason we have avoided defining :default handlers for generic MultiFns, despite the fact that defaults are certainly convenient in some cases (like false for exact? and having the default case for freeze pass through).

    • The default exponentiation routine built on generic multiplication would, in the case of raising to the zero power, return the one-like of the exponent; now it returns the one-like of the base, which is correct.

    • The generic negative? required Numbers instead of Comparables; this is fixed.

    • Documentation string for pochhammer corrected.

• #145 (thank you to @mhuebert for amazing work here!!):

  • Adds emmy.util/sci-macro for defining macros meant to be exposed via SCI, without requiring redefinition as a fn.

  • Modifies emmy.sci so that SCI has access to all of the metadata we need for a great experience on https://2.maria.cloud and other platforms that use SCI.

  • Removes some unused kondo/ignore metadata and upgrades clj-kondo to 2023.07.13, which caught a couple more errors like a test with no assertion and a block of tests accidentally included in another test block.

  • Upgrades emmy.calculus.coordinate/define-coordinates and emmy.util.def/{import-vars,careful-def} to play nicely with SCI.

  • Resolves the ambiguous simplify implementation for subvectors.

  • Adds docstrings to the aliased macros in emmy.env.

  • Exposes emmy.calculus.coordinate/coordinate-functions as emmy.env/coordinate-functions.

• #143:

  • Replace the implementation of common subexpression elimination with the algorithm described in Flajolet's 1990 paper (cited within). This algorithm does not have any dependence on hash collection ordering, so the deterministic? flag has been removed.

  • Update unit test expected data to remove symbol namespaces that may differ between clj and cljs. Restore a test found not to be stable in cljs that has become so with the simpler Flajolet algorithm.

  • The structure of the emitted code changes with this revision, to a more assembly-like form in which operations are fanned out into a sequence of two-operand forms in the commutative cases, boiling down to the return of a single symbol.

• #142 fixes advanced compilation warnings and bumps Clerk to a new version.

New Contributors

• @ingydotnet made their first contribution in #171
• @yuhan0 made their first contribution in #172