Rainbow – an attempt to display colour on a B&W monitor
The aim of this project was to display a colour image on a black and white monitor, by overlaying an acetate bayer filter over the monitor and mosaicing a colour image.
SAT solver on top of regex matcher
A SAT problem is an NP-problem, while regex matching is not. However, a quite popular regex ‘backreferences’ extension extends regex matching to a (hard) NP-problem.
KVM host in a few lines of code
KVM is a virtualization technology that comes with the Linux kernel. In other words, it allows you to run multiple virtual machines (VMs) on a single Linux VM host. VMs in this case are known as guests. If you ever used QEMU or VirtualBox on Linux - you know what KVM is capable of.
But how does it work under the hood?
The Success and Failure of Ninja
Ninja has been by far my most successful open source project, depending on how you quantify success. (Other projects of mine like Chrome have more users, but I was responsible for only parts of Chrome; Ninja also has had important contributions by collaborators but it feels more like “mine”.) I released Ninja in 2011, gave ownership of the Ninja project away in 2014, and it has since been passed on again to a third maintainer, so now that my part in the story is pretty much over I here would like to reflect on what I learned.
Ten Lessons I Wish I Had Learned Before I Started Teaching Differential Equations
One of many mistakes of my youth was writing a textbook in ordinary differential equations. It set me back several years in my career in mathematics. However, it had a redeeming feature: it led me to realize that I had no idea what a differential equation is. The more I teach differential equations, the less I understand the mystery of differential equations.
Introducing Glush: a robust, human readable, top-down parser compiler
It’s been 45 years since Stephen Johnson wrote Yacc (Yet another compiler-compiler), a parser generator that made it possible for anyone to write fast, efficient parsers. Yacc, and its many derivatives, quickly became popular and were included in many Unix distributions. You would imagine that in 45 years we would have further perfected the art of creating parsers and would have standardized on a single tool. A lot of progress has been made, but there are still annoyances and problems affecting every tool out there.
This is great, even just for the overview of parsing.
The CYK algorithm (named after Cocke–Younger–Kasami) is in my opinion of great theoretical importance when it comes to parsing context-free grammars. CYK will parse all context-free parsers in O(n3), including the “simple” grammars that LL/LR can parse in linear time. It accomplishes this by converting parsing into a different problem: CYK shows that parsing context-free languages is equivalent to doing a boolean matrix multiplication. Matrix multiplication can be done naively in cubic time, and as such parsing context-free languages can be done in cubic time. It’s a very satisfying theoretical result, and the actual algorithm is small and easy to understand.
The history of Tetris randomizers
In Tetris, a randomizer is a function which returns a randomly chosen piece. Over the years, the rules of how pieces are chosen has evolved, affecting gameplay and actual randomness.
Several of them have been reversed engineered and documented. I’ve curated a list of ones that I believed to be important and show how the state of Tetris has changed over the years.
Running from the past
Functional programming encourages us to program without mutable state. Instead we compose functions that can be viewed as state transformers. It’s a change of perspective that can have a big impact on how we reason about our code. But it’s also a change of perspective that can be useful in mathematics and I’d like to give an example: a really beautiful technique that alows you to sample from the infinite limit of a probability distribution without needing an infinite number of operations.
Solving Rush Hour, the Puzzle
How I created a database of all interesting Rush Hour configurations.
Parsing: a timeline
The results of 1961 transformed the Operator Issue. Before ALGOL, parsing operator expressions essentially was parsing. After ALGOL, almost all languages will be block-structured and ad hoc string manipulatons are no longer adequate -- the language as a whole requires a serious parsing technique. Parsing operator expressions becomes a side show, or so it seems.
From Markov to now. With references.
CSS3 Patterns Gallery
Go & Versioning
We need to add package versioning to Go. More precisely, we need to add the concept of package versions to the working vocabulary of both Go developers and our tools, so that they can all be precise when talking to each other about exactly which program should be built, run, or analyzed. The go command needs to be able to tell developers exactly which versions of which packages are in a particular build, and vice versa.
Shortest Addition Chains
A finite sequence of positive integers a0, a1, ..., ar is called an addition chain iff for each element ai, but the first a0 which equals 1, there exist elements in the list with smaller indexes j and k such that ai = aj + ak.
Preciser this is called an addition chain of length r for its last number ar. It can be interpreted like calculating n = ar starting from 1 by addition of only previous calculated numbers.
Social Decay: Illustrations by Andrei Lacatusu
Photo realistic images of company logos as abandoned diner signs.
A Water-based Solution of Polynomial Equations
Quinto: Resurrecting an Abandoned Board Game
Quinto is basically Scrabble, except with numbers instead of letters.
OBNC is a compiler for Niklaus Wirth’s programming language Oberon. It implements the latest version of the language from 2016. OBNC translates source code written in Oberon to the lower-level programming language C. The translated code is then compiled and linked with the C compiler and linker of the host operating system. The build command obnc performs all these tasks and keeps track of which files need to be compiled or recompiled.
Numba gives you the power to speed up your applications with high performance functions written directly in Python. With a few annotations, array-oriented and math-heavy Python code can be just-in-time compiled to native machine instructions, similar in performance to C, C++ and Fortran, without having to switch languages or Python interpreters. Numba works by generating optimized machine code using the LLVM compiler infrastructure at import time, runtime, or statically (using the included pycc tool). Numba supports compilation of Python to run on either CPU or GPU hardware, and is designed to integrate with the Python scientific software stack.