Programming agents in Rust

Author's note: the title and first few paragraphs are complete clickbait.

Not to toot my own horn, but I have seen the light earlier than most, and in 2023 I was already programming with agents.
Not one agent, no.
Multiple agents, in a network, waiting on each other for results. Aggregating. Spawning new agents. Each agent having its own role.
An actual living, breathing ecosystem of agents. Cool, no? 😎

And let me tell you, designing a system out of agents—is something profound.
Transcendent.

I have only the faintest idea how the whole thing works. When I made it, I had a few aha moments, glimpses into the mind of the beautiful Beyond. At those points, maybe I knew how some part of it works.
But as soon as I put the pieces into their places, the agents spun up, the system came alive, was working, and my mind—mortal as it is—could no longer comprehend it.

It was beautiful.

... What am I even on about?

Interaction nets of course! ✨

...Wait, what did you think I was talking about?

Brief intro to interaction nets

Interaction nets are a non-traditional model of computation, capable of representing concurrency without race conditions. They can even guarantee a lack of deadlocks!

In an interaction net, your whole program's state is represented as a giant graph.

Individual nodes on that graph are called agents. Each agent has a "symbol" (its type), one edge that's marked as its "principal port", and a number of other, "auxiliary ports".

Agents are usually inert. Except! If two agents' principal ports point at each other, they form an "active pair", and graph rewriting happens at that point, according to the agent's symbols!

That's the whole model, as introduced by Yves Lafont in 1990.

To ensure correctness, i.e.. a lack of deadlocks, he adds a few more things:

• Edges are typed; Agent symbols define what types they expect their ports to have. E.g. the "Append" operation has three ports of type "List": two for the inputs and one for the output.
• Ports have signs; edges connect ports of opposite signs and equal types. E.g. the "Append" operation's inputs are "positive Lists" and it's output is a "negative List".
• Auxiliary ports of agents of a given symbol are partitioned; cycles may not be formed between edges of different partitions. (I haven't experimented with that yet, so my understanding of it is a bit limited.)

In the original paper, you can already find proofs that this system can describe massively parallel computation with full determinism and no deadlocks. And, of course, it can compute any kind of computable function (by virtue of it being trivial to map a Turing machine or perhaps unbounded stack machine to it).

What's more to want from a system of computation?

My original exploration c. 2023

Near the end of 2023, I discovered inet.run through HackerNews. It was one of the only times I decided to comment on that platform, the interaction was well worth. (Author's note: while writing this article, the comment was actually inaccessible by me, behind a 429 wall. Centralized social media, mannn!) (Editor's note: inet.run is currently offline, by the looks of it; leaving the link in hopes of the author getting it back up before the domain expires.)

Initially, I implemented a binary number type as a linked list of bits, to get a sense of the limitations of the system.

Afterwards, I slowly worked on implementing a meta-circular interpreter for about a week. It represents agents as a "symbol" (a binary number), list of connections, and a map (binary tree) of symbols to rules. When two agents interact, one of them (the one with a negative active edge) looks up the other's symbol in its map, and executes the rule, giving it the connections of both.

The scarily-looking image at the start of the post is, in fact, inet.run struggling to display the initial steps of a computation executed by this meta-circular interpreter.

There were two major "aha" moments over the course of the implementation:

DupOut

The first aha moment was discovering the "dupOut" operation. The inet.run examples already included a "dup" operation which takes one positive (input) and two negative (output) edges of the same type and duplicates the input into two outputs. "dupOut" is the same, but with signs flipped. It takes one negative edge and duplicates it into two positive edges — effectively duplicating code instead of a duplicating data.

For example, here is what happens when we duplicate an "Append" operation:

It might not seem like a lot, but this interaction alone lets us duplicate anything.

Rules as duplicated computation

The other profound realization was that I could use dupOut to duplicate a Rule.

...and that when I do so, I can effectively express a partially-applied function that gets duplicated.

Maybe it could be written in Rust?

That's about where I stopped in 2023. In the meantime, I worked on a continuation-passing-style virtual machine and otherwise found ways to satisfy the itch for esoteric programming environments.

But this year, I finally thought:

What if I took the idea of inet.run and turned it into a compile-time Rust thing. Could I model that with the Rust type system?

Now, for context, me and the Rust type system are not best friends. It's either the compiler being smarter than me and seeing a race condition I've missed... or it's me being smarter than the compiler, and running head-first into a not-yet-implemented RFC. It can sometimes feel like there is a much simpler system hiding within the Rust compiler, which struggles to be expressed through the syntax of Rust.

So, with mediocre hopes in place, I set out to model an agent:

The first point was dealing with ownership. It is a crucial aspect of the Rust memory management system, after all.

From my prior experimentation, I knew that every agent's principal port points either at another agent's principal port—in which case the two have to interact with each other, and thus can be tracked by the runtime—or points to another agent's auxiliary port, in which case the first agent has to wait.

This line of thinking led to the idea that the principal port can own the rest of the agent.

struct Append {
  // input1 is the primary port, which is not a field
  input2: PositivePort<List>,
  output: NegativePort<List>,
}
impl Agent for Append {
  type Principal = PositivePort<List>; // e.g.
  // ...
}

To model types correctly, I could use enums to list out all the positive and negative agent symbols:

enum PositiveList<T> {
  Cons(PositivePort<T>, PositivePort<List<T>>),
  Null(),
  // ...
}
enum NegativeList<T> {
  Append(PositivePort<List<T>>, NegativePort<List<T>>),
  // ...
}
impl<T> Interaction for (PositiveList<T>, NegativeList<T>) {
  fn interact(positive: PositiveList<T>, negative: NegativeList<T>) {
    match (positive, negative) {
      // ...
    }
  }
}

However, doing it this way would mean that a type defined by one crate can never be extended by another—which would certainly be not ideal.

So, in the end, I landed on a model where only the positive, "data" agents are enumerated:

enum List<T> {
  Cons{
    item: PositivePort<T>, 
    rest: PositivePort<List<T>>
  },
  Null(),
  // ...
}
struct Append<T>(PositivePort<List<T>>, NegativePort<List<T>>);

impl<T> NegativeAgent for Append<T> {
  type Type = List<T>;
  fn interact(self, input1: List<T>) {
    let Append(input2Port, outputPort) = self;
    match input1 {
      // ...
    }
  }
}

Note: because somebody (me) is going to be confused about signs about ten seconds from now:

• Auxiliary ports are termed positive/negative from the perspective of the agent holding them.
• Agents are termed positive/negative from the perspective of other agents surrounding them.

Append has 3 ports: it holds the negative end of the edge of its inputs, and the positive edge of its output. One of its inputs is its primary port (since its "waiting" on one of the two lists it needs to process).

Per the convention just laid out: Append is a negative agent, because its primary port is negative from the perspective of others. The other input of append is a "positive" port, since it expects a positive agent on the other side. The output of append is a "negative" port, since it expects a negative agent on the other side.

Modeling edges

..that's about where the easy part of the modeling ends.

The real stumbling block, which consumed the rest of the time, turning a Saturday project into a week-long project, was modeling the edges between agents. 😁

To remind, we want agents to be owned by their principal port. In turn, agents own their auxiliary ports—thus forming a tree of ownership which starts at a pair of principle ports looking at each other and expands out to the rest of the agents.

Some fiddling with the type system can give us half of that already:

enum PositivePort<T> {
  Principal(Box<T>), // We own the memory of the other agent, while it "waits" on us
  Auxiliary(), // ??? We aren't owned by the other agent (else it'd be our principal port), and we don't own them (since it's their auxiliary too)
}
enum NegativePort<T> {
  Principal(Box<dyn NegativeAgent<Type = T>>),
  Auxiliary(), // ???
}

The trouble comes when we start modeling auxiliary ports connected to other auxiliary ports...

In that case, each agent will have an "auxiliary" port pointing... at the other agent's auxiliary port. Which points back to the first agent! It's a reference cycle, and the only way to break it is to wait for one of the two ends of the edge to become a principal port, at which point we can make it be owned by the other end. (Or, if both ends turn into principal ports, we add them to a queue for processing.)

I iterated through a few versions of the auxiliary port handling; experimenting in short bursts, before realizing that the newest idea, too, won't work.

At first, I thought that maybe I can use Weak references to keep track of the other port.

// PortHeap describes the other end of an edge
enum PortHeap<T, Other_Side> {
  Principal(Box<T>), // Other end is a principal port - we own it
  Auxiliary(Weak<Mutex<PortHeap<Other_Side>>>), // Other end is an auxiliary port - we reference it
  Invalid, // We need this for mem::replace
}
type PositivePort<T> = Arc<Mutex<PortHeap<T, dyn NegativeAgent<Type = T>>>>;
type NegativePort<T> = Arc<Mutex<PortHeap<dyn NegativeAgent<Type = T>, T>>>;

Then we can implement linking of two ports like so:

fn link<T>(p: PositivePort<T>, n: NegativePort<T>, queue: _) {
  // 1. Take the locked ports out of the Mutexes
  let mut p_lock = p.lock().unwrap(); // ???
  let mut n_lock = n.lock().unwrap(); // ???

  let n = mem::replace(&mut n_lock, PortHeap::Invalid);
  let p = mem::replace(&mut p_lock, PortHeap::Invalid);

  // 2. Depending on the states of the two ports, take appropriate action
  match (p, n) {
    // Principal <-> Principal - add to queue, we need to process this
    (PortHeap::Principal(p), PortHeap::Principal(n)) => {
      queue.add(p, n);
    }
    // Auxiliary <-> * - lock the auxiliary end and write the principal there
    (PortHeap::Auxiliary(weak_p), n) => {
      let p = weak_p.upgrade().unwrap();
      let mut p_lock = p.lock().unwrap(); // !!!
      *p_lock = n;
    }
    (p, PortHeap::Auxiliary(weak_n)) => {
      let n = weak_n.upgrade().unwrap();
      let mut n_lock = n.lock().unwrap(); // !!!
      *n_lock = p;
    }
    // Invalid <-> * - Shouldn't get here?
    (_, PortHeap::Invalid) | (PortHeap::Invalid, _) => unreachable!(),
  }
}

And it works! 🎉

And then it deadlocks with multiple threads! 😭

The culprit seems to be locking the far end of an edge. If both auxiliary ports of an auxiliary-auxiliary edge are upgraded at the same time, each link operation locks its "near" end first (lines marked ???), before locking the "far" end (lines marked !!!). Since each operation's "near" end is the other operation's "far" end, it turns into a perfect, by-the-book deadlock!

I then proceeded to draw diagrams on paper of various ways of resolving that deadlock. I assumed that that having two Mutexes per edge was the problem, and proceeded to think of ways to to have a single Mutex per edge.

What did work, eventually, was moving the Arc<Mutex<_>> inward, and letting the heap-allocated portions point at each other, like so:

// EdgeHeap describes an auxiliary-auxiliary edge
enum EdgeHeap<T> {
  Unlinked,                          // ! Both auxiliary ports of the edge remain unlinked
  PositiveLinked(PositivePort<T>),   // ! The NegativePort::Auxiliary was linked to something
  NegativeLinked(NegativePort<T>),   // ! The PositivePort::Auxiliary was linked to something
}
enum PositivePort<T> {
  Principal(Box<T>),
  Auxiliary(Arc<Mutex<EdgeHeap<T>>>), // ! Unlinked or PositiveLinked
}
enum NegativePort<T> {
  Principal(Box<dyn NegativeAgent<Type = T>>),
  Auxiliary(Arc<Mutex<EdgeHeap<T>>>), // ! Unlinked or NegativeLinked
}

fn link<T>(p: PositivePort<T>, n: NegativePort<T>, queue: _) {
  // 1. Depending on the states of the two ports, take appropriate action
  match (p, n) {
    // Principal <-> Principal - add to queue, we need to process this
    (PositivePort::Principal(p), NegativePort::Principal(n)) => {
        queue.add(p, n);
    }
    // Auxiliary <-> * - move the other end into the Auxiliary
    (PositivePort::Auxiliary(mutex), n) => {
      let mut heap = mutex.lock();
      *heap = match heap {
        // Auxiliary <- Heap -> * - move the port into the EdgeHeap
        Unlinked => NegativeLinked(n),
        // * <- Heap -> * - eliminate the intervening EdgeHeap
        PositiveLinked(p) => return link(p, n, queue),
        // Unreachable, there should be only one PositivePort::Auxiliary for this port
        NegativeLinked(_n) => unreachable!(),
      }
    }
    (p, NegativePort::Auxiliary(mutex)) => {
      let mut heap = mutex.lock();
      *heap = match heap {
        Unlinked => PositiveLinked(p),
        NegativeLinked(n) => return link(p, n, queue),
        PositiveLinked(_p) => unreachable!(),
      }
    }
  }
}

Insert dramatic pause here, as the author frantically waves hands while mentally visualizing the code

This ends up not deadlocking, because of the restrictions on EdgeHeap states noted in the comments starting with !.

Work-stealing concurrency

In parallel to modeling edges and node types, I was also working on making an execution engine that can run in multiple threads. That's the main thing I felt was missing from the inet-js project which inspired me to start looking into interaction nets in the first place. Plus, the ease of multi-threading is like half the reason I picked Rust for this (the other half being the type system).

I didn't have to spend as much time here as on other parts of the project, thanks to the excellent crossbeam::deque crate, which gives you work-stealing queues right away. (We want a work-stealing job queue, because it means that tasks started by a thread can stay local to it, and thus utilize CPU caches better. Agents can only be activated by other agents next to them, so this is like a perfect usecase for that.)

In the end, my main loop looks something like this:

struct Context {
  worker: Worker<Task>,
  stealers: Vec<Stealer<Task>>,
}
impl Context {
  // queue() is called by the link() operation above, when two principal ports are linked to each other
  fn queue(&self, task: Task) {
    self.worker.push(task);
  }
  // run() picks tasks as long as they are some available.
  fn run(&self) {
    while let Some(next) = self.worker.pop().or_else(|| {
      iter::repeat_with(|| {
        self.stealers
          .iter()
          .map(|s| s.steal_batch_and_pop(&self.worker))
          .collect::<Steal<_>>()
      })
      .find(|s| !s.is_retry())
      .and_then(|s| s.success())
    }) {
      next.execute(&self);
    }
  }
  // run_multithreaded() starts multiple run() threads
  fn run_multithreaded(workers: usize) {
    crossbeam_utils::thread::scope(|s| {
      // List of workers, one for each thread
      let workers = (0..workers).map(|_| Worker::new_fifo()).collect::<Vec<_>>();
      // List of stealers, gets passed to each worker (so it can find queues to steal from)
      let stealers = workers.iter().map(|w| w.stealer()).collect::<Vec<_>>();
      
      for worker in workers {
        let stealers = stealers.clone();
        s.spawn(move |_| Self {worker, stealers}.run());
      }
    }).unwrap();
  }
}

Finally, a sample computation

I ended up expanding the types above to allow for introspection of the running graph; however, just describing that would easily double the size of this post... so, separate post it is. Enjoy the pretty diagrams for now.

Instead, I would rather leave you with an example of what the current version of the code can do.

Suppose we have a computation we want to compute, which looks like this:

result = x * 10 + 4 * 6 + 100 * y

We can represent individual operations with agents like so:

// Mul awaits the primary port to be filled with the first number before looking for a the number in its second port
struct Mul(PositivePort<i32>, NegativePort<i32>);
impl NegativeAgent for Mul {
  type Principal = i32;
  fn interact(self, arg1: i32, ctx: &Context) {
    let Mul(arg2, result) = self;
    arg2.link(NegativePort::new(Mul2(arg1, result)))
  }
}

// Mul2 already has its first number filled, and now awaits its primary port to be filled with a second number
struct Mul2(i32, NegativePort<i32>);
impl NegativeAgent for Mul2 {
  type Principal = i32;
  fn interact(self, arg2: i32, ctx: &Context) {
    let Mul(arg1, result) = self;
    result.link(PositivePort::new(arg1 * arg2))
  }
}

The full computation then looks like so:

fn compute() -> (NegativePort<i32>, NegativePort<i32>, PositivePort<i32>) {
  let (x_pos, x_neg) = PositivePort::create();
  let (y_pos, y_neg) = PositivePort::create();
  
  let ten = PositivePort::new(10);
  let x_times_ten = PositivePort::create_with(|neg| {
    x_pos.link(NegativePort::new(Mul(ten, neg)));
  });
  
  let four = PositivePort::new(4);
  let six = PositivePort::new(6);
  let four_time_six = PositivePort::create_with(|neg| {
    four.link(NegativePort::new(Mul(six, neg)));
  });
  
  let hundred = PositivePort::new(100);
  let hundred_times_y = PositivePort::create_with(|neg| {
    hundred.link(NegativePort::new(Mul(y_pos, neg)));
  });
  
  let part_result = PositivePort::create_with(|neg| {
    x_times_ten.link(NegativePort::new(Add(four_time_six, neg)));
  });
  let result = PositivePort::create_with(|neg| {
    part_result.link(NegativePort::new(Add(hundred_times_y, neg)));
  });
  
  return (x_neg, y_neg, result_pos);
}

Crucially, we can see that the agents representing 4 * 6 already have principal ports pointing at each other.

Letting the computation of this subset of the graph proceed, we get:

So, that's one cool thing about interaction nets: not only do they let you run massively parallel work, but they also automatically pre-compute constant expressions! 🎉

Further reading

If you found this post interesting (and not just painfully complicated; it was really hard to explain all of that!), here are some more things to check out:

• Yves Lafont's original paper (1989). It's good, short, and sweet, and holds up nicely 37 years later!
• Yves Lafont's Interaction Combinators paper (1997). I haven't read it fully yet, but it shows how a total of 3 symbols (6 with signs) are enough to express/simulate any interaction net.
• HigherOrderCO's Bend virtual machine. A virtual machine on top of Interaction Combinators, also written in Rust. Not exactly sure what they are on about (it's one of those rewrite-the-internet companies), but it looks interesting.
• inet-js. My initial inspiration to investigate interaction nets further, and a pretty cool project in its own right.
• graphviz. neato and dot were godsends in making all the nice diagrams in this blog post. If I had to draw those by hand... whew.
• The code behind this post: inet-rust ((commit as of writing)). It's not nearly as nice as the samples above, since I still haven't found a nice way to represent DupOut, but it's getting there.

Browse more articles?

← Wordle in LibreOffice Articles tagged technology (17/17) →|

|← Articles tagged interaction-nets (1/1) →|

← Great webcomics I love Articles on this blog (50/50) →|