search

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

What is the simplest demo of chemlambda? #6

Closed shadiakiki1986 closed 3 years ago

shadiakiki1986 commented 5 years ago

Hello. Thanks for sharing this awesome package! I'm trying it out, but some of the models have a lot of atoms/molecules and make it difficult for me to understand. Do you have "hello world" example for chemlambda that I can start with? I realize you have lots of examples on your demos page, but it's being difficult for me to understand what's going on in the animation. Is one of the examples a particularly simple one that I can start with?

chorasimilarity commented 5 years ago

Hi, thanks for the interest. Not sure what you look for. This page may help: http://imar.ro/~mbuliga/chemlambda-v2.html There is also this visual tutorial: http://imar.ro/~mbuliga/chemlambda_story.html Then there is this page where all the sources are tagged with the version of chemlambda: http://imar.ro/~mbuliga/buliga_sim.html

If the notation and the model are clear, then a very simple place to start would be https://github.com/chorasimilarity/chemlambda-gui/blob/gh-pages/dynamic/mol/letbeta.mol Can you anticipate how it reduces? If so, how can you modify it to transform into (\x.x)B ?

Another easy one is https://github.com/chorasimilarity/chemlambda-gui/blob/gh-pages/dynamic/mol/skk.mol which is the lambda term for SKK, should reduce to I. Can you write the K combinator, then write KAB and see how it reduces?

The shuffle trick is important https://github.com/chorasimilarity/chemlambda-gui/blob/gh-pages/dynamic/mol/shuffle_trick.mol Can you anticipate how it reduces? It is the mechanism which allows duplications of molecules inspired from lambda terms.

One thing I never did, but it would be very useful, is a program which turns lambda terms into the chemlambda molecule version.

For the passage from GLC to chemlambda see also the thread of posts starting with https://chorasimilarity.wordpress.com/2019/01/21/graphic-lambda-calculus-and-chemlambda-i/

On 4/3/19, Shadi Akiki notifications@github.com wrote:

Hello. Thanks for sharing this awesome package! I'm trying it out, but some of the models have a lot of atoms/molecules and make it difficult for me to understand. Do you have "hello world" example for chemlambda that I can start with? I realize you have lots of examples on your demos page, but it's being difficult for me to understand what's going on in the animation. Is one of the examples a particularly simple one that I can start with?

-- You are receiving this because you are subscribed to this thread. Reply to this email directly or view it on GitHub: https://github.com/chorasimilarity/chemlambda-gui/issues/6

shadiakiki1986 commented 5 years ago

Thanks a lot for your reply. I will go through the links and get back to you. When you say the one thing you never did was a program that converts lambda terms to Chemlambda molecule version, do you mean the generation of the mol files?

On Thu, Apr 4, 2019, 00:31 Marius Buliga notifications@github.com wrote:

Hi, thanks for the interest. Not sure what you look for. This page may help: http://imar.ro/~mbuliga/chemlambda-v2.html There is also this visual tutorial: http://imar.ro/~mbuliga/chemlambda_story.html Then there is this page where all the sources are tagged with the version of chemlambda: http://imar.ro/~mbuliga/buliga_sim.html

If the notation and the model are clear, then a very simple place to start would be https://github.com/chorasimilarity/chemlambda-gui/blob/gh-pages/dynamic/mol/letbeta.mol Can you anticipate how it reduces? If so, how can you modify it to transform into (\x.x)B ?

Another easy one is

https://github.com/chorasimilarity/chemlambda-gui/blob/gh-pages/dynamic/mol/skk.mol which is the lambda term for SKK, should reduce to I. Can you write the K combinator, then write KAB and see how it reduces?

The shuffle trick is important

https://github.com/chorasimilarity/chemlambda-gui/blob/gh-pages/dynamic/mol/shuffle_trick.mol Can you anticipate how it reduces? It is the mechanism which allows duplications of molecules inspired from lambda terms.

One thing I never did, but it would be very useful, is a program which turns lambda terms into the chemlambda molecule version.

For the passage from GLC to chemlambda see also the thread of posts starting with https://chorasimilarity.wordpress.com/2019/01/21/graphic-lambda-calculus-and-chemlambda-i/

On 4/3/19, Shadi Akiki notifications@github.com wrote:

Hello. Thanks for sharing this awesome package! I'm trying it out, but some of the models have a lot of atoms/molecules and make it difficult for me to understand. Do you have "hello world" example for chemlambda that I can start with? I realize you have lots of examples on your demos page, but it's being difficult for me to understand what's going on in the animation. Is one of the examples a particularly simple one that I can start with?

-- You are receiving this because you are subscribed to this thread. Reply to this email directly or view it on GitHub: https://github.com/chorasimilarity/chemlambda-gui/issues/6

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

chorasimilarity commented 5 years ago

a program that converts lambda terms to Chemlambda molecule version, do you mean the generation of the mol files?

Yes, a parser from lambda terms to mol format. It's little more than lambda_term --> AST.

Btw, also a full js implementation instead of this awk-d3. Personally I am satisfied by this proof of principle (I am a mathematician, not a programmer) but I'd be happy to play with a full js version. I'm not sure that d3 is the right thing to use and I don't know what to use instead, excepting a whole rewrite of the physics and rendering. Too much for my abilities alone.

Also, have no idea how to generate stick-and-ring graphs like these https://chorasimilarity.wordpress.com/2019/03/22/small-graph-rewrite-systems-3/

shadiakiki1986 commented 5 years ago

Could you provide a few examples of transformations from lambda terms to mol format? I can use your examples as tests cases to test that my code to do the conversion works correctly

chorasimilarity commented 5 years ago

Sure:

shadiakiki1986 commented 5 years ago

How exactly do you plan to write out the original function? For example, for Ackermann (2,2), what exactly is the source text file that will be converted to the mol file? Is it for example the awk implementation of the function? Like http://rosettacode.org/wiki/Ackermann_function#AWK

On Sat, Apr 6, 2019, 21:11 Marius Buliga notifications@github.com wrote:

Sure:

https://github.com/chorasimilarity/chemlambda-gui/blob/gh-pages/dynamic/mol/omega.mol

https://github.com/chorasimilarity/chemlambda-gui/blob/gh-pages/dynamic/mol/ackermann_2_2.mol

  • Ackermann(3,2)

https://github.com/chorasimilarity/chemlambda-gui/blob/gh-pages/dynamic/mol/ackermann_3_2.mol

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

chorasimilarity commented 5 years ago

The Ackermann function is the lambda term Ack applied to the Church number 2 applier to the Church number 2, so Ack 2 2.

Ack is as defined in [1] page 12, see the example 46, p. 9-12. Church numbers as defined in [2]. The S^+ function from [1] is the successor as defined at p. 8 exercise 33, or the term SUCC as defined in [2].

The predecessor is the term PRED as defined in [2]. So pred(28) is PRED 28 with 28 the Church number 28.

The combinator S is the lambda term \x.\y.\z.((xz)(yz) . The combinator K is the lambda term \x\y.x .

[1] http://www.little-lisper.org/website/files/lambda-calculus-tutorial.pdf [2] https://en.wikipedia.org/wiki/Lambda_calculus#Arithmetic_in_lambda_calculus

shadiakiki1986 commented 5 years ago

I don't think I've made my previous point clear. The math behind the lambda calculus is already clear to me. If a parser from lambda terms to mol file is to be written, how will the lambda terms be written? For example, for ackermann(2,2), does it suffice to write a parser that converts the following text file:

a(2,2) = a(1, a(2,1))
  a(2,1) = a(1, a(2,0))
    a(2,0) = a(1,1)
      a(1,1) = a(0, a(1,0))
        a(1,0) = a(0,1)
          a(0,1) = 2
        a(1,0) = 2
      a(1,1) = a(0, 2)
        a(0,2) = 3
      a(1,1) = 3
    a(2,0) = 3
  a(2,1) = a(1, 3)
    a(1,3) = a(0, a(1,2))
      a(1,2) = a(0, a(1,1))
        a(1,1) = a(0, a(1,0))
          a(1,0) = a(0,1)
            a(0,1) = 2
          a(1,0) = 2
        a(1,1) = a(0, 2)
          a(0,2) = 3
        a(1,1) = 3
      a(1,2) = a(0, 3)
        a(0,3) = 4
      a(1,2) = 4
    a(1,3) = a(0, 4)
      a(0,4) = 5
    a(1,3) = 5
  a(2,1) = 5
a(2,2) = a(1, 5)
  a(1,5) = a(0, a(1,4))
    a(1,4) = a(0, a(1,3))
      a(1,3) = a(0, a(1,2))
        a(1,2) = a(0, a(1,1))
          a(1,1) = a(0, a(1,0))
            a(1,0) = a(0,1)
              a(0,1) = 2
            a(1,0) = 2
          a(1,1) = a(0, 2)
            a(0,2) = 3
          a(1,1) = 3
        a(1,2) = a(0, 3)
          a(0,3) = 4
        a(1,2) = 4
      a(1,3) = a(0, 4)
        a(0,4) = 5
      a(1,3) = 5
    a(1,4) = a(0, 5)
      a(0,5) = 6
    a(1,4) = 6
  a(1,5) = a(0, 6)
    a(0,6) = 7
  a(1,5) = 7
a(2,2) = 7

to the corresponding mol file?

PS: The above text was outputted with this

chorasimilarity commented 5 years ago

No, the mol file for A= Ack 2 2 is obtained from a conversion of the lambda term A to a chemlambda molecule. The mol file is not a recording of the reductions.

A mol file is an encoding for a graph called chemlambda molecule. Such a graph is made by 3-valent, 2-valent and 1-valent nodes. The 3-valent node types are A, L, FI, FO, FOE, there is only one 2-valent node type called Arrow (irrelevant for the conversion part) and the 1-valent node types are FRIN (i.e. free in) FROUT (i.e. free out) and T (termination). The FRIN and FROUT nodes are needed for the edges of the graph with either free source or free target and they are not needed in the mol version because the awk script adds them if needed.

The edges are oriented. Use any string which does not contain space or newline to label the edges, so that different edges have different labels. Imagine each edge as made of 2 half-edges and each node, for example each 3-valent node, as having associated 3 half-edges.

More precisely these graphs are "oriented fatgraphs", which in this setting just means that each node has an associated list of half-edges, not an associated set of half-edges.

In mol notation the graph is represented as a list of nodes. Each line of the mol file is for one node. Lines are separated by newline characters.

A line for a 3-valent node looks like this:

U a b c

where U is one of the "A" (application) "L" (lambda) "FI" (fanin) "FO" (fanout) "FOE" (external fanout) and a, b, c are labels of edges. In the mol notation a,b, c are called "port variables" and each position in the list of a node has a type which is a pair { left,right,middle} X {in,out}

It follows that in a mol file each label of an edge appears at most two times. Moreover, as the edge is oriented, that means an edge label which appears twice, has to appear once in a position which is of type (, in) and in another position which is of type (, out)

For the 3-valent nodes the types of the positions are:

U (middle,in) (left,out) (right,out) for U=L, FO, FOE

U (left,in) (right,in) (middle, out) for U=A, FI

For Ack 2 2, from the source [1] let

SUCC= \y.\z.\x.(z (y z x))

1 = \y.\x.(y x)

2 = \y.\x.(y (y x))

F = \a.\b.(SUCC b a 1)

Ack= \a.(a F SUCC)

A = Ack 2 2

The mol file of Ack 2 2 is obtained from the conversion of the lambda term A into mol format. The algorithm is described in [3] p. 12-15. Even if that article is about Graphic Lambda Calculus, it does not matter. Shortly said, the algorithm starts with a lambda term which has the variables eventually renamed so that there is no clash. Build the AST of the lambda term by using nodes of type L for lambda, nodes of type A for application. Mind that you use oriented edges and that the edge which represents "x" in \x.A has a peculiar orientation. For each variable x which occurs more than 1 time use a tree of FO nodes to multiply it (the algorithm does not specify which tree to use, it is interesting to have an option in the parser for this). In case of variables which appear from \x.A the tree of FO nodes starts from the edge of that L node. Otherwise there may be free variables and the tree will start from a free edge. In the case \x.A where x does not occur anywhere else add a T node at x.

[3] https://arxiv.org/pdf/1305.5786.pdf

shadiakiki1986 commented 5 years ago

Would you mind if instead of using your custom mol file format for specifying a graph in a file, I use the graphviz format? That's a more popular format that would have a lot of compatibility with other existing software to make life easier. To visualize the graph of pred(2), the following is the graphviz format

digraph G {
  "3" -> "L1"
  "2" -> "L1"
  "L1" -> "1"

  "2" -> "T"

  "6" -> "L2"
  "6 " -> "L2"
  "L2" -> "5"

  "4" -> "L3"
  "3" -> "L3"
  "L3" -> "7"

  "7" -> "L4"
  "8" -> "L4"
  "L4" -> "9"

  "10" -> "A1"
  "8" -> "A1"
  "A1" -> "11"

  "12" -> "A2"
  "11" -> "A2"
  "A2" -> "13"

  "13" -> "L5"
  "12" -> "L5"
  "L5" -> "14"

  "14" -> "L6"
  "10" -> "L6"
  "L6" -> "a43"

  "a42" -> "A3"
  "5" -> "A3"
  "A3" -> "4"

  "a03" -> "A4"
  "1" -> "A4"
  "A4" -> "a02"

  "a13" -> "FO1"
  "a11" -> "FO1"
  "FO1" -> "a03"

  "a11" -> "A5"
  "a02" -> "A5"
  "A5" -> "a12"

  "a43" -> "FO2"
  "a41" -> "FO2"
  "FO2" -> "a13"

  "a41" -> "A6"
  "a12" -> "A6"
  "A6" -> "a42"

}

Paste the above in http://www.webgraphviz.com/ for example to see it in the browser. It's straight-forward to imply the graphviz format from the .mol format in that each mol file row becomes 3 rows. I addes suffixes to the different A and L to distinguish them. Will update you on next step of converting from lambda terms to graphviz format (which can then go to mol format for using your awk files for validation).

chorasimilarity commented 5 years ago

No problem, excepting that there is not necessary to number the node types like "FO2". Why not json, I used it in a previous version.

shadiakiki1986 commented 5 years ago

Json would not permit circular graphs. Graphviz is already a popular syntax for specifying graphs, with plenty of libraries to support it. There even are packages that automatically convert function calls into a graphviz graph. I plan to try it out on lambda terms written in a programming language like python or haskell.

On Sun, Apr 7, 2019, 14:32 Marius Buliga notifications@github.com wrote:

No problem, excepting that there is not necessary to number the node types like "FO2". Why not json, I used it in a previous version.

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

chorasimilarity commented 5 years ago

Json would not permit circular graphs.

Not true. A mol file is a list of lists. That the graph has cycles or not is irrelevant.

It can be [["L","3","2","1"], ["T", "2"], ...] or even [{"node":"L", "middle.in":"3", "left.out":"2","right.out":"1"}, {"node":"T", "middle.in":"2"}, ...]

shadiakiki1986 commented 5 years ago

In fact you're right. But it would require a lot of custom code, whereas going with graphviz would allow the usage of a lot of pre-made code

On Sun, Apr 7, 2019, 17:11 Marius Buliga notifications@github.com wrote:

Json would not permit circular graphs.

Not true. A mol file is a list of lists. That the graph has cycles or not is irrelevant.

It can be [["L","3","2","1"], ["T", "2"], ...] or even [{"node":"L", "middle.in":"3", "left.out":"2","right.out":"1"}, {"node":"T", "middle.in":"2"}, ...]

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

chorasimilarity commented 5 years ago

I used your graphviz formatted version as you suggested previously. There are several problems with it.

  1. The orientation of edges is wrong. For the mol line

L 3 2 1

It should not be

"3" -> "L1" "2" -> "L1" "L1" -> "1"

but instead

"3" -> "L1" "L1" -> "2" "L1" -> "1"

(same for FO and FOE).

  1. The representation is wrong because the graphviz format is not for fatgraphs, only for graphs.

L 3 2 1 != L 2 3 1 (or any other permutation of ports)

For graphviz, it represents the same

"3" -> "L1" "2" -> "L1" "L1" -> "1"

(which is wrong from the pov of orientations anyway) and

"2" -> "L1" "3" -> "L1" "L1" -> "1"

It seems that it tries a bit to respect the order of the lines, but it fails, as it can be seen in the representation of the nodes L3 and L4. For the node L3, which in mol is L 4 3 7, it represents them in the trigonometric circular order. For the node L4, which in mol is L 7 8 9, it represents them in the opposite trigonometric circular order.

To see how this problem has been solved in the visualizations of chemlambda look at this old visual tutorial http://imar.ro/~mbuliga/chemlambda_story.html

The solution was to represent each port as a node, with color and radius coding for the type.

  1. The graph is not a force graph, which makes edges as short as possible. By chemlambda standards this is a small graph. I can easily visualize graphs with about 2500 3-valent nodes (see why 2500 later) and I want to visualize graphs with 10^5 or 10^6 nodes. Graphviz can't do more than about a hundred nodes, right?

  2. A small problem with "6" and "6 ". Btw I counter with a naming error I made, the file http://imar.ro/~mbuliga/pred_2.mol is really pred(3). I used it in this chemlambda v1 simulation (i.e. there is no FOE) http://imar.ro/~mbuliga/pred_3_is_2.html :)

The solution could be the same in graphviz, namely to use 4 nodes for a 3-valent chemlambda node. Let's suppose there are only 3-valent nodes in the graph and no free edges, to get an estimate. This means that a N nodes graph has (3/2)N edges.We use 4N nodes for visualization and (3/2)N+3N edges. With safari on macbook I was able to see reductions (so not only force graphs) for graphs with about 4N = 10 000 nodes. The awk scripts have no such limit.

Conclusion: I don't see what advantage has graphviz. I reccommend to read http://imar.ro/~mbuliga/chemlambda-v2.html With the condition that anyways you produce graphviz files from lambda terms in such a way that it respects the ports order and orientations, I can easily make a script which converts them to mol.

shadiakiki1986 commented 5 years ago

About pred(3), let's continue the discussion at this gist where you can also add comments. I updated the graphviz dot file there to reflect orientation of edges and left/middle/right structure of the A/L/etc.

shadiakiki1986 commented 5 years ago

@chorasimilarity I completed a first draft of the javascript parser of lambda calculus terms. You can find it here. Just wait a few seconds while the window loads, check the bottom right window pane, and follow the instructions there. It's still buggy though.

chorasimilarity commented 5 years ago

Thank you! I replied at the gist https://gist.github.com/shadiakiki1986/e215afed6308dad4036b33cef4c513ce about the structure of the mol.

On 4/9/19, Shadi Akiki notifications@github.com wrote:

@chorasimilarity I completed a first draft of the javascript parser of lambda calculus terms. You can find it here. Just wait a few seconds while the window loads, check the bottom right window pane, and follow the instructions there. It's still buggy though.

-- You are receiving this because you were mentioned. Reply to this email directly or view it on GitHub: https://github.com/chorasimilarity/chemlambda-gui/issues/6#issuecomment-481288831

chorasimilarity commented 5 years ago

Seen the parser, I have to understand the js. Question(s): why not jump directly to a chemlambda.js ? Once the parser works well in graphviz, what to do with it? How the rewrites happen in graphviz? What to do with big graphs?

shadiakiki1986 commented 5 years ago

why not jump directly to a chemlambda.js ? Once the parser works well in graphviz, what to do with it? How the rewrites happen in graphviz?

Maybe the next step after the parser of lambda terms would be to write up the initial modifications you descriped in your Apr 9 comment. Then maybe implement the rewrites that you have in awk.

What to do with big graphs?

The largest graph I tried was the pred(3). Are the larger graphs you mention coming from lambda calculus or are they unrelated?

chorasimilarity commented 5 years ago

A chemlambda.js would be great, if somebody does it then it can be used beyond the proof of principle.

A parser in itself would simplify the creation of graphs from lambda terms which then they could be modified in many ways. Whenever I see discussions about the utility of a visual programming environment I feel the need to say "but chemlambda can do more with graphs than with terms...".

With these pieces to play with then I'd try a graphical REPL.

On 4/12/19, Shadi Akiki notifications@github.com wrote:

why not jump directly to a chemlambda.js ? Once the parser works well in graphviz, what to do with it? How the rewrites happen in graphviz?

Maybe the next step after the parser of lambda terms would be to write up the initial modifications you descriped in your Apr 9 comment. Then maybe implement the rewrites that you have in awk.

What to do with big graphs?

The largest graph I tried was the pred(3). Are the larger graphs you mention coming from lambda calculus or are they unrelated?

-- You are receiving this because you were mentioned. Reply to this email directly or view it on GitHub: https://github.com/chorasimilarity/chemlambda-gui/issues/6#issuecomment-482493887

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.