Posts tagged tutorials

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!