Wow - the docs are a really nice intro to interaction nets. I've been wanting to dig into them ever since stumbling upon kind / HVM but hadn't worked up the courage, but having something to click on and play around with along with a simple guide is great. Also really dig how the code example text splits responsively. This is super cool! Took me a minute to realize clicking on the red edges was application of rules.
It is true that I am not clear about
how should I put this idea to practical usage.
And I was also deeply puzzled
when I first read Lafont's paper "Interaction Nets"
(a paper publish at 1990!)
> What unique about this computation model?
Every computations in interaction nets can be easily done in parallel.
Some algorithm that make heavy use of graph
might be easier to express in interaction nets,
the main example is Lamping's paper
called "An algorithm for optimal lambda calculus reduction".
> What unique about this language?
My humble contribution to interaction nets
is to use a stack-based lower layer language to build graph,
maybe this idea can be applied to other places,
and maybe this idea can provide us an opportunity
to make the whole language practical.
> How to be practical and useful?
Currently the language only has a pure core,
just like pure Haskell without any IO,
I planed to implement inet again
in a system programming language
(maybe C, C++, Rust, Zig).
And add built-in functions about IO to it,
we can do this in a way that
will not hurt the purity of the core,
by only extending the lower layer stack-based language.
I like the minimalist design. You might want to more clearly make a visual distinction between buttons and headings in the app, now it's somewhat confusing to know where to click.
If I tell you the process of designing it, you may laugh at me.
The situation is when I am not sure about how to design some graphic,
I just put a square button at some corner to bear the functionality :p
I think I am just start learning about graphic design,
I am reading a book called "Graphic Design Manual: Principles and Practice" by Armin Hofmann
(a book first published at 1965!)
I think you are right about the rules, just expressing them in a different way,
not by local interaction between neighboring nodes,
but by first-order logic!
Was really fun to play with; made a quick implementation of a Bin(ary) type supporting log-time addition as opposed to the linear-time addition of the Nat type (and log-squared-time multiplication as opposed to the squared-time multiplication of Nat-s).
I think I have just caught the first user of this little language :)
It is amazing that you can understand the language simply by my minimal amount of docs,
and write this non-trivial example.
I will study your example and add it to the repository.
Your implementation of `Bin` reminds me of
the implementation of binary number
in minikanren ( http://minikanren.org ),
in a book called "The Reasoned Schemer".
Self-hoist will be a very very interesting challenge!
(1) Maybe we can do it by firstly implement a low level graph processing VM,
and compile it to the byte-code of the VM.
(2) How about self-interpreting? like lisp's meta-circular evaluator.
Maybe this is even more challenging then compiling.
Either way, We will need some built-in primitive functions about IO,
and also some primitive functions about string processing (to parse the syntax).
Maybe we can keep the core pure, and extend the lower layer stack-based language.
Should we do this in this JavaScript/TypeScript implementation?
or to do this in a C/C++/Rust/Zig implementation?
(the later seems have more potential to be practical)
I think it should be quite nice to write an interpreter in Haskell (and then introduce meta-circular to it?)
e.g. we can have Graph be a monad made up of `Node[]` with `runGraph` defined by somehow composing Rules
```
data PortType = ... deriving (Show, Read)
data Port = Port { portType :: PortType, portName :: String } deriving (Show, Read)
data Node = Node { inputPorts :: [Port], outputPorts :: [Port], principal :: Port } deriving (Show, Read)
```
Will need some creativity for the Rules to be defined more naturally, or it would end up just a function:
```
zeroAddRule :: Port -> [Port] -> Maybe [Port]
zeroAddRule target [addend]
| target == outputPorts zero !! 0 = Just [addend]
| otherwise = Nothing
```
[edited for elaboration]: I'm actually working on a LLM prompt-orchestration and fine-tuning/testing framework in Haskell (and will be open-source soon https://github.com/0a-io/ArchGPT ). The more I learn about iNet now the more I think I will try to write an implementation of it in Haskell and see how well it can fit into the hypergraph architecture I’m designing for building automated-software-development pipelines :)
I think what's so cool about the interaction-nets model of computation is that it makes tracing and stepping much more like first-class citizens, as well as a kind of intuitiveness for anything combinatorial
Well, to be fair, making binary multiplication took more attempts that I would rather admit; I'm a programmer, not a mathematician XD
I also tried to make a game of life implementation, making use of the graph as a two-dimensional grid; however, it was too much for a single idle afternoon -- might have to retry that later. Main issue was trying to work around the stack-based part of the language (and I guess around port signed-ness); I can envision roughly what I want to get on the screen, but writing it out as stack manipulations, when there are so many cyclical references (ideally, I want every cell to be connected to up to 8 neighboring cells), is nontrivial -- especially when it comes to node rearranges, which, frankly, I didn't quite get. (:'
For self-hoisting, I would imagine the challenge would be around storing the rules and expressing the different node types. Tho - come to think of it, there are indeed two ways to implement it; one would be by defining a data structure to hold the graph and having an "interpreter" walk around the graph updating places where the rules match, and the other would be to define a sort-of composite "agent" which is able to correctly orient its primary port and interact with other composite agents around it, following the production rules it carries around. I guess that is pretty much what you are saying.. I'd say the latter/self-interpreting version is the more advanced one and would better benefit from improvements in the runtime, but the former should indeed be much simpler to write out.
For IO... I was thinking I'd rather have it at the graph layer, but now that you mention it, being able to customize it at the lower layer language would actually be quite neat.
And finally for implementation; the current JS/TS implementation is quiiite slow; it takes multiple seconds to crunch through a few thousand steps. Chrome profiler suggests the closeAllFreePorts function is the culprit; but I can't tell if that's an issue of the language or the implementation. Still, it might be worth keeping the JS/TS version for prototyping things out, then moving to another language only once things are more or less stable?
I have some concerns about it when deciding to use it, because it is so different from common programming languages.
I am comfortable with postfix notation, because I am familiar with the Forth language ( https://en.wikipedia.org/wiki/Forth_(programming_language) ).
> About Rearrange.
I will improve the docs about it.
> About `closeAllFreePorts`
If `closeAllFreePorts` is the culprit, maybe it is because of my wrong implementation of the web frontend (not the language).
Would you mind elaborating on your idea of the composite "agent"? I don't quite understand it, and it does not sound like what I think OP's metacircular evaluator is referring to.
Well.. hm. Basically, in a "normal", non-self-hoisted interaction net you have agents that have principal ports and interact with each other -- in iNet, those are called nodes. So, I'm thinking it might be possible to make a self-hoisted interaction net by replacing each custom node/agent in the original "normal" net with a subgraph which is composed entirely of reusable nodes that implement the self-hoisting. And, I'd imagine that such a subgraph would have a single principal port pointing in the same direction as the "normal" agent's principal port did, plus an internal set of nodes which encode the rules. Hence, each "normal agent" is turned into a "composite agent" -- if that makes sense.
I have been working on LLM agent systems, and have come across a few different syntaxes for expressing multi-agent problem-solving in a structured way, such as SCXML. I will definitely have to do a deeper dive on this.
My system currently implements a custom framework which generates and uses a directed acyclic graph which can express tasks as nodes, and relationships between tasks as edges.
To my naive mind, this model seems strongly aligned to how Quantum computers work. A QC can simultaneously perform operations on all possible states, which makes them exponentially faster. But working with them might as well be like working with alien tech. Weird sounding gates, superposition of states, it’s all hard to wrap one’s head around. Counter intuitive to everything we know in the macro world.
This model feels a lot less alien and could provide a much better starting point for programming on them. I can envision a compiler that will take an interaction net as input and spit out a quantum circuit.
I think of classical computers operating on yes and no, and quantum computers operating on direction and magnitude. Things like Q# make it a lot more approachable, but I'm also very much a naive mind. That said, I'm not seeing the overlap between quantum computing and interaction nets. I'd think parallel-focused hardware like GPU's and eventually optical would be more natural hardware targets.
It makes me want to learn more about quantum computing.
The foundational paper about interaction nets is published in 1990.
(https://github.com/cicada-lang/inet/blob/master/docs/referen...)
There must be some interesting developments during these 30 more years,
maybe some of the developments are related to quantum computing ~
I am also somewhat naive minded,
although I implemented this language,
I actually only read the first 1990 paper about interaction nets,
there are many follow up papers by the original author Lafont,
some papers are about combinators, some papers are about linear logic and proof theory background of inet.
to have a model for quantum computing you will need to be able to define individual Qunatum Gates operating on qubit (like Hadamard gate https://cs.stackexchange.com/questions/37080/trying-to-under... ) in order to implement algo like Shor's algorithm for (quantum-sped-up) prime-factoring in polylogarithmic time.
i.e. the quantum "simultaneity" only works via doing linear transformation across the probability amplitudes.
Will be interesting to see how interaction net can be extended (if possible at all?) to fit into the linear algebra of QM
I'm another fellow admirer of Interaction nets. I'd like to inquire on the positioning of iNet, whether you intend for it to be a performant/beta-optimal runtime like HVM, or if you're interested in other theoretical developments?
In case you wanted to steer it in the direction of a beta-optimal runtime like HVM, do note the pathological cases (e.g. the last page of https://sci-hub.hkvisa.net/10.1006/inco.1997.2643) and the other pitfalls which HVM suffers from (; of a fundamental nature of the framework of Interaction nets, I'm afraid, demanding breakthroughs in theory to be overcome https://news.ycombinator.com/item?id=35336113#35340714).
Despite these issues, I am quite strongly convinced that Girard's framework of Geometry of Interaction is the best way forward towards a computational model with local and denotational properties for large scale software.
My current plan is to programming with interaction nets directly,
and to view Lamping's "optimal lambda calculus reduction" as an example.
I have not read Lamping's paper yet.
But if it uses "Interaction Combinators",
maybe I can not even do it in my implementation.
Because there are two version of inet:
(1) Lafont's 1990 paper "Interaction Nets"
(2) Lafont's 1997 paper "Interaction Combinators"
I implemented (1) where a port has a sign (input port v.s. output port).
Given two ports, I can only connect them when they have opposite signs.
In (2) there is no input port v.s. output port,
ports are not signed (Lafont called the signed version "directed" in (2)).
"Interaction Combinators" uses self interaction
(rule about a node interacting with itself),
it is not possible in signed version of inet.
Because one node only has one principle port,
thus can not connect to it's own principle port,
because the same principle port has the same sign,
not opposite signs.
------
I said "programming with interaction nets directly",
because it seems already a more practical language than lambda calculus,
for we do not need lambda encoding to express datatype and pattern matching,
we can define rules case by case directly.
Ahh that is certainly a very interesting idea to explore! Indeed, programming on the nets directly would not need messing with the fairly complex details of beta-optimality, leaving it as something to be dealt with, if required, by the programmer directly. As a language in its own right rather than as a computational device, interaction nets becomes a kind of Prolog-like language, where one similarly directly defines atoms and uses them as if they were data types.
By the way, I'm fairly certain that the Interaction Nets is the more general term, encompassing Interaction Combinators as merely some set of nets that happens to be a universal model of computation. They definitely both share the distinctions of principal ports v.s. auxiliary ports.
Indeed, I see that Lafont's 1990 paper introduces 'input' and 'output' denominations under Section 2 "Type Discipline".
> The choice of an input/output denomination is purely conventional: it does not matter if you call input what I call output, and conversely, but we must agree on matching. [...] typing ensures local correctness of computations
It seems to me that the input/output convention is really just one particular type system, orthogonal to the essential idea of Interaction nets or Interaction combinators. Indeed if iNet requires such a typing discipline, then nets like Interaction combinators cannot be implemented.
39 comments
[ 2.9 ms ] story [ 81.8 ms ] threadThe site feels more like an intelligence test or a riddle. “Here are N possible statements and M possible words, figure it out if you can.”
I suppose the background learning required starts here
https://en.wikipedia.org/wiki/Interaction_nets
[1] https://github.com/HigherOrderCO/HVM
And I was also deeply puzzled when I first read Lafont's paper "Interaction Nets" (a paper publish at 1990!)
> What unique about this computation model?
Every computations in interaction nets can be easily done in parallel.
Some algorithm that make heavy use of graph might be easier to express in interaction nets, the main example is Lamping's paper called "An algorithm for optimal lambda calculus reduction".
> What unique about this language?
My humble contribution to interaction nets is to use a stack-based lower layer language to build graph, maybe this idea can be applied to other places, and maybe this idea can provide us an opportunity to make the whole language practical.
> How to be practical and useful?
Currently the language only has a pure core, just like pure Haskell without any IO,
I planed to implement inet again in a system programming language (maybe C, C++, Rust, Zig).
And add built-in functions about IO to it, we can do this in a way that will not hurt the purity of the core, by only extending the lower layer stack-based language.
I should improve the graphic design.
If I tell you the process of designing it, you may laugh at me.
The situation is when I am not sure about how to design some graphic, I just put a square button at some corner to bear the functionality :p
I think I am just start learning about graphic design, I am reading a book called "Graphic Design Manual: Principles and Practice" by Armin Hofmann (a book first published at 1965!)
```
S = ∀z r.result[res=adder(z,r)]
adder = ∀n m.result[case(m,n,result) = plus]
plus = ∀n m. if(m=0) then result[n] else result[s=plus(n, pred(m)), res=S(s)]
```
And so when we add 2 (S(S(0))) and 3 (S(S(S(0)))), we start with:
```
Z
|
S -> S -> S -> Z
|
S -> S -> Z
```
and then we would reduce it to:
```
Z
|
S -> S -> S -> S -> S -> Z
```
or am I missing something?
I think you are right about the rules, just expressing them in a different way, not by local interaction between neighboring nodes, but by first-order logic!
When we add 2 (S(S(0))) and 3 (S(S(S(0)))).
I think we start with:
```
Add
| -- S -- S -- Z
| -- S -- S -- S -- Z
```
and then we would reduce it to:
```
S -- S -- S -- S -- S -- Z
```
At the top right corner of the homepage, there is a link to "Docs" -- https://readonly.link/articles/https://cdn.inet.cic.run/docs...
Maybe this article can help.
https://gist.github.com/bojidar-bg/85026fa70e6ba7b1862bf8226...
Would be really cool if we had more input/output options; also, I'm curious if it might be possible to self-hoist the language somehow.
I think I have just caught the first user of this little language :)
It is amazing that you can understand the language simply by my minimal amount of docs, and write this non-trivial example.
I will study your example and add it to the repository.
Your implementation of `Bin` reminds me of the implementation of binary number in minikanren ( http://minikanren.org ), in a book called "The Reasoned Schemer".
Self-hoist will be a very very interesting challenge!
(1) Maybe we can do it by firstly implement a low level graph processing VM, and compile it to the byte-code of the VM.
(2) How about self-interpreting? like lisp's meta-circular evaluator. Maybe this is even more challenging then compiling.
Either way, We will need some built-in primitive functions about IO, and also some primitive functions about string processing (to parse the syntax).
Maybe we can keep the core pure, and extend the lower layer stack-based language.
Should we do this in this JavaScript/TypeScript implementation? or to do this in a C/C++/Rust/Zig implementation? (the later seems have more potential to be practical)
e.g. we can have Graph be a monad made up of `Node[]` with `runGraph` defined by somehow composing Rules
```
data PortType = ... deriving (Show, Read)
data Port = Port { portType :: PortType, portName :: String } deriving (Show, Read)
data Node = Node { inputPorts :: [Port], outputPorts :: [Port], principal :: Port } deriving (Show, Read)
```
Will need some creativity for the Rules to be defined more naturally, or it would end up just a function:
```
zeroAddRule :: Port -> [Port] -> Maybe [Port]
zeroAddRule target [addend]
```[edited for elaboration]: I'm actually working on a LLM prompt-orchestration and fine-tuning/testing framework in Haskell (and will be open-source soon https://github.com/0a-io/ArchGPT ). The more I learn about iNet now the more I think I will try to write an implementation of it in Haskell and see how well it can fit into the hypergraph architecture I’m designing for building automated-software-development pipelines :)
I think what's so cool about the interaction-nets model of computation is that it makes tracing and stepping much more like first-class citizens, as well as a kind of intuitiveness for anything combinatorial
If you made an implementation, I will make a list of implementations in the homepage ( https://inet.run ), and add your implementation to the list :)
------
I do not know much about LLM yet, but I like hypergraphs too :)
(I learned about it from Wolfram Physics's docs.)
I will not miss an issue there :)
Well, to be fair, making binary multiplication took more attempts that I would rather admit; I'm a programmer, not a mathematician XD
I also tried to make a game of life implementation, making use of the graph as a two-dimensional grid; however, it was too much for a single idle afternoon -- might have to retry that later. Main issue was trying to work around the stack-based part of the language (and I guess around port signed-ness); I can envision roughly what I want to get on the screen, but writing it out as stack manipulations, when there are so many cyclical references (ideally, I want every cell to be connected to up to 8 neighboring cells), is nontrivial -- especially when it comes to node rearranges, which, frankly, I didn't quite get. (:'
For self-hoisting, I would imagine the challenge would be around storing the rules and expressing the different node types. Tho - come to think of it, there are indeed two ways to implement it; one would be by defining a data structure to hold the graph and having an "interpreter" walk around the graph updating places where the rules match, and the other would be to define a sort-of composite "agent" which is able to correctly orient its primary port and interact with other composite agents around it, following the production rules it carries around. I guess that is pretty much what you are saying.. I'd say the latter/self-interpreting version is the more advanced one and would better benefit from improvements in the runtime, but the former should indeed be much simpler to write out.
For IO... I was thinking I'd rather have it at the graph layer, but now that you mention it, being able to customize it at the lower layer language would actually be quite neat.
And finally for implementation; the current JS/TS implementation is quiiite slow; it takes multiple seconds to crunch through a few thousand steps. Chrome profiler suggests the closeAllFreePorts function is the culprit; but I can't tell if that's an issue of the language or the implementation. Still, it might be worth keeping the JS/TS version for prototyping things out, then moving to another language only once things are more or less stable?
In the paper "Interaction Nets" ( https://github.com/cicada-lang/inet/blob/master/docs/referen... ), there is an example of 1-dimensional Cellular Automata. (Section 1.4. Example: Cellular Automata).
> About the stack-based layer of the language.
I have some concerns about it when deciding to use it, because it is so different from common programming languages. I am comfortable with postfix notation, because I am familiar with the Forth language ( https://en.wikipedia.org/wiki/Forth_(programming_language) ).
> About Rearrange.
I will improve the docs about it.
> About `closeAllFreePorts`
If `closeAllFreePorts` is the culprit, maybe it is because of my wrong implementation of the web frontend (not the language).
I should not call `closeAllFreePorts` in a loop.
see: https://github.com/cicada-lang/inet-website/blob/master/src/...
and: https://github.com/cicada-lang/inet-website/blob/master/src/...
It is a bug that I should fix.
I also implemented a command line program and a REPL: https://github.com/cicada-lang/inet#command-line-tool
Maybe a few thousand steps will not be slow there.
we will probably need some graph-theoretical way of defining the env for it to be able to spring up a towel of meta-circular interpreters
I removed the syntax of rearrange, and added a new builtin `@spread`, I hope it is less confusing now :)
My system currently implements a custom framework which generates and uses a directed acyclic graph which can express tasks as nodes, and relationships between tasks as edges.
I get excited whenever I see "State" and "Notation" in one sentence.
I learn about state-based language from the language Forth: https://www.forth.com/starting-forth
and the language Joy: https://hypercubed.github.io/joy/joy.html
Maybe you will find them inspiring too.
The use case of your system seems interesting too, if your project is open source, feel free to share it here :)
This model feels a lot less alien and could provide a much better starting point for programming on them. I can envision a compiler that will take an interaction net as input and spit out a quantum circuit.
It makes me want to learn more about quantum computing.
The foundational paper about interaction nets is published in 1990. (https://github.com/cicada-lang/inet/blob/master/docs/referen...) There must be some interesting developments during these 30 more years, maybe some of the developments are related to quantum computing ~
I am also somewhat naive minded, although I implemented this language, I actually only read the first 1990 paper about interaction nets, there are many follow up papers by the original author Lafont, some papers are about combinators, some papers are about linear logic and proof theory background of inet.
I will keep learning.
i.e. the quantum "simultaneity" only works via doing linear transformation across the probability amplitudes.
Will be interesting to see how interaction net can be extended (if possible at all?) to fit into the linear algebra of QM
In case you wanted to steer it in the direction of a beta-optimal runtime like HVM, do note the pathological cases (e.g. the last page of https://sci-hub.hkvisa.net/10.1006/inco.1997.2643) and the other pitfalls which HVM suffers from (; of a fundamental nature of the framework of Interaction nets, I'm afraid, demanding breakthroughs in theory to be overcome https://news.ycombinator.com/item?id=35336113#35340714).
Despite these issues, I am quite strongly convinced that Girard's framework of Geometry of Interaction is the best way forward towards a computational model with local and denotational properties for large scale software.
My current plan is to programming with interaction nets directly, and to view Lamping's "optimal lambda calculus reduction" as an example.
I have not read Lamping's paper yet. But if it uses "Interaction Combinators", maybe I can not even do it in my implementation.
Because there are two version of inet:
(1) Lafont's 1990 paper "Interaction Nets"
(2) Lafont's 1997 paper "Interaction Combinators"
I implemented (1) where a port has a sign (input port v.s. output port). Given two ports, I can only connect them when they have opposite signs.
In (2) there is no input port v.s. output port, ports are not signed (Lafont called the signed version "directed" in (2)).
"Interaction Combinators" uses self interaction (rule about a node interacting with itself), it is not possible in signed version of inet.
Because one node only has one principle port, thus can not connect to it's own principle port, because the same principle port has the same sign, not opposite signs.
------
I said "programming with interaction nets directly", because it seems already a more practical language than lambda calculus, for we do not need lambda encoding to express datatype and pattern matching, we can define rules case by case directly.
By the way, I'm fairly certain that the Interaction Nets is the more general term, encompassing Interaction Combinators as merely some set of nets that happens to be a universal model of computation. They definitely both share the distinctions of principal ports v.s. auxiliary ports.
------
> They definitely both share the distinctions of principal ports v.s. auxiliary ports.
Version (1) and (2) both have principal ports v.s. auxiliary ports.
But only (1) has input ports v.s. output ports.
(I was actually quite shocked by this, when I read the 1997 paper.)
> The choice of an input/output denomination is purely conventional: it does not matter if you call input what I call output, and conversely, but we must agree on matching. [...] typing ensures local correctness of computations
It seems to me that the input/output convention is really just one particular type system, orthogonal to the essential idea of Interaction nets or Interaction combinators. Indeed if iNet requires such a typing discipline, then nets like Interaction combinators cannot be implemented.