Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Interaction combinators
# -*- 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])
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.