The Silent Llama of Doom

Putting A Lid On IT: Linux Containers

Tue 26 January 2021

I’m a little late to the container party which has been raging, I suppose, since about 2013 when Docker hit it big or alternatively in 2005 when Solaris Zones were a thing or maybe even 2000 when FreeBSD jails were introduced. It’s been going for a long time is what I’m trying to say. We’re in that weird after period when all the snacks are gone and the small talk has been exhausted and people are checking their watches. So, hey, this is probably a good time to arrive right?

There are a ton of blogs about containers but they are all almost universally Docker centric (with some LXC and podman thrown in here and there). In this post I’m going to go over all the lower level details.

What are containers?

This is a surprisingly difficult question to answer. On Linux containers are less a ‘thing’ and more the intersection of a whole lot of things. Explanations like “They’re Virtual Machines without, you know, the virtual machine” don’t help all that much. In order to really understand what containers are we need to understand a little bit about virtualisation.

Virtualisation happens when software lies. Yep - it’s an entire specialisation based on dishonesty. Consider a VM - it’s not a real machine, it’s just some process pretending to be a machine. Dishonest. Our OS even virtualises our processes - we write our programs as if we have a cpu all to ourselves …

Doing my Daughter's Homework with the Z3 SMT Solver

Sat 17 October 2020

My nine year old daughter came to me the other day with a difficult math problem. When I looked I realised that she was right - whoever was setting the homework that day hadn’t realised just what they were asking for.

I can’t remember the exact wording but the problem was as follows:

In South African currency, using only bank notes, find all the different ways
you can make R400. How can you be sure you've found all the different
combinations?

I suspect the intention was to use a single note for each combination. In South Africa we have R10, R20, R50, R100 and R200 notes. If we use only a single note each time we get 5 combinations:

40 x R10

20 x R20

8 x R50

4 x R100 and

2 x R200

Stated that way this would indeed be appropriate for a Grade 3 child. However it was not stated like that and the question wanted all possible combinations. I thought about it for a moment and realised that far from being an easy question I actually didn’t know how to go about solving this!

Z3 to the Rescue

For some work research I’ve been playing around with Microsoft’s Z3 Theorem Prover recently. It’s a fascinating piece of software - it’s meant to solve Satisfiability problems. A Satisfiability problem is one where we are given a set of constraints and we need to find some solution that satisfies those constraints. The …

Fractals: the Mandelbrot Set

Sat 01 February 2020

We’re going to temporarily set aside L-systems to look at a different type of fractal. As we’ve seen creating fractals involves repeating a process over and over again. We’ve seen this with simple drawings of triangles and squares and moved up to more complex patterns involving branching and randomness. We’re now going to take a detour in to the world of mathematical functions. I’m going to try and explain everything from the ground up - all I’m assuming is that you have some basic high school math.

Math Functions?

Repeating shapes makes intuitive sense but what can we achieve by repeating a math function? The example I’ve seen in several textbooks is one you’ve probably already played with. When you first get a calculator with a square root function a lot of people instinctively start pressing the button over and over again to see what happens. You’ll notice that eventually, no matter how big the starting number, you hit zero. This is an example of an iterated function. This should sound familiar - it’s exactly the same idea we’ve been using for our previously fractals - iterating the same process on itself.

Let’s start a new Rust project making sure we have the image library available:

$ cargo new mandelbrot

:::rust
// Cargo.toml
[dependencies]
image = "*"

Alright so which math functions are we going to try? I’m not going to jump straight into the fractal, I’m going to try and sneak …

Fractals: Plants and Stochastic L-systems

Sat 18 January 2020

One particular type of fractal that I find compelling is the ‘plant fractal’. These are fractals that model plant growth.

In fact Aristid Lindenmayer, the man L-systems are named after, was a biologist studying the growth patterns of plants and he devised the L-system approach because it helped model those patterns.

Branching

Naturally the first thing we are faced with is the problem of branching. How do we instruct our turtle to draw a stem and branch and then to return to where it started to continue the stem? We could, I suppose, create a rule that creates a branch and then reverses itself to get the turtle back to where it started but that sounds too complicated.

Lets imagine an extension of our L-system rules. We add the following to our rule alphabet: [ and ]. Think of these exactly like parentheses in English. A sentence can have a main topic (and then have some other information added on) and return to that topic after the parenthetical statement. In the same way a turtle can draw something and then arrive at some instructions enclosed in our [] ‘parentheses’. It will execute the instructions in the parentheses and then return to what it was doing before.

The question is how to implement this? We need to supply our turtle with some sort of memory. Let’s do that:

// turtle.rs

struct Position {
    x: i32,
    y: i32,
    angle: f32,
}

We add a Position struct that saves the exact position and angle of our turtle …

Fractals: More L-Systems

Mon 13 January 2020

This post follows on from the previous posts on fractals.

Fractals with JSON

It’s a little annoying to have to recompile our program for every change. It would be better to define our pattern and rule in a seperate file and pass them in. Let’s first create a FractalDefinition struct that we can use to define how we want to draw things.

Create a fractal_def.rs file and add the following:

// fractal_def.rs
use serde::Deserialize;
use std::collections::HashMap;

#[derive(Deserialize)]
pub struct FractalDefinition {
    pub axiom: String,
    pub rules: HashMap<char, String>,
    pub iterations: u32,
    pub angle: f32,
    pub forward: f32,
    pub start_x: u32,
    pub start_y: u32,
    pub start_angle: f32,
    pub width: Option<u32>,
    pub height: Option<u32>,
}

We’ll need to change our Cargo.toml as well:

[dependencies]
image = "*"
imageproc = "*"
serde = { version = "1.0", features = ["derive"] }
serde_json = "1.0"

We’ve added the serde Rust library. This library makes it easy to serialize and deserialize data. We’ll use it to load our fractal definitions from json files. Let’s add in some code to read the definition from the command line:

// main.rs
// -- snip --
use fractal_def::FractalDefinition;
use std::env;
use std::fs::File;
use std::io::BufReader;
// -- snip --

fn main() {
    // Read all our command line arguments into a vector of Strings
    let args: Vec<String> = env::args().collect();

    if args.len() == 1 {
        println!("Please supply a fractal definition file");
        return;
    }

    // The first argument needs to be the fractal definition json file:
    let …

How to draw Fractals - L-Systems

Wed 08 January 2020

In the last post we ended up with a renderer for a Koch Snowflake. It took a lot of effort and explaining. In this post we’ll go over a system that allows us to draw various different fractals using exactly the same framework. It’s much easier to understand and code.

It’s All Relative

Part of what made drawing the previous fractal difficult was having to keep track of all the coordinates and angles. It’s a lot like trying to give directions as a list of GPS coordinates. While that might be a good fit for a robot we humans tend to give directions in a completely different way. If you wanted to get to my daughter’s school I might tell you to travel down the road and take the first left and then the next right. I don’t have to specify where you are - if you’re following the directions each next instruction will make sense.

This is the difference between absolute coordinates and relative coordinates. Relative coordinates are always given depending on where you are at that moment.

Imagine drawing the Koch fractal with relative coordinates. I could simply tell you to draw a line and then turn left 60 degrees. I could tell you to draw another line, turn right 120 degrees, draw another line turn left 60 degrees and draw the final line. That’s a lot easier and doesn’t involve any trigonometry at all.

Turtles all the way down …

How to Draw Fractals - The Basics

Mon 30 December 2019

I love fractals. I love the idea that a few simple rules can produce images of stunning complexity. I remember reading about them as a kid and thinking that you had to be an advanced mathematician to be able to understand or produce anything like them. Now that I’m older I’ve realised that, while they are complex, they can be understood and appreciated by us mere mortals. In this series of blog posts I hope to show how accessible they can be.

So, what is a Fractal?

Wikipedia defines Fractals in terms of something called a ‘fractal dimension’ which is… not the simplest thing for the non-mathematician to understand. The man who coined the term ‘fractal’, Benoit Mandelbrot, defined fractals as “a shape made of parts similar to the whole in some way”.

In the absolute simplest terms a fractal is what happens when you take some process and then repeat it over and over again. That’s basically it.

It’s easiest to understand with an example. Let’s start with a pattern:

Now we’re going to replace each line in the above pattern with the same pattern again:

And again:

Last time:

This is an example of a fractal called a Koch Snowflake. This demonstrates the essence of all fractals - we take a simple procedure, in this case replacing lines with a triangular shape, and then we keep repeating the procedure over and over again. The fancy math term for this is an iterated function …

The Halting Problem

Sat 21 July 2018

Most people who have used a computer will have run into a program that suddenly hangs for, seemingly, no reason. The program freezes and won’t respond to anything you do. As a programmer I run into these depressingly often - usually because I made some mistake when I was coding. One of the reasons this happens is simple: computer programs do exactly what you tell them to. They’re like Golems. The clay creatures obey anything their master tells them to do, absolutely and to the letter. So if you ask one to, say, dig a trench it will. It will continue digging the trench indefinitely until it circles the world and then, for a change of pace, it’ll keep digging. You need to specify very carefully when it has to stop - maybe after 20 metres, or when the trench reaches a river or after an hour. There has to be some end condition. Computer programs are just like Golems - if you don’t tell them when to stop they’ll keep running in circles forever.

This is one of the causes of hanging programs (there are others but we’ll only consider this one today). Sometimes a program can get into a loop and won’t have any way to get out - we call this an infinite loop. It happened to me the other day when I wrote a program to read an excel file. The program was supposed to read each row into memory so I could …