Ilse BredeAlgorithms and verified systems
Menu
Write to me

Open-source work

Projects that ship with their proofs

Four maintained libraries, each tied to a paper. They are small, tested against the bounds the paper claims, and released under permissive licences.

Benchmark plot of kestrel query time against graph size
Figure 1. Benchmark plot of kestrel query time against graph size. Papers: [1], [5].

kestrel

Shortest paths on compressed graphs

  • Rust library
  • 2,340 stars
  • MIT licence
  • v0.9.2, August 2026

The reference implementation of Theorem 1. It reads a graph once, compresses it into blocks of sorted adjacency, and answers single-source queries without expanding it. On a 24-million-edge road network it uses 41% of the memory of a plain adjacency list.

Listing 1. Query and check the certificate
let g = kestrel::Graph::from_edges(&edges)
    .compress(4);          // k = 4
let tree = g.dijkstra(source);
assert!(tree.certificate().check(&g));

Source and documentation

Diagram of the tallow queue: heap nodes, helping array and proof outline
Figure 2. Diagram of the tallow queue: heap nodes, helping array and proof outline. Papers: [2], [7].

tallow

A wait-free priority queue, with its proof

  • Rust and proof scripts
  • 610 stars
  • Apache-2.0 licence
  • v1.0.0, September 2026

A concurrent priority queue where every operation finishes in a bounded number of its own steps, whatever other threads do. The repository holds the code and the machine-checked proof side by side, and CI fails if they drift apart.

Listing 2. Push and pop from any thread
let q = tallow::Queue::with_threads(8);
q.push(17, job);
if let Some((key, job)) = q.pop_min() {
    run(job);
}

Source and documentation

Two panes: paper source on the left, rendered theorem page on the right
Figure 3. Two panes: paper source on the left, rendered theorem page on the right. A tool, not tied to one paper.

quire

Theorem environments for the web

  • Python tool
  • 1,180 stars
  • MIT licence
  • v2.3.0, May 2026

Converts theorem, lemma, proof and algorithm blocks from a paper source into accessible HTML with stable anchors, so lecture notes can be read on a phone and cited by paragraph. This site is set with its stylesheet.

Listing 3. Build lecture notes
$ quire build notes/ --out site/
# 14 theorems, 9 figures, 3 algorithms
# anchors: thm-1 … thm-14

Source and documentation

Sorting visualisation with bars, two compared elements highlighted and step controls
Figure 4. Sorting visualisation with bars, two compared elements highlighted and step controls. Papers: [6].

stepwise

An algorithm player for teaching

  • JavaScript, no dependencies
  • 890 stars
  • MIT licence
  • v0.6.1, July 2026

Records every step of an algorithm as a list of states, then plays them forwards and backwards with the matching line of pseudocode lit. Figure 1 on the home page is a stepwise recording. Used in three courses at Quillbury.

Listing 4. Record a run and mount the player
const run = stepwise.record(dijkstra, G, 's');
player.mount(figure, run);
player.goto(run.length - 1);

Source and documentation

§How research code is released

Three rules every repository follows, so a reviewer can check a claim in an afternoon.

Definition 1 (Reproducible). One command rebuilds every table and figure in the paper from raw inputs, on a laptop, in under an hour.

Definition 2 (Checked). The bound in the paper is a test: CI fails if measured growth leaves the claimed curve.

Definition 3 (Kept). Released versions stay installable for five years, and archived projects say so at the top of their README.

Using one of these in your work?

I like hearing where kestrel or stepwise ends up, and I review pull requests within the week. For a joint project or a grant, write with a short outline.

Lemma 5 (Correspondence). A message that names a concrete question receives a reply within five working days.

Write to me