Introduction to symmetric interaction combinators(SIC).

A distant civilization travels to earth and lands a ship, they have never developed an alphabet, numbers are a foreign concept to them, the pen-n-paper game sprouts is the most competitive activity in their homeworld, the ship's computer is programmed entirely with drawings.

Nodes

The drawings show 3 different types of nodes, we'll give them names, so let's say: Delta(D), Gamma(G) and Epsilon(E). Each one has a single primary port, Delta and Gamma have two auxiliary ports(x, y):

Rules

The nodes are wired together, and each combination of connected primary ports between two nodes result in a different interaction. The following four rules are capable of encoding all of computation:

A black triangle with a white dot indicates that it can be either a Delta or Gamma node, but in the second rule, both triangles have to be of the same kind.

• Ann1(E><E): Two epsilons, annihilate each other.
• Ann2(D><D/G><G):Two gammas/deltas, annihilate each other and connect their wires in parallel.
• Com1(E><D/E><G): An epsilon and a gamma/delta, create two epsilons connected to the outgoing ports.
• Com2(D><G): A gamma and a delta create two new nodes connected into a square.

Annihilation Annotation

As an extra aid to understanding the system, or as a way to legitimize the documentation since nobody actually believes me when I tell them that programming can be done entire with doodles, we'll use a side-by-side notation to represent graphs textually:

Da          ; A Del node, with id: #a
Gb(Ec)      ; A Gam node #b, with an Eps connected into auxliary x.
Ec ~> Gb.x  ; An Eps node #c, connected to #b.x by its primary.
Ge >< Df    ; A Gam node #e, connected to #f by their primaries. 

But really, the best medium for this, is pen and paper.

Graph	Ann
	• Gb(Da, Ec) >< Ed, Da(Da.y, Da.x) ~> Gb.x, Ec ~> Gb.y • Ec >< Ef, Da(Da.y, Da.x) >< Ee • Da(Da.y, Da.x) >< Ee • Eg >< Eh

Each transformation is equal to a computing step, every operation operates locally so the order of operation does not matter, any two nodes connected by their primary port can be reduced at once.

Booleans

It's important to understand that booleans are encoded as nets and not single nodes, this means that true and false are transformations that will force the graph to reduce in either one of two states.

; True
Ga(Eb, Gc.x) ~> Gc.y
Eb ~> Ga.x
Gc(Ga.y, Ga) ~> nil

; False
Ea ~> Gc.x
Gb(Gb.y, Gb.x) ~> Gc.y
Gc(Ea, Gb) ~> nil

On the graph below, the nets to the left of the line are true(above) and false(below), when wired to the right side of the line, each rewrites the graph to send out either one of two nodes:

Loops

Not all graphs stabilize, for example, the following graph will loop for ever, creating its else again and again, resulting into an infinite loop, you can see it in action in this video.

Evaluation

Programming is done entirely by drawing a graph of connected nodes, and evaluation is done by rewriting primary port connections based on the four rules, until it stabilizes:

Graph

Ann

• Gb(Ec, Ga) >< Dd, Ga(Ga.y, Ga.x) ~> Gb.y, Ec ~> Gb.x • Ga(Ga.y, Ga.x) >< Dg(Gf.y, Gh.y), Ec >< De(Gf.x, Gh.x), Gf(De.x, Dg.x) ~> nil, Gh(De.y, Dg.y) ~> nil • Di(Gj.x, Gl.x) >< Dk(Gj.y, Gl.y), Ec >< De(Gf.x, Gh.x), Gf(De.x, Gj) ~> nil, Gh(De.y, Gl) ~> nil, Gj(Di.x, Dk.x) ~> Gf.y, Gl(Di.y, Dk.y) ~> Gh.y • Ec >< De(Gf.x, Gh.x), Gf(De.x, Gj) ~> nil, Gh(De.y, Gl) ~> nil, Gj(Gj.y, Gj.x) ~> Gf.y, Gl(Gl.y, Gl.x) ~> Gh.y Gf(Em, Gj) ~> nil, Gh(En, Gl) ~> nil, Gj(Gj.y, Gj.x) ~> Gf.y, Gl(Gl.y, Gl.x) ~> Gh.y, Em ~> Gf.x, En ~> Gh.x

I/O

Communication with the outside world, like handling incoming events and outputting data, is a matter of connecting into open ports, for example, if a program is made of an Epsilon and a Gamma with primary ports pointing leftward, the incoming event is represented as the left-side of the boundary, and its output as the right-side of the boundary.

In one case, the program will route the Episilon into the Gamma node and emit an Epsilon; in the other, a Delta:

• Symmetric Interaction Combinators, Uxntal.
• Interaction Nets in Motion, animation by Yves Lafont.