ic/inet/
mod.rs

1// Implements Interaction Combinators. The Abstract Calculus is directly isomorphic to them, so, to
2// reduce a term, we simply translate to interaction combinators, reduce, then translate back.
3
4#![allow(dead_code)]
5
6#[derive(Clone, Debug)]
7pub struct INet {
8  pub nodes: Vec<u32>,
9  pub reuse: Vec<u32>,
10  pub rules: u32,
11}
12
13// Node types are consts because those are used in a Vec<u32>.
14pub const ERA : u32 = 0;
15pub const CON : u32 = 1;
16pub const ANN : u32 = 2;
17pub const DUP : u32 = 3;
18pub const EQL : u32 = 0xFFFFFFFF;
19
20// The ROOT port is on the deadlocked root node at address 0.
21pub const ROOT : u32 = 1;
22
23// A port is just a u32 combining address (30 bits) and slot (2 bits).
24pub type Port = u32;
25
26// Create a new net, with a deadlocked root node.
27pub fn new_inet() -> INet {
28  INet {
29    nodes: vec![2,1,0,0], // p2 points to p0, p1 points to net
30    reuse: vec![],
31    rules: 0
32  }
33}
34
35// Allocates a new node, reclaiming a freed space if possible.
36pub fn new_node(inet: &mut INet, kind: u32) -> u32 {
37  let node : u32 = match inet.reuse.pop() {
38    Some(index) => index,
39    None => {
40      let len = inet.nodes.len();
41      inet.nodes.resize(len + 4, 0);
42      (len as u32) / 4
43    }
44  };
45  inet.nodes[port(node, 0) as usize] = port(node, 0);
46  inet.nodes[port(node, 1) as usize] = port(node, 1);
47  inet.nodes[port(node, 2) as usize] = port(node, 2);
48  inet.nodes[port(node, 3) as usize] = kind;
49  return node;
50}
51
52// Builds a port (an address / slot pair).
53pub fn port(node: u32, slot: u32) -> Port {
54  (node << 2) | slot
55}
56
57// Returns the address of a port (TODO: rename).
58pub fn addr(port: Port) -> u32 {
59  port >> 2
60}
61
62// Returns the slot of a port.
63pub fn slot(port: Port) -> u32 {
64  port & 3
65}
66
67// Enters a port, returning the port on the other side.
68pub fn enter(inet: &INet, port: Port) -> Port {
69  inet.nodes[port as usize]
70}
71
72// Type of the node.
73// 0 = era (erasure node)
74// 1 = con (abstraction or application)
75// 2 = dup (superposition or duplication)
76pub fn kind(inet: &INet, node: u32) -> u32 {
77  inet.nodes[port(node, 3) as usize]
78}
79
80// Links two ports.
81pub fn link(inet: &mut INet, ptr_a: u32, ptr_b: u32) {
82  inet.nodes[ptr_a as usize] = ptr_b;
83  inet.nodes[ptr_b as usize] = ptr_a;
84}
85
86// Reduces a wire to weak normal form.
87pub fn reduce(inet: &mut INet, prev: Port) -> Port {
88  let mut path = vec![];
89  let mut prev = prev;
90  loop {
91    let next = enter(inet, prev);
92    // If next is ROOT, stop.
93    if next == ROOT {
94      return path.get(0).cloned().unwrap_or(ROOT); // path[0] ?
95    }
96    // If next is a main port...
97    if slot(next) == 0 {
98      // If prev is a main port, reduce the active pair.
99      if slot(prev) == 0 {
100        inet.rules += 1;
101        rewrite(inet, addr(prev), addr(next));
102        prev = path.pop().unwrap();
103        continue;
104      // Otherwise, return the axiom.
105      } else {
106        return next;
107      }
108    }
109    // If next is an aux port, pass through.
110    path.push(prev);
111    prev = port(addr(next), 0);
112  }
113}
114
115// Reduces the net to normal form.
116pub fn normal(inet: &mut INet) {
117  let mut warp = vec![ROOT];
118  while let Some(prev) = warp.pop() {
119    let next = reduce(inet, prev);
120    if slot(next) == 0 {
121      warp.push(port(addr(next), 1));
122      warp.push(port(addr(next), 2));
123    }
124  }
125}
126
127// Rewrites an active pair.
128pub fn rewrite(inet: &mut INet, x: Port, y: Port) {
129  if kind(inet, x) == kind(inet, y) {
130    let p0 = enter(inet, port(x, 1));
131    let p1 = enter(inet, port(y, 1));
132    link(inet, p0, p1);
133    let p0 = enter(inet, port(x, 2));
134    let p1 = enter(inet, port(y, 2));
135    link(inet, p0, p1);
136    inet.reuse.push(x);
137    inet.reuse.push(y);
138  } else {
139    let t = kind(inet, x);
140    let a = new_node(inet, t);
141    let t = kind(inet, y);
142    let b = new_node(inet, t);
143    let t = enter(inet, port(x, 1));
144    link(inet, port(b, 0), t);
145    let t = enter(inet, port(x, 2));
146    link(inet, port(y, 0), t);
147    let t = enter(inet, port(y, 1));
148    link(inet, port(a, 0), t);
149    let t = enter(inet, port(y, 2));
150    link(inet, port(x, 0), t);
151    link(inet, port(a, 1), port(b, 1));
152    link(inet, port(a, 2), port(y, 1));
153    link(inet, port(x, 1), port(b, 2));
154    link(inet, port(x, 2), port(y, 2));
155  }
156}
ic/inet/mod.rs

ic/inet/
mod.rs
