non-complete implementation of an interaction net

interaction_net.py

class Agent:
    def __init__(self, name, ports=None):
        self.name = name
        self.ports = ports if ports else []
        # Each element of ports is either None or a tuple (other_agent, other_port_index)

    def __repr__(self):
        return f"{self.name}"

def connect(a, pa, b, pb):
    a.ports[pa] = (b, pb)
    b.ports[pb] = (a, pa)

def disconnect(a, pa):
    # Disconnect port pa of agent a and its counterpart
    link = a.ports[pa]
    if link is not None:
        b, pb = link
        a.ports[pa] = None
        b.ports[pb] = None

class INT(Agent):
    def __init__(self, val):
        super().__init__(f"INT({val})", [None])
        self.val = val

class NIL(Agent):
    def __init__(self):
        super().__init__("NIL", [None])

class CONS(Agent):
    def __init__(self):
        super().__init__("CONS", [None, None, None])

class FOO(Agent):
    def __init__(self):
        # ports: 0 principal, 1 n, 2 xs, 3 acc
        super().__init__("FOO", [None, None, None, None])

class ROOT(Agent):
    def __init__(self):
        super().__init__("ROOT", [None])

def build_list(lst):
    if not lst:
        return NIL()
    else:
        head = INT(lst[0])
        tail_list = build_list(lst[1:])
        cons = CONS()
        # connect cons head
        connect(cons, 1, head, 0)
        # connect cons tail
        connect(cons, 2, tail_list, 0)
        return cons

def extract_list(agent):
    if agent.name == "NIL":
        return []
    elif agent.name == "CONS":
        head_agent, _ = agent.ports[1]
        tail_agent, _ = agent.ports[2]
        return [head_agent.val] + extract_list(tail_agent)
    else:
        # Should be a list structure
        raise ValueError("Not a list structure")

def is_principal_port(agent, port):
    # Assume port 0 is always principal for all agents
    return port == 0

def find_redex(agents):
    # A redex is a pair of agents connected on their principal ports
    for a in agents:
        if a.ports and a.ports[0] is not None:
            b, pb = a.ports[0]
            if b is not None and is_principal_port(a, 0) and is_principal_port(b, pb):
                return (a, b)
    return None

def reduce_foo(a, b):
    # Identify foo_agent and other
    if a.name.startswith("FOO"):
        foo_agent = a
        other = b
    elif b.name.startswith("FOO"):
        foo_agent = b
        other = a
    else:
        return False  # Not a FOO redex

    # foo_agent ports: [0 principal, 1 n, 2 xs, 3 acc]
    n_agent, _ = foo_agent.ports[1]
    xs_agent, _ = foo_agent.ports[2]
    acc_agent, _ = foo_agent.ports[3]

    if not n_agent.name.startswith("INT"):
        return False

    n = n_agent.val

    # Cases:

    # Case 1: n == 0 => return acc
    if n == 0:
        # Disconnect from other
        disconnect(foo_agent, 0)
        # Now connect other to acc_agent
        connect(other, 0, acc_agent, 0)
        foo_agent.ports = [None, None, None, None]
        return True

    # Case 2: xs == NIL and n > 0 => return acc
    if xs_agent.name == "NIL" and n > 0:
        disconnect(foo_agent, 0)
        connect(other, 0, acc_agent, 0)
        foo_agent.ports = [None, None, None, None]
        return True

    # Case 3: xs = CONS(...)
    if xs_agent.name == "CONS":
        head_int, _ = xs_agent.ports[1]
        tail_list, _ = xs_agent.ports[2]
        if head_int.name.startswith("INT"):
            if head_int.val == 1 and n > 0:
                # foo(n, 1:rest, acc) => foo(n-1, rest, CONS(1, acc))
                new_cons = CONS()
                one_int = INT(1)
                connect(new_cons, 1, one_int, 0)
                connect(new_cons, 2, acc_agent, 0)

                new_foo = FOO()
                connect(new_foo, 1, INT(n-1), 0)
                connect(new_foo, 2, tail_list, 0)
                connect(new_foo, 3, new_cons, 0)

                disconnect(foo_agent, 0)
                connect(other, 0, new_foo, 0)

                foo_agent.ports = [None, None, None, None]
                return True
            else:
                # foo(n, h:rest, acc) with h != 1 => foo(n, rest, acc)
                new_foo = FOO()
                connect(new_foo, 1, INT(n), 0)
                connect(new_foo, 2, tail_list, 0)
                connect(new_foo, 3, acc_agent, 0)

                disconnect(foo_agent, 0)
                connect(other, 0, new_foo, 0)

                foo_agent.ports = [None, None, None, None]
                return True

    return False

def reduce_step(agents):
    redex = find_redex(agents)
    if redex is None:
        return False
    a, b = redex
    if "FOO" in a.name or "FOO" in b.name:
        return reduce_foo(a, b)
    return False

def run(agents):
    while reduce_step(agents):
        pass

def collect_list_agents(agent, visited=None):
    if visited is None:
        visited = set()
    if agent in visited:
        return []
    visited.add(agent)
    if agent.name == "NIL":
        return [agent]
    elif agent.name == "CONS":
        # collect from head
        head_agent, _ = agent.ports[1]
        tail_agent, _ = agent.ports[2]
        return [agent] + collect_list_agents(head_agent, visited) + collect_list_agents(tail_agent, visited)
    elif agent.name.startswith("INT"):
        return [agent]
    else:
        return [agent]

def make_foo_call(n, xs, acc):
    foo_agent = FOO()
    root = ROOT()
    n_int = INT(n)
    xs_agent = build_list(xs)
    acc_agent = build_list(acc)

    connect(foo_agent, 1, n_int, 0)
    connect(foo_agent, 2, xs_agent, 0)
    connect(foo_agent, 3, acc_agent, 0)
    connect(root, 0, foo_agent, 0)

    # Collect all agents for convenience
    all_agents = [root, foo_agent, n_int, acc_agent]
    all_agents += collect_list_agents(xs_agent)
    all_agents += collect_list_agents(acc_agent)
    return all_agents

def get_result(root):
    if root.ports[0] is None:
        return None
    res_agent, _ = root.ports[0]
    if res_agent.name == "NIL":
        return []
    elif res_agent.name == "CONS":
        return extract_list(res_agent)
    else:
        return []

if __name__ == "__main__":
    test_cases = [
        (2, [1, 0, 1], []),
        (1, [1, 0], []),
        (0, [1, 0], []),
        (3, [0, 1, 1, 0, 1], [])
    ]

    for (n, xs, acc) in test_cases:
        agents = make_foo_call(n, xs, acc)
        run(agents)
        root = agents[0]
        print(f"foo({n}, {xs}, {acc}) -> {get_result(root)}")