Virtual machine interaction net bootstrap for https://inet.run/playground/

README.md

Sample run: (computes 3 + 2 * 4)

npx @cicada-lang/inet-js run https://gist.githubusercontent.com/bojidar-bg/6c52d1f1ed3fb3a583aaff9a184687fe/raw/73ab4e6d9dbcddaba230c529a4fc0c236a353db8/Nat_bootstrap.test.i | grep 'activeEdge-' | wc -l

Result:

11

Meaning: 11 bootstrapped nodes exist in the final graph, which is 10 s_add1 nodes and 1 s_zero node.

Hence: 3 + 2 * 4 = 10 \o/

Playground link

How it works:

A longer writeup would be necessary to explain the full operation, but in brief:

The bootstrapped nodes execute independently, without any "program" which walks a list of active nodes. This way, any improvements in the parallelism of the underlying executor would be immediatelly passed to the nodes.

Simulated nodes are represented by two node types, nodePos and nodeNeg -- depending on whether their active/primary edge is positive (an input) or negative (an output).

Each node holds its identity as a Symbol. Symbol is pretty similar to a Binary number, just because base two encoding makes for some rather short symbols without complicating the rest of the functionality.

Since any interaction that happens is guaranteed to be between a pair of (nodePos, nodeNeg), we can store the interaction rules with either of the two. Without loss of generality, we store the rules in nodePos.

The rules are represented as a SymbolMap(SymbolMap(Rule)) -- where SymbolMap is a simple structure that allows retrieving a particular entry in O(log2(symbolsize)) operations.

When an interaction occurs, we look up the positive node's Symbol in the first layer map, followed by the negative node's Symbol in the second map. Note that this mean two nodes could in theory share a symbol if they have different active edge signs, though we never make use of that.

The Rule-s themselves are implemented really succinctly (thanks to interaction nets, it felt quite profound the first time it clicked in place), with a rule node which outputs two lists of non-active edge connections for each of the two nodes that are part of the interaction, and collects a list of all the newly-created nodes as input.

To execute a Rule we duplicate it and then use an exec node to replace the missing inputs and grab the output.

And finally, the "magic" happens as we "inflate" the outputs by giving the newly-created nodes full references to duplicates of the rules table... aaand...

waves hands for dramatic effect

...they suddenly become normal nodePos-s and nodeNeg-s!

And the whole process can start anew!

How it was made:

Two sleepless nights (no caffeine, sheer force of will), plenty of headscratching to get the ideas flowing. It was a wonderfully fun challenge, I would definitelly recommend... assuming one has the time.

At first, I started with the rule table datastructure and got Symbol and SymbolMap done.

Then, there was some playing around with the generic del and dup nodes (those feel like something which would be best if it could be auto-generated), until I roughly mastered those.

Next, I got some preliminary rules going; at first the rule had a list of "Instructions" that would have had been executed in-order. Experimentation with the pop instruction led to discovering dupOut and the fact that serializing the instructions is unnecessary.

Armed with those new tools, I started tinkering with nodes and edges, but that's about where the first night was over and I decided to sleep on the issue instead.

Next time I set out to do things, I had already gotten the basic idea of what a node is - something with an active edge - and the rest of the edges kept in lists.

To store both positive and negative edges in a list, pos and neg were born; soon after nodePos and nodeNeg came to be.

..and the rest was just wiring everything up, making sure the instructions work, adding the inflateNode system.. ..testing everything a few times, fixing a few silly oversights (missing dup operators, etc.).. ..refactoring some of the names..

..writing out a Nat sample and testing that (nope, it did not work on first try).. ..getting everything out of the single file I had it in so far.. ..ironing out the issues around imports..

And finally writing this file. Tadah! (:

Update: 2023-10-30/31: One day later, realized the massive savings that can be achieved by duplicating the rules table lazily, hence the addition of Lazy.i. This simple change gets the runtime of the example bootstrap from nearly 13k steps to a mere 4k steps -- and takes a headless test testing squaring 10 * 10 from ~9 seconds to ~5 seconds. Executing rules which create more than one positive node is still O(rule table size), but at least those are a minority of the cases.

Potential future work:

The main thing missing at the moment for a full bootstrap is a parser and a compiler for the rules. As parsing and compiling seemed like the "less fun" part (and since we don't have IO), those has been left as an exercise for the reader.

Minimizing the bootstrap should be possible. A curious project might be to see how minimal it could be made, so that a bootstrap-in-bootstrap can be attempted reasonably. Note that according to Y. Lafont, 1997 (via Wikipedia), Interaction Combinators should be able to simulate any system with just three kinds of nodes (or perhaps six-ish to account for signs?); but I would rather not minimize the bootstrap that far.

// SPDX-License-Identifier: GPL-3.0-only

Connection.i

require "./SymbolMap.i" // Diamond imports don't work

// import { List, null } from "./List.i"
// import { del, delOut, dup, dupOut } from "./Generic.i"

type Edge
type Connection

node pos(
  edge: Edge,
  ------
  connection!: Connection,
)

node neg(
  ------
  connection!: Connection,
  edge: Edge,
)

rule dup(value!, a, b) pos(edge, connection!) {
  let aE, bE = dup(edge)
  pos(aE, a)
  pos(bE, b)
}

rule dup(value!, a, b) neg(connection!, edge) {
  let aE, bE, dO = dupOut()
  @connect(dO, edge)
  neg(a, aE)
  neg(b, bE)
}

rule del(value!) pos(edge, connection!) {
  del(edge)
}

rule del(value!) neg(connection!, edge) {
  delOut(edge)
}

type Invalid

node invalidConnection(
  connection: Connection,
  i!: Invalid
  ------
  i_: Invalid
)

node connectionPair(
  dummy!: List('A) // NOTE: it'd be much simpler if this could be just a function
  ------
  connectionPos: Connection,
  connectionNeg: Connection
)

rule connectionPair(dummy!, connectionPos, connectionNeg) null(dummy!) {
  let edge = neg(connectionNeg)
  pos(edge, connectionPos)
}

node connect(
  connectionA!: Connection,
  connectionB: Connection
  ------
)

rule connect(connectionA!, connectionB) dupOut(a, b, value!) {
  let aB, bB = dup(connectionB)
  connect(a, aB)
  connect(b, bB)
}

rule connect(connectionA!, connectionB) delOut(value!) {
  del(connectionB)
}

node connectPos(
  edgeA: Edge,
  connectionB!: Connection
  ------
)

rule connect(connectionA!, connectionB) pos(edgeA, connection!) {
  connectPos(edgeA, connectionB)
}

rule connectPos(edgeA, connectionB!) neg(connection!, edgeB) {
  @connect(edgeA, edgeB)
}

node connectNeg(
  connectionB!: Connection
  ------
  edgeA: Edge
)

rule connect(connectionA!, connectionB) neg(connection!, edgeA) {
  connectNeg(connectionB, edgeA)
}

rule connectNeg(connectionB!, edgeA) pos(edgeB, connection!) {
  @connect(edgeA, edgeB)
}

Generic.i

require "./List.i" // Diamond imports don't work

node del(
  value!: 'A
  ------
)

node delOut(
  ------
  value!: 'A
)


node dup(
  value!: 'A
  ------
  outA: 'A,
  outB: 'A
)

node dupOut(
  a: 'A,
  b: 'A
  ------
  out!: 'A
)

rule del(value!) delOut(value!) {
}

rule dup(value!, a, b) dupOut(aO, bO, out!) {
  @connect(aO, a)
  @connect(bO, b)
}

rule del(value!) dupOut(aO, bO, out!) {
  @connect(aO, del())
  @connect(bO, del())
}

// import { null, cons } from "./List.i"

rule del(value!) null(value!) {
}

rule del(value!) cons(head, tail, value!) {
  del(head)
  del(tail)
}

rule dup(value!, a, b) null(value!) {
  @connect(a, null())
  @connect(b, null())
}

rule dup(value!, a, b) cons(head, tail, value!) {
  let aH, bH = dup(head)
  let aT, bT = dup(tail)
  @connect(a, cons(aH, aT))
  @connect(b, cons(bH, bT))
}

Inflate.i

require "./Rule.i" // Diamond imports don't work

// import { List, null, cons } from "./List.i"
// import { del, dup } from "./Generic.i"
// import { lazyDup } from "./Lazy.i"
// import { Option, some, assertSome } from "./Option.i"
// import { Symbol } from "./Symbol.i"
// import { SymbolMap, symbolMapReplace, orEmptyMap } from "./SymbolMap.i"
// import { Edge, Connection, pos, neg,} from "./Connection.i"
// import { Output, Rule, rule, exec, node } from "./Rule.i"

node inflateNode(
  node!: Output,
  rules: SymbolMap(SymbolMap(Rule))
  ------
  rulesOut: SymbolMap(SymbolMap(Rule))
)

node inflateNodeAux(
  symbol: Symbol,
  rules: SymbolMap(SymbolMap(Rule)),
  activeConnection!: Connection,
  connections: List(Connection)
  ------
  rulesOut: SymbolMap(SymbolMap(Rule))
)

node nodePos(
  symbol: Symbol,
  rules: SymbolMap(SymbolMap(Rule)),
  activeEdge!: Edge,
  connections: List(Connection)
  ------
)

node nodeNeg(
  symbol: Symbol,
  connections: List(Connection)
  ------
  activeEdge!: Edge,
)

rule inflateNode(node!, rules, rulesOut) node(symbol, activeConnection, connections, result!) {
  inflateNodeAux(symbol, rules, activeConnection, connections, rulesOut)
}

rule inflateNodeAux(symbol, rules, activeConnection!, connections, rulesOut) pos(activeEdge, activeConnection!) {
  let rules = dup(rules, rulesOut)
  nodePos(symbol, rules, activeEdge, connections)
}

rule inflateNodeAux(symbol, rules, activeConnection!, connections, rulesOut) neg(activeConnection!, activeEdge) {
  nodeNeg(symbol, connections, activeEdge)
  @connect(rules, rulesOut)
}

node inflateNodes(
  outputs!: List(Output),
  rules: SymbolMap(SymbolMap(Rule))
  ------
)

rule inflateNodes(outputs!, rules) null(value!) {
  del(rules)
}

rule inflateNodes(outputs!, rules) cons(output, rest, value!) {
  let rules = inflateNode(output, rules)
  inflateNodes(rest, rules)
}

rule nodePos(symbolA, rules, activeEdge!, connectionsA) nodeNeg(symbolB, connectionsB, activeEdge!) {
  let rulesABack, rules, rulesA = symbolMapReplace(rules, symbolA)
  let ruleBack, rulesA, rule = symbolMapReplace(orEmptyMap(rulesA), symbolB)
  let rule = dup(rule, ruleBack)
  @connect(rulesABack, some(rulesA))
  
  let outputs = exec(connectionsA, connectionsB, assertSome(rule))
  
  inflateNodes(outputs, lazyDup(rules))
}

Lazy.i

require "./Generic.i" // Diamond imports don't work

// import { del, dup } from "./Generic.i"

type LazyDup(Element: @Type)

node lazyDup(
  value: 'A
  ------
  out!: 'A
)

node lazyDupAux(
  value: 'A
  ------
  outA!: 'A,
  outB: 'A
)

rule del(out!) lazyDup(value, out!) {
  del(value)
}

rule dup(out!, a, b) lazyDup(value, out!) {
  lazyDupAux(value, a, b)
}

rule del(out!) lazyDupAux(value, outA!, outB) {
  @connect(value, outB)
}

rule dup(out!, a, b) lazyDupAux(value, outA!, outB) {
  let value, valueClone = dup(value)
  @connect(value, outB)
  lazyDupAux(valueClone, a, b)
}

List.i

// == https://github.com/cicada-lang/inet-js/blob/master/std/datatype/List.i

type List(Element: @Type)

node null(
  --------
  value!: List('A)
)

node cons(
  head: 'A,
  tail: List('A)
  --------
  value!: List('A)
)

node append(
  target!: List('A),
  rest: List('A)
  --------
  result: List('A)
)

rule append(target!, rest, result) null(value!) {
  @connect(rest, result)
}

rule append(target!, rest, result) cons(head, tail, value!) {
  cons(head, append(tail, rest), result)
}

ListUtil.i

require "./Lazy.i" // Diamond imports don't work

// import { List, null, cons } from "./List.i"
// import { delOut, dupOut } from "./Generic.i"

node assertCons (
  listIn!: List('A),
  ------
  listOut: List('A),
  valOut: 'A
)

rule assertCons(listIn!, listOut, valOut) dupOut(a, b, value!) {
  let aL, bL, dO = dupOut()
  @connect(dO, listOut)
  let aV, bV, dO = dupOut()
  @connect(dO, valOut)
  assertCons(a, aL, aV)
  assertCons(b, bL, bV)
}

rule assertCons(listIn!, listOut, valOut) delOut(value!)  {
  @connect(delOut(), listOut)
  @connect(delOut(), valOut)
}

rule assertCons(listIn!, listOut, valOut) cons(val, list, value!)  {
  @connect(list, listOut)
  @connect(val, valOut)
}

node assertNull(
  value!: List('A)
  ------
)

rule assertNull(value!) null(value!) {
}

rule assertNull(value!) delOut(value!) {
}

rule assertNull(value!) dupOut(aO, bO, out!) {
  @connect(aO, assertNull())
  @connect(bO, assertNull())
}

Nat_bootstrap.i

require "RuleUtil.i" // Diamond imports don't work

// import { null, cons } from "./List.i"
// import { assertCons, assertNull } from "./ListUtil.i"
// import { Symbol, symbol_, symbol0, symbol1 } from "./Symbol.i"
// import { SymbolMap } from "./SymbolMap.i"
// import { connectionPair, connect } from "./Connection.i"
// import { Rule, rule, node } from "./Rule.i"
// import { insertRule } from "./RuleUtil.i"

function s_zero(): Symbol {
  return symbol_()
}
function s_add1(): Symbol {
  return symbol0(symbol_())
}
function s_add(): Symbol {
  return symbol1(symbol_())
}
function s_dup(): Symbol {
  return symbol0(symbol0(symbol_()))
}
function s_del(): Symbol {
  return symbol0(symbol1(symbol_()))
}
function s_mul(): Symbol {
  return symbol1(symbol0(symbol_()))
}

function Nat_i(rules: SymbolMap(SymbolMap(Rule))): SymbolMap(SymbolMap(Rule)) {
  let outs_, ruleAddZero, add, zero = rule()
  let outs = null()
  let add, addend = assertCons(add)
  let add, result = assertCons(add)
  assertNull(add)
  assertNull(zero)
  connect(addend, result)
  @connect(outs_, outs)
  let rules = insertRule(rules, s_add(), s_zero(), ruleAddZero)
  
  let outs_, ruleAddAdd1, add, add1 = rule()
  let outs = null()
  let add, addend = assertCons(add)
  let add, result = assertCons(add)
  assertNull(add)
  let add1, prev = assertCons(add1)
  assertNull(add1)
  let innerPos, innerNeg = connectionPair(null())
  let outs = cons(node(s_add(), prev, cons(addend, cons(innerNeg, null()))), outs)
  let outs = cons(node(s_add1(), result, cons(innerPos, null())), outs)
  @connect(outs_, outs)
  let rules = insertRule(rules, s_add(), s_add1(), ruleAddAdd1)
  
  let outs_, ruleDelZero, del, zero = rule()
  let outs = null()
  assertNull(del)
  assertNull(zero)
  @connect(outs_, outs)
  let rules = insertRule(rules, s_del(), s_zero(), ruleDelZero)
  
  let outs_, ruleDelAdd1, del, add1 = rule()
  let outs = null()
  assertNull(del)
  let add1, prev = assertCons(add1)
  assertNull(add1)
  let outs = cons(node(s_del(), prev, null()), outs)
  @connect(outs_, outs)
  let rules = insertRule(rules, s_del(), s_add1(), ruleDelAdd1)
  
  let outs_, ruleDupZero, dup, zero = rule()
  let outs = null()
  let dup, a = assertCons(dup)
  let dup, b = assertCons(dup)
  assertNull(dup)
  assertNull(zero)
  let outs = cons(node(s_zero(), a, null()), outs)
  let outs = cons(node(s_zero(), b, null()), outs)
  @connect(outs_, outs)
  let rules = insertRule(rules, s_dup(), s_zero(), ruleDupZero)
  
  let outs_, ruleDupAdd1, dup, add1 = rule()
  let outs = null()
  let dup, a = assertCons(dup)
  let dup, b = assertCons(dup)
  assertNull(dup)
  let add1, prev = assertCons(add1)
  assertNull(add1)
  let aPrev, aPrevNeg = connectionPair(null())
  let bPrev, bPrevNeg = connectionPair(null())
  let outs = cons(node(s_dup(), prev, cons(aPrevNeg, cons(bPrevNeg, null()))), outs)
  let outs = cons(node(s_add1(), a, cons(aPrev, null())), outs)
  let outs = cons(node(s_add1(), b, cons(bPrev, null())), outs)
  @connect(outs_, outs)
  let rules = insertRule(rules, s_dup(), s_add1(), ruleDupAdd1)
  
  let outs_, ruleMulZero, mul, zero = rule()
  let outs = null()
  let mul, mulend = assertCons(mul)
  let mul, result = assertCons(mul)
  assertNull(mul)
  assertNull(zero)
  let outs = cons(node(s_del(), mulend, null()), outs)
  let outs = cons(node(s_zero(), result, null()), outs)
  @connect(outs_, outs)
  let rules = insertRule(rules, s_mul(), s_zero(), ruleMulZero)
  
  let outs_, ruleMulAdd1, mul, add1 = rule()
  let outs = null()
  let mul, mulend = assertCons(mul)
  let mul, result = assertCons(mul)
  assertNull(mul)
  let add1, prev = assertCons(add1)
  assertNull(add1)
  let aMulend, aMulendNeg = connectionPair(null())
  let bMulend, bMulendNeg = connectionPair(null())
  let outs = cons(node(s_dup(), mulend, cons(aMulendNeg, cons(bMulendNeg, null()))), outs)
  let mulOut, mulOutNeg = connectionPair(null())
  let outs = cons(node(s_mul(), prev, cons(aMulend, cons(mulOutNeg, null()))), outs)
  let outs = cons(node(s_add(), bMulend, cons(mulOut, cons(result, null()))), outs)
  @connect(outs_, outs)
  let rules = insertRule(rules, s_mul(), s_add1(), ruleMulAdd1)
  
  return rules
}

Nat_bootstrap.test.i

require "./Nat_bootstrap.i" // Diamond imports don't work

// import { null, cons } from "./List.i"
// import { emptySymbolMap } from "./SymbolMap.i"
// import { Connection, invalidConnection, connectionPair } from "./Connection.i"
// import { node } from "./Rule.i"
// import { inflateNodes } from "./Inflate.i"
// import { s_zero, s_add1, s_add, s_mul, Nat_i } from "./Nat_bootstrap.i"

function world(): Connection {
  let rules = Nat_i(emptySymbolMap())
  let outs = null()
  
  // 3 + 4 * 2 = ???
  
  // 4:
  
  let zeroOut, zeroOutNeg = connectionPair(null())
  let outs = cons(node(s_zero(), zeroOutNeg, null()), outs)
  let oneOut, oneOutNeg = connectionPair(null())
  let outs = cons(node(s_add1(), oneOutNeg, cons(zeroOut, null())), outs)
  let twoOut, twoOutNeg = connectionPair(null())
  let outs = cons(node(s_add1(), twoOutNeg, cons(oneOut, null())), outs)
  let threeOut, threeOutNeg = connectionPair(null())
  let outs = cons(node(s_add1(), threeOutNeg, cons(twoOut, null())), outs)
  let fourOut, fourOutNeg = connectionPair(null())
  let outs = cons(node(s_add1(), fourOutNeg, cons(threeOut, null())), outs)
  
  // 3:
  
  let zeroOut, zeroOutNeg = connectionPair(null())
  let outs = cons(node(s_zero(), zeroOutNeg, null()), outs)
  let oneOut, oneOutNeg = connectionPair(null())
  let outs = cons(node(s_add1(), oneOutNeg, cons(zeroOut, null())), outs)
  let twoOut, twoOutNeg = connectionPair(null())
  let outs = cons(node(s_add1(), twoOutNeg, cons(oneOut, null())), outs)
  let threeOut, threeOutNeg = connectionPair(null())
  let outs = cons(node(s_add1(), threeOutNeg, cons(twoOut, null())), outs)
  
  // 2:
  
  let zeroOut, zeroOutNeg = connectionPair(null())
  let outs = cons(node(s_zero(), zeroOutNeg, null()), outs)
  let oneOut, oneOutNeg = connectionPair(null())
  let outs = cons(node(s_add1(), oneOutNeg, cons(zeroOut, null())), outs)
  let twoOut, twoOutNeg = connectionPair(null())
  let outs = cons(node(s_add1(), twoOutNeg, cons(oneOut, null())), outs)
  
  // 3 * 2:
  
  let mulOut, mulOutNeg = connectionPair(null())
  let outs = cons(node(s_mul(), twoOut, cons(threeOut, cons(mulOutNeg, null()))), outs)
  
  // 4 + (3 * 2):
  
  let addOut, addOutNeg = connectionPair(null())
  let outs = cons(node(s_add(), fourOut, cons(mulOut, cons(addOutNeg, null()))), outs)
  
  let result = addOut
  
  // // Just for fun: square the result
  // let aOut, aOutNeg = connectionPair(null())
  // let bOut, bOutNeg = connectionPair(null())
  // let outs = cons(node(s_dup(), result, cons(aOutNeg, cons(bOutNeg, null()))), outs)
  // 
  // let mulOut, mulOutNeg = connectionPair(null())
  // let outs = cons(node(s_mul(), aOut, cons(bOut, cons(mulOutNeg, null()))), outs)
  // 
  // let result = mulOut
  
  inflateNodes(outs, rules)
  
  return result
}

// eval @inspect(world()) // Kills browser performance; graph's suuper large
eval @inspect(@run(world())) // (oh, and it takes around.. 4k steps to reduce to a representation of 10)

Option.i

require "./ListUtil.i" // Diamond imports don't work
// import { del, delOut, dup, dupOut } from "./Generic.i"

type Option(Element: @Type)

node some(
  value: 'A
  ------
  opiton!: Option('A)
)
node none(
  ------
  opiton!: Option('A)
)

rule del(va!) some(value, option!) {
  del(value)
}
rule del(val!) none(option!) {
}
rule dup(va!, a, b) some(value, option!) {
  let va, vb = dup(value)
  some(va, a)
  some(vb, b)
}
rule dup(va!, a, b) none(option!) {
  none(a)
  none(b)
}

node assertSome(
  value!: Option('A)
  ------
  result: 'A
)

rule assertSome(value!, result) some(value, option!) {
  @connect(value, result)
}

rule assertSome(value!, result) delOut(value!) {
  delOut(result)
}

rule assertSome(value!, result) dupOut(aO, bO, out!) {
  let aR, bR, dO = dupOut()
  @connect(dO, result)
  assertSome(aO, aR)
  assertSome(bO, bR)
}

Rule.i

require "./Connection.i" // Diamond imports don't work
// import { List, null, cons } from "./List.i"
// import { del, delOut, dup, dupOut } from "./Generic.i"
// import { Symbol } from "./Symbol.i"
// import { Connection } from "./Connection.i"

type Rule
type Output

node rule(
  outputs: List(Output)
  ------
  trigger!: Rule,
  connectionsA: List(Connection),
  connectionsB: List(Connection),
)

rule dup(value!, a, b) rule(outputs, trigger!, connectionsA, connectionsB) {
  let aO, bO = dup(outputs)
  let aA, bA, dO = dupOut()
  @connect(dO, connectionsA)
  let aB, bB, dO = dupOut()
  @connect(dO, connectionsB)
  rule(aO, a, aA, aB)
  rule(bO, b, bA, bB)
}

rule del(value!) rule(outputs, trigger!, connectionsA, connectionsB) {
  del(outputs)
  @connect(delOut(), connectionsA)
  @connect(delOut(), connectionsB)
}


node exec(
  connectionsA: List(Connection),
  connectionsB: List(Connection),
  trigger!: Rule,
  ------
  outputs: List(Output)
)

rule exec(connectionsA, connectionsB, trigger!, outputs) rule(outputsRule, trigger!, connectionsARule, connectionsBRule) {
  @connect(connectionsA, connectionsARule)
  @connect(connectionsB, connectionsBRule)
  @connect(outputs, outputsRule)
}


node node(
  symbol: Symbol,
  activeConnection: Connection,
  connections: List(Connection)
  ------
  result!: Output,
)

rule dup(value!, a, b) node(symbol, activeConnection, connections, result!) {
  let aS, bS = dup(symbol)
  let aA, bA = dup(activeConnection)
  let aC, bC = dup(connections)
  node(aS, aA, aC, a)
  node(bS, bA, bC, b)
}

rule del(value!) node(symbol, activeConnection, connections, result!) {
  del(symbol)
  del(activeConnection)
  del(connections)
}

RuleUtil.i

require "./Inflate.i" // Diamond imports don't work

// import { del } from "./Generic.i"
// import { some } from "./Option.i"
// import { Symbol } from "./Symbol.i"
// import { SymbolMap, symbolMapReplace, orEmptyMap } from "./SymbolMap.i"
// import { Rule, rule } from "./Rule.i"

// // Writing this as a function fails typecheck :(
// function insertRule(rules: SymbolMap(SymbolMap(Rule)), symbolA: Symbol, symbolB: Symbol, rule: Rule): SymbolMap(SymbolMap(Rule)) {
//   let rulesABack, rules, rulesA = symbolMapReplace(rules, symbolA)
//   let rulesA, o = symbolMapReplace(orEmptyMap(rulesA), symbolB, some(rule))
//   del(o)
//   @connect(rulesABack, some(rulesA))
// }

node insertRule(
  rules: SymbolMap(SymbolMap(Rule)),
  symbolA: Symbol,
  symbolB: Symbol,
  rule!: Rule
  ------
  rulesOut: SymbolMap(SymbolMap(Rule)),
)

rule insertRule(rules, symbolA, symbolB, rule!, rulesOut) rule(outputs, trigger!, connectionsA, connectionsB) {
  let rule, connectionsA_, connectionsB_ = rule(outputs)
  @connect(connectionsA_, connectionsA)
  @connect(connectionsB_, connectionsB)
  let rulesABack, rules, rulesA = symbolMapReplace(rules, symbolA)
  let rulesA, o = symbolMapReplace(orEmptyMap(rulesA), symbolB, some(rule))
  del(o)
  @connect(rulesABack, some(rulesA))
  @connect(rules, rulesOut)
}

Symbol.i

require "./Option.i" // Diamond imports don't work

// import { del, dup } from "./Generic.i"

type Symbol

node symbol_(
  ------
  value!: Symbol
)
node symbol0(
  next: Symbol
  ------
  value!: Symbol
)
node symbol1(
  next: Symbol
  ------
  value!: Symbol
)

rule del(value!)
  symbol_(value!) {
}
rule del(value!)
  symbol0(next, value!) {
  del(next)
}
rule del(value!)
  symbol1(next, value!) {
  del(next)
}

rule dup(value!, outA, outB) symbol_(value!) {
  @connect(outA, symbol_())
  @connect(outB, symbol_())
}
rule dup(value!, outA, outB) symbol0(next, value!) {
  let nextA, nextB = dup(next)
  @connect(outA, symbol0(nextA))
  @connect(outB, symbol0(nextB))
}
rule dup(value!, outA, outB) symbol1(next, value!) {
  let nextA, nextB = dup(next)
  @connect(outA, symbol1(nextA))
  @connect(outB, symbol1(nextB))
}

SymbolMap.i

require "./Symbol.i" // Diamond imports don't work

// import { del, dup } from "./Generic.i"
// import { Option, some, none } from "./Option.i"
// import { Symbol, symbol_, symbol0, symbol1 } from "./Symbol.i"

type SymbolMap(Element: @Type)

node symbolMapLeaf(
  value: Option('A),
  ------
  map!: SymbolMap('A)
)
node symbolMapNode(
  s0: SymbolMap('A),
  s1: SymbolMap('A),
  value: Option('A),
  ------
  map!: SymbolMap('A)
)

rule del(value!) symbolMapNode(s0, s1, value, map!) {
  del(s0)
  del(s1)
  del(value)
}
rule del(value!) symbolMapLeaf(value, map!) {
  del(value)
}

rule dup(v!, a, b) symbolMapNode(s0, s1, value, map!) {
  let a0, b0 = dup(s0)
  let a1, b1 = dup(s1)
  let aV, bV = dup(value)
  symbolMapNode(a0, a1, aV, a)
  symbolMapNode(b0, b1, bV, b)
}
rule dup(v!, a, b) symbolMapLeaf(value, map!) {
  let aV, bV = dup(value)
  symbolMapLeaf(aV, a)
  symbolMapLeaf(bV, b)
}

node symbolMapReplace(
  mapIn: SymbolMap('A),
  key!: Symbol,
  newVal: Option('A)
  ------
  mapOut: SymbolMap('A),
  oldVal: Option('A)
)
node symbolMapReplace0(
  mapIn!: SymbolMap('A),
  key: Symbol,
  newVal: Option('A)
  ------
  mapOut: SymbolMap('A),
  oldVal: Option('A)
)
node symbolMapReplace1(
  mapIn!: SymbolMap('A),
  key: Symbol,
  newVal: Option('A)
  ------
  mapOut: SymbolMap('A),
  oldVal: Option('A)
)
node symbolMapReplace_(
  mapIn!: SymbolMap('A),
  newVal: Option('A)
  ------
  mapOut: SymbolMap('A),
  oldVal: Option('A)
)

rule symbolMapReplace(mapIn, key!, newVal, mapOut, oldVal) symbol0(keynext, value!) {
  symbolMapReplace0(mapIn, keynext, newVal, mapOut, oldVal)
}
rule symbolMapReplace(mapIn, key!, newVal, mapOut, oldVal) symbol1(keynext, value!) {
  symbolMapReplace1(mapIn, keynext, newVal, mapOut, oldVal)
}
rule symbolMapReplace(mapIn, key!, newVal, mapOut, oldVal) symbol_(value!) {
  symbolMapReplace_(mapIn, newVal, mapOut, oldVal)
}

rule symbolMapReplace0(mapIn!, key, newVal, mapOut, oldVal) symbolMapNode(s0, s1, value, map!) {
  let m0, r = symbolMapReplace(s0, key, newVal)
  @connect(r, oldVal)
  symbolMapNode(m0, s1, value, mapOut)
}
rule symbolMapReplace0(mapIn!, key, newVal, mapOut, oldVal) symbolMapLeaf(value, map!) {
  let m0, r = symbolMapReplace(symbolMapLeaf(none()), key, newVal)
  @connect(r, oldVal)
  symbolMapNode(m0, symbolMapLeaf(none()), value, mapOut)
}

rule symbolMapReplace1(mapIn!, key, newVal, mapOut, oldVal) symbolMapNode(s0, s1, value, map!) {
  let m1, r = symbolMapReplace(s1, key, newVal)
  @connect(r, oldVal)
  symbolMapNode(s0, m1, value, mapOut)
}
rule symbolMapReplace1(mapIn!, key, newVal, mapOut, oldVal) symbolMapLeaf(value, map!) {
  let m1, r = symbolMapReplace(symbolMapLeaf(none()), key, newVal)
  @connect(r, oldVal)
  symbolMapNode(symbolMapLeaf(none()), m1, value, mapOut)
}

rule symbolMapReplace_(mapIn!, newVal, mapOut, oldVal) symbolMapNode(s0, s1, value, map!) {
  symbolMapNode(s0, s1, newVal, mapOut)
  @connect(value, oldVal)
}
rule symbolMapReplace_(mapIn!, newVal, mapOut, oldVal) symbolMapLeaf(value, map!) {
  symbolMapLeaf(newVal, mapOut)
  @connect(value, oldVal)
}

// // Wouldn't it be wonderful if functions could also return multiple values? (:
// function symbolMapLookup(mapIn: SymbolMap('A), key: Symbol): SymbolMap('A), Option('A) {
//   let newVal, mapOut, oldVal = symbolMapReplace(mapIn, key)
//   dup(oldVal, newVal, val)
//   return mapOut, val
// }

function emptySymbolMap(): SymbolMap('A) {
  return symbolMapLeaf(none())
}

node orEmptyMap(
  option!: Option(SymbolMap('A))
  ------
  result: SymbolMap('A)
)
  
rule orEmptyMap(option!, result) some(map, option!) {
  @connect(result, map)
}
rule orEmptyMap(option!, result) none(option!) {
  @connect(result, emptySymbolMap())
}

@xieyuheng Enjoy? 😊

Amazing!