Tech & Programming

Typeclasses from scratch (25 October 2021)

In this post, I want to introduce the concept of typeclasses (aka traits). Typeclasses are the primary way to do ad hoc polymorphism in languages like Rust and Haskell, and one option for it in Scala. They are comparable to interfaces in class-based object oriented languages, but have different tradeoffs.

More context on the SKI Combinator Calculus (19 February 2021)

A while back I published a post about SKI combinator calculus, and how it was computationally equivalent to lambda calculus. Specifically, you can mechanically convert from one to the other, and performing the computation on the SKI version or in the lambda calculus version will give you the same result.

Comparing Traits and Typeclasses (14 February 2021)

Rust and Haskell share a similar mechanism for polymorphism: traits in Rust and typeclasses in Haskell. This post explores their similarities and differences, as well as what’s next for both.

Elo ratings (26 November 2020)

Elo systems are used for ranking players in many competitions, including chess, sports like football (American or otherwise), e-sports, and board games. There are many variants in existence, but they ultimately derive from the version invented by Arpad Elo and implemented starting in the 1960s.

Debt simplification (25 September 2020)

This is a short post about algorithms for debt simplification: reducing a list of debts among a set of people to the smallest possible number of transfers. This is a common problem for groups of friends or roommates, and the solution is implemented in various apps and websites, such as Splitwise, Tricount, and others.

Monads! (19 June 2020)

I’m trying to be named least interesting blogger on the internet (I already have excellent supporting documentation in the form of my nearly-empty Apache access logs), so I thought I’d write something about monads.

Macro systems in Scheme (13 May 2020)

Notes on Scheme macro systems that I’ve taken while working on Peroxide, my R5RS implementation in Rust.

Cyclic Structures and Immutability (8 September 2019)

A piece of folk knowledge that doesn’t really seem to be explicitly laid out on the Internet is that in a language that (a) has no mutable data types, (b) isn’t lazy, you can’t create cyclic structures.

Implementing Unlambda (7 September 2019)

I recently implemented Relambda, a bytecode compiling Unlambda interpreter. In this post, I review Unlambda, Bytecode compilation, and the tricks I used to make them work together.

SKI Calculus (1 September 2019)

I recently implemented Relambda, an esolang interpreter based on SKI combinator calculus. This post explores SKI and its relationship to lambda calculus. A basic understanding of lambda calculus is useful.

Content-Defined Chunking (5 February 2019)

While investigating Restic the other day for my personal backups, I came across the cool concept of content-defined chunking (aka sliding-block chunking, content-based slicing, and a bunch of other names). It’s a simple idea, but I thought it was pretty cool.

Wave Function Collapse in Python (18 November 2018)

If you’re into game design (or maybe someting more exotic, like computer-generated art), you may have needed to generate large random patterns. Maybe because you want infinite levels, or because you’re just making randomly-generated levels for your cool roguelike, or you’re lazy pressed for time and would like some computer help to generate textures.

Building finite types (4 November 2018)

This post is about interesting properties of types in programming languages. It assumes you know about basic functional programming and types. A bit of Haskell syntax can be helpful but isn’t required.

Displaying 3D images in Python (10 December 2017)

May 2020 edit: updated package versions and made small adjustments to the code.

Comparing the size of Wikipedia languages (21 October 2016)

While doing preliminary work for a project that uses Wikipedia as a dataset to classify languages, I noticed some oddities in the size of certain language editions of Wikipedia. I collect some of my observations here.