Interaction combinators

interaction_combinators.py

# -*- encoding: utf-8 -*-
# Implements symmetric interaction combinators
# I took some ideas from Victor Maia's projects. 

# Bunch of cells form an interaction net.
# It's a half-edge graph.
class Cell:
    def __init__(self, kind):
        self.ports = (Port(self), Port(self), Port(self))
        self.kind = kind # 'era', 'con', 'fan'

class Port:
    def __init__(self, cell):
        self.cell = cell
        self.link = self # to other port

# The interaction net functions as a substrate in this implementation.
# At any time there are several open ports
# that are either I/O or inactive program fragments.
# Although the input language is supposed to be turing-complete,
# the halting part is attempted to be kept out from the substrate.

# The graph is evaluated when it is not in a normal form.
# In the sequential implementation everything evaluates immediately.
# Otherwise you would add active pairs into reduction queue.
def link(port_a, port_b):
    if is_active(port_a, port_b):
        interaction(port_a.cell, port_b.cell)
    else:
        port_a.link = port_b
        port_b.link = port_a

# The first port in each cell is a principal port.
# An active pair forms when principal ports are connected.
def is_active(port_a, port_b):
    cell_a = port_a.cell
    cell_b = port_b.cell
    return port_a is cell_a.ports[0] and port_b is cell_b.ports[0]

# Interactions can be divided to two groups, same-kind and different-kind.
def interaction(x, y):
    if x.kind == y.kind:
        # Same-kind interactions are eliminating.
        if kind == 'era':
            pass
        elif kind == 'con':
            link(x.ports[1].link, y.ports[1].link)
            link(x.ports[2].link, y.ports[2].link)
        elif kind == 'fan':
            link(x.ports[1].link, y.ports[2].link)
            link(x.ports[2].link, y.ports[1].link)
        # at this point you can reclaim x, y
    # ──┐                   erasing interaction can reuse the other cell.
    #  y├────╸x
    # ──┘
    # -------------
    # ──╸ x
    # ──╸ y
    elif x.kind == 'era':
        y.kind = x.kind
        a = y.ports[1].link
        b = y.ports[2].link
        link(a, x.ports[0])
        link(b, y.ports[0])
    elif y.kind == 'era':
        x.kind = y.kind
        a = x.ports[1].link
        b = x.ports[2].link
        link(a, x.ports[0])
        link(b, y.ports[0])
    else:
        # Interactions between constructors and duplicators.
        # Everything duplicates as they slide past each other.
        # ──┐       ┌──
        #  x├───────┤y
        # ──┘       └──
        # -------------
        #   ┌───────┐  
        # ──┤y     x├──
        #   └───┐  ┌┘  
        #    ┌──┼──┘
        #   ┌┘  └───┐  
        # ──┤b     a├──
        #   └───────┘  
        a = Cell(x.kind)
        b = Cell(y.kind)
        link(b.ports[0], x.ports[1].link)
        link(y.ports[0], x.ports[2].link)
        link(a.ports[0], y.ports[1].link)
        link(x.ports[0], y.ports[2].link)
        link(a.ports[1], b.ports[1])
        link(a.ports[2], y.ports[1])
        link(x.ports[1], b.ports[2])
        link(x.ports[2], y.ports[2])