Welcome

Have you ever needed to process some raw text and extract only parts of it? Most of the time, you can get by with some nasty regular expressions with groups, but sometimes the pattern that you’re trying to process is too complicated for regular expressions. That’s what parsers are good for, and they’re also the first step in an interpreter/compiler!

In this post, we’ll discover parsers and create a domain-specific language for creating parsers in Racket.

In this post, we’re going to implement an algorithm for computing the \(n\)th fibonacci number. We’ll gradually optimize it and eventually end up with an algorithm that takes \(O(\log n)\) steps, which is much better than the \(n\) steps that most implementations take. I’ll assume some familiarity with complexity analysis. If you know big O notation, you’ll be fine.

Math, at its core, is a network of facts that are undoubtably known to be true. We start out with some simple assumptions called axioms and prove new facts to be true using logic and reasoning. As long as the proofs are valid, then under the founding assumptions, anything that can is proven is definitely true. But when you’re proving something in math, how do you actually know if you’re doing it right? What if you make a mistake? What if you gloss over proving something which is "obviously true" that turns out to be false? One way to be sure is to have a computer check your proof, which is what we’re going to do. But first, we’re going to have to build math from the ground up.

Have you ever played Minesweeper? If you have, you’ve probably run into a situation where you’re forced to guess, hoping you’re not about to step on a mine and lose the game. What if I told you it was possible to make it so you never have to guess in a game of minesweeper?

In this post, I’ll explain how I made a minesweeper solver and how I used the solver to generate guess-free minefields.

Algebraic effects are kind of like exceptions that you can resume from. They can be used to express computational effects like non-determinism, generators, multi-threading, and of course, exceptions. They are a slightly less confusing alternative to using raw continuations via operators like call/cc and have other benefits like dynamic interpretation.

In this post, we will discover and implement algebraic effects using continuations in Racket. I will assume you are familiar with Racket and continuations. If you’re not, I have the perfect post for you!

Macros are a powerful tool that allow programmers to extend the syntax of a language. In a language with macros, features like for-loops, while-loops, and pattern matching can be implemented as a library by users of the langauge! In this post, we’ll discover what macros are, how and why to use them, and how to implement a tiny language with a simple macro system.

For this post, you’ll need some familiarity with Racket, but no familiarity with macros is required. If you don’t know what something is, click on the variable name in the code and you’ll be taken to its documentation.

call/cc is a powerful tool for implementing custom control forms operators. However, call/cc can be pretty unwieldy, so people tend to use delimited, composable continuations with operators like reset and shift. But what if I told you that these operators can be implemented using just call/cc?

In this post, we’ll implement delimited continuations, composable continuations, dynamic-wind, and parameters all from just call/cc. I will assume a solid familiarity with continuations and Racket. If you aren’t very familiar, then feel free to check out my continuations post to get some background. But even having read that, you sould play around with them a lot to get familiar, because this post is pretty heavy on continuation weirdness!

Pattern matching is a very powerful tool used to destructure and perform case analysis on data. It’s commonly found in more academic functional languages and has recently made its way into Python. In this post, we’ll discover pattern matching and implement it in Racket.

I will assume that you have some familiarity with Racket. We’re going to be writing some macros, but general familiarity with macros should be enough, we’re not doing anything fancy.

You may have heard of the lamdba calculus. It is a model of computation where everything is either a function, a variable, or a function call. It is the essence of functional programming and the theoretical foundation for modern functional programming languages. Even though it is very simple, it is just as powerful as any programming language since it is Turing-complete.

The pi calculus is a similar idea, but instead of functional programming, it is the essence of concurrent programming. For our purposes, it will serve as a simple example of a programming language with concurrency. In this post, we will explore and implement the pi calculus in Racket. This will give an idea of how modern programming languages implement concurrency.

This post requires some familiarity with Racket or any Lisp-like language. If you have read some of my Racket posts which explain Racket stuff, you should be fine. If you see something you don’t understand in the code, you can click on it and the link will take you to its documentation.

In this post, we explore a simple and elegant algorithm to find the (real) zeros of a polynomial using recursion and derivatives.