Programming

Classical concurrent data structures such as FIFO queues are foundational in many different applications. It is very simple to implement such a queue by wrapping a sequential implementation in a mutex. However, lock-free designs are often preferred, as they can give better scalability and progress guarantees than ones relying on locks. The classic lock-free FIFO queue is the Michael-Scott queue (MS queue), which is a neat lock-free linked list. Lock-free designs are inherently tricky to implement, and linked lists are known to be troublesome in Rust, so this post details my journey of implementing this MS queue in Rust.

This was my fourth year doing Advent of Code, my second year trying to compete, and my first year appearing on the top 100 leaderboard (if only for a single day). Last year lit a fire in me to become faster, and since then I have built my programming language Zote, practiced some competitive programming, and learned to touch type using Colemak. This will be a short retrospective on this year's event, as well as my preparation leading up to it.

Do you lay awake at night contemplating the best scheme for variable bindings? Neither do I. However, I have thought a bit about it recently and realized it is not as simple or obvious as I once thought. In this post I give a short introduction to the late and early binding schemes and discuss their respective advantages and disadvantages.

I don't think I will ever completely understand Rust lifetimes. Every time I think I get them, they come right back and hit me in the face. The other day I wanted to implement scoped variable bindings for my new programming language Zote, and it took me several hours to figure out why it did not work as I expected. So let's talk a bit about lifetimes, for both of our sakes.