Interaction Net Reducer Algorithm based on Taelin's algorithm

inet.rs

// An address is just a pointer to some agent inside the interaction net.
#[derive(Clone, Copy, PartialEq, Eq)]
pub struct Address(usize);

/// A slot is part of an agent that can connect to other ports.
#[derive(Clone, Copy, PartialEq, Eq)]
pub struct Slot(usize);

impl Slot {
    /// The main port is always zero
    pub fn is_main(&self) -> bool {
        self.0 == 0
    }
}

impl Address {
    /// This function creates a new port address using an address
    pub fn with(self, slot: usize) -> Port {
        Port {
            address: self,
            slot: Slot(slot),
        }
    }
}

/// A port is a pointer to a port inside an agent.
#[derive(Clone, Copy, PartialEq, Eq)]
pub struct Port {
    pub address: Address,
    pub slot: Slot,
}

impl Port {
    /// The root node is on the address zero
    pub fn is_root(&self) -> bool {
        ROOT == *self
    }
}

pub const ROOT: Port = Port {
    address: Address(0),
    slot: Slot(0),
};

/// An agent is a construction that can interact with some other things.
pub struct Agent {
    pub kind: Kind,
    pub ports: [Port; 3],
}

impl Agent {
    pub fn new(address: Address, kind: Kind) -> Self {
        Agent {
            kind,
            ports: [address.with(0), address.with(1), address.with(2)],
        }
    }
}

#[derive(Clone, Copy, PartialEq, Eq)]
pub enum Kind {
    Erased = 0,
    Constructor,
    Duplicator,
}

#[derive(Default)]
pub struct InteractionNet {
    pub nodes: Vec<Agent>,
    pub reuse: Vec<Address>,
}

impl InteractionNet {
    /// Gets a new location for a new agent.
    #[inline(always)]
    fn get_new_address(&mut self) -> Address {
        self.reuse.pop().unwrap_or(Address(self.nodes.len()))
    }

    /// Allocates a new agent based on the kind
    #[inline(always)]
    pub fn alloc(&mut self, kind: Kind) -> Address {
        let address = self.get_new_address();
        self.nodes[address.0] = Agent::new(address, kind);
        address
    }

    /// Frees a port and adds it to the reuse queue.
    #[inline(always)]
    pub fn free(&mut self, address: Address) {
        self.reuse.push(address)
    }

    /// Enters inside a port and returns the other port
    #[inline(always)]
    pub fn enter(&mut self, port: Port) -> Port {
        self.nodes[port.address.0].ports[port.slot.0]
    }

    #[inline(always)]
    pub fn get(&mut self, port: Port) -> &mut Port {
        &mut self.nodes[port.address.0].ports[port.slot.0]
    }

    #[inline(always)]
    pub fn agent(&self, address: Address) -> &Agent {
        &self.nodes[address.0]
    }

    #[inline(always)]
    pub fn agent_mut(&mut self, address: Address) -> &mut Agent {
        &mut self.nodes[address.0]
    }

    #[inline(always)]
    pub fn link(&mut self, a: Port, b: Port) {
        *self.get(a) = b;
        *self.get(b) = a;
    }

    pub fn reduce(&mut self, mut prev: Port) -> Port {
        let mut path = vec![];

        loop {
            let next = self.enter(prev);

            if next.is_root() {
                path.get(0).cloned().unwrap_or(ROOT);
            }

            if next.slot.is_main() {
                if prev.slot.is_main() {
                    self.rewrite(next.address, prev.address);
                    prev = path.pop().unwrap();
                    continue;
                } else {
                    return next;
                }
            }

            path.push(prev);
            prev = next.address.with(0);
        }
    }

    // Reduces the net to a normal form
    pub fn normal(&mut self) {
        let mut warp = vec![ROOT];
        while let Some(prev) = warp.pop() {
            let next = self.reduce(prev);
            if next.is_root() {
                warp.push(next.address.with(1));
                warp.push(next.address.with(2));
            }
        }
    }

    pub fn rewrite(&mut self, port_a: Address, port_b: Address) {
        let agent_a = self.agent(port_a);
        let agent_b = self.agent(port_b);

        if agent_a.kind == agent_b.kind {
            let port_aux_a = self.enter(port_a.with(1));
            let port_aux_b = self.enter(port_b.with(1));
            self.link(port_aux_a, port_aux_b);

            let port_aux_a = self.enter(port_a.with(2));
            let port_aux_b = self.enter(port_b.with(2));
            self.link(port_aux_a, port_aux_b);

            self.reuse.push(port_a);
            self.reuse.push(port_b);
        } else {
            // DUP-CONS interaction
        }
    }
}