interaction_net.md

   1 # Interaction Net
   2
   3 Interaction nets are a way of performing computation by manipulating graphical diagrams according to a few simple rules. Interaction nets can be seen as one of many possible ways to create the lowest level basis for a [computer](computer.md), so we call them a *[model of computation](model_of_computation.md)*; other models of computation are for example [grammars](grammar.md), [Turing machines](turing_machine.md), [lambda calculus](lambda_calculus.md), [cellular automata](cellular_automaton.md) etc. -- all of these can be used to perform the same computations, though in different ways; interaction nets do this by representing a [program](program.md) with a [graph](graph.md)-like diagram which is then manipulated by some predefined rules and "reshaped" into another graph that represents the result of the performed computation. For this interaction nets can also be see as a kind of graphical [programming language](programming_language.md) (and even a textual one once we learn how to represent the graphical diagrams with text, which we call *interaction calculus*), though it's an extremely low level language (even things such as addition of natural numbers have to be programmed from scratch) that would be extremely impractical for everyday programming. The advantage of interaction nets is besides their simplicity usually said to be mainly their **[parallel nature](parallelism.md)**: as computation really means locally replacing parts of the network with predefined patterns, it is possible to simultaneously process multiple parts of the network at once, greatly speeding up the computation.
   4
   5 **WATCH OUT**: interaction nets are a bit confusing to newcomers because they look a bit like [logic circuits](logic_circuit.md) and so people think the computation happens by passing some data through the network -- THIS IS NOT THE CASE! The computation happens by CHANGING THE NETWORK itself, i.e. there is no data flowing, all that happens is REPLACING parts of the network with patterns defined by the rewriting rules (similarly to how in lambda calculus there are really no function calls but just text replacement). The idea is similar to that of rewriting rules in [grammars](grammar.md). Think of the connections less like of electric wires and more like of strings with knots that you tie and untie to perform the computation.
   6
   7 A general interaction net consists of nodes, or **agents**, that are connected with wires, or **edges**. Alongside the net exist **interaction rules** that say how patterns in the net get replaced with other patterns. A concrete definition of specific agent types and interaction rules is called an **interaction system** (i.e. *interaction net* is the general idea, like for example a *[cellular automaton](cellular_automaton.md)*, while *interaction system* is a specific realization of that idea, like for example *[game of life](game_of_life.md)*).
   8
   9 An **agent** is a type of block that may appear in the net. We may see it as a block with a number of ports (wires); it must have exactly one **principal port** (a kind of special, interacting port) and can have any number (even zero) of additional **auxiliary ports** (kind of "passive" ports) -- usually we just say the agent has *N* ports (where *N* >= 1) and we consider the first one to be the principal port, the other ones are auxiliary. Graphically the principal port is usually distinguished e.g. with an arrow. For example let's define three agents:
  10
  11 ```
  12     ______
  13    |      |
  14    | ZERO |==>
  15    |______|
  16     ______
  17    |      |
  18 ---| SUCC |==>
  19    |______|
  20     ______
  21 <==|      |
  22    | ADD  |---
  23    |      |
  24 ---|______|
  25 ```
  26
  27 Here we defined agents `ZERO`, with one port (only the principal one), `SUCC` (for "successor", one principal and one auxiliary port) and `ADD`, with three ports (one of them is principal).
  28
  29 Now let's define interaction rules with these agents. An interaction rule simply defines a pattern of interconnected agents that get replaced by another pattern; however **interaction rule may only be defined for agents both connected by their principal ports** (so called *active pairs*). Naturally, the rules also have to keep the interface (edges going in and out) of the group the same. Our interaction rules will be following:
  30
  31 ```
  32 rule 1:
  33        ______
  34       |      |       ______
  35       | ZERO |==><==|      |
  36       |______|      | ADD  |--- y    rewrites to            x ------------- y
  37                     |      |
  38                x ---|______|
  39
  40 rule 2:
  41
  42        ______
  43       |      |       ______                                ______        ______
  44  x ---| SUCC |==><==|      |         rewrites to     x <==|      |      |      |
  45       |______|      | ADD  |--- z                         | ADD  |------| SUCC |==> z
  46                     |      |                              |      |      |______|
  47                y ---|______|                         y ---|______|
  48 ```
  49
  50 Now we can perform a computation of 2 + 1. We first set up the interaction net that represents our program and then we'll be applying the interaction rules as long as we can:
  51
  52 ```
  53           representation of 2
  54    ______        ______        ______
  55   |      |      |      |      |      |       ______
  56   | ZERO |==>---| SUCC |==>---| SUCC |==><==|      |
  57   |______|      |______|      |______|      | ADD  |--- z
  58                  ______        ______       |      |
  59                 |      |      |      |==>---|______|
  60                 | ZERO |==>---| SUCC |
  61                 |______|      |______|
  62
  63                  representation of 1
  64
  65 apply rule 2:
  66
  67    ______        ______
  68   |      |      |      |       ______        ______
  69   | ZERO |==>---| SUCC |==><==|      |      |      |
  70   |______|      |______|      | ADD  |------| SUCC |==> z
  71    ______        ______       |      |      |______|
  72   |      |      |      |==>---|______|
  73   | ZERO |==>---| SUCC |
  74   |______|      |______|
  75
  76 apply rule 2:
  77                  ______
  78                 |      |       ______        ______        ______
  79                 | ZERO |==><==|      |      |      |      |      |
  80                 |______|      | ADD  |------| SUCC |==>---| SUCC |==> z
  81    ______        ______       |      |      |______|      |______|
  82   |      |      |      |==>---|______|
  83   | ZERO |==>---| SUCC |
  84   |______|      |______|
  85
  86 apply rule 1:
  87    ______        ______        ______        ______
  88   |      |      |      |      |      |      |      |
  89   | ZERO |==>---| SUCC |==>---| SUCC |==>---| SUCC |==> z
  90   |______|      |______|      |______|      |______|
  91
  92            representation of 3 (the result)
  93
  94 no more rules to apply
  95 ```
  96
  97 One specific very important interaction system is called **"interaction combinators"** -- it is a very simple system, consisting of three predefined agents and three patterns of rewrite rules, which can simulate any other system, i.e. it is [Turing complete](turing_complete.md) (we say the model is capable of *universal computation*); we know this because it's possible to e.g. automatically convert any [lambda calculus](lambda_calculus.md) expression to interaction combinators. The following show the interaction combinator rules (`E`, `D` and `Y` are the three agents, `t` is a general subtree with possible additional inputs `{...}`):
  98
  99 ```
 100
 101 erasing rule:                                            _____
 102         _____        _____                              |     |
 103   x ---|     |      |     |                        x <==|  E  |
 104   {...}|  t  |==><==|  E  |         rewrites to         |_____|
 105   y ---|_____|      |_____|                        {...} _____
 106                                                         |     |
 107                                                    y <==|  E  |
 108                                                         |_____|
 109
 110 duplication rule:
 111                                                           _____        _____
 112                                                          |     |------|     |
 113         _____        _____                          x <==|  D  | {...}|  t  |==> z
 114   x ---|     |      |     |--- z                         |_____|--. .-|_____|
 115   {...}|  t  |==><==|  D  |         rewrites to     {...} _____    X   _____
 116   y ---|_____|      |_____|--- w                         |     |--' '-|     |
 117                                                     y <==|  D  | {...}|  t  |==> w
 118                                                          |_____|------|_____|
 119
 120 non-termination rule:
 121
 122    _____                                  _____
 123   |     |       _____        _____       |     |                    .---.
 124   |  E  |==>---|     |      |     |---<==|  E  |    rewrites to    (     )
 125   |_____|      |  D  |==><==|  Y  |      |_____|                    '---'
 126            .---|_____|      |_____|---.
 127           (                            )
 128            '--------------------------'
 129 ```
 130
 131 TODO: text representation, compare text representation of interaction nets with grammars?
 132
 133 ## See Also
 134
 135 - [rule 110](rule110.md)