\[ \DeclareMathOperator{\expt}{expt} \DeclareMathOperator{\mul}{mul} \DeclareMathOperator{\add}{add} \DeclareMathOperator{\derivative}{derivative} \]

Automatic differentiation is a technique that allows programs to compute the derivatives of functions. It is vital for deep learning and useful for optimization in general. For me, it’s always been dark magic, but I recently thought of a nice way to implement it and made a little library. This blog post takes you along the journey of discovering that implementation. Specifically, we will be implementing forward mode automatic differentiation for scalar numbers.

This post requires some knowledge of differential calculus. You’ll need to know basic derivative rules, the chain rule, and it’d help to know partial derivatives. If you’ve taken an introductory calculus course, you should be fine.

The code is in Racket. If you don’t know Racket, you should still be able to follow along. I’ll explain the Racket-y stuff. Don’t let the parentheses scare you away!

Regular expressions allow us to describe patterns in text. They are very useful and show up all over the place in programming, but matching regular expressions can be difficult. One well-known technique for matching regular expressions is converting the regular expression to a finite state machine. This is pretty elegant, but can get complicated and messy.

An alternative technique, which is the subject of this blog post, involves something called a Brzozowski derivative. This technique can be used to compute the derivative of a generalized regular expression.

Before there is any confusion, I’m not talking about JavaScript promises that are used for asynchronous computations. In this case, a promise is just a delayed computation. For example, a simple form of a promise is a function that takes in no arguments and returns a result. In this blog post, we will be focusing on promises that remember their results and promises that may evaluate to other promises. Promises are useful for control flow and implementing lazy semantics in a strict language.

In this blog post, we will learn what promises are and how to implement them efficiently. Promises are useful and interesting, but honestly, I mainly wrote this just to talk about the algorithm for forcing composable promises because I think it’s very cool!