chorasimilarity / chemlambda-gui

Life like molecular computers with artificial chemistry.
https://chemlambda.github.io/index.html
GNU General Public License v2.0
134 stars 14 forks source link

How does the naming of ports affect the locality of chemlambda interactions? #4

Closed synergistics closed 3 years ago

synergistics commented 8 years ago

Hey again Marius! I have another question about chemlambda. First, some background on the situation:

I'm currently implementing the moves for chemlambda-hask. In my implementation of chemlambda, a graph is a list of atoms and their port numbers. An atom is of the form:

L [1,2,3]

where L is the atom (in this case Lambda) and the subsequent list is the list of ports. A graph is just a list of nodes of this form.

Often, applying a move to a part of a graph introduces new, unique, port numbers. To properly introduce new nodes to a graph, I have to check to see which port numbers are already in use as to not conflict with them. So say I need to add a new port and numbers 0 through 4 are taken in the initial graph, the new port will have the id of 5. However, this seems to defy locality because the id of the port relies on which ids are already in use in the entire graph.

As I understand it, moves in chemlambda are local. However, what I don't understand is at what level of abstraction is that true. Is it just an implementation detail that port ids must be unique so that the system can properly add new ports, or is there something inherently wrong about that. I'm inclined to believe that it's ok to check the graph for usable port names because one of the requirements for a mol file to be a proper molecule is that each port name occurs twice, once in an in port, once in an out port. For this to be true, the whole graph must be checked, so subsequent checks for available port names seems to be required to make sure this rule holds.

Also, I've been thinking that as chemlambda gains more active contributors, it would be a good idea to start a subreddit about chemlambda to form a larger, productive community around the project.

chorasimilarity commented 8 years ago

Good question. In the most recent versions of the program I use a counter for generating new names for port variables. But in the first versions I used a local procedure to get new names from the old names involved in the rewrite, for example by concatenating in certain orders the old names to get new ones (one has to be careful with the initial names, though).

An alternative to use a counter for the port names is to use a counter for the nodes. This raises a philosophical problem, actually, because indeed it is not a local procedure, but on the other side different atoms can be identified by different names, right?

So eventually I put these matter on hold because that's just a notation problem, I mean a human notation problem. A hypothesis dear to me is that there exist real molecules (for nodes, ports, bonds and the invisible enzymes) which react as in chemlambda. Then, a mixture of such real molecules will behave like in a chemlambda simulation, without having the naming problem of a chemlambda program.

Alternative: any naming system is practically a tree, with names as nodes and arrows as letters from an alphabet (there's an arrow, say, from the word w to the word aw, where a is a letter). Now, imagine that you allow the existence of "actors" with unique names (unique ID's, i.e. coming from a tree of servers with the actors as leaves, as in reality), so that each actor has a chemlambda molecule as a state. Each actor has the freedom to follow it's own rule of naming the nodes and bonds, so it's a kind of enlarged notion of locality of naming. Each actor has the freedom to reduce it's own molecule by following any algorithm of reduction. There exist though bonds between nodes belonging to different actors, and these bonds appear between FRIN and FROUT nodes of different actors. These bonds have names which are given by a mixture between the server structure and actors (just like a combination of ports names of an individual computer and the computer ID). Based on such a system one can imagine different algorithms for reducing a pair of nodes belonging to different actors (that's actually something I would like to try or see somebody trying). Overall any evolution of such a decentralized system is equivalent to a random reduction over the whole molecule, but due to the locality of reduction and due to the server structure (hence due to a naming of bonds algorithm which is also local), one does not have to care about synchronization, nor about notions which do not make sense, like global state of the network of actors.

About the reddit, good idea, please do something like this and put me to work by asking more and more punctual questions until something better than I can do alone emerges.

I should (or anybody willing to) write the algorithms in other language than awk, there are many others things to do, like writing a parser from lambda calculus to chemlambda mol notation, or finding a more clever way to visualize the computation, or writing small programs for various statistics, or doing some search in the space of molecules (which is huge) by some genetic like algorithms. Somebody said once that a version of Haskell in chemlambda style would be nice. Indeed, that is doable in principle, because the main structure of chemlambda comes from FI, FO and FOE and their rewrites, for the rest of the nodes, they have some internal reductions (like beta for the pair A-L) and otherwise they are distributors. Or, why not take the Haskell primitives as nodes?

On Sun, Jul 10, 2016 at 7:39 PM, synergistics notifications@github.com wrote:

Hey again Marius! I have another question about chemlambda. First, some background on the situation:

I'm currently implementing the moves for chemlambda-hask. In my implementation of chemlambda, a graph is a list of atoms and their port numbers. An atom is of the form:

L [1,2,3]

where L is the atom (in this case Lambda) and the subsequent list is the list of ports. A graph is just a list of nodes of this form.

Often, applying a move to a part of a graph introduces new, unique, port numbers. To properly introduce new nodes to a graph, I have to check to see which port numbers are already in use as to not conflict with them. So say I need to add a new port and numbers 0 through 4 are taken in the initial graph, the new port will have the id of 5. However, this seems to defy locality because the id of the port relies on which ids are already in use in the entire graph.

As I understand it, moves in chemlambda are local. However, what I don't understand is at what level of abstraction is that true. Is it just an implementation detail that port ids must be unique so that the system can properly add new ports, or is there something inherently wrong about that. I'm inclined to believe that it's ok to check the graph for usable port names because one of the requirements for a mol file to be a proper molecule is that each port name occurs twice, once in an in port, once in an out port. For this to be true, the whole graph must be checked, so subsequent checks for available port names seems to be required to make sure this rule holds.

Also, I've been thinking that as chemlambda gains more active contributors, it would be a good idea to start a subreddit about chemlambda to form a larger, productive community around the project.

— You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub https://github.com/chorasimilarity/chemlambda-gui/issues/4, or mute the thread https://github.com/notifications/unsubscribe/AIDOW36LC_MDF4eCnYpuqLGdIyJaad6aks5qUSAwgaJpZM4JI3nn .

synergistics commented 8 years ago

I'm interested, could you elaborate on the actors you're talking about? First, what do you consider a server? Does the tree of servers and actors represent a single molecule? In addition to encapsulating a certain reaction behavior, does an actor represent a namespace for the ports (or FRIN and FROUT nodes)? Like let's say two actors are connected by a FRIN and FROUT pair, call them Apple and Banana cause why not). Let's say the FROUT in Apple had an id of 1, and the FRIN in Banana had an id of 2. Would the connection between the two, in chemlambda notation with the addition of namespaced actors be as follows?

FROUT(1) Banana:2 //in Apple
FRIN(2) Apple:1 //in Banana

Where the (n) indicates the id of the FRIN or FROUT, and S:a indicates a connection to another FRIN or FROUT of id a in actor S. Does that describe the model you're discussing? It brings up a bunch of other interesting topics to think about. Like, could actors be dynamic, and cover different parts of a molecule at different points in a reaction? If I imagine a chemlambda molecule in my head, an actor would be like a circle capturing group that moves over a certain part of the graph and modifies it according to the pattern it's looking for and the result it encodes. But then if actors are dynamic in such a way, then all I did was describe an enzyme. Hehe. So it seems that what would make an actor useful is that it would be static over a certain region... maybe. I think I could make more sense of this if you explained the server actor tree in more detail.

chorasimilarity commented 8 years ago

Good remarks! OK, what I imagine is the following. Suppose the names of the actors are words with the letters 0, 1. So the actors are the leaves of some binary tree and the nodes of the binary tree are servers.

  1. If you consider a mol file F then there are port variables which occur once or twice, right? Those which occur only once induce the creation of some FRIN or FROUT nodes so that, with those nodes added, they occur twice.
  2. Then, if we partition the mol file F to the actors, it follows that each actor (say, named w, with w a word with letters 0 and 1) receives a mol file F_w, which is a valid mol file, because each port variable from F_w occurs once or twice.
  3. Suppose that there is an agreement between the actors concerning the way to name port variables which occur once, initially. A port variable a which occurs twice in F, but such that it occurs once in F_w and once in F_q, with w \not = q, gets the name "w:a" in F_w and "q:a$ in F_q, simply because we add "w:" to all the names of port variables in F_w. There is an agreement about how to manage variables which occurs only once in F_w, for any F_w, for example there is an algorithm, which each actor has, so that it announces to the servers which are on the path from the name w to the root that on "actor port x" it has a port variable publicly called "y", which is the port variable of a node of type L, A, FO, ... on the pozition Z (i.e for example it's the port variable of the 3rd port of an L, say). Then each actor keeps a table of correspondence between internal names and public names of those variables.
  4. Define the boundary of an actor w state F_w as being those lines of F_w which contain a port variable which occurs once. Suppose there is an agreement between the actors about which ports of a node which belongs to a boundary are active (i.e. the 3rd port of a node L, the 1st port of a node FOE, etc). Mind that for example a node A may be involved in a A-L rewrite, in which case the first port of the A node is active, or, say, in a A-FO rewrite, in which case the 3rd port of A is active. Just decide in advance an unique active port for any node (type). The nodes from the boundary which have an n active port connected to a FRIM or FROUT are blocked (they are not involved into internal rewrites).
  5. Your remark about enzymes travelling through servers is right! Indeed, suppose that the point 3 is modified into actors announcing their servers (on the path to the root) only the active port variables and their place as active ports of nodes. Then there is an unique server (say u) who knows that the actor uv has a node N on the boundary and the actor uw has a node M on the boundary such that NM is a pattern for a rewrite and it does perform the rewrite by splitting it in half and sending to uv and uw the right commands.
  6. A special place occupy the COMB rewrites between different actors, but this is left for clarification.

Something like this.

On Sun, Jul 10, 2016 at 11:24 PM, synergistics notifications@github.com wrote:

Better formatting in the code:

`FROUT(1) Banana:2 //in Apple

FRIN(2) Apple:1 //in Banana`

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/chorasimilarity/chemlambda-gui/issues/4#issuecomment-231608935, or mute the thread https://github.com/notifications/unsubscribe/AIDOW18-pV6dtasp_ADnmqH9QwvPx0SDks5qUVUOgaJpZM4JI3nn .

synergistics commented 8 years ago

I'll be able to talk later but had to say something because I thought this was so funny. I had drawn some pictures to help me make sense of what you were saying just a few hours ago, and I guess we were thinking alike. HA!

synergistics commented 8 years ago

Alright. I'm getting what you're saying for the most part. But how do the actors play in each move cycle? Is the set of actors originally produced for a graph the same set used in every move cycle? I guess this would depend partially on where the actors are placed in the graph, that is, over which nodes they're placed.

On that note, how would the positions of the actors be initially determined? I guess the algorithm for reduction used would have something to do with that. One idea would be splitting the graph into actors placed over the reaction sites, or even between them. But then, would a new set of actors be produced on each move cycle, because the reactions sites at one stage of the molecule would obviously be different from the next reduction in most cases.

With these questions answered, maybe you'll have already answered this next question for me, but what would be the benefit of using actors over a simple counter?

chorasimilarity commented 8 years ago

This actors thing is originally designed for reducing graphs in a decentralized, asynchronous manner. There was this initial proposal about a precursor of chemlambda, called GLC (graphic lambda calculus): http://arxiv.org/abs/1312.4333

This was part of a project which was submitted for a NSF grant, but at that moment there were no programs so the (very fair in my opinion) referees recognized that may be something big but for the moment too theoretical. Out of frustration, after asking the real programmers to make some demos which would at least simulate what may happen, I eventually made these chemlambda programs, to simulate possible behaviours of a decentralized system. It happens that the building of a decentralized system with chemlambda is very close to the building of a molecular computer with chemlambda in reality, the only differences are: in reality one has to identify real chemicals which react like in the moves and for the rest let Nature, the fastest and the best decentralized async computer work, while for a system living on a network of computers the chemlambda (or GLC initially) has to be supplemented with these actors and your preferred communication algorithm between actors (and servers).

This chemlambda with actors can be simulated in a simple way: just add to any node (which is as you say a list, or a line in a mol file) an actor color, and supplement the rewrites with rules for coloring the new nodes, i.e. enhance the rewrites to rewrites for graphs with nodes colored with "actor colours".

If you look into the repository then you'll notice that there are some files with the extension "mola" instead of "mol". The mola files are exactly like mol files, with the actor color added as the last element of the list which represent a node. You can play with these by using bash quiner_node.sh which calls an awk script (look into the quiner_node.sh) which performs the enhanced rewrites.

There are examples which appeared in the chemlambda collection:

Again, I stress that these are simulations of a decentralized computation, where the actors appear as colors decorating nodes and the random reductions simulate async computation.

So:

On Mon, Jul 11, 2016 at 7:34 AM, synergistics notifications@github.com wrote:

Alright. I'm getting what you're saying for the most part. But how do the actors play in each move cycle? Is the set of actors originally produced for a graph the same set used in every move cycle? I guess this would depend partially on where the actors are placed in the graph, that is, which nodes their placed over. How would the positions of the actors be initially determined? I guess the algorithm for reduction used would have something to do with that. One idea would be splitting the graph into all the places where reactions occur. But then, would a new set of actors be produced on each move cycle? With these questions answered, maybe you'll have already answered this question for me, but what would be the benefit of using actors over a simple counter?

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/chorasimilarity/chemlambda-gui/issues/4#issuecomment-231640251, or mute the thread https://github.com/notifications/unsubscribe/AIDOW604hmNJwoJWftboytLN2fjWars2ks5qUcfPgaJpZM4JI3nn .

chorasimilarity commented 8 years ago

I updated the awk file called by quiner_node.sh, i.e. https://github.com/chorasimilarity/chemlambda-gui/blob/gh-pages/dynamic/quiner_experia_fifrin_node.awk . It's funny, there was there an old bug (caused by a typo in the random parameter for the FI-FO move, where I wrote "growcont" instead of "growfact"). This bug made the FI-FO move inactive, so it was not visible what the enhanced FI-FO move does with the colours. After fixing the bug I ran quinernode.sh with ackack.mola, the example with two computations of ackermann functions with shared part. It did no longer behave as in https://plus.google.com/u/0/+MariusBuliga/posts/HDahJJYPbXv , and I finally realized that I can reproduce that example by inhibiting the FI-FO move by hand (I picked the wei parameter for that move to be 1000).

That made me realize that the enhanced FI-FO move may be not right and after some thinking I modified it into a version where the colours of the new nodes are all coming from the source node of the move (i.e. the colour of FI). Now it works well, although I should carefully update the script in other respects as well, to the level of quiner_shuffle.awk.

On Mon, Jul 11, 2016 at 11:24 AM, Marius Buliga marius.buliga@gmail.com wrote:

This actors thing is originally designed for reducing graphs in a decentralized, asynchronous manner. There was this initial proposal about a precursor of chemlambda, called GLC (graphic lambda calculus): http://arxiv.org/abs/1312.4333

This was part of a project which was submitted for a NSF grant, but at that moment there were no programs so the (very fair in my opinion) referees recognized that may be something big but for the moment too theoretical. Out of frustration, after asking the real programmers to make some demos which would at least simulate what may happen, I eventually made these chemlambda programs, to simulate possible behaviours of a decentralized system. It happens that the building of a decentralized system with chemlambda is very close to the building of a molecular computer with chemlambda in reality, the only differences are: in reality one has to identify real chemicals which react like in the moves and for the rest let Nature, the fastest and the best decentralized async computer work, while for a system living on a network of computers the chemlambda (or GLC initially) has to be supplemented with these actors and your preferred communication algorithm between actors (and servers).

This chemlambda with actors can be simulated in a simple way: just add to any node (which is as you say a list, or a line in a mol file) an actor color, and supplement the rewrites with rules for coloring the new nodes, i.e. enhance the rewrites to rewrites for graphs with nodes colored with "actor colours".

If you look into the repository then you'll notice that there are some files with the extension "mola" instead of "mol". The mola files are exactly like mol files, with the actor color added as the last element of the list which represent a node. You can play with these by using bash quiner_node.sh which calls an awk script (look into the quiner_node.sh) which performs the enhanced rewrites.

There are examples which appeared in the chemlambda collection:

Again, I stress that these are simulations of a decentralized computation, where the actors appear as colors decorating nodes and the random reductions simulate async computation.

So:

  • how to partition the initial molecule to actors? To explore!
  • the actors are dynamical, because you may imagine an actors diagram, with the actors as nodes of this actors diagram and the bonds as those bonds which connect ports from different actors states

On Mon, Jul 11, 2016 at 7:34 AM, synergistics notifications@github.com wrote:

Alright. I'm getting what you're saying for the most part. But how do the actors play in each move cycle? Is the set of actors originally produced for a graph the same set used in every move cycle? I guess this would depend partially on where the actors are placed in the graph, that is, which nodes their placed over. How would the positions of the actors be initially determined? I guess the algorithm for reduction used would have something to do with that. One idea would be splitting the graph into all the places where reactions occur. But then, would a new set of actors be produced on each move cycle? With these questions answered, maybe you'll have already answered this question for me, but what would be the benefit of using actors over a simple counter?

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/chorasimilarity/chemlambda-gui/issues/4#issuecomment-231640251, or mute the thread https://github.com/notifications/unsubscribe/AIDOW604hmNJwoJWftboytLN2fjWars2ks5qUcfPgaJpZM4JI3nn .

synergistics commented 8 years ago

Okay. So then actors aren't an inherent solution to the port naming problem because reactions can occur inside actors, not just between them, right?

chorasimilarity commented 8 years ago

I wrote that before and won't repeat again. In older programs I used a local port naming system. Just use concatenations of names of the ports which are in the rewrite pattern before the move.

On Tue, Jul 12, 2016 at 11:07 PM, synergistics notifications@github.com wrote:

Okay. So then actors aren't an inherent solution to the port naming problem because reactions can occur inside actors, not just between them, right?

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/chorasimilarity/chemlambda-gui/issues/4#issuecomment-232163817, or mute the thread https://github.com/notifications/unsubscribe/AIDOWwa4Z8kX33VlJ1l0OkP92QBWvOL5ks5qU_QIgaJpZM4JI3nn .

synergistics commented 8 years ago

Alright. I wasn't sure because when you mentioned actors as an "alternative," I was unclear on what exactly they'd be an alternative to. As we moved away from the topic of naming, that was still a bit ambiguous. Thank you for the clarification.

chorasimilarity commented 8 years ago

Is OK. Locality itself is a matter of definition. One can easily imagine concrete situations where the extreme locality considered in chemlambda may be relaxed, like for the example with the actors, where inside of an actor state is the actor business to ensure good naming of ports, externally there are always non-local (but algorithmic) procedures for naming the bonds between nodes of different actors, but otherwise all rewrites and the colors of the new nodes are decided locally. Or, another example, suppose that we take as given an algorithm, call it "physics", which takes as input the initial molecule (a pure graph theoretic object) and an embedding of this graph into a space X. Suppose also, for the sake of the discussion, that we accept a notion of global time variable and that the physics algorithm produces a time-indexed embedding of the graph (i.e. how the molecule moves in X, when it's not rewritten). Now, suppose that we add to the rewrite a condition which says that the rewrite is possible only if the embedding given by the physics allows it (to model, say, the fact that some chemical reactions cannot happen unless there's some spatial conditions for them too, relative to the "shape" of the graph in X). Then we may still talk about locality of rewrites, but relative to the physics algorithm. The advantage of the physics algorithm is that it gives good port names (positions in X). For example I make the whole program in javascript. D3.js gives me the physics and I'll add some random moving nodes which represent the enzymes and I allow only rewrites when the enzymes are close enough to the rewrite pattern.

Of course that's a digression which may lead us to tons of discussions. But it shows that locality is indeed a serious thing to think about. And it's not all or nothing, there are subtle degrees.

On Tue, Jul 12, 2016 at 11:56 PM, synergistics notifications@github.com wrote:

Alright. I wasn't sure because when you mentioned actors as an "alternative," I was unclear on what exactly they'd be an alternative to. As we moved away from the topic of naming, that was still a bit ambiguous. Thank you for the clarification.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/chorasimilarity/chemlambda-gui/issues/4#issuecomment-232178498, or mute the thread https://github.com/notifications/unsubscribe/AIDOW-OgeLoeuNB4ZLwRUdX_WI65_HA0ks5qU_9qgaJpZM4JI3nn .

chorasimilarity commented 8 years ago

I see your progress at https://github.com/synergistics/chemlambda-hask . Currently I can't play with it because objective reasons but please let me know if/when it's working and news, thank you!

On Wed, Jul 13, 2016 at 12:21 AM, Marius Buliga marius.buliga@gmail.com wrote:

Is OK. Locality itself is a matter of definition. One can easily imagine concrete situations where the extreme locality considered in chemlambda may be relaxed, like for the example with the actors, where inside of an actor state is the actor business to ensure good naming of ports, externally there are always non-local (but algorithmic) procedures for naming the bonds between nodes of different actors, but otherwise all rewrites and the colors of the new nodes are decided locally. Or, another example, suppose that we take as given an algorithm, call it "physics", which takes as input the initial molecule (a pure graph theoretic object) and an embedding of this graph into a space X. Suppose also, for the sake of the discussion, that we accept a notion of global time variable and that the physics algorithm produces a time-indexed embedding of the graph (i.e. how the molecule moves in X, when it's not rewritten). Now, suppose that we add to the rewrite a condition which says that the rewrite is possible only if the embedding given by the physics allows it (to model, say, the fact that some chemical reactions cannot happen unless there's some spatial conditions for them too, relative to the "shape" of the graph in X). Then we may still talk about locality of rewrites, but relative to the physics algorithm. The advantage of the physics algorithm is that it gives good port names (positions in X). For example I make the whole program in javascript. D3.js gives me the physics and I'll add some random moving nodes which represent the enzymes and I allow only rewrites when the enzymes are close enough to the rewrite pattern.

Of course that's a digression which may lead us to tons of discussions. But it shows that locality is indeed a serious thing to think about. And it's not all or nothing, there are subtle degrees.

On Tue, Jul 12, 2016 at 11:56 PM, synergistics notifications@github.com wrote:

Alright. I wasn't sure because when you mentioned actors as an "alternative," I was unclear on what exactly they'd be an alternative to. As we moved away from the topic of naming, that was still a bit ambiguous. Thank you for the clarification.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/chorasimilarity/chemlambda-gui/issues/4#issuecomment-232178498, or mute the thread https://github.com/notifications/unsubscribe/AIDOW-OgeLoeuNB4ZLwRUdX_WI65_HA0ks5qU_9qgaJpZM4JI3nn .

synergistics commented 8 years ago

Haha sure thing man. I'm not sure how long it will take, but I've almost finished the standard rewrite algorithm. There probably won't be too much to play with for a bit since I've been building the core like a library and haven't done anything involving user interaction yet. Sooner than a full graphical interface of course, you'll at least be able to get a textual output for a mol file reaction. Looking forward to all the progress to be made. This is just the start.

chorasimilarity commented 8 years ago

Great, the library style is clearly better!

On Wed, Jul 20, 2016 at 6:05 PM, synergistics notifications@github.com wrote:

Haha sure thing man. I'm not sure how long it will take, but I've almost finished the standard rewrite algorithm. There probably won't be too much to play with for a bit since I've been building the core like a library and haven't done anything involving user interaction yet. Sooner than a full graphical interface of course, you'll at least be able to get a textual output for a mol file reaction. Looking forward to all the progress to be made. This is just the start.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/chorasimilarity/chemlambda-gui/issues/4#issuecomment-233977899, or mute the thread https://github.com/notifications/unsubscribe-auth/AIDOW_cpVIniTXV-1FnL3ynHQ8Lno4OLks5qXjkdgaJpZM4JI3nn .

chorasimilarity commented 8 years ago

Hi, I'll open soon an issue at your chemlambda-hask, but for the moment I comment here. Thank you for your haskell repo! Here are some mol files to try with your programs. All of them come from lambda terms and they have a normal form, so the computation stops:

To check some of the moves, an useful file is the one about the shuffle trick https://github.com/chorasimilarity/chemlambda-gui/blob/gh-pages/dynamic/mol/shuffle_trick.mol

Other remarks:

Thank you again, please tell me what do you need more, here or by mail, or we talk more later.

On Wed, Jul 20, 2016 at 8:15 PM, Marius Buliga marius.buliga@gmail.com wrote:

Great, the library style is clearly better!

On Wed, Jul 20, 2016 at 6:05 PM, synergistics notifications@github.com wrote:

Haha sure thing man. I'm not sure how long it will take, but I've almost finished the standard rewrite algorithm. There probably won't be too much to play with for a bit since I've been building the core like a library and haven't done anything involving user interaction yet. Sooner than a full graphical interface of course, you'll at least be able to get a textual output for a mol file reaction. Looking forward to all the progress to be made. This is just the start.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/chorasimilarity/chemlambda-gui/issues/4#issuecomment-233977899, or mute the thread https://github.com/notifications/unsubscribe-auth/AIDOW_cpVIniTXV-1FnL3ynHQ8Lno4OLks5qXjkdgaJpZM4JI3nn .

synergistics commented 8 years ago

Thanks for the linking the mol files to work with. That brings up a question I was going to ask you actually. Do you have any links to the resulting molecules after the full rewrite had been run on a graph? If not, what would be the best way of getting these. This would greatly help with testing my version so I have something to compare my results to.

Handling conflicting matches

Currently, I'm able to write multiple methods of handling conflicting pattern since I made a general library as the basis of this project. I was actually thinking that eventually we could have a general enough system that others could contribute not only molecules that follow the existing rules, but their very own rules and logic. However for now, the project has a general enough foundation that many algorithms can be made. If you check out the Standard directory under src/Chemlambda, you'll find the "standard" enzymes, and patterns that correspond to your definitions.

Here I've defined a rewrite algorithm that's given a list of lists of enzymes. standardEnzymes is ordered by the priority of the each enzyme. Each inner list indicates the enzymes that have the same priority. So if we consider the priorities going from 0-5 in correspondence to the indices of the standardEnzymes, [ distAEnzyme, distLEnzyme, distFIEnzyme ] all have a priority of 1, the second highest while [betaEnzyme, fanInEnzyme] both have the priority of 2. The rewrite algorithm is split into two conceptual parts: finding all of the left patterns in the graph, and adding back all the right patterns resulting from the left patterns being reacted. The left pattern matching part (priorityBasedReactionSites in Chemlamda.Standard.Rewrite) handles the conflicting patterns by not allowing any to exist in the first place! It does the following given this list and a graph (call it g) to rewrite:

  1. Take the first list of the list (standardEnzymes in this case), call it es (short for "current enzymes" and just for convenience).
  2. Since the enzymes in es can be run without conflicting, hence having the same priority, get the list of reaction sites that result from matching the patterns of the enzymes in g. A reaction site btw is just a pair of the matched subgraph in g, and the move to be run on it. It's a product of the two. So when you run, say, the beta enzyme over a graph, you get a list of things that look like this:

    ReactionSite ( Graph [Node L [1,2,3], Node A [3,4,5]] ) betaMove

    which is like a tuple holding the matched graph and the move that takes that graph and returns the Right Pattern in its context.

    So if es was [betaEnzyme, fanInEnzyme], it might return the reaction sites with the subgraphs of:

    [ Graph [ Node L  [1,2,3], Node A [3,4,5] ],
     Graph [ Node L  [5,6,7], Node A [7,8,9] ],
     Graph [ Node FI [10 11 12], Node FOE [12, 13,14] ]

    where each element is the matching subgraph in some graph with those nodes.

  3. For each subgraph in the list, do the following

    a. Remove the nodes of the subgraph from g b. Run the enzyme's move on the subgraph to produce a new subgraph to be added back into g (i.e. the Right Pattern).

  4. After all the matched nodes are removed from g (call the new graph g'), repeat back from step 1 using the tail of the list of enzymes and g'.

This algorithm was inspired by your comment in the chemlambda moves page that said for each pattern, "block the nodes" and match the next patterns on the rest of the graph. That's exactly what I've done here by making the nodes that were matched in previous patterns inaccessible (at least while pattern matching) to following patterns by removing them from the graph on which the following patterns are matched. So if some A atom for example was involved in a distA and beta move, only the distA would be able to match it because by the time we got to the beta pattern, it would be "invisible".

This approach is subject to change and criticism. Things are gonna get really interesting when I start implementing parallelism on the matching and readding of nodes.

Random rewrites

Due to the flexibility of the system, I can build a rewrite algorithm that takes each match from above and run a predicate function on it that determines whether that site will be reacted or not. The predicate function could do something like return true if rand(10) is <= 5. Get the gist? (And that's just pseudocode, but it sort of looks like python, hehe).

:P

As I develop the project more, there will of course be lots more to explain, so bring on the questions! (I will to you too because there's a ton to learn about this stuff). Thanks for taking interest in the project and tell me if anything here was unclear!

Oh I thought of a question!

Can you tell me at some point about the random algorithm how it's different in nature from an algorithm that runs all matches. Is this randomness to simulate nature in some way? What are the effects of making the algorithm random rather than completely deterministic? Through all my looking through chemlambda (not really that much yet), this has been one of the most interesting things to me. Your "stupid" algorithm. Hehe.

Another thing. I'm not totally convinced of the applications of bringing chemlambda into the real world with real molecules and why that would be helpful but I've been speculating a bit. One idea would be encoding computations into materials for making materials that compute their shape or something like that based on some stimulus. You probably have a lot more ideas and I'd love to hear them because I'm really excited to see chemlambda in the real world and where it can go. As I learn more about the formalism, I'll be better able to come up with my own ideas for how chemlambda might be useful. Maybe this question should go into another issue though?

chorasimilarity commented 8 years ago

I'll try to answer to what I can right now and after I'll come back to the rest.

  1. The enzymes are the engines of the computation, like for example the head of a Turing machine is in the TM model of computation. I mentioned the Algorithmic Chemistry of Fontana and Buss as being close to chemlambda, but actually a closer model is the class studied by Christoph Flamm (take a look http://www.tbi.univie.ac.at/~xtof/papers.html ) which can be described in the following way: molecules are graphs (patterns) and rewrites have the form

    A+B - - > C+D

the rewrites being random. This can be studied in the framework of a chemical reaction network, but it has two problems: (a) the chemical reaction network associated to an initial molecule explodes, typically, in time, (b) this type of rewrites can be understood as looking for the left pattern (A+B) as made by two sub-patterns A and B which are not connected one with the other, then perform the rewrite, or this means that one has to search for pairs of patterns on the graph before making the rewrite.

In chemlambda the rewrite is

enzyme + A - - > enzyme + B

which simplifies a lot the search (only for pattern A) and eliminates the explosion of complexity of a chemical reaction network.

  1. A graph molecule is given as a list of nodes, i.e. a mol file. The order of the list should not matter, nor the order of possible rewrites, correct? That is why the rewrite algorithm should reflect that.
  2. The randomness is also related to the asynchronicity. Imagine that we want to model the situation where the molecule M is reduced in two places, in parallel. Take the M as a mol file and partition it into M1 and M2. These two are also valid mol files, so we give M1 to one computer, M2 to another and we keep a correspondence between the bonds between nodes which are on different computers, we discussed previously about this. Now, there is no control over the global order of rewrites, so this can be modeled as a random reduction of M (and a system like colour actors, etc).
  3. I take for the deterministic algorithm the script called by bash moving_randommetabo.sh from chemlambda-gui, with the wei parameters set to 0 (these wei_parameters are like what you describe in the Random rewrites paragraph) . It works like this. The DIST rewrites have higher priority because in the algorithm there is first a search-and-block for those first.
  4. There is a random version which is almost correct, namely make in the same script the wei_ parameters greater than 0
  5. The correct version for the random rewrites is, I think, the one from quiner_shuffle.sh. Notice that any pattern in chemlambda is a pair of nodes linked by a bond. So, first shuffle the list of bonds. Then use the shuffled list to greedily select a maximal list of bonds such hat no two bonds have a node in common. Then proceed like in 4.
  6. As for testing purposes, the first versions of the programs did the rewrites step by step, saving the results in a json file, see http://imar.ro/~mbuliga/gallery.html
  7. Although chemlambda is not especially about lambda calculus, it would be interesting to seriously compare reduction strategies in lambda calculus with rewrite strategies in chemlambda, for molecules coming from lambda calculus. By this I mean the following.

    (a) write a lambda2mol converting program

    (b) write a mol2lambda program, but attention that this should take as input a mol file and return a list of lambda terms, one for each bond of the molecule. This is because many molecules do not admit a global decoration of bonds with lambda terms, such that obvious local rules are respected. For example if you have a node A 1 2 3 and we denote by u[1], u[2] and u[3] the decorations on the bonds, then a local rule for the node A is that u[3] = u[1] u[2]. Same idea for the nodes L and FO, with problems for the nodes FI and FOE (maybe FOE like FO, but FI does not have an obvious choice of local rule). OK, but write one, any one.

Btw, related is the discussion here https://github.com/MaiaVictor/optlam/issues/1

(c) compare the reduction of a lambda term, by a given strategy, with the chemlambda reduction, by a given priority of rewrites, deterministic.

On Mon, Jul 25, 2016 at 4:29 AM, synergistics notifications@github.com wrote:

Thanks for the linking the mol files to work with. That brings up a question I was going to ask you actually. Do you have any links to the resulting molecules after the full rewrite had been run on it? If not, what would be the best way of getting these. This would greatly help with testing my version so I have something to compare my results to. Handling conflicting matches

Currently, I'm able to write multiple methods of handling conflicting pattern since I made a general library as the basis of this project. I was actually thinking that eventually we could have a general enough system that others could contribute not only molecules that follow the existing rules, but their very own rules and logic. However for now, the project has a general enough foundation that many algorithms can be made. If you check out the Standard directory under src/Chemlambda, you'll find the "standard" enzymes, and patterns that correspond to your definitions.

Here I've defined a rewrite algorithm that's given a list of lists of enzymes https://github.com/synergistics/chemlambda-hask/blob/master/src/Chemlambda/Standard/Enzymes.hs#L25-L33. standardEnzymes is ordered by the priority of the each enzyme. Each inner list indicates the enzymes that have the same priority. So if we consider the priorities going from 0-5 in correspondence to the indices of the standardEnzymes, [ distAEnzyme, distLEnzyme, distFIEnzyme ] all have a priority of 1, the second highest while [betaEnzyme, fanInEnzyme] both have the priority of 2. The rewrite algorithm is split into two conceptual parts: finding all of the left patterns in the graph, and adding back all the right patterns resulting from the left patterns being reacted. The left pattern matching part (priorityBasedReactionSites in Chemlamda.Standard.Rewrite) handles the conflicting patterns by not allowing any to exist in the first place! It does the following given this list and a graph (call it g) to rewrite:

1.

Take the first list of the list (standardEnzymes in this case), call it es (short for "enzymes" and just for convenience). 2.

Since the enzymes in es can be run without conflicting, hence having the same priority, get the list of reaction sites that result from matching the patterns of the enzymes in g. A reaction site btw is just a pair of the matched subgraph in g, and the move to be run on it. It's a product of the two. So if es was [betaEnzyme, fanInEnzyme], it might return the reaction sites with the subgraphs of:

[ Graph [ Node L [1,2,3], Node A [3,4,5] ], Graph [ Node L [5,6,7], Node A [7,8,9] ], Graph [ Node FI [10 11 12], Node FOE [12, 13,14] ]

where each element is the matching subgraph in some graph with those nodes. 3.

For each subgraph in the list, do the following

a. Remove the nodes of the subgraph from g b. Run the enzyme's move on the subgraph to produce a new subgraph to be added back into g (i.e. the Right Pattern). 4.

After all the matched nodes are removed from g (call the new graph g'), repeat back from step 1 using the tail of the list of enzymes and g'.

This algorithm was inspired by your comment in the chemlambda moves page that said for each pattern, "block the nodes" and match the next patterns on the rest of the graph. That's exactly what I've done here by making the nodes that were matched in previous patterns inaccessible (at least while pattern matching) to following patterns by removing them from the graph on which the following patterns are matched. So if some A atom for example was involved in a distA and beta move, only the distA would be able to match it because by the time we got to the beta pattern, it would be "invisible".

This approach is subject to change and criticism. Things are gonna get really interesting when I start implementing parallelism on the matching and readding of nodes. Random rewrites

Due to the flexibility of the system, I can build a rewrite algorithm that takes each match from above and run a predicate function on it that determines whether that site will be reacted or not. The predicate function could do something like return true if rand(10) is <= 5. Get the gist? (And that's just pseudocode, but it sort of looks like python, hehe). :P

As I develop the project more, there will of course be lots more to explain, so bring on the questions! (I will to you too because there's a ton to learn about this stuff). Thanks for taking interest in the project and tell me if anything here was unclear! Oh I thought of a question!

Can you tell me at some point about the random algorithm how it's different in nature from an algorithm that runs all matches. Is this randomness to simulate nature in some way? What are the effects of making the algorithm random rather than completely deterministic? Through all my looking through chemlambda (not really that much yet), this has been one of the most interesting things to me. Your "stupid" algorithm. Hehe.

Another thing. I'm not totally convinced of the applications of bringing chemlambda into the real world with real molecules and why that would be helpful but I've been speculating a bit. One idea would be encoding computations into materials for making materials that compute their shape or something like that based on some stimulus. You probably have a lot more ideas and I'd love to hear them because I'm really excited to see chemlambda in the real world and where it can go. Maybe this question should go into another issue though?

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/chorasimilarity/chemlambda-gui/issues/4#issuecomment-234817586, or mute the thread https://github.com/notifications/unsubscribe-auth/AIDOW5qwy6YEIMHcHnSdaesCa3huO-xEks5qZBGMgaJpZM4JI3nn .

chorasimilarity commented 8 years ago

Hi, I cleaned up a bit the chemlambda-gui repository and made a folder https://github.com/chorasimilarity/chemlambda-gui/tree/gh-pages/dynamic/test which can be used for testing purposes wrt chemlambda-hask.

It works like this. I modified the scripts for the deterministic algorithm. If you copy the repository https://github.com/chorasimilarity/chemlambda-gui/tree/gh-pages/dynamic then you go to the test folder, do the following (for example)

The file tempo_0.mol is the input mol file (in this case ackermann_2_2.mol) but with FRIN, FROUT nodes added, if needed, and with a more economic renaming of the port variables (based on a counter).

The rest of the tempo_*.mol files are the mol files of the intermediate and final steps.

The sta.txt file is a rough statistics of the number and type of rewrites.

I hope this can be used for comparing the results of chemlambda-hask with those of chemlambda-gui.

Please tell me if you can use it or otherwise what you need!

On Mon, Jul 25, 2016 at 10:11 AM, Marius Buliga marius.buliga@gmail.com wrote:

I'll try to answer to what I can right now and after I'll come back to the rest.

  1. The enzymes are the engines of the computation, like for example the head of a Turing machine is in the TM model of computation. I mentioned the Algorithmic Chemistry of Fontana and Buss as being close to chemlambda, but actually a closer model is the class studied by Christoph Flamm (take a look http://www.tbi.univie.ac.at/~xtof/papers.html ) which can be described in the following way: molecules are graphs (patterns) and rewrites have the form

    A+B - - > C+D

the rewrites being random. This can be studied in the framework of a chemical reaction network, but it has two problems: (a) the chemical reaction network associated to an initial molecule explodes, typically, in time, (b) this type of rewrites can be understood as looking for the left pattern (A+B) as made by two sub-patterns A and B which are not connected one with the other, then perform the rewrite, or this means that one has to search for pairs of patterns on the graph before making the rewrite.

In chemlambda the rewrite is

enzyme + A - - > enzyme + B

which simplifies a lot the search (only for pattern A) and eliminates the explosion of complexity of a chemical reaction network.

  1. A graph molecule is given as a list of nodes, i.e. a mol file. The order of the list should not matter, nor the order of possible rewrites, correct? That is why the rewrite algorithm should reflect that.
  2. The randomness is also related to the asynchronicity. Imagine that we want to model the situation where the molecule M is reduced in two places, in parallel. Take the M as a mol file and partition it into M1 and M2. These two are also valid mol files, so we give M1 to one computer, M2 to another and we keep a correspondence between the bonds between nodes which are on different computers, we discussed previously about this. Now, there is no control over the global order of rewrites, so this can be modeled as a random reduction of M (and a system like colour actors, etc).
  3. I take for the deterministic algorithm the script called by bash moving_randommetabo.sh from chemlambda-gui, with the wei parameters set to 0 (these wei_parameters are like what you describe in the Random rewrites paragraph) . It works like this. The DIST rewrites have higher priority because in the algorithm there is first a search-and-block for those first.
  4. There is a random version which is almost correct, namely make in the same script the wei_ parameters greater than 0
  5. The correct version for the random rewrites is, I think, the one from quiner_shuffle.sh. Notice that any pattern in chemlambda is a pair of nodes linked by a bond. So, first shuffle the list of bonds. Then use the shuffled list to greedily select a maximal list of bonds such hat no two bonds have a node in common. Then proceed like in 4.
  6. As for testing purposes, the first versions of the programs did the rewrites step by step, saving the results in a json file, see http://imar.ro/~mbuliga/gallery.html
  7. Although chemlambda is not especially about lambda calculus, it would be interesting to seriously compare reduction strategies in lambda calculus with rewrite strategies in chemlambda, for molecules coming from lambda calculus. By this I mean the following.

    (a) write a lambda2mol converting program

    (b) write a mol2lambda program, but attention that this should take as input a mol file and return a list of lambda terms, one for each bond of the molecule. This is because many molecules do not admit a global decoration of bonds with lambda terms, such that obvious local rules are respected. For example if you have a node A 1 2 3 and we denote by u[1], u[2] and u[3] the decorations on the bonds, then a local rule for the node A is that u[3] = u[1] u[2]. Same idea for the nodes L and FO, with problems for the nodes FI and FOE (maybe FOE like FO, but FI does not have an obvious choice of local rule). OK, but write one, any one.

Btw, related is the discussion here https://github.com/MaiaVictor/optlam/issues/1

(c) compare the reduction of a lambda term, by a given strategy, with the chemlambda reduction, by a given priority of rewrites, deterministic.

On Mon, Jul 25, 2016 at 4:29 AM, synergistics notifications@github.com wrote:

Thanks for the linking the mol files to work with. That brings up a question I was going to ask you actually. Do you have any links to the resulting molecules after the full rewrite had been run on it? If not, what would be the best way of getting these. This would greatly help with testing my version so I have something to compare my results to. Handling conflicting matches

Currently, I'm able to write multiple methods of handling conflicting pattern since I made a general library as the basis of this project. I was actually thinking that eventually we could have a general enough system that others could contribute not only molecules that follow the existing rules, but their very own rules and logic. However for now, the project has a general enough foundation that many algorithms can be made. If you check out the Standard directory under src/Chemlambda, you'll find the "standard" enzymes, and patterns that correspond to your definitions.

Here I've defined a rewrite algorithm that's given a list of lists of enzymes https://github.com/synergistics/chemlambda-hask/blob/master/src/Chemlambda/Standard/Enzymes.hs#L25-L33. standardEnzymes is ordered by the priority of the each enzyme. Each inner list indicates the enzymes that have the same priority. So if we consider the priorities going from 0-5 in correspondence to the indices of the standardEnzymes, [ distAEnzyme, distLEnzyme, distFIEnzyme ] all have a priority of 1, the second highest while [betaEnzyme, fanInEnzyme] both have the priority of 2. The rewrite algorithm is split into two conceptual parts: finding all of the left patterns in the graph, and adding back all the right patterns resulting from the left patterns being reacted. The left pattern matching part (priorityBasedReactionSites in Chemlamda.Standard.Rewrite) handles the conflicting patterns by not allowing any to exist in the first place! It does the following given this list and a graph (call it g) to rewrite:

1.

Take the first list of the list (standardEnzymes in this case), call it es (short for "enzymes" and just for convenience). 2.

Since the enzymes in es can be run without conflicting, hence having the same priority, get the list of reaction sites that result from matching the patterns of the enzymes in g. A reaction site btw is just a pair of the matched subgraph in g, and the move to be run on it. It's a product of the two. So if es was [betaEnzyme, fanInEnzyme], it might return the reaction sites with the subgraphs of:

[ Graph [ Node L [1,2,3], Node A [3,4,5] ], Graph [ Node L [5,6,7], Node A [7,8,9] ], Graph [ Node FI [10 11 12], Node FOE [12, 13,14] ]

where each element is the matching subgraph in some graph with those nodes. 3.

For each subgraph in the list, do the following

a. Remove the nodes of the subgraph from g b. Run the enzyme's move on the subgraph to produce a new subgraph to be added back into g (i.e. the Right Pattern). 4.

After all the matched nodes are removed from g (call the new graph g'), repeat back from step 1 using the tail of the list of enzymes and g'.

This algorithm was inspired by your comment in the chemlambda moves page that said for each pattern, "block the nodes" and match the next patterns on the rest of the graph. That's exactly what I've done here by making the nodes that were matched in previous patterns inaccessible (at least while pattern matching) to following patterns by removing them from the graph on which the following patterns are matched. So if some A atom for example was involved in a distA and beta move, only the distA would be able to match it because by the time we got to the beta pattern, it would be "invisible".

This approach is subject to change and criticism. Things are gonna get really interesting when I start implementing parallelism on the matching and readding of nodes. Random rewrites

Due to the flexibility of the system, I can build a rewrite algorithm that takes each match from above and run a predicate function on it that determines whether that site will be reacted or not. The predicate function could do something like return true if rand(10) is <= 5. Get the gist? (And that's just pseudocode, but it sort of looks like python, hehe). :P

As I develop the project more, there will of course be lots more to explain, so bring on the questions! (I will to you too because there's a ton to learn about this stuff). Thanks for taking interest in the project and tell me if anything here was unclear! Oh I thought of a question!

Can you tell me at some point about the random algorithm how it's different in nature from an algorithm that runs all matches. Is this randomness to simulate nature in some way? What are the effects of making the algorithm random rather than completely deterministic? Through all my looking through chemlambda (not really that much yet), this has been one of the most interesting things to me. Your "stupid" algorithm. Hehe.

Another thing. I'm not totally convinced of the applications of bringing chemlambda into the real world with real molecules and why that would be helpful but I've been speculating a bit. One idea would be encoding computations into materials for making materials that compute their shape or something like that based on some stimulus. You probably have a lot more ideas and I'd love to hear them because I'm really excited to see chemlambda in the real world and where it can go. Maybe this question should go into another issue though?

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/chorasimilarity/chemlambda-gui/issues/4#issuecomment-234817586, or mute the thread https://github.com/notifications/unsubscribe-auth/AIDOW5qwy6YEIMHcHnSdaesCa3huO-xEks5qZBGMgaJpZM4JI3nn .

synergistics commented 8 years ago

Thanks for putting in the effort! It's really appreciated. This is really what I needed for testing so yea, thanks for the help. I'll probably start playing with this tonight!

In addition, the random version of the algorithm is almost complete. We can talk about it once it's done.

Lastly, when you do get the time, I'd be really interested to hear about how you see chemlambda being used in the real world. I've read your vision page and the stuff on the MicrobiomeOS, but it's still not clicking with me completely. With that, it would be easier for me to start brainstorming about the future of chemlambda which just leads to more innovation. It's great!

chorasimilarity commented 8 years ago

I'm really eager to see chemlambda-hask at work! It looks great, we should talk more about what can we do with all that.

On Mon, Aug 1, 2016 at 2:05 AM, synergistics notifications@github.com wrote:

Thanks for putting in the effort! It's really appreciated. This is really what I needed for testing so yea, thanks for the help. I'll probably start playing with this tonight!

In addition, the random version of the algorithm is almost complete. We can talk about it once it's done.

Lastly, when you do get the time, I'd be really interested to hear about how you see chemlambda being used in the real world. I've read your vision page and the stuff on the MicrobiomeOS, but it's still not clicking with me completely. With that, it would be easier for me to start brainstorming about the future of chemlambda which just leads to more innovation. It's great!

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/chorasimilarity/chemlambda-gui/issues/4#issuecomment-236462349, or mute the thread https://github.com/notifications/unsubscribe-auth/AIDOW7zpIWxgdyz1fOrH86bIrW-ySpa4ks5qbSoxgaJpZM4JI3nn .

chorasimilarity commented 3 years ago

The official page of all chemlambda projects is https://chemlambda.github.io/index.html

The repository chemlambda-gui is kept because of the content, otherwise, for new experiments, go to the official page.