7 ms·

Show HN: iNet – A programming language for interaction nets

67 points by xyheme 3y ago

gsuuon 3y ago
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.
- xyheme 3y ago
  happy to see you like it :)
pavlov 3y ago
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.”
- savolai 3y ago
  Hi pavlov, here's a reaction :) I suppose the background learning required starts here https://en.wikipedia.org/wiki/Interaction_nets https://en.wikipedia.org/wiki/Interaction_nets
- gsuuon 3y ago
  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 https://github.com/HigherOrderCO/HVM
- xyheme 3y ago
  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.
savolai 3y ago
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.
- xyheme 3y ago
  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!)
archibaldJ 3y ago
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?
- xyheme 3y ago
  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/articles/programming-with-interaction-nets.md https://readonly.link/articles/https://cdn.inet.cic.run/docs... Maybe this article can help.
  - archibaldJ 3y ago
    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
  - archibaldJ 3y ago
    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
bojidar-bg 3y ago
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/85026fa70e6ba7b1862bf8226ba9feca 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.
- xyheme 3y ago
  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 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)
  - archibaldJ 3y ago
    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 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
jondwillis 3y ago
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.
- xyheme 3y ago
  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 https://www.forth.com/starting-forth and the language Joy: https://hypercubed.github.io/joy/joy.html 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 :)
sheepscreek 3y ago
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.
- gsuuon 3y ago
  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.
- xyheme 3y ago
  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/references/papers/1990-interaction-nets.pdf 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.
- archibaldJ 3y ago
  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-understand-how-the-first-hadamard-gate-in-deutsch-jozsa-algorithm-work 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
deleted 3y ago
[deleted]
xyheme 3y ago
Thanks everybody, your feedback and replys make me feel less lonely, I really appreciate it.
- qazxcvbnm 3y ago
  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 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 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.
  - xyheme 3y ago
    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.

67 points by xyheme 3y ago

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.

xyheme 3y ago
happy to see you like it :)

pavlov 3y ago

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.”

savolai 3y ago
Hi pavlov, here's a reaction :) I suppose the background learning required starts here https://en.wikipedia.org/wiki/Interaction_nets https://en.wikipedia.org/wiki/Interaction_nets
gsuuon 3y ago
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 https://github.com/HigherOrderCO/HVM
xyheme 3y ago
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.

savolai 3y ago

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.

xyheme 3y ago
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!)

archibaldJ 3y ago

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?

xyheme 3y ago
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/articles/programming-with-interaction-nets.md https://readonly.link/articles/https://cdn.inet.cic.run/docs... Maybe this article can help.
- archibaldJ 3y ago
  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
- archibaldJ 3y ago
  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

bojidar-bg 3y ago

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/85026fa70e6ba7b1862bf8226ba9feca 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.

xyheme 3y ago
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 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)
- archibaldJ 3y ago
  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 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

jondwillis 3y ago

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.

xyheme 3y ago
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 https://www.forth.com/starting-forth and the language Joy: https://hypercubed.github.io/joy/joy.html 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 :)

sheepscreek 3y ago

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.

gsuuon 3y ago
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.
xyheme 3y ago
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/references/papers/1990-interaction-nets.pdf 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.
archibaldJ 3y ago
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-understand-how-the-first-hadamard-gate-in-deutsch-jozsa-algorithm-work 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

deleted 3y ago

[deleted]

xyheme 3y ago

Thanks everybody, your feedback and replys make me feel less lonely, I really appreciate it.

qazxcvbnm 3y ago
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 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 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.
- xyheme 3y ago
  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.