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?
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.
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.
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 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.
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
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 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.
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?
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.
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).
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.
Thanks for your example!
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]
```
[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
5 replies →
(X
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?
6 replies →
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.
happy to see you like it :)
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.
Thanks for your reply :)
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 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.
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
It looks very cool, but what is it for? What can you do with this language that’s unique or useful?
The 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.”
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.
A more developed example is HVM[1] which is also built on interaction nets - this computation model enables for-free parallelization
[1] https://github.com/HigherOrderCO/HVM
Hi pavlov, here's a reaction :)
I suppose the background learning required starts here
https://en.wikipedia.org/wiki/Interaction_nets
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.
Thanks for your advice :)
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!)
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.
SCXML actually stands for State Chart XML: State Machine Notation for Control Abstraction!
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 :)
Thanks everybody, your feedback and replys make me feel less lonely, I really appreciate it.
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://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.
Thanks for the info.
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.
4 replies →
hmm I'm just a bit confused; Can I make sense of it like this?
```
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?
Thanks for your reply.
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.
aw thanks for the link! what’s very nice to read !
I was on mobile and I think I accidentally clicked the gh link for the doc, and thought the readme was the doc
btw for me the readonly link took a while (like 4 sec) to load, probably due to parsing & cuz I’m on vpn.
would be cool to have a server-rendered page