It starts off looking like a slightly modified Rust until about half way through where it gets real weird. It’s burying the lede… why not open with what interaction nets are and why you’re building them into a programming language?
Made my head hurt a bit, it’s odd that it doesn’t really attempt to contextualise if the weirdness is for its own sake or some greater practical purpose.
Always fun to find a novel way to think about programming though.
Yeah I don't know enough rust to know what's special here. Presumably the inverse backwards part. I retain that every project (language, application, etc) should start with what it is, what it looks like (code or screenshot as appropriate), and why it matters. This felt very implicit in that.
And, I'm still not sure how that wacky stuff gets compiled down. It looks like syntax sugar as a language.
"This function calculates the minimum of a list of numbers, and subtracts every number in the list by that minimum. This function currently iterates over the list twice; once to calculate the minimum, and once to do the subtraction. At a first glance, it looks like there is no way to merge these two loops, because you need to calculate the minimum of all the numbers before you can subtract from any of them. As it turns out, this is possible, using the inverse operator."
I was long curious about interaction nets. Can someone confirm if Vine will automagically derive an algorithm for doing this with a single pass or it will do one pass in "forward mode", but once the minimum is resolved, follow it up with a second implicit "book keeping and variable re-resolution pass" that will be equivalent to an actual full second pass you'd get in an imperative language?
It is all very much reminiscent of programming in tensorflow 0.x.
> it will do one pass in "forward mode", but once the minimum is resolved, follow it up with a second implicit "book keeping and variable re-resolution pass" that will be equivalent to an actual full second pass you'd get in an imperative language
Yes, this is correct. Though it's worth noting that this is not some transformation being done by the compiler, but an emergent property of the interaction net.
I was thinking it must be possible to do something semantically similar in Prolog:
find_min_and_subtract([H], [R], Min) :-
Min = H,
R is H - Min.
find_min_and_subtract([H|T], [R|Rs], Min) :-
find_min_and_subtract(T, Rs, TailMin),
(H < TailMin -> Min = H ; Min = TailMin),
R is H - Min,!.
Which [9,4,12,2] -> [7, 2, 10, 0].
But this doesn't work for all cases anyway (just the ones where the last value is also the minimum). I feel it can be fully expressed in one pass with miniKanren instead but no time to figure that out now; it can defer the arithmetic by setting up constraints.
Always liked the idea of 'using variables in the past' (or creating them in the future) and the first amazement moment was with Prolog (there were quite a lot of wow! moments in Prolog for the young me who only knew basic, pascal & c, like when you have some 'write multiply in prolog', when you deliver f(x,y)=x*y, you can not only do f(2,3) and get 6, but also f(2,y)=6 and get y=3), but, so it made me think of it.
Yes, thunks with sugar is my thinking as well. Does not explain the "last unassignment" examples though. I don't quite understand why it's needed though :)
I like Inverse types! While it's not novel idea, this seems like a very concise implementation of it.
Inverse types are also known as negative types (https://legacy.cs.indiana.edu/~sabry/papers/rational.pdf) or holes. This concept is what needed to make a concrete category for computation compact (highly recommend: http://arxiv.org/abs/0903.0340) and make the connection to how our physical universe actually works on a quantum level, with antiparticles performing backward computation.
I'm pretty sure this model of computation of filling holes with inference would allow us to understand advantages of quantum computation much better.
Do you have any thoughts on HVM's SupGen for program synthesis? I would love to understand how interaction nets makes the notion of inverse types and filling holes more natural and efficient.
Constructive criticism, but I checked out the docs hoping for an up-front explanation of interaction nets and how they can improve a PL, what kinds of problems they are uniquely good for, etc. Finding none, I read the interaction nets wiki page, but still wasn't sure why "a PL based on Interaction Nets" is something I'd want. Of course, if the answer is "why not" in an esolang sense that's great, but I sensed there was something more and wanted to know what it was. In short, why did you make this language.
EDIT: btw, I knew I recognized your handle and it was from this amazing code golf answer:
Interaction nets are an alternate model of computation (along the lines of the lambda calculus or Turing machines). It has several interesting properties, one of the most notable being that it is fundamentally parallel. https://en.wikipedia.org/wiki/Interaction_netshttps://t6.fyi/guides/inets
I think there are many potential applications for interaction nets in parallel & distributed computing, among other fields; and such applications will need a language – hence Vine.
(re your edit – that's fun lol; Totally Cubular is one of my favorite projects)
Do interaction nets have any interesting properties that make them useful for distributed computing? Think IoT, edge computing, embedded, that kind of thing?
And synchronization primitives?
I wanted to also say I loved reading the documentation. Your idea of places, spaces and values feels like a waaay more intuitive naming scheme for than what's common in CS.
The time-travel example also felt oddly intuitive to me. I don't really care that it uses black magic underneath, it's quite elegant!
> Do interaction nets have any interesting properties that make them useful for distributed computing?
Of course, the intrinsic parallelism is useful there (especially since it is emergent from the structure of the program, rather than needing to be explicitly written). In terms of other interesting properties: interaction nets don't rely on linear memory, instead being based on a graph, which can naturally be chunked and distributed across machines, with synchronization only being necessary when wires span different chunks.
> And synchronization primitives?
The initial answer to this question is: interaction nets don't need synchronization primitives, as all parallelism is emergent from the net structure.
Now, in practice, one may want some additional synchronization-esque primitives. For example, a parallel shortcircuiting or is not expressible in vanilla interaction nets (as all computation is deterministic, and such an operation isn't deterministic). There are extensions to interaction nets for non-determinism, that allow some of these use-cases, which start to look more like synchronization primitives. Vine doesn't support any of these at the moment, but it may in the future.
> I wanted to also say I loved reading the documentation. Your idea of places, spaces and values feels like a waaay more intuitive naming scheme for than what's common in CS.
I'm glad to hear it! I spend a lot of time trying to come up with good names for things, so it's nice to know that that pays off. Though I suppose it's not too hard to improve on the status quo, when it's 'lvalue'/'rvalue', lol. (I did, however, steal 'place' and 'value' from Rust.)
> The time-travel example also felt oddly intuitive to me. I don't really care that it uses black magic underneath, it's quite elegant!
Yeah, the 'time-travel' stuff sounds wacky, but I do think it can be really intuitive if one is willing to accept it. I wrote a really cool algorithm a little while ago that really uses this 'time-travel' idea; I [wrote about it](https://discord.com/channels/1246152587883970662/12461564508...) on Discord. (I should really type that up into a blog post of sorts.
This is something I never got through my annual rechecking of the interaction nets wiki page, cause isn't the lambda calculus also fundamentally parallel? Are nets even more?
Both lambda calculus and interaction nets are confluent. That is, for a term that can be normalised (i.e. evaluated), one can obtain the same answer by performing any available action in any order (n.b. if the chosen order terminates). For example, for `A (B) (C (D))`, I can choose to first evaluate either `A (B)` or `C (D)` and the final answer will be the same. This is true in both systems (although the reduction in interaction nets has more satisfactory properties).
The key reason one may consider interaction nets to be more parallelisable than lambda calculus is that the key evaluation operation is global in lambda calculus, but local in interaction nets. The key evaluation operation in labmda calculus is (beta) reduction. For instance, if one evaluates a lambda term `(\n -> f n n) x`, reduction takes this to the term `f x x`. To do so, one must duplicate the entire term `x` from the argument to perform the computation, by either 1) physical duplication, or 2) keeping track of references. Both are unsatisfactory solutions with many properties hindering parallelism. As I shall explain, the term `x` may be of unbounded size or be intertwined non-locally with a large part of the control graphs of other terms.
If `x` is simply a ground term (i.e. a piece of data), then it seems like either duplication or keeping track of the references would be an inevitable and reasonable cost, with the usual managed-language issues of garbage collection. If one decides to solve the problem by attempting to force the argument to be a ground term, one would find the only method to be to impose eager evaluation, evaluating terms by always first evaluating the leaf of the expression, before evaluating internal nodes in the expression. Eager evaluation can easily become unboundedly wasteful when one strives to reuse a general computation for some more specific use cases, so one may not prefer an eager evaluation doctrine.
However, once one evaluates in an order that is not strictly eager (e.g. lazy evaluation), the terms that one is duplicating or referencing are no longer simple pieces of data, but pieces of a (not necessarily acyclic) control graph, and any referencing logic quickly becomes very complicated. Moreover, the argument `x` could also be a function, and keeping track of references would involve keeping track of closures over different variables and scopes, which complicates the problem of sharing even further.
Thus, either one follows an eager evaluation order, in which most of the nodes in a term's expression tree are not available for evaluation yet, and available pieces of work for evaluation are only generated as evaluation happens, which imposes a global and somewhat strict serialised order of execution, or one deals with a big complicated shared graph, which is also inconvenient to be distributed across computational resources.
In contrast with lambda calculus, the key evaluation operation in interaction nets is local. Interaction nets can be seen as more low-level than lambda calculus, and both code and data are represented as graphs of nodes to be evaluated. Thus, a large term is represented as a large net, and regardless of the unbounded size of a term, in one unit of evaluation, only one node from the term's graph is involved.
Given a graph of some 'net' to be evaluated, one can choose any "active" node and begin evaluating right there, and the result of computation in that unit of evaluation will be guaranteed to affect only the nodes originally connected to the evaluated node, no referencing involved. Thus, the problem of computation becomes almost embarrassingly parallel, where workers simply pick any piece of a graph and locally add or remove from that piece of the graph.
This is what is meant when one refers to interaction nets being more parallelisable than lambda calculus.
You may be interested in my other comment. To put it simply, pure languages remove serialisation of false data dependencies, exposing data parallelism, and interaction nets remove serialisation of false control dependencies, exposing control parallelism.
Have you thought about how autodiff can be baked into the lang? Given that it is already seemingly all representing computation with graphs of operations, building AD into it seems like a natural extension that could open up some pretty useful applications/bring in some scientific computing interest.
I’m also curious to think about how the “time travel” might interact (if at all) with (1) basic algebra and (2) building off that, systems of equations and (3) building off of that something like implicit/crank-nicholson finite difference schemes.
Without having thought about it much, it feels intuitively like there might be an elegant way of expressing such algorithms using this notion of information traveling backwards, but perhaps not.
As an aside, although I’m not really a fan, the representation of time travel in Tenet seems like a natural analogy to include in your docs for fun if desired. More relevant, talking about things like backprop in standard ML packages might be one way of providing a shared reference point for contextualizing information flowing backward through a computational graph.
Finally, echoing what others have said about not burying the lede in the docs, as well as wanting to see more motivation/examples/discussion of interaction nets.
About the inverse feature: it is not clear to me how code using it evaluates and how much faster it is. But I find it confusing when reading the sub_min[1] function and reminds me how much I value readability. I'm not convinced that feature should be exposed just because interaction nets allow you to flow time backwards. Better free parallelism is already a great improvement!
I don’t pretend to understand all the theory for nets stuff, but the premise seems super cool and I love languages that have experimental and unusual ideas!
Also liked the dedicated section about the compiler design: the description of the different passes is cool.
There are many. One major difference is that HVM/Bend focus entirely on functional programming, whereas Vine supports both imperative and functional patterns, in a cohesive manner.
It starts off looking like a slightly modified Rust until about half way through where it gets real weird. It’s burying the lede… why not open with what interaction nets are and why you’re building them into a programming language?
Made my head hurt a bit, it’s odd that it doesn’t really attempt to contextualise if the weirdness is for its own sake or some greater practical purpose.
Always fun to find a novel way to think about programming though.
Yeah I don't know enough rust to know what's special here. Presumably the inverse backwards part. I retain that every project (language, application, etc) should start with what it is, what it looks like (code or screenshot as appropriate), and why it matters. This felt very implicit in that.
And, I'm still not sure how that wacky stuff gets compiled down. It looks like syntax sugar as a language.
"This function calculates the minimum of a list of numbers, and subtracts every number in the list by that minimum. This function currently iterates over the list twice; once to calculate the minimum, and once to do the subtraction. At a first glance, it looks like there is no way to merge these two loops, because you need to calculate the minimum of all the numbers before you can subtract from any of them. As it turns out, this is possible, using the inverse operator."
https://vine.dev/docs/features/inverse
I was long curious about interaction nets. Can someone confirm if Vine will automagically derive an algorithm for doing this with a single pass or it will do one pass in "forward mode", but once the minimum is resolved, follow it up with a second implicit "book keeping and variable re-resolution pass" that will be equivalent to an actual full second pass you'd get in an imperative language?
It is all very much reminiscent of programming in tensorflow 0.x.
Reading this page made me feel same way when was watching Tenet.
> it will do one pass in "forward mode", but once the minimum is resolved, follow it up with a second implicit "book keeping and variable re-resolution pass" that will be equivalent to an actual full second pass you'd get in an imperative language
Yes, this is correct. Though it's worth noting that this is not some transformation being done by the compiler, but an emergent property of the interaction net.
I was thinking it must be possible to do something semantically similar in Prolog:
Which [9,4,12,2] -> [7, 2, 10, 0].But this doesn't work for all cases anyway (just the ones where the last value is also the minimum). I feel it can be fully expressed in one pass with miniKanren instead but no time to figure that out now; it can defer the arithmetic by setting up constraints.
Always liked the idea of 'using variables in the past' (or creating them in the future) and the first amazement moment was with Prolog (there were quite a lot of wow! moments in Prolog for the young me who only knew basic, pascal & c, like when you have some 'write multiply in prolog', when you deliver f(x,y)=x*y, you can not only do f(2,3) and get 6, but also f(2,y)=6 and get y=3), but, so it made me think of it.
That's a very cute feature! Thinking about it in terms of thunks makes it pretty understandable to me.
Yes, thunks with sugar is my thinking as well. Does not explain the "last unassignment" examples though. I don't quite understand why it's needed though :)
I like Inverse types! While it's not novel idea, this seems like a very concise implementation of it. Inverse types are also known as negative types (https://legacy.cs.indiana.edu/~sabry/papers/rational.pdf) or holes. This concept is what needed to make a concrete category for computation compact (highly recommend: http://arxiv.org/abs/0903.0340) and make the connection to how our physical universe actually works on a quantum level, with antiparticles performing backward computation. I'm pretty sure this model of computation of filling holes with inference would allow us to understand advantages of quantum computation much better.
Do you have any thoughts on HVM's SupGen for program synthesis? I would love to understand how interaction nets makes the notion of inverse types and filling holes more natural and efficient.
Awesome. It looks like Easy mode rust.
1. Since it is based on Interaction Net, is it parallelized well?
2. Will there be a borrow checker like Rust does?
I first heard about interaction nets from HVM [1]. It sounds very interesting but I can't say I get it.
[1] https://higherorderco.com/
> Think inets as like sort of lambda calculus runtime: > lambdas -> inets -> reduced inets -> lambdas
a bit like Tree Calculus but with nets.
[dead]
Related article I’m enjoying for more context on interaction nets:
https://wiki.xxiivv.com/site/interaction_nets.html
(We changed the URL from https://vine.dev/ to the linked page that starts off with a bit more background)
Author here, happy to answer any questions.
Constructive criticism, but I checked out the docs hoping for an up-front explanation of interaction nets and how they can improve a PL, what kinds of problems they are uniquely good for, etc. Finding none, I read the interaction nets wiki page, but still wasn't sure why "a PL based on Interaction Nets" is something I'd want. Of course, if the answer is "why not" in an esolang sense that's great, but I sensed there was something more and wanted to know what it was. In short, why did you make this language.
EDIT: btw, I knew I recognized your handle and it was from this amazing code golf answer:
https://codegolf.stackexchange.com/questions/108170/totally-...
Yeah, that would be good to add to the docs.
Interaction nets are an alternate model of computation (along the lines of the lambda calculus or Turing machines). It has several interesting properties, one of the most notable being that it is fundamentally parallel. https://en.wikipedia.org/wiki/Interaction_nets https://t6.fyi/guides/inets
I think there are many potential applications for interaction nets in parallel & distributed computing, among other fields; and such applications will need a language – hence Vine.
(re your edit – that's fun lol; Totally Cubular is one of my favorite projects)
Do interaction nets have any interesting properties that make them useful for distributed computing? Think IoT, edge computing, embedded, that kind of thing?
And synchronization primitives?
I wanted to also say I loved reading the documentation. Your idea of places, spaces and values feels like a waaay more intuitive naming scheme for than what's common in CS.
The time-travel example also felt oddly intuitive to me. I don't really care that it uses black magic underneath, it's quite elegant!
> Do interaction nets have any interesting properties that make them useful for distributed computing?
Of course, the intrinsic parallelism is useful there (especially since it is emergent from the structure of the program, rather than needing to be explicitly written). In terms of other interesting properties: interaction nets don't rely on linear memory, instead being based on a graph, which can naturally be chunked and distributed across machines, with synchronization only being necessary when wires span different chunks.
> And synchronization primitives?
The initial answer to this question is: interaction nets don't need synchronization primitives, as all parallelism is emergent from the net structure.
Now, in practice, one may want some additional synchronization-esque primitives. For example, a parallel shortcircuiting or is not expressible in vanilla interaction nets (as all computation is deterministic, and such an operation isn't deterministic). There are extensions to interaction nets for non-determinism, that allow some of these use-cases, which start to look more like synchronization primitives. Vine doesn't support any of these at the moment, but it may in the future.
> I wanted to also say I loved reading the documentation. Your idea of places, spaces and values feels like a waaay more intuitive naming scheme for than what's common in CS.
I'm glad to hear it! I spend a lot of time trying to come up with good names for things, so it's nice to know that that pays off. Though I suppose it's not too hard to improve on the status quo, when it's 'lvalue'/'rvalue', lol. (I did, however, steal 'place' and 'value' from Rust.)
> The time-travel example also felt oddly intuitive to me. I don't really care that it uses black magic underneath, it's quite elegant!
Yeah, the 'time-travel' stuff sounds wacky, but I do think it can be really intuitive if one is willing to accept it. I wrote a really cool algorithm a little while ago that really uses this 'time-travel' idea; I [wrote about it](https://discord.com/channels/1246152587883970662/12461564508...) on Discord. (I should really type that up into a blog post of sorts.
This is something I never got through my annual rechecking of the interaction nets wiki page, cause isn't the lambda calculus also fundamentally parallel? Are nets even more?
Both lambda calculus and interaction nets are confluent. That is, for a term that can be normalised (i.e. evaluated), one can obtain the same answer by performing any available action in any order (n.b. if the chosen order terminates). For example, for `A (B) (C (D))`, I can choose to first evaluate either `A (B)` or `C (D)` and the final answer will be the same. This is true in both systems (although the reduction in interaction nets has more satisfactory properties).
The key reason one may consider interaction nets to be more parallelisable than lambda calculus is that the key evaluation operation is global in lambda calculus, but local in interaction nets. The key evaluation operation in labmda calculus is (beta) reduction. For instance, if one evaluates a lambda term `(\n -> f n n) x`, reduction takes this to the term `f x x`. To do so, one must duplicate the entire term `x` from the argument to perform the computation, by either 1) physical duplication, or 2) keeping track of references. Both are unsatisfactory solutions with many properties hindering parallelism. As I shall explain, the term `x` may be of unbounded size or be intertwined non-locally with a large part of the control graphs of other terms.
If `x` is simply a ground term (i.e. a piece of data), then it seems like either duplication or keeping track of the references would be an inevitable and reasonable cost, with the usual managed-language issues of garbage collection. If one decides to solve the problem by attempting to force the argument to be a ground term, one would find the only method to be to impose eager evaluation, evaluating terms by always first evaluating the leaf of the expression, before evaluating internal nodes in the expression. Eager evaluation can easily become unboundedly wasteful when one strives to reuse a general computation for some more specific use cases, so one may not prefer an eager evaluation doctrine.
However, once one evaluates in an order that is not strictly eager (e.g. lazy evaluation), the terms that one is duplicating or referencing are no longer simple pieces of data, but pieces of a (not necessarily acyclic) control graph, and any referencing logic quickly becomes very complicated. Moreover, the argument `x` could also be a function, and keeping track of references would involve keeping track of closures over different variables and scopes, which complicates the problem of sharing even further.
Thus, either one follows an eager evaluation order, in which most of the nodes in a term's expression tree are not available for evaluation yet, and available pieces of work for evaluation are only generated as evaluation happens, which imposes a global and somewhat strict serialised order of execution, or one deals with a big complicated shared graph, which is also inconvenient to be distributed across computational resources.
In contrast with lambda calculus, the key evaluation operation in interaction nets is local. Interaction nets can be seen as more low-level than lambda calculus, and both code and data are represented as graphs of nodes to be evaluated. Thus, a large term is represented as a large net, and regardless of the unbounded size of a term, in one unit of evaluation, only one node from the term's graph is involved.
Given a graph of some 'net' to be evaluated, one can choose any "active" node and begin evaluating right there, and the result of computation in that unit of evaluation will be guaranteed to affect only the nodes originally connected to the evaluated node, no referencing involved. Thus, the problem of computation becomes almost embarrassingly parallel, where workers simply pick any piece of a graph and locally add or remove from that piece of the graph.
This is what is meant when one refers to interaction nets being more parallelisable than lambda calculus.
That's a great explanation.
Isn't any pure language easy to parallelize? What advantage do interaction nets offer over a parallelizing compiler for a purely functional language?
You may be interested in my other comment. To put it simply, pure languages remove serialisation of false data dependencies, exposing data parallelism, and interaction nets remove serialisation of false control dependencies, exposing control parallelism.
Have you thought about how autodiff can be baked into the lang? Given that it is already seemingly all representing computation with graphs of operations, building AD into it seems like a natural extension that could open up some pretty useful applications/bring in some scientific computing interest.
I’m also curious to think about how the “time travel” might interact (if at all) with (1) basic algebra and (2) building off that, systems of equations and (3) building off of that something like implicit/crank-nicholson finite difference schemes.
Without having thought about it much, it feels intuitively like there might be an elegant way of expressing such algorithms using this notion of information traveling backwards, but perhaps not.
As an aside, although I’m not really a fan, the representation of time travel in Tenet seems like a natural analogy to include in your docs for fun if desired. More relevant, talking about things like backprop in standard ML packages might be one way of providing a shared reference point for contextualizing information flowing backward through a computational graph.
Finally, echoing what others have said about not burying the lede in the docs, as well as wanting to see more motivation/examples/discussion of interaction nets.
About the inverse feature: it is not clear to me how code using it evaluates and how much faster it is. But I find it confusing when reading the sub_min[1] function and reminds me how much I value readability. I'm not convinced that feature should be exposed just because interaction nets allow you to flow time backwards. Better free parallelism is already a great improvement!
[1] https://vine.dev/docs/features/inverse
This is really, really cool!
I don’t pretend to understand all the theory for nets stuff, but the premise seems super cool and I love languages that have experimental and unusual ideas!
Also liked the dedicated section about the compiler design: the description of the different passes is cool.
Why Vine and Ivy instead of Bend and HVM?
Please provide an example on the first page.
What are the differences with HVM?
There are many. One major difference is that HVM/Bend focus entirely on functional programming, whereas Vine supports both imperative and functional patterns, in a cohesive manner.