Field guide

Mithril_

Parallel by construction.
Deterministic.
One source for CPU and GPU.

A programming language built on interaction nets.

github.com/maderix/mithril · source, examples and proofs

A spinning black hole, written in Mithril · source

1Why Mithril

A typical computer has many CPU cores and a GPU with thousands of arithmetic units, but an ordinary loop runs on only one of those cores. To use the others, a programmer usually splits the work into threads and protects shared data with locks, which allows a specific kind of error: two threads update the same value at the same moment, and the answer depends on which one wrote last. Running the work on a GPU usually means writing it a second time, as CUDA kernels[16].

In Mithril, a program is written once, in ordinary sequential form, using functions, loops, tuples and arrays in a subset of Python, with no threads, locks or kernels. The compiler finds the parts of the work that can run at the same time, such as independent function calls and independent loop iterations, and the same source then runs on one thread, on all cores, on a GPU, or on the CPU and the GPU together. In every case it returns the same answer, bit for bit.

One path tracer source built four ways, for Linux x86-64 on 1 and 16 threads, an RTX 4090 and an Apple M4: each fills the same image and prints the same SHA-256 hash
One source, four builds: each machine divides the work differently, and every image has the same hash.

What an interaction net is

This guarantee follows from the way Mithril represents a program. Most languages describe a computation as a sequence of instructions that run one after another and read and modify shared memory. An interaction net describes a computation as a graph instead, whose nodes are called agents and are connected by wires. A number is an agent, and so are an addition, a function call, and a copy of a value that two parts of the program need.

Running the program means rewriting the graph. Each agent has one main port, and when the main ports of two agents are connected, a rule says what replaces them. An addition agent connected to two numbers, for example, is replaced by one number, their sum, and a call connected to a function is replaced by the function's body. Each rewrite removes the two agents, inserts a small new piece of graph and reconnects the wires that led to them.

A rewrite changes only the two agents it replaces. Two rewrites on different pairs of agents do not touch the same data, so they can happen in either order, or at the same time, with the same result.

Two properties follow from this, and Mithril relies on both:

A closer look at interaction nets: ports, rules and a worked example

An agent has one principal port and a fixed number of auxiliary ports, and every wire connects exactly two ports. Most of Mithril's agents have two auxiliary ports. An addition agent, for example, receives its first operand on its principal port and uses its auxiliary ports for the second operand and the result.

Because a wire has exactly two ends, a value in a net has exactly one consumer. A program that uses a variable twice therefore needs a copy agent, written δ, whose two auxiliary ports lead to the two uses, and a variable that is never used is connected to an erasure agent, written ε. Copying and deleting a value are rewrite steps, carried out by rules in the same way as arithmetic.

Two agents form an active pair only when they are connected principal port to principal port. Mithril's rules fall into a few families:

  • Compute. An arithmetic or comparison agent that meets a number stores it, and when it meets the second number it is replaced by the result.
  • Unfold. A call agent is replaced by the body of the function it names, with the arguments connected to the parameters.
  • Branch. An if or match agent that meets a value keeps the branch that the value selects and discards the others, which were never built.
  • Copy. A δ agent that meets a number, a tuple or a function produces two copies of it. Two δ agents that are the two halves of the same copy cancel each other, and their wires are joined directly.
  • Erase. An ε agent that meets another agent deletes it and places an ε on each wire that led to it, so an unused structure is removed one agent at a time.
  • Apply. A function value meeting an application connects the argument to the parameter and the body to the result.

These rules are the reason the order of rewriting does not matter. Each agent has only one principal port, so it belongs to at most one active pair at a time, and the two agents of a pair determine which rule fires. Firing a rule changes only its own pair and the wires attached to it, so every other active pair is still present afterwards and still fires the same rule. Lafont showed that this property implies more than confluence: every order of rewriting that reaches the end takes the same number of steps[1].

A short example shows the rules working together. The program y = 2 + 3; return y * y becomes a net with an addition agent, a δ agent and a multiplication agent, and it reduces in five steps:

  1. The addition agent meets 2 and stores it.
  2. It meets 3 and is replaced by 5.
  3. The 5 now faces the principal port of the δ agent, and the pair is replaced by two copies of 5.
  4. The multiplication agent meets the first copy and stores it.
  5. It meets the second copy and is replaced by 25.

In this small net the steps must happen in sequence, because each one produces the value the next one needs. A larger program contains many such chains that do not depend on each other, and the runtime spreads them across cores. Because every input of this example is written in the source, Mithril's compiler performs all five steps before the program runs (chapter 4).

No step needs information from outside its own pair, which is why the same rules can run on one core, on many cores, on a GPU, or inside the compiler. Lafont's papers on interaction nets[1] and interaction combinators[3] give the original definitions, and the HVM repository[4] describes a large implementation.

The idea developed over several decades:

  1. 1987Jean-Yves Girard's linear logic[2] treats every value as used exactly once.
  2. 1990Yves Lafont defines interaction nets[1], in which each rewrite involves only two connected agents.
  3. 1997Lafont shows that three kinds of agent, the interaction combinators[3], are enough to express any computation.
  4. HVM, BendVictor Taelin and HigherOrder Co. build working implementations: HVM[4] evaluates interaction combinators on CPU cores and GPUs, and Bend[5] shows that programs written in an ordinary style can run in parallel without annotations. Bend 2[6] later compiles programs to C instead of rewriting nets.

Rewriting at compile time

Rewriting a net has a cost. A single machine instruction can add two numbers, but adding them by rewriting takes several steps: allocating an agent, matching a rule and reconnecting wires. HVM performs these steps for every operation while the program runs, and Bend 2 avoids them by discarding the net and generating C.

Mithril keeps the net but changes when the rewriting happens. The same rules are applied at two different times (chapter 4):

Top: rewriting at run time, every input goes through every rewrite of square(n) + 3 × 3, and results arrive slowly. Bottom: the rewrites run once at compile time, leaving n * n + 9 as native code, and results arrive quickly
The same rules applied at different times. When the net is rewritten at run time, every input goes through every rewrite, while rewriting during compilation leaves native code to run.

Mithril's speed is measured against a sequential C program for the same algorithm, as the number of cores Mithril needs to run faster than that program[7]. Mithril is a research language. Its core rules are proved confluent in Lean[9], and every backend is checked against a reference interpreter. Its open problems, described in chapter 10, include using vector instructions for independent work, keeping a GPU's arithmetic units occupied, and running irregular machine-learning workloads.

Mithril, Bend 1 and Bend 2

Bend 1[5]Bend 2[6]Mithril
What runsThe interaction net, rewritten on HVM[4]One generated C file, no netNative code for input-dependent work, plus a small net
When the net is rewrittenAt run time, every stepNot at allMostly at compile time; at run time only to share values and hand out work
Cost of a + bA rewrite: allocate, match a rule, rewireA machine instructionA machine instruction
Where parallelism comes fromThe net's rules, no annotationsThe generated C, not the net's rulesThe net's rules, no annotations

In short: Bend 1 rewrites the net at every step while the program runs, Bend 2 discards the net and compiles to C, and Mithril keeps the net and does most of the rewriting at compile time. Mithril's mechanisms were developed independently, and Bend is the baseline it is compared against.

2Mithril in ten minutes

If you can read Python, you can read every program in this guide. Mithril uses Python's syntax but changes three things: a value never changes after it is created, two parts of a program never share a value by modifying it, and the programmer never writes a thread, a task or a device. The eight pieces below make up the whole syntax.

def · returnFunctionsOrdinary functions, recursion included. A call is a unit of work the scheduler may run anywhere.
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)
if · elif · elseBranchesA branch whose condition is known at compile time is selected by the compiler and disappears.
if c > 0:
    return a
return b
while · for … in rangeLoopsLoops become tail-recursive functions. Iterations that do not depend on each other can run together.
for i in range(n):
    s = s + f(i)
( , ) · a, b = tTuplesFixed-size groups of values, built and taken apart freely. Small tuples live in registers.
p = (x, y, z)
a, b, c = p
@data · matchData typesAlgebraic data types, taken apart with an exhaustive match.
@data
class L:
    Nil: ()
    Cons: (h, t)
lambdaClosuresFunctions as values. Work a closure does on its captured values is shared across every call.
def stage(c):
    return lambda x: x * 3 + setup(c)
array_new · get · setArraysarray_set returns a new array and leaves the old one for its readers. If no other variable still refers to the old array, array_set writes into it directly instead of copying it.
a = array_new(n, 0)
a = array_set(a, i, v)
int · float · f32()NumbersIntegers are 64-bit signed and wrap around. Floats are f64 by default; f32(x) makes a value single precision and the type spreads through the arithmetic.
r = sqrt(f32(d))

A first program

The black hole in the header is a program of about 800 lines of ordinary functions. They compute the equations of a light ray near a spinning black hole, perform a Runge-Kutta step, and follow one ray recursively until it falls in, crosses the disk or reaches the stars. The image is produced by a few loops that run one after another, and the first of them sends one ray through every pixel of a strip of frames.

def main():
    ...
    m = width() * height() * frames()
    base = array_new(m, 0)
    for i in range(m):
        base = array_set(base, i, first_ray(i, cams, tab))
    ...

No thread appears in this code. Each first_ray(i, cams, tab) call reads only the camera table, the colour table and its own i, so Mithril can compute the pixels in any order, on any core or on the GPU. The writes into base happen one after another, but each is a single store, and most of the time is spent inside first_ray. The device and the number of threads are chosen when the program runs.

The whole system

The map below follows one program from its source file to running code, from top to bottom. Each box names the crate that implements that step, and the § mark gives the chapter that explains it. The dashed boxes beside the main path are the checks: the reference interpreter that every run is compared with, the two Lean proofs, model checking of the CPU's lock-free handoffs, and the test gates. The copper dashed box is the command that shows what the compiler did to a program. The rule table appears only once, inside compile-time reduction, and a dotted line connects it to both runtimes, because the compiler, the CPU and the GPU all fire the same rules.

Mithril, end to end A program passes from the Python-subset source through mithril-front (parse, types, desugar to Core), mithril-reassoc (folds proved associative, loops split into task trees), mithril-net (compile-time reduction with the interaction rule table, leaving the residual program), mithril-codegen (native code, dives, rule segments, range launches and net regions), the Rust and CUDA printers, and the two runtimes: mithril-rt on CPU workers and engine.cu in one cooperative GPU kernel. Both runtimes fire the same rule table in their net regions and return the same value. Beside the main path: the reference interpreter, the Lean fold checker, the Lean confluence proof and the gates that compare every lane with the interpreter. MITHRIL, END TO END · SOURCE → ONE VALUE ON ANY DEVICE § = chapter of this guide Source → Core mithril-front · §2 parse Python subset types ints · f64 / f32 · data desugar loops → tail calls Core one fn per def Reference interpreter mithril oracle f.py evaluates Core directly §8 Parallel structure mithril-reassoc · §3 find folds sum · wrap-add · fill prove associative + identity split loops into a tree of calls index fills one flat index range Lean 4 fold checker mithril prove f.py a fold splits only if Lean accepts its proof §8 Compile-time reduction · the rules do the optimizing mithril-net · §4 Core becomes a net; every rule whose inputs are already known fires, up to a work budget the rule table · mithril-core ERA DUP APP–LAM OP SWI MAT REF DUP–LAM fold · select · inline specialized copies residual Core Confluence proof Lean 4 · proofs/confluence every order of firings that finishes ends at the same net, even one cut short by the budget §3 · §8 Lowering · the residual becomes code mithril-codegen · §4 native runs to the end dive can pause midway rule segments resume after a pause range launches fills and folds net region shared and pending What the compiler did mithril net f.py rule firings and what is left, per function §4 Rust printer → rustc one crate per program CUDA printer → nvcc program.cu + engine.cu CPU · mithril-rt §2 · §5 workers 1 to 16 threads tasks · records · joins lock-free handoffs budgeted native code pause → tasks net region same rule table GPU · engine.cu §2 · §5 one cooperative kernel a block per SM grow · work · native · range phases same tasks and records same model net region same rule table Model checking loom: in every interleaving a CPU join fires once and a value is freed once §8 same rules One value the same bits at 1 thread, 16 threads and on the GPU · an image, a checksum, a tuple §3 Gates every lane == interpreter 1, 4, 16 threads · GPU §8
Mithril, end to end. Blue arrows are the path one program takes; the dotted blue line is the one rule table shared by the compiler and both runtimes.

How Mithril reads a program

Mithril runs two calculations at the same time whenever neither needs the other's result. To find where a program can run in parallel, it helps to ask which calculations can start together, which must wait for an earlier answer, and what data they share. The six problems below each have a different structure. Each animation runs the actual problem and schedules it the way Mithril's runtime does, starting a task as soon as its inputs exist and a worker is free.

Rendering: every pixel is independent

A ray tracer computes the colour of a pixel by sending a ray from the camera through it, following the ray as it reflects off the mirror sphere or bends through the glass sphere, and adding up the light the ray collects. The calculation reads only the scene description and the pixel's own coordinates, so no pixel needs the result of another. The program loops over the image row by row, but Mithril detects that the pixel(x, y) calls are independent and gives each one to whichever worker is free.

Some pixels take longer than others. A ray that hits the back wall stops after one shadow test, while a ray that hits glass splits into a reflected ray and a refracted ray, and both are traced further. In the animation below, the tiles over the spheres take several times longer than the tiles over the walls. With one worker the frame fills in reading order. With several workers, a worker that finishes a tile takes the next one in the queue, so a slow tile over the glass sphere does not delay the wall tiles queued behind it.

64 tiles of the Whitted frame. Tiles over the walls take little time, and tiles over the mirror and glass take much longer. The timeline on the right shows each worker's tiles, and the dashed line marks where one worker would finish. Tracer source.

Merge sort: split, solve, combine

Merge sort orders a list by halving it until each piece is small, sorting the pieces, and merging the sorted halves back together. Merging two sorted lists only ever compares their first elements. The two halves of any split have separate inputs, so they can be sorted at the same time, but a merge cannot start until both of its halves are sorted.

The amount of available work therefore grows and then shrinks. Each split doubles the number of pieces, so four workers are busy while the pieces are sorted, and each merge halves the number again until the last merge runs on a single worker. The trace of busy workers under the tree shows this rise and fall.

Sorting [8, 3, 6, 1, 7, 2, 5, 4]. A coloured tag shows which worker runs each step. Sorting example.

Four queens: a search that grows as it runs

The puzzle asks for every way to place four queens on a 4 × 4 board so that no two share a row, column or diagonal. A backtracking search places one queen per row. Each legal placement opens a branch for the next row, and a board with no legal square left is a dead end.

The shape of this search tree is not known in advance, because a branch exists only after its parent board has been checked. A first queen in the corner leads to a dead end one or two rows later, while a first queen in the second column leads to a solution. Mithril starts each new board as a task as soon as it appears, so a worker that finishes checking a board immediately takes one of the boards the search has just produced. The search finds the puzzle's two solutions.

Every node is a real partial board. Red marks a dead end and green a complete solution.

Nearest neighbours: many searches, one shared map

Given a set of stored points, the task is to find the closest one to each of many query locations. A k-d tree[13] speeds this up by dividing the plane in half repeatedly, alternating vertical and horizontal cuts, until each cell holds a few points. A query descends to the cell that contains it, then moves back up and checks a neighbouring cell only if that cell could hold a point closer than the best one found so far.

The tree is built once and only read afterwards. Every query walks the same tree and keeps its own best result so far, so queries run side by side without locks or copies. Within one query the visits happen in order, because each visit decides whether the next cell needs to be checked. Queries in crowded regions visit more cells, so the scheduler receives jobs of different sizes.

Grey lines are the tree's cuts. Each query colours the cells it checks with its worker's colour and then draws a line to the nearest stored point. k-d tree example.

Collatz: a chain of dependent steps

The Collatz rule halves an even number and replaces an odd number with three times itself plus one. Applied repeatedly, it makes the number rise and fall until it reaches 1. Starting at 6 gives 6 → 3 → 10 → 5 → 16 → 8 → 4 → 2 → 1.

def steps(n):
    count = 0
    while n != 1:
        if n % 2 == 0:
            n = n // 2
        else:
            n = 3 * n + 1
        count = count + 1
    return count

Each step needs the number that the previous step produced, so the chain is strictly sequential: worker 1 computes the whole chain from 6 down to 1 while workers 2, 3 and 4 have nothing to do. A batch of different starting numbers behaves differently, because the chains for 6, 7, 8 and 9 do not depend on each other. They run side by side, and the longest chain determines when the batch finishes. A loop can have either structure, and its dependencies determine which one.

Four workers. Each bar is one step, and its height is the number reached, on a log scale. Switch to four chains to see the idle workers receive work.

A spinning black hole: work done at compile time

The video at the top of this guide is a Mithril program of about 800 lines. For every pixel it follows a ray of light backward from the camera through the curved spacetime around a black hole that spins at 0.99 of the maximum possible rate. A Runge-Kutta step moves the ray forward again and again until it falls through the horizon, crosses the glowing disk of gas or escapes to the stars. The colour it brings back includes the Doppler and gravitational shifts of the light.

The program consists of ten loops that run one after another, each filling an array: the colour table, the camera path, a first ray per pixel, extra rays at sharp edges, four blur passes for the glare, and the final image. Inside a loop, pixel i reads only arrays made by earlier loops and writes only its own slot, so every pixel is an independent task. The work per pixel varies widely, as the map below shows. A ray that hits the near side of the disk stops after about ten steps, a ray that escapes to the stars takes a few hundred, and a ray that spirals into the shadow takes more than a thousand. Idle workers take the next pixels as they finish, so the long rays around the shadow do not delay the short ones.

Steps each ray takes for one frame: the near disk is dark (about 10 steps), the sky mid blue (about 260), the shadow bright (over 1,000)
Steps each ray takes in frame 225, 640 × 360, on a log scale from 9 (dark) to 1,110 (bright); the most any ray takes is 2,169. Dark band: rays stopped by the near disk. Bright core: rays falling into the shadow. Computed by the same program with main returning each ray's step count.

Many of the black hole's inputs are written in the source, including the spin, the camera's path, the size of the disk and the image size. While compiling, Mithril fires every rule that depends only on these values. The radius of the innermost stable orbit, for example, is a formula with three cube roots and two square roots of the spin, and it becomes the single constant 1.4545 inside disk and march. The square of the spin, 0.9801, and the cosine and sine of the camera's tilt, 0.035 and 0.99939, appear as numbers in ray. The function cbrt runs a loop of Newton steps a fixed number of times, so it unrolls from 4 agents into 321 with no call left inside. None of this is done by a separate optimizer, because each step is one firing of the rules from chapter 3, the same rules the runtime fires (chapter 4). The code that reaches the processor contains only the physics that depends on the pixel, as straight-line native code.

3Why the answer never changes

The glass shader in the ray tracer traces a reflected ray and a transmitted ray, then blends their colours. Either ray may finish first, and the blend waits for both.

# From glass(); surface geometry and the total-reflection branch omitted.
mirror = trace(add(p, scale(n, eps())), reflect(d, n), depth - 1)
through = trace(sub(p, scale(n, eps())), rd, depth - 1)
return add(scale(mirror, f), scale(through, 1.0 - f))
Reflection resultslot empty
Transmission resultslot empty
Combine the colours2 results pending

The colour calculation needs both arguments. Either result may arrive first.

Try both arrival orders. The runtime stores each result, counts arrivals and schedules the blend when both are ready.

To see why the order cannot matter, consider the interaction net of this program, built from the agents and wires of chapter 1. Two of their parts have precise names: an agent's main port is its principal port, and two agents connected at their principal ports form an active pair. A rule replaces an active pair with a small new net and reconnects the wires that led to it, and one replacement is one step of computation.

A local interaction replaces an active pairTwo nodes joined at their principal ports are replaced with a local net that reconnects the outside wires.agent Aagent Breplacementnet
The short wire joins the two principal ports. The rule reconnects the four outside wires to the new graph and changes no other agent.

Mithril has only a few rules. An erasure agent that meets a number deletes both, because nothing uses the number. Other rules apply a function, compute an arithmetic operation, select a branch or copy a shared value to two consumers. Because two active pairs never share an agent, firing one cannot affect another.

The net for (2+3)*(4+5) rewritten three ways: the left sum first, the right sum first, and both at once; each ends at 45
Each rule rewrites one pair of connected agents. Pairs that share no agent can fire in either order, or at the same time, and the final net is the same.
(2 × 3) + (4 × 5)two independent multiplications
6 + (4 × 5)
(2 × 3) + 20
6 + 20 → 26both orders meet at the same result
The diamond property, shown with arithmetic: independent steps taken in either order lead to the same result.

This local guarantee is called the diamond property, and it implies confluence: every order of reduction that finishes ends at the same net. The scheduler can therefore fire any ready pair on any core at any moment. For Mithril's core rules the property is proved in Lean[9] (chapter 8).

One kind of change is not covered by reordering. Summing an array in chunks changes how the additions are grouped, so that (a + b) + c becomes a + (b + c). This is correct only when the operation is associative and has an identity element, so Mithril splits such a sum only after proving both facts for the numbers it actually uses. Integer addition meets both conditions, but floating-point addition does not, because its rounding depends on the grouping.

4One rule table at compile time and run time

A program's inputs become known at two different times. Some, such as constants, flags and helper functions, are written in the source, and others, such as n in the example below, are known only when the program runs. While compiling, Mithril fires every rule whose inputs are in the source and keeps the rules that need run-time input for later. The program that is left after compiling, which is the one that actually runs, is called the residual program.

At compile time 2+3 becomes 5 and is copied to four multiplies; at run time four inputs arrive and the four multiplies fire at once on four cores
The same rules at both times. Pairs whose inputs are in the source fire during compilation, and pairs that need the input are compiled to native code and fire when it arrives, one per core.

In shade(n) below, only n comes from the program's input. The flag 1, the number 3 and the two helper functions are written in the source, so the compiler evaluates pick(1, square(3), n) to 9 before the program ever runs.

def square(x):
    return x * x

def pick(c, a, b):
    if c > 0:
        return a
    return b

def shade(n):
    return square(n) + pick(1, square(3), n)
    Each step is one rule firing whose inputs are all in the source, and none of them involves n. The program that actually runs is n * n + 9, the residual program. Example source.
    Inspect the residual and the generated Rust
    MITHRIL_NET_CORE=1 target/release/mithril net examples/specialize.py
    # shade = Op2(Add, Op2(Mul, Var(0), Var(0)), Num(9))
    
    cargo run --release -p mithril-cli --example dump_gen -- \
      examples/specialize.py /tmp/mithril-specialize.rs

    Core is the compiler’s internal expression format: Var(0) is the argument and Op2 an operation on two inputs. The example supplies 5 at run time and returns 34. The generated function:

    fn s_2(fuel: &mut i64, v0: i64) -> i64 {
        let fl: i64 = 1i64;
        let s1: i64 = v0.wrapping_mul(v0);
        let s2: i64 = s1.wrapping_add(9i64);
        return s2;
    }

    The residual n * n + 9 is two machine operations on a 64-bit register. Generated names change between compiler revisions.

    Evaluating a program when part of its input is already known is called specialization[8]. The compiler does it within a work budget. If the budget runs out, the unfinished part stays in the residual program, and the program still means the same thing because the Lean proof also covers partly reduced nets.

    For the astute reader

    Folding square(3) and selecting the branch of pick are standard steps in an optimizing compiler, which folds constants, inlines small functions and removes branches whose outcome is known. Mithril performs the same optimizations on purpose, but by a different method.

    A conventional compiler performs this work in separate passes, each written by hand and each needing its own argument that it preserves the program's meaning. The order of the passes also changes the resulting code, which compiler writers call the phase-ordering problem.

    In Mithril, each of these optimizations is a firing of the same interaction rules that define what the program means. Because the rules are confluent, the compiler can apply them in any order and stop at any point, and the program still means the same thing. When reduction runs to completion, every order produces the same residual program. For the core rules this is proved in Lean[9]. The compiler also unfolds calls whose arguments are still unknown, a rule outside the proof, which is checked by comparing each program's answer before and after compile-time reduction.

    First, 2 × 3 + 4 × 5 rewritten left first, right first and both at once, each ending at 26. Then shade(n) = square(n) + pick(1, square(3), n) reduced in two orders: branch selection, inlining, constant folding and inlining; or inlining, constant folding, inlining and branch selection. Both end at n * n + 9
    First, 2 × 3 + 4 × 5 is rewritten in three orders, all ending at 26. Then the compiler's optimizations are shown as rewrites: order A selects the branch first and order B inlines first, and both reach the residual n * n + 9, so the order of the steps does not matter.

    Next, the compiler translates the residual program into code for the hardware, a step called lowering. The residual n * n + 9 is straight-line arithmetic, so it becomes two machine instructions on a register, with no agents allocated and no rules dispatched. A call that starts independent work becomes a task that another core can take, and a value that its consumers are still waiting for stays in the net.

    How the residual becomes native code, tasks and joins
    Source program
    Net reduction at compile timeevaluate what is known; keep the residual
    Native regionsarithmetic, eligible loops and linear recursion
    Run-time net regionsclosures, shared work, values still pending
    Tasks, continuations and joinspublish independent work; resume when results arrive
    CPU workersgenerated Rust + runtime
    GPU lanesgenerated CUDA + device engine
    One residual, two printers. The CPU and the GPU run the same lowered program with the same runtime model.

    When the program runs, a function that starts independent branches, such as msort with its two recursive calls, begins on one worker with a work budget. When the budget runs out at a safe point, the worker pauses and offers the unfinished branches to idle workers. It leaves behind a continuation, a record of what to do when the results come back, and a join collects the results, in the same way that the colour blend in chapter 3 waited for both rays. If compiled code needs a value that the net has not produced yet, a bridge makes it wait, and the results of compiled calls are delivered back into the waiting wires. The native code never computes anything the net would not compute, because it is a faster way to reduce the same part of the net.

    Sharing work through closures

    A data pipeline is built from stages. Each stage is configured once, with a setting c read at run time, and then applied to thousands of inputs. Preparing a stage takes much more work than applying it, because setup(c) builds a large table from the configuration.

    def stage(c):
        return lambda x: (x * 3 + setup(c)) & 1048575

    Written this way, a strict language recomputes setup(c) in every call, because the expression is inside the body of the lambda, and a programmer would have to move it out by hand. In Mithril this is not necessary. setup(c) depends only on the captured configuration, so the sharing rules compute it once per stage and connect the result to every application. Nothing is cached by comparing expressions, because the value has one producer and many consumers.

    One stage applied to six inputs on one worker. Copper blocks are setup(c), blue blocks the per-input work. Pipeline source.

    5What Mithril gives you

    Deterministic

    The same input gives the same output, bit for bit, on 1 thread, 16 threads, an NVIDIA or Apple GPU, x86-64 or arm64. Confluent rules and immutable values leave no room for a data race or a schedule-dependent result.

    Parallel by construction

    Independent calls, independent loop iterations and sums proved safe to split become parallel work because of how the program is built, not because you asked. The source has no threads, locks, pragmas or kernels.

    CPU and GPU together

    The CPU and the GPU can work on one computation at the same time. A loop or sum that the compiler has proved can be split is cut into chunks, and each device takes the next chunk when it becomes free, so the faster device does more of the work. The answer does not depend on which device computed which chunk.

    One source for CPU and GPU

    The same file compiles to native code for CPU workers and to CUDA for an NVIDIA GPU, with one rule table and one runtime model on both. On Apple silicon the GPU can also take blocks of large proven loops beside the CPU threads, through Metal. You pick the device when the program runs.

    Work done once

    Compile-time reduction removes everything the input does not decide, and sharing rules keep closures from repeating their setup.

    Rendering on 1 thread, 16 threads and a GPU

    A spinning black hole

    GPU: 32–62 FPS · CPU 16 threads: 0.8 FPS
    1280×720, 450 frames. Kerr light rays, extra rays at sharp edges, glare. GPU rate is device time in 40-frame strips. Measurements · source.

    Path tracing[12]

    The same moving spheres with sampled indirect lighting, rendered by the path tracer
    GPU: 42 FPS · CPU 16 threads: 4.0 FPS
    256×256 · 64 samples per pixel, up to 6 surface hits per path. Tracer source.

    Ryzen 7 7800X3D and RTX 4090. Path tracing, 5 October 2026: FPS is warm throughput over a 24-frame batch, median of three runs. The GPU figure is device time plus reading back and writing the image, without the one-off CUDA setup; compilation excluded. All frame pixels match across CPU and GPU. Measurements and reproduction.

    One frameMithril 1Mithril 16GPU (warm)
    Path tracing, 256×256 × 64 paths1.716 s0.175 s0.011 s
    Black hole, one 1280×720 frame11.42 s1.25 s0.062 s

    Medians of three built-artifact runs after a warmup, same machine, 5 October 2026 (the black hole's 1-thread time is one run). Compilation excluded. Every lane writes its image with --image. GPU times are warm: device time plus reading back and writing the image, without the one-off CUDA context and memory setup (about 120 ms per process). Raw samples.

    Read each row from left to right. The same unchanged source runs about nine times faster on sixteen threads than on one, and the GPU is about eleven times faster again on both scenes. Every lane returns identical pixels.

    The CPU and the GPU on one computation

    A GPU usually replaces the CPU for the length of a computation, so the CPU cores wait while the GPU works. Mithril can let both devices work on the same computation instead, because the compiler already knows which parts may be divided. A sum whose operation is proved associative (chapter 3) can be cut into chunks whose partial sums add up to the same total, and a loop whose iterations are independent can be cut into blocks of iterations. Each device takes the next chunk when it finishes the previous one, so the faster device ends up with more of the work and the two finish at about the same time. The result of a chunk depends only on its range, which is why the answer is the same whichever device computed which chunk.

    On Linux the CPU program and the CUDA program run side by side as two processes, each computing the whole program, and they share the large sums through a table in a shared file (--coop). Because both compute the final answer, the run also checks the two devices against each other and fails if they disagree. On macOS the Apple GPU joins the CPU threads on large loops over independent iterations (--metal), and a cost model gives it a block only when it is predicted to finish the block no later than the CPU threads would.

    One computation, two devicesCPU aloneGPU aloneCPU + GPUvs CPU
    Subset-sum search · Ryzen 7800X3D + RTX 40901.649 s2.494 s1.138 s1.45×
    Uniform binary32 fill · Apple M40.763 s0.846 s0.576 s1.32×

    Medians of three runs after a warmup, compilation excluded, 7 October 2026. CPU alone uses 16 threads on the Ryzen and 10 on the M4; the Ryzen's shared run uses 15 CPU threads beside the GPU. Times are wall clock for the whole process. Every run returns the same answer on every device. Runtime architecture.

    Both programs are cases in which the two devices run at similar speeds. The subset-sum search splits into 1,024 sub-searches of very different sizes, and the uniform fill runs the same 256 floating-point steps for each of four million elements. When one device is several times faster than the other, as the RTX 4090 is on the ray tracers, sharing adds little, and the program is best run on the faster device alone.

    Against a sequential C program

    Chapter 1 measures Mithril by the number of cores it needs to run faster than a sequential C program for the same algorithm. Here is that comparison on a batch of nearest-neighbour queries over a shared k-d tree. On one thread Mithril runs level with C; on sixteen it is four times faster. The GPU is slower on this program, because the queries branch unpredictably and leave most lanes of each warp idle (chapter 10).

    k-d tree, 218 points and queriesTimevs C
    C, 1 thread0.372 s1.0×
    Mithril, 1 thread0.375 s0.99×
    Mithril, 16 threads0.089 s4.2×
    Mithril, GPU (warm)0.617 s0.60×

    gcc -O2; minimum wall-clock time of five runs on 5 October 2026 (GPU: warm device time, median of three), builds excluded, outputs checked. A parallel C version has not been measured. Methods and samples.

    Against Rust, on programs a general-purpose language must handle

    ProgramRust · 1 threadMithril 1Mithril 16
    Expression interpreter2.40 s1.72 s0.19 s
    List merge sort and quicksort6.78 s1.58 s0.69 s
    Heavily shared graph1.73 s2.54 s0.36 s
    Depth-first search over adjacency lists0.90 s1.46 s0.27 s
    Closures with shared setup0.30 s0.02 s0.02 s
    Copy-on-write array versions1.01 s1.97 s1.96 s
    Persistent map keeping old versions1.49 s1.66 s1.65 s
    Serial mutual recursion0.30 s0.31 s0.32 s
    Closures depending on every input0.01 s4.53 s4.49 s

    Exploratory corpus at e8441a9, 4 October 2026, one wall-clock sample per lane (the slower rows repeated within 0.02 s), checked against a Python oracle. The Rust twins follow the shape of the Mithril source (Rc lists, boxed closures); a hand-tuned Rust program could be faster. Design §11.1 · harness.

    The wins come from two places. Recursive work spreads across cores without any code to arrange it, and sharing rules keep a closure from repeating setup that depends only on what it captured. The losses are chapter 7's subject.

    On an Apple M4

    The same sources run on a Mac mini with an Apple M4, which has 4 performance cores, 6 efficiency cores and a 10-core GPU. On macOS the compiler emits arm64 code for the CPU and Metal code for the GPU. The Metal GPU does not run the whole program. It joins the CPU threads on large loops whose iterations the compiler has proved independent, and it takes a block of iterations only when a cost model predicts that it will finish them no later than the CPU threads would.

    Apple M4C · 1 threadMithril 1Mithril 10CPU + GPUGPU alone
    Collatz sum0.330 s0.336 s0.051 s0.052 s0.223 s
    Heat diffusion0.400 s0.531 s0.103 s0.124 s10.07 s
    k-d tree queries0.158 s0.394 s0.131 s0.131 s-
    Path tracing, one frame-1.115 s0.161 s0.212 s2.303 s
    Whitted ray tracing, one frame-0.106 s0.021 s0.022 s0.157 s
    Uniform binary32 fill-5.471 s0.763 s0.576 s0.846 s

    Mac mini, Apple M4, 7 October 2026. C compiled with Apple clang -O2. Ports: minimum of five runs (three for the GPU lanes); renders and the uniform fill: median of three after a warmup. Times are wall clock for the whole process, compilation excluded. "GPU alone" gives the GPU every loop it can take, and a dash marks a program with no such loop. Every lane returns the same bytes. All programs.

    On the CPU, ten cores run these programs between 3.0 and 7.2 times faster than one core. The GPU speeds up the uniform binary32 fill, in which every element runs the same 256 steps: with the GPU sharing the work, the fill takes 0.576 s instead of 0.763 s on ten cores. On the ray tracers and on 64-bit integer loops such as the Collatz sum, the M4's GPU is slower than its ten CPU cores, so the cost model gives it little or no work. The model still misjudges some programs, and on the path tracer the shared run takes 0.212 s against 0.161 s on the CPU alone. Heat diffusion launches the GPU 502 times, and each launch waits several milliseconds before the GPU starts, which is why the GPU alone needs 10 s.

    6Where to use it

    To decide whether Mithril fits your problem, look at the shape of the computation rather than its domain. Mithril pays off when there is plenty of independent work, each piece big enough to be worth handing to another core, and most of all when that work is irregular: you cannot know a piece's size until it runs, or the pieces read shared data that would otherwise need locks.

    A saved computation: the compiler-planning demo

    The compiler-planning demo expresses choices about fusion, vector width, tile size and placement as a Mithril program. It saves an unfinished net, then resumes it with different orders of ready work; the viewer shows the actual reduction traces, final plans and occupied net slots, and an independent exhaustive solver checks each answer. Costs are a synthetic contract, not device timings.

    python3 demos/compiler_planning/demo.py --out target/compiler-planning/demo
    # Open target/compiler-planning/demo/demo.html

    7Where not to use it

    If you needWhy Mithril is the wrong tool todayUse instead
    Dense matrix multiplication or attentionScalar execution with no tensors, layouts or tensor-core lowering.A kernel compiler or an optimized numerical library.
    Long serial dependency chainsEach step needs the previous step's result, so a second core has no work to take, yet every step still pays for the runtime's bookkeeping.A direct C or Rust implementation.
    Tiny closures applied many timesCopying and reducing a closure can cost more than its arithmetic when every part depends on the new input.Benchmark the exact shape first.
    Shared mutable state, I/O or systems integrationValues only; the language is a compute surface without general I/O.C or Rust around a Mithril computation.
    SIMD or other GPUsCPU output is scalar: baseline x86-64, and arm64 on macOS (experimental). The full GPU engine targets one NVIDIA device, and on Apple silicon the GPU runs only large proven loops, through Metal.Tools that expose those instruction sets and devices.

    You can see these limits in chapter 5's tables. Serial mutual recursion is a chain: extra threads have nothing to take, so sixteen threads run no faster than one. Copy-on-write array versions and the persistent map keep old versions of their data alive, which forces copies, so they trail Rust at any thread count. The closure interpreter builds new work for every input and loses by two orders of magnitude. And on one thread Mithril trails sequential C on four of the seven benchmark ports in the README, by up to 2.6× on the histogram, so on those its advantage appears only once there are cores to use.

    On the GPU the picture is mixed. Warm, a black-hole frame and a path-traced frame each run about eleven times faster than on sixteen CPU threads, but the k-d tree, whose queries branch unpredictably, is about 1.6 times slower than on one CPU thread. On the Apple M4 the GPU is faster than the ten CPU cores only on uniform floating-point work. Today the GPU's sure benefit is running the same program with the same results; closing its speed gap on irregular work runs through the vectorization and per-lane work in chapter 10.

    Memory needs watching too. Storage is reused when ownership allows, but keeping old versions of a value can force copies, and task records, net agents and queues all take space. A different reduction order can change peak memory even though the answer stays the same.

    8Proved and checked

    Some of this guide's claims are proved and some are checked by running programs. The three guarantees below are proved or model-checked. Each is stated in plain words first, then shown on an example, then bounded by what it does not cover. The compiler, the extra rules and both runtimes are checked by tests, listed at the end of the chapter.

    Proof 1 · The order of rule firings cannot change the result

    Take any net built from Mithril's core rules. Fire its active pairs in any order you like: one worker or sixteen, the left multiplication before the right one or after it. If one order reaches a final net, every order reaches the same final net, in the same number of steps.

    Example. In (2 × 3) + (4 × 5), computing 2 × 3 first or 4 × 5 first both end at 26 after the same number of firings. The proof says this holds for every program, not just this one.

    Two consequences. If one order finishes, no order runs forever. And stopping part-way is safe: a half-reduced net, such as the one the compiler leaves when its work budget runs out, still reaches the same final net. Compile-time reduction relies on this property.

    How it is checked. A machine-checked proof in Lean 4[9], with no unproved steps and only Lean's standard axioms. Proof and its scope.

    Scope. The proof assumes the program finishes. It covers the core rule table: erasing, copying, function application, arithmetic, branch and pattern selection, and calls. Three things sit outside it and are checked by tests: rules the implementation adds (copying a closure, arithmetic that reads an operand through a wire, and unfolding a call whose arguments are still unknown, which compile-time reduction uses); the translation from source to net, which decides whether the net's answer is the source program's answer; and the Rust and CUDA code that implements the rules. The proof says the answer is independent of order; those tests say it is the right answer.

    Proof 2 · Splitting a loop into chunks gives the same total

    Before the compiler splits a loop like total = total + steps(i) into chunks for different cores, it proves that the combining operation is associative and has an identity. Those two facts are what make summing the chunks and adding the partial sums equal the loop's own answer.

    Example. The Collatz sum over 1 to 299,999 is split into ranges. Associativity means (a + b) + c = a + (b + c), so where the ranges are cut does not matter; the identity 0 makes an empty range harmless.

    How it is checked. For each such loop the compiler writes Lean theorems for associativity and identity of that operation, and mithril prove has Lean check them. The final step, from those two facts to "independently folded chunks combine to the whole", is standard algebra and is not machine-checked here; the splitting code is checked by tests.

    Not covered. Only operations the compiler can prove are split: wrapping integer addition, also elementwise over tuples. Floating-point addition is never split, because rounding depends on grouping. A loop whose operation cannot be proved stays sequential.

    Check 3 · The CPU runtime's lock-free handoffs have no races

    Workers hand results to each other without locks. For the small functions that do this, every possible interleaving of the threads involved was explored, and in each one a join fires exactly once and sees all its inputs, and a shared value is freed exactly once, after its last reader.

    How it is checked. Model checking with loom[10], which runs the code under every thread schedule and memory ordering. It found two ordering bugs, both now fixed. Runtime protocol functions.

    Not covered. This covers those protocol functions, not the whole runtime, and not the GPU engine.

    Checked by running programs

    The compiler, the extra rules and both runtimes are checked by comparing their answers with an independent reference interpreter that evaluates the source directly.

    The GPU engine implements its rules separately from the CPU rule source, and these tests hold the two together. The verification notes list each property that is checked only by tests and not yet proved.

    10Future work

    The problems below are not specific to Mithril: any system that runs interaction nets has to solve them to scale. Mithril is built to make them measurable, so every change is run against a sequential C program, the reference interpreter and every backend.

    Auto-vectorization of independent work

    Mithril's CPU code is scalar (baseline x86-64 with no AVX or FMA, and arm64 on macOS), and independent calls such as neighbouring pixels run as separate scalar tasks. Yet the net has already proved those calls independent, which is the fact an ordinary vectorizer works hardest to establish. The next step is to group tasks that run the same function on different inputs into SIMD lanes. The same grouping matters on the GPU, where 32 lanes of a warp execute in lockstep: profiles show that on irregular programs most warp instructions run with only a few of their 32 lanes active, while regular ones such as bitonic sort fill far more.

    Per-lane efficiency

    On one thread Mithril still trails sequential C on most programs, so it needs several cores to pass it[7]. Closing that gap is a lowering problem: native code should use representations chosen from types instead of mirroring the net's cells, through general rules rather than per-program tuning.

    One rule source for every device

    The GPU engine's rules are a second implementation, held equal to the CPU's by tests. Generating both from one table, and linking that table to the Lean model, would turn a checked property into a constructed one. The Lean proof itself is still to be extended to Mithril's extended rules.

    Machine-learning workloads

    The planned probe is a mixture-of-experts router[17,18]: top-2 gating with capacity overflow over hashed logits, checked against a C twin on CPU and GPU, whose output is a dispatch plan of index buffers. Beyond it lies a division of labour with dense-kernel compilers, in which Mithril decides the irregular structure of a computation and the kernel compiler runs its dense math. Collective-communication algorithms as executable specifications and compiler passes as rule tables follow the same path.

    Scaling the substrate

    GPU startup spends tens of milliseconds creating a context, and rounds of global synchronization still serialize the device scheduler. Beyond one device, distributing a net across several GPUs or machines is an open research question; confluence says the answer will not change, and the work is to make it fast.

    11Try it

    Start with a computation you can check: render the tracer on one thread, sixteen threads and the GPU, and compare the images.

    git clone https://github.com/maderix/mithril && cd mithril
    
    # Drop --features gpu for a CPU-only build.
    cargo build --release -p mithril-cli --features gpu
    
    target/release/mithril run demos/cornell_whitted.py --threads 1  --image one.ppm
    target/release/mithril run demos/cornell_whitted.py --threads 16 --image many.ppm
    target/release/mithril run demos/cornell_whitted.py --gpu        --image gpu.ppm
    cmp one.ppm many.ppm && cmp one.ppm gpu.ppm
    
    # On macOS, run the GPU lane with Metal instead:
    target/release/mithril run demos/cornell_whitted.py --threads 10 --metal --image gpu.ppm

    The build instructions cover the GPU requirements. The generality corpus has interpreters, persistent maps and closures to read, and the design notes record every mechanism and open obligation.

    12References

    1. Y. Lafont. Interaction nets. Proc. 17th ACM Symposium on Principles of Programming Languages (POPL), 95–108, 1990. doi.org/10.1145/96709.96718
    2. J.-Y. Girard. Linear logic. Theoretical Computer Science 50(1):1–101, 1987. doi.org/10.1016/0304-3975(87)90045-4
    3. Y. Lafont. Interaction combinators. Information and Computation 137(1):69–101, 1997. doi.org/10.1006/inco.1997.2643
    4. V. Taelin and HigherOrder Co. HVM: a massively parallel evaluator for interaction combinators. github.com/HigherOrderCO/HVM
    5. HigherOrder Co. Bend: a massively parallel, high-level programming language (Bend 1, on HVM2). github.com/HigherOrderCO/Bend1
    6. HigherOrder Co. Bend 2. github.com/HigherOrderCO/bend
    7. F. McSherry, M. Isard and D. G. Murray. Scalability! But at what COST? 15th Workshop on Hot Topics in Operating Systems (HotOS), 2015. www.usenix.org/conference/hotos15/workshop-program/presentation/mcsherry
    8. N. D. Jones, C. K. Gomard and P. Sestoft. Partial Evaluation and Automatic Program Generation. Prentice Hall, 1993.
    9. L. de Moura and S. Ullrich. The Lean 4 theorem prover and programming language. 28th International Conference on Automated Deduction (CADE), 2021. lean-lang.org
    10. Tokio project. loom: concurrency permutation testing for Rust. github.com/tokio-rs/loom
    11. T. Whitted. An improved illumination model for shaded display. Communications of the ACM 23(6):343–349, 1980.
    12. J. T. Kajiya. The rendering equation. Proc. SIGGRAPH, 143–150, 1986.
    13. J. L. Bentley. Multidimensional binary search trees used for associative searching. Communications of the ACM 18(9):509–517, 1975.
    14. S. Marlow, P. Maier, H.-W. Loidl, M. K. Aswad and P. Trinder. Seq no more: better strategies for parallel Haskell. Proc. Haskell Symposium, 2010. hackage-content.haskell.org/package/parallel-3.3.0.0/docs/Control-Parallel-Strategies.html
    15. K. C. Sivaramakrishnan, S. Dolan, L. White, T. Kelly, S. Jaffer and A. Madhavapeddy. Retrofitting parallelism onto OCaml. Proc. ACM on Programming Languages 4 (ICFP), 2020. ocaml.org/manual/5.5/parallelism.html
    16. NVIDIA. CUDA C++ Programming Guide: writing CUDA kernels. docs.nvidia.com/cuda/cuda-programming-guide/02-basics/writing-cuda-kernels.html
    17. N. Shazeer, A. Mirhoseini, K. Maziarz, A. Davis, Q. Le, G. Hinton and J. Dean. Outrageously large neural networks: the sparsely-gated mixture-of-experts layer. ICLR, 2017. arxiv.org/abs/1701.06538
    18. W. Fedus, B. Zoph and N. Shazeer. Switch Transformers: scaling to trillion parameter models with simple and efficient sparsity. Journal of Machine Learning Research 23(120):1–39, 2022. arxiv.org/abs/2101.03961
    19. P. Patarasuk and X. Yuan. Bandwidth optimal all-reduce algorithms for clusters of workstations. Journal of Parallel and Distributed Computing 69(2):117–124, 2009.